48. 컨시스턴트 해싱 (Consistent Hashing)

⚠️ 이 문서는 수십 대의 서버(노드)로 구성된 NoSQL 데이터베이스(카산드라 등)나 분산 캐시 시스템(Redis)에서, 서버를 새로 추가하거나 고장 난 서버를 빼더라도 전체 데이터의 대대적인 이동(리밸런싱) 폭풍 없이 오직 해당 노드 인근의 데이터만 부드럽게 넘겨주는 가상 링(Ring) 기반의 분산 저장 알고리즘을 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 기존의 단순 나머지 연산(Hash(Key) % N)이 서버 대수(N)가 바뀔 때마다 모든 데이터의 주소를 엉망으로 헝클어뜨리는 치명적인 결함을 해결하기 위해 고안된 '원형 분산 논리'다.
  2. 가치: N대의 서버 중 1대가 고장 나서 N-1대가 되더라도, 전체 데이터의 $1/N$ 만큼만 바로 옆 서버로 이사할 뿐, 나머지 $(N-1)/N$의 데이터는 원래 있던 서버에 그대로 머물러 있어 시스템의 장애 파급을 최소화한다.
  3. 기술 체계: 해시 함수의 출력값을 동그란 원(Ring)으로 말아 데이터와 서버를 동일한 선상에 배치하고, 특정 데이터가 링 위에 떨어지면 시계 방향으로 가장 처음 만나는 서버가 해당 데이터를 소유하는 원리를 따른다.

Ⅰ. 전통적 모듈러(Modulo) 해싱의 재앙

빅데이터 환경에서는 노드가 수시로 죽고 살아나는데, 옛날 방식은 이 변화를 견디지 못한다.

  1. 나머지 연산의 분산:
    • 서버 번호 = Hash(데이터 키) % 서버 총 대수(N)
    • 데이터 '100'이 들어왔고 서버가 3대면, $100 % 3 = 1$이므로 1번 서버에 저장된다.
  2. 서버 추가/삭제 시의 대학살 (Rehash Storm):
    • 만약 3번 서버가 화재로 고장 나면 서버 총 대수가 2대(N=2)로 바뀐다.
    • 갑자기 공식이 $100 % 2 = 0$으로 바뀌면서, 멀쩡히 1번 서버에 잘 있던 데이터마저 0번 서버로 주소가 바뀌어 버린다.
    • 단 한 대의 서버가 죽었을 뿐인데, **시스템 전체 데이터의 90% 이상이 새로운 주소를 찾아 대규모 민족 대이동(리밸런싱)**을 시작하며, 이 과정에서 발생하는 엄청난 네트워크/디스크 부하로 나머지 서버들마저 연쇄적으로 뻗어버리는 대참사가 일어난다.

📢 섹션 요약 비유: 학생 100명을 4반으로 나눌 때 '출석 번호 나누기 4'로 반을 배정했는데, 4반 선생님이 결근했다고 갑자기 100명 전체를 운동장에 모아놓고 '나누기 3'으로 1반부터 끝반까지 처음부터 다 다시 배정하는 미련한 방식입니다.

Ⅱ. 컨시스턴트 해싱 링(Ring)의 발상

MIT에서 제안된 이 개념은 수식을 버리고 '시계방향 위치'라는 기하학적 규칙을 도입했다.

  1. 거대한 해시 링 만들기:
    • 해시 함수의 결괏값(예: $0$ ~ $2^{32}-1$)을 일직선이 아니라 끝과 끝이 만나는 둥근 원(Ring)으로 구부린다.
  2. 서버와 데이터의 배치:
    • 물리 서버 3대(A, B, C)의 IP 주소를 해싱하여 링 위에 3개의 점표를 찍는다. (예: 12시, 4시, 8시 방향)
    • 이제 저장할 유저 데이터(Key)도 해싱하여 링 위에 점을 찍는다.
  3. 가장 가까운 서버 찾기 규칙:
    • 데이터가 링 위의 특정 지점에 떨어지면, 그 자리에서부터 시계 방향(Clockwise)으로 돌면서 가장 먼저 마주치는 서버가 해당 데이터를 자신의 디스크에 저장한다.
  4. 장애가 발생했을 때의 기적:
    • 4시 방향의 서버 B가 죽었다고 치자. 그러면 서버 B가 당담하던 영역의 데이터들만 시계 방향으로 조금 더 흘러가서 8시 방향의 서버 C에게 자연스럽게 흡수된다.
    • 12시 방향의 서버 A가 가진 데이터는 이 사태와 아무런 상관없이 자기 자리에 가만히 있는다. (대규모 리밸런싱 방지)

📢 섹션 요약 비유: 둥근 운동장에 3명의 선생님이 듬성듬성 서 있고, 학생들이 눈을 감고 운동장에 무작위로 착지한 뒤 '오른쪽(시계방향)으로 고개를 돌려 제일 먼저 보이는 선생님' 반으로 가는 겁니다. 한 선생님이 조퇴하면 그 선생님 반 아이들만 조금 더 오른쪽으로 걸어가 다음 선생님 반으로 갈 뿐, 다른 반은 아무 동요가 없습니다.

Ⅲ. 가상 노드 (Virtual Nodes)와 불균형 해소

이론적으로 완벽해 보이지만 현실에서는 운이 나쁘게 링이 편향될 수 있다.

  1. 데이터 쏠림 현상 (Hotspot):
    • 서버 3대를 링에 찍었는데 공교롭게도 12시, 1시, 2시 방향에 다닥다닥 붙어서 찍힐 확률이 있다. 이렇게 되면 2시부터 12시까지의 엄청나게 넓은 공백 영역에 떨어지는 모든 데이터는 12시 서버 한 대가 독박을 써서 터져버린다.
  2. VNode (가상 노드) 튜닝 기법:
    • 이 불균형을 막기 위해 실제 물리 서버 1대당 링 위에 100~200개의 '가상 분신(Virtual Nodes)'을 만들어 링 전체에 골고루 촘촘하게 흩뿌린다. (예: 서버 A-1, A-2... A-100)
    • 이렇게 하면 링이 촘촘해져 특정 구역에 데이터가 몰리더라도 결국 물리 서버 3대가 통계적으로 거의 완벽하게 33%씩 데이터를 나눠 가지게 된다.
    • 고성능 최신 서버를 도입하면 그 서버의 가상 노드 개수를 300개로 늘려 더 많은 데이터를 받게 하는(가중치 조절) 기법으로도 응용된다.

📢 섹션 요약 비유: 세 명의 선생님이 우연히 한쪽 구석에 몰려 서 있으면 반 배정이 불공평해지므로, 각 선생님의 등신대(판넬 분신) 100개씩을 만들어 운동장 전체에 골고루 촘촘하게 세워두어 100명의 학생이 아주 공평하게 나뉘도록 만든 마법입니다.