Split keys with hash mod N

Hashing the partition key and taking it mod N spreads writes evenly across N servers, beating range partitioning's hot-tail problem.

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
Try it
Predict
Capture

What to watch for

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

Highlighted lines are the ones running in the diagram right now.

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.

Where this sits in Build a wide-column store (Cassandra / DynamoDB family)

Scene 02 of 13, in the Sharding act — Hash mod N spreads load — until adding a server reshuffles 80% of keys.. Hash the key, take it mod N, route to that server — keys spread evenly across the cluster.

Up next. Hash mod N spreads load beautifully — until the day we add the fifth server, when N suddenly changes and almost every key needs a new home.

All 13 scenes in Build a wide-column store (Cassandra / DynamoDB family) · Every curriculum

Built with Arqly

Every scene in Build a wide-column store (Cassandra / DynamoDB family) builds on the one before it.All 13 Build a wide-column store (Cassandra / DynamoDB family) scenes