تقسیم (Sharding)Sharding

Five ideas this chapter revolves around:

• The mapping algorithm: from partition key to shard and from shard to node — and why hash % N is a disaster when N changes.
• Rebalancing: moving whole shards, splitting ranges, or consistent hashing — each with its own price.
• Skew and hotspots: even the best hash doesn't spread one hot key's real load.
• Request routing: how a client learns which node owns which key — and what happens during shard moves.
• Secondary indexes: a secondary index must be sharded too; local (document-partitioned) or global (term-partitioned).

A distributed database usually spreads data across nodes in two ways:

• Replication (Chapter 6): a copy of the same data on several nodes — for failure tolerance and more reads.
• Sharding: when data or writes exceed one node's capacity, data is broken into smaller shards and each shard goes to a different node.

Each record belongs to exactly one shard; in practice each shard is a small independent database (though some systems have multi-object operations). Sharding usually combines with replication: each shard has several copies, each shard's leader sits on one node and its followers on others — and each node can simultaneously lead some shards and follow others.

The big picture of “sharding + replication”: four nodes each leading one shard and following another, with the application sending writes to the leader and reads to any replica:

In SaaS products, each customer (tenant) has separate, self-contained data. Sometimes sharding serves exactly that: one shard per tenant, or several small tenants in one shard. Advantages:

• Resource isolation: one tenant's heavy operations don't ruin the rest's performance.
• Access isolation: an access-control bug doesn't leak another tenant's data (physically separate data).
• Cell-based architecture: one tenant group's services and storage gather in a self-contained “cell”; each cell's failure stays inside itself.
• Separate backup and recovery: restoring one tenant without touching the rest — e.g. after a mistaken data deletion.
• Legal compatibility: GDPR and CCPA grant “access and erase personal data” rights; when each person's data sits in its own shard, export and delete get simple.
• Data residence: if a tenant's data must stay in a given jurisdiction, pin its shard to that region.
• Gradual schema rollout: migrations don't run for everyone at once; you advance tenant by tenant and spot problems earlier.

Challenges: the “each tenant fits on one machine” assumption (a giant tenant must be sharded inside itself too), many small tenants (per-shard overhead and moving them as they grow), and harder features spanning several tenants' data.

The core question: with all this data, where do we put which record? The goal is spreading data and query load evenly across nodes. Unfair splitting is called skew: some shards hold more data or queries and sharding goes ineffective — extremely, all load lands on one shard while 9 of 10 nodes idle. Such a shard is a hot shard and an overloaded key a hot key (e.g. a celebrity's account on a social network).

The mapping algorithm's input must be the partition key and its output the shard; in a key-value store usually the key (or the key's first part), in the relational model one table column (not necessarily the primary key). The algorithm must also stay flexible for rebalancing — for escaping hotspots.

Here each shard holds a contiguous range of sorted keys — like volumes of a printed encyclopedia: volume 1 words A and B, volume 12 words T to Z. Boundaries needn't be evenly spaced, because data isn't uniform; boundaries must adapt to the data.

• Advantage: inside each shard keys are ordered (B-tree or SSTable — Chapter 4), so range scans are fast and a composite key works like a multi-column index.
• Example: sensor-network data keyed by timestamp — fetching a month of readings costs no effort.
• Risk: concentrated writes on nearby keys heat one shard. If the key is only a timestamp, all of “this month's” writes go to this month's shard while the rest idle.
• Common fix: prefixing the key with the sensor (or tenant) ID to spread load across shards — price: a multi-sensor time range needs several separate queries.
• Boundaries: manual (like Vitess) or automatic (Bigtable, HBase, range mode in MongoDB, CockroachDB, FoundationDB).
• Rebalancing: pre-splitting at the start (dangerous without knowing the key distribution), then split/merge like the top of a B-tree; HBase's common split threshold is ~10GB or writes persistently crossing a threshold.
• Split cost: all data must be rewritten into new files (like compaction) — and exactly the hot shard under pressure splits, raising its pressure further.

Now ask yourself which scheme fits your load; let's walk the decision step by step:

If key closeness doesn't matter to you (e.g. keys are tenant IDs), the most common move is first hashing the partition key. A good hash evens out skewed data: output looks random but identical input always gives identical output.

• The hash needn't be cryptographic: MongoDB uses MD5 and Cassandra/ScyllaDB use Murmur3.
• Programming-language hash functions may differ between processes (Object.hashCode() in Java, Object#hash in Ruby) and don't fit sharding.
• The hash(key) % N trap: seemingly simple, but when N changes nearly all keys move (going from 3 to 4 nodes, most keys switch nodes). Good rebalancing moves the least data, so mod N is rejected.
• Fixed shard count: e.g. 1000 shards from the start, 100 on each of 10 nodes; a key goes to shard hash(key) % 1000 and only the “shard-to-node map” changes. When a node joins, a few whole shards move — cheaper than splitting. Pick the shard count with many divisors and give stronger nodes more shards (Citus, Riak, Elasticsearch, Couchbase).
• Fixed-count price: if the shard count comes out small and more nodes are needed, expensive resharding is required (splitting each shard and rewriting files; some systems forbid it during writes).
• Hash ranges: key-range combined with hashing — each shard holds a range of hash values (e.g. 0–16383 for shard zero). Nearby keys (consecutive timestamps) scatter and big shards split like key-range; only range queries on the partition key itself get expensive. The composite-key trick (partition key in the first column, order from the rest) still preserves in-shard range reads. This scheme lives in YugabyteDB and DynamoDB and is one MongoDB option.

See the full “key to node” path and its two main branches at a glance:

Cassandra and ScyllaDB split the hash-value range (e.g. 0–1024) into contiguous ranges with random boundaries and give each node several ranges (default: 16 ranges per node in Cassandra, 256 in ScyllaDB). Some ranges are bigger but several ranges per node compensate the inequalities. When a node joins, boundaries shift and parts of ranges move — with no more transfer than needed.

Consistent hashing is a mapping algorithm with two properties: (1) each shard holds roughly as many keys, (2) when the shard count changes, the fewest keys move. Note “consistent” here has nothing to do with replica consistency (Chapter 6) or ACID (Chapter 8); it means “a key's tendency to stay in its place”. Other families: rendezvous (highest random weight) and jump consistent hashing, which hand scattered keys to the fresh node instead of splitting ranges.

Consistent hashing spreads keys evenly, but that doesn't guarantee real load is even. If query load concentrates on some keys (a celebrity's post with millions of followers causing an activity storm), nodes still break under load while the rest idle.

• Isolating the hot key: in range-based schemes (key or hash), the hot key can sit alone in one shard and even get a dedicated machine.
• Random prefix: adding two random digits to the key's start or end spreads one key's writes across 100 keys. Price: reads must fetch all 100 keys and merge; only writes spread, not reads. You must also know which keys turned “hot” and own a process for converting a plain key into a managed one.
• Changing over time: a viral post is hot for days then calms; some keys are write-hot and some read-hot — each needs a different strategy.
• Cloud systems: automatic “heat management” or “adaptive capacity” fixes (like DynamoDB) move load around; their details are outside the book.

Whenever a node joins or leaves, or data grows unbalanced, data must be respread (rebalancing). Three approaches exist:

Now shards have found their places. Next question: to read or write a given key, which node — which IP and port — do you connect to? That job is request routing, very like service discovery (the “load balancers and service meshes” section in Chapter 5). The big difference: application services are usually stateless and any instance can answer any request; but a key's request must only go to a node holding a replica of that key's owning shard.

Three famous approaches: (1) a request reaches any node and that node forwards it, (2) a routing tier that executes no requests itself and is only a shard-aware load balancer, (3) a shard-aware client connecting straight to the right node. The diagram below shows the second approach with ZooKeeper coordination and a transient shard-move node:

• Who decides? The simplest case is one coordinator; but what if that node fails? And if the role fails over, how is split brain (two coordinators with conflicting decisions) prevented?
• Who learns of changes? The routing tier or client must be told of shard-ownership changes.
• In-flight requests at cutover: the fresh owner has taken over, but requests still reach the old owner.

Many systems keep a separate coordination service like ZooKeeper or etcd: each node registers itself, the authoritative shard→node map lives there, and the routing tier or shard-aware client subscribe to it. Every ownership change notifies them. These services are shielded against failure and split brain by a consensus algorithm (Chapter 10).

Server IP addresses change more slowly, so DNS usually suffices for finding the nodes themselves. And a last note: this discussion was about finding one key's shard (fit for OLTP); in analytical databases one query usually must gather and join many shards' data in parallel — a different problem arriving in Chapter 11.

Moving one shard from node A to node B is no “single-step command”; it is a state machine. Data must be copied, writes arriving mid-copy must be followed, and ownership flips at only one defined instant. If we name each moment of that path a “state” and make transitions explicit, we understand what failure at each stage means and what the system must decide then — instead of picturing the move as one vague, irreversible process.

The most sensitive moment is the cutover window: that short span when the shard map switches while requests still fly to the old owner. In that window there are two customer kinds: those whose requests still reach the old node (and must be forwarded or rejected) and those who cached the old map and never heard the owner changed — whose writes may land in the wrong place.

And this cycle's reassuring note: if the move fails midway, no data is lost. Until the shard map updates, the owner is still A, and the incomplete copy on B is just extra data to discard. The diagram below shows that cycle UML-style — with the main path, the fall path and the stranded-writes path:

All the schemes above assume the client knows the record's partition key (in a key-value store, the primary key). But a secondary index doesn't identify a record; it is a search path: “all of user 123's actions”, “all articles containing hogwash”, “all red cars”. The problem: a secondary index doesn't stick to shards — two fixes: local and global.

Comparing the two write and read paths — from record registration to query answer:

Local secondary index (in information retrieval: document-partitioned): each shard indexes only its own records. Writing (add, delete, update) engages only that record's shard. The used-car-sale example with the ad's unique ID as partition key: adding one red car, its own shard appends the ID to the color:red postings list.

• If you know the partition key, the search runs in that same shard; if you want only “a few results”, any shard suffices.
• If you want all results without knowing the partition key, the query must go to all shards and answers merge (red cars may sit in both shard zero and one).
• Scatter reads amplify tail latency and bound scalability: more shards mean more space, not more query throughput.
• Still very common: MongoDB, Riak, Cassandra, Elasticsearch, SolrCloud and VoltDB.
• Risk: if you build a value→ID index yourself in application code, race conditions and partial writes detach the index from the data; hence the need for multi-object transactions (Chapter 8).

Global secondary index (or term-partitioned): the index spans all shards and is sharded separately itself — e.g. colors a–r in one shard and s–z in another. Because a “term” (each searchable value) is the partition key, you know which shard to read.

• A single-condition query (color = red) reads the postings list from one shard; but fetching the records themselves still spans shards.
• Multi-condition queries (color + brand) likely land on different shards; AND means intersecting two postings lists — slow for long lists.
• Writing is more complex: one record may update several index shards (each term may own its shard), needing distributed transactions.
• CockroachDB, TiDB and YugabyteDB have global indexes; DynamoDB updates its own asynchronously, so reading it may be stale.

• Conflating sharding with network partitions — only their names match.
• Saying “sharding means splitting data” and forgetting the real goal: evenly spreading data and load and avoiding hotspots.
• Recommending sharding for any system; if one machine suffices, sharding is just extra complexity.
• Recommending hash(key) % N as the fix — blind to most keys moving when N changes.
• Forgetting that in key-range sharding, a bare timestamp key heats “this month's” shard.
• Saying “hashing evens everything” while missing that one hot (celebrity) key's load still stays on one shard.
• Saying “a random prefix fixes hotspots” without explaining that only writes spread while reads must merge 100 keys.
• Conflating “consistent hashing” with consistency; here consistent means “a key stays in its place”.
• Forgetting split cost: rewriting all data, exactly on the shard under pressure.
• In rebalancing, missing the dangerous “automatic + automatic failure detection” mix and cascading-failure risk.
• In routing, only saying “we use a load balancer” and missing the three hard questions: who decides, who learns of changes, and cutover in-flight requests.
• Forgetting that a secondary index must itself be sharded, and that scatter-gather amplifies tail latency.
• Saying “a global index makes reads free”; the postings list is one shard but fetching records and multi-term intersection stay expensive.
• Recommending hand-rolled indexes in application code with no multi-object transaction (index-data inconsistency risk).
• Saying “a shard is one machine”; a shard is a logical data unit and several shards can sit on one machine (even several processes on one CPU).

1. Define shard and its difference from replication and network partitions — in one sentence.
2. Two main families (key-range vs hash) + one advantage and one price each.
3. Define the mod-N trap with a numeric example (3 → 4 nodes) and name its three alternatives.
4. Four rebalancing styles and the danger of mixing automatic rebalancing with automatic failure detection.
5. Define hotspot and its three fixes (dedicated shard, random prefix, heat management) + each one's price.
6. Three request-routing styles and the three hard questions (coordinator, change notification, cutover).
7. Local vs global secondary index: each one's write and read paths + each one's price.
8. One sentence on multitenancy and why “one shard per tenant” is both attractive and limited.