Course contentsShow
← Computer Science
Lesson 1732 of 2,87239. NoSQL and Modern DatabasesFree lesson

Consistent Hashing

Using consistent hashing to minimize data movement when nodes are added or removed from the cluster.

Consistent Hashing

You'll learn how consistent hashing minimizes data movement when scaling key-value stores up or down.

The Problem with Naive Hashing

In a key-value store with multiple nodes, you might naively distribute keys using node = hash(key) % number_of_nodes. This works—until you add or remove a node. Suddenly, the modulo changes, and almost every key maps to a different node, forcing massive data migration.

How Consistent Hashing Works

Consistent hashing maps both keys and nodes onto the same circular hash space (imagine a clock face from 0 to 2³²-1). Each node claims responsibility for the range of hash values between itself and the previous node on the ring.

When a key needs storage, you hash it, find its position on the ring, and walk clockwise to the nearest node.

Why It Minimizes Movement

Adding a node: Only keys in the range between the new node and its predecessor need to move—just one node's worth of data.

Removing a node: Only that node's keys move to its successor. All other keys stay put.

With naive hashing, adding the 4th node to a 3-node cluster remaps ~75% of keys. With consistent hashing, only ~25% move (roughly 1/N where N is the new total).

The Ring Analogy

Think of a circular parking lot where cars (keys) park at the first available spot clockwise from their assigned number. Adding a new parking attendant (node) only affects cars between the new attendant and the previous one—everyone else stays parked.

Key Takeaway: Consistent hashing places keys and nodes on a shared hash ring, ensuring that adding or removing nodes only redistributes keys from immediate neighbors, typically affecting just 1/N of the data instead of nearly all of it.