1. 해시 키 재비치 문제
•
N대의 캐시 서버가 있을 경우 부하를 균등하게 나누는 보편적 방법은 해시 함수를 사용하는 것이다.
◦
serverIndex = hash(key) % N
•
이 방법은 서버 풀의 크기가 고정되어 있을 때, 데이터 분포가 균등항 때는 잘 작동한다.
◦
서버가 추가되거나 기존 서버가 삭제되면 문제가 생기기 시작한다.
◦
해시의 연산이 달라지며 엉뚱한 서버로 캐시를 찾기위해 찾아갈 수 있다.
2. 안정 해시
•
해시 테이블의 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술
◦
k = 키의 개수, n = 슬롯 개수
◦
전통적 해시 테이블은 전체를 재배치 해야한다.
2.1. 해시 공간과 해시 링
•
SHA-1을 사용 한다면 범위는 0부터 2^160-1 까지로 알려져 있다.
◦
이 해시를 일렬로 쭉 줄세워 만들었을 때 처음과 끝을 접하게 하면 해시 링이 만들어진다.
2.2. 해시 서버
•
해시 함수 f를 사용하면 서버 IP나 이름을 이 링 위의 어떤 위치에 대응할 수 있다.
2.3. 해시 키
•
여기 사용된 해시 함수는 “해시 키 재배치 문제”에 언급된 함수와는 다르며, 나머지 연산은 사용하지 않고 있음에 유의하자
•
캐시할 키 key 0~4 또한 해시 링 위의 어느 지점에 배치할 수 있다.
2.4. 서버 조회
•
어떤 키가 저장되는 서버는, 해당 키의 위치로 부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.
2.5. 서버 추가
•
서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.
•
앞서 본 그림에서 서버4가 추가된다면 key0만 재배치하면 된다.
◦
원형 순회 시 key0이 처음으로 만나는 서버가 서버4이기 때문
2.6. 서버 제거
•
하나의 서버가 제거되면 키 가운데 일부만 재배치된다.
•
앞서 본 그림에서 서버1이 제거된다면 서버1을 가르키던 key2만 서버2로 재배치된다.
2.7. 기본 구현법의 두 가지 문제
•
기본적인 절차
◦
서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
◦
키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
•
문제점
◦
서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기가 균등하게 유지하는게 불가능하다
◦
키의 균등 분포를 달성하기가 어렵다
2.8. 가상 노드
•
가상노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
•
위 그림에서는 서버당 1~3개 정도의 가상 노드를 가진다.
◦
해당 수는 임의로 정한것이며 실제 환경에서는 훨씬 큰 값이 사용된다.
◦
따라서 각 서버는 하나의 파티션이 아닌 여러 파티션을 관리해야 한다.
•
키 또한 생성되어 시계방향으로 탐색하여 만나는 최초의 가상노드를 가리킨다.
•
가상 노드의 수를 늘리면 키의 분포는 점점 더 균등해진다.
◦
표준편차가 적어져 데이터가 고르게 분포되기 때문
•
가상 노드의 개수를 늘리면 표준 편차 값은 더 떨어진다.
◦
그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다.
◦
결국 시스템 요구사항에 맞게 적절히 조절해야한다.
