Consistent Hashing

출처 : http://timroughgarden.org/notes.html

Consistent Hashing

Goal

• hash bucket(node/server)의 add/detach에서 relocate되는 data의 수를 최소화하자.

Algorithm

• data는 x_i, bucket은 b_j라 부른다.
• hash func을 사용하여 h(x_i)와 h(b_j)를 모두 계산한다. 이때 치역이 동일해야 한다. (ex - Z_2^32)
• x_i는 h(x_i)의 우측 중 가장 가까운 h(b_j)값을 가지는 b_j에 assign된다. (Z_2^32가 원형이라고 생각하자.)
• 그러면 relocation되는 data 수의 기대값은 |X| / |B|.

추가 테크닉

• h(b_j)는 self-balancing tree로 유지하자.
• virtual copy를 사용하면 variance를 낮출 수 있다.
• 각 bucket(node/server)의 capacity에 따라 virtual copy의 수를 조절할 수도 있다.