[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 안정 해시

Intro

안정 해시는 수평적 확장을 고려할 때 각 서버에 균등하게 데이터를 나누기 위해 사용하는 방법.

해싱(Hashing)이란 무엇인가?

해싱이란 다양한 길이의 입력값들에 대해서 고정된 길이의 출력값을 생성해주는 과정을 뜻한다. 이 출력값을 우리는 해시값(hash value)라고 부른다. 그리고 이 과정을 수행하기 위해 진행하는 과정에 쓰이는 것을 해시 함수(hash function)이라고 한다.

원인

해시 키 재배치(refresh) 문제

- 총 4개의 서버

키	해시	서버
key0	18358617	1
key1	26143584	0
key2	18131146	2
key3	34085809	1
key4	35863496	0
key5	27581703	3
key6	38164978	2

 

- 총 3개의 서버(1개 서버 다운)

키	해시	서버
key0	18358617	0
key1	26143584	0
key2	18131146	1
key3	34085809	2
key4	35863496	1
key5	27581703	0
key6	38164978	1

• 위 예제처럼 해시 값을 서버의 개수로 모듈러 연산을 진행하는 해시 함수를 사용해 키가 저장된 서버의 위치를 특정 짓는다고 가정해보자.
• 그러면 1개의 서버가 다운될 경우 모듈러 연산을 하는 기준이 4개에서 3개로 변경되면서 각 키에 해당하는 서버 Index는 모두 꼬이게 된다.
• 결론은 대규모 cache miss가 발생하게 되고 특정 서버에 몰리게 되면 과부하가 걸리며 서비스는 혼돈에 빠질 것이다..

해결 방안

안정 해시(Consistent Hash)

💡 Wikipedia에서는 일관된 해싱이라는 명칭을 사용하고 있으며, 웹 서버의 개수가 변동하는 가운데 요청을 분산하는 방법이다. 특징은 모든 키를 재배치 해야하는 일반적인 해시 기술과는 다르게 K/n(K : key, n: Server)만 재배치 하면 된다.

• 작동 과정
  1. 해시 함수의 결과값에 대한 저장 공간 범위를 정한다. 이를 해시 공간(hash space)라 부른다.
  2. 이 공간을 해시 링으로 만든다.
  3. 모든 서버들을 해싱하고 동일하게 해시 링에 매핑 시킨다.
  4. 모든 키들도 3번과 동일하게 작업한다.
  5. 키들은 시계 방향으로 서버를 탐색한다.

Hash ring

HashRing

회색 글씨로 쓰인 점들을 Server가 매핑된 곳, 파란색 글씨로 쓰인 점들을 key값이라고 가정했을 때,

키	해시	서버
key-0	15000	1
key-1	25678	2
key-2	29536	2
key-3	33357	2
key-4	36458	3
key-5	39600	3
key-6	58765	0

위 표와 같이 서버에 key 값이 분배되는 것을 확인할 수 있다.

HashRing Server Down

• 위 그림과 차이점은 S3 서버가 다운되어 없어졌다는 점이다. - hash ring을 사용한 안정 해시에서는 S2부터 S0까지의 키 값들만 재배치를 하면 된다.

키	해시	서버
key-0	15000	1
key-1	25678	2
key-2	29536	2
key-3	33357	2
key-4	36458	0
key-5	39600	0
key-6	58765	0

• key-4와 key-5만 재배치가 완료되자 정상적으로 배정이 된 것을 확인할 수 있다.

안정 해시 문제점과 해결 방안

문제점

1. 파티션 크기의 균등 유지
   • 서버가 삭제되거나 추가됐을 때 키의 재분배를 빠르게 처리가 가능하다는 장점이 있지만 해시 링 내에서 각 서버에 할당되는 해시 공간의 크기가 일정하지 않다는 문제점이 발생한다.
   • 그림을 참고하면 S3 서버가 삭제되면서 S2와 S0 서버 사이의 해시 공간의 범위가 늘어난 것을 확인할 수 있다.
2. 균등 분포의 문제점
   • 위 그림 예시처럼 하나의 서버에 많은 키값이 저장될 수 있는 것에 더해서 특정 서버에는 어떠한 키값도 저장되지 않는 문제점이 발생할 수도 있다.

해결 방안

• 가상 노드(virtual node)의 활용
  • 가상 노드를 각 서버마다 n개 생성해서 각 서버를 가르키도록 설정하고 해시 링 내에 매핑 시킨다.
  • 키 값들은 시계 방향 탐색을 진행하며 가상 노드를 마주칠 경우 해당 서버에 키 값을 저장시킨다.
• 특징
  • 가상 노드의 개수가 많아질 수록 키의 분포는 더욱 균등해진다.
  • 하지만, 가상 노드의 개수가 많아질 수록 해당 가상 노드의 데이터를 저장할 공간 또한 필요하므로 메모리 쪽 효율은 떨어질 수 밖에 없음에 주의하자.

마무리

안정 해시가 필요한 이유는 핫스팟(hotspot) 키 문제를 줄일 수 있다는 점이다. 데이터베이스 내 특정 샤드에 접근이 지나치게 많이 이루어진다면 과부하가 발생할 수 밖에 없기 때문에 해당 문제점을 해결하는데 탁월하다.