Consistent Hashing: Adding Nodes Without Losing the Cache
Published on · In Software Engineeringby Steven Brown
Consistent hashing is a method for assigning keys to servers so that adding or removing a server moves only a small share of the keys instead of nearly all of them. Every server and every key is hashed into the same numeric range, that range is treated as a circle, and each key belongs to the first server found moving clockwise from the key's own position. When a server is added, it takes over only the keys sitting between itself and the previous server on the circle. Every other key stays where it was.
That property is the whole reason the technique exists. The obvious alternative, hash(key) % serverCount, reassigns almost every key the moment the server count changes: going from eight cache nodes to nine moved 88.8% of a million keys in the measurements below, while a hash ring moved 11.8%. For a cache in front of a database, the first number is an outage and the second is a Tuesday.
