일관된 해싱

1 개요

consistent hashing

일관된 해싱

• 웹서버의 개수가 변동하는 가운데 요청을 분산하는 방법
• 해시테이블의 크기가 변할 때, 평균적으로 K/n개의 키가 재매핑되면 된다.
• 즉 노드나 슬롯의 개수가 바뀔 때, 노드의 추가나 삭제를 할 때, 전체 n개 노드 중 K개 항목만 다시 섞이면 되는 것이다.
• 기존의 해싱에서는, 키와 슬롯간의 매핑이 모듈러 연산에 의해 정의되었기 때문에, 슬롯의 개수가 변화할 경우 거의 모든 키가 다시 재매핑되어야 했다.

2 복잡도

노드(또는 슬롯) [math]\displaystyle{ N }[/math]개와 키 [math]\displaystyle{ K }[/math]개에 대한 점근적 시간 복잡도

	전통적 해시 테이블	일관적 해싱
노드 1개 추가	[math]\displaystyle{ O(K) }[/math]	[math]\displaystyle{ O(K/N + \log N) }[/math]
노드 1개 삭제	[math]\displaystyle{ O(K) }[/math]	[math]\displaystyle{ O(K/N + \log N) }[/math]
키 1개 추가	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log N) }[/math]
키 1개 삭제	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log N) }[/math]

3 사례

• Couchbase의 자동화된 데이터 파티셔닝
• 오픈스택의 오브젝트 스토리지 서비스 Swift
• 아마존 Dynamo의 파티셔닝 컴포넌트
• Azure Cosmos DB의 데이터 파티셔닝
• 아파치 카산드라의 데이터 파티셔닝
• 볼드모트의 데이터 파티셔닝
• Akka의 일관된 해싱 라우터
• Riak의 분산 키-값 데이터베이스
• GlusterFS의 네트워크 연결 스토리지 파일 시스템
• Akamai CDN

4 같이 보기

• 해싱

5 참고

• 위키백과 "일관된 해싱"
• 다음백과 "일관된 해싱"
• 네이버백과 "일관된 해싱"