Partitioning Internals: Key → Partition Function → Node

Strip sharding down and there are three things: a key (whatever identifies the row for routing: a tenant id, a user id, a timestamp), a partition function that maps the key to a partition, and an assignment of partitions to nodes. Everything the practical lesson described — "hash sharding", "range sharding", "hot shard", "resharding" — is a statement about the function or the assignment. The separation matters: a function that maps keys directly to nodes (hash mod N) has nothing to change incrementally when N changes; a function that maps keys to many small, stable partitions, plus an assignment table, can move one partition at a time.

Hash. node = hash(key) mod N, or a hash onto a fixed number of slots (Redis Cluster: CRC16 mod 16384; DynamoDB and Cassandra: a 128-bit token). A good hash makes any key distribution uniform across partitions, so balance is free and a point lookup is one node. Order is destroyed: WHERE ts BETWEEN or WHERE id > 1000 must visit every partition. Composite keys can hash a prefix and keep order within it — Cassandra's partition key vs clustering columns, DynamoDB's partition key vs sort key — so that "all events for device 42 in June" is one partition with a range inside it.

Range. A sorted table of boundaries: keys in [a, b) go to partition 1. Adjacent keys share a partition, so range scans and prefix scans are local, and time-based retention is "drop the oldest range". The key's distribution becomes the partition distribution: names cluster, ids grow, one tenant dominates. A monotonically increasing key — auto-increment, timestamp — means every insert goes to the *last* range: the write hot spot, cured by prefixing a hash or a tenant id ((tenant_id, ts)) at the cost of losing the global time order. Ranges must be split when they grow (HBase regions, CockroachDB ranges at 512 MB) and merged when they shrink.

List / geographic. An explicit mapping from key values to partitions: region = EU → cluster-eu. It is the only option when law dictates where data lives, it gives locality for free, and its partitions are as unequal as the regions are. In practice it is the outer level of a hierarchy: list by region, then hash or range inside.

With hash mod N, changing N changes the result for almost every key: going from 4 to 5 nodes remaps 80 % of keys, which for a terabyte cluster is a terabyte of copying to add 25 % capacity. Consistent hashing maps both nodes and keys onto the same circle of hash values [0, 2³²); a key belongs to the first node clockwise from its position. Adding a node inserts one point and claims only the arc between it and its predecessor — on average 1/N of the keys, taken from exactly one neighbour. Removing a node hands its arc to the next node clockwise. This is the same idea as a Hash Table whose buckets can be added one at a time without rehashing the rest.

One point per node gives uneven arcs (a node might own 40 % of the circle by bad luck) and dumps a departing node's entire load on one neighbour. Virtual nodes fix both: each physical node owns 64–256 points scattered around the ring, so its share is the sum of many small arcs (variance shrinks like 1/√vnodes), a new node takes a sliver from every existing node, and a departing node's arcs are spread across all survivors. Heterogeneous hardware gets more vnodes. Cassandra defaults to 16 vnodes per node (256 historically); DynamoDB and Riak use the same construction. Redis Cluster achieves the same effect differently: 16,384 fixed hash slots assigned to nodes in contiguous ranges, moved one slot at a time.

A partition function balances *keys*; it cannot balance *traffic per key*. If one tenant generates 40 % of requests, the partition holding that tenant carries 40 % of the load however the tenants are hashed. If one row — a celebrity's profile, a global counter, today's feature flag — is read a million times a second, its partition is hot and adding nodes does nothing. Under range partitioning, a time-ordered key makes the newest range hot for *every* write. Detecting it is a per-partition metric (requests, bytes, CPU) with the max far above the mean; DynamoDB surfaces it as throttling on one partition while the table's aggregate is idle.

The remedies are all at the key level. Split the key: counter:42 becomes counter:42#0 … #15, writes pick a suffix at random, reads sum sixteen keys. Salt the range key: prefix a time-based key with a small hash so inserts spread over k partitions, and read all k for a time range. Cache the hot key in front of the store. Isolate: give the whale tenant its own partition or node — an explicit exception in the routing table. Adaptive splitting (DynamoDB adaptive capacity, CockroachDB load-based splitting) does the range version automatically by splitting a range that receives disproportionate traffic, but it cannot split a single key.

Two different operations hide under "rebalance". Moving a fixed partition (a hash slot, a vnode's arc): the partition's data is copied to the new owner while the old owner keeps serving; writes during the copy are either forwarded or double-written; at cutover the metadata changes, requests that arrive at the old owner are redirected (Redis MOVED/ASK), and the old copy is deleted. The unit is fixed and the count is large, so moves are small and parallel. Splitting a range: a range that grew beyond a size or load threshold is split at a median key into two ranges, the metadata gains a boundary, and one half may then be moved. Ranges are created by the data, so the count grows with the table and the split decision is a per-range policy.

Both must handle the same hazards: a client with stale metadata (answer with a redirect and the new epoch), a move that fails halfway (the old owner stays authoritative until the cutover record is durable), and rebalancing load competing with production traffic (rate limits; Cassandra streams, CockroachDB's snapshot rate limit). Never rebalance by changing the function itself — mod 4 to mod 5 — on a live system; that is the naive step from the derivation, and it moves everything at once.

An index on a column that is not the partition key faces a choice. A local index (document-partitioned) lives inside each partition and indexes only that partition's rows: writes stay local — the row and its index entries are on the same node, in the same transaction — but a query WHERE email = ? must be sent to every partition, because any of them might hold a match. Cassandra secondary indexes, DynamoDB local secondary indexes, Citus and PostgreSQL per-partition indexes work this way. A global index (term-partitioned) is itself partitioned by the indexed value: email hashes to one index partition, which stores (email → partition key), so the query is one index lookup plus one row fetch. Writes now touch two partitions — the row's and the index's — which is either a distributed transaction (CockroachDB, Spanner) or asynchronous and eventually consistent (DynamoDB global secondary indexes, Elasticsearch).

Every query that does not name the partition key is a scatter/gather: send to all P partitions, execute locally, merge. Aggregations merge per group; ORDER BY … LIMIT k needs k from every partition and a k-way merge; COUNT(*) sums; a join across partitions is either co-located (both tables partitioned by the same key, so each partition joins locally — the single most important shard-design trick) or a broadcast of the smaller table to every partition, or a full reshuffle. Latency is the slowest partition's; cost grows linearly with P; and a query that was fine at 4 partitions is a problem at 64. This is why the shard key must appear in almost every query, and why designs that cannot achieve that (Partitioning and Sharding) should not shard.