안정 해시 설계

DongHwan·2022년 6월 1일
0

Design

목록 보기
4/11

"가상 면접 사례로 배우는 대규모 시스템 설계 기초"를 읽고 정리한 글입니다 :)

서버의 개수를 늘리는 수평적 규모 확장을 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시(Consistent Hash)가 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다. 안정 해시는 해시 키 재배치(Rehash) 문제를 해결할 수 있는 기술이다. 그러니 해시 키 재배치 문제에 대해 먼저 알아보자

해시 키 재배치(Rehash) 문제

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

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

이 방법은 서버 풀(Server Pool)의 크기가 고정되어 있을 때, 또 데이터 분포가 균등할 때는 잘 동작한다. 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 발생한다. 예를 들어 총 4개의 서버가 있는 시스템에서 한개의 서버가 동작을 중단한 경우, 서버 풀의 크기는 3이 된다. 그 결과 나머지 연산을 적용하여 계산된 serverIndex의 값이 달라질 것이다. 그 결과 대부분의 클라이언트가 자신이 원래 가야할 서버가 아닌 엉뚱한 서버에 접속하게 된다. 안정 해시는 이 문제를 효과적으로 해결할 수 있다.

안정 해시(Consistent Hash)

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

https://tom-e-white.com/2007/11/consistent-hashing.html

안정 해시는 해시 링(Hash Ring)을 사용하여 데이터와 서버를 배치한다.

우선 서버 IP나 이름을 해시 함수를 사용하여 해시 링 위에 배치한다. 위 사진에서는 1, 2, 3, 4로 표시된 4개의 서버가 배치되었다고 가정하자.

서버 뿐만이 아니라 키들도 해시 링 위의 특정 지점에 배치를 할 수 있을 것이다. 이때 어떠한 키가 저장되는 서버는 해당 키의 위치에서부터 시계 방향으로 링을 탐색해 가장 먼저 만나는 서버이다. 즉, 위 사진에서 A 데이터는 2번 서버에 저장되고, B 데이터는 3번 서버에 저장된다.

이 방식을 사용한다면 새로운 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다. 예를 들어 위 사진에서 B 데이터와 3번 서버 사이에 5번 서버가 추가되었다고 가정하자. 그렇다면, B 데이터만 5번 서버로 재배치하면 Rehash가 끝이 난다.

반대로 기존 서버를 제거할 때도, 일부 키만 재배치하면 된다. 위 사진에서 3번 서버가 제거되면, B 데이터만 4번 서버로 재배치하면 Rehash가 끝이 난다.

기본 접근법의 2가지 문제

안정 해시의 기본 접근법은 다음과 같다.

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

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

먼저 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(Partition)의 크기를 균등하게 유지하는 게 불가능하다. 여기서 파티션은 인접한 서버 사이의 해시 공간을 의미한다. 기본 접근법에서는 서버가 추가되거나 삭제되는 경우 어떤 서버에 굉장히 작은 해시 공간 혹은 굉장히 큰 해시 공간을 할당받는 상황이 가능하다.

두번째 문제는 키의 균등 분포를 달성하기가 어렵다. 해시 공간이 균등하게 할당되는 것이 아닌 불균등하게 할당될 가능성이 크고, 키의 배치 역시 특정 공간에 몰릴 가능성이 크다.

이 문제를 해결하기 위해 제안된 기법이 가상 노드(Virtual Node) 또는 복제 노드(Replica)이다.

가상 노드

https://medium.com/interviewnoodle/how-to-use-consistent-hashing-in-a-system-design-interview-b738be3a1ae3

가상 노드(Virtual Node)는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. 쉽게 얘기하면 위처럼 여러 개의 가상 노드를 두고, 각 서버는 하나가 아닌 여러개의 파티션을 관리하는 것이다.

이 가상 노드의 개수를 늘리면 키의 분포가 점점 더 균등해진다. 하지만 그만큼 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. 즉, TradeOff를 고려하여 적절한 개수를 고르는 것이 중요하다.

안정 해시의 이점

  • 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
  • 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
  • 핫스팟(HotSpot) 키 문제를 줄인다.
    • 특정한 샤드(Shard)에 대한 접근이 지나치게 몰리는 것을 줄일 수 있다.
profile
날 어떻게 한줄로 소개해~

0개의 댓글