SDI(9)
오늘 배운 것
5장 - 안정 해시 설계
수평적 규모 확장성을 위해 서버를 분산하면, 요청을 골고루 넣어줘야 한다. 이때 해시-안정해시가 사용된다.
해시 키 재배치 문제
간단한 해시 함수 f를 생각해보자.
f: serverIdx=hash(key) % N (N은 서버의 개수)
그러면 서버 4개가 있고, 인덱스가 0123이 된다.
그리고 Data가 8개가 있고, 이 Data가 key를 갖고있다고 치면, 해시를 통해 key가 해시되고 골고루 저장된다.
서버 0-Data 0-1 서버 1 - Data 3 5 …
그런데 문제는, 서버 풀이 변경되면 문제가 생긴다. hash(key)가 % 당할 N 자체가 변경되어 장애가 발생하여 종료된 해당 서버의 키 뿐만 아니라. 멀쩡하던 다른 데이터도 해시 대칭이 달라져서 아예 다른 서버로 연결된다.
이로 인해 발생한 문제를 해결하기 위해, 안정해시가 도입되었다.
안정 해시
안정 해시 는 `해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. k는 키의 개수, n은 슬롯의 개수다.
이와 달리, 전통적 해시 테이블은 슬롯의 수가 바뀌면, 대부분의 키를 재배치한다.
해시 공간과 해시 링
해시 함수가 생성하는 모든 가짓수의 집합을 해시 공간이라고 한다. 이 해시공간을 쭉 일자로 표현할텐데, 이걸 앞뒤를 이어 링으로 만들어서 생각한다.
해시 서버
해시 함수를 사용하여 서버를 링 위의 어떤 위치에 대응시킨다.
해시 키
여기 사용된 해시 함수는 “해시 키 재배치 문제” 에서 언급된 함수와는 다르다. 캐시할 키들도 어느 지점에 배치한다.
서버 조회
이 키가 저장되는 서버는, 시계방향 기준으로 처음 만나는 서버에 저장된다.
서버 추가
서버를 추가하면 링 위에 놓고, 전통적으로는 거의 대부분의 키가 재배치 될테지만, 여기서는 추가한 서버 기준으로 반시계방향으로 가면서 만나는 키를 저장한다. 그러다가 다른 서버를 만나면 탐색 종료.
서버 제거
서버가 제거되더라도 전통방식처럼 혼란이 없고, 그냥 길잃은 키를 재배치한다.
기본 구현법의 2가지 문제
이 안정 해시 알고리즘은 MIT에서 개발되었고, 기본 절차는 다음과 같다.
- 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계방향으로 탐색하다 만나는 최초 서버가 키가 저장될 서버다.
그러나 여기에는 2가지 문제가 있다.
-
서버가 추가, 삭제되는 상황에서 파티션의 크기를 균등하게 유지하는게 불가능 하다. 어떤건 자기 관할 해시링 구간의 크기가 작고, 어떤건 크다.
-
키의 균등 분포를 달성하기가 어렵다. (1번의 확장) 키가 균등분포 되더라도. 1번때문에 안된다.
서버가 균등하게 분포되더라도
가상 노드
일종의 링크파일느낌으로, 서버의 분신을 여럿 만들어서 해시 링위에 놓아서 1번문제를 해결한다.
재배치할 키 결정
그냥 그림으로 생각해보면 쉽게 이해 가능하다.
마치며
안정 해시의 이점
- 서버가 UPDATE 될 때 재배치 되는 키의 수가 감소한다.
- 데이터가 보다 균등하게 분포되므로 수평적 규모 확장성을 달성하기 쉽다.
- hotspot 키 문제를 줄인다.