Hash-Based Sharding

Apply consistent hashing to ensure uniform data distribution and minimal remapping during node changes.

In this lesson, you will learn how hash-based sharding solves the data distribution problem and how consistent hashing minimizes disruption when your cluster scales.

The Challenge of Simple Hashing

In basic hash-based sharding, you map a key to a specific node using the formula node = hash(key) % N, where N is the total number of nodes. While this provides excellent uniform data distribution (avoiding "hot spots" common in range-based sharding), it has a catastrophic flaw: when you add or remove a node, N changes. Because the modulo operator relies on the total number of nodes, nearly 100% of your data keys will map to a different node, forcing a massive, expensive rebalancing operation across the entire cluster.

Enter Consistent Hashing

Consistent hashing solves this by mapping both your data keys and your nodes onto a virtual "ring"—a circular address space (e.g., 0 to 2^32 - 1).

Placement: You hash each node’s identifier to place it at a specific point on the ring.
Mapping: For any given data key, you hash it to land on the ring. You then travel clockwise until you hit the first node. That node is the owner of that data.

-- Conceptual Mapping
-- Key 'user_123' hashes to position 500
-- Node A hashes to 100, Node B to 600
-- 'user_123' belongs to Node B (the next node clockwise)

Minimizing Remapping

When you add a new node, it only "steals" keys from the node immediately clockwise to it on the ring. The rest of the nodes remain unaffected. If you remove a node, its keys simply shift to the next available node on the ring. This limits the data movement to only $K/N$ keys (where $K$ is the total keys and $N$ is the number of nodes), rather than the "all-or-nothing" remapping of standard modulo hashing.

To further improve distribution, we often assign each physical node multiple "virtual nodes" (or tokens) scattered around the ring. This ensures that if one node fails, its load is distributed across multiple neighbors, preventing a single surviving node from becoming overwhelmed.

Key Takeaway: Consistent hashing maintains uniform data distribution while confining data remapping to a small, localized subset of nodes during cluster membership changes.