Partitioning
Partitioning splits data across several nodes, so each node stores and serves only part of it. With a modulo hash, a change from 3 to 4 nodes moves about 3 of 4 keys. Consistent hashing moves only about 1 in 4, the keys that the new node takes.
See it on the board
The same traffic runs on two boards. The simulator measured both when this page was built.
| Measure | Goal | Modulo hash routing | Consistent hash routing |
|---|---|---|---|
| Moved keys | under 30% | 75.4% Fail | 24.6% Pass |
| CPU use | under 55% | 45% Pass | 45% Pass |
| Monthly cost | 64 USD/mo | 64 USD/mo | |
| p99 latency | 3.7 ms | 3.7 ms | |
| Error rate | 0% | 0% |
Key numbers
| Number | Value |
|---|---|
| Reads per second, one cache node | 100,000 ops/s |
| Operations per second, one key-value node | 30,000 ops/s |
| Queries per second, one database | 15,000 ops/s |
| Virtual nodes for each machine, default | 128 nodes |
Hash ring · 3 to 4 nodes · 8 of 36 keys move
How it works
One database or cache node has a limit on storage and on requests per second. Partitioning, also called sharding, splits the keys across several nodes. Each node owns a part of the keys, and a router or the client finds the owner of each key.
The rule that maps keys to nodes is important. A range rule keeps keys in order, which helps range queries, but new keys can all land on one node. A hash rule spreads keys evenly. A simple hash with modulo, key hash mod N, moves most keys when N changes. Consistent hashing puts nodes and keys on a ring, so a new node takes keys only from its neighbors. With virtual nodes, each machine has many small points on the ring, which spreads the load more evenly.
Partitioning has costs. A query that needs many keys must ask many nodes. A transaction across partitions needs coordination. A hot key still lands on one node, so a very popular key can overload its owner while the other nodes are idle.
In the levels you choose the partition rule and add nodes without moving most of the keys.