일관성 해싱

일관성 해싱은 키를 여러 서버에 나눠 맡기는 방법입니다. 서버를 한 대 더하거나 빼도 주인이 바뀌는 키가 일부에 그칩니다. 해시값을 서버 수로 나눈 나머지로 배정하면 서버 수가 바뀔 때 거의 모든 키가 옮겨집니다. 그 이동을 줄이려고 만든 방법입니다.

상세

이 절은 작은 예 둘로 시작합니다. 먼저 노드를 넷에서 다섯으로 늘리는 예로, 나머지 연산으로 나눌 때 무엇이 깨지는지 봅니다. 그다음 노드 A·B·C 셋을 원 위에 올려 노드를 더하고 뺄 때 무엇이 달라지는지 봅니다.

뒤로 가면서 원 위에 점을 여러 개 찍는 가상 노드, 복제본을 고르는 법, 복잡도, 이 방법이 맞는 경우와 안 맞는 경우를 차례로 다룹니다.

키를 서버에 나눠 맡기는 문제

키는 user:42 처럼 값을 찾을 때 쓰는 이름입니다. 데이터를 여러 서버에 나눠 담으면 키마다 "이 키는 어느 서버에 있나"를 정해야 합니다.

이렇게 데이터를 나눠 담는 일을 샤딩이라고 부릅니다. 한 서버에 다 담기에는 데이터나 요청이 너무 많을 때 씁니다. 나눠 받는 서버 한 대는 여기서 노드라고 부릅니다.

가장 쉬운 방법은 해시 함수를 쓰는 것입니다. 해시 함수는 어떤 입력이든 정해진 범위의 수 하나로 바꿔 줍니다. 같은 입력에는 언제나 같은 수가 나오므로, 그 수로 노드를 고르면 누가 계산해도 같은 노드가 나옵니다.

나머지 연산으로 나눌 때의 이동량

해시값을 노드 수로 나눈 나머지를 노드 번호로 쓰는 방식이 먼저 떠오릅니다. 노드가 넷이면 나머지 0~3이 곧 노드 번호입니다. 조회는 나눗셈 한 번이라 빠릅니다.

문제는 노드 수가 바뀔 때 드러납니다. 노드를 넷에서 다섯으로 늘리면 나누는 수가 바뀌므로 나머지도 바뀝니다.

1234 % 4   // 2
1234 % 5   // 4  주인이 바뀐다
1241 % 4   // 1
1241 % 5   // 1  주인이 그대로다

해시값 1234 인 키는 2번 노드에 있다가 4번 노드로 가야 합니다. 1241 인 키는 운 좋게 1번에 남습니다.

얼마나 남는지 세어 보면 이렇습니다. 해시값 0부터 19까지 스무 개를 넣으면 넷으로 나눈 나머지와 다섯으로 나눈 나머지가 같은 것은 0, 1, 2, 3 넷뿐입니다. 스무 개 중 넷만 남고 열여섯이 옮겨집니다. 다섯 개 중 네 개꼴입니다.

일반으로 쓰면 노드가 N 대에서 N+1 대가 될 때 남는 키는 1/(N+1) 이고, 옮겨지는 키는 N/(N+1) 입니다. 노드가 많을수록 옮겨지는 몫이 1에 가까워집니다. 노드는 한 대 늘었을 뿐입니다. 그런데 키는 거의 전부 옮겨집니다.

이 이동이 곤란한 까닭은 옮기는 동안 데이터가 엉뚱한 노드에서 찾아진다는 데 있습니다. 캐시라면 주인이 바뀐 키는 새 노드에 없으니 캐시 미스가 납니다. 거의 모든 키가 한꺼번에 캐시 미스를 내면 그 요청이 전부 원본 데이터베이스로 몰립니다.

해시 링

일관성 해싱은 나누는 수를 노드 수에 묶지 않습니다. 대신 해시값의 범위 전체를 원으로 봅니다. 가장 큰 값 다음이 다시 0으로 이어지는 원이고, 이것을 해시 링이라고 부릅니다.

예를 들려고 해시값이 0부터 999까지만 나온다고 합시다. 노드 A, B, C 의 이름을 해시해서 각각 100, 400, 700 이 나왔다면, 링 위 100, 400, 700 에 점을 찍습니다.

키도 똑같이 해시해서 링 위에 놓습니다. 그리고 시계 방향으로 걸어가다 처음 만나는 노드가 그 키의 주인입니다. 해시값 250 인 키는 걸어가다 400 에서 B 를 만나므로 B 가 맡습니다. 850 인 키는 999 를 넘어 0으로 돌아간 뒤 100 에서 A 를 만납니다.

flowchart TD
    A["노드 A · 100"] --> B["노드 B · 400"]
    B --> C["노드 C · 700"]
    C -->|"999 다음은 0"| A
    K1["키 250"] -.->|"걸어가서 만남"| B
    K2["키 850"] -.->|"0 을 지나 만남"| A

그림의 화살표가 시계 방향입니다. C 에서 A 로 가는 화살표가 999 에서 0으로 넘어가는 이음매입니다.

그러면 노드마다 맡는 구간이 정해집니다. 노드는 자기 바로 앞 노드 다음부터 자기 위치까지를 맡습니다.

코드로 옮기면 정렬된 맵에서 "이 값 이상인 첫 항목"을 찾는 일입니다. 없으면 링을 한 바퀴 돈 것이니 맨 앞 항목을 씁니다.

TreeMap<Integer, String> ring = new TreeMap<>();
ring.put(100, "A");
ring.put(400, "B");
ring.put(700, "C");

String owner(int h) {
    var e = ring.ceilingEntry(h);
    if (e == null) e = ring.firstEntry();
    return e.getValue();
}

owner(250)   // "B"
owner(850)   // "A"  0 을 지나 처음으로

ceilingEntry 는 주어진 값 이상인 키 중 가장 작은 것을 돌려줍니다. 850 이상인 점이 없으므로 null 이 나옵니다. 그래서 맨 앞의 A 로 넘어갑니다.

노드를 더하거나 뺄 때

노드 D 를 새로 더했더니 해시값이 550 이 나왔다고 합시다. 링 위 550 에 점이 하나 늘어납니다.

영향을 받는 키는 401~550 구간뿐입니다. 이 키들은 전에는 걸어가다 700 에서 C 를 만났습니다. 이제는 550 에서 D 를 먼저 만납니다. 다른 구간의 키는 걸어가는 길에 새 점이 없으므로 주인이 안 바뀝니다.

표에서 바뀐 줄은 C 와 D 둘뿐입니다. 옮겨지는 키는 전부 C 에서 D 로 가고, A 와 B 는 아무것도 주고받지 않습니다.

노드를 뺄 때는 거꾸로입니다. B 가 빠지면 B 가 맡던 101~400 의 키가 시계 방향 다음 노드인 C 로 넘어갑니다. 나머지 노드의 키는 그대로 있습니다.

해시값이 링 위에 고르게 흩어진다고 합시다. 노드가 N 대에서 N+1 대로 늘면 옮겨지는 키는 평균 전체의 1/(N+1) 입니다. 새 노드가 맡을 몫만큼만 움직인다는 뜻입니다. 나머지 연산 방식에서는 N/(N+1), 곧 거의 전부가 움직였습니다.

가상 노드

노드마다 점을 하나씩만 찍으면 구간 길이가 고르지 않습니다. 해시값은 무작위처럼 흩어집니다. 그래서 어떤 두 노드의 점은 가깝게 붙습니다. 어떤 두 노드 사이는 멀리 벌어집니다.

앞의 예에서 D 를 550 에 더하자 C 의 구간은 300 에서 150 으로 줄었습니다. 그런데 A 는 여전히 400 을 맡습니다.

노드를 뺄 때도 고르지 않습니다. 빠진 노드의 키가 전부 바로 다음 노드 한 대로 넘어갑니다. 다음 노드는 갑자기 자기 몫의 두 배 가까이를 떠안게 됩니다.

이 두 문제를 푸는 방법이 가상 노드입니다. 실제 노드 한 대가 링 위에 점을 여러 개 찍습니다. 노드 A 라면 A#1, A#2, A#3 처럼 이름을 달리해 각각 해시합니다. 나온 값마다 점을 찍습니다.

점 하나하나를 가상 노드라 부릅니다. 어느 점에 떨어진 키든 실제로는 A 가 맡습니다.

점이 많아지면 짧은 구간과 긴 구간이 섞여서 노드마다 맡는 총량이 평균에 가까워집니다. 주사위를 한 번 던질 때보다 여러 번 던져 더할 때 합이 평균 근처로 모이는 것과 같습니다.

아래는 A·B·C 가 점을 둘씩 찍어 링 위에 이 순서로 섞인 모습입니다. 화살표가 시계 방향이고, 마지막 B#2 다음은 다시 A#1 입니다.

flowchart TD
    A1["A#1"] --> B1["B#1"]
    B1 --> C1["C#1"]
    C1 --> A2["A#2"]
    A2 --> C2["C#2"]
    C2 --> B2["B#2"]
    B2 --> A1

노드를 뺄 때의 쏠림도 풀립니다. 위 링에서 A 가 빠지면 A#1 이 맡던 키는 다음 점인 B#1 로, A#2 가 맡던 키는 C#2 로 갑니다. A 의 몫이 B 와 C 로 나뉘어 넘어가므로 어느 한 대만 떠안지 않습니다.

점 개수로 노드의 몫을 조절할 수도 있습니다. 메모리가 두 배인 서버에 점을 두 배로 찍으면 평균적으로 키도 두 배를 받습니다.

가상 노드의 대가는 링이 커진다는 것입니다. 노드가 N 대이고 노드마다 점을 V 개 찍으면 링 위 점은 N×V 개입니다. 이 점들을 정렬해 들고 있어야 하니 메모리가 그만큼 듭니다. 조회도 그만큼 큰 목록에서 찾아야 합니다.

복제본을 고르는 법

키 하나를 노드 여러 대에 겹쳐 담는 일을 복제라고 합니다. 한 대가 죽어도 다른 대에서 읽으려는 것입니다. 해시 링 위에서는 복제본을 둘 노드도 같은 규칙으로 고릅니다.

키의 위치에서 시계 방향으로 걸어가며 만나는 노드를 차례로 고릅니다. 복제본을 셋 두려면 처음 만나는 서로 다른 실제 노드 셋을 씁니다. 가상 노드를 쓸 때는 같은 실제 노드의 점을 또 만나면 건너뜁니다. 건너뛰지 않으면 복제본 둘이 한 서버에 담겨 복제한 뜻이 없어집니다.

이렇게 고른 노드의 순서 있는 목록을 선호 목록이라고 부릅니다. 어떤 키의 선호 목록이 [B, C, A] 인데 B 가 빠졌다고 합시다. 목록은 [C, A, 그다음 노드] 가 됩니다. 뒤의 노드가 한 칸씩 앞으로 당겨지고, 끝에 링에서 다음으로 만나는 노드가 붙습니다.

목록이 바뀌는 키는 B 를 목록에 담고 있던 키뿐입니다. 그래서 노드가 빠져도 영향이 링의 일부에 그칩니다.

복잡도

링은 점 M 개를 해시값 순으로 정렬해 둔 목록입니다. 코드에서는 앞의 TreeMap 같은 균형 트리로 들고 있습니다. 넣고 빼고 찾는 일이 모두 로그 시간에 끝나기 때문입니다. 가상 노드를 쓰면 M 은 노드 수 N 에 노드당 점 수 V 를 곱한 값입니다.

나머지 연산 방식과 견주면 무엇을 바꿨는지가 보입니다. 나머지 연산은 조회가 O(1) 입니다. 링을 들고 있을 필요도 없습니다. 대신 노드가 N 대에서 N+1 대로 늘면 전체 키의 약 N/(N+1) 이 옮겨집니다.

일관성 해싱은 조회에 로그 시간과 링 메모리를 냅니다. 그 대신 옮겨지는 키를 전체의 약 1/(N+1) 로 줄입니다.

옮겨지는 몫 1/(N+1) 은 해시값이 링 위에 고르게 흩어진다는 가정 위의 평균입니다. 점이 적으면 한 노드가 평균보다 훨씬 긴 구간을 맡을 수 있습니다. 가상 노드는 이 어긋남을 줄이는 장치입니다.

「일관성」이라는 이름

여기서 일관성은 "노드가 바뀌어도 키 배정이 대부분 전과 같게 유지된다"는 뜻입니다. 원어 consistent hashing 의 consistent 도 그 뜻입니다.

분산 데이터베이스에서 말하는 일관성과는 다른 말입니다. 그쪽은 여러 복제본이 같은 값을 보여 주느냐를 묻습니다. 일관성 해싱을 써도 복제본끼리 값이 맞는다는 보장은 생기지 않습니다. 그 문제는 복제본끼리 값을 맞추는 다른 장치가 맡습니다.

분산 시스템에서 자주 듣는 CAP 정리의 C 도 그쪽 일관성입니다. CAP 는 Consistency, Availability, Partition tolerance, 곧 일관성·가용성·분할 내성의 머리글자입니다. 이름에 같은 낱말이 들어 있어도 일관성 해싱과는 묻는 것이 다릅니다.

맞는 경우와 안 맞는 경우

노드 수가 자주 바뀌는 곳에 맞습니다. 부하에 맞춰 캐시 서버를 늘리고 줄이는 클러스터, 노드가 수시로 죽고 되살아나는 분산 저장소가 그렇습니다. 노드가 바뀔 때마다 거의 전부를 옮기는 비용을 감당할 수 없는 곳입니다.

중앙에 묻지 않고 각자 계산해야 할 때도 맞습니다. 노드 목록과 해시 함수만 같으면 어느 클라이언트든 같은 링을 만들어 같은 답을 냅니다. 키마다 주인을 적어 둔 표를 한 곳에서 관리할 필요가 없습니다.

노드 수가 거의 안 바뀐다면 나머지 연산으로 충분합니다. 조회가 더 쌉니다. 들고 있을 링도 없습니다.

키의 순서가 중요한 경우에도 안 맞습니다. 해시는 가까운 키를 링 위 먼 곳으로 흩어 놓습니다. user:001 부터 user:100 까지 훑는 범위 질의는 모든 노드를 돌아야 합니다. 이럴 때는 키 값의 구간으로 나누는 범위 샤딩이 맞습니다.

해시값을 먼저 정해진 개수의 슬롯에 나눠 담고, 슬롯을 노드에 배정하는 방법도 있습니다. 노드가 바뀔 때 옮길 슬롯을 사람이나 관리 도구가 정합니다. 데이터가 언제 어디로 옮겨 갈지를 직접 통제하고 싶다면 이쪽이 맞습니다. 이 방법은 해시 슬롯에서 다룹니다.

관련 항목

일관성 해싱을 이루는 구성 요소

해시 링 · 가상 노드 · 토큰 · 토큰 링 · 물리 노드 · 해시 함수 · 선호 목록

일관성 해싱이 키를 나눠 맡기는 대상

샤딩 · 샤드 · 파티셔닝 · 노드 · 클러스터 · 로드 밸런서 · 분산 캐시 · 분산 해시 테이블

같은 배정 문제를 두고 겨루는 방식

모듈러 해싱 · 랑데부 해싱 · 점프 일관성 해시 · Maglev 해싱 · 해시 슬롯 · 범위 샤딩 · 룩업 샤딩

노드가 바뀔 때 일관성 해싱이 줄이는 비용

리밸런싱 · 데이터 이동 · 캐시 미스 · 캐시 스탬피드 · 썬더링 허드 · 핫스팟

일관성 해싱 위에 얹히는 복제 장치

복제 · 복제본 · 느슨한 정족수 · 힌티드 핸드오프 · 코디네이터 · 정족수

일관성 해싱을 채택한 제품

memcached · Cassandra · Amazon Dynamo · groupcache

일관성 해싱과 이름이 겹치는 개념

일관성 · CAP · 일관성 모델 · 강한 일관성 · 최종 일관성

조회와 부하 분산을 따지는 도구

이진 탐색 · 균형 이진 탐색 트리 · 생일 문제 · 균등 분포 · 부하 분산