Week 5: Scaling the Data Layer: Replication & Sharding

1. Leader-Follower Replication & Read Replicas

Replication means keeping copies of the same data on multiple machines. The most common setup is leader-follower (also called primary-replica or master-slave): one node, the leader, accepts all writes; one or more follower nodes continuously replicate the leader's data and can serve reads. This does nothing for write capacity — every write still goes through the leader — but it does two things a single instance can't: it scales read throughput horizontally by spreading read queries across followers, and it improves durability and availability, since a follower can be promoted to leader if the original leader fails.

leader-follower topology

                 writes
[App Servers] ---------> [Leader DB]
     |                        |
     | reads (~90% of load)   | replication stream
     v                        v
[Follower DB 1]  [Follower DB 2]  [Follower DB 3]
     ^                ^                ^
     +--- read queries routed here by the app layer ---+

Replication can be synchronous or asynchronous, and the choice is a direct latency-vs-durability tradeoff. With synchronous replication, the leader waits for at least one follower to confirm it has the write before acknowledging the client — a follower is always guaranteed up to date, but every write now pays the network round trip to that follower, and if the follower is slow or down, writes stall. With asynchronous replication, the leader acknowledges the write immediately and streams it to followers in the background — writes stay fast, but followers lag behind by some amount of time, and a leader crash before a write replicates means that write can be lost.

That lag is the reason read replicas aren't a free lunch: a client that writes data and then immediately reads it back from a follower can see stale data if the write hasn't replicated yet — the classic read-your-own-writes problem. Common mitigations are routing a user's own reads to the leader for a short window after they write, or using "read-after-write" session stickiness to a specific replica. This is a small, concrete preview of the strong-vs-eventual consistency tradeoff Week 9 covers formally — asynchronous replication is, in effect, choosing eventual consistency for your read replicas in exchange for write latency and availability.

Replicas scale reads, not writes

A candidate who says "let's add read replicas" to solve a write-throughput problem has misdiagnosed the bottleneck — every write still funnels through one leader. If writes themselves are the bottleneck, replication alone doesn't help; you need sharding (Section 2) to split the write load across multiple leaders, each owning a different slice of the data.

2. Sharding & Partitioning Strategies

Sharding (or horizontal partitioning) splits a dataset across multiple independent database instances — called shards — where each shard holds a disjoint subset of the rows. Unlike replication, sharding scales both reads and writes, because there are now multiple leaders, each responsible for its own slice of data and its own write traffic. The tradeoff is complexity: queries that need data from multiple shards (a "scatter-gather" query, or a cross-shard join) become slower and harder to express, and the application now needs a way to route each request to the correct shard.

There are three common strategies for deciding which rows go to which shard:

three sharding strategies

Range-based:
  Shard 1: user_id 1        - 1,000,000
  Shard 2: user_id 1,000,001 - 2,000,000
  Shard 3: user_id 2,000,001 - 3,000,000
  + Simple to implement; range queries stay on one shard
  - New users all land on the newest (last) shard -> hot spot

Hash-based:
  shard_index = hash(user_id) % num_shards
  + Spreads writes evenly across shards, no hot "newest" shard
  - Range queries ("all users created this week") now scatter
    across every shard
  - Changing num_shards reshuffles almost all keys (Section 4)

Directory-based:
  A lookup service maps each key -> specific shard:
    user_id 88214 -> Shard 7   (stored in a directory table)
  + Full flexibility: rebalance individual keys without a
    formula change, support variable-size shards
  - The directory is an extra hop and a new single point of
    failure/bottleneck unless it's itself replicated and cached

Hash-based sharding is the default answer in most interviews because it avoids the hot-newest-shard problem that plain range-based sharding creates — but a naive hash(key) % num_shards has its own failure mode: adding or removing a single shard changes the modulus, which reassigns almost every key to a different shard. Section 4 covers consistent hashing, the fix you saw introduced conceptually as a load-balancing algorithm in Week 3 and that reappears here for exactly the same reason — minimizing how much data moves when the number of nodes changes.

Sharding is a last resort, not a first move

Sharding adds real operational complexity: cross-shard transactions are hard or impossible, cross-shard queries need application-level fan-out, and every migration is a project. Reach for vertical scaling, indexing (Week 4), read replicas and caching (Weeks 6–7) first — shard only when write throughput or data volume on a single leader genuinely can't be solved any other way.

3. Choosing a Shard Key

The shard key (or partition key) is the field used to decide which shard a row lives on, and it is close to the most consequential decision in a sharded system's design — changing it later means migrating the entire dataset. A good shard key needs three properties: high cardinality (many distinct values, so there's enough granularity to spread load), an even distribution of both data volume and — critically — access frequency across values, and alignment with the application's most common query pattern, so that most queries can be answered by hitting a single shard.

shard key choice — a social app's posts table

Option A: shard by post_id
  - "Get all posts by user X" now scatters across every shard
    (that user's posts are spread randomly by post_id hash)
  - Most-common query pattern (view a user's profile/posts)
    becomes a slow scatter-gather on every single shard

Option B: shard by user_id
  + "Get all posts by user X" hits exactly one shard -- matches
    the dominant query pattern
  - A celebrity account with 50M followers concentrates huge
    read AND write volume onto one shard -- a hot key/hot
    partition, the same failure mode named conceptually in
    Week 3's discussion of scalability failure modes

Option B is usually the right call for this access pattern — it's a genuine tradeoff, not a free win, and interviewers want to hear you name the hot-key risk explicitly rather than pretend the "good" shard key has no downside. Real systems mitigate a hot key with techniques like splitting an unusually hot user's data across multiple sub-shards, adding a caching layer in front of the shard (Weeks 6–7) so the shard itself sees far less direct read traffic, or salting the key for write-heavy hot partitions to spread writes artificially.

Ask "what's the most common query?" before picking a key

The shard key decision should be driven by the read/write access pattern, not by which field looks most like a natural identifier. Walk through the two or three queries the system runs most often and check each candidate key against them before committing — this is the same discipline as Week 1's estimation step, applied to a schema decision instead of a capacity number.

4. The Operational Cost of Resharding

Resharding — changing the number of shards, or moving data because a shard grew too hot or too large — is one of the most expensive operations in a distributed system's lifecycle. With naive hash(key) % N sharding, changing N from 4 to 5 remaps roughly 80% of all keys to a different shard, meaning the vast majority of rows need to be physically copied to a new machine while the system stays online and serving traffic.

why consistent hashing limits the blast radius

Naive hashing, N: 4 -> 5
  key 101: hash % 4 = 1   ->   hash % 5 = 1   (same, lucky)
  key 102: hash % 4 = 2   ->   hash % 5 = 2   (same, lucky)
  key 103: hash % 4 = 3   ->   hash % 5 = 3   (same, lucky)
  key 104: hash % 4 = 0   ->   hash % 5 = 4   (MOVED)
  ...in general, ~(N-1)/N of all keys move on almost any change

Consistent hashing: shards are placed as points on a hash
ring; a key belongs to the next shard clockwise from its own
hash position. Adding a 5th shard only steals the keys that
fall between it and its clockwise neighbor -- roughly 1/N of
the keyspace moves, not the whole dataset.

Beyond the hashing scheme, teams use two practical techniques to keep resharding tractable. First, over-provisioning logical shards: split the keyspace into far more logical partitions than physical machines up front (say, 4,096 logical shards mapped onto 8 physical database nodes), so that scaling out later means moving whole logical shards to new machines — a bookkeeping change — rather than rehashing the entire keyspace. Second, online migration with dual writes: during a migration, writes go to both the old and new shard locations while a background job backfills historical data, and reads gradually cut over once the new location is verified caught up — avoiding a hard downtime cutover.

This is also why the shard key decision in Section 3 matters so much: a bad shard key doesn't just cause a hot partition, it guarantees an expensive resharding project down the line to fix. The cost of resharding is the single strongest argument for spending real time on the shard key choice before the system launches, rather than treating it as a detail to revisit later.

Naming consistent hashing earns real credit

When an interviewer pushes on "what happens when you need to add a shard?", naming consistent hashing specifically — and explaining that it moves roughly 1/N of the keys instead of nearly all of them — is a strong, concrete answer that shows you understand the operational cost, not just the initial design.

5. Hands-on Exercise

Hands-on

Design the data layer for a photo-sharing app

The app has 50M users, is read-heavy (photo views vastly outnumber uploads), and its two most common queries are "get this user's photos" and "get this photo's metadata by photo ID."

Requirements:

Design a replication topology: how many read replicas would you start with, would you use synchronous or asynchronous replication, and what specific risk does your choice introduce? Justify each in one sentence.
Choose a shard key for the photos table from these candidates — photo_id, user_id, upload_date — and justify your choice against the app's two most common queries.
Name the specific hot-key risk your chosen shard key introduces, and describe one mitigation for it.
Assuming 500M total photos and a target of no more than ~50M photos per shard, calculate the minimum number of shards needed.
Write 2–3 sentences describing how you'd migrate from your Step 4 shard count to double that count without taking the system offline.

Hint

Step 2 has a trap: photo_id looks like the "natural" key for a photos table, but check it against "get this user's photos" specifically before choosing it. Whichever key you pick, Step 3 should name a real, specific risk — not a generic "some shards might be uneven" statement.

6. Knowledge Check

Four quick questions. Expand each to check your answer.

Why doesn't adding read replicas help a system that's bottlenecked on write throughput?

In leader-follower replication, every write still has to go through the single leader — followers only replicate data and serve reads. Adding more followers increases how much read traffic the system can absorb but does nothing to increase the leader's write capacity. A write-throughput bottleneck needs sharding, which introduces multiple independent leaders each owning a slice of the data, not more replicas of the same single leader.

What's the main tradeoff between range-based and hash-based sharding?

Range-based sharding keeps range queries fast because contiguous key ranges live on one shard, but it tends to create a hot spot — new sequential keys (like newly created user IDs) all land on the most recent shard. Hash-based sharding spreads writes evenly across all shards by hashing the key, eliminating that hot spot, but it destroys locality: a range query like "all users created this week" now has to scatter across every shard and merge results.

What three properties should you evaluate a candidate shard key against, and why does query pattern matter as much as data distribution?

A good shard key needs high cardinality, even distribution of data and access load, and alignment with the system's most common query pattern. Cardinality and distribution alone can produce a key that's perfectly balanced but still forces every common query to scatter across all shards and merge results — which is slow and defeats much of the point of sharding. Matching the query pattern is what keeps the majority of real queries confined to a single shard.

Why does naive `hash(key) % N` sharding make resharding so expensive, and how does consistent hashing fix it?

Because the modulus N is baked directly into every key's shard assignment, changing N — adding or removing even a single shard — reassigns roughly (N-1)/N of all keys to a different shard, requiring almost the entire dataset to be copied while the system stays live. Consistent hashing places shards as points on a hash ring and assigns each key to the next shard clockwise, so adding a shard only reassigns the keys that fall in the small arc it now owns — roughly 1/N of the keyspace instead of nearly all of it.