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

https://product.kyobobook.co.kr/detail/S000001033116

가상 면접 사례로 배우는 대규모 시스템 설계 기초 | 알렉스 쉬 - 교보문고

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

 

이 파트는 필자가 정말 재밌게 읽었던 부분이다. 안정해시와 관련해서 최범균님의 영상도 있으니 관심있는 사람은 같이 봐도 좋을 것 같다.

https://www.youtube.com/watch?v=UQfNytDFpgk&t=281s 

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

 

해시 키 재배치(rehash)문제

N개의 캐시서버에 부하를 균등하게 나누기 위해서 일반적으로 아래의 해시함수를 이용한다.

serverIndex = hash(key) % N

 

그런 만약 여기서 캐시 서버가 증가하거나 제거된다면 문제가 생긴다. N -> N-1으로 변경되었으니, 기존에 들어있던 데이터들이 잘못된 위치에 들어간 꼴이 되는 것이다. 따라서 현재 서버에 들어가 있는 대부분의 데이터를 다른 서버로 재 분배 해야한다. 안정해시는 이 문제를 효과적으로 해결하는 기술이다.

 

안정 해시

안정해시는 해시 테이블 크기가 조정 될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다.(k=키 개수, n=슬롯 개수)
해시 함수로 SHA-1을 사용한다고 했을 때 함수의 출력 값 범위(해시 공간; hash space)는 0~ 2^160-1이다. 여기서 처음과 끝을 연결해서 연결리스트처럼 만든 모양을 해시 링이라고 부른다.

 

해시 서버

해시 서버를 사용하면 해시 링의 특정 위치에 서버를 위치 시킬 수 있다. 이제 링의 특정 위치에 할당되는 서버는 특정 위치에서 값을 증가시키면서 가장 먼저 만나는 서버로 정할 수 있을 것이다. 그럼 서버가 제거된다면 제거된 서버 다음순서로 있던 서버로 기존 데이터를 옮기면 될 것이고, 서버가 추가된다면 추가된 서버 다음에 있는 서버에 할당되어 있던 데이터들 중에 추가된 서버보다 앞에 있던 데이터를 추가된 서버로 옮기면 될 것이다. 

 

안정 해시 알고리즘의 기본 절차는 2가지이다.

1. 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.

2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.

 

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

1. 서버가 추가/삭제 된다면 파티션의 크기를 균등하게 유지할 수 없다.

2. 해시의 특성상 특정 서버에 데이터가 몰릴 수 있어서 키의 균등 분포를 달성하기 어렵다.

이 문제들을 해결하는 방법이 바로 가상 노드이다.

 

가상 노드

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.(바로가기, link를 생각하면 이해하기 쉽다) 이를 통해 파티션이 더 잘게 쪼개지게 되며, 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 그러나 가상 노드의 개수가 늘어나면 저장 공간은 더 늘어나게 된다. 트레이드 오프가 필요한 순간이다.