<대규모 시스템 설계 기초> "5장 안정 해시 설계"를 읽고 작성하는 포스트 입니다.

안정 해시(Consistent Hashing) 이란?

안정 해시(Consistent Hash)는 일반적으로 요청 또는 데이터를 서버에 균등하게 나누기 위해 일반적으로 사용되는 기술이다.

전통적 해시 테이블(Hash Table)

전통적인 Hash Table의 경우 모듈로(%) 연산을 이용한다

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

이 경우 적용하려는 대상(서버 또는 데이터)의 갯수가 고정되어 있는 경우 문제가 없지만, 해당 대상이 추가 되거나 삭제 되는 등의 변동이 있는 경우, 대부분의 해시 대상이 재분배 된다. 따라서 확장성(scalability)에 취약하다

해시 키 재배치

해시 키 재배치란, 책에 나온 예를 들자면 Key 8개와 서버 4대가 있을 때 Key는 2개씩 0, 1, 2, 3에 할당되어 있지만 서버 1대가 장애가 나는 경우 서버 대수(위 수식의 N)를 기반으로 해싱하기에 모두 새로 해싱되어 해시 키가 재배치(Rehash) 된다. 이 경우 장애가 발생한 서버에 보관된 키를 제대로 찾지 못해서 대규모 Cache Miss가 발생하게 된다.

안정 해시와 해시 테이블

이런 해시테이블과 다르게 안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 Key/N(위의 서버 수와 동일)의 키만 재배치하도록 하는 해시 기술이다.

안정 해시는 전통적 해시 테이블과 다르게 모듈로 연산(%)으로 대상을 탐색하지 않으며, Hash Ring을 만들어 링 위에서 첫번째 만나는 것을 대상으로 한다.

이미지 출처

1, 2, 3, 4의 서버가 있을 때 A의 대상 서버는 2이다.
위와 같은 구조일 때 서버 2에 장애가 난다면 A는 2가 아닌 3 서버에 재배치될 것이다.

안정 해시 기본 구현법의 문제

• 균등 분포 해시 함수를 사용
• 시계 방향 첫 번째의 서버를 지정하는 것

이 해시의 문제점은 균등 분포 해시 함수를 사용해도 해시 파티션(partition) (위 그림의 링 위의 서버 사이의 간격) 의 크기를 균등하게 유지하는게 불가능 하다는 것과 이로 인해 키가 균등하게 분포되기 어렵다는 문제가 있다.

이를 해결 하기 위해 가상노드(Virtual Node) or 복제(Replica)라 불리는 기법을 사용한다

안정 해시의 가상 노드(Virtual Node)

이미지 출처

하나의 서버는 링 위에서 여러 개의 가상 노드를 가지게 된다. (우측 그림)
따라서 안정 해시는 탐색 후 첫번째 만나는 서버를 대상으로 하므로, 가상 노드가 없는 좌측 그림의 구조와 달리 가상 노드가 많을 수록 키의 분포가 균등하게 된다.
가상 노드의 개수를 늘릴 수록 표준 편차의 값은 떨어지지만 가상 노드 데이터를 저장할 공간은 더 많이 필요하므로 시스템의 요구사항에 맞는 적절한 수치가 필요하다.

추가적으로 찾아본 것

읽다보니 주 스택으로 사용하는 Java에서의 Hash는 어떻게 구현되어 있나 궁금함이 생겨 검색해보니 아래의 글이 나왔다.

• Java의 Hash Collection
  • Java 7에서 Java 8의 Hash 구현 변화와 해시 충돌을 막기 위한 보조 해시 함수에 대한 내용, String 객체에 대한 해시 함수 내용이 있다. 고퀄리티의 글이라 읽는 것을 추천한다.
  • Java의 HashMap에서는 해시 충돌 방지를 위해 Seperate Chaning과 보조 해시 함수를 사용하고, Java8의 경우 Separate Chaning에서 Linked List 대신 Tree를 사용하기도 한다.
  • 웹 어플리케이션 서버의 경우 HTTP Request가 생성될 때마다 여러개의 HashMap이 짧은 시간내 생성되고 사라지기에 GC의 대상이 된다.

또, 책 내에서 참고 문헌으로 든 Discord의 Scaling 사례가 있다.

• Discord의 Scaling
  • Discord에서는 Fast Access를 위해 Consistent Hashing 을 사용하고 있으며 사용 후에도 Node 조회에 이슈가 있어 세마포어를 구현해 Node 조회 이슈를 해결한 문제에 대해 설명하고 있다.