Data Sharding Techniques

A sharding technique is nothing more than a function shard = f(key) that maps every row to one of N partitions; the shape of that function is what decides your three real costs — how much data must move when you add or remove a node (resharding cost), how evenly load spreads (hotspot risk), and whether a query hits one shard or all of them (fan-out). The six techniques below are just different choices of f, and the whole engineering skill is matching that choice to your access pattern.

• Range — f preserves order, so shards own contiguous key intervals.
• Hash — f scrambles the key so neighbours scatter (naive hash-mod vs. consistent hashing — the critical distinction most notes get wrong).
• Directory — f is an explicit lookup table you control.
• Geographic — f keys on location for residency/latency.
• Dynamic — f is a range map that auto-splits under load.
• Hybrid — f is layered (e.g. geo on top, hash inside).

1. Range-based sharding

Mechanism: the key space is cut into contiguous intervals and each shard owns one interval, so rows that are near each other by key stay physically together — which is exactly what makes ordered scans cheap and range queries hit a single shard.

Worked example. An e-commerce table sharded on order_date:

Query “all orders in May 2026” touches only S2 — no scatter, no merge step. That locality is the entire appeal. The flip side: because order_date only ever increases, every new write lands on the newest shard, so S3 (and whatever succeeds it) is a permanent write hotspot while S1–S2 sit idle. Range sharding rewards range queries and punishes monotonic keys.

2a. Hash-based sharding — the naive version (hash-mod)

Mechanism: compute a hash of the key and take it modulo the shard count — shard = hash(key) % N — so keys are sprayed uniformly and a single-key lookup is O(1) with no directory. The uniformity is real; the trap is the literal N sitting inside the formula.

Worked trace. Eight user IDs, N = 4 shards. (Take hash(id) = id to keep the arithmetic visible.)

Adding one shard relocated 5 of 8 keys. This is not bad luck: when the divisor changes from N to N+1, the residue of almost every key changes, so in the general case roughly 1 − 1/(N+1) (~80% for 4→5, rising as N grows) of all rows in the cluster must be re-hashed and physically copied to a different machine.

Why the naive version is wrong: hash-mod bakes the cluster size N into the placement function, so the day you grow the cluster you trigger a near-total data migration while still serving live traffic. Uniform distribution was never the problem — elasticity is. This is the exact pain that motivates consistent hashing, and it is why you should almost never use raw % N in a system expected to scale.

2b. Consistent hashing — the fix

Mechanism: hash both the keys and the nodes onto the same fixed ring (say 0…2³²), and a key belongs to the first node found walking clockwise; because node placement no longer depends on the count of nodes, adding or removing one only reassigns the keys in that node's arc — everyone else stays put.

Worked example. Shrink the ring to 0…999 for legibility. Nodes land at A=100, B=400, C=750. Each key goes to the next node clockwise:

Now add node D at position 500. D only captures keys in the arc (400, 500] — its slice of what used to be C's range. So only k4 (pos 450) moves, from C to D; k1, k2, k3, k5 never budge. One key moved instead of five. In general, adding one node to N moves about K/N keys out of K — the minimum possible.

Virtual nodes (why real systems need them): with only a handful of physical nodes, three random ring positions produce lumpy arcs — one node ends up owning a huge slice. Worse, if a node dies, its entire load dumps onto its single clockwise successor. The fix is to place each physical node at many pseudo-random points (Dynamo/Cassandra use dozens to hundreds of vnodes): arcs even out statistically, and a departing node's load is redistributed across many successors instead of crushing one. This is the difference between the textbook idea and a production-grade ring.

3. Directory-based sharding

Mechanism: instead of computing placement, you store it — a lookup service maps each key (or bucket of keys) to a shard, so placement becomes an editable table rather than an arithmetic rule. That indirection buys total freedom: move a single bucket, put a whale tenant on dedicated hardware, or rebalance without any global recompute.

Example. A gaming platform keeps a directory username → shard. A read first hits the directory, then the shard. Onboarding a huge guild? Point just their buckets at a fresh shard and copy only those rows — no rehash of anyone else. The cost: every request pays an extra hop, the directory is a potential SPOF and throughput bottleneck (mitigated by caching + replication), and a stale cached directory entry silently routes reads to the wrong shard. You are trading arithmetic for a table you now have to keep correct and highly available.

4–6. Geographic, dynamic, and hybrid

Geographic: f keys on region, so a user's rows live in a data center near them. Mechanism-wise this is directory or range sharding with location as the key. It cuts latency and satisfies data-residency law (GDPR: EU users' data stays in the EU). Cost: any query that spans regions becomes a cross-region scatter, and a user who moves country needs a data migration.

Dynamic: f is a range map the system rewrites itself — a shard that grows past a threshold or gets hot is split in two, and cold neighbours are merged. This is how HBase region splits and DynamoDB partition splits work in production: no human picks boundaries. Cost: rebalancing consumes I/O, and a sudden write burst can trigger a split storm at the worst moment.

Hybrid: layer the functions — e.g. geo-shard to a region first, then consistent-hash within it. Real large systems are almost always hybrids because no single f satisfies residency, elasticity, and locality at once. It is powerful but multiplies operational surface: two routing layers to reason about, monitor, and debug.

Pitfalls

• Monotonic key + range sharding = write hotspot. Timestamps or auto-increment IDs send every insert to the last shard. Salt the key or switch to hash for the write path.
• A single hot key defeats every hashing scheme. Hashing spreads distinct keys; it cannot spread one celebrity user's key across shards. That needs key-splitting (append a bucket suffix) or read replicas — no f alone fixes it.
• Raw hash-mod on an elastic cluster. As traced above, growing the cluster copies ~80% of rows. Use consistent hashing (with vnodes) or a directory instead.
• Consistent hashing without virtual nodes. Few nodes → lumpy arcs and skewed load; a node's death dumps its entire load on one successor. Vnodes are not optional at scale.
• Cross-shard joins and transactions. Once data is split, a join or multi-row transaction fans out to many shards and loses single-node ACID guarantees — you inherit scatter-gather and distributed-transaction complexity.
• Directory drift / SPOF. A stale or unavailable directory misroutes or halts reads. Cache with invalidation and replicate it.
• Picking an unchangeable shard key. The shard key is welded into every query plan; choosing wrong forces a full re-shard later. Decide the key before the technique.

Selection & trade-offs — how a senior engineer decides

Start from the access pattern, not the technique. The two questions that settle most of it: do my hot queries scan ranges of the key, or look up single keys? and will the cluster grow/shrink often? Range and consistent hashing sit at opposite ends of that first axis.

Crisp rules of thumb: choose range when your money queries are scans over the key and you can avoid a monotonic key; prefer consistent hashing the moment membership is elastic and access is point lookups — you gain near-free rebalancing but you forfeit ordered scans. Choose a directory when you need to place data by hand (tenants, whales, compliance) and can pay for a highly-available lookup layer; prefer a computed function otherwise to dodge the extra hop and SPOF. Reach for dynamic when load is unpredictable and you'd rather the system rebalance than you; reach for hybrid only when one axis genuinely can't satisfy all constraints, and accept the doubled operational surface.

Takeaways

• A sharding technique is a choice of shard = f(key); that choice, plus the shard key, is welded into every future query — decide it deliberately and early.
• Hash-mod's fatal flaw is the literal N in the formula: change the node count and ~80% of rows move. Consistent hashing removes N from placement, so only ~K/N keys relocate — and virtual nodes are what make it even and fault-tolerant in practice.
• Range vs. consistent hashing is the core trade: ordered locality (great scans, hotspot risk) versus scattered uniformity (elastic, no scans). You cannot have both from one function.
• No hashing scheme rescues a single genuinely hot key or a cross-shard join — those are separate problems (key-splitting, replication, scatter-gather).

Re-authored and deepened for this guide. Sources: Martin Kleppmann, Designing Data-Intensive Applications, ch. 6 (Partitioning); DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007); Karger et al., Consistent Hashing and Random Trees (STOC 1997); Apache Cassandra and Apache HBase official documentation on virtual nodes and region splitting.