안정 해시 설계

👉 안정 해시 설계

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다. 

 

해시 키 재배치란?

장애가 발생한 1번 서버에 보관되어 있는 키 뿐만 아닌 대부분의 키가 재분배되었다. 1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다는 뜻이다. 이러한 문제를 해결하기 위해 안정 해시 기술이다.

 

 

해시 공간과 해시 링

해시 공간(hash space)은 해시 함수f로는 SHA-1을 사용한다고 하고, 그 함수의 출력 값 범위는 x0 부터 xn까지 사이의 값을 갖게 될 것이다.

 

해시 링(hash ring)은 해시 공간의 양쪽을 구부려 접으면 밑에 동그랍게 만들어진다.

 

해시 서버

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

해시  키

여기 사용된 해시 함수는 "해시 키 재배치 문제"에 언급된 함수와는 다르며, 나머지(modular) 연산 %는 사용하지 않는다.

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

 

서버 조회

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

key0은 서버0에 저장되고, key1은 서버 1에 저장되며, key2는 서버 2, key3은 서버3에 저장된다.

서버  추가

서버 4가 추가되기 전에 key0은 서버 0에 저장되어 있었다. 하지만 서버 4가 추가된 뒤에 key0은 서버 4에 저장된다. 왜냐하면 key0의 위치에서 시계 방향으로 순회 했을 때 처음으로 만나게 되는 서버가 서버4이기 때문이다. 다른 키들은 재배치되지 않는다.

서버 제거

하나의 서버가 제거되면 키 가운데 일부만 재배치된다. 서버 1이 삭제되었을때 기존에 key1이 서버 2로 재배치됨을 알 수 있다. 나머지 키에는 영향이 없다.

 

기본 구현법의 두 가지 문제

• 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치한다.
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키카 저장될 서버다.

파티션(partition)의 크기가 균등하게 유지하는게 불가능하므로 하나의 서버의 공간이 여러개 서버의 공간으로 분할하여 

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

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

 

가상노드

 

• 가상 노드(virtual node)는 실제 노드 또는 서버를 가리키는 노드로서 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
• 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 한다.

• 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.
• k0가  저장되는 서버는 k0의 위치로부터 링을 시계방향으로 탐색하다 만나는 최초의 가상 노드 s1_1가 나타내는 서버, 즉 서버 1이다.

재배치 할 키 결정

• 서버가 추가되거난 제거되면 데이터 일부는 재배치해야한다. 
• 서버가 추가되면 (새로 추가된 노드) 부터 그 반시계 방향에 있는 첫 번째 서버 s3까지이다.