System Design · Project SD

Design a system

The capstone: build ONE system (a URL shortener) four times — beginner in-memory → intermediate persisted+API → advanced cached+analytics → expert web-scale — then apply the same method to a news feed. Every stage is runnable Python.

⏱️ ~6 hours🏗️ Capstone project🎯 Beginner→Expert

What you'll buildOne system — a URL shortener — built four times, each tier adding what the last couldn't do: a beginner in-memory version, an intermediate persisted+API version, an advanced cached+analytics version, and an expert web-scale version (sharding, distributed IDs, rate limiting). Then we apply the same method to a second system — a news feed — in real Python. Every block runs.

Learning objectives

Apply a repeatable 5-step design method to any prompt.
Evolve one system from a 20-line prototype to a web-scale design, in runnable Python.
Use every SD1–SD7 building block (schema, patterns, cache, CAP, sharding, queues) in context.
Present a design the way an interview and a real project demand.

▶ Runnable companionEvery code block here is also saved under code/proj-sd-casestudy/ — pure Python / sqlite3, runs with no setup.

1 · The method — 5 steps, every time essential

Before code, the method. Every system-design prompt — in an interview or at work — yields to the same five steps. Say them out loud; the structure is what impresses.

Design any system

Requirements — functional (what it does) + non-functional (scale, latency, consistency).
API — the handful of operations. Pins down the contract.
Data model — tables/collections + the shard key.
Architecture — the client → LB → service → cache/DB boxes and data flow.
Scale — estimate load, then apply caching / replication / sharding / queues where the numbers demand.

Our running example: a URL shortener (TinyURL/bit.ly). Requirements: shorten a long URL to a short code; redirect a code to its original; read-heavy (far more redirects than creations); low-latency redirects; eventually billions of URLs. API: shorten(long_url) → code and resolve(code) → long_url.

2 · Beginner build — make it work (in memory) essential

The first version ignores scale entirely and just works. A dictionary maps codes to URLs; we generate codes from an incrementing counter. This is the whole idea in 20 lines — always start here, then evolve.

Example code for learning — review, test, and adapt it before running against real or production systems. Commands can create, change, or delete resources. See the Terms & Disclaimer.

Step 1 · The simplest thing that works

v1_inmemory.pyimport string

ALPHABET = string.digits + string.ascii_letters   # 62 chars: 0-9 a-z A-Z

def encode(n):
    """Turn a number into a short base62 code: 0->'0', 125->'21'."""
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, r = divmod(n, 62)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

class TinyURL:
    def __init__(self):
        self._store = {}     # code -> long_url
        self._next = 1        # incrementing id

    def shorten(self, long_url):
        code = encode(self._next)
        self._store[code] = long_url
        self._next += 1
        return code

    def resolve(self, code):
        return self._store.get(code)

t = TinyURL()
c = t.shorten("https://studybydoing.in/a/very/long/path")
print("code:", c, "->", t.resolve(c))
print("missing:", t.resolve("zzz"))

code: 1 -> https://studybydoing.in/a/very/long/path
missing: None

▶ How this works

This is the whole URL shortener in about 20 lines — the "make it work first" version. It keeps everything in memory (a plain Python dictionary): give it a long URL, it hands back a short code; give it the code back, it returns the original URL. No database, no server yet — just the core idea.

ALPHABET is the 62 characters 0-9 a-z A-Z. base62 means we write numbers using 62 digits instead of the usual 10, so a small number becomes a short, URL-safe code.
encode(n) turns a plain number into that short code. divmod(n, 62) splits n into a quotient and a remainder in one step; the remainder picks a character. Repeating that peels off characters, then reversed(out) puts them in the right order.
class TinyURL holds the state: self._store is the dictionary code → long_url, and self._next is a counter that only ever goes up.
shorten gives the current counter a code, saves the URL under it, then bumps the counter by 1 so the next URL gets a different code. resolve just looks the code up; .get(code) returns None instead of crashing if it's missing.

What the output means: It prints code: 1 -> https://studybydoing.in/a/very/long/path (the first URL got code 1), then missing: None because "zzz" was never stored — None is Python's way of saying "nothing here".

Try this: Call t.shorten(...) a second and third time and print the codes. You'll see them climb (1, 2, 3) — that incrementing counter is what guarantees every code is unique, for free.

Why base6262 characters (0-9, a-z, A-Z) make codes short and URL-safe. A 7-char base62 code encodes 62⁷ ≈ 3.5 trillion URLs — plenty. Converting an integer id to base62 guarantees uniqueness for free (each id maps to one code).

What's wrong with v1 (on purpose)It loses everything on restart (no persistence), can't run on more than one machine (state in memory), and has no analytics or abuse protection. Each following tier fixes one class of problem — exactly how real systems grow.

3 · Intermediate build — persist it + an API intermediate

A real service must survive restarts and be callable over HTTP. We move storage to a database (SD1/SD2 — using sqlite3 so it runs anywhere) and let the DB's auto-increment id generate our codes. Then we wrap it in a tiny HTTP API shape.

🗺️ How to read this diagram

This shows the intermediate design (v2/v3): a client talking over HTTP to your service, which saves data in a durable database. Read it left to right — that's the direction a request travels.

Left box — POST /shorten (client): whoever wants a short link (a browser, an app, curl). It sends the long URL to the service.
Arrow: the network request going into your service — the HTTP call.
Middle box — TinyURL service (encode/decode): your code. It turns the database's numeric id into a short base62 code on create, and decodes a code back to a number on lookup.
Right box — SQLite (id → url), "durable": the database that actually stores the mapping and, being on disk, survives restarts. "Durable" is the word for "data doesn't vanish".

In short: A create request flows client → service → database and a code comes back the same way in reverse. The single database here is the piece that later can't keep up — which is exactly what the next tiers fix.

Step 2 · Persisted service

v2_persisted.pyimport sqlite3, string
ALPHABET = string.digits + string.ascii_letters

def encode(n):
    if n == 0: return ALPHABET[0]
    out = []
    while n:
        n, r = divmod(n, 62); out.append(ALPHABET[r])
    return "".join(reversed(out))

def decode(code):
    n = 0
    for ch in code: n = n * 62 + ALPHABET.index(ch)
    return n

class TinyURL:
    def __init__(self, path=":memory:"):
        self.db = sqlite3.connect(path)
        self.db.execute("CREATE TABLE IF NOT EXISTS urls (id INTEGER PRIMARY KEY, long TEXT NOT NULL)")
        self.db.commit()

    def shorten(self, long_url):
        cur = self.db.execute("INSERT INTO urls(long) VALUES (?)", (long_url,))
        self.db.commit()
        return encode(cur.lastrowid)          # DB gives us a unique id -> code

    def resolve(self, code):
        row = self.db.execute("SELECT long FROM urls WHERE id = ?", (decode(code),)).fetchone()
        return row[0] if row else None

t = TinyURL()
c = t.shorten("https://studybydoing.in/pricing")
print(c, "->", t.resolve(c))

1 -> https://studybydoing.in/pricing

▶ How this works

Version 1 forgot everything the moment the program stopped. This version stores the URLs in a real database (SQLite, which ships with Python) so the data survives a restart. The clever part: we let the database itself hand out the unique numbers, then turn each number into a base62 code.

sqlite3.connect(path) opens the database. CREATE TABLE IF NOT EXISTS urls makes a table with two columns — an id that is the PRIMARY KEY (SQLite auto-fills it with a new number each insert) and the long URL text.
encode is the same base62 converter as before; decode is its reverse — it walks the code's characters and rebuilds the original number (n = n * 62 + index).
shorten runs an INSERT. The database assigns the row a fresh id, which we read back as cur.lastrowid and encode into a code. That's why the comment says the DB gives us a unique id — no separate counter to manage.
resolve does the reverse trip: decode(code) back to a number, then SELECT ... WHERE id = ? looks up that row. The ? is a safe placeholder that stops malicious input from tampering with the query.

What the output means: It prints 1 -> https://studybydoing.in/pricing — the first inserted URL got id 1 → code 1, and resolving that code returns the original URL.

Try this: Change TinyURL() to TinyURL("urls.db"), run it, then run it again. A file urls.db appears and the data is still there on the second run — that is what "persistence" means.

Now the HTTP layer. We keep it dependency-free with Python's built-in http.server so it runs with no installs — the same request/response shape FastAPI would give you (DA3).

Step 3 · A real HTTP API (stdlib only)

v3_api.pyfrom http.server import BaseHTTPRequestHandler, HTTPServer
import json

service = TinyURL()                            # from Step 2

class Handler(BaseHTTPRequestHandler):
    def do_POST(self):                          # POST /shorten  {"url": "..."}
        n = int(self.headers.get("Content-Length", 0))
        body = json.loads(self.rfile.read(n) or "{}")
        code = service.shorten(body["url"])
        self._json(200, {"code": code})

    def do_GET(self):                           # GET /<code>  -> 302 redirect
        code = self.path.lstrip("/")
        long = service.resolve(code)
        if long:
            self.send_response(302); self.send_header("Location", long); self.end_headers()
        else:
            self._json(404, {"error": "not found"})

    def _json(self, status, obj):
        self.send_response(status); self.send_header("Content-Type", "application/json")
        self.end_headers(); self.wfile.write(json.dumps(obj).encode())

# HTTPServer(("", 8000), Handler).serve_forever()   # uncomment to run the server

▶ How this works

So far you could only call the shortener from Python. A real service is reachable over the web. This wraps the same TinyURL service in a tiny HTTP server so a browser or app can create short links and follow them — using only Python's built-in http.server, no installs.

service = TinyURL() reuses the exact class from Step 2 — the web layer sits on top of it and never changes it.
do_POST handles POST /shorten: it reads the request body, parses the JSON to get the url, calls service.shorten(...), and replies with the new code. This is the "create a short link" operation.
do_GET handles GET /<code>: it strips the leading slash to get the code, resolves it, and if found sends a 302 redirect — an HTTP reply that tells the browser "go to this other address instead". If not found it returns a 404 error.
_json is a small helper that writes a JSON response with the right status code and Content-Type header. The last line (commented out) is what actually starts the server listening on port 8000.

What the output means: Nothing prints — this file defines the server. Uncomment the final line and it would listen on port 8000: posting a URL returns a code, and visiting /<code> bounces your browser to the original link.

Try this: Notice the two operations map exactly to the API contract from step 1: shorten(long_url) -> code is the POST, resolve(code) -> long_url is the GET redirect. Same contract, now over HTTP.

Same shape, any frameworkThis is the stdlib version so it runs instantly. In production you'd use FastAPI/Flask (DA3) — but the contract is identical: POST /shorten creates, GET /{code} redirects. The service class doesn't change.

4 · Advanced build — cache + analytics advanced

Redirects are read-heavy and latency-sensitive: the same popular links get resolved constantly. We add the LRU cache from SD5 so hot codes skip the DB, and a click-count for analytics — without slowing the redirect path.

🗺️ How to read this diagram

This shows the advanced design (v4): the same redirect, but with a cache in front of the database and analytics moved off the critical path. Follow the arrows left to right to see a redirect's journey.

GET /code (redirect): a user clicking a short link — this is the read-heavy, latency-sensitive path we're optimizing.
LRU cache ("fast hit"): checked first. If the code is here, we answer instantly and skip the database entirely — that's the "hot path".
DB (on miss), "slow miss": only reached when the cache doesn't have the code. We read it, then store it in the cache so the next hit is fast.
async click++ ("don't block"): counting the click happens beside the main path, not in front of it, so recording analytics never slows down the redirect the user is waiting on.

In short: The core idea: most requests stop at the cache (fast); only the rare miss pays the database cost; and analytics run to the side. That's how you keep redirects instant even under heavy read traffic.

Step 4 · Cached, analytics-aware service

v4_cached.pyimport sqlite3, string
from collections import OrderedDict
ALPHABET = string.digits + string.ascii_letters
def encode(n):
    if n == 0: return ALPHABET[0]
    o=[]
    while n: n,r=divmod(n,62); o.append(ALPHABET[r])
    return "".join(reversed(o))
def decode(code):
    n=0
    for ch in code: n=n*62+ALPHABET.index(ch)
    return n

class LRUCache:
    def __init__(self, capacity): self.cap=capacity; self._d=OrderedDict()
    def get(self, k):
        if k not in self._d: return None
        self._d.move_to_end(k); return self._d[k]
    def put(self, k, v):
        self._d[k]=v; self._d.move_to_end(k)
        if len(self._d)>self.cap: self._d.popitem(last=False)

class TinyURL:
    def __init__(self, cache_size=1000):
        self.db = sqlite3.connect(":memory:")
        self.db.execute("CREATE TABLE urls (id INTEGER PRIMARY KEY, long TEXT, clicks INTEGER DEFAULT 0)")
        self.cache = LRUCache(cache_size)

    def shorten(self, long_url):
        cur = self.db.execute("INSERT INTO urls(long) VALUES (?)", (long_url,)); self.db.commit()
        return encode(cur.lastrowid)

    def resolve(self, code):
        cached = self.cache.get(code)
        if cached is not None:                  # fast path: no DB touch
            self._bump(code); return cached
        row = self.db.execute("SELECT long FROM urls WHERE id=?", (decode(code),)).fetchone()
        if not row: return None
        self.cache.put(code, row[0]); self._bump(code)
        return row[0]

    def _bump(self, code):                       # analytics — kept simple here;
        self.db.execute("UPDATE urls SET clicks=clicks+1 WHERE id=?", (decode(code),))
        self.db.commit()                          # in prod: fire-and-forget to a queue (SD7)

    def stats(self, code):
        r=self.db.execute("SELECT clicks FROM urls WHERE id=?",(decode(code),)).fetchone()
        return r[0] if r else 0

t=TinyURL(); c=t.shorten("https://studybydoing.in")
t.resolve(c); t.resolve(c); t.resolve(c)         # 3 redirects (2 from cache)
print("clicks:", t.stats(c))

clicks: 3

▶ How this works

Redirects are read-heavy: the same popular links get clicked over and over, and each click was hitting the database. This version adds an LRU cache (a small in-memory shortcut for the hottest links) plus a click counter for analytics — making common redirects fast while still counting every hit.

class LRUCache is a fixed-size memory of recent items built on an OrderedDict. get moves a used key to the end (marking it "recently used"); put adds a key and, if the cache is full, popitem(last=False) drops the Least Recently Used one.
In resolve, we check the cache first. If the code is cached (cached is not None) we return it immediately — the comment calls this the fast path because it never touches the slow database.
On a cache miss we fall back to the database SELECT, then self.cache.put(code, row[0]) stores it so the next request for that code is fast too.
_bump increments the clicks count for analytics, and stats reads it back. The comment flags that in production this write would be sent to a queue instead of blocking the redirect (see the warning box below).

What the output means: It shortens one URL, resolves it 3 times, and prints clicks: 3. The first resolve was a cache miss (hit the DB); the next two were fast cache hits — but all three were still counted.

Try this: Create the service with TinyURL(cache_size=1), shorten two URLs, resolve them alternately, and add a print inside the DB-miss branch. You'll watch the tiny cache evict one entry and go back to the database — exactly how a real cache behaves under pressure.

Analytics off the critical pathUpdating the click count on every redirect adds a DB write to the latency-critical path. At scale you'd push click events to a message queue (SD7) and aggregate them asynchronously — the redirect returns instantly, analytics catch up. We keep it inline here so the demo runs standalone.

5 · Expert build — scale to billions expert

Now the numbers bite. Estimate first (SD6): say 100M new URLs/month and 10:1 read:write → ~40 writes/sec, ~400 reads/sec average, multiples at peak, and billions of rows over a few years. One database can't hold or serve that. Three changes take us to web scale.

Problem A — one DB can't hold it all. Shard the data across N databases using consistent hashing (SD7) so adding a shard moves few keys.

Step 5a · Route each code to a shard

v5a_sharding.pyimport hashlib, bisect

class HashRing:
    def __init__(self, nodes=(), vnodes=100):
        self.vnodes=vnodes; self._ring={}; self._sorted=[]
        for n in nodes: self.add(n)
    def _h(self, key): return int(hashlib.md5(key.encode()).hexdigest(), 16)
    def add(self, node):
        for i in range(self.vnodes):
            h=self._h(f"{node}:{i}"); self._ring[h]=node; bisect.insort(self._sorted,h)
    def get(self, key):
        h=self._h(key); i=bisect.bisect(self._sorted,h)%len(self._sorted)
        return self._ring[self._sorted[i]]

ring = HashRing(["db0","db1","db2","db3"])
for code in ("a","b7","Xk","99"):
    print(code, "-> shard", ring.get(code))     # each code deterministically maps to a shard

▶ How this works

At billions of URLs, no single database can hold everything, so we split the data across several databases called shards. This code decides which shard a given code belongs to using consistent hashing — a scheme that spreads keys evenly and, crucially, barely reshuffles anything when you add or remove a shard.

A hash turns any string into a big number. _h does that with MD5. We picture all possible hash values arranged around a circle (a "ring").
add(node) places each database on the ring many times (vnodes=100 "virtual nodes" per database). More points per database means the load spreads out more evenly instead of clumping.
get(key) hashes the key, then bisect.bisect finds the next node clockwise on the sorted ring — that node owns the key. The % len wraps around from the end of the ring back to the start.
Because the same key always hashes to the same spot, the same code always lands on the same shard — that is what "deterministic" means, and it's why lookups can find the data again.

What the output means: For each test code it prints which shard owns it, e.g. a -> shard db2. Run it twice and the mapping never changes — deterministic routing.

Try this: Add a fifth database with ring.add("db4") before the loop and re-check the assignments. Most codes keep their old shard — only a small slice moves. That stability is the whole point of consistent hashing versus a plain hash % N.

Problem B — auto-increment ids don't work across shards. Each shard would generate the same ids. Use a distributed ID generator (Snowflake-style): pack a timestamp + a machine id + a per-ms counter into a 64-bit int that's globally unique and roughly time-ordered.

Step 5b · A Snowflake-style ID generator

v5b_snowflake.pyimport threading

class SnowflakeID:
    """64-bit IDs: 41 bits ms-timestamp | 10 bits machine | 12 bits sequence."""
    def __init__(self, machine_id, epoch_ms=1_700_000_000_000):
        self.machine_id = machine_id & 0x3FF          # 10 bits
        self.epoch = epoch_ms
        self.seq = 0
        self.last_ms = -1
        self._lock = threading.Lock()

    def next_id(self, now_ms):                        # now_ms injected -> testable
        with self._lock:
            if now_ms == self.last_ms:
                self.seq = (self.seq + 1) & 0xFFF     # 12-bit sequence within the ms
                if self.seq == 0:                     # sequence exhausted this ms
                    while now_ms <= self.last_ms:
                        now_ms += 1                   # wait for next ms (simulated)
            else:
                self.seq = 0
            self.last_ms = now_ms
            return ((now_ms - self.epoch) << 22) | (self.machine_id << 12) | self.seq

gen = SnowflakeID(machine_id=1)
ids = [gen.next_id(1_700_000_005_000 + (i // 3)) for i in range(5)]
print(ids)
print("all unique:", len(set(ids)) == len(ids), "| increasing:", ids == sorted(ids))

[20971520000, 20971520001, 20971520002, 20971524096, 20971524097]
all unique: True | increasing: True

▶ How this works

With many shards, we can't rely on one database's auto-increment id — every shard would hand out the same numbers and collide. A Snowflake ID generator solves this: it packs a timestamp, a machine number, and a per-millisecond counter into a single 64-bit integer that is globally unique and roughly sorted by time.

The id is built from three parts squeezed into 64 bits: 41 bits of millisecond timestamp, 10 bits of machine id (so different servers never clash), and 12 bits of sequence (so one machine can mint many ids within the same millisecond).
next_id(now_ms) takes the current time as an argument (injected, so it's easy to test). The with self._lock makes it thread-safe — two threads can't corrupt the counter at once.
If two ids are requested in the same millisecond, self.seq increments (& 0xFFF keeps it inside 12 bits). If the millisecond changed, the sequence resets to 0.
The final line does the packing with bit-shifts: the timestamp is shifted left 22 places, the machine id 12 places, then the sequence is dropped into the low bits with | (OR). The result is one number holding all three fields.

What the output means: It prints 5 generated ids, then all unique: True | increasing: True. The first three share a millisecond (their sequence counts 0,1,2); the last two jump because time advanced — and every id is larger than the last, giving rough time ordering.

Try this: Request ids without advancing time — call gen.next_id(1_700_000_005_000) five times with the same value. Watch the low digits climb 0,1,2,3,4: that's the sequence field keeping ids unique inside a single millisecond.

Problem C — abuse + uneven load. Add the rate limiter from SD4 at the gateway (per client), read from replicas (SD6), and keep app servers stateless so the load balancer can spread traffic freely. Here's the whole expert architecture:

🗺️ How to read this diagram

This is the full expert architecture — everything wired together for web scale. Read left to right: each box is a layer a request passes through, and each layer solves a specific SD1–SD7 problem (the small labels name which lesson it comes from).

Clients ("millions"): the incoming traffic — far more than one machine could handle.
Gateway: rate-limit + LB (SD4+SD5): the front door. It rate-limits each client to block abuse, and the load balancer spreads requests across many service machines.
Stateless services (SD6): the app servers. "Stateless" means any server can handle any request because they keep no per-user memory — so the load balancer is free to send traffic anywhere and you can add more servers at will.
Cache → sharded DB + replicas (SD5+SD6+SD7): the storage layer — the cache for hot reads, data sharded across many databases to fit billions of rows, and replicas to share the read load.

In short: A request flows clients → gateway (throttle + balance) → a stateless service → cache, then sharded/replicated storage on a miss. Each layer removes one bottleneck the earlier tiers hit — that layered progression is the essence of scaling a system.

Step 5c · The pieces, wired into one router

v5c_wired.py# Bringing it together: a request router that rate-limits, caches, and shards.
# (HashRing, LRUCache, SnowflakeID, RateLimiter come from the steps above / SD4-SD7.)

class ShardedTinyURL:
    def __init__(self, ring, cache, id_gen):
        self.ring, self.cache, self.id_gen = ring, cache, id_gen
        self.shards = {n: {} for n in ["db0","db1","db2","db3"]}   # stand-in per-shard stores

    def shorten(self, long_url, now_ms):
        _id = self.id_gen.next_id(now_ms)          # globally-unique id (5b)
        code = _b62(_id)
        shard = self.ring.get(code)                # which DB (5a)
        self.shards[shard][code] = long_url
        return code

    def resolve(self, code):
        hit = self.cache.get(code)                 # hot path (step 4 / SD5)
        if hit is not None: return hit
        shard = self.ring.get(code)                # miss -> the right shard
        val = self.shards[shard].get(code)
        if val is not None: self.cache.put(code, val)
        return val

def _b62(n):
    import string; A=string.digits+string.ascii_letters
    if n==0: return A[0]
    o=[]
    while n: n,r=divmod(n,62); o.append(A[r])
    return "".join(reversed(o))

svc = ShardedTinyURL(HashRing(["db0","db1","db2","db3"]), LRUCache(1000), SnowflakeID(1))
code = svc.shorten("https://studybydoing.in/scaled", now_ms=1_700_000_009_000)
print(code, "->", svc.resolve(code))

▶ How this works

This is the payoff: the sharding, caching, and ID pieces from the previous steps wired into one service. It shows how a single shorten or resolve call flows through all the web-scale machinery — the same two operations from step 1, now backed by the full design.

The constructor is handed the three building blocks: a ring (which shard), a cache (the fast path), and an id_gen (unique ids). self.shards is a stand-in dictionary per shard so the demo runs without four real databases.
shorten flows top to bottom: get a globally-unique id from the Snowflake generator (5b), turn it into a code with _b62, ask the ring which shard owns that code (5a), then store the URL in that shard.
resolve checks the cache first (the hot path from step 4). On a miss it asks the ring for the right shard, reads the value there, and warms the cache with self.cache.put(...) so the next lookup is fast.
_b62 is the same base62 encoder, included locally so this file stands alone. The bottom lines build the service and prove one round-trip: shorten a URL, then resolve the code back to it.

What the output means: It prints something like <code> -> https://studybydoing.in/scaled — one value shortened and resolved through the sharded, cached, distributed-ID stack in a single flow.

Try this: Trace one resolve(code) in your head: cache → (miss) ring picks a shard → read that shard → fill cache. That four-step path is the entire advanced/expert design in miniature.

The climb in one glancev1 dict (works) → v2 sqlite (survives restart) → v3 HTTP API (callable) → v4 cache + analytics (fast + measurable) → v5 sharding + distributed IDs + rate limiting (web scale). Each tier solved exactly what the previous couldn't — that progression is system design.

6 · Apply the method again — a news feed expert

The proof that you've learned the method: apply it to a different system. A news feed (Twitter/Instagram home timeline). Requirements: users follow others; a user's feed shows recent posts from followees, newest first; read-heavy; must feel instant. The design hinges on one classic decision: fan-out on write vs read.

Approach	On post	On feed read	Best for
Fan-out on write (push)	copy post into every follower's feed	just read your feed (fast)	most users
Fan-out on read (pull)	just store the post	gather from all followees (slow)	celebrities (millions of followers)

Real systems do both: push for normal users, pull for celebrities (the "hybrid" model). Here's a runnable core showing both strategies:

Step 6 · A news feed core (push + pull)

v6_newsfeed.pyfrom collections import defaultdict, deque

class NewsFeed:
    def __init__(self, celeb_threshold=3):
        self.follows = defaultdict(set)            # user -> set of followees
        self.followers = defaultdict(set)          # user -> set of followers
        self.posts = defaultdict(list)             # user -> [(ts, text)]
        self.feed = defaultdict(lambda: deque(maxlen=100))  # pushed feeds
        self.celeb_threshold = celeb_threshold      # >= this many followers = "celebrity"

    def follow(self, u, other):
        self.follows[u].add(other); self.followers[other].add(u)

    def post(self, u, ts, text):
        self.posts[u].append((ts, text))
        if len(self.followers[u]) < self.celeb_threshold:
            for f in self.followers[u]:            # PUSH: fan-out on write
                self.feed[f].append((ts, text, u))

    def get_feed(self, u):
        items = list(self.feed[u])                 # pushed (normal followees)
        for other in self.follows[u]:              # PULL: celebrities on read
            if len(self.followers[other]) >= self.celeb_threshold:
                items += [(ts, txt, other) for ts, txt in self.posts[other]]
        return [ (t, who, txt) for (t, txt, who) in sorted(items, reverse=True)[:20] ]

nf = NewsFeed()
for f in ["u1","u2","u3","u4"]: nf.follow(f, "celeb")   # celeb has 4 followers -> pull
nf.follow("u1", "u2")                                    # u2 normal -> push
nf.post("u2", 1, "hi from u2")
nf.post("celeb", 2, "big announcement")
print(nf.get_feed("u1"))     # sees both: pushed u2 post + pulled celeb post

[(2, 'celeb', 'big announcement'), (1, 'u2', 'hi from u2')]

▶ How this works

To prove the 5-step method transfers, we apply it to a totally different system: a news feed (a home timeline of posts from people you follow). The whole design hinges on one decision — fan-out on write (push) vs fan-out on read (pull) — and this code implements a hybrid that uses both.

The constructor sets up the data: follows/followers track who follows whom, posts stores each user's posts, and feed holds a ready-made timeline per user (a deque(maxlen=100) keeps only the newest 100).
PUSH (fan-out on write) — in post, if the author has few followers (under celeb_threshold), we immediately copy the post into every follower's feed. Reading their feed is then instant.
PULL (fan-out on read) — a "celebrity" with many followers is skipped by push (copying to millions would be wasteful). Instead, get_feed gathers a celebrity's posts on the fly when someone actually reads their feed.
get_feed merges the two sources — the pre-pushed items plus the pulled celebrity posts — then sorted(items, reverse=True) orders them newest-first and keeps the top 20.

What the output means: For u1 it prints [(2, 'celeb', 'big announcement'), (1, 'u2', 'hi from u2')] — the celeb post (pulled) and the normal u2 post (pushed), merged and sorted newest-first.

Try this: Lower celeb_threshold to 1 so even u2 counts as a celebrity, or raise it above 4 so the celeb gets pushed. Watch how the same post travels a different path — that switch is the core design decision for a feed.

Same 5 steps, different hingeURL shortener hinged on code generation + sharding; the feed hinges on fan-out strategy. Every system has one or two core decisions; the method (requirements → API → data → architecture → scale) is what surfaces them. WhatsApp hinges on per-recipient queues (SD7); Uber on a geospatial index + matching queue.

Project SD · Design a system end to end

Context: The interview signal for system design is narrating a repeatable method, not just coding a data structure. This capstone asks you to design a whole system end to end and defend the scaling choices.

Your task: Pick a system (Dropbox, ticket-booking, Twitter search) and produce a 5-step writeup, an evolving runnable Python core, an architecture diagram, and a scale plan.

Requirements:

A 5-step writeup (requirements → API → data model → core → scale)
A runnable Python core evolved through at least beginner → intermediate → advanced
An architecture diagram
A capacity estimate and which SD1-SD7 techniques apply where
Presented as if in an interview, stating the method out loud

💡 Hint: State the method aloud as you go — the panel is grading your process as much as the result; reuse the shortener's beginner→advanced evolution as the template.

🪜 Practice ladder beginner → industry

Six graded exercises, easy to real-world. Try each before opening its solution.

Exercise 1 · Scaffold: in-memory shortener with base62 codesBeginner

Context: System design starts by making it work and ignoring scale. A URL shortener is a dict of code → URL plus an incrementing counter fed through base62, which keeps codes short and URL-safe.

Your task: Implement an in-memory shortener with base62 codes: shorten(url) and resolve(code), confirming codes climb 1, 2, 3.

Requirements:

A base62 encode over digits + letters
A counter guarantees unique, ascending codes
shorten stores and returns the code
resolve returns the URL or None for an unknown code
Show the first codes ascend

💡 Hint: This is step one of the method (requirements/API) in ~20 lines; base62 of a monotonic counter gives short, unique codes for free.

Show solution

Design. Step 1 of the method (requirements/API) in 20 lines: shorten(url)->code, " "resolve(code)->url. base62 keeps codes short and URL-safe; the counter guarantees " "uniqueness.

import string
ALPHABET = string.digits + string.ascii_letters   # 62 chars

def encode(n):
    if n == 0: return ALPHABET[0]
    out = []
    while n:
        n, r = divmod(n, 62); out.append(ALPHABET[r])
    return "".join(reversed(out))

class TinyURL:
    def __init__(self): self._store = {}; self._next = 1
    def shorten(self, url):
        code = encode(self._next); self._store[code] = url
        self._next += 1; return code
    def resolve(self, code): return self._store.get(code)

t = TinyURL()
print(t.shorten("https://a.com"), t.shorten("https://b.com"))  # 1 2
print(t.resolve("1"), t.resolve("zzz"))                        # https://a.com None

Exercise 2 · Core feature: persist it (survive restarts)Intermediate

Context: A real service outlives its process, so storage moves to SQLite. The DB's primary key becomes the counter — the code is just encode(id) — and a parameterized query prevents injection.

Your task: Move storage to SQLite so the DB assigns the id (read back as lastrowid) and resolve decodes the code back to the id, and prove data survives a reconnect.

Requirements:

A base62 encode/decode pair
The DB primary key is the counter; the code is encode(id)
Inserts use parameterized SQL (no string interpolation)
resolve decodes the code and looks up by id
Data survives a fresh connection to the same store

💡 Hint: Let the primary key be the counter so lastrowid is the id you encode; a shared in-memory SQLite DB lets the demo run anywhere while still proving persistence.

Show solution

Design. Steps 2-3 (API + data model). The DB's PRIMARY KEY is the counter, so the " "code is just encode(id). A parameterized WHERE id = ? prevents injection. Use an " "in-memory shared DB here so it runs anywhere.

import sqlite3, string
ALPHABET = string.digits + string.ascii_letters
def encode(n):
    if n == 0: return ALPHABET[0]
    out=[]
    while n: n, r = divmod(n, 62); out.append(ALPHABET[r])
    return "".join(reversed(out))
def decode(code):
    n = 0
    for ch in code: n = n * 62 + ALPHABET.index(ch)
    return n

class TinyURL:
    def __init__(self, con):
        self.con = con
        con.execute("CREATE TABLE IF NOT EXISTS urls(id INTEGER PRIMARY KEY, url TEXT)")
    def shorten(self, url):
        cur = self.con.execute("INSERT INTO urls(url) VALUES(?)", (url,))
        return encode(cur.lastrowid)
    def resolve(self, code):
        row = self.con.execute("SELECT url FROM urls WHERE id=?",
                               (decode(code),)).fetchone()
        return row[0] if row else None

con = sqlite3.connect("file:sd?mode=memory&cache=shared", uri=True)
t = TinyURL(con); code = t.shorten("https://pricing")
print(code, TinyURL(con).resolve(code))   # 1 https://pricing -- survives new handle

Exercise 3 · Harder variant: LRU cache on the read-heavy pathAdvanced

Context: Redirects are read-heavy and latency-sensitive, and most reads hit a few hot codes. A fixed-size LRU cache checked before the DB serves those hot codes without touching storage.

Your task: Add a fixed-size LRU cache checked before the DB; on a miss, read the DB then populate the cache. Prove a hot code skips the DB and that eviction is least-recently-used.

Requirements:

An OrderedDict-backed LRU with O(1) get/put
get moves the key to most-recently-used; over capacity evicts the LRU
resolve checks the cache first and only reads the DB on a miss
A DB-read counter proves a hot code avoids the DB
Eviction removes the least-recently-used entry

💡 Hint: move_to_end on access and popitem(last=False) to evict; count DB reads so you can prove the cache actually short-circuits the slow path.

Show solution

Design. Step 5 (scale) applied where the numbers demand: most reads hit a few hot codes. " "OrderedDict gives O(1) LRU — move_to_end on get, popitem(last=False) " "to evict. Count DB reads to prove the cache works.

from collections import OrderedDict

class LRUCache:
    def __init__(self, cap): self.cap = cap; self.d = OrderedDict()
    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k); return self.d[k]
    def put(self, k, v):
        self.d[k] = v; self.d.move_to_end(k)
        if len(self.d) > self.cap: self.d.popitem(last=False)  # evict LRU

class Store:
    def __init__(self, cache_size=2):
        self.db = {"1": "https://a", "2": "https://b", "3": "https://c"}
        self.cache = LRUCache(cache_size); self.db_reads = 0
    def resolve(self, code):
        hit = self.cache.get(code)
        if hit is not None: return hit           # fast path, no DB
        self.db_reads += 1                        # slow path
        v = self.db.get(code); self.cache.put(code, v); return v

s = Store(cache_size=2)
s.resolve("1"); s.resolve("1"); s.resolve("1")   # 1 miss, 2 hits
print("db_reads:", s.db_reads)                    # 1
s.resolve("2"); s.resolve("3")                    # evicts '1'
print("1 cached?", s.cache.get("1") is not None)  # False -- LRU evicted

Exercise 4 · Subtle correctness: consistent-hash sharding (minimal key movement)Expert

Context: One DB can't hold billions of rows. A consistent-hash ring shards so that adding a shard moves only ~1/N of keys — unlike hash % N, which reshuffles almost everything.

Your task: Shard with a consistent-hash ring so the same code always maps to the same shard, and measure how few keys move when you add a node.

Requirements:

Virtual nodes spread each physical shard around the ring
A key maps to the next node clockwise (bisect on a sorted ring)
The same code deterministically maps to the same shard
Adding a shard remaps only a small fraction of keys
The measured movement is far below what hash % N would cause

💡 Hint: Hash each of many virtual nodes onto the ring and use bisect to find the next node; compare the before/after mapping to count how few keys actually move.

Show solution

Design. Step 5 at web scale (SD7). Virtual nodes spread load; bisect finds the " "next node clockwise. The property that matters: adding a shard remaps only ~1/N of keys — unlike " "hash % N, which reshuffles almost all of them.

import hashlib, bisect

class HashRing:
    def __init__(self, nodes=(), vnodes=100):
        self.vnodes = vnodes; self._ring = {}; self._sorted = []
        for n in nodes: self.add(n)
    def _h(self, key): return int(hashlib.md5(key.encode()).hexdigest(), 16)
    def add(self, node):
        for i in range(self.vnodes):
            h = self._h(f"{node}:{i}"); self._ring[h] = node
            bisect.insort(self._sorted, h)
    def get(self, key):
        h = self._h(key); i = bisect.bisect(self._sorted, h) % len(self._sorted)
        return self._ring[self._sorted[i]]

keys = [f"code{i}" for i in range(2000)]
r1 = HashRing(["db0", "db1", "db2"])
before = {k: r1.get(k) for k in keys}
r2 = HashRing(["db0", "db1", "db2", "db3"])       # add a shard
moved = sum(1 for k in keys if before[k] != r2.get(k))
print("deterministic:", r1.get("code7") == r1.get("code7"))  # True
print(f"moved {moved}/{len(keys)} keys")   # ~1/4, not ~all

Exercise 5 · Production concerns: Snowflake IDs (no coordinator, sortable)Professional

Context: Sharding removes the single auto-increment counter, so shards must mint unique ids without coordinating. Snowflake ids pack timestamp, machine, and sequence into 64 bits — unique across machines and roughly time-sortable.

Your task: Implement Snowflake-style 64-bit ids (timestamp | machine | sequence) that are unique across machines and sortable, covering the sequence-exhausted-within-a-millisecond edge.

Requirements:

High bits are time (sortable), middle bits machine id, low bits a per-ms sequence
Different machines never collide on the same timestamp
The sequence is masked to its bit width
On sequence overflow within a ms, spin to the next ms
now_ms is injectable so it's testable

💡 Hint: Shift and OR the three fields into one integer; when the per-ms sequence wraps to zero, advance the clock rather than reusing an id.

Show solution

Design. Coordination-free ids: high bits are time (sortable), middle bits are machine id " "(no collisions across shards), low bits a per-ms sequence. When the sequence overflows in one ms, spin to " "the next ms. Inject now_ms so it's testable.

import threading

class SnowflakeID:
    def __init__(self, machine_id, epoch_ms=1_700_000_000_000):
        self.machine_id = machine_id & 0x3FF     # 10 bits
        self.epoch = epoch_ms; self.seq = 0
        self.last_ms = -1; self._lock = threading.Lock()
    def next_id(self, now_ms):
        with self._lock:
            if now_ms == self.last_ms:
                self.seq = (self.seq + 1) & 0xFFF     # 12-bit sequence
                if self.seq == 0:                     # exhausted this ms
                    while now_ms <= self.last_ms: now_ms += 1
            else:
                self.seq = 0
            self.last_ms = now_ms
            return (((now_ms - self.epoch) << 22)
                    | (self.machine_id << 12) | self.seq)

g0, g1 = SnowflakeID(0), SnowflakeID(1)
a = g0.next_id(1_700_000_050_000)
b = g1.next_id(1_700_000_050_000)      # same ms, different machine
print(a != b)                          # True -- machine bits prevent collision
c = g0.next_id(1_700_000_050_001)
print(c > a)                           # True -- later ms sorts higher

Exercise 6 · Real-world: re-apply the method to a news feed (fan-out choice)Industry scenario

Context: The method generalizes. A news feed forces the classic scaling decision: fan-out on write (push to followers) vs fan-out on read (pull), with celebrities pulled to avoid write storms.

Your task: Design a news feed and make the fan-out decision, handling the celebrity/hot-key edge where huge follower counts must use read fan-out.

Requirements:

Follow relationships and posts are modelled
Normal authors push to followers' feeds on write
Celebrities (over a follower threshold) are pulled at read time
A follower-count threshold picks the strategy per author
The choice avoids a write storm for high-follower authors

💡 Hint: Threshold on follower count: push for normal users, pull for celebrities; a hybrid-per-author strategy is what real feeds use to avoid the fan-out storm.

Show solution

Design. Same method, new prompt. The scaling insight (SD6/SD7): pushing a celebrity's post to " "millions of feeds on write is a fan-out storm, so celebrities are pulled at read time and normal users are " "pushed. Threshold on follower count picks the strategy per author.

from collections import defaultdict, deque

class NewsFeed:
    def __init__(self, celeb_threshold=3):
        self.followers = defaultdict(set)
        self.follows = defaultdict(set)
        self.posts = defaultdict(list)                      # author -> [(ts, text)]
        self.pushed = defaultdict(lambda: deque(maxlen=100))
        self.th = celeb_threshold
    def follow(self, u, author):
        self.follows[u].add(author); self.followers[author].add(u)
    def post(self, author, ts, text):
        self.posts[author].append((ts, text))
        if len(self.followers[author]) < self.th:           # normal -> push (write)
            for f in self.followers[author]:
                self.pushed[f].append((ts, text, author))
        # celebrity -> do nothing on write; pulled at read time
    def feed(self, u):
        items = list(self.pushed[u])                        # pushed (normal authors)
        for author in self.follows[u]:                      # pull celebrities
            if len(self.followers[author]) >= self.th:
                items += [(ts, txt, author) for ts, txt in self.posts[author]]
        return sorted(items, reverse=True)[:100]

nf = NewsFeed(celeb_threshold=3)
for u in ("a", "b", "c"): nf.follow(u, "celeb")     # celeb has 3 followers
nf.follow("a", "bob")                                # bob is a normal author
nf.post("celeb", 2, "big news")                      # NOT pushed (pulled)
nf.post("bob", 1, "hi")                              # pushed to 'a'
print(len(nf.pushed["a"]))                            # 1  -- only bob pushed
print([t for _, t, _ in nf.feed("a")])               # ['big news', 'hi'] -- celeb pulled in

✓ Checkpoint — you can move on when you can…

Apply the 5-step method to an unseen prompt without hesitation.
Evolve a system from a working prototype to a web-scale design, in runnable Python.
Explain the core decision(s) each system hinges on (codes/sharding, fan-out, geospatial).
Justify every choice with the right SD1–SD7 building block.

📋 Staff-level self-scoring — is this system design defensible in review?

Dimension	Meets the bar	Above the bar (staff)
Requirements coverage	Functional and non-functional requirements are stated (read-heavy, low-latency redirects, eventual billions of URLs) before any design.	Requirements are quantified with a back-of-envelope load estimate (QPS, storage, read:write ratio) that drives the design decisions that follow.
API & data model	The API is a small, explicit contract (`shorten`/`resolve`) and the data model names its primary/shard key.	The shard key is justified against the access pattern, and the code-generation scheme (counter, hash, distributed ID) is chosen with its collision/coordination tradeoffs stated.
Scalability	The design evolves from in-memory to persisted to cached to sharded, applying caching/replication/sharding where the numbers demand — not everywhere.	A distributed-ID scheme and rate limiting are designed for the web-scale tier, and the hot-read path (redirects) is optimized with a stated cache hit-rate target.
Tradeoff justification	Each added component is justified by a requirement; CAP/consistency choices are named for reads vs writes.	You can defend why you did not add a component, and you state the consistency model per operation (e.g. eventually-consistent analytics, strongly-consistent create).
Failure modes	You name what happens on a DB/cache node loss and on a traffic spike.	Cache stampede, hot shard, ID-generator outage, and replication lag are each addressed with a concrete mitigation.
Communication	You can present the design as the five steps (requirements → API → data model → architecture → scale) clearly.	The same method transfers to a second, different system (e.g. the news feed) without restarting from scratch — evidence the method, not the answer, is learned.

Score each dimension 0 (missing), 1 (meets bar), or 2 (above bar). 0–5: a sketch. 6–9: an interview-ready design. 10–12: staff-level — quantified, scaled where the numbers demand, tradeoffs and failure modes defended, and the method transfers to a new problem. A 0 on Requirements coverage undermines everything above it — fix first.

Knowledge check check yourself

✓ Knowledge check

Why does the case study build one system (a URL shortener) four times across tiers instead of jumping straight to the web-scale design?

Show answer

Each tier adds only what the previous one couldn't do — in-memory, then persisted+API, then cached+analytics, then sharded/web-scale — so you apply caching, CAP, sharding, and queues where the numbers actually demand them. It teaches that scale is earned in response to load, not added upfront.

✓ Knowledge check

In the 5-step design method, why does the Scale step come last, after requirements, API, data model, and architecture?

Show answer

Because you estimate load against a concrete design and then apply caching, replication, sharding, or queues only where the numbers demand — scaling decisions must be justified by the requirements and traffic, not applied speculatively before the system is even defined.

Educational content, provided as-is and without warranty. Code samples are examples — review, test, and adapt them before using in production. See the Terms of Use & Disclaimer. Use at your own risk.

Learning objectives

1 · The method — 5 steps, every time essential

2 · Beginner build — make it work (in memory) essential

3 · Intermediate build — persist it + an API intermediate

4 · Advanced build — cache + analytics advanced

5 · Expert build — scale to billions expert

6 · Apply the method again — a news feed expert

Project SD · Design a system end to end

🪜 Practice ladder beginner → industry

✓ Checkpoint — you can move on when you can…

Knowledge check check yourself

More in Projects