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

수평적 규모 확장성을 달성하기 위해서는 요청, 데이터를 서버에 균등하게 나누는 것이 중요 ☑️

안정 해시는 이런 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

⚠️ 해시 키 재배치 문제 (rehash)

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

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

 

👀 예시 - 4대의 서버

키	해시	해시 % 4 (서버 인덱스)
key0	18358617	1
key1	26143584	0
key2	18131126	2
key3	35863496	0
key4	34085809	1
key5	27581703	3
key6	38164978	2
key7	22530351†	3

- 해시 값과 서버 인덱스를 계산한 결과

 

키 값이 서버에 어떻게 분산되는지 그림으로 보면 다음과 같다.

 

이 방법은 서버 풀의 크기가 고정되어 있고 데이터 분포가 균등할 때는 잘 작동한다.

 

⚠️ 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.

 

ex) 서버 하나에 장애가 발생해 동작이 중단하면 서버 풀의 크기는 3으로 변한다.

• 키에 대한 해시 값은 변하지 않지만 나머지 연산을 적용해 계산한 서버 인덱스 값은 달라진다.
• 올바르지 않은 서버로 접근하게 된다.

 

 

이렇게 장애가 발생한 서버에 보관된 키뿐 아니라 대부분의 키가 재분배되었고 캐시 클라이언트가 데이터가 없는 서버에 접속하게 되어 대규모 캐시미스가 발생하게 된다

 

⭐ 안정 해시

안정 해시

• 해시 테이블 크기가 조정될 때 평균적으로 k / n 개의 키만 재배치하는 기술
• k: 키의 개수
• n: 슬롯의 개수
  

 

📖 해시 공간과 해시링

🧩 해시 공간

 

해시 함수의 출력 값 범위가 x0, x1, x2, x3, …. xn 과 같다고 하자.

해시 함수로 SHA-1 를 사용한다고 하면 해시 공간의 범위는 0부터 까지로 알려져 있고 이 해시 공간을 그림으로 표현한 것.

 

⭕ 해시 링

 

해시 링은 해시 공간의 양쪽을 구부려 잡으면 만들어진다.

 

🤖 해시 서버

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

https://karmesin924.tistory.com/88

 

🔑 해시 키

https://karmesin924.tistory.com/88

 

사용된 해시 함수는 해시키 재배치 문제에 언급된 함수와 다르다.

나머지 연산(%) 은 사용하고 있지 않다.

 

캐시할 키 (key0, key1, …) 또한 해시 링의 어느 지점에 위치할 수 있다.

 

🔍 서버 조회

키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색하다 만나는 첫 번째 서버이다.

https://karmesin924.tistory.com/88

• key0은 서버 0, key1은 서버 1, key2은 서버 2, key3은 서버 3에 저장된다.

 

📌 서버 추가 / 제거

서버를 추가하더라도 키 가운데 일부만 재배치를 하면 된다.

https://karmesin924.tistory.com/88

 

서버 4가 추가된 이후에 key0만 재배치가 되었다.

• key0 위치에서 시계방향으로 돌때 처음으로 만나는 서버가 서버 4이기 때문

 

하나의 서버가 제거될 때 역시 일부만 재배치된다.

https://karmesin924.tistory.com/88

⚠️ 기본 구현법의 2가지 문제

안정 해시 알고리즘의 절차는 아래와 같다.

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

 

이 방법에는 2가지 문제가 있다.

 

💣 파티션의 크기를 균등하게 유지하는 게 불가능

📖 파티션

• 인접한 서버 사이의 해시 공간

 

어떤 서버는 작은 해시 공간을 할당 받고 다른 서버는 큰 해시 공간을 할당 받는 상황이 가능해진다.

 

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

특정 서버는 아무 데이터를 가지고 있지 않을 수도 있는데 다른 서버에서는 대부분의 키가 저장되는 문제가 발생할 수 있다.

이런 문제를 해결하기 위해서 제안된 기법이 가상 노드 기법이다.

 

👋 가상 노드

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

https://karmesin924.tistory.com/88

 

서버 0와 서버 1은 3개의 가상 노드를 가지고 있다.

서버 0는 S0 를 하나 쓰는 대신 S0_0, S0_1, S0_2 을 사용했다.

서버 1도 동일하게 3개의 가상 노드를 사용했다.

 

따라서, 각 서버는 여러 개의 파티션을 관리해야 한다.

 

 

💡 가상 노드의 개수를 늘리면 키의 분포는 점점 균등해진다.

• 표준 편차가 작아져 데이터가 고르게 분포되기 때문
• ⚠️ 하지만 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 된다 (트레이드 오프)

 

🔖 배운 점 정리 및 궁금한 점 정리

💡 안정 해시의 핵심 아이디어

• 해시 공간을 원형(해시 링) 으로 보고
• 서버와 키를 같은 해시 공간에 매핑한 뒤
• 키 위치에서 시계 방향으로 처음 만나는 서버에 할당한다.
• 서버가 추가, 삭제돼도 평균적으로 k/n개의 키만 재배치되므로 캐시 미스가 적어진다.

 

📚 Ref.

https://product.kyobobook.co.kr/detail/S000001033116