System Design · Chapter SD6

Scalability & CAP

Scalability from "one server is full" to CAP and capacity math: horizontal scaling, statelessness, replication, and CP-vs-AP — each with a runnable Python simulation.

⏱️ ~3 hours🧪 4 labs🎯 Beginner→Expert

🌱 Start here — from zero Scalability, from scratch — start from "one server is full — now what?" and build up to CAP and capacity math.

Scalability is how a system handles growth. When one server can't keep up you either buy a bigger one (vertical) or add more (horizontal) — and adding more only works if your app is stateless. This chapter climbs from those basics through replication and the CAP theorem to back-of-envelope capacity estimation, with runnable Python simulations.

The words you'll hear (in plain terms):

Term	What it actually means
scaling	handling more load: vertical (bigger box) or horizontal (more boxes).
stateless	a server keeps no per-user memory, so any server can handle any request.
replication	keeping copies of data on several machines for safety and read speed.
consistency	whether every read sees the latest write.
CAP	under a network partition, choose Consistency or Availability — not both.

What you need before starting:

The HLD chapter (SD5) sets the scene.
Basic Python; the sims are plain Python.
Comfort with rough arithmetic for capacity estimates.

New to the topic? Read this box, then take the chapters in order — each section is tagged essential → expert so you always know the depth you're at.

Learning objectives

Distinguish vertical from horizontal scaling and why statelessness matters.
Simulate primary-replica replication and eventual consistency.
State the CAP theorem and classify systems as CP or AP.
Estimate server/replica counts from a QPS target.

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

1 · Two ways to scale essential

Vertical = a bigger machine (simple, but capped and pricey). Horizontal = more machines (cheap, effectively unlimited — but requires stateless app servers). Modern systems scale horizontally.

🗺️ How to read this diagram

This picture answers one question every growing system hits: "one server is full — now what?" It shows the two directions you can grow in, read left to right.

The left box ("More load") is the trigger: more users, more requests — "pressure" your current server can't handle.
The first arrow points to "Vertical: bigger box" — you keep one machine but make it more powerful (more CPU/RAM). The sub-label "simple, capped" is the catch: it's easy, but there's a limit to how big one machine can get, and big machines are expensive.
The second arrow points to "Horizontal: more boxes" — instead of one huge machine you add many ordinary ones and split the work between them. "stateless, unbounded" means: if your servers keep no per-user memory (stateless), you can keep adding boxes almost without limit.
The arrows are a progression, not a network diagram — they read like "load grows → first you go vertical → eventually you must go horizontal." Modern large systems live on the right-hand side.

In short: Vertical = a bigger machine (quick fix, hits a ceiling). Horizontal = more machines (cheaper, scales far) — but only works if the app is stateless. The rest of this chapter is really about making horizontal scaling safe.

Statelessness is the enablerIf a server keeps session state in memory, request #2 must hit the same server — you can't freely add boxes. Push state to a shared store (cache/DB), keep app servers stateless, and any server handles any request. That's why SD5's load balancers work.

2 · Statelessness, demonstrated essential

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 · Stateful (breaks) vs stateless (scales)

stateless.py# STATEFUL: session lives in one server's memory -> must be sticky
class StatefulServer:
    def __init__(self): self.sessions = {}
    def login(self, user): self.sessions[user] = "token"
    def check(self, user): return user in self.sessions

s1, s2 = StatefulServer(), StatefulServer()
s1.login("ava")
print("stateful, wrong server:", s2.check("ava"))   # False! request hit s2

# STATELESS: session in a SHARED store -> any server works
shared = {}
class StatelessServer:
    def login(self, user): shared[user] = "token"
    def check(self, user): return user in shared

a, b = StatelessServer(), StatelessServer()
a.login("ava")
print("stateless, any server:", b.check("ava"))     # True

stateful, wrong server: False
stateless, any server: True

▶ How this works

This lab shows why horizontal scaling needs stateless servers. It builds two toy servers twice: first the broken "stateful" way (each server remembers logins in its own memory), then the fixed "stateless" way (logins live in a store both servers share).

StatefulServer keeps self.sessions = {} — a private dictionary inside that one server. When s1.login("ava") runs, only s1 knows about Ava.
So s2.check("ava") returns False: the request landed on the wrong server, and s2 never saw the login. This is why stateful servers need "sticky" routing — every request from a user must return to the same box.
StatelessServer fixes it by reading and writing a single shared dictionary that lives outside the servers (think of a shared cache or database). Both a and b talk to the same shared store.
Now a.login("ava") writes to shared, and b.check("ava") reads the same shared store and returns True — any server can answer any request. That is exactly what lets you add more boxes freely.

What the output means: stateful, wrong server: False then stateless, any server: True — the first design loses the login when the request hits a different server; the second one doesn't, because the state is shared.

Try this: Add a third stateless server c = StatelessServer() and call c.check("ava") — it also returns True without any extra work, because the login lives in the shared store, not in any single server.

3 · Replication & eventual consistency intermediate

Replication keeps copies on multiple machines: survive failures and serve reads from replicas. The catch is sync lag — a replica may briefly serve stale data (eventual consistency).

Step 2 · Primary-replica with lag

replication.pyclass Primary:
    def __init__(self): self.data = {}
    def write(self, k, v): self.data[k] = v

class Replica:
    def __init__(self, primary): self.primary = primary; self.data = {}
    def sync(self): self.data = dict(self.primary.data)   # periodic catch-up
    def read(self, k): return self.data.get(k)

primary = Primary(); replica = Replica(primary)
primary.write("x", 1)
print("before sync (stale):", replica.read("x"))   # None
replica.sync()
print("after sync:", replica.read("x"))             # 1

before sync (stale): None
after sync: 1

▶ How this works

Replication means keeping copies of your data on more than one machine — so you survive a machine failure and can serve read requests from the copies. This lab models the simplest setup: one primary that takes writes, and one replica that copies from it. It also shows the catch: the replica can lag behind and briefly serve stale (out-of-date) data.

Primary holds the real data in self.data and its write(k, v) method stores a value — this is the machine that accepts changes.
Replica starts empty and only catches up when sync() runs: self.data = dict(self.primary.data) copies the primary's current data. In a real system this sync happens continuously but with a small delay.
The script writes primary.write("x", 1), then immediately reads from the replica before syncing — so replica.read("x") returns None. The replica simply hasn't received the update yet. This gap is called eventual consistency: the copy will be correct eventually, just not this instant.
After replica.sync() the copy is up to date, so replica.read("x") now returns 1.

What the output means: before sync (stale): None then after sync: 1 — the replica served wrong (empty) data in the tiny window before it caught up, then correct data afterward.

Try this: Write a second value (primary.write("y", 2)) after the sync and read replica.read("y") before syncing again — you'll see None once more. Every new write reopens the stale-read window until the next sync.

4 · The CAP theorem advanced

CAP: when a network partition splits your machines, you must choose Consistency (reject requests to stay correct) or Availability (answer, possibly stale). Partitions happen, so P isn't optional — the real choice is CP vs AP.

Choice	During a partition	Examples
CP	reject to stay correct	traditional SQL, ZooKeeper, etcd
AP	answer, maybe stale	Cassandra, DynamoDB, DNS

Step 3 · Simulate a CP vs AP choice under partition

cap.pyclass Node:
    def __init__(self, mode): self.mode = mode; self.value = None; self.reachable = True
    def read(self):
        if not self.reachable and self.mode == "CP":
            return ("error", "unavailable to stay consistent")   # CP: refuse
        return ("ok", self.value)                                 # AP: answer (maybe stale)

cp = Node("CP"); cp.value = "v1"; cp.reachable = False   # partitioned off
ap = Node("AP"); ap.value = "v1"; ap.reachable = False
print("CP node:", cp.read())     # refuses
print("AP node:", ap.read())     # answers with possibly-stale v1

CP node: ('error', 'unavailable to stay consistent')
AP node: ('ok', 'v1')

▶ How this works

This lab makes the CAP theorem concrete. CAP says: when the network partitions (machines can't reach each other), a system must pick one of two behaviours — stay Consistent (only ever return correct data, even if that means refusing) or stay Available (always answer, even if the data might be stale). You cannot have both during a partition. Systems that pick correctness are called CP; systems that pick answering are AP.

A Node has a mode ("CP" or "AP"), a stored value, and a reachable flag. Setting reachable = False simulates "this node is cut off by a network partition."
In read(), the CP node checks: if it's unreachable and its mode is CP, it refuses — returning an error rather than risk serving out-of-date data. Correctness wins over answering.
Any other case (including the AP node) falls through to return ("ok", self.value) — it answers anyway with whatever value it last had, which might be stale. Availability wins over correctness.
The script cuts off both nodes (reachable = False), then reads each. The CP node returns an error; the AP node returns its possibly-old "v1". Same partition, opposite choices.

What the output means: CP node: ('error', 'unavailable to stay consistent') and AP node: ('ok', 'v1') — CP would rather fail than lie; AP would rather answer than fail.

Try this: Set the CP node's reachable = True and read again — it now answers normally. That's the real lesson: CAP only forces the hard choice during a partition; when the network is healthy you get both consistency and availability.

CAP is about partitions, not everyday lifeWhen the network is healthy you get both C and A. CAP only forces the choice during a partition. 'CP vs AP under partition' is the interview-level model (PACELC refines it).

5 · Expert — capacity estimation expert

Design work needs rough numbers: 1 server or 1,000? Learn to estimate from a few facts. Latency figures every engineer should know, roughly:

Operation	~Time
memory read	~100 ns
SSD read	~100 µs
same-region round-trip	~0.5 ms
indexed DB query	~1–10 ms
cross-continent round-trip	~150 ms

Step 4 · Size a fleet for a target QPS (runs standalone)

capacity.pydef size_fleet(dau, req_per_user_per_day, per_server_qps, peak_factor=3):
    avg_qps = dau * req_per_user_per_day / 86_400
    peak_qps = avg_qps * peak_factor            # traffic is bursty
    servers = -(-int(peak_qps) // per_server_qps)   # ceil division
    return round(avg_qps), round(peak_qps), servers

avg, peak, servers = size_fleet(dau=1_000_000, req_per_user_per_day=20, per_server_qps=500)
print(f"avg {avg} qps, peak ~{peak} qps -> {servers} app servers (+ headroom)")

# read-heavy? size read replicas separately:
reads = peak * 0.9                               # 90% reads
replicas = -(-int(reads) // 800)                 # each replica ~800 read qps
print(f"peak reads ~{round(reads)} qps -> {replicas} read replicas")

avg 231 qps, peak ~694 qps -> 2 app servers (+ headroom)
peak reads ~625 qps -> 1 read replicas

▶ How this works

This lab is capacity estimation — the back-of-the-envelope math that answers "how many servers do I need?" from a few facts. It's the exact reasoning interviewers want to hear, done step by step: users → requests per second → peak → number of machines.

avg_qps = dau * req_per_user_per_day / 86_400 turns daily activity into an average QPS (queries per second). dau is daily active users, and 86_400 is the number of seconds in a day — the underscores are just readability, Python ignores them.
peak_qps = avg_qps * peak_factor multiplies by 3 because traffic is bursty — real usage clumps at busy hours, so you must size for the peak, not the average, or you'll fall over when it matters.
servers = -(-int(peak_qps) // per_server_qps) is a trick for rounding up (ceiling division): if peak is 694 and each server handles 500, you need 2 servers, not 1. Normal // rounds down, so negating twice flips it to round up.
The second half sizes read replicas separately: reads = peak * 0.9 assumes 90% of traffic is reads, then divides by each replica's read capacity (800 qps) with the same round-up trick. Reads and writes often need different amounts of hardware.

What the output means: avg 231 qps, peak ~694 qps -> 2 app servers and peak reads ~625 qps -> 1 read replicas — from a million users you land on a small, concrete fleet size.

Try this: Change dau to 10_000_000 (10× the users) and re-run — every number scales up and you'll need roughly 10× the servers. Then drop per_server_qps to 200 and watch the server count jump: weaker machines mean more of them.

Interviewers grade the method, not the numberState assumptions → avg → peak → divide by per-unit capacity → add headroom. The same math sizes databases, caches, and queues (SD7). Say it out loud as you go.

Exercise SD6.1 — Scale a read-heavy service

Context: Sizing a read-heavy service end to end is the bread-and-butter scalability exercise: estimate load, provision the app and replica tiers, choose a consistency stance, and prove the read-routing behaves under lag.

Your task: For a service with 10M daily active users, 90% reads, and a 5ms DB query, estimate peak QPS, size both app servers and read replicas, choose CP or AP with justification, and extend the replication simulation to route reads to a replica pool and writes to the primary, showing a stale read during lag.

Requirements:

Estimate peak QPS from DAU and the read/write split
Size app servers and read replicas from the QPS and per-node limits
Choose CP or AP for this workload and justify the choice
Route reads across a pool of replicas and writes to the primary
Demonstrate a stale read occurring during replication lag

💡 Hint: Peak QPS is well above the daily average, so apply a peak multiplier; replicas carry the read fan-out while writes stay on the primary, which is where the stale-read window appears.

🪜 Practice ladder beginner → industry

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

Exercise 1 · Vertical vs horizontal, quantifiedBeginner

Context: There are two ways to add capacity: a bigger box (vertical) or more boxes (horizontal). Vertical is simplest until you hit the largest instance; past that, only horizontal keeps growing.

Your task: Model the maximum throughput of vertical scaling (one box, capped at some core count) versus horizontal scaling (add nodes), and show where horizontal overtakes.

Requirements:

Model vertical throughput as cores times per-core rps, capped at a maximum core count
Model horizontal throughput as nodes times per-node rps, uncapped
Show vertical throughput plateauing once the biggest box is reached
Show horizontal throughput continuing to rise as nodes are added
Conclude that beyond the biggest single box, only horizontal scaling adds capacity — which requires statelessness

💡 Hint: The vertical function needs a min(cores, max_cores) cap; the crossover is wherever added nodes exceed what the capped single box can ever do.

Show solution

Vertical hits a ceiling; horizontal keeps going:

def vertical(cores, per_core_rps=100, max_cores=32):
    return min(cores, max_cores) * per_core_rps      # capped by biggest box

def horizontal(nodes, per_node_rps=800):
    return nodes * per_node_rps                        # add boxes

print("vertical @64 cores:", vertical(64))   # 3200 (capped at 32 cores)
print("horizontal @5 nodes:", horizontal(5)) # 4000
# Beyond the biggest single box, only horizontal scaling adds capacity.

Vertical scaling is simplest until you hit the largest instance; past that, throughput only grows by adding nodes — which requires statelessness.

Exercise 2 · Statelessness enables horizontal scaleIntermediate

Context: Horizontal scaling only works if any node can serve any request. Session state kept in one node's local memory pins users to that node and breaks load balancing the moment a request lands elsewhere.

Your task: Contrast a stateful server that stores sessions in local memory (which fails when a request hits the wrong node) with a stateless one that stores sessions in a shared store (where any node works).

Requirements:

Build a stateful node that keeps sessions in its own memory
Show a login on one node not being visible on a second node
Build a stateless node that reads and writes sessions to a shared store
Show a login on one stateless node being visible from another
Explain that moving state to a shared store is the precondition for round-robin load balancing

💡 Hint: Give the stateful nodes separate dicts and the stateless nodes one shared dict; the difference between True False and True True is the whole point.

Show solution

State in local memory pins a user to a node and breaks load balancing:

# Stateful: session lives on ONE node -> requests to another node fail
class StatefulNode:
    def __init__(self): self.sessions = {}
    def login(self, user): self.sessions[user] = "token"
    def check(self, user): return user in self.sessions

n1, n2 = StatefulNode(), StatefulNode()
n1.login("ada")
print(n1.check("ada"), n2.check("ada"))   # True False  <-- broken on n2!

# Stateless: session in a SHARED store; any node works
shared = {}
class StatelessNode:
    def login(self, user): shared[user] = "token"
    def check(self, user): return user in shared

s1, s2 = StatelessNode(), StatelessNode()
s1.login("ada")
print(s1.check("ada"), s2.check("ada"))   # True True

Moving session state to a shared store makes every node interchangeable — the precondition for round-robin load balancing to work.

Exercise 3 · Replication & eventual consistencyAdvanced

Context: Read replicas scale read throughput, but asynchronous replication means a replica can lag the primary. That lag window is exactly where eventual consistency shows up.

Your task: Simulate a primary with asynchronous replicas and show a read hitting a stale replica before replication has caught up, then the correct value after it runs.

Requirements:

Model a primary plus a set of replicas and a pending-write buffer
On a write, update the primary and queue the change as pending (not yet on replicas)
Provide a replicate step that flushes pending writes to every replica
Read a replica before replication and get a stale (missing) value
Read again after replication and get the correct value — eventual consistency in action

💡 Hint: Keep writes in a pending list until replicate() flushes them; the gap between write and flush is the "eventual" — fine for a like count, not a bank balance.

Show solution

Async replication trades freshness for read throughput:

class Replicated:
    def __init__(self, n_replicas):
        self.primary = {}
        self.replicas = [{} for _ in range(n_replicas)]
        self.pending = []
    def write(self, k, v):
        self.primary[k] = v
        self.pending.append((k, v))          # not yet on replicas
    def replicate(self):
        for k, v in self.pending:
            for r in self.replicas: r[k] = v
        self.pending.clear()
    def read_replica(self, i, k):
        return self.replicas[i].get(k)

db = Replicated(2)
db.write("x", 1)
print(db.read_replica(0, "x"))   # None  <-- stale, replication hasn't run
db.replicate()
print(db.read_replica(0, "x"))   # 1     <-- eventually consistent

The window between write and replicate is the "eventual" in eventual consistency — fine for a like count, not for a bank balance.

Exercise 4 · CAP: choose CP or AP under partitionExpert

Context: The CAP theorem says that under a network partition you must choose between consistency and availability — there is no "CA" once the network splits. Systems encode this choice as a policy.

Your task: Model both a CP and an AP write policy and show that under a partition the CP policy refuses the write while the AP policy accepts it, risking divergence.

Requirements:

Take a policy and a partitioned flag as inputs
Under a partition, have CP reject the write to stay consistent
Under a partition, have AP accept the write to stay available (risking divergence)
When there is no partition, accept the write normally
Explain the domain examples: a ledger chooses CP, a shopping cart often chooses AP and reconciles later

💡 Hint: The branch is just if partitioned then split on policy; the teaching point is that you are choosing which property to sacrifice, never keeping both.

Show solution

During a partition, CP and AP make opposite calls:

def handle_write(policy, partitioned):
    if partitioned:
        if policy == "CP":
            return "REJECT (stay consistent, sacrifice availability)"
        if policy == "AP":
            return "ACCEPT (stay available, risk divergence)"
    return "ACCEPT (no partition)"

for p in ("CP", "AP"):
    print(p, "->", handle_write(p, partitioned=True))
# CP -> REJECT (stay consistent, sacrifice availability)
# AP -> ACCEPT (stay available, risk divergence)

There's no "CA" under a real partition — you only choose which to give up. A ledger picks CP; a shopping cart often picks AP and reconciles later.

Exercise 5 · Back-of-envelope capacity estimateProfessional

Context: Back-of-envelope storage and bandwidth estimates decide whether one database suffices or you need to shard. It's the classic interview and design-review calculation.

Your task: For a service with D daily writes of S bytes each, retained for R years, compute the total storage and the average write bandwidth.

Requirements:

Compute per-day bytes as daily writes times bytes each
Compute total bytes across the full retention period (days times years)
Compute average write bandwidth as per-day bytes divided by seconds per day
Return the figures in human-friendly units (GB per day, TB total, KB/s average)
Use the totals to judge whether one DB suffices or sharding is needed

💡 Hint: Keep the unit conversions explicit (bytes to GB/TB, per-day to per-second); the total is what you carry into the sharding decision in the next chapter.

Show solution

The classic interview/design estimate, as a calculator:

def estimate(daily_writes, bytes_each, retention_years):
    per_day_bytes = daily_writes * bytes_each
    total_bytes = per_day_bytes * 365 * retention_years
    avg_write_bps = per_day_bytes / 86400          # bytes per second
    GB = 1024 ** 3
    return {
        "per_day_GB": round(per_day_bytes / GB, 2),
        "total_TB": round(total_bytes / GB / 1024, 2),
        "avg_write_KBps": round(avg_write_bps / 1024, 1),
    }

print(estimate(daily_writes=10_000_000, bytes_each=500, retention_years=3))
# {'per_day_GB': 4.66, 'total_TB': 4.99, 'avg_write_KBps': 56.5}

10M writes/day × 500B ≈ 4.7 GB/day, ≈ 5 TB over 3 years — enough to decide whether one DB suffices or you need sharding (SD7).

Exercise 6 · Scaling plan across growth stagesIndustry scenario

Context: Scaling is staged, not a single leap. As projected load grows, the right move changes from a single box, to read replicas, to sharding — and simple thresholds can encode that escalation.

Your task: Given projected read and write rps at launch, six months, and a year, write a decision function that chooses at each stage between a single box, adding replicas, and sharding, using simple thresholds.

Requirements:

Keep everything on a single box while total load is under its capacity
Add read replicas (or replicas plus a read cache) when read rps exceeds one box
Escalate to sharding writes once write rps exceeds what one box handles
Return the list of scaling moves recommended for the given load
Encode the key fact that replicas scale reads but never writes

💡 Hint: Split the read and write decisions: replicas answer read pressure, sharding answers write pressure — so a high write rps must trigger sharding no matter the read path.

Show solution

A decision function that maps load to the right scaling move:

def scaling_decision(read_rps, write_rps,
                     single_box_cap=1000, replica_read_cap=8000):
    plan = []
    if read_rps + write_rps <= single_box_cap:
        plan.append("single box")
    else:
        if read_rps > single_box_cap:
            plan.append("add read replicas" if read_rps <= replica_read_cap
                        else "add replicas + read cache")
        if write_rps > single_box_cap:
            plan.append("shard writes (SD7)")   # replicas don't scale writes
    return plan

print(scaling_decision(500, 300))       # ['single box']
print(scaling_decision(5000, 400))      # ['add read replicas']
print(scaling_decision(9000, 2000))     # ['add replicas + read cache', 'shard writes (SD7)']

Replicas scale reads but never writes — so once write rps exceeds one box, the plan correctly escalates to sharding.

✓ Checkpoint — you can move on when you can…

Contrast vertical/horizontal scaling and explain statelessness.
Simulate replication and eventual consistency.
State CAP and classify systems as CP or AP.
Estimate servers and replicas from a QPS target.

Knowledge check check yourself

✓ Knowledge check

The lesson contrasts vertical and horizontal scaling and says modern systems scale horizontally. What is the difference between the two, and what property must the app servers have for horizontal scaling to work?

Show answer

Vertical scaling means using one bigger, more powerful machine (simple but capped and pricey); horizontal scaling means adding more ordinary machines and splitting work across them (cheap and effectively unlimited). Horizontal scaling only works if the app servers are stateless, so any server can handle any request; per-user state must be pushed to a shared store like a cache or DB.

✓ Knowledge check

According to the CAP theorem as taught here, why isn't Partition-tolerance really optional, and what distinguishes a CP system from an AP system during a network partition?

Show answer

Partitions happen in real networks, so P isn't optional and the real choice is CP vs AP. During a partition a CP system rejects requests to stay correct (e.g., traditional SQL, ZooKeeper, etcd), while an AP system still answers with possibly-stale data to stay available (e.g., Cassandra, DynamoDB, DNS). When the network is healthy you get both consistency and availability.

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 · Two ways to scale essential

2 · Statelessness, demonstrated essential

3 · Replication & eventual consistency intermediate

4 · The CAP theorem advanced

5 · Expert — capacity estimation expert

Exercise SD6.1 — Scale a read-heavy service

🪜 Practice ladder beginner → industry

✓ Checkpoint — you can move on when you can…

Knowledge check check yourself

More in System design