We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningIntermediate · Data Replication & Distribution
A hashing technique where adding or removing servers only moves a small fraction of keys. Used by Amazon DynamoDB and Cassandra for data distribution.
In short
Consistent hashing is a way to spread keys across a changing set of servers so that when you add or remove a server, only about 1/N of the keys have to move instead of nearly all of them. It maps both servers and keys onto the same circular hash space, and each key is handled by the first server it meets going clockwise.
In short
Consistent hashing is a way to spread keys across a changing set of servers so that when you add or remove a server, only about 1/N of the keys have to move instead of nearly all of them. It maps both servers and keys onto the same circular hash space, and each key is handled by the first server it meets going clockwise.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Consistent Hashing across a run of lessons, not one page. These 4 alone are about 135 minutes of step-by-step reading, every one with a quiz.
The algorithm that makes adding or removing nodes cheap, an interview favorite and production essential.
Design a distributed key-value store - LSM trees, compaction, consistent hashing, replication, tunable consistency, and failure detection.
How a distributed cache spreads keys across nodes with consistent hashing and virtual nodes. Measured tests show why a hot key still overloads a node.
Using hash functions to distribute rows evenly across partitions, the antidote to hotspots and skewed data.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Consistent Hashingpay once,
yours for life
Suppose you run a cache or a database split across several servers, and you decide which server owns a key with simple modulo arithmetic: server = hash(key) % N, where N is the number of servers. With three servers this is fine. The trouble starts the moment N changes.
Add a fourth server and N goes from 3 to 4. Now hash(key) % 4 gives a different answer than hash(key) % 3 for almost every key. In practice somewhere around 75 to 100 percent of keys suddenly map to a different server. For a cache that means a near-total miss storm: every lookup misses, every miss falls through to the database, and the database gets hit with the full traffic it was being shielded from. For a sharded database it means moving almost all of your data between nodes just to add one machine.
Servers do not stay fixed. They crash, they get added during traffic spikes, they get removed when load drops. A scheme that reshuffles everything on each change is unusable at scale. Consistent hashing exists to make that change cheap.
Instead of hashing into a small range of server indexes, consistent hashing hashes into a large fixed space, for example the integers from 0 to 2^32 minus 1, and treats that space as a circle. The end wraps back around to the start.
Every server is hashed onto a point on this circle, usually by hashing its name or IP address. Every key is hashed onto the circle the same way. To find which server owns a key, you start at the key's position and walk clockwise until you hit the first server. That server owns the key.
The important part is what happens on change. When you add a server, it lands somewhere on the circle and takes over only the keys that sit between it and the previous server going counter-clockwise. Every other key keeps the same owner. When a server leaves, only its keys move, and they all go to the next server clockwise. Either way you disturb roughly 1/N of the keys, not the whole set.
The hash ring
Servers and keys share one circular hash space. A key is owned by the first server clockwise from it.
A plain ring has two weaknesses. First, with only a few servers placed at random points, the gaps between them are uneven, so one server can end up responsible for a much larger arc of the circle, and therefore much more traffic, than the others. Second, when a server dies, its entire share lands on the single neighbor clockwise from it, which can overload that one machine.
The fix is virtual nodes. Each physical server is placed on the ring not once but many times, often 100 to 200 times, by hashing names like server-A#1, server-A#2, and so on. Now each physical server owns many small arcs scattered around the circle instead of one big arc. The load evens out, and when a server fails its share is spread across many neighbors rather than dumped on one.
Virtual nodes also let you weight servers. A machine with twice the memory can be given twice as many points on the ring, so it naturally takes twice the share of keys.
Consistent hashing is more complex than modulo. You need a sorted structure of ring positions, typically a balanced tree or a sorted array with binary search, so that the clockwise lookup is fast. With virtual nodes you also store many more positions, which costs a little memory and makes the ring metadata something every node has to agree on.
It reduces how many keys move on a membership change, but it does not give you fault tolerance by itself. If the single server that owns a key dies, that key is gone unless you also replicate it. Real systems combine consistent hashing for placement with replication to the next few servers clockwise for durability.
Choosing the number of virtual nodes is a tuning decision. Too few and the load is lumpy. Too many and the ring metadata and rebalancing bookkeeping grow. Most production systems settle somewhere in the low hundreds per physical node.
Amazon DynamoDB
The original Dynamo paper popularized consistent hashing with virtual nodes for partition assignment and replication across nodes.
Apache Cassandra
Cassandra arranges nodes on a token ring and uses the same clockwise ownership model, with virtual nodes (vnodes) for even distribution.
Redis Cluster
Uses 16,384 hash slots rather than a pure ring, a closely related idea that keeps key movement small when the cluster changes.
It keeps the number of keys that move small when servers are added or removed. With plain modulo hashing, changing the number of servers remaps almost every key, which causes a cache miss storm or a full data reshuffle. Consistent hashing moves only about 1/N of the keys instead.
Modulo hashing computes server = hash(key) % N, so the answer depends on N. Change N and almost every key changes server. Consistent hashing maps servers and keys onto a fixed circular hash space and assigns each key to the next server clockwise, so adding or removing a server only affects the keys near that server's position.
A virtual node is one of many ring positions assigned to a single physical server. Without them, a few servers placed at random points create uneven load, and a failing server dumps its whole share on one neighbor. Giving each server 100 to 200 positions evens out the load and spreads a failed server's keys across many neighbors.
Roughly 1/N of the keys, where N is the number of servers, compared with close to all of the keys under modulo hashing. With virtual nodes the moved keys also come from many small arcs spread around the ring rather than one large block.
Amazon DynamoDB and Apache Cassandra use it for partition placement, Discord and many CDNs such as Akamai use it for request routing and caching, and Redis Cluster uses the closely related fixed hash-slot approach.
Design a Key-Value Store
Design a distributed key-value store - LSM trees, compaction, consistent hashing, replication, tunable consistency, and failure detection
Distributed Cache
How a distributed cache spreads keys across nodes with consistent hashing and virtual nodes. Measured tests show why a hot key still overloads a node.
Hash Partitioning
Using hash functions to distribute rows evenly across partitions, the antidote to hotspots and skewed data
Affinity Routing
Routing on a key that names whose data a request is for, so the request lands where that data already is
Sharding
Splitting a database into smaller pieces (shards) distributed across multiple servers. Each shard holds a subset of the data.
Load Balancer
Distributes incoming traffic across multiple servers so no single server gets overwhelmed. Like a traffic cop directing cars to different lanes.
Replication
Keeping copies of the same data on multiple servers. Improves read performance and provides fault tolerance if one server goes down.
Database Partitioning
Dividing a large table into smaller, more manageable pieces while keeping them in the same database. Sharding is partitioning across servers.
Read Replica
A copy of your database that handles read queries, reducing load on the primary database. Writes still go to the primary and replicate out.
Write-Ahead Log
A technique where changes are written to a log before being applied to the database. Ensures durability and crash recovery.
This page explains the idea. The "Consistent Hashing" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Consistent Hashing lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Consistent Hashing in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
