Key-Value Store and Pastebin

A Dynamo-style KV store, then Pastebin as a thin API on top of it.

• Advanced
• 40 min read
• 3 objectives

Before this lessonLesson 7: Rate Limiter

A distributed key-value store is the engine under sessions, URL shorteners, and Pastebin. The interview is two layers: (A) a Dynamo-style store that survives machine loss, then (B) Pastebin as a thin API on top of it.

Part A — The KV store

Clarify

• Operations: put(key, value), get(key), optional delete and TTL.
• Value size: bytes to a few MB. Larger blobs go to object storage; the KV holds a pointer.
• CAP: high availability over linearizability (AP). Tunable N, W, R.
• Scale by adding nodes. Survive disk, node, and network failure.

Consistent hashing

hash(key) % N remaps almost every key when N changes. A hash ring places nodes on a circle; a key walks clockwise to the first node. Adding a node only steals its slice. Virtual nodes (many positions per physical box) keep load even when hardware differs.

flowchart TB subgraph ring [Hash ring] N1[Node A] N2[Node B] N3[Node C] N4[Node D] end K[hash key] --> N2 N2 -->|replica| N3 N2 -->|replica| N4

The key lands on the first node clockwise. The next N-1 nodes store replicas. Virtual nodes are omitted from the sketch but you should name them.

Replication and quorum

Store N copies (often 3). A coordinator sends the write to N nodes and waits for W acks. A read waits for R replies. W + R > N means every read overlaps at least one node that took the write (quorum consistency). W=1, R=1 is fast and can return stale data. W=N, R=1 is a durable write, cheap read.

N, W, R = 3, 2, 2
print("quorum overlap", W + R > N)
print("fast stale-possible", (1, 1))
print("read-your-writes likely", W + R > N)

quorum overlap True
fast stale-possible (1, 1)
read-your-writes likely True

When a replica is down

• Sloppy quorum / hinted handoff: write to a healthy neighbor with a hint, replay when the owner returns.
• Conflicts: last-write-wins (clocks) or vector clocks that return siblings for the client to merge.
• Anti-entropy: background Merkle-tree compare and repair so replicas do not drift forever.
• Storage engine: LSM tree (memtable + SSTables + compaction) for high write QPS; mention compaction I/O.

Failure and 10x

Coordinator is any node; clients cache the ring. If a whole rack dies, remaining replicas still serve if R can be met. At 10x keys, add nodes — consistent hashing moves only ~1/N of data. Watch hot keys: cache them, or split a key with a suffix.

Part B — Pastebin

Pastebin is a KV with a public URL, metadata, and optional expiry — a URL shortener for blobs of text.

POST /api/v1/pastes
  { "content": "…", "expire_seconds": 86400, "language": "python" }
  -> { "url": "https://paste.example/3ORDSU", "id": "3ORDSU" }

GET /{id}         rendered or raw
GET /{id}.json    metadata
DELETE /{id}      owner only

id     = public code (random or base62 of an internal id)
value  = content if < 1 MB else s3://bucket/id
meta   = created_at, expire_at, user_id, size, language

• IDs from the previous lesson. Small pastes in the KV; large ones in object storage, metadata keeps the pointer.
• Hot pastes (viral gists) in Redis; CDN for immutable public pastes.
• TTL in the KV plus a sweeper for S3 objects so you do not pay for forgotten GB.
• Size caps, rate limits, malware scan of content — same abuse story as the shortener.

small, large = 0.80, 0.20
per_day = 10_000_000
gb_small = per_day * small * 30_000 / 1e9          # 30 KB average
gb_large = per_day * large * 2_000_000 / 1e9       # 2 MB average
print(round(gb_small), round(gb_large), "GB/day")
print("30-day TB", round((gb_small + gb_large) * 30 / 1000, 1))

240 4000 GB/day
30-day TB 127.2

// Write your solution here