When there is more data or load than one node can handle, you cut it into partitions (a.k.a. shards): each record lives in exactly one partition, and partitions are spread across nodes. We cover the practice of sharding on MongoDB — replica set, shard key, chunks, balancer. This article is one floor up: how to choose the split, what happens to secondary indexes, how to move data when nodes are added, and how a client even finds the right partition. All these questions are the same for MongoDB, Cassandra, Elasticsearch, and HBase — only the names change.
The goal is evenness, the enemy is a hot spot
The point of partitioning is one thing: spread data and load across nodes evenly. Ten nodes should handle ten times a single one. If the split is uneven — some partitions carry a disproportionate share of data or requests — it is called skewed, and the overloaded partition is a hot spot. In the extreme, all load lands on one node while nine idle. The two basic ways to assign a record to a partition — by key range and by key hash — are essentially two different answers to the question of how to avoid a hot spot.
Range vs hash
By key range (range partitioning): each partition gets a contiguous stretch of keys, like the volumes of a paper encyclopedia (A–C, D–F, …). The boundaries are tuned to the data, because distribution is uneven (there are more words on "A" than on "Q"). The upside is range queries: keys within a partition sit sorted, and "all events in March" is one scan. The downside is that the same ordering easily breeds a hot spot: if the key starts with a timestamp, all of today's writes fall into one partition while yesterday's nodes idle. The cure is a compound key where time is not the first element (sensor name first, then time).
By key hash (hash partitioning): a good hash function turns even similar keys into evenly scattered numbers, and a partition owns a range of hashes. Evenness is nearly free — that is what Cassandra and MongoDB do (MD5 on the input). The price is losing the sort order: keys that are neighbours in meaning fly apart across all partitions, and a range query is forced to poll every node. Cassandra strikes a compromise with a compound key: only the first part is hashed (it picks the partition), the rest act as a sorted index within the partition — "all of one user's messages over a period" reads efficiently, while users are spread evenly.
A separate trouble that neither hash nor range fixes is a hot key: a celebrity with millions of followers whose entire traffic hits one record (the hash of two identical keys is identical). Only the application helps here: append a random suffix from a hundred variants to the key — the record smears across a hundred partitions, but a read must now gather and merge all hundred. Apply the trick to a handful of known-hot keys, not to all of them.
Secondary indexes: local vs global
As long as access goes by primary key, it is simple — route by it. But an application needs secondary indexes: "find all red cars", "all articles containing the word hogwash". A secondary index does not line up with the partitioning, and there are two ways to slice it — with diametrically opposite costs.
By document (local index). Each partition maintains a secondary index over only its own documents: add a red car to partition 3 and the color:red entry appears in partition 3's index. Writes are cheap: everything is local, one partition is touched. But reads are scatter/gather: red cars are scattered across all partitions, so "find red ones" must be sent to every node and the answers merged. This is how MongoDB, Cassandra, and Elasticsearch work. Fragmented reads amplify tail latency (you wait for the slowest node), but writes stay local — which is why it is the default.
By term (global index). One index for the whole cluster, but it too is partitioned — by the searched term: all of color:red sits in one index partition. Reads are fast — you go to one partition instead of all. The cost tips over on writes: adding a single document with several fields touches several index partitions at once (the color and make terms live in different places), and keeping that in sync is a distributed transaction. So global indexes are updated asynchronously: after a write the change shows up in the index with a lag (this is how DynamoDB works — "usually a fraction of a second, longer during failures").
The choice is exactly as everywhere: a local index is cheap writes, expensive reads; a global one is the reverse. Most systems default to local.
Rebalancing: how to move partitions
Over time nodes are added (load grew) and removed (a failure). Moving partitions from node to node is called rebalancing, and three things are expected of it: afterwards the load is even again; during it the database keeps reading and writing; no more data is moved than necessary.
- How not to do it —
hash mod N. Tempting: partition =hash(key) % N. But when the number of nodes N changes, almost all keys change partition — 10→11 nodes reshuffles nearly everything. Rebalancing becomes unbearable. - A fixed number of partitions. Create many more partitions than nodes (1000 partitions for 10 nodes) and hand out many per node. A new node "borrows" several partitions from existing ones — whole partitions move, their count and the key-to-partition mapping stay put, only the layout across nodes changes. This is what Elasticsearch, Riak, and Couchbase do. The rake is guessing the partition count up front: it is the ceiling of growth, and too many carry overhead.
- Dynamic partitioning. A partition outgrew a threshold — it splits in two; shrank — it merges with a neighbour (like a B-tree node). The partition count adapts to data volume. This is how HBase, MongoDB (chunks), and RethinkDB work. The empty-database rake is one partition at the start, all writes to one node until the first split (cured by pre-splitting, if the distribution is known).
And a separate question — automatic vs manual. Fully automatic rebalancing is convenient but dangerous paired with automatic failure detection: an overloaded node answers slowly → the system decides it failed → it kicks off rebalancing → it adds load to the already-overloaded node → a cascading failure. A human in the loop ("the system proposes — an admin confirms", as in Couchbase and Riak) is slower but saves you from such surprises.
Request routing: where does "foo" live?
Partitions spread across nodes and move during rebalancing. How does a client know which node to go to for key foo? This is a special case of service discovery, and there are three solutions:
- The client knocks on any node (a round-robin load balancer). If the key is there, the node answers itself; if not, it proxies the request to the right node and returns the answer. Cassandra and Riak do this via a gossip protocol: nodes exchange the cluster map among themselves, no external coordinator needed.
- A routing tier takes all requests and knows which node is responsible for what (mongos in MongoDB). It processes no requests itself — just a partition-aware load balancer.
- The client knows the layout and connects to the right node directly, without intermediaries.
In all three, someone must know the current "partition → node" map and learn of changes. The classic solution is a separate coordination service, ZooKeeper: nodes register in it, routers subscribe to changes, and when a partition moves ZooKeeper notifies everyone. HBase, SolrCloud, and Kafka do this. The alternative is gossip (Cassandra, Riak): more complex nodes, but no dependency on an external coordinator.
Where this applies
The "how to shard" fork arrives exactly when one node stopped coping — and almost every decision here is irreversible: a shard key is hard to change, an index scheme cannot be replayed after launch. The practical frame: range — when you need scans by time/order and are ready to fight the hot spot with a compound key; hash — when evenness matters more; local secondary indexes — the default; global — only if reads by a secondary key are critical and an asynchronous update is acceptable.
Where beginners stumble:
- A partition key that starts with a timestamp or auto-increment — all fresh writes into one partition, the classic hot spot. Put diversity first in the key.
- Expecting a secondary index to be as fast as the primary — with local indexes any query not by the shard key is a scatter/gather across all nodes.
hash mod Nfor assigning partitions — the first change in node count reshuffles almost all the data. You need a fixed or dynamic partition count.- Fully automatic rebalancing + automatic failure detection — a recipe for a cascading failure. Keep a human in the rebalancing loop.
- Forgetting the hot key — a celebrity or one popular product takes down a partition, even though the distribution is formally even.
What to read next: MongoDB replication and sharding — shard key, chunks, balancer, mongos in practice; replication models — partitioning almost always comes with replication; building blocks — where sharding sits in the bigger picture. The primary source is Martin Kleppmann, "Designing Data-Intensive Applications," chapter 6.