How many keys move when you add servers?
Keys have uniformly random 64-bit hashes . Scheme 1 assigns a key to server . Scheme 2 is ideal consistent hashing (each server owns an equal share of a hash ring, and adding servers only moves keys onto the new servers). You grow the cluster from to servers. The fraction of keys that change server under Scheme 1 is how many times the fraction under Scheme 2?
Show hints (2)+
- A key keeps its server iff ; that depends only on .
- Under consistent hashing, which keys have to move at all?
Answer
Reveal answer →Final answer
3
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading