Skip to content
Get started

How many keys move when you add servers?

Keys have uniformly random 64-bit hashes hh. Scheme 1 assigns a key to server h mod Nh \bmod N. 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 N=6N = 6 to N=8N = 8 servers. The fraction of keys that change server under Scheme 1 is how many times the fraction under Scheme 2?

Show hints (2)+
  1. A key keeps its server iff h mod 6=h mod 8h \bmod 6 = h \bmod 8; that depends only on h mod 24h \bmod 24.
  2. Under consistent hashing, which keys have to move at all?

Answer

Reveal answer →

3

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions