[TIL] 가상 면접 사례로 보는 대규모 시스템 설계 기초 - 5장

이 글은 책을 보고 배운 내용을 요약합니다. 자세한 설명은 생략되어 있기 때문에 책을 직접 구입해서 보시길 바랍니다.

안정 해시 설계

수평적 규모 확장성(scale out)을 하기 위해서는 요청이나 데이터를 각 서버에 균등하게 나눠야 한다. 그 방법으로 사용할 수 있는 일반적인 기술이 안정 해시다. 안정 해시에 대해서 다루기 전에 안정 해를 통해 해결하려고 하는 문제가 무엇인지부터 살펴보자.

해시 키 재배치 문제

N개의 서버가 존재할 때 이 서버들에 부하를 균등하게 나누는 일반적인 방법은 아래의 해시 함수를 사용하는 것이다.

serverIndx = hash(key) % N

자세한 설명은 책을 참고하길 바란다. 요약하면 해시 함수를 사용해서 균등하게 분배하는 것은 다음과 같은 조건이 따라야 한다.

• 서버 풀 크기가 고정
• 데이터 분포가 균등

하지만 N이 변경됬을 때 해시 값으로부터 나오는 serverIndex 자체가 변경되기 때문에 서버 인덱스가 변경되고 원하는 데이터에 접근할 수 없을 수도 있다.

안정 해시

위키피디아에 따른 안정해시의 정의는 다음과 같다.

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

쉽게 이해하자면 인덱스가 달라졌을 때 모든 키를 다 재배치하는 것보다 안정해시를 통해서 재배치하는 양을 k/n개로 줄이자는 의미다.

동작 원리에 대해서 자세한 설명은 책을 참고하고 요약하면 다음과 같다.

1. 해시 서버와 해시 키를 균등 분포 해시 함수를 사용해서 해시 링에 배치한다.
2. 해시 키의 위치에서 시계 방향으로 돌면서 해시 서버를 찾는다. 첫 번째 해시 서버가 해시 키가 저장될 장소다.
3. 해시 서버가 중간에 빠지거나 추가되었을 때, 영향을 받는 키에 대해서만 재배치를 수행하면 된다.

이 알고리즘에 대한 단점은 두가지가 있다.

• 파티션의 크기를 균등하게 유지하는게 불가능하다.
• 키의 균등 분포를 달성하기 어렵다.

이를 해결하기 위한 방법이 가상 노드 또는 복제라 불리는 기법이다.

가상 노드

가상 노드는 하나의 서버를 여러개의 파티션(가상 노드)로 나눠서 하나의 서버가 여러 개의 파티션을 관리하는 형태다. 그렇게 되면 서버가 추가되거나 삭제될 때 재배치되는 키가 하나 서버에 몰리는 것이 아니라 각 가상 노드에 분배되기 때문에 파티션을 많이 나눌 수록 균등하게 배치가 된다.

마치며

안정해시가 왜 필요하며 어떻게 동작하는지에 대해 이해할 수 있었다. 책에서 소개하는 안정 해시의 장점은 다음과 같다.

• 서버가 변경될 때 재배치되는 키의 수가 최소화된다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
• 핫스팟 키 문제를 줄일 수 있다.

실제로 안정 해시를 쓰는 곳은 다음과 같다.

• 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
• 아파치 카산드라 클러스터에서의 데이터 파티셔닝
• 디스코드 채팅 어플리케이션
• 아카마이 CDN
• 매그레프 네트워크 부하 분산기