📁 topics / 25-pastebin.md

#Design Pastebin / GitHub Gist

#1. Problem Statement & Clarifications

Pastebin / GitHub Gist is a content-sharing service that allows users to store and share plain text or code snippets via short, unique URLs. Users paste content, receive a shareable link, and anyone with the link can view the content. It is a deceptively simple system with interesting challenges around URL generation, storage optimization, and read-heavy traffic at scale.

#Functional Requirements

  1. Create Paste — Users submit text/code content (up to 10MB) and receive a unique short URL (e.g., paste.example.com/aB3xK9)
  2. Read Paste — Anyone with the URL can view the paste content with syntax highlighting
  3. Paste Expiration — Support configurable TTL: 10 minutes, 1 hour, 1 day, 1 week, 1 month, never (default: never)
  4. User Accounts (Optional) — Registered users can view their paste history, edit, and delete pastes
  5. Visibility Controls — Public (searchable), unlisted (link-only), private (owner-only)
  6. Syntax Highlighting — Auto-detect or manually select language for code rendering

#Non-Functional Requirements

Requirement Target
Read Latency P99 < 100ms for paste retrieval
Write Latency P99 < 200ms for paste creation
Availability 99.99% — shared links must always work
Scale 5M new pastes/day, 50M reads/day, 10:1 read:write ratio
Durability No data loss for non-expired pastes
URL Length 6–8 characters (base62 encoded)

#Out of Scope

#Assumptions

#2. Back-of-Envelope Estimation

#Traffic Estimates

New pastes/day:         5M
Reads/day:              50M (10:1 read:write)
Write QPS (avg):        5M / 86400 ≈ 58 QPS
Write QPS (peak 3x):   ~175 QPS
Read QPS (avg):         50M / 86400 ≈ 580 QPS
Read QPS (peak 3x):    ~1,750 QPS

#Storage Estimates

Avg paste size:         10KB
New storage/day:        5M × 10KB = 50GB/day
New storage/year:       50GB × 365 = 18.25TB/year
5-year total:           ~91TB (before expiration cleanup)
Active pastes (no-expire): ~60% of 5M/day × 365 × 5 = ~5.5B pastes
Metadata per paste:     ~500B (URL, timestamps, user_id, settings)
Metadata storage:       5.5B × 500B = 2.75TB

#URL Space Calculation

URL characters:         Base62 (a-z, A-Z, 0-9)
6-char URL:             62^6 = 56.8 Billion unique URLs
7-char URL:             62^7 = 3.5 Trillion unique URLs
8-char URL:             62^8 = 218 Trillion unique URLs

At 5M pastes/day:       6 chars sufficient for 31+ years
                        → Use 6-char URLs, upgrade to 7 when needed

#Bandwidth

Read bandwidth (avg):   580 × 10KB = 5.8 MB/s
Read bandwidth (peak):  1,750 × 10KB = 17.5 MB/s
Write bandwidth (avg):  58 × 10KB = 0.58 MB/s
Total:                  ~18 MB/s peak (very manageable)

#Cache Estimates

Hot pastes (24h):       5M pastes × 10KB = 50GB
Top 20% (Pareto):       1M × 10KB = 10GB
Cache size:             10–50GB Redis cluster (easily fits in memory)
Cache hit ratio:        90%+ (power-law distribution)

#3. API Design

#Create Paste

POST /api/v1/pastes
Authorization: Bearer <token>    // optional — anonymous pastes allowed

{
  "content": "def hello():\n    print('Hello, World!')",
  "title": "My Python Script",           // optional
  "language": "python",                   // optional, auto-detected if omitted
  "expiration": "1d",                     // 10m | 1h | 1d | 1w | 1M | never
  "visibility": "unlisted"               // public | unlisted | private
}

Response 201:
{
  "paste_id": "aB3xK9",
  "url": "https://paste.example.com/aB3xK9",
  "raw_url": "https://paste.example.com/raw/aB3xK9",
  "created_at": "2025-05-29T12:00:00Z",
  "expires_at": "2025-05-30T12:00:00Z",
  "visibility": "unlisted",
  "language": "python"
}

#Read Paste

GET /api/v1/pastes/{paste_id}

Response 200:
{
  "paste_id": "aB3xK9",
  "title": "My Python Script",
  "content": "def hello():\n    print('Hello, World!')",
  "language": "python",
  "created_at": "2025-05-29T12:00:00Z",
  "expires_at": "2025-05-30T12:00:00Z",
  "visibility": "unlisted",
  "view_count": 342,
  "author": {                             // null for anonymous
    "username": "john_doe",
    "user_id": "U123"
  }
}

Response 404: { "error": "paste_not_found" }    // expired or invalid
Response 403: { "error": "private_paste" }       // private + not owner

#Get Raw Content

GET /api/v1/pastes/{paste_id}/raw
Content-Type: text/plain

def hello():
    print('Hello, World!')

#Delete Paste (Owner only)

DELETE /api/v1/pastes/{paste_id}
Authorization: Bearer <token>

Response 204: No Content

#List User's Pastes

GET /api/v1/users/{user_id}/pastes?page=1&limit=20&sort=created_at_desc

Response 200:
{
  "pastes": [
    { "paste_id": "aB3xK9", "title": "My Python Script", "language": "python",
      "created_at": "...", "visibility": "unlisted", "view_count": 342 }
  ],
  "total": 47,
  "page": 1
}

#4. Data Model

#Paste Metadata Store (PostgreSQL — sharded by paste_id)

CREATE TABLE pastes (
  paste_id      VARCHAR(8) PRIMARY KEY,      -- base62 encoded short URL
  user_id       BIGINT NULL,                 -- NULL for anonymous pastes
  title         VARCHAR(255) NULL,
  language      VARCHAR(50) NULL,
  content_size  INT,                         -- bytes
  content_hash  VARCHAR(64),                 -- SHA-256 for dedup
  visibility    ENUM('public','unlisted','private') DEFAULT 'unlisted',
  expires_at    TIMESTAMP NULL,              -- NULL = never expires
  created_at    TIMESTAMP DEFAULT NOW(),
  view_count    BIGINT DEFAULT 0,
  is_deleted    BOOLEAN DEFAULT false
);

CREATE INDEX idx_pastes_user ON pastes(user_id, created_at DESC)
  WHERE user_id IS NOT NULL;
CREATE INDEX idx_pastes_expiry ON pastes(expires_at)
  WHERE expires_at IS NOT NULL AND is_deleted = false;
CREATE INDEX idx_pastes_public ON pastes(created_at DESC)
  WHERE visibility = 'public' AND is_deleted = false;

#Paste Content Store (Object Storage — S3 / MinIO)

Bucket: paste-content
Key:    {paste_id}           -- e.g., "aB3xK9"
Body:   <raw paste content, compressed with zstd if > 1KB>
Metadata:
  content-type:     text/plain
  content-encoding: zstd          // if compressed
  original-size:    10240

Why S3 over database?

#Content Deduplication (Optional — for popular content)

-- If same content is pasted multiple times, share the storage
CREATE TABLE content_store (
  content_hash  VARCHAR(64) PRIMARY KEY,   -- SHA-256
  s3_key        VARCHAR(100),               -- actual S3 object key
  ref_count     INT DEFAULT 1,
  content_size  INT,
  created_at    TIMESTAMP
);

#URL Key Store (Redis — cache layer)

Key:   paste:{paste_id}
Value: {
  "title":        "My Python Script",
  "language":     "python",
  "content_size": 10240,
  "visibility":   "unlisted",
  "user_id":      "U123",
  "s3_key":       "aB3xK9",
  "expires_at":   1716984000,
  "created_at":   1716897600
}
TTL: matches paste expiration, or 24h for non-expiring pastes (LRU eviction)

#Access Patterns

Query Store Index/Key
Get paste by ID Redis cache → PostgreSQL PK: paste_id
Get paste content S3 (via CDN/CloudFront) Key: paste_id
List user's pastes PostgreSQL IX: user_id + created_at DESC
Browse public pastes PostgreSQL IX: visibility + created_at DESC
Cleanup expired pastes PostgreSQL IX: expires_at
Check content dedup PostgreSQL PK: content_hash

#5. High-Level Design (HLD) & Scale Evolution

#Stage 1: MVP / Single Server (1K pastes/day)

#Stage 2: Growth Scale (500K pastes/day)

#Stage 3: Full Scale (5M pastes/day, 50M reads/day)

Target architecture with separated concerns and horizontal scalability.

#Architecture Diagram

                    ┌──────────────┐
                    │     CDN      │ ← Raw paste content + static assets
                    │ (CloudFront) │
                    └──────┬───────┘
                           │
                ┌──────────▼──────────┐
                │    API Gateway /     │
                │    Load Balancer     │
                │ (Rate limit, Auth)   │
                └──────────┬──────────┘
                           │
              ┌────────────┼────────────┐
              ▼            ▼            ▼
     ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
     │ Read Service  │ │ Write Service│ │ Cleanup      │
     │               │ │              │ │ Service      │
     │ • Get paste   │ │ • Create     │ │ (Cron)       │
     │ • List user   │ │ • Delete     │ │              │
     │ • Raw content │ │ • Validate   │ │ • Expire     │
     │               │ │ • Generate ID│ │ • Purge S3   │
     └──────┬───────┘ └──────┬───────┘ └──────┬───────┘
            │                │                │
       ┌────▼────┐      ┌───▼────┐      ┌────▼────┐
       │  Redis  │      │  Key   │      │PostgreSQL│
       │  Cache  │      │  Gen   │      │ (query   │
       │         │      │ Service│      │  expired)│
       └────┬────┘      └───┬────┘      └─────────┘
            │               │
       ┌────▼───────────────▼────┐
       │     PostgreSQL          │
       │     (Metadata, sharded) │
       └────────────┬────────────┘
                    │
       ┌────────────▼────────────┐
       │       S3 / MinIO        │
       │   (Paste content blobs) │
       └─────────────────────────┘

#Component Breakdown

Component Responsibility Tech Choice
API Gateway / LB Rate limiting, auth, routing, SSL Nginx / Kong
Read Service Fetch paste metadata + content; cache-first reads Go / Node.js microservice
Write Service Validate content, generate ID, store metadata + content Go microservice
Key Generation Service Pre-generate unique base62 keys Standalone service with ZooKeeper ranges
Cleanup Service Delete expired pastes (metadata + S3 objects) Cron job / scheduled worker
Redis Cache Paste metadata cache; hot paste content for small pastes Redis cluster
PostgreSQL Paste metadata, user data, dedup table Sharded by paste_id hash
S3 Paste content blobs AWS S3 / MinIO
CDN Serve raw paste content globally with low latency CloudFront

#Data Flow

Write Path (Create Paste):

Client → API GW → Write Service
  → 1. Validate content (size < 10MB, rate limit check)
  → 2. Fetch pre-generated unique paste_id from Key Generation Service
  → 3. Compute SHA-256 hash of content
  → 4. Upload content to S3 (key = paste_id, compress if > 1KB)
  → 5. Insert metadata into PostgreSQL
  → 6. Optionally cache in Redis
  → 7. Return paste_id + URL to client

Read Path (Get Paste):

Client → CDN (cache hit for raw content? → return)
       → API GW → Read Service
  → 1. Check Redis cache for metadata (hit → skip DB)
  → 2. Cache miss → query PostgreSQL
  → 3. Check if expired or deleted → 404
  → 4. Check visibility (private → verify owner)
  → 5. Fetch content from S3 (or CDN cache)
  → 6. Populate Redis cache
  → 7. Increment view_count (async, batched)
  → 8. Return paste with metadata + content

Cleanup Path (Expiration):

Cron (every 5 min) → Cleanup Service
  → 1. Query PostgreSQL: SELECT paste_id, s3_key FROM pastes
         WHERE expires_at < NOW() AND is_deleted = false LIMIT 1000
  → 2. Batch delete S3 objects
  → 3. Mark as is_deleted = true in PostgreSQL
  → 4. Delete from Redis cache

#6. Deep Dive — Core Components

#Key Generation Service — Detailed Design

The Problem: We need globally unique, short, URL-safe IDs at 175 QPS peak. Options:

Approach Pros Cons
Auto-increment + Base62 Simple, sequential Predictable URLs (security risk), single DB bottleneck
Random Base62 Non-predictable Collision risk; must check DB each time
UUID → Base62 Globally unique 22+ chars (too long for short URLs)
Pre-generated Key Ranges Fast, no collision, short Extra service to manage

Chosen: Pre-generated Key Range Service

┌─────────────────────────────────────────────────┐
│              Key Generation Service              │
│                                                   │
│  1. On startup: generate 1M random 6-char base62 │
│     keys and store in a KV table                 │
│                                                   │
│  2. Each app server requests a batch of 1000 keys│
│     → marks them as "assigned" in the table      │
│                                                   │
│  3. App server uses keys from local pool          │
│     → no DB lookup needed per paste creation     │
│                                                   │
│  4. When pool < 200 keys → request new batch     │
│                                                   │
│  ZooKeeper coordinates which ranges are assigned │
│  to which server to prevent overlap              │
└─────────────────────────────────────────────────┘

Key table:

CREATE TABLE pre_generated_keys (
  key_value   VARCHAR(8) PRIMARY KEY,
  status      ENUM('available', 'assigned', 'used') DEFAULT 'available',
  assigned_to VARCHAR(100) NULL,
  used_at     TIMESTAMP NULL
);

Why not hash-based? MD5/SHA of content → base62 truncation has collision risk at 6 chars. Pre-generation guarantees uniqueness with zero runtime collision checks.

#Read Service — Detailed Design

Cache-First Strategy:

Read Request → Redis GET paste:{id}
  → HIT:  Check expiration → return metadata
          Fetch content from CDN/S3
  → MISS: PostgreSQL SELECT → check exists + not expired
          Fetch content from S3
          SET in Redis with appropriate TTL
          Return to client

View Count Optimization:
View counts at 1,750 QPS would create hot rows in PostgreSQL if updated synchronously.

Strategy: Buffer in Redis → batch flush to PostgreSQL

1. INCR paste:views:{paste_id} in Redis (atomic, < 0.1ms)
2. Every 60 seconds, cron reads all paste:views:* keys
3. Batch UPDATE pastes SET view_count = view_count + N
4. Delete Redis counter keys after flush

#Content Compression — Detailed Design

Upload Pipeline:
  Content (raw) → Size check
    < 1KB  → Store as-is (overhead of compression not worth it)
    1KB–1MB  → Compress with zstd (level 3) → ~60% size reduction
    > 1MB  → Compress with zstd (level 1) → fast compression for large content

  S3 object metadata: content-encoding = "zstd" or "identity"

Read Pipeline:
  S3 GET → Check content-encoding header
    "zstd" → decompress before serving
    "identity" → serve as-is
  CDN caches the decompressed version

Storage savings: With 60% compression on 80% of content:

Before: 50GB/day
After:  50 × 0.2 (uncompressed) + 50 × 0.8 × 0.4 (compressed) = 10 + 16 = 26GB/day
Savings: ~48% → $$ at 18TB/year scale

#Scaling Strategy

Component Strategy
Read Service Stateless; horizontal scale behind LB; scale based on read QPS
Write Service Stateless; scale independently from reads (10x fewer writes)
PostgreSQL Hash-shard by paste_id across 4–8 shards; read replicas per shard
Redis Cluster mode, 50GB across 10 nodes; LRU eviction for paste cache
S3 Infinite scale; no sharding needed; lifecycle policies for cost optimization
CDN CloudFront edge caches for raw content; 24h TTL for popular pastes
Key Gen Service Single leader with standby; pre-generates keys in background

#Caching Strategy

┌──────────────────────────────────────────────────────┐
│ Layer 1: CDN (CloudFront)                             │
│ • Raw paste content (TTL: 24h for public/unlisted)   │
│ • Static assets (syntax highlighting JS/CSS)          │
│ • ~80% of read traffic served from edge              │
├──────────────────────────────────────────────────────┤
│ Layer 2: Redis (Metadata + Small Content)              │
│ • Paste metadata (TTL: matches expiration or 24h)    │
│ • Small paste content < 50KB inline in cache         │
│ • 90%+ hit rate due to power-law access pattern      │
├──────────────────────────────────────────────────────┤
│ Layer 3: Application-Level                            │
│ • Key pool (pre-generated IDs in local memory)       │
│ • Language detection model weights (in-process)      │
└──────────────────────────────────────────────────────┘

#Consistency Models

Data Model Rationale
Paste content Strongly consistent (write-once, immutable) Content never changes after creation; S3 provides read-after-write consistency
Paste metadata Eventually consistent (< 5s) Redis cache may briefly serve stale metadata; acceptable
View counts Eventually consistent (< 60s) Buffered in Redis, flushed every minute; exact count not critical
Expiration Eventually consistent (< 5 min) Cron runs every 5 min; paste may be accessible briefly past expiry

#7. Low-Level Design — Core Functionality

#Key Algorithms

1. Base62 Encoding

CHARSET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62_encode(num):
    """Convert integer to base62 string."""
    if num == 0:
        return CHARSET[0]
    result = []
    while num > 0:
        result.append(CHARSET[num % 62])
        num //= 62
    return ''.join(reversed(result))

def base62_decode(s):
    """Convert base62 string back to integer."""
    num = 0
    for char in s:
        num = num * 62 + CHARSET.index(char)
    return num

# Example: base62_encode(1000000) → "4c92"
# 6-char range: 0 to 56,800,235,583

2. Paste Creation Flow

def create_paste(content, title, language, expiration, visibility, user_id):
    # 1. Validate
    if len(content) > 10 * 1024 * 1024:  # 10MB
        raise PayloadTooLarge()

    # 2. Get unique ID
    paste_id = key_pool.get_next()  # from pre-generated pool

    # 3. Content processing
    content_hash = sha256(content)
    compressed = zstd_compress(content) if len(content) > 1024 else content
    encoding = "zstd" if len(content) > 1024 else "identity"

    # 4. Detect language if not specified
    if not language:
        language = detect_language(content)  # heuristic / ML

    # 5. Upload to S3
    s3.put_object(
        bucket="paste-content",
        key=paste_id,
        body=compressed,
        metadata={"content-encoding": encoding, "original-size": len(content)}
    )

    # 6. Store metadata
    expires_at = compute_expiry(expiration)
    db.insert("pastes", {
        paste_id, user_id, title, language,
        content_size=len(content), content_hash,
        visibility, expires_at
    })

    # 7. Cache metadata
    redis.setex(f"paste:{paste_id}", ttl=86400, value=metadata_json)

    return paste_id

3. Language Auto-Detection (Heuristic)

LANGUAGE_PATTERNS = {
    "python":     [r"def \w+\(", r"import \w+", r"print\(", r"class \w+:"],
    "javascript": [r"function\s+\w+", r"const \w+", r"=>\s*{", r"require\("],
    "java":       [r"public\s+class", r"System\.out", r"void\s+main"],
    "sql":        [r"SELECT\s+", r"FROM\s+", r"CREATE\s+TABLE", r"INSERT\s+INTO"],
    "html":       [r"<html", r"<div", r"<head>", r"<!DOCTYPE"],
    "bash":       [r"#!/bin/bash", r"\$\{?\w+\}?", r"echo\s+"],
}

def detect_language(content):
    scores = {}
    for lang, patterns in LANGUAGE_PATTERNS.items():
        scores[lang] = sum(1 for p in patterns if re.search(p, content))
    best = max(scores, key=scores.get)
    return best if scores[best] >= 2 else "plaintext"

#Design Patterns Used

Pattern Where Why
Cache-Aside Redis for paste metadata Read-heavy workload; 90%+ cache hit; simple invalidation on delete
Pre-computation Key Generation Service Avoid runtime collision checks; zero-latency ID assignment
Write-Behind View count buffering in Redis Decouple hot-path reads from PostgreSQL writes
Content-Addressable Storage SHA-256 dedup for paste content Save storage when identical content is pasted multiple times
CQRS Separate Read and Write services 10:1 read:write ratio; scale independently
TTL-Based Eviction Redis cache + S3 lifecycle + DB cleanup Multi-layer expiration handling

#8. Failure Handling & Edge Cases

#What Happens When X Fails?

Failure Impact Mitigation
Redis down Reads hit PostgreSQL directly (latency spike) Read replicas absorb load; Redis is cache-only, not source of truth
PostgreSQL primary down Writes fail; reads served from replicas Auto-failover to standby; writes queued for < 30s
S3 down Content unavailable Multi-AZ S3 (99.999999999% durability); CloudFront serves cached content
Key Gen Service down Can't create new pastes Each app server has local pool of ~1000 keys; survives hours without key gen
CDN down Latency increase for global users Fallback to direct S3 reads; origin always available
Cleanup cron fails Expired pastes remain accessible longer Pastes checked at read time too (expires_at < NOW → 404); cron is best-effort

#Edge Cases

#9. Monitoring & Observability

#Key Metrics

Metric Target Alert Threshold
Read P99 latency < 100ms > 250ms
Write P99 latency < 200ms > 500ms
Cache hit ratio (Redis) > 90% < 75%
CDN hit ratio > 80% < 60%
S3 upload error rate < 0.01% > 0.1%
Key pool remaining > 500 per server < 100
Expired paste cleanup lag < 10 min > 30 min
Storage growth rate ~50GB/day > 100GB/day (abuse?)

#Alerting Strategy

#SLAs / SLOs

Read API:           99.99% availability, P99 < 100ms
Write API:          99.95% availability, P99 < 200ms
Content Durability: 99.999999999% (11 nines, S3 guarantee)
Expiration Accuracy: Pastes removed within 10 min of expiry

#10. Trade-off Summary

Decision Chose Over Because
Content storage S3 (object storage) PostgreSQL BYTEA / TEXT 10MB pastes degrade DB; S3 is cheaper, more durable, CDN-friendly
URL generation Pre-generated key pool Hash-based / auto-increment No collision risk, no sequential guessing, zero runtime overhead
URL length 6 characters (base62) 8+ characters 56.8B keyspace is sufficient for 31+ years at 5M/day; shorter URLs are better UX
Metadata DB PostgreSQL (sharded) MongoDB, DynamoDB Relational queries for user paste lists, public browse; partial indexes for efficiency
Cache strategy Cache-aside (Redis) Write-through Read-heavy (10:1); cache misses are rare and tolerable; simpler invalidation
View counting Buffered in Redis, batch flush Synchronous DB update Avoids hot row contention at 1,750 QPS; exact count not critical
Compression Zstandard (zstd) Gzip, LZ4 Best compression ratio for text at acceptable CPU cost; 48% storage savings
Expiration Cron-based cleanup + read-time check DB TTL / scheduled deletes Lazy + active cleanup covers all cases; no expired paste served

#11. Extensions & Follow-ups

#What Would You Add With More Time?

  1. Paste Forking — Create a new paste based on an existing one (like GitHub Gist forks), tracking lineage
  2. Diff View — Compare two pastes or paste versions side-by-side
  3. Collaborative Pastes — Real-time collaborative editing using OT/CRDT (moves toward Google Docs territory)
  4. API Keys & Programmatic Access — CLI tool (paste-cli create < file.py) with API key auth
  5. Paste Collections — Group related pastes into a collection (like multi-file Gists)
  6. Full-Text Search — Elasticsearch index for public pastes; search by content, title, or language
  7. Burn After Reading — One-time view pastes that auto-delete after first read (encrypted at rest)

#How Would This Change at 100x Scale?

#12. Cross-References

Topic Connection
URL Shortener (#1) Nearly identical URL generation and key management problem
Unique ID Generator (#4) Key Generation Service is a specialized unique ID system
Distributed Cache (#15) Redis cluster design underpins paste metadata caching
Web Crawler (#12) Paste content indexing for search shares parsing patterns

#Building Blocks Used

#Concepts Used