Architecture(1) - 안정 해시(Consistent Hashing)

in DEV on Architecture Consistent-hashing Load-balancing System-design 안정해시 분산시스템 대규모시스템 Hash-ring


대규모 시스템을 설계할 때 가장 중요한 과제 중 하나는 폭발적으로 늘어나는 트래픽을 감당하기 위한 Scale-out 이다.
이를 성공적으로 달성하려면 수많은 요청이나 데이터를 여러 대의 서버에 고르게 분산시키는 기술이 필수적이다.

데이터가 한쪽 서버에만 몰리게 된다면 확장의 의미가 퇴색된다.
이 때 데이터의 균등한 분산을 돕고, 서버의 유연한 확장을 가능하게 하는 기술이 바로 안정 해시(Consistent Hashing)이다.

1. 해시 키 재배치(rehash) 문제

안정 해시를 이해하기 위해 먼저 ‘전통적인 해시 방식이 왜 대규모 시스템에 적합하지 않은지’를 알아야 한다.

N개의 캐시 서버가 있다고 가정해보자.
이 서버들에 부하를 균등하게 나누기 위해 보편적으로 사용하는 방법은 아래와 같이 나머지(Modulo) 연산을 활용한 해시 함수를 사용하는 것이다.

기본 해시 분산 공식

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

총 4대의 서버(N=4)를 사용한다고 가정하고, 주어진 각각의 key에 대해 해시 값과 저장될 서버 인덱스를 계산하면 아래와 같은 결과가 나온다.

키해시(Hash)해시 % 4 (서버 인덱스)
key0183586171
key1261435840
key2181311462
key3358634960
key4340858091
key5275817033
key6381649782
key7225303513

예를 들어 hash(key0) % 4 = 1 이므로 클라이언트는 key0에 해당하는 데이터를 가져오기 위해 1번 서버에 접속하게 된다.
이 규칙에 따라 4대의 서버에 키 값이 분산되는 모습을 그리면 아래와 같다.

해시 키 배치

1.1. 서버 개수가 변할 때 발생하는 대규모 캐시 미스

이 방식은 서버 풀(Pool)의 크기가 고정되어 있고 데이터 분포가 균등할 때만 완벽하게 동작한다.
하지만 대규모 시스템에서는 트래픽 폭주로 서버를 증설하거나, 반대로 장애가 발생해 서버가 다운되는 일이 빈번하다.

예를 들어 1번 서버가 장애를 일으켜 다운되었다고 가정해보자.
이제 활성화된 전체 서버의 개수(N)은 4에서 3으로 변한다.

키에 대한 고유한 해시값 자체는 변하지 않지만, 나머지 연산(%3)을 적용하여 계산된 서버 인덱스 값은 완전히 달라지게 된다.

키해시해시 % 3 (서버 인덱스)
key0183586170
key1261435840
key2181311461
key3358634962
key4340858091
key5275817030
key6381649781
key7225303510

아래 그림은 활성 서버가 3대로 줄었을 때 새롭게 변화된 키의 분포이다.

결과적으로 장애가 난 1번 서버에 보관되어 있던 키뿐만 아니라, 거의 모든 키의 위치가 재배치(Rehash)되어버린다.
클라이언트는 엉뚱한 서버로 데이터를 요청하게 되고, 데이터가 없으니 대규모 캐시 미스가 발생한다.
이는 결국 원본 데이터베이스에 엄청난 읽기 부하를 일으켜 시스템 전체의 마비로 이어질 수 있다.

해시 키 재배치

2. 안정 해시(Consistent hash)

앞서 살펴본 해시 키 재배치 문제를 근본적으로 해결하기 위해 등장한 기술이 바로 안정 해시이다.

안정 해시란?
해시 테이블의 크기가 조정(서버 추가 또는 삭제)될 때, 전체 키를 재배치하는 것이 아니라 평균적으로 오직 \(k/n\)개(k: 전체 키의 개수, n: 서버의 개수)의 키만 재배치하는 효율적인 해시 기술이다.
대부분의 키는 원래의 위치를 유지하므로 대규모 캐시 미스 사태를 방지할 수 있다.

2.1. 해시 공간과 해시 링

안정 해시의 동작 원리를 이해하기 위해, 해시 공간(Hash Space)을 하나의 ‘Ring’으로 만들어보자.

해시 함수 \(f\)로 SHA-1을 사용한다고 가정해보자.
SHA-1 알고리즘이 생성할 수 있는 해시 값의 범위는 0부터 \(2^{160}-1\)까지로 매우 넓다.
이 출력 값 범위를 \(x_0, x_1, \dots, x_n\)이라고 할 때, \(x_0\)은 0, \(x_n\)은 \(2^{160}-1\)이 된다.

이 넓은 1차원의 직선 해시 공간을 그림으로 표현하면 아래와 같다.

해시 공간

이제 이 직선의 양 끝(\(x_0\)과 \(x_n\))을 구부려 이어 붙이면, 아래와 같은 해시 링이 완성된다.
안정 해시는 바로 이 원형 공간 위에서 동작한다.

해시 링

2.2. 해시 링 위에 서버와 키 배치하기

이 해시 링 위에는 ‘서버’와 ‘데이터(키)’를 모두 올릴 수 있다.
여기서 중요한 점은 앞서 사용한 나머지 연산을 전혀 사용하지 않는다는 것이다.

서버의 IP 주소나 이름을 해시 함수에 통과시켜 해시 링 위의 특정 위치에 대응시킨다.
아래 그림은 4대의 서버(서버0~서버3)을 해시 링 위에 배치한 모습이다.

해시 서버

2.3. 데이터가 저장될 서버 조회(서버 조회 알고리즘)

캐시할 데이터의 키(key0, key1, key2, key3) 역시 동일한 해시 함수를 거쳐 해시 링 위의 특정 지점에 배치된다.

해시 키 배치

그렇다면 특정 키는 어느 서버에 저장될까?
어떤 키가 저장될 서버는, 해당 키의 위치로부터 링을 시계 방향으로 탐색해 나가면서 만나는 ‘첫 번째 서버’이다.

아래 그림을 보면 key0의 위치에서 시계 방향으로 순회할 때 가장 먼저 만나는 서버가 s0(서버 0)이므로, key0은 서버 0에 저장된다.

서버 조회

2.4. 유연한 확장과 장애 대응: 서버 추가 및 제거 시의 동작

이 원형 링 구조가 빛을 발하는 순간은 바로 서버의 개수가 변할 때이다.

서버를 추가할 때(Scale-out)
트래픽이 늘어나 새로운 서버 4(s4)가 추가되었다고 가정해보자.
아래 그림을 보면, 기존 서버들에 저장되어 있던 모든 데이터가 이동하는 것이 아니라 새로 추가된 s4와 그 반시계 방향에 있는 첫 번째 서버(s3) 사이의 키들만 재배치된다.
결과적으로 key0만 서버 0에서 서버 4로 이동하며, 나머지 키들은 제자리를 유지한다.

서버 추가

서버를 제거할 때(Scale-in/장애 발생)

서버 1(s1)에 장애가 발생해 링에서 제거되었다고 해보자.
이 경우에도 전체 데이터가 흔들리지 않는다.
삭제된 s1과 그 반시계 방향에 있는 최초 서버(s0) 사이의 키들만 다음 시계 방향 서버인 s2로 재배치된다.
즉, key1만 서버 2로 이동하게 된다.

서버 제거

3. 기본 안정 해시의 한계와 해결책

기본 안정 해시 알고리즘 절차는 매우 훌륭하지만, 실제 대규모 운영 환경에 바로 적용하기에는 두 가지 치명적인 한계가 있다.

3.1. 파티션 크기 불균형과 데이터 쏠림 현상

첫 번째 문제는 서버별 파티션 크기를 균등하게 유지하는 것이 불가능하다는 것이다.
여기서 파티션은 해시 링 위에서 인접한 서버 사이의 해시 공간을 의미한다.

서버가 지속적으로 추가되고 삭제되다 보면, 어떤 서버는 굉장히 작은 해시 공간을 할당받고, 어떤 서버는 굉장히 큰 해시 공간을 갖게 된다.

아래 그림은 서버 1이 삭제되는 바람에 서버 2의 파티션이 다른 파티션 대비 거의 두 배로 커진 상황이다.

파티션 크기 문제

두 번째 문제는 파티션 크기가 제멋대로 변하면서 키의 균등 분포(Uniform Distribution)를 달성하기 어려워진다는 점이다.

아래 그림처럼 서버가 우연히 한쪽으로 몰려 배치되었다고 가정해보자.
이 경우 서버 1과 서버 3은 아무 데이터도 갖지 못하는 반면, 링의 절반 이상을 차지하는 서버 2의 파티션에 대부분의 키가 집중적으로 보관된다.
이렇게 되면 트래픽을 분산하려던 원래의 목적이 완전히 무너진다.

키의 균등 분포 문제

3.2. 가상 노드(Virtual Node)

이러한 불균형 문제를 해결하기 위해 도입된 기법이 가상 노드(Virtual Node), 또는 복제(Replica)라 불리는 기술이다.

가상 노드를 실제 물리적인 서버 1대를 해시 링 위에서 여러 대의 논리적인 노드로 쪼개어 표현하는 방식이다.
아래 그림을 보면 물리 서버 0과 서버 1이 링 위에서 각각 3개의 가상 노드(s0_0, s0_1, s0_2 등)를 갖고 있다.
(숫자 3은 설명을 위한 임의의 값일 뿐, 실제 상용 시스템에서는 데이터의 고른 분포를 위해 100~200개 이상의 훨씬 큰 값을 사용한다.)

가상 노드

이렇게 가상 노드를 촘촘하게 배치하면 각 물리 서버가 관리해야 할 파티션이 링 전체에 걸쳐 여러 개로 분산된다.

데이터가 저장될 서버를 찾는 방법은 기존과 동일하다.
키의 위치에서 시계 방향으로 탐색하다 만나는 최초의 ‘가상 노드’가 해당 키를 품게 된다.

아래 그림에서 키 k0은 시계 방향으로 탐색 시 가상 노드 s1_1을 가장 먼저 만나게 되므로, 물리적으로는 서버 1에 저장된다.

가상 노드

가상 노드의 개수를 늘리면 표준 편차가 작아져 키의 분포는 점점 더 완벽한 균등 상태에 가까워진다.
하지만 가상 노드 데이터를 저장할 메모리 공간도 그만큼 더 많이 필요해지므로, 시스템 요구사항에 맞는 적절한 트레이드오프 조정이 필요하다.

표준 편차(Standard Deviation)는 데이터가 평균값으로부터 얼마나 흩어져 있는지를 나타내는 통계 용어이다.
표준 편차가 ‘크다’는 것은 데이터가 서버 2에만 왕창 몰려 있고, 다른 서버는 텅 비어있는 등 들쭉날쭉하다는 뜻이다.
반대로 가상 노드의 개수를 늘려 표준 편차가 ‘작아졌다’는 것은, 모든 서버가 비슷한 양의 데이터를 고르게 나눠 가졌음을 의미한다.

3.3. 노드 변동 시 재배치되는 키의 범위 결정 방식

가상 노드 환경을 이해한 상태에서, 서버가 추가되거나 제거될 때 실제로 데이터가 어떻게 이동하는지 다시 한 번 보자.

서버 추가 시 데이터 이동 범위

아래 그림처럼 새로운 서버 4(s4)가 링에 추가되었다고 해보자.

서버 추가 시 키의 재배치

이에 영향을 받는 범위는 새로 추가된 노드(s4)부터 그 반시계 방향에 있는 첫 번째 노드(s3)까지이다.
즉, s3부터 s4 사이에 있는 키들만 s4로 재배치하면 된다.

서버 삭제 시 데이터 이동 범위

반대로 서버 1(s1)이 장애로 인해 삭제된다면 아래 그림처럼 삭제된 노드(s1)부터 그 반시계 방향에 있는 최초 노드(s0) 사이의 공간이 영향을 받는다.
이 공간에 있던 키들은 오갈 데가 없어졌으므로, 시계 방향을 따라 다음으로 살아있는 노드인 s2로 모두 재배치해주면 된다.

서버 삭제 시 키의 재배치

4. 정리하며..

대규모 아키텍처 설계에서 트래픽을 감당하기 위해 안정 해시는 선택이 아닌 필수 교양이다.
이번 포스트에서 다룬 안정 해시를 시스템에 도입했을 때 얻을 수 있는 3가지 핵심 이점은 다음과 같다.

1)서버 변동 시 데이터 이동 최소화
서버가 추가되거나 삭제될 때 전체 데이터를 다시 섞는 것이 아니라, 링 구조상 인접한 노드의 일부 데이터(평균 \(k/n\)개)만 재배치한다.
덕분에 대규모 캐시 미스로 인한 데이터베이스(DB) 과부하 사태를 막을 수 있다.

2)진정한 수평적 규모 확장성(Scale-out) 달성
가상 노드(Virtual Node) 기법을 통해 데이터를 링 위에 촘촘하고 고르게 분포시킬 수 있어, 유연한 시스템 확장이 가능해진다.

💡데이터가 균등하게 분포하는 것과 수평적 규모 확장은 무슨 관계일까?

만약 데이터가 고르게 분배되지 않고 특정 서버 한 대에만 몰려있다면(데이터 쏠림 현상), 트래픽을 감당하려고 물리 서버를 100대로 늘려도 사용자들의 요청은 여전히 그 1대의 서버로만 향하게 된다.
확장의 의미가 전혀 없는 것이다.
데이터가 모든 서버에 공평하게 쪼개져 있어야만 서버를 1대 추가했을 때 기존 서버들의 짐(부하)을 정확히 덜어줄 수 있고, 전체 시스템의 처리 용량도 추가한 만큼 정비례해서 늘어나는 ‘진정한 수평적 규모 확장’이 가능해진다.

3)핫스팟(Hotspot) 키 문제 방지
특정 데이터(샤드)에 대한 접근이 지나치게 빈번해 발생하는 서버 과부하를 줄여준다.
예를 들어 수천만 명의 팔로워를 가진 유명인의 SNS 게시물 정보가 우연히 한 대의 서버에 집중적으로 저장되는 최악의 상황을 방지하고, 트래픽을 여러 서버로 분산시켜 준다.

실제 상용 시스템의 안정 해시 활용 사례

안정 해시는 실제로 우리가 매일 사용하는 글로벌 IT 기업들의 아키텍처에 깊숙이 자리 잡고 있다.

참고 사이트 & 함께 보면 좋은 사이트

본 포스트는 알렉스 쉬 저자의 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 기반으로 스터디하며 정리한 내용들입니다.




© 2020.08. by assu10

Powered by assu10