[System Design Interview] 05. ⚙️ 안정해시란?

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (System Design Interview) - 저 : 알렉스 쉬, 역 : 이병준 을 읽고 정리한 글입니다.

 

5장에서는 안정 해시 설계에 대한 내용을 다룹니다.

이번 글에서는, 안정 해시가 왜 필요하며 어떻게 동작하는지에 대해서 이야기합니다.

 

 

[목차]

1. 해시 키 재배치 문제
2. 안정 해시란
3. 안정 해시 동작 과정
4. 안정 해시 장점

 

 

---

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

해시 키 재배치 문제란, 안정 해시로 인해 풀고자하는 문제입니다.

 

해시 키 재배치 문제가 일어나는 상황 예시

보통 N개의 서버가 있고, 아래와 같은 해시 함수를 사용하여 부하를 균등하게 나누고 있다고 가정합니다.

클라이언트에서는, 이렇게 계산된 serverIndex 값을 이용해 데이터에 접근합니다.

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

→ 이러한 경우, 서버 풀 (server pool) 의 개수가 고정되어 있고, 데이터 분포가 균등할 때는 전혀 문제가 없습니다.

잘 작동되는 해시 키 분배

 

 

👏🏻 단 이러한 경우, 서버가 추가되거나 기존 서버가 삭제될 떄 문제가 발생합니다.

• 예를 들어 총 4개의 서버가 있는 시스템에서 한개의 서버가 동작을 중단한 경우, 서버 풀의 크기는 3이 됩니다.
• 그 결과 나머지 연산을 적용하여 계산된 serverIndex의 값이 달라질 것 입니다.
• 그 결과 대부분의 클라이언트가 자신이 원래 가야할 서버가 아닌 엉뚱한 서버에 접속하게 되고 이는 대규모 캐시 미스 (cache miss) 로 이어집니다.

 

안정 해시는 이러한 해시 재배치  (hash refresh )문제를 효과적으로 해결할 수 있습니다//

 

---

📌 02. 안정 해시 (Consistent Hash)

수평적 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요합니다.
안정해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술입니다.

 

안정 해시란

• 안정 해시(Consistent Hash)는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술입니다.
• 여기서 k는 키의 개수이고, n은 슬롯(Slot)의 개수이다. 전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치합니다.

 

해시 공간과 해시 링

• 안정 해시는 기본적으로 해시공간을 구부린, 해시 링이라는 개념을 사용합니다.
• 해시공간이란, 특정 해시 함수로 나누어질 수 있는 공간의 전체 범위를 의미합니다.
• 해시 링이란, 이 해시 공간의 양 끝쪽을 구부려서 논리적인 링처럼 생각하는 개념입니다.

 

💡 해시공간과 해시 링 예시

• 해시 함수로 SHA-1 을 사용하고 결과값 출력 범위는  x0, x1, x2, … xn과 같다고 가정해보겠습니다.
• SHA-1의 해시공간 범위는 0부터 2160-1 까지라고 알려져 있으니, 
• 따라서 x0는 0, xn은 2160-1이며, 나머지 x1 부터 xn-1까지는 그 사이의 값을 갖게 될 것입니다.

 

그럼 아래와 같은 논리적인 해시공간이 생기고, 이를 구부린 것이 해시 링입니다.

해시 서버

• 이 해시 함수를 f 를 사용하면 서버 IP 혹은 이름을 이 링 위의 특정한 주소에 위치 시킬 수 있습니다.
• 아래는 4개의 서버를 해시 링 위에 위치시킨 결과입니다.

 

해시링의 "해시 키 배치" 및 "서버 조회"

• 여기서 사용하는 해시 함수는, "해시 키 재배치 문제" 에 언급한 함수와 다르며, 나머지 연산 "%" 는 사용하지 않습니다.
• 아래의 그림과 같이, 캐시할 키 key0, 1, 2, 3 을 서버처럼 해시 링 위의 어느 한 지점에 배치할 수 있습니다.
• 이 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫번째 서버 입니다.
• 예를들어, key0은 서버 0에 저장되며, key1 은 서버1, key 2 는 서버2에 저장됩니다.

 

해시링 서버 추가 및 서버 삭제 시 동작 과정

• 이렇게 되는 경우, 서버를 추가하거나 삭제하더라도 해시 키 전체가 재배치되지 않고, 일부만 재배치 되게 됩니다.
• 안정 해시를 사용했으므로, 서버를 추가하더라도 키 가운데 일부만 재배치 되고
• 서버를 삭제하더라도, 얘를들어 서버 1이 삭제되어도, key1만이 서버 2로 재배치되며 나머지 키에는 영향을 주지 않습니다.

왼쪽은 서버추가 시 재배치, 오른쪽은 서버 삭제 시 재배치

 

---

📌 03. 안정해시 구현방법

안정 해시 알고리즘은 MIT 에서 처음 제안되었으며, 그 기본 절차는 아래와 같다고 합니다.

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

 

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

1. 첫 번째는, 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기(인접한 서버 사이의 해시 공간) 를 균등하게 유지하는 게 불가능하다는 것이고
2. 두 번째 문제는 키의 균등 분포를 달성하기가 어렵다는 것입니다.

 

예를들어 아래 그림과 같이

• 어떤 서버는 굉장히 작은 해시 공간을 할당 받고, 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 가능해 집니다. (첫번째 문제)
• 서버1과 서버3은 아무 데이터를 갖지 않는 반면, 대부분의 키는 서버2에 보관될 것입니다. (두번째 문제)

 

안정해시 문제점

 

이 문제를 해결하기 위해 제안된 기법이 가상 노드(virtual node) 또는 복제(replica)라 불리는 기법입니다.

 

가상 노드

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

가상 노드 예시

• 아래 그림을 보면 서버0과 서버1은 3개의 가상 노드를 갖습니다.
• 여기서 숫자 3은 임의로 정한 것이며, 실제 시스템에서는 그보다 훨씬 큰 값이 사용됩니다.
• 서버 0을 링에 배치하기 위해 서버0 하나만 쓰는 대신, 서버0_0, 서버0_1, 서버0_2의 세 개 가상 노드를 사용합니다.
• 마찬가지로 서버 1을 링에 배치할 때 서버1_0, 서버1_1, 서버1_2의 세 개 가상 노드를 사용했다.
• 키의 위초로부터 시계방향으로 링을 탐색하다가 만나는 최초의 가상노드가 해당 키의 저장 서버가 됩니다.

가상 노드 유의할 점

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

1. 하지만, 가상노드 데이터를 저장할 공간이 더 많이 필요해야하고
2. 그림과 같이, 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 합니다.

 

---

📌 04. 안정해시 장점

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

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

 

 

끝!!

 

생각보다 정리하는데 올래걸렸던 장 크으

 

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

 

 

 

---

• 그림 참고 : https://donghyeon.dev/%EC%9D%B8%ED%94%84%EB%9D%BC/2022/03/20/%EC%95%88%EC%A0%95-%ED%95%B4%EC%8B%9C-%EC%84%A4%EA%B3%84/