ch05 대규모 시스템 설계 기초

5장 안정 해시 설계

N개의 캐시 서버가 있다고 할 때, 이 서버들에 부하를 균등하게 나누는 보편적인 방법은 아래와 같은 해시함수를 사용하는 것이다.

serverIndex = hash(key) % N

4대의 서버를 사용한다고 할 때, 각각의 키에 대해서 해시 값과 서버 인덱스를 계산

특정한 키가 보관된 서버를 알아내기 위해, 나머지 연산을 key % 4 와 같이 적용

ex) hash % 4 = 1이면, 서버 1에 접속하여 데이터를 가져옴

Figure 5-1 은 키 값이 서버에 어떻게 분산되었는지 보여준다.

서버 풀의 개수가 고정되어 있을 때, 부하를 균등하게 나눌 수 있다.

서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.

만약 한 서버에 이상이 발생하여 서버 풀의 개수가 줄어들거나, 트래픽이 몰려서 서버 풀의 개수를 늘려야 한다면?

1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다

해당 서버에 존재하던 해시키가 사라지고, 엉뚱한 서버로 접근하게 되어 대규모 캐시 미스가 발생하게 된다.

캐시 미스 문제를 방지하기 위해 해결하기 위한 기술로써, 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술이다.

k : 키의 개수 n : 슬롯의 개수

해시 공간의 양쪽을 구부려 접으면 아래와 같은 해시 링이 만들어진다.

해시함수f (해시 재배치 문제의 함수와 다른 함수)를 사용하여 서버를 링 위에 어떤 위치에 대응 시킬 수 있음
캐시할 키도 링 위에 어느 지점에 배치할 수 있음
키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.
- key0은 s0에 저장
- key1은 s1에 저장
- key2는 s2에 저장
- key3은 s3에 저장

s4가 추가되기 전, k0은 s0에 저장되어 있었다. 하지만 s4가 추가되면 시계 방향으로 순회했을 때 처음으로 만나게 되는 서버가 s4이기 때문에 s4에 저장된다. 다른키들은 재배치 되지 않는다.

s1이 삭제되었을 때 key1만이 s2로 재배치됨 나머지 키에는 영향이 없다.

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

가상 노드의 개수를 늘리면 표준 편차가 작아져서 키의 분포도는 점점 균등해진다.

100~200개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 5% (가상 노드가 200개인 경우)에서 10%(가상 노드가 100개인 경우) 사이다.

가상 노드의 수를 더 늘리면 표준 편차의 값은 더 떨어지지만 가상 노드 데이터를 저장할 공간이 더 많이 필요해지게 된다.

결론 : 타협이 필요하다. 시스템 요구사항에 맞게 적절한 가상 노드 개수를 조정해야 한다.

서버가 추가, 제거되면 데이터 일부를 재배치하게 된다.

안정 해시의 이점

서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
핫스팟 키 문제를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 발생
- 유명인의 데이터가 몰리는 상황을 상상해보자
- 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄인다.

쓰이고 있는 기술들