서버 아키텍처 - 해시와 안정 해시

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

 

1. 해시(hash)란?

 해시 알고리즘은 어떠한 데이터 입력해도 고정된 길이의 결과를 출력한다. 즉, 데이터를 입력하고 고정된 길이로 결과를 출력한다면 모두 해시 함수라 한다.

 

 해시 알고리즘의 종류로 SHA(0, 1, 224, 256, 384, 512), MD(4, 5) 등이 있다. 암호화의 한 종류로 단방향 암호화기법이다. 암호화에도 사용되지만, 해싱을 통해 더 빠르게 데이터를 접근할 때 사용하기도 한다. 해시는  평문에서 암호문으로 변환하는 과정은 쉽게 가능하지만, 암호문에서 평문으로 되돌리는 과정은 어렵다는 특징이 있다.

 

2. 해시키 재배치(rehash) 문제

 N개의 캐시 서버가 있다. 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것이다.

serverIndex = hash(key) % N

 

 간단하게 4대의 서버가 있고 key 0~7이 있다. 그리고 key를 입력하면, 8자리 정수를 만들어주는 해시 함수가 있다.

키	해시	해시 % 4
key0	18358617	1
key1	26143584	0
key2	18131146	2
key3	35863496	0
key4	34085809	1
key5	27581703	3
key6	38164978	2
key7	22530351	3

 

 server0에는 key1, key3이 server1에는 key0, key4가 server2에는 key2, key6이 server3에는 key5, key7로 서버에 접근이 된다.

 

 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다. server1에 장애가 생긴다고 가정해보자.

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

server0에는 key0, key1, key5, key7이 server2에는 key2, key4, key6이 server3에는 key3으로 서버에 접근이 된다. 1번 서버가 죽으면 대부분 캐시 클라이언트는 데이터가 없는 엉뚱한 서버에 접속하여 데이터를 가져오게 된다.

 

※ 개인적인 생각 : 책을 읽으면서 사용자의 트래픽을 관리하기 위한 무상태성 서버의 로드밸런싱과 데이터 접근을 위한 로드밸런싱을 구분해서 이해할 수 있을것 같다. "서버들에 부하를 균등하게 나누는 보편적 방법"으로 로드밸런싱을 생각하고 읽으니, 이해가 되지 않았는데, 각 server별로 저장된 데이터가 다르기 때문에 접근한다는 개념으로 읽으면 이해가 된다. 

 

3. SHA-1

 최대 64비트 길이의 입력 데이터를 160비트의 출력데이터(해시값)으로 변경하는 알고리즘이다. 인터넷 보안 프로토골과 공개키 인증서에도 적용되고 있는 중요한 암호 알고리즘이다.

 

4. 안정 해시(consistent hash) 기본 구현

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

 

해시 함수로 SHA-1을 사용한다고 하면, 해시 공간의 범위는 0 ~ 2^160-1 이다. 함수의 출력값은 x0~xn이라 한다.

해시 공간

해시 공간을 구부려 접으면 해시 링이 된다.

해시 링 - 1

해시링에 key와 server 배치, 해시 링 - 2

안정 해시 공간 어디라도 key와 server를 고르게 분포하고, 시계방향으로 server를 접근한다고 설정한다.

• 서버 삭제 시 키 하나가 접근하는 서버의 위치만 변경된다.

해시 링 - 3

• 서버 추가 시 키 하나가 접근하는 서버의 위치만 변경된다.

해시 링 - 4

 

5. 안정 해시(consistent hash) 가상 노드

4.의 안정해시 기본 구현에 문제점은 두 가지다. 첫 번째, 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(키와 서버의 거리 공간)의 크기를 균등하게 유지하는 게 불가능하다. 두 번째, 키의 균등 분포(해시 링 - 3)를 달성하기 어렵다(하나의 서버에만 여러 키가 입력).

 

이 문제를 해결하기 위해 실제 서버와 연결되는 가상 노드를 만든다. 가상 노드가 많을 수록 데이터를 고르게 분포할 수 있다.

안정 해시 가상 노드

 

6. 안정 해시의 정리

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수 최소화.
• 데이터가 보다 균등하게 분포되므로 수평적 규모의 확장성을 달성하기 쉬움.
• 핫스팟(hotspot) 키 문제를 줄임.

 

7.  실례

• 아마존 다이나모 DB의 파티셔닝
• 아파치 카산드라 클러스터의 데이터 파티셔닝

 

정확하게 이것만 보고 안정해시를 어떻게 구현할지는 알 수 없지만, 많이 사용되는 실례에서 이런 방식을 사용한다고 하니, 추후에 사용할 때 도움이 되지 않을까 싶다.

 

 

 

참고자료:

• 가상면접 사례로 배우는 대규모 시스템 설계 기초
• chatGpt
• https://angangmoddi.tistory.com/m/289