Pastebin — System Design Interview

Phase 1: Clarify, Scope & Constraints

Interviewer: "Let's design Pastebin — a service where users paste text and get a short URL to share it. Simple enough?"

Candidate: "Simple surface, interesting depth. Let me clarify the core user journeys:

1. Create journey — User pastes text (code, a note, a log file), gets a short unique URL
2. Read journey — User (or anyone with the link) visits the URL and sees the paste content
3. Expiration journey — Pastes expire after a configured time (10 minutes, 1 hour, 1 day, up to 1 year, or never)
4. Privacy journey — Pastes can be public (listed in archive), unlisted (URL-only access), or private (owner-only)

The dominant complexity is deceptively simple: key generation. Generating short, unique, collision-free paste keys at scale without a central coordinator is the core challenge. The naive approach — generate a random key, check if it exists, insert if not — has race conditions and doesn't scale.

WHY: The second complexity is the extreme read/write asymmetry. A viral paste (e.g., a leaked document, a popular code snippet) might get 10 million reads but was created exactly once. Cache hit rates become critical — a cache miss on a popular paste slams the database.

Non-goals for V1:

• Real-time collaborative editing (different system — Google Docs territory)
• Syntax highlighting server-side (client-side library, no server impact)
• User accounts and dashboards (treat as anonymous by default; user accounts are additive)
• Full-text search across all pastes (separate search index — out of scope for V1)

Interviewer: "What about burn-after-read (one-time view) pastes? Those are used for secrets."

Candidate: "Yes — I'll include that as an expiration option. A paste with expiry=burn is deleted immediately after the first read. This adds an important access pattern: instead of just 'does this key exist', we need 'atomically read and delete'. I'll handle this with a Redis atomic operation."

Interviewer: "Non-functional requirements?"

Candidate:

• Availability: 99.9% — Pastebin is not life-critical; brief outages are tolerable
• Latency: Paste creation P99 < 500ms, paste read P99 < 100ms (reads are far more common and latency-sensitive)
• Durability: High — a paste that wasn't expired should not be lost. But not 11-nines: if a non-expired paste is occasionally lost in a failure, it's acceptable (unlike financial data)
• Consistency: Eventual — it's OK if a newly created paste takes a second to be readable globally
• Read/write ratio: Approximately 10:1 reads to writes (a paste is created once, shared and read many times)
• CAP: AP for reads (availability + eventual consistency), CP for writes (no duplicate keys)

Interviewer: "Is 10:1 right? Some pastes are viewed millions of times, others never."

Candidate: "The distribution is highly skewed. Most pastes are read < 10 times; a few viral pastes are read millions of times. The 10:1 overall ratio is a reasonable average. What this means architecturally: the read path must be cached aggressively, and the write path (key generation + storage) must be correct rather than fast. We'd rather have 200ms paste creation with guaranteed uniqueness than 50ms creation with key collisions."

Back-of-Envelope Math:

Pastebin doesn't publish current metrics. I'll use commonly accepted system design estimates, which are pedagogically reasonable:

$\text{Monthly writes} = 10\text{M pastes}$

$\text{Write QPS} = \frac{10\text{M}}{30 \times 86{,}400} \approx 4\text{ writes/sec}$

$\text{Read QPS} = 4 \times 10 = 40\text{ reads/sec (average)}$

Peak reads (viral paste): potentially $10{,}000\text{ reads/sec for a single hot paste}$

Storage per paste:

• Average paste size: ~10 KB (observed range 1–512 KB; most are small code snippets)
• Maximum: 512 KB (free), 10 MB (PRO)

$\text{Storage per month} = 10\text{M} \times 10\text{ KB} = 100\text{ GB/month}$

$\text{Storage per year} = 1.2\text{ TB/year}$

After 10 years (assuming 50% of pastes expire): $\approx 6\text{ TB total}$

Key space:

Pastebin uses 8-character base62 keys (observed from live site):

$62^8 = 218\text{ trillion possible keys}$

At 10M pastes/month:

$\text{Years to exhaust} = \frac{218\text{ trillion}}{10\text{M} \times 12} \approx 1.8\text{ million years}$

The key space is effectively infinite for any realistic scale. The challenge is not exhaustion, but collision-free generation at speed.

WHY: The math tells us storage is tiny (6 TB after 10 years) — this is not a big data problem at Pastebin's scale. The interesting problems are key uniqueness, cache efficiency for viral pastes, and correct expiration/deletion.

Phase 2: High-Level Architecture

Candidate: "Let me design the API, data model, and core architecture.

API Design — REST over HTTPS:

# Create paste
POST /api/v1/pastes
  Body: {
    content: "...",        -- paste text (max 512KB for free)
    expiry: "10M|1H|1D|1W|2W|1M|6M|1Y|never|burn",
    privacy: "public|unlisted|private",
    syntax: "python|javascript|...",  -- for client-side highlighting hint
    title?: "..."
  }
  Returns: { paste_id: "aB3dEfGh", url: "https://paste.io/aB3dEfGh", expires_at }

# Read paste
GET /api/v1/pastes/{paste_id}
  Returns: { paste_id, content, title, syntax, created_at, expires_at, view_count }

# Delete paste (owner only)
DELETE /api/v1/pastes/{paste_id}
  Returns: 204

# List public pastes (archive)
GET /api/v1/pastes?page={n}&limit=50
  Returns: { pastes: [{paste_id, title, syntax, created_at}...] }

I'll use REST — Pastebin's traffic is browser and CLI-based; REST is the obvious choice. The paste URL is /{paste_id} at the web layer, which routes to the API.

Data Model:

I'll separate metadata (relational, small, frequently queried) from content (large blobs, infrequently queried relative to metadata):

Copy
-- MySQL (paste metadata — fits on one server at Pastebin's scale)
CREATE TABLE pastes (
  paste_id      CHAR(8) NOT NULL,          -- base62 key, e.g. "aB3dEfGh"
  owner_id      BIGINT,                    -- NULL for anonymous pastes
  title         VARCHAR(256),
  syntax        VARCHAR(50),               -- hint for client-side highlighting
  privacy       ENUM('public','unlisted','private') DEFAULT 'public',
  expiry_type   ENUM('10M','1H','1D','1W','2W','1M','6M','1Y','never','burn'),
  expires_at    TIMESTAMP,                 -- NULL if expiry_type='never'
  view_count    INT DEFAULT 0,
  storage_key   VARCHAR(1024),             -- pointer to object store path
  created_at    TIMESTAMP DEFAULT NOW(),
  PRIMARY KEY (paste_id),
  INDEX idx_expires (expires_at),          -- for expiration GC job
  INDEX idx_public_recent (privacy, created_at DESC)  -- for archive listing
);

-- Object storage (paste content — S3-compatible, e.g. MinIO or AWS S3)
-- Key: /pastes/{paste_id}
-- Value: raw text bytes
-- Content-Type: text/plain
-- Metadata: expiry time (for object lifecycle rules)

Why separate content from metadata?

1. Different access patterns: Metadata is queried on every request (even CDN misses need expiry check). Content is large and benefits from blob storage (streaming, range reads, CDN offloading).
2. Different storage engines: SQL is efficient for small structured records; object storage is efficient for large blobs. Storing 512KB blobs in MySQL rows wastes buffer pool memory and makes backups slow.
3. CDN cacheability: Object storage URLs can be served via CDN with long TTLs. SQL data cannot.

Key Generation — Key Generation Service (KGS):

The central challenge: generate 8-character base62 keys that are unique. Options:

Option A — Hash on write:

• SHA-256 hash the content → take first 8 chars → check for collision → retry if collision
• Problem: Race condition — two concurrent requests could get the same key and both pass the collision check

Option B — Key Generation Service (KGS):

• A dedicated service pre-generates millions of random base62 keys and stores them in a database table unused_keys
• When a paste is created, the KGS atomically marks one key as used (UPDATE unused_keys SET used=true WHERE key='...' LIMIT 1)
• Keys are generated offline in batches; the KGS service holds a small in-memory pool of pre-generated keys for fast serving

This eliminates the collision check race condition — each key is assigned atomically.

Option C — Snowflake-style sequential ID:

• Generate a time-based unique ID, then base62-encode it
• Problem: IDs are predictable — users could enumerate pastes by guessing sequential IDs

I'll use Option B (KGS) for V1 — it's collision-free, fast (key is pre-generated), and non-predictable (keys are random base62). The tradeoff: KGS is a dependency that must be highly available.

unused_keys table (MySQL):
  key CHAR(8) PRIMARY KEY,
  used BOOLEAN DEFAULT false,
  assigned_at TIMESTAMP

Pre-generation batch: generate 10M keys at a time → at 4 writes/sec, this lasts 2.5M seconds (~29 days) before needing regeneration.

Core Architecture:

-+ResetFullscreen

Write path (create paste):

1. Client → API Gateway (rate limit: 10 pastes/hour for anonymous, 250/day for PRO)
2. Paste Service requests a key from KGS (in-memory pool → O(1) if pool not empty)
3. Paste Service writes content to object storage at key /pastes/{paste_id}
4. Paste Service writes metadata row to MySQL
5. Paste Service stores full paste in Redis cache (key=paste_id, TTL=1 hour)
6. Return paste_id and URL to client

Read path (read paste):

1. Client → CDN (cache hit for public pastes → return immediately)
2. CDN cache miss → API Gateway → Paste Service
3. Paste Service checks Redis: cache hit → return paste (sub-millisecond)
4. Redis miss → read metadata from MySQL (check expiry, privacy), read content from object storage
5. Write paste to Redis cache, return to client
6. For burn-after-read pastes: atomic Redis GETDEL + MySQL delete + S3 delete in one operation sequence

Interviewer: "What if the KGS goes down? Can we still create pastes?"

Candidate: "Yes, with graceful degradation. Each Paste Service instance maintains a local in-memory pool of pre-fetched keys (e.g., 1,000 keys fetched from KGS in bulk). If KGS goes down, the local pool serves for a while. At the aggregate 4 writes/sec (split across service instances — Phase 4 elaborates the per-instance rate), each instance's 1,000-key pool lasts at least 250 seconds — enough for most transient KGS failures. After pool exhaustion, we fall back to Option A (hash-based key generation) with collision retry. Not ideal, but functional."

Phase 3: Deep Dive & Evolution

Interviewer: "What breaks first when a paste goes viral? Say a Hacker News link to a paste sends 10,000 requests/second."

Candidate: "The read path. Let's trace it:

• 10,000 req/sec → CDN layer (public paste, cacheable)
• CDN TTL is 1 hour for public pastes → first request to CDN misses, subsequent requests hit
• CDN cache miss rate ~1% at steady state: 100 req/sec reach origin
• At 100 req/sec: Redis cache → sub-millisecond → zero DB load

So for a public paste, the CDN absorbs 99%+ of traffic. The paste content is immutable — perfect for long CDN TTL.

But what about the first few seconds after it's posted, before CDN is warm? That's the hot start problem:

Hot Start Mitigation:

1. Redis as L1 cache: 10,000 req/sec → Redis handles easily (Redis does >1M ops/sec). MySQL never sees the traffic.
2. CDN cache warming: After paste creation, proactively push to CDN edge nodes for large platforms. For Pastebin's scale, natural warming (first request to each CDN edge warms it) is sufficient.
3. Request coalescing at origin: If many requests reach origin simultaneously for the same paste_id (all CDN cache misses before warm), the origin uses a mutex: first request fetches from DB, others wait, all receive the same response.

Burn-After-Read — Atomic Implementation:

The tricky case: user B and user C both open the link simultaneously. Only one should see the content.

# Redis pipeline (atomic)
result = redis.pipeline()
  .get(paste_id)               # read content
  .delete(paste_id)            # delete from cache
  .execute()

if result[0] is None:
  # Not in cache - check DB with row-level lock
  with db.transaction():
    paste = SELECT ... FROM pastes WHERE paste_id=? FOR UPDATE
    if paste.expiry_type == 'burn' and not paste.burned:
      content = s3.get(paste_id)
      UPDATE pastes SET burned=true WHERE paste_id=?
      return content
    else:
      return 404  # already burned

# Async cleanup: schedule S3 and MySQL delete

The FOR UPDATE lock in MySQL guarantees only one concurrent reader wins for burn-after-read pastes. The loser sees 404. Content is served before the async delete, so there's no race between serve and delete.

WHY: We use optimistic locking (row lock for burn) rather than a global mutex because the common case (non-burn pastes) doesn't need locking at all. We only lock when the expiry is 'burn', which is a small fraction of all reads.

Expiration — Two Strategies:

1. Lazy expiration: When any read request comes in, check expires_at in metadata. If expired, return 404 and mark for async deletion. Zero background work; slightly stale deletions.

2. Eager expiration (GC cron): A background cleanup job runs every hour, queries SELECT paste_id FROM pastes WHERE expires_at < NOW(), deletes from S3 and MySQL. Frees storage proactively.

I'll use both: lazy expiration (immediate correctness for reads) + eager GC (reclaim storage). The INDEX idx_expires (expires_at) makes the GC query fast.

View Count — Approximate Counter:

Incrementing view_count on every read at 10,000 req/sec creates a MySQL write hotspot on a single row. Solution:

• Use Redis atomic INCR view_count:{paste_id} on every read (sub-millisecond, no contention)
• Background job flushes Redis counters to MySQL every 5 minutes: UPDATE pastes SET view_count=? WHERE paste_id=?
• View count shown to users is slightly stale (up to 5 min) — totally acceptable

Evolved Architecture:

-+ResetFullscreen

What changed from Phase 2:

1. KGS Local Pool — Each Paste Service instance holds a local in-memory pool of 1,000 pre-fetched keys. Eliminates per-request network call to KGS. KGS is consulted only when the pool runs low.
2. CDN layer — Public pastes are served from CDN edge nodes with 1-hour TTL. Content is immutable, so TTL can be set to the paste's expiry time (or 1 hour for never-expiring pastes, with re-validation).
3. View Count Cache — Redis INCR decouples view counting from MySQL writes. ViewFlushSvc runs every 5 minutes.
4. MySQL replica — Added read replica for metadata reads (expiry checks, archive listing). Primary handles writes only.
5. Lazy expiration in read path — Paste Service checks expires_at on every read; returns 404 and triggers async cleanup if expired.

Phase 4: Robustness & Operations

Interviewer: "What if the KGS database goes down? Can users still create pastes?"

Candidate: "With the local pool architecture, each Paste Service instance has 1,000 pre-fetched keys in memory. At 4 writes/sec with N service instances sharing the load, each instance handles ~1–2 writes/sec — so 1,000 keys lasts ~500–1,000 seconds (8–16 minutes) per instance.

If KGS DB is down for longer:

1. Primary fallback: Generate random 8-character base62 keys locally using a cryptographic RNG, then check MySQL for collision. At 218 trillion possible keys vs. a few hundred million in use, collision probability is negligible (<0.001%). This is safe as a fallback.
2. Alert: KGS DB downtime triggers PagerDuty immediately — it's a critical dependency.

Interviewer: "What if the Redis cache goes down? How does read performance degrade?"

Candidate: "Read traffic at 40 avg reads/sec falls through to MySQL + S3:

• MySQL metadata read: ~5ms
• S3 object read: ~20–50ms

Total read latency without cache: ~50ms, vs. ~1ms with cache. Pastebin's 100ms P99 SLA is still met. At the scale we estimated (40 avg reads/sec), MySQL and S3 can easily handle the load without Redis.

The danger is a viral paste event — 10,000 req/sec hitting origin without CDN and Redis. That would overwhelm MySQL. Mitigations:

• CDN is the primary protection for public pastes — it operates independently of Redis
• If Redis fails and CDN is down, apply circuit-breaker: limit max concurrent requests to MySQL, shed excess with 503

Interviewer: "How do you prevent abuse? Pastebin is notorious for being used to host malware and leaked credentials."

Candidate: "Several layers:

1. Rate limiting: Anonymous users: 10 pastes/hour per IP. Free accounts: 20 pastes/24 hours. PRO: 250/day. This limits bulk upload of malicious content.

2. Content scanning: New pastes run through an async content classification pipeline:

   • Malware signatures: YARA rules to detect malware samples
   • PII / credential detection: Regex patterns for AWS keys, private key header markers, and credit card numbers
   • CSAM detection: PhotoDNA hash matching (for any image embeds in the text)
   • If flagged: paste hidden from public listing and reported for review

3. DMCA / abuse API: Legal team can bulk-delete pastes matching a hash or pattern.

4. Paste size limits: Free users capped at 512 KB. Large pastes are often data dumps.

5. Burn-after-read mode: Legitimate use case for secrets (API keys, passwords shared once). Reduces persistence window of sensitive data.

Observability & Security:

SLIs I'd monitor:

• Paste creation P99 (target < 500ms)
• Paste read P99 (target < 100ms)
• Redis cache hit rate (target > 90%)
• CDN cache hit rate for public pastes (target > 95%)
• KGS key pool depth (alert if any instance pool drops below 100 keys)
• Expiration GC lag (alert if expired pastes linger > 1 hour past expiry)
• Content store (S3) error rate (alert if > 0.1%)

Security:

• TLS everywhere — HTTPS only, HSTS headers
• Pre-signed URLs for private pastes: instead of returning raw content through the API, return a pre-signed S3 URL (5-minute TTL, bound to requesting user). Even if the URL leaks, it expires quickly.
• Rate limiting on reads — prevents paste content scraping (enumerate all paste IDs, download everything). Returns 429 after 1,000 reads/hour per IP.

Executive Summary:

Key trade-offs I made:

1. KGS over hash-based key generation: Pre-generated random keys guarantee collision-freedom and avoid the check-then-insert race condition. The cost is operational complexity (one more service to maintain). At Pastebin's scale (4 writes/sec), a simpler approach would work, but the KGS pattern is the right one to demonstrate in an interview.

2. Metadata/content split: MySQL for small structured metadata, S3 for large blobs. This allows different scaling strategies for each — MySQL scales via read replicas and reasonable sharding; S3 scales horizontally without limit. The alternative (storing content in MySQL) wastes buffer pool memory on binary data and makes backup/restore painful.

3. Lazy + eager expiration: Lazy provides immediate correctness (expired pastes return 404 instantly). Eager GC reclaims storage. The cost is implementation complexity for both paths. The alternative (eager only) requires the GC to be always running; the alternative (lazy only) leaks storage indefinitely.

4. Approximate view counts: Redis-based counting with 5-minute flush lag. View counts are informational — the user doesn't need exact real-time accuracy. The alternative (synchronous MySQL increment) creates write hotspots on popular pastes.

For V2, I'd add:

• Full-text search: Index public paste titles and first 500 chars in Elasticsearch. Users can search for code snippets by topic.
• User-facing analytics: For registered users, show real-time view count graphs and referrer data. Requires a click analytics pipeline (Kafka → Flink → time-series DB).
• API access tier: Developer API with OAuth, higher rate limits, bulk paste operations. This is Pastebin PRO's main value proposition.
• Geographic routing: Users in Europe get pastes served from EU data centers (GDPR compliance). Metadata DB needs regional replication with appropriate data residency guarantees.