DevPath
Tracks

Databases at Scale

Replication for reads and availability, sharding for size, consistency and CAP in plain terms, choosing SQL or NoSQL, and a hash-based shard router with fixed slots.

advanced45 min#replication#sharding#cap#consistency#nosql

Prerequisites: Databases and SQL, Caching Strategies

Why it matters

A single database server eventually runs out of something: disk, memory, CPU, or connections. It is also one machine that can fail. Scaling the data tier is harder than scaling stateless app servers because data has to live somewhere and stay correct. Two tools do most of the work: replication (copies for read capacity and survival) and sharding (splitting data so no machine holds all of it). Each brings consistency trade-offs you need to be able to explain.

Intuition

Replication is photocopying a book so several readers can read at once and one fire cannot destroy the only copy. The catch: when the author edits the original, the copies are briefly out of date.

Sharding is splitting an encyclopedia into volumes, A to F, G to M, and so on. Each volume is smaller and can sit on its own shelf. The catch: a question that spans volumes needs several lookups, and rebalancing the volumes later is real work.

How it works

Replication

In leader-follower replication, all writes go to one leader, which streams changes to followers. Reads can be served by followers, multiplying read capacity. If the leader dies, a follower is promoted (failover).

  • Asynchronous replication returns after the leader writes. It is fast, but followers lag, so a read from a follower can return old data, and an unreplicated write can be lost if the leader dies.
  • Synchronous replication waits for a follower to confirm. It is safer but slower, and a slow follower slows every write.

Replication helps reads and availability. It does not help write volume or total data size, because every node still holds everything.

Application
Writes
Reads
Leaderaccepts all writes
Follower 1serves reads
Follower 2serves reads
Read/write split: writes go only to the leader, which streams changes to followers, while reads fan out across followers. Read capacity grows with each follower, but write capacity does not.

Sharding

Sharding (horizontal partitioning) splits rows across independent databases by a shard key. Common strategies:

  • Range: key ranges per shard. Range queries are cheap, but hot ranges (like newest timestamps) overload one shard.
  • Hash: hash the key and map to a shard. Load spreads evenly, but range scans touch every shard.
  • Directory: a lookup table says where each key lives. Flexible, but the directory is another component to keep alive.

Hashing with hash % number_of_shards breaks when you add a shard because almost every key moves. A better pattern: hash into a large fixed number of slots (for example 64 or 1,024), then keep a small table mapping slots to shards. Adding a shard means reassigning some slots and copying only their data.

Costs of sharding: cross-shard joins and transactions are hard, secondary indexes may span shards, and a bad shard key (low cardinality or skewed) creates hot spots that no amount of hardware fixes.

Application
Shard routerhash(key) % 64 = slot, then slot table
Shard 1slots 0-15
Shard 2slots 16-31
Shard 3slots 32-47
Shard 4slots 48-63
The router is the only place that knows where data lives. The slot ranges here are one illustrative layout; the lesson's code deals slots out round-robin, which works the same way.
s1: 16
0
s2: 16
1
s3: 16
2
s4: 16
3
s5: 0
4
Four shards own 16 slots each. A new shard s5 is about to be added with no slots.
step 1 / 4

Each cell is a shard and the number of its 64 slots. Adding s5 takes 12 slots (64 divided by 5, rounded down) from the busiest shards, so only those slots' data is copied.

Consistency and CAP in plain terms

When a network partition splits your nodes, you must choose between two things. You can keep answering requests, risking stale or conflicting answers (availability). Or you can refuse some requests until the nodes agree, so every answer is correct (consistency). That is the CAP trade-off: during a partition you cannot have both. When there is no partition, the real trade-off is latency versus consistency.

  • Strong consistency: after a write completes, every read sees it. Easier to reason about; slower and less available.
  • Eventual consistency: replicas converge if writes stop, but reads may be stale for a while. Faster and more available.

Useful middle grounds: read-your-writes (you always see your own updates, for example by reading from the leader right after you write) and monotonic reads (you never see time go backwards).

SQL or NoSQL?

Choose from access patterns, not fashion.

  • Relational (SQL): structured data, joins, multi-row transactions, ad hoc queries. Scales vertically very far and with replication; sharding is possible but manual.
  • Key-value and wide-column stores: simple lookups by key at very large scale, built for partitioning, often eventual consistency, limited queries.
  • Document stores: nested, flexible-shape records fetched as a unit.

A frequent answer is both: SQL as the system of record for money-like data, plus a key-value store or cache for high-volume simple reads.

OperationTimeNotes
Read from a replicaScales with replicasMay be stale (replication lag)
Write (single leader)Bounded by one machineReplication does not add write capacity
Shard lookup (hash to slot to shard)O(1)Plus network hop
Cross-shard queryO(number of shards)Scatter-gather; avoid on the hot path

Code: a hash-based shard router

The router hashes a key into one of 64 slots and looks up the owner. Adding a shard steals slots from the busiest shards. We compare how many keys move against naive modulo hashing.

def h32(text):
    h = 2166136261
    for b in text.encode("utf-8"):
        h ^= b
        h = (h * 16777619) & 0xFFFFFFFF
    h ^= h >> 16
    h = (h * 0x85EBCA6B) & 0xFFFFFFFF
    h ^= h >> 13
    h = (h * 0xC2B2AE35) & 0xFFFFFFFF
    h ^= h >> 16
    return h
 
class ShardRouter:
    SLOTS = 64
 
    def __init__(self, shards):
        self.owner = [shards[i % len(shards)] for i in range(self.SLOTS)]
 
    def route(self, key):
        return self.owner[h32(key) % self.SLOTS]
 
    def add_shard(self, name):
        shards = sorted(set(self.owner))
        target = self.SLOTS // (len(shards) + 1)
        for _ in range(target):
            counts = {s: self.owner.count(s) for s in shards}
            donor = max(shards, key=lambda s: (counts[s], s))
            slot = max(i for i, s in enumerate(self.owner) if s == donor)
            self.owner[slot] = name
 
    def load(self, keys):
        out = {}
        for k in keys:
            s = self.route(k)
            out[s] = out.get(s, 0) + 1
        return dict(sorted(out.items()))
 
keys = [f"user:{i}" for i in range(1000)]
router = ShardRouter(["s1", "s2", "s3", "s4"])
before = {k: router.route(k) for k in keys}
print("load before:", router.load(keys))
 
router.add_shard("s5")
after = {k: router.route(k) for k in keys}
print("load after:", router.load(keys))
 
moved = sum(1 for k in keys if before[k] != after[k])
modulo_moved = sum(1 for k in keys if h32(k) % 4 != h32(k) % 5)
print("slot router moved:", moved)
print("modulo moved:", modulo_moved)

Both versions print:

load before: {'s1': 249, 's2': 249, 's3': 242, 's4': 260}
load after: {'s1': 195, 's2': 202, 's3': 200, 's4': 207, 's5': 196}
slot router moved: 196
modulo moved: 812

Only the keys in the reassigned slots moved, a small fraction of the data, whereas modulo hashing relocated most of it.

Slot router moved
196 of 1000 keys
Modulo moved
812 of 1000 keys
Keys relocated when a fifth shard joins, from the lesson's output. The slot router moves only the keys in the 12 reassigned slots; modulo hashing remaps most of them.

In production, those moved slots are copied in the background and the table is switched over when each slot is caught up.

Common pitfalls

  • Sharding too early. Indexes, caching, and read replicas take many systems a long way. Sharding permanently complicates queries and transactions.
  • Hot shards. A celebrity user or a timestamp key sends disproportionate traffic to one shard.
  • Reading stale replicas by accident. Reading your own write from a lagging follower makes data look lost. Route those reads to the leader or track lag.
  • Cross-shard transactions. They need coordination protocols and are slow and fragile. Design so the common operations stay inside one shard.
  • Modulo placement. It makes adding capacity a mass migration. Use slots or consistent hashing.
  • Assuming failover is free. Promotion can lose acknowledged writes under asynchronous replication, and split-brain (two leaders) must be prevented.

Practice

Replicas and write volume easy

Hint

Where do writes go in leader-follower replication?

Show solution

Adding followers increases read capacity but not write capacity: every write still goes to the leader and is replayed on every follower. If writes are the bottleneck you need sharding (or a different write path), not more replicas.

Choose a shard key for a messaging app medium

Hint

What is the most common query? Which key keeps it on one shard?

Show solution

The hot query is "fetch the messages in this conversation". Sharding by conversation id keeps a conversation on one shard and spreads load across many conversations. Sharding by sender would scatter a conversation across shards, and sharding by timestamp would make the newest shard the hot one.

Fix read-your-writes medium

Hint

After a write, where could the next read be served from?

Show solution

Options: read from the leader for a short window after a user writes; or have the client carry the write's position (a version or log offset) and read only from replicas that have caught up to it. The first is simpler; the second preserves replica read capacity.

Rebalance with fewer moved keys hard

Hint

Which fixed layer sits between key and machine?

Show solution

Use many more slots than shards. When a shard is added, reassign roughly an equal share of slots from existing shards to it and copy just those slots. Keys move only if their slot moves, so about 1/(n+1) of the data relocates instead of nearly everything. This is the same idea behind consistent hashing and fixed hash-slot designs.

Interview questions

  1. Replication versus sharding? Replication copies the same data for read scale and availability; sharding splits different data across machines for size and write scale.
  2. Explain CAP simply. In a network partition you either serve possibly stale data (available) or reject requests until agreement (consistent).
  3. What are the downsides of eventual consistency? Stale reads and conflicting writes that need resolution, so the application must tolerate or handle them.
  4. When would you pick NoSQL over SQL? When access is simple key-based lookups at a scale or shape that a single relational node cannot serve, and you can live without joins and multi-row transactions.
  5. How do you pick a shard key? High cardinality, even load, and alignment with the dominant query so most operations stay on one shard.

Interviewers look for: the distinction between read scaling and write scaling, explicit mention of consistency trade-offs, and a shard key justified by query patterns and skew.

Quick check

Your database is read-heavy and the leader's CPU is fine, but read latency is high. What is the most direct first step?

Finished this lesson?

Further resources

Related lessons