Share
Sign In
안정 해시
해시 키 재비치(rehash) 문제
보편적인 해시 함수 : serverIndex = hash(key) % N (N은 서버 개수)
서버의 개수가 바뀌면 serverIndex를 모두 다시 계산 ⇒ 대규모 캐시 미스가 발생
안정 해시(consistant hash)
해시 함수로 SHA-1를 사용한다고 가정하면 총 해시 공간은 0~2^{160}-1
서버 : 서버의 고유한 값(IP, 이름 등)을 해싱해서 이 공간 어딘가에 배치한다.
키 : 키를 해싱해서 이 공간 어딘가에 배치한다.
해시 공간의 앞 뒤를 이어붙이면 아래 그림처럼 된다.
그리고 모든 키값은 자기 바로 다음에 나오는 서버(노드)에 할당된다.
서버 추가 : 오른쪽 그림과 같이 주황색 서버가 추가되면 파랑과 주황 사이의 키값들만 재배치된다.
서버 제거 : 주황색 서버가 제거된다면, 주황색 서버에 배치된 키들만 재배치된다.
문제점
파티션(서버 사이의 해시 공간)이 균일하지 않다.
서버를 추가 또는 삭제할 경우 파티션의 크기가 급격하게 달라진다.
키값이 균등하게 분포하지 않는다.
⇒ 가상 노드 또는 복제 기법을 사용해 해결한다.
가상 노드
하나의 서버를 여러 해시 공간에 가상으로 두는 방법이다.
가상 노드의 개수가 많아질 수록 표준 편차가 줄어들어 키의 분포는 점점 균등해진다.
SHA-1에서 가상 노드가 200개 일 때 표준 편차가 평균의 5%로 제일 낮았다.
재배치 방법은 안정 해시와 비슷하게 가상 노드 사이의 키들만 재배치한다.
표준 편차와 노드의 저장 공간 사이의 트레이드 오프가 필요하다.
장점
재배치되는 키의 수가 최소화된다.
데이터가 균등하게 분포하므로 수평적 규모 확장에 용이하다.
특정 노드(샤드)에 접근이 몰리는 핫스팟 문제를 줄일 수 있다.
용례
AWS DynamoDB 파티셔닝 관련 컴포넌트
Apache Cassandra 클러스터의 데이터 파티셔닝
디스코드 채팅 앱
추가
데이터를 여러 대의 노드에 저장하는 방법이다. 키의 위치 다음 N개의 노드에 데이터를 저장한다.
