[ 데이터 베이스 ] Consistent Hashing에 대해서 설명해 보세요.

Hash Ring을 사용해서 해싱을 하는 방법입니다.
메타정보 조회 없이 클러스터에서 키가 저장된 노드를 바로 찾아갈 수 있습니다.
Rebalancing문제를 해결하기 위한 방법입니다.
Virtual Node는, 실제 물리 노드보다 토큰을 더 많이 보유하는 방식입니다.
이를 통해, Object분포의 불균일성을 해결합니다.

일반 HashTable을 사용하면, 분산 DB에서 node를 추가하거나 삭제하는데
O(K)의 시간이 걸립니다. (K는 Key의 수) Coninstent Hashing을 사용하면
O(K/N)의 시간으로 가능합니다. 단, Key를 추가하거나 삭제할 때,
일반적인 HashTable은 O(1)이면 가능하지만, Consistent Hashing의 경우
O(logN)의 시간이 걸립니다. (N은 Node의 수)

DynamoDB, Memcached와 같은 NOSQL에 주로 사용되고 있습니다.

 

참고 자료:

https://binux.tistory.com/119

https://velog.io/@dev-log/%EC%95%88%EC%A0%95-%ED%95%B4%EC%8B%9C-%EC%84%A4%EA%B3%84Consistent-hashing