일관된 해시

가장 자연스러운 규칙이 가장 위험하다

샤드가 4개일 때, 어떤 키를 어느 샤드에 넣을지 정하는 가장 쉬운 방법은 이것입니다.

샤드 번호 = 키를 숫자로 바꾼 값 % 4

%는 나머지입니다. 키를 숫자로 바꿔 4로 나눈 나머지가 0이면 0번 샤드, 1이면 1번 샤드에 넣습니다. 간단하고, 고르게 퍼지고, 언제나 같은 답이 나옵니다. 완벽해 보입니다.

그런데 샤드를 하나 늘리면

트래픽이 늘어 샤드를 5개로 늘립니다. 이제 규칙은 % 5가 됩니다. 키 몇 개만 따라가 봅시다.

참담합니다. 계산해 보면 약 80%의 키가 자리를 옮겨야 합니다. 샤드를 하나 추가했을 뿐인데 데이터 대부분이 이사를 갑니다.

이게 무슨 뜻일까요. 이사가 끝날 때까지 찾는 곳에 데이터가 없습니다. 캐시라면 전부 헛탕이고, 데이터베이스라면 그 데이터는 사라진 것과 같습니다. 그동안 원본 저장소로 요청이 폭주해서 시스템 전체가 무너집니다.

서버를 늘려서 서비스를 죽이는 겁니다. 그것도 트래픽이 가장 많은 날에요.

시계 문자판에 올려 보자

일관된 해시의 아이디어는 놀랍도록 단순합니다.

동그란 시계 문자판을 상상하세요. 0시부터 12시까지 돌아가는 원입니다.

1. 서버들을 문자판 위 어딘가에 올려 둡니다. 서버 A는 2시, B는 5시,

C는 8시, D는 11시 자리라고 합시다.

1. 키도 계산해서 문자판 위의 한 지점에 올립니다. 어떤 키가 3시 방향에

떨어졌다고 합시다.

1. 거기서 시계 방향으로 돌다가 처음 만나는 서버가 그 키의 주인입니다.

3시에서 시계 방향으로 가면 5시의 B를 먼저 만납니다. 그러니 B가 주인입니다.

            12시
        D ●      ● (11시)
     ┌─────────────────┐
9시  │                 │  3시  ← 키가 여기 떨어짐
  C ●│                 │↓ 시계 방향으로 돌다가
(8시)│                 │  B를 만남 → B가 주인
     └─────────────────┘
            ● B (5시)
            6시

서버 하나가 빠지면

C(8시)가 고장 났습니다. C를 문자판에서 지웁니다.

그러면 원래 C에게 가던 키들만 시계 방향으로 조금 더 돌아 D(11시)를 만나게 됩니다. 나머지 키들은 아무 일도 없었던 것처럼 그대로입니다. A와 B는 자기 자리에 그대로 있으니까요.

이것이 전부입니다. % N 방식에서 80%가 이사하던 일이, 일관된 해시에서는 C의 몫인 약 25%만 이사합니다.

왜 이런 차이가 나는가

한 문장으로 말하면 이렇습니다.

나머지 연산은 서버 개수를 계산에 넣기 때문에 개수가 바뀌면 모든 답이 바뀝니다. 일관된 해시는 서버의 위치만 보기 때문에, 사라진 서버 주변만 영향을 받습니다.

남은 문제 하나

C가 빠지면 C의 몫이 전부 D에게 갑니다. D는 갑자기 두 배의 일을 하게 됩니다. 그러다 D도 못 견디고 쓰러지면 그 몫이 다시 A에게 가고... 이렇게 도미노처럼 무너지는 걸 연쇄 장애라고 합니다.

그래서 실무에서는 두 가지를 합니다.

1. 가상 노드 — 서버 하나를 문자판 위 여러 지점에 올려 둡니다. C를

8시에만 두지 않고 8시, 1시, 6시 세 곳에 둡니다. 그러면 C가 빠질 때 그 몫이 여러 서버에 잘게 나뉘어 갑니다. 한 명이 다 뒤집어쓰지 않습니다.

1. 여유 확보 — 각 서버를 평소에 100% 채워 두지 않습니다. 한 대가 빠져도

남은 서버들이 그 몫을 흡수할 빈 자리를 미리 남겨 둡니다.

아래 과제는 두 번째를 다룹니다. 샤드 하나가 실제로 죽었을 때, 링에 남은 샤드들이 그 몫을 받아낼 수 있는지 직접 확인해 보세요.