Why does hash(key) mod N break when cluster size changes?
When N grows from 4 to 5 nodes, hash(key) mod 4 and hash(key) mod 5 almost never point to the same node. Redis running mod 4 answers 'key lives on node 2'. The cluster adds a node and switches to mod 5. Now the same key hashes to node 3. Everything on disk is stale—the cache is wiped.
Answered in
When 87% of Your Cache VanishesConsistent hashing maps nodes and keys to a circle, so adding a server moves only 1/N of keys instead of almost all of them.
Read the full analysisOther questions this article answers
More system design & architecture questions
- What does CodeDeploy RESTART actually deploy?
- Does CodeDeploy RESTART work with ECS or Lambda?
- Does RESTART remove an application from load-balancer traffic while it restarts?
- Does Elastic Beanstalk's Active Directory join require a domain password?
- Can an Elastic Beanstalk environment be healthy if the domain join fails?
- Will enabling Active Directory replace running instances?
- What is different about AWS Lambda Web Functions?
- Does Lambda Web Functions automatically cost less than ordinary Lambda?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design & Architecture beat.