안정 해시 설계

[가상 면접 사례로 배우는 대규모 시스템 설계]를 읽고 작성하는 포스트 입니다. 

틀린 내용이 있을 수도 있습니다! 

틀린 내용이 있다면 댓글로 달아주시면 감사하겠습니다!

 

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

이번 포스팅에서는 수평적 규모 확장성 구조에 왜 안정해시 설계가 필요한지에 대해서 작성한다.  

 

우선 안정 해시 설계에 대해서 알아보기전에, 어떤 문제를 풀려고 하는지에 대해서부터 알아보자. 

다음 문제에 주목하자. 

 

해시 키 재배치(rehash) 문제

4개의 캐시 서버가 있다고 가정하자.

보편적으로 데이터를 4개의 캐시 서버에 고루 배정할 때 다음과 같은 해시 함수를 사용할 수 있다. 

serverIndex = hash(key) % 4

 

예를 들어 hash(key0) % 4 = 1일 때,

클라이언트는 캐시에 보관된 데이터(key0과 관련된)를 가져오기 위해 서버 1에 접속해야 한다. 

 

이 방식은 캐시서버 4개일 때, 즉 서버 풀이 고정되어 있을 때는 잘 동작한다. 

하지만, 서버 풀에서 서버가 추가되거나 삭제되면 문제가 생긴다. 

 

위 예시에서 이어서 서버1이 죽었다고 하자.

서버 풀은 3이 되고, hash(key0) % 3 = 2가 되어 기존에 저장되었던 key0을 서버2에서 찾게 되는 문제가 발생할 수 있다. 

정작 key0과 관련된 데이터는 서버1에 저장되어 있는데 말이다...

 

즉, 서버 풀이 변하는 것과 상관 없이, 안정적으로 데이터를 저장하고 조회할 수 있도록 만들고 싶은 것이다! 

그래서 우리는 안정 해시 설계를 공부한다.  

 

안정해시 설계

안정 해시 설계는 n 개의 서버와 k개 의 key가 있을 때, 해시 테이블의 크기가 변함에도 불구하고 각 서버에 k/n개의 key를 평균적으로 재배치하는 기술이다.    

위에서 보았던 해시 키 재배치 문제처럼 일반적인 방식의 해시 테이블은 slot의 갯수가 변하면 대부분의 key를 재배치한다. 

 

그렇다면 어떻게 안정해시 설계를 통해서 키를 최소한으로 재배치하여 설계할 수 있을까

 

어떤 해시함수를 이용해서 출력값이 x0부터 xn까지 나왔다고 하자.

이 때 해시 공간은 다음과 같다. 

 

[ x0, x1, x2... , xn-2, xn-1, xn ] 

 

그리고 x0과 xn을 연결하여 링 모양의 해시 링(hash ring)을 만들 수 있다. 

다음과 같이, 해시 함수 f를 사용해서 서버 IP나 이름을 링 위에 대응시킬 수 있다.

 

 key 또한 해시함수 f를  통해서 해시 링 위의 어떤 지점에 배치할 수 있다.

 

그렇다면 key는 어떤 서버와 매칭될까 

key와 server를 매칭할 때는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫번째 서버가 해당 key와 매칭되는 서버다. 

 

서버가 추가되는 경우

서버가 추가될 때, 키 일부만 재배치하면 된다.

다음과 같이 server5가 추가될 때, server2를 가르키던 key2는 server5를 가르키게 된다. 

 

서버가 삭제되는 경우

서버가 삭제될 때, 키 일부만 재배치하면 된다.

다음과 같이 server2가 삭제될 때, server2를 가르키던 key2는 server3을 가르키게 된다. 

 

안정해시 설계의 문제점

하지만 이러한 안정해시 설계 방식에도 문제가 있다.

 

첫번째는 서버가 추가되거나 삭제될때 파티션의 크기를 균등하게 유지할 수 없다는 것이다. 

참고로 파티션이란 서버와 서버 사이의 해시 공간의 크기다. 

 

두번째는 키를 균등하게 분포시키기 어렵다는 것이다. 

 

다음과 같은 구조에서 server0은 key2~key6, server1은 key1을 갖게 되면서 키 분포에 문제가 생긴다. 

 

가상 노드(Virtual node)

그래서 이러한 문제를 해결하기 위해 가상 노드(virtual node)라는 기법을 사용한다.   

가상 노드 기법이란 하나의 서버는 링 위에서 여러 개의 가상노드를 가질 수 있도록 하는 것이다.

    

지금까지 server0을 배치하는데 하나의 노드만 사용했다면,

가상 노드를 이용하게 되면 server0을 배치하는데 server0_0, server0_1, server0_2을 이용해서 배치시킬 수 있다. 

 

다음은 서버 하나에 가상 노드 2개를 매핑시킨 것이다. 

 

만약 key2가 server0_1에 해당된다면, key2는 server0에 저장되고,

만약 key0가 server0_0에 해당된다면, key0는 server0에 저장된다. 

 

위와 같이 가상 노드를 두어 키 분포 문제를 해결할 수 있다.

 

이렇게 가상노드의 개수를 늘려 키의 분포는 균등하게 만들 수 있다.

(참고로 가상 노드의 개수를 늘리면 표준편차 값이 작아지면서 데이터를 골고루 분포시킬 수 있다) 

하지만 가상 노드의 개수를 늘리는 것은 반대로 가상노드를 저장할 공간을 쓴다는 것을 의미하기 때문에 이는 타협적 결정이 필요하다. 

 

정리해보자. 

 

안정해시를 사용하면 다음과 같은 이점을 얻을 수 있다.

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화 된다.
• 데이터를 균등하게 배분할 수 있기 때문에 수평적 확장 구조에 적합하다. 
• 유명인사 문제(hotspot key) 문제를 해결할 수 있다.