Redis ‐ Hash Slot Rebalancing - thought-corner/Backend-PlayGround GitHub Wiki

Redis - Hash Slot Rebalancing

Hash Slot

1. 키 입력

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

2. CRC16 해시 계산

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

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

• 레디스 클러스터는 전체 데이터를 16,384개의 슬롯으로 나누어 관리한다.
• 해시값을 16,384로 나눈 나머지 값을 구하면 이 키가 들어갈 슬롯 번호가 결정된다.

4. 슬롯 번호 결정

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

5. 마스터 노드로 매핑

• 클러스터에 참여 중인 각 마스터 서버들은 전체 슬롯 중 일부 구역을 담당한다.

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

• 서버 추가/제거가 매우 쉽다. : 만약 서버를 한 대 더 추가하면 기존 서버들이 가진 슬롯 중 일부를 새로운 서버로 옮겨주기만 하면 된다.
• 데이터가 골고루 분산된다 : 해시 알고리즘 덕분에 특정 서버에만 데이터가 몰리지 않고 여러 마스터 노드에 데이터가 균등하게 퍼져 전체 시스템의 부하가 분산된다.

Sharding

1. 클라이언트의 요청

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

2. 슬롯 계산 및 체크

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

3. MOVED 응답 반환

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

4. 재요청

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

5. 성공

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

Cluster Rebalancing

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

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

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

• 슬롯이 A 노드에서 B 노드로 이동 중일 때 요청이 들어오면 다음과 같은 단계를 거치게 된다.
  • 상태 표시 : 소스 노드는 MIGRATING, 타겟 노드는 IMPORTING 상태가 된다.
  • 데이터 이동 : 키를 한꺼번에 옮기지 않고, 점진적으로 복사한다.

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

• MOVED(영구적 이동) : 클라이언트가 이 응답을 받으면 자신의 슬롯 맵을 갱신하여 다음부터는 바로 새로운 노드로 간다.
• ASK(임시 이동) : 마이그레이션 중이라 다른 노드에 요청을 보내라는 의미이다.

4. 리밸런싱(Rebalancing)

• 특정 노드에 데이터나 부하가 쏠렸을 때, 균형을 맞추는 자동화 과정이다.
  • 불균형 감지 : 노드당 슬롯 분포를 분석
  • 목표 계산 : 전체 슬롯을 노드 수로 나누어 이상적인 슬롯 수를 산출
  • 최소 이동량 계획 : 네트워크 부하를 줄이기 위해 가장 효율적인 이동 경로를 계산해 무중단으로 실행