consistent hashing does: minimizes remapping when nodes join/leave

How can we efficiently share resources without constant reorganization?

Imagine you're organizing a group of friends to share a limited number of books. Each friend wants to borrow books without causing chaos when new friends join or when some leave.

Think of each book as a slot in a library. Consistent hashing helps us assign books to friends in such a way that when new friends come or go, only a few need to swap books instead of everyone.

Example

If there are 10 books (slots) and 5 friends (keys), consistent hashing means only 2 friends (10/5) need to change their book assignments when a new friend joins or an old one leaves.

Remember this

Consistent hashing minimizes the number of friends who need to swap books when the group changes, making sharing resources smoother and less disruptive.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

consistent hashing solves: minimizes key redistribution when servers are added/removed

Consistent hashing minimizes key redistribution when servers are added/removed

Locality-sensitive hashing

Locality-sensitive hashing (LSH) hashes similar items into the same buckets

ACID

ACID guarantees data validity in transactions

database sharding does: splits data across machines by a partition key

Why can't you just split a huge library into smaller ones?

Hash table

Hash table lookup: O(1) average time complexity

O(n log n) is the lower bound for comparison-based sorting

Ever wonder why sorting can't be faster than a certain point?

Swipe through 100 ML concepts daily

Open Pocket Polymath