Split keys with hash mod N

Build a wide-column store (Cassandra / DynamoDB family) (13 scenes)

Scene 02 · Split keys with hash mod N

Hash the key, take it mod N, route to that server — keys spread evenly across the cluster.

Previously

One box has three ways to die, so we need many boxes; the first job is deciding which box owns which key.

Scene 02

Split keys with hash mod N

Watch

Diagram

Four **server** bins along the bottom (S0..S3). A stream of **key** dots falls from the top, each labelled with a small partition-key string. A **hash-mod-N** router box in the middle decides which bin each dot drops into. The **partition key** is the labelled string on each dot — the portion of the row identifier that is hashed to decide which server owns the row. **Hash mod N** is the routing scheme itself: server index = hash(partition_key) mod N, where N is the cluster size.

Watch each partition key get hashed and dropped into one of four server bins. Same key always lands in the same bin — that's how a client can later find a row by hashing the key and going straight to the owner.

Implementation

Router.route (hash mod N)

hash the partition key, take it mod cluster size

1def route(key, N):
2    h = hash(partition_key(key))
3    return servers[h mod N]
4 
5# same key → same h → same server,
6# every time, on every client.

Router.route (range)

binary-search the key into a sorted list of range bounds

1# ranges = [(-inf, b0), (b0, b1), ..., (b_{N-2}, +inf)]
2def route(key, ranges):
3    i = upper_bound(ranges, key)
4    return servers[i]
5 
6# monotonically-increasing keys (timestamps, auto-incr ids)
7# all return the same i — the rightmost bin.

PreviousOne server, three ways to die NextAdding a server remaps everything