출처 : 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의 수를 조절할 수도 있다.
'알고리즘' 카테고리의 다른 글
Bidirectional Dijkstra 설명 (0) | 2020.03.13 |
---|---|
(Approximate) Heavy Hitters, Count-Min Sketch, Bloom Filter (0) | 2020.03.13 |
Universal Hash Family 설명 (0) | 2020.03.13 |
다양한 Cache Replacement Policy 정리 (0) | 2020.01.07 |
다양한 Data Compression 알고리즘 정리 (0) | 2020.01.02 |