참고
해시 키 재배치(refresh) 문제
NOTE
해시 키 재배치 문제는 안정 해시로 인해 풀고자하는 문제이다!
serverIndex = hash(key) % N (N = 서버의 개수)
Java
복사
N개의 서버를 위의 해시 함수를 사용해 부하를 나누려고 한다.
총 4대의 서버를 사용하고, 키에 대한 인덱스를 뽑는다.
서버 풀의 크기가 고정되고, 데이터 분포가 균등하면 잘 동작한다!
기존 서버 1이 장애를 일으켜 동작을 중단한다. (N이 3으로 변경)
1번에 있던 키뿐 아니라, 대부분의 키가 재분배되었다. (대규모 캐시 미스가 발생하게됨)
안정 해시
NOTE
수평적 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
⇒ 안정해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술!
•
안정 해시는 해시 테이블의 크기가 조정될 떄 평균적으로 오직 k/n개의 키만 재배치하는 기술이다.
•
여기서 k는 키의 개수이고 n은 슬롯의 개수이다. 전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다.
해시 공간과 해시 링
NOTE
안정 해시는 기본적으로 해시 공간을 구부린, 해시 링이라는 개념을 사용한다!
위의 직선(해시 공간)을 원(해시 링)으로 만든다고 생각하면 된다.
•
해시 공간
◦
특정 해시 함수로 나누어질 수 있는 공간의 전체 범위를 의미한다.
•
해시 링
◦
이 해시 공간의 양쪽 끝을 구부려서 논리적인 링처럼 생각하는 개념
해시 서버
NOTE
해시 서버의 해시 함수 ⇒ 서버 IP 혹은 이름을 링의 특정한 주소에 위치 시킬 수 있다!
4개의 서버를 해시 링에 배치한 결과
해시 키
NOTE
해시 키의 해시 함수 ⇒ 캐시할 key를 해시 링 위의 지점에 배치할 수 있다!
4개의 key가 해시 링에 배치한 결과
서버 조회
NOTE
어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다!
각 key는 시계방향에서 만나는 첫 번째 서버로 배치된다.
서버 추가/제거
NOTE
해당 서버의 key만 재배치되며, 나머지 key는 재배치되지 않는다!
key0이 기존의 서버0이 아닌, 서버4로 재배치된다.
key1이 서버1이 아닌, 서버2로 배치된다.
기본 구현 법의 2가지 문제
NOTE
파티션(partition)의 크기를 균등하게 유지하거나, 키의 균등 분포가 힘들다!
서버1이 삭제되면서 서버2가 절반 가까이 공간을 차지하게 된다.
대부분의 key가 서버 2에 보관되게 된다.
가상 노드
NOTE
실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다!
서버 0, 서버 1 (가상 노드 3개를 가진다)
가상 노드의 개수를 늘리면 키의 분포가 점점 더 균등해지기 떄문에 나온 방법!
안정 해시의 이점과 사용사례
NOTE
이점
•
서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
•
데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
•
핫스팟(hotspot) 키 문제를 줄인다.
◦
특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다.
◦
유명인의 데이터가 전부 같은 샤드에 몰리게 되는 경우를 생각하자.
사용 사례
•
아마존 DynamoDB의 파티셔닝과 컴포넌트
•
아파치 카산드라 클러스터에서의 데이터 파티셔닝
•
디스코드 채팅 애플리케이션