가상 면접 사례로 배우는... : 안정 해시 설계

5장. 안정 해시 설계 

수평적 규모 확장성을 달성하기 위해서 요청 / 데이터를 서버에 균등하게 분포하는 것은 중요한 일이다. 이 작업은 '안정 해시'로 구현될 수 있다. 

---

해시 키 재배치(Rehash) 문제

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

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

이 방법으로 해시키를 분배할 경우 초기에는 균등히 분배되지만, 서버가 추가/삭제 되었을 때 많은 해시 키가 재배치 된다. 4대의 서버가 3대의 서버로 줄었을 때를 가정하면 아래 결과를 볼 수 있다. 

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

서버 1대가 죽으면서, 전체 키 중 75%(6/8)이 재배치 된다. 동일한 요청이 여러 번 왔을 때, 75%의 요청이 캐시 미스를 경험하게 될 것이다. 만약 캐시 서버가 DB로부터 데이터를 읽어와서 저장하고 클라이언트에게 응답해주는 구조라고 한다면 캐시 서버 1대에 장애가 발생했을 때, 장애가 DB로 전파될 수 있음을 의미한다. 

 

---

안정 해시

안정 해시는 해시 테이블의 크기가 조정되더라도 평균적으로 k/n개의 키만 재배치하는 해시 기술이다. 여기서 k는 Key의 갯수, n은 해시 슬랏의 개수다. 

 

---

해시 공간과 해시 링

해시 함수로 SHA-1을 사용하고, 출력값은 x0 ~ xn까지의 범위를 가질 수 있다고 가정하자. SHA-1의 해시 공간은 (2^160) -1이다. 따라서 다음 조건이 확정되는 것을 알 수 있다.

• X0 : 0
• Xn : (2^160) - 1

SHA-1이 가지는 해시 공간을 그림으로 표현하면 다음과 같다. 각 슬랏은 SHA-1로 표현할 수 있는 해시 값들을 의미하고, 값이 저장될 수 있는 공간을 슬랏이라고 한다.

해시공간

개념적으로 해시 공간은 하나의 선으로 표현되지만, 이 선을 원으로 만들어서 사용할 수 있다. 이것을 해시 링이라고 한다.

해시 링

 

---

해시 서버

해시 서버의 이름으로 해시 값으로 만들 수 있다. 아래 그림처럼 해시 값에 해당되는 해시 슬랏에 해시 서버를 배치한다고 가정하자.  

예를 들면 다음 코드를 이용해서 특정 해시 함수로 서버의 이름을 해시 키값으로 바꿀 수 있다. 

final MD5HashAlgorithm instance = new MD5HashAlgorithm();
final String serverName = getServerName();
final long hash = instance.getHash(serverName);

 

---

해시 키

해시 서버의 이름을 해시 값으로 위에서 바꿨다. 동일한 방법으로 Key 값을 해시 값으로 바꿔서 해시 슬랏에 배치 할 수도 있다. 예를 들면 아래 코드처럼 실행할 수 있다. 

final MD5HashAlgorithm instance = new MD5HashAlgorithm();
final String key = getKey();
final long hash = instance.getHash(key);

해시 키 값을 해시 슬랏에 배치한 그림은 아래에서 볼 수 있다. 

 

---

서버 조회

특정 해시 키 값이 어떤 서버에 저장되어야 하는지는 간단하다. 해시 키 값이 위치한 슬랏에서 시계 방향으로 움직여 처음으로 만나는 노드를 찾으면 된다. 예를 들면 파란색 해시 키들은 s1 서버에 저장될 것이고, 초록색 해시 키들은 s3 서버에 저장될 것이다. 

 

---

서버 추가

전통적인 해시 함수는 서버가 추가 / 삭제 될 때 많은 해시 키가 재배열되어서 캐시 미스를 유발했다. 안정해시에서는 서버를 추가하더라도 해시 키 재배열을 최소화한다. 아래 그림처럼 S5 서버가 하나 더 추가되었을 때 재배열되는 키는 1개다. (S2 ~ S5 사이의 해시 슬랏에 속한 키)

 

---

기본 구현법의 두 가지 문제

안정해시의 기본 개념은 다음 두 가지다.

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

그런데 위의 설계만으로는 해결해야 할 문제가 두 가지 남아있다.

• 서버가 추가 / 삭제 될 때 서버 사이의 해시 간격이 균등하지 않다. 
• 키의 균등 분포를 달성하기 어렵다. (핫 스팟 키 문제)

아래 그림은 위의 단점을 시각화 한 것이다. 왼쪽 그림은 각 서버 간의 해시 공간 간격이 일정하지 않은 경우를 보여준다. 오른쪽 그림은 해시 키가 균등하게 분포되어 있지 않아, 특정 서버(s3)이 현재 해시 키 값을 다 가지고 있음을 의미한다.

---

가상 노드

위 두 가지 문제점을 해결하기 위해 '가상 노드'라는 개념이 추가되었다. 실제 서버는 여러 가상 노드를 가질 수 있고, 가상 노드는 해시 슬랏에 배치된다. 여기서 가상 노드는 실제 머신이 될 수도 있으며, 개념적인 노드가 될 수 있다. 나는 이것을 개념적으로 이해하고 구현했다.

• 노드 이름 : S1
• 가상 노드 이름 : S1_1, S1_2, S1_3

이제 해시 링에는 노드 이름이 아니라, 가상 노드 이름이 배치된다. 현재는 노드 마다 가상 노드의 갯수가 4개이기 때문에 아래 그림처럼 표시되었다. 이 때 가상 노드의 갯수가 충분히 많아지는 경우를 생각해보자.

• '적분'의 개념처럼 가상 노드의 군집은 해시 링 전체를 표현하게 됨. 
• 각 서버마다 전체 구간을 균등하게 표현하게 됨. (특정 서버는 특정 영역만 표현하는게 아니라) 

100 ~ 200개의 가상 노드를 사용했을 때, 키의 분포에 대한 표준 편차 값은 평균의 5% ~ 10%에 가깝다고 한다. 가상 노드가 더 많아지면 표준 편차 값은 줄어들겠지만, 가상 노드 데이터를 저정할 메모리 공간이 더 많이 필요하게 될 것이다. 따라서 이 부분은 트레이드 오프로 고려해야 할 부분이다. 

 

---

안정 해시 vs 일반 해시 실험치 비교 

코드, 테스트 환경, 테스트 코드를 작성해서 안정 해시와 일반 해시를 비교했다. 관련 코드는 이곳에 있다. 테스트 환경은 다음과 같다. 

1. Docker-Compose 환경에서 서버 1 ~ 5번을 띄운 후, 1번이 죽는 시나리오.
2. 각 서버는 Redis에게 자신의 헬스를 체크함. 
3. 테스트 코드에서 각 서버에 요청을 보내기 전에, Redis를 통해 서버 상태를 확인한 후 라우팅 함. 
4. 테스트 코드는 매 테스트 케이스마다 1 ~ 10000의 값을 Key로 순서대로 보냄. (1만번 요청함)

테스트를 통해서 확인하고자 한 부분은 다음과 같다. 

• 안정 해시 vs 일반 해시의 키 재배치 개수 확인. 
• 안정 해시의 가상 노드 개수 증가 시, 키의 균등분포 확인 

 

안정해시 테스트 결과

Virtual Node Count	10	50	100	500	1,000
Node1	-	-	-	-	-
Node2	553	780	419	451	470
Node3	641	384	427	527	428
Node4	14	711	790	442	431
Node5	80	151	717	493	480
죽은 노드 Key 개수	1288	2026	2353	1913	1809
재배치 된 Key 개수	1288	2026	2353	1913	1809
재배치 키 표준분포	99.597	57.89	32.83	8.23	5.88

위는 안정해시 테스트 결과다. 

• 죽은 노드(서버1)가 가지고 있는 Key의 갯수만큼만 재배치되었다. 
• 가상 노드의 갯수가 증가할수록 각 노드에 해시 키가 골고루 분포된다. 

 

일반 해시 테스트 결과

해시 링 없이, 일반 해시 개념을 이용해서 테스트를 했다. 즉, 아래처럼 노드로 라우팅하는 룰을 작성했다.

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

노드	키 개수
Node1
Node2	1964
Node3	2070
Node4	1979
Node5	1975
죽은 노드 Key 개수	1951
재배치 된 Key 개수	7988
재배치 키 표준분포	2.45

결과를 살펴보면 안정해시와 다른 것을 알 수 있다. 

• 재배치 된 Key는 80% 수준임(8000 / 10000) 
• 재배치 된 Key의 표준 분포는 양호함.

 

실험 결론

안정해시를 사용했을 때의 결론은 다음과 같다.

• 안정해시는 일반해시 대비 키 재배열 관점에서 안정적이다. 즉, 캐시 미스가 적을 것이다.
• 안정해시는 가상노드의 개수를 늘려갈수록, 각 노드에 키가 균등하게 저장된다.
• 안정해시는 죽은 노드가 가지고 있는 키의 갯수만큼 재배치 된다. 

---

고민해보면 좋을만한 것들

안정 해시를 이용한 서버에게 데이터를 요청할 때 어떻게 구현하는 것이 맞을까? 예를 들어 클라이언트가 캐시 서버에게 데이터를 요청하는 것을 상상해보자. 그러면 세 가지 방법이 있을 것이다. (아마 더 있을지도?) 

• 클라이언트 서버 : 클라이언트 서버에서 라우팅 알고리즘을 알고, 특정 서버에게만 요청.
• 미들 웨어 : LB 같은 미들웨어에서 클라이언트 서버의 요청을 받고, 안정해시 라우팅 알고리즘에 의해서 서버를 특정해 요청
• 캐시 서버 : 요청을 받았을 때, 자신에 저장되지 않은 데이터라면 안정해시 라우팅 알고리즘에 의해서 서버를 특정해서 클라이언트에게 응답함. 그리고 클라이언트는 응답을 보고 리다이렉팅 함. 

나는 위 테스트 코드에서는 클라이언트 서버에서 라우팅 알고리즘을 알고 특정 서버에게만 요청하도록 구현을 했다. 그러면 각 경우 고려해야 할만한 것이 어떤 것이 있을까? 

---

클라이언트 서버에서 라우팅 알고리즘을 알고 서버 특정함. 

이 경우의 장/단점 및 고려사항은 다음과 같다. 

• 장점 : 클라이언트가 직접 특정 서버에게 요청을 함. LB 같은 중간 단계가 없어 네트워크 Hopping이 감소할 수 있음.
• 단점 : 클라이언트가 라우팅 가능한 모든 서버에 대해서 실시간으로 알고 있어야 함. 

아래 방법처럼 구현해 볼 수 있을 것 같다. 

• 서버는 Redis에게 자신이 살아있음을 저장함. (만료 시간을 설정함)
• Client는 Redis에게 살아있는 서버를 질의한 후, 라우팅 알고리즘을 통해서 보낸다. 

여기서는 Server가 Redis에게 직접 헬스 체크를 하는 방법으로 접근했지만, 이 경우 서버에 자신의 헬스를 알려주는 로직이 추가되어야 한다. 만약에 비즈니스 서버에 특정 인프라 코드가 들어가는게 마음에 들지 않는다면, Redis 대신 WAS를 하나 만들고 그 WAS가 각 서버가 살아있는지를 살펴보도록 체크를 하는 방법도 가능할 것으로 보인다. 

---

미들 웨어에서 라우팅

클라이언트는 일단 요청을 보내고, Nginx 같은 로드 밸런서 계층에서 요청을 받아서 안정 해시 알고리즘에 따라서 라우팅 하는 작업을 하는 것이다. 

• 장점 
  • 대규모 서비스에서는 LB를 이용해서 여러 서버로 트래픽을 분산하는게 일반적이다. 따라서 어렵지 않게 추가할 수 있다. 
  • LB는 Upstream 서버의 헬스 체크를 하는 기능이 포함되어 있으므로, Active하게 헬스체크해서 존재하지 않는 서버를 라우팅 대상에서 제거할 수 있음.
• 단점 
  • 단일 LB가 장애 포인트가 발생할 수 있음. 따라서 클러스터링 LB를 이용해서 고가용성을 확보해야 함. 

참고로 Nginx에서는 Round Robin 뿐만 아니라 안정해시 알고리즘을 기반으로 라우팅하는 기능이 내장되어 있다고 한다. 

 

---

캐시 서버에서 리다이렉팅 처리

또 다른 방법은 클라이언트는 아무 캐시 서버에 요청을 보낸다. 요청을 받은 캐시 서버는 자신이 가지고 있는 데이터인지 확인하고, 아닌 경우 안정 해시 알고리즘을 이용해 적절한 캐시 서버 노드로 Redirect를 해주는 것이다. 이 방법의 장/단점은 다음과 같다.

• 장점 : 서버 간의 리다이렉팅을 통해 자동으로 데이터의 위치를 찾을 수 있음.
• 단점 : 대규모의 트래픽이 왔을 때, 대규모의 리다이렉팅이 발생할 수 있음. 즉, 대규모의 네트워크 홉이 발생하며 Latency 문제가 있을 수 있음.

 

 

---

결론

안정해시의 이점은 다음과 같다.

• 서버가 추가 / 삭제 될 때, 재배치 되는 키의 수가 최소화 됨.
• 데이터가 보다 균등하게 분포되므로 수평적 규모 확장 달성에 용이함. 
• 핫스팟 키 문제를 줄임. 특정 해시 슬랏 구간에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있음. 예를 들면 레이디 가가같은 유명인 데이터가 특정 해시 슬랏 구간에만 저장된 경우를 해결해줌. 
• 기존 해시 알고리즘으로 라우팅 시, 대부분의 키가 리밸런싱 됨. 따라서 한 캐시 서버의 장애가 대규모의 캐시 미스를 유발할 수 있으며, DB까지 장애 영향이 미친다.