30-Second Glance
- Rebalance when data size, query load, or machine failure demands it — while still serving reads/writes, moving minimal data, and ending balanced.
- Never use hash mod N: adding/removing a node reshuffles nearly every key.
- Consistent hashing rings (nodes + keys on a circle, virtual nodes for evenness) move only the keys neighboring a change — at the cost of skew, complexity, and coordination.
- Fixed partition counts (e.g. 1000 partitions on 10 nodes) keep key→partition fixed and move whole partitions gradually — but the count must be sized right.
- Dynamic auto-split/merge plus consensus-based failure detection is the dream, but churn too fast and you flood the network.
Rebalancing Partitions
Rebalancing is the process of redistributing data and requests across nodes in a cluster to handle changes such as increased query throughput (requiring more CPUs), increased dataset size (requiring more disks and RAM), and machine failures (necessitating other machines to take over). This ensures efficient load management by moving data and requests from one node to another.
Regardless of the partitioning scheme, rebalancing must meet the following minimum requirements:
- After rebalancing, the load (data storage, read, and write requests) should be evenly distributed across the nodes.
- The database must continue accepting reads and writes during the rebalancing process.
- Only the necessary amount of data should be moved between nodes to ensure fast rebalancing and minimize network and disk I/O load.
Strategies for Rebalancing:
1. How not to do it: hash mod N (= hash(key) % N)
The problem with mod N approach is that if the number of nodes changes, most of the keys will need to be moved from one node to another. Such frequent moves makes rebalancing excessively expensive!
2. Consistent Hashing
The goal of consistent hashing is to minimize the number of objects that need to be reassigned when the number of servers changes, ensuring that almost all objects remain assigned to the same server to maintain balance and minimize disruptions. Watch this: https://youtu.be/UF9Iqmg94tk?t=148
Read here: 2. Hash Based Partitioning(Hashing a key) - Consistent Hashing
Consistent hashing is a technique used in distributed systems to efficiently distribute data across multiple nodes while minimizing the disruption caused by the addition or removal of nodes. It is particularly useful in scenarios where the number of nodes can change dynamically, such as in distributed caches, load balancers, and databases.
Here’s how consistent hashing works:
- Hash Space Representation: Consistent hashing organizes the hash space into a circle, often referred to as a ring. This ring represents the entire range of hash values.
- Node Placement: Each node (server) in the distributed system is assigned a position on the ring based on a hash of its identifier (e.g., IP address, hostname). This placement is typically done using a hash function that generates a hash value for each node.
- Data Placement: Each piece of data (e.g., a cache entry, database record) is also hashed to determine its position on the ring. The data is then assigned to the first node that comes after its position in the clockwise direction on the ring.
- Handling Node Changes:
- Node Addition: When a new node is added, it is placed on the ring based on its hash value. Only the data that would now fall under the new node’s range (between the new node and its predecessor) needs to be moved to the new node. This minimizes the amount of data that needs to be redistributed.
- **Node Removal**: When a node is removed, its data is reassigned to the next node in the clockwise direction. Again, only a small portion of the data needs to be redistributed.
- Virtual Nodes: To improve load balancing and reduce data movement even further, consistent hashing can use virtual nodes. Each physical node is assigned multiple virtual nodes, each with its own position on the ring. This helps distribute the data more evenly and ensures that the removal or addition of a physical node has an even smaller impact on the data distribution.
Cons of consistent hashing are:
- Non-Uniform Distribution: Hash functions might not evenly distribute data, causing load imbalance.
- Increased Complexity: Implementation, especially with virtual nodes, adds complexity.
- Coordination Overhead: Node additions/removals require coordination, introducing latency.
- Partition Hotspots: Uneven key distribution can create hotspots with excessive traffic.
3. Fixed number of partitions:
To address load imbalance in consistent hashing, a system can use more partitions than nodes and assign multiple partitions to each node. For example, in a cluster with 10 nodes, the data could be divided into 1,000 partitions, with each node managing around 100 partitions. When a new node is added, it takes some partitions from existing nodes, and if a node is removed, its partitions are redistributed among remaining nodes.
Key points:
- More partitions than nodes are created (e.g., 1,000 partitions for 10 nodes).
- Nodes manage multiple partitions.
- Adding/removing nodes redistributes entire partitions.
- The number of partitions and key-to-partition assignments remain fixed.
- Reassignment of partitions is gradual, maintaining the old assignment during data transfer.
Cons:
Need to choose pretty good number. Too few : Partitions too big for DB. Too many: Overhead for disk to store partitions (of what partition means what, for example: p0: 0-72, p1: 73-115, .....pN: 800-999).
Dynamic Partitioning:
Should our DB automatically split big partitions and merge small partitions, i.e., manage it's own partitioning ?? What about re-balancing when a node goes down ??
Maybe, but if we do it too often we send tons of data over the network!
How do we ever know if our system is down? Solution : Distributed Consensus
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| hash mod N | Trivial to implement | Almost all keys move on any node change | Never in production (the note's anti-pattern) |
| Consistent hashing (+ virtual nodes) | Minimal key movement on membership change | Skew, hotspot risk, implementation and coordination overhead | Dynamic caches, load balancers, elastic DBs |
| Fixed number of partitions | Stable mapping; gradual whole-partition moves | Too few = oversized partitions; too many = metadata/disk overhead | Clusters with known growth bounds (e.g. 1000 partitions / 10 nodes) |
| Dynamic auto-split/merge | Self-balancing without operators | Rebalance storms can saturate network and disk I/O | Managed stores willing to trade chatter for hands-off balance |
Interview One-Liners
Q: What are rebalancing's three hard requirements? A: End balanced, stay available for reads/writes throughout, and move only the minimum data necessary.
Q: Why is hash(key) mod N the "how not to do it"? A: Every membership change remaps nearly all keys, making rebalancing ruinously expensive.
Q: How does consistent hashing limit movement? A: Nodes and keys share a hash ring; a new node takes only its successor range, a removed node's keys fall to the next clockwise node — virtual nodes even the spread.
Q: What are consistent hashing's cons per the note? A: Non-uniform distribution, virtual-node complexity, coordination overhead on changes, and hotspot risk.
Q: How does fixed-partition-count rebalancing work? A: Create many more partitions than nodes, pin key→partition, and hand whole partitions to new nodes (or redistribute on removal) while serving from the old mapping mid-move.
Q: What danger does the note flag for dynamic auto-splitting? A: Splitting/merging too eagerly ships tons of data over the network — and you need consensus to even agree who is down.