Part 5 of 8 · 2 min read
Why hash mod N fails
The cost of changing the number of nodes under the simplest placement rule.
Think of a classroom where a teacher seats pupils by the last digit of their ID number: 10 desks for 10 digits. When an 11th desk is added, the teacher wants to seat by "ID mod 11" instead. Nearly every pupil must move.
Clusters change. The book lists the causes: query throughput grows and CPUs must be added; the data grows and disks and memory must be added; a machine fails and others take over its work. All of these need data and requests to move from one node to another. This is called rebalancing.
Rebalancing
Rebalancing is the process of moving data and load from one node to another so that the load is shared fairly after nodes are added or removed.
Example: a cluster of 10 nodes gets an 11th. Some partitions move from the old nodes to the new one so that all 11 hold about the same.
The book sets minimum requirements for any scheme:
- After rebalancing, the load (data, reads, writes) is shared fairly.
- While it happens, the database keeps accepting reads and writes.
- No more data than necessary is moved, to keep it fast and to limit network and disk load.
The book's example of how not to do it: place a key on node hash(key) mod N. If the number of nodes N changes, most keys must move. Take a key with hash 123456. With 10 nodes it lives on node 6 (123456 mod 10). With 11 nodes it moves to node 3 (123456 mod 11). With 12 nodes it moves to node 0 (123456 mod 12). Such frequent moves make rebalancing very expensive.
A worked example of the amount moved. 1,000,000 keys on 10 nodes, one node added.
- Keys that stay: those whose hash gives the same remainder mod 10 and mod 11. Looking over a cycle of 110 hash values, that holds for 10 values (0 to 9), so one in 11.
- Keys that move: 10 ÷ 11 ≈ 91 percent, about 909,000 keys.
- The minimum necessary: the new node should hold 1/11 of the data, about 91,000 keys. So mod N moves 10 times more than needed.
The fix is to separate two ideas: the partition of a key and the node of a partition. The next section shows how.
Check yourself:
- A key has hash 5,000. On which node is it with 8 nodes, and with 9 nodes?
- What is the least amount of data that must move when a 10th node joins a cluster of 9?