4.1 Sharding and Replication: Where Is the Data Stored?

Distributed storage first addresses two core concerns: using sharding to scale capacity and throughput, and using replication to withstand node or failure domain outages. Sharding determines who is responsible for a given piece of data, while replication determines where else that data must be stored.

Why Modular Sharding Is Hard to Scale

shard = hash(key) mod N

Changing N remaps many keys. For hash values 0–11, expanding from 3 shards to 4 leaves only 0, 1, and 2 on the same numbered shard: 9 of 12 values move. Every router must also use the same hash algorithm, input encoding, and seed, avoiding language built-in hashes randomized per process. During migration, old and new locations coexist, so routing, catch-up, throttling, and recovery require coordination.

A fixed number of logical shards can reduce the impact of node changes: first map keys to many logical shards, then assign those logical shards to physical nodes. When scaling out, only move a subset of logical shards, rather than altering the entire hash function.

The Trade-off Between Hash and Range

Shard Strategy	Advantages	Disadvantages
Hash	Distribution is typically even; point lookups are direct and efficient	Range queries span shards, leading to poor locality
Range	Range scans and locality of adjacent data are excellent	Hotspots, shard splitting, and metadata management become more complex
Composite Strategy	Can balance tenant and time-based dimensions	Routing and capacity models become harder to design and manage

The distribution of business keys matters more than the algorithm name. A single super-tenant, monotonically increasing time-based keys, or a small number of popular objects can create hotspots, even if the overall byte distribution appears uniform.

Consistent Hashing and Rendezvous Hashing

Consistent hashing maps nodes and keys onto a ring, where each key is assigned to the next clockwise node. Adding or removing nodes moves the ranges adjacent to affected tokens. With several tokens per physical node, those ranges can be scattered around the ring. Virtual nodes allow a single physical node to own multiple tokens, improving load balancing and enabling capacity-based distribution.

Rendezvous hashing computes a score for each (key, node) and selects the node with the highest score; selecting the top k distinct physical nodes yields candidate replicas, which must then satisfy failure-domain constraints. It needs no explicit ring. If the score function and existing node identities stay fixed, adding a node moves only keys it wins, and removing a node moves only keys it owned. The straightforward implementation scores every node per lookup, which has a routing cost at large membership sizes.

Neither approach automatically resolves:

• Nodes with differing capacities;
• Rack/zone failure correlation;
• Hot keys;
• Bandwidth and tail latency during data migration;
• Routing divergence caused by inconsistent node lists.

Replicas Must Span Failure Domains

Three replicas on one rack do not survive that rack losing power. Replica placement strategies must account for host, rack, zone, and region:

partition P
  ├─ replica 1: zone-a / rack-1
  ├─ replica 2: zone-b / rack-2
  └─ replica 3: zone-c / rack-3

Synchronous acknowledgments across regions add the relevant network round trips to write latency. Write availability during a partition depends on acknowledgment thresholds and replica placement. Asynchronous replication reduces foreground waiting but may lose updates not yet delivered when disaster strikes. RPO (Recovery Point Objective) describes acceptable data loss, often measured as time; RTO (Recovery Time Objective) describes acceptable time to restore service. Design both together with failure domains.

Rebalancing is an online protocol

A safe migration typically follows these steps:

1. New nodes join the cluster but initially do not handle read traffic;
2. Snapshots are copied from existing replicas;
3. Capture changes from the position corresponding to the snapshot and catch up continuously, with no gap between snapshot and change log;
4. Compare checksums, row counts, and business invariants at the same logical position;
5. Switch replica ownership using versioned routing. Old owners reject or forward writes using stale routes, preventing independent acknowledgments on both sides;
6. Retain old replicas for a rollback window, then remove them. A rollback must also catch up writes made after cutover; an old replica being present does not make it current.

The migration must be rate-limited, with recovery traffic, user traffic, and background compaction all modeled within the same capacity budget. Otherwise, scaling may overwhelm the cluster.

Hotspots Can't Be Solved Just by Adding Nodes

Hotspot sources include:

• Extremely high request volume for a single key;
• A low cardinality of partition keys;
• Concentrated time ranges falling on a single shard;
• Large partitions causing overly heavy compaction and recovery operations;
• Queries fan-out to all shards.

These should be addressed through key splitting, time bucketing, caching, request merging, localized replication, or business-level rate limiting. Key splitting introduces costs related to aggregation and consistency, so read-write semantics must be clearly defined before implementation.

Design Acceptance

• Does the shard key align with the primary query patterns?
• What are the maximum shard size and request rate limits?
• Are replicas distributed across different failure domains?
• Who owns the routing version during node addition or removal?
• How does migration catch up and verify incremental changes?
• How is a hot key identified and mitigated?

The next lesson uses leaderless replication and Cassandra to explore quorum intersection, conflict resolution, and replica repair.

References

• Karger et al., Consistent Hashing and Random Trees
• Thaler, Ravishankar, Using Name-Based Mappings to Increase Hit Rates