[대규모 시스템 설계 기초] 5장. 안정 해시 설계

🌱 들어가기 전

이번 포스팅에서는 수평적 규모 확장성을 위한 안정 해시 설계에 대해 알아보자.

---

 

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

안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

🌱 해시 키 재배치(rehash) 문제

N개의 서버가 있다고 하자. 이 서버들에 부하를 균등하게 나누기 위해 보통 아래의 해시 함수를 사용한다.

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

💭 이 방법이 잘 동작하는 조건

- 서버 풀이 고정되어 있을 때

- 데이터 분포가 균등할 때

 

💭 문제가 생기는 상황

- 서버가 추가되거나 기존 서버가 삭제될 때

 

ex) 서버가 4개 있었는데, 1번 서버가 장애를 일으켜 동작을 중단했다고 하자.

서버 풀의 크기가 3으로 변한다. 그 결과, 키에 대한 해시 값은 변하지 않지만 나머지(%) 연산을 적용하면 계산한 서버 인덱스 값이 달라진다. 

 

문제는 장애가 발생한 1번 서버에 보관되어 있는 키 뿐만 아닌 대부분의 키가 재분배되는 것이다. 

즉, 1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다. 그 결과 대규모 캐시미스가 발생하게 될 것이다. 

 

안정해시는 이 문제를 효과적으로 해결하는 기술이다. 

 

 🌱안정 해시

안정 해시 = 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다.  (k = 키의 개수, n = 슬롯(slot)의 개수)

 

🤔 '해시 테이블의 크기가 조정될 때' 라는 말은 어떤 의미인가?

💡 안정 해시에서 말하는 '해시 테이블'은 전통적인 의미의 해시 테이블과는 약간 다르게 사용된다. 여기서 해시 테이블은 데이터(키)를 여러 노드나 서버에 분산하여 저장하기 위한 논리적 구조를 의미한다. 이 구조는 일반적으로 원형 링 형태로 표현되며, 각 노드와 키는 동일한 해시 함수를 통해 이 링 위의 특정 위치에 매핑된다. 

"해시 테이블의 크기가 조정될 때"라는 것은 해시 테이블 전체 크기가 아니라, 각 노드가 차지하고 있는 해시 테이블의 범위나 크기가 조정되는 것을 의미한다.

 

💭 해시 공간과 해시 링

해시 함수의 출력 값 범위(해시 공간 범위)는 x0, x1, x2, ... , xn-1, xn과 같다고 하자. 

 

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

hash ring

💭 해시 서버

해시 함수 f를 사용하면 서버 IP나 이름을 이 링 위의 어떤 위치에 대응시킬 수 있다.

 

예를 들어, 4개의 서버를 이 해시 링 위에 배치하면 아래와 같다.

 

💭 해시 키

여기서 사용된 해시 함수는 앞서 본 '해시 키 재배치 문제'에 언급된 함수와는 다르며, 나머지 연산도 사용하지 않고 있음에 유의하자.

 

캐시할 키 key0, key1, key2, key3 또한 해시 링 위의 어느 지점에 배치할 수 있다.

🤔 캐시할 키란 무엇인?

💡 일반적으로 분산 시스템에서 저장하고자 하는 데이터의 식별자를 의미한다.

💭 서버 조회

어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.

💭 서버 추가

방금 설명한 내용에 따르면 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.

 

새로운 서버 4가 추가되면, key0만 재배치됨을 알 수 있다. key0의 위치에서 시계 방향으로 순회했을 때 처음으로 만나게 되는 서버가 서버 4이기 때문이다. 다른 키들은 재배치되지 않는다.

 

💭 서버 제거

하나의 서버가 제거되면 키 가운데 일부만 재배치된다.

서버 1이 삭제됐을 때 key1만이 서버 2로 재배치됨을 알 수 있다. 나머지 키에는 영향이 없다.

 

💭 기본 구현법의 두 가지 문제

안정 해시 알고리즘의 기본 절차

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

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

 

이 접근법의 두 가지 문제

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

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

어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능하다.

 

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

 

해결 기법

이 문제를 해결하기 위해 제안된 기법이 가상 노드 (또는 복제) 기법이다.

 

💭 가상 노드

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

 

서버 0을 링에 배치하기 위해 s0 하나만 쓰는 대신, s0.0, s0.1, s0.2의 세 개의 가상 노드를 사용하였다. 따라서 각 서버는 하나가 아닌 여러 개의 파티션을 관리해야 한다. s0으로 표시된 파티션은 서버 0이 관리하는 파티션이다.

(세 개는 임의로 정한 것이며, 실제 시스템에서는 그보다 훨씬큰 값이 사용된다.)

 

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

 

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다. 표준편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도다.

가상 노드의 개수를 더 늘리면 표준 편차의 값은 더 떨어지지만, 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 된다. 타협적 결정(tradeoff)이 필요하다는 뜻이다.

 

💭 재배치할 키 결정

서버가 추가되거나 제거되면, 어느 범위의 키들이 재배치되어야 할까?

서버 4가 추가되었다고 해 보자. 이에 영향 받은 범위는 새로 추가된 노드(s4)부터 그 반시계 방향에 있는 첫 번째 서버(s3)까지이다.

즉, s3부터 s4사이에 있는 키들을 s4로 재배치하여야 한다.

 

삭제되면 어떨까?

 

서버 1이 삭제되었다고 해 보자. 삭제된 노드(s1)부터 그 반시계 방향에 있는 최초 서버 (s0) 사이에 있는 키들이 재배치되어야 한다.

 

🌱 마치며

안정 해시의 이점

- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.

- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.

- 핫스팟 키 문제를 줄인다. 특정 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄인다.