대규모 시스템 설계 공부 005

수평적 규모 확장을 의해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
요청 또는 데이터를 균등하기 나누기 위해 보편적으로 사용하는 기술이 안정 해시이다.
이 해시 기술이 풀려고 하는 문제부터 좀 더 자세히 알아본다.

해시 키 재배치(rehash) 문제

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

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

예를 들어 4개의 서버를 사용한다고 할 때 주어진 각각의 키에 대해 해시 값과 서버 인덱스를 계산하면

이렇게 나온다.

특정 키가 보관된 서버를 알아내기 위해 나머지연산을 f(key)A%4와 같이 적용했다.
예를 들어 hash(key0)%4=1 이면 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속해야 한다.

이런 식으로 서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때에는 잘 동작한다.
그런데 만약에 서버가 추가되거나 삭제된다면?

예를 들어 1번 서버가 장애가 나서 동작이 동작되면, 서버 풀의 크기는 3으로 변환다.
그러면 해시 값은 변하지 않지만 (%)연산을 적용해서 얻은 인덱스 값이 변하게 될 것이다.

이런 식으로 나머지연산 할 때에 값이 달라지고, 키 분포가 변화되게 된다.

위의 그림처럼, 장애가 발생한 1번 서버에 보관되어 있는 키뿐 아니라, 대부분의 키가 재분배되었다.
즉, 1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다는 뜻이다.
그 결과로 대규모 캐시미스(cache miss)가 발생하게 될 것이다.

안정 해시

안정 해시는 위의 문제를 해결하는 데에 도움을 준다.
안정 해시란 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다.
여기서 k는 키의 개수이고, n은 슬롯의 개수이다.

이와 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다.

해시 공간과 해시 링

이제 안정 해시의 동작 원리를 알아본다.
해시 함수 f로는 SHA-1을 사용한다고 하고, 그 함수의 출력 값 범위는 x0, x1, x2, x3, ... xn과 같다고 한다.
SHA-1의 해시 공간(hash space)범위는 0 ~ 2^160 - 1까지라고 알려져 있다..
따라서 x0은 0, xn은 2^160 - 1이며, 나머지 x1부터 xn-1까지는 그 사이의 값을 갖게 된다.

이 해시 공간의 양쪽을 구부려 접으면

이런 해시 링이 만들어진다.

해시 서버

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

해시 키

해시 링 위에 4개의 서버를 배치한다.

캐시할 키 key0 ~ key3을 링 위의 어느 지점에 배치한다.
해당 방식은 너머지 연산을 사용하고 있지 않다.

서버 조회

어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.
key0 -> 서버0 , k1 -> 서버1 ,.... 이런 식으로 저장되게 된다.

서버 추가

위의 내용에 따르면, 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.

여기서 확인해 보면, 새로운 서버 4가 추가된 후에 key0만 재배치된다.
k1, k2, k3는 같은 서버에 남는다.

1. 서버 4가 추가되기 전, key0은 서버 0에 저장되어 있었다.
2. 서버 4가 추가된 뒤에 key0은 서버 4에 저장될 것인데, key0의 위치에서 시계 방향으로 순회했을 때 처음으로 만나는 서버가 서버4이기 때문이다.
3. 다른 키들은 재배치되지 않는다.

서버 제거

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

서버1이 삭제되었을 때 key1만이 서버2로 재배치된다.
다른 키에는 영향이 없다.

기본 구현법의 두 가지 문제

안정 해시 알고리즘 절차는 다음과 같다.

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

이 접근법에는 두 가지 문제가 있다.

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

파티션은 인접한 서버 사이의 해시 공간이다.
어떤 서버는 굉장히 작은 해시 공간을 할당받고, 어떤 서버는 굉장히 큰 공간을 할당 받는 상황이 가능하다.

여기서 s1이 삭제되는 바람에 s2의 파티션이 다른 파티션 대비 거의 두 배 커지는 상황이 보여진다.

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

여기서 서버1과 서버3은 아무 데이터도 갖지 않는 반면, 대부분의 키는 서버2에 보관될 것이다.

가상 노드

위의 문제를 해결하기 위해 제안된 기법이며, 가상 노드 혹은 복제라 불린다.
가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

여기서 서버 0과 서버 1은 3개의 가상 노드를 갖는다.
숫자 3은 임의로 정해진 것이며 실제 시스템에서는 이보다 훨씬 큰 값이 사용된다.
서버 0을 링에 배치하기 위해 s0하나만 쓰는 대신, s1_0, s1_1, s1_2세개 가상 노드를 사용했다.
각 서버는 따라서 하나가 아닌 여러 개의 파티션을 관리하여야 한다.
s0으로 표시된 파티션은 서버0이, s1은 서버1이 관리하는 식으로이다.

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

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

표준 편차는 데이터가 어떻게 퍼져 나갔는지 보여주는 척도이다.
100~200개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 5%(가상노드가 200개인 경우) 에서 10%(가상 노드가 100개인 경우)의 사이이다.
가상 노드의 개수를 더 늘리면 표준 편차의 값은 더 떨어진다.
그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다.

즉 tradeoff가 필요하다는 것이다.
그러니 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야 할 것이다.

재배치할 키 결정

서버가 추가되거나 제거되면 데이터 중 일부는 재배치하여야 한다.
어느 범위의 키들이 재배치되어야 할까??

이런 식으로 서버4가 추가되었다고 해 보자
이에 영향받은 범위는 s4부터 그 반시계 방향에 있는 서버 s3까지이다.
즉 s3부터 s4사이의 키들을 s4로 재배치해야 한다.

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

정리

안정 해시가 왜 필요하며 어떻게 동작하는지를 알아보았다.
안정 해시의 이점은 다음과 같다.

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