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

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

5장 안정 해시 설계

수평적 규모 확장을 위해 요청 이나 데이터를 균등하게 저장해야 한다. 이 기술은 모든 데이터를 균등하게 보편적으로 나누기 위해 사용되는 기술이다.

해시 키 재배치(rehash) 문제

ServerIndex = Hash(Key) % N

(N은 서버의 개수이다.)

이런 해쉬 함수가 있다고 가정할 때 인덱스의 키 값에 따라 N개의 서버에 균등하게 저장된다. 하지만 서버가 만약 추가되거나 없어진다면 N 의 수는 변동하고 모든 Hash함수를 통해 저장된 값들에게 변동사항이 생긴다. 안정 해시는 이러한 문제를 효과적으로 해결하고자 만들어진 기술이다.

안정 해시

안정 해시 란 테이블의 크기가 조정될 때 재배치의 횃수가 평균적으로 K/N 번인 해시 기술이다.

K는 키의 개수이고 N은 슬롯의 개수이다.

1. 해시 공간과 해시 링
2. 해시 서버와 해시 키
3. 서버 추가 및 제거

   기본 구현법 두가지

• 서버와 키를 균등 분포 해시 함수를 사용하여 해시 링에 배치
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다. 이 두 가지 절차는 몇가지 문제가 있다.

1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 게 불가능하다.
2. 키의 균등 분포를 달성하기 어렵다는 것이다. 위 문제를 해결하기 위해 가상노드가 나왔다.

가상노드

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

S1이라는 서버를 S1_0, S1_1, S1_2로 가상 서버로 만들어 링위에 배치할 수 있다는 의미이다.

이런 가상 노드의 개수를 늘리면 키의 분포는 점점 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다.

결론

이 장은 안정해시의 필요성과 그 동작 방법에 대해 말해보았다.

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수를 최소화한다.
• 데이터가 보다 균등하게 분포되므로 수평적 규모확장에 유리하다.
• 샤드에서 나올 수 있는 문제점들을 해결한다.