5장. 안정 해시 설계

nowwater 2023. 8. 3. 19:58

728x90

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.

해시 키 재배치(rehash) 문제

서버들에 부하를 균등하게 나누는 보편적 방법은 해시 함수를 사용하는 것이다.

serverIndex = hash(key) % N (N 은 서버의 개수)

서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다.

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

키에 대한 해시 값은 변하지 않지만 나머지 연산을 적용하여 계산한 서버 인덱스 값은 달라지게 된다.

특정 서버(그림에서는 서버 1)가 죽게 되면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하여 대규모 캐시 미스가 발생하게 된다. 이러한 문제를 효과적으로 해결하는 기술이 바로 안정 해시이다.

해시 테이블 크기가 조정될 때 평균적으로 오직 K/N 개의 키만 재배치하는 해시 기술.

1. 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.

2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.

해시 함수 f 로 SHA-1 을 사용한다고 했을 때, 그 함수의 해시 공간 범위는 0부터 2^160 - 1 까지이다.

이 해시 공간을 그림으로 표시하면 다음과 같이 나타난다.

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

해시 함수 f 를 사용하여 서버를 링 위의 특정 지점에 대응 시킬 수 있으며, 캐시할 키 또한 해시 링 위에 대응 시킬 수 있다.

이후 특정 키의 위치로부터 시계 방향으로 링을 탐색하면서 첫 번째로 만나는 서버에 해당 키 값이 저장되므로, 조회할 때도 마찬가지 방식으로 데이터가 저장된 서버를 찾을 수 있다.

이때 만약 새로운 서버가 추가되거나 제거된다 하더라도, 키 가운데 일부만 재배치하면 된다.

1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티선의 크기를 균등하게 유지하는 게 불가능하다.

- 파티션: 인접한 서버 사이의 해시 공간

2. 키의 균등 분포를 달성하기가 어렵다

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

서버를 가상 노드로 분리하여 해시 링 위에 배치하게 되면서 각 서버는 하나가 아닌 여러 개의 파티션을 관리해야 한다.

마찬가지로 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버이다.

가상 노드의 개수를 늘리면 표준 편차가 작아져서 데이터가 고르게 분포되므로 키의 분포가 점점 더 균등해진다.

그러나 가상 노드 데이터를 저장할 공간이 더 많이 필요하게 되어 타협적 결정(Trade-off) 이 필요한 상황이 된다.

따라서 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야 한다.

새로 추가되거나 삭제되는 서버 노드로부터 반시계 방향으로 첫 번째 서버 노드가 있는 범위의 키들이 재배치되어야 한다.

서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
데이터를 균등하게 분배하기에 핫스팟 키 문제를 해결해준다.
- 핫스팟 키: 특정 샤드에 대한 접근이 지나치게 빈번하게 이루어져 서버 과부하에 문제를 일으키는 상황