Redis ‐ Hash Slot Rebalancing - thought-corner/backend-roadmap GitHub Wiki

1. 키 입력

• 사용자가 저장하고 싶은 데이터의 키값으로 어떤 문자열이든 올 수 있다.

2. CRC16 해시 계산

• 레디스는 입력받은 키를 CRC16이라는 알고리즘을 통해 해싱한다.
• 이 과정을 거치면 어떤 길이의 키라도 일정한 규칙을 가진 숫자 형태의 해시값으로 변환된다.

3. 해시값 % 16384(모듈러 연산)

• 레디스 클러스터는 전체 데이터를 16,384개의 슬롯으로 나누어 관리한다.
• 해시값을 16,384로 나눈 나머지 값을 구하면 이 키가 들어갈 슬롯 번호가 결정된다.
• 즉 slot = CRC16(key) mod 16384 한 줄이 전부다. 어느 노드에 물어봐도 같은 키는 같은 슬롯 번호가 나온다.

4. 슬롯 번호 결정

• 계산 결과 키는 N번 슬롯에 할당된다.

5. 마스터 노드로 매핑

• 클러스터에 참여 중인 각 마스터 서버들은 전체 슬롯 중 일부 구역을 담당한다.
• 예를 들어 마스터가 3대라면 0~5460, 5461~10922, 10923~16383 식으로 나눠 갖는다.
• 16,384개 슬롯 중 하나라도 담당 노드가 없으면 클러스터 전체가 요청을 거부한다.(cluster-require-full-coverage yes가 기본값) 노드 장애 시 클러스터가 통째로 멈추는 이유가 이것이다.

왜 이런 복잡한 방식을 쓰는지?

• 서버 추가/제거가 매우 쉽다. : 만약 서버를 한 대 더 추가하면 기존 서버들이 가진 슬롯 중 일부를 새로운 서버로 옮겨주기만 하면 된다.
• 데이터가 골고루 분산된다 : 해시 알고리즘 덕분에 특정 서버에만 데이터가 몰리지 않고 여러 마스터 노드에 데이터가 균등하게 퍼져 전체 시스템의 부하가 분산된다.
• 키를 직접 노드에 매핑했다면 노드 수가 바뀔 때마다 모든 키의 위치가 재계산되어야 한다. 슬롯이라는 중간 계층을 두어 노드 수와 키 배치를 분리한 것이 핵심이다.

왜 하필 16,384개인가?

• 2^14 = 16,384다. 노드들은 자신이 담당하는 슬롯 정보를 비트맵으로 만들어 클러스터 버스로 주고받는데, 16,384비트는 2KB에 불과해 하트비트마다 전송해도 부담이 적다.
• 65,536(2^16)으로 하면 비트맵이 8KB가 되어 통신 비용이 커진다. Redis Cluster가 현실적으로 상정하는 노드 수(최대 1,000대 규모)에는 16,384면 충분히 세밀하다.

• 슬롯이 다르면 여러 키를 한 명령으로 다룰 수 없다. MSET, SINTER, MULTI, Lua 스크립트 모두 모든 키가 같은 슬롯에 있어야 한다.
• 다른 슬롯의 키를 함께 다루려 하면 CROSSSLOT 에러가 발생한다.

MSET user:100:profile "..." user:100:cart "..."
# (error) CROSSSLOT Keys in request don't hash to the same slot

# 해시 태그 : {} 안의 문자열만 해싱 대상이 된다
MSET user:{100}:profile "..." user:{100}:cart "..."
# OK   ← 둘 다 CRC16("100") % 16384 로 같은 슬롯

CLUSTER KEYSLOT user:{100}:profile   # 슬롯 번호 확인

• 해시 태그를 남용하면 특정 슬롯에 데이터가 몰려(hot slot) 분산 효과가 사라진다. 함께 다뤄야만 하는 키에만 최소한으로 사용해야 한다.

1. 클라이언트의 요청

• 클라이언트는 키를 저장하기 위해 아무 마스터 노드에게 요청을 보낸다.

2. 슬롯 계산 및 체크

• 요청을 받은 마스터는 즉시 해당 키의 해시 슬롯을 계산하고 계산 결과, 이 키는 N번 슬롯에 해당한다는 것을 알게 된다.
• 하지만 마스터 1은 자기 자신이 N번 슬롯을 담당하고 있지 않다는 사실을 확인하게 된다.

3. MOVED 응답 반환

• 마스터 1은 데이터를 저장하는 대신 클라이언트에게 N번 슬롯이 자기가 담당하는 슬롯이 아니기 때문에 다른 마스터 노드로 가라고 주소를 가르쳐주는데 이를 MOVED 에러라고 한다.

-MOVED 3999 127.0.0.1:7002
       └슬롯  └ 담당 노드 주소

4. 재요청

• 가이드를 받은 클라이언트는 알려준 주소로 다시 요청을 보낸다.

5. 성공

• 자기 구역의 요청을 받은 마스터는 정상적으로 데이터를 저장하고 응답을 보낸다.

• 매번 이렇게 두 번 왕복하면 느리다. 그래서 클러스터 인식 클라이언트(Lettuce, redis-cli -c 등)는 처음 접속 시 슬롯 → 노드 맵을 받아 캐싱하고, 이후에는 곧바로 올바른 노드로 요청한다. MOVED를 받으면 맵이 낡았다는 신호로 보고 갱신한다.

1. 노드 추가 및 제거(Scale Out / In)

• 노드 추가 : 새로운 서버가 시작되면 기존 클러스터에 조인(HandShake)한다. 처음엔 할당된 슬롯이 0개인 빈 마스터 상태가 되며, 이후 기존 노드들로부터 슬롯을 균등하게 배분받는 계획을 세운다.
• 노드 제거 : 해당 노드가 가진 모든 슬롯을 다른 노드로 마이그레이션을 한 후 비워진 노드를 클러스터에서 제거한다.

# 노드 추가 → 슬롯은 0개인 상태로 합류
redis-cli --cluster add-node 127.0.0.1:7004 127.0.0.1:7000

# 슬롯 재분배 (대화형으로 개수·출발지·목적지 지정)
redis-cli --cluster reshard 127.0.0.1:7000

# 균등하게 자동 계산해 재분배
redis-cli --cluster rebalance 127.0.0.1:7000

# 노드 제거 (슬롯을 먼저 비워야 한다)
redis-cli --cluster del-node 127.0.0.1:7000 <node-id>

2. 슬롯 마이그레이션 상태와 요청 처리

• 슬롯이 A 노드에서 B 노드로 이동 중일 때 요청이 들어오면 다음과 같은 단계를 거치게 된다.
  • 상태 표시 : 소스 노드는 MIGRATING, 타겟 노드는 IMPORTING 상태가 된다.
  • 데이터 이동 : 키를 한꺼번에 옮기지 않고, 점진적으로 복사한다.
• 이동 중에도 서비스는 중단되지 않는다. 소스 노드는 요청받은 키가
  • 아직 자신에게 있으면 → 그대로 처리한다.
  • 이미 옮겨졌거나 없으면 → ASK 응답으로 타겟 노드를 알려준다.
• 마지막에 CLUSTER SETSLOT <slot> NODE <target-id>로 소유권을 확정하면 그때부터 MOVED가 반환된다.

3. 리다이렉션 타입 : MOVED vs ASK

• ASK에서 맵을 갱신하면 안 되는 이유는 아직 이동이 끝나지 않았기 때문이다. 같은 슬롯의 다른 키는 여전히 소스 노드에 있을 수 있으므로, 맵을 미리 바꾸면 오히려 잘못된 노드로 가게 된다.
• ASKING은 "이 요청은 마이그레이션 때문에 온 것이니 아직 내 슬롯이 아니어도 처리해달라"는 표시다. 이것이 없으면 타겟 노드는 자기 슬롯이 아니라며 MOVED로 돌려보낸다.
• 마이그레이션 중 여러 키를 다루는 명령은 키들이 소스·타겟에 흩어져 있으면 TRYAGAIN 에러가 날 수 있다. 잠시 후 재시도하면 된다.

4. 리밸런싱(Rebalancing)

• 특정 노드에 데이터나 부하가 쏠렸을 때, 균형을 맞추는 과정이다.
  • 불균형 감지 : 노드당 슬롯 분포를 분석
  • 목표 계산 : 전체 슬롯을 노드 수로 나누어 이상적인 슬롯 수를 산출
  • 최소 이동량 계획 : 네트워크 부하를 줄이기 위해 가장 효율적인 이동 경로를 계산해 무중단으로 실행
• Redis Cluster는 리밸런싱을 스스로 하지 않는다. 노드를 추가해도 슬롯이 저절로 넘어오지 않으며, redis-cli --cluster rebalance(또는 reshard)를 운영자가 직접 실행해야 한다. 자동으로 이루어지는 것은 슬롯 재분배가 아니라 장애 시 Replica의 Master 승격(Failover) 이다.
• 실행 중 주의할 점
  • 슬롯 이동은 키를 하나씩 옮기므로 큰 키(수백만 요소의 컬렉션)가 있으면 그 키를 옮기는 동안 양쪽 노드가 블로킹된다. 거대한 키는 미리 쪼개두는 것이 안전하다.
  • 트래픽이 적은 시간대에 수행하고, --cluster-timeout으로 여유를 두는 것이 좋다.
  • 진행 상황은 redis-cli --cluster check로 확인한다.