taeknology/notes

[Redis] 해시 슬롯 16384: 클러스터 데이터 분배 원리

한 줄 요약: 레디스 클러스터는 키 공간을 16384개의 해시 슬롯 으로 고정 분할하고, CRC16(key) mod 16384 로 키를 슬롯에 매핑한 뒤 슬롯을 노드에 분배함. 16384라는 숫자는 Gossip 메시지의 슬롯 비트맵을 2KB(2048바이트)로 유지 하면서도 재샤딩 해상도를 충분히 확보하기 위한 설계 균형점임.

샤딩 규칙 개요

레디스 클러스터의 샤딩은 “키 → 슬롯 → 노드” 2단 매핑으로 동작함.

  1. 키 공간을 16384개 슬롯으로 미리 쪼개 둠. 슬롯은 키와 노드 사이의 논리적 중간층임.
  2. 키 → 슬롯 매핑은 CRC16(key) mod 16384 로 결정됨. 공식이 결정적이라 클라이언트와 서버가 독립적으로 계산해도 같은 답이 나옴.
  3. 슬롯 → 노드 매핑은 운영자가 지정함. 노드 추가/삭제 시 “몇 번 슬롯을 어디로” 단위로만 재분배하면 됨. 키를 하나하나 재해싱하지 않음.

이 중간층 덕분에 키 분포와 노드 구성이 분리됨. 클라이언트는 키만 보고 목적지를 계산할 수 있고, 운영자는 대규모 키 재해싱 없이 슬롯 단위로 재샤딩할 수 있음.

결론

왜 이런 설계인가

질문답변
왜 샤딩이 필요한가레디스는 인메모리 저장소라 물리 RAM이 곧 데이터 상한임. 스케일 업은 곧 한계에 부딪히므로 스케일 아웃(샤딩)이 필수임.
왜 “슬롯” 이라는 중간층인가키를 직접 노드에 매핑하면 노드 추가/삭제 때마다 대규모 재해싱이 필요함. 슬롯을 두면 “슬롯 단위” 로만 재분배하면 됨.
왜 CRC16인가빠르고(매 명령마다 계산), 분포가 균일하고, 결정적임. MD5/SHA 같은 암호학적 해시는 클러스터 목적에 비해 오버헤드가 큼.
왜 하필 16384인가Gossip 메시지에 실리는 슬롯 비트맵 크기가 2KB로 작고, 1000노드 규모에서도 노드당 평균 ~16 슬롯으로 재샤딩 해상도가 충분함.

운영 시 기억할 것

  • 키 이름만 보면 어느 노드에 저장될지 로컬에서 계산 가능 함. 스마트 클라이언트가 이를 활용해 첫 요청부터 올바른 노드로 감.
  • 노드 추가/제거 시 이동하는 것은 슬롯 범위 이지 개별 키가 아님. 재샤딩 명령도 “몇 번~몇 번 슬롯을 어디로” 로 내려감.
  • 단일 레디스에서 쓰던 다중 키 연산(MGET, 트랜잭션 등)은 키들이 같은 슬롯 에 있어야만 동작함. 흩어져 있으면 CROSSSLOT 에러가 남.

상세

1. 왜 단일 노드로는 부족한가

레디스는 인메모리 저장소임. 모든 데이터가 RAM 위에 있음. 빠른 만큼, 물리 메모리 크기가 곧 데이터 상한이 됨.

예를 들어 32GB 장비 한 대에 레디스를 올리면 쓸 수 있는 데이터 용량은 30GB 안팎임 (OS/버퍼 제외). 서비스 데이터가 80GB로 자라는 순간 이 장비로는 감당이 안 됨. 선택지는 두 가지임.

  • 스케일 업(scale-up): 더 큰 장비로 옮김. 한계가 금방 옴. 수직 확장은 비용이 지수적으로 증가함.
  • 스케일 아웃(scale-out): 여러 장비에 데이터를 나눠 담음. 이게 샤딩(sharding) 임.

레디스 클러스터는 스케일 아웃을 위해 설계된 공식 샤딩 모드임. 그리고 그 샤딩 규칙의 핵심이 해시 슬롯 임.

2. 해시 슬롯 — 키와 노드 사이의 중간층

레디스 클러스터는 키 공간 전체를 16384개의 슬롯(slot) 으로 미리 쪼개 둠. 키 하나가 어떤 노드에 저장될지는 “이 키가 어느 슬롯에 속하는가” 만으로 결정됨.

graph TD
    subgraph Key_Space [전체 키 공간: 슬롯 0 ~ 16383]
        S1[슬롯 0 ~ 5460]
        S2[슬롯 5461 ~ 10922]
        S3[슬롯 10923 ~ 16383]
    end

    NodeA[(노드 A)]
    NodeB[(노드 B)]
    NodeC[(노드 C)]

    S1 --> NodeA
    S2 --> NodeB
    S3 --> NodeC
  • 노드를 추가하면 슬롯 단위로만 재분배가 일어남. 키를 하나하나 재해싱하지 않음.
  • 운영자는 “몇 번~몇 번 슬롯을 이 노드로 옮긴다” 로 재샤딩을 명령함. 키 목록을 건드릴 필요가 없음.

슬롯은 논리적 단위임. 클러스터 내부에서는 “키 → 슬롯 → 노드” 2단 매핑으로 동작함. 이 중간층 덕분에 노드 추가/삭제와 키 분포가 분리됨.

3. 키 → 슬롯 매핑 공식

공식은 매우 단순함.

slot = CRC16(key) mod 16384
  1. 키 문자열을 CRC16 해시 함수에 넣음.
  2. 결과를 16384로 나눈 나머지 를 슬롯 번호로 씀.

예시:

CRC16("user:1000")  mod 16384 = 1649
CRC16("order:42")   mod 16384 = 8691
CRC16("session:ab") mod 16384 = 9201

위 값은 Redis 7.4 클러스터 모드에서 redis-cli CLUSTER KEYSLOT <key> 로 직접 검증한 실측치임.

이 규칙은 클라이언트와 서버가 동일하게 따름. 그래서 스마트 클라이언트는 키만 보고도 “이 명령은 어느 노드로 보내야 하는지” 계산할 수 있음. 엉뚱한 노드에 보내면 MOVED <slot> <ip:port> 응답이 돌아오고, 클라이언트는 내부 슬롯 맵을 갱신함.

왜 CRC16인가

  • 빠름: 단순 비트 연산 기반. 매 명령마다 키 해시를 계산하므로 MD5/SHA 같은 암호학적 해시의 오버헤드를 감당할 이유가 없음.
  • 분포가 충분히 균일: 클러스터 목적에는 충돌 내성보다 균등 분포가 중요함. CRC16이 이 조건을 만족함.
  • 결정적: 같은 키는 항상 같은 슬롯으로 감. 클라이언트와 서버가 독립적으로 계산해도 결과가 일치함.

4. 왜 하필 16384인가 (2^14)

“왜 65536도 아니고 4096도 아닌 16384인가?” 는 자주 나오는 질문임. 안티레즈(antirez, Salvatore Sanfilippo)의 공식 답변은 Gossip 메시지 크기 최적화 임. 여기서 Gossip이란 클러스터 노드들이 주기적으로 서로의 상태(어떤 슬롯을 누가 담당하는지 등)를 주고받는 통신 방식임.

슬롯 수비트맵 크기재샤딩 해상도 (1000 노드 기준)평가
1024128 B노드당 평균 1 슬롯너무 거칠어서 부적절
4096512 B노드당 평균 4 슬롯여전히 부족
163842 KB노드당 평균 ~16 슬롯균형점 (채택)
655368 KB노드당 평균 ~65 슬롯메시지 오버헤드 4배
  • 각 노드는 클러스터 버스(cluster bus) 로 주기적으로 상태를 주고받음. 이 메시지에 “내가 담당하는 슬롯 목록” 이 비트맵(bitmap) 으로 들어감.
  • 16384비트 = 2KB, 65536비트 = 8KB. 수백~수천 노드가 초당 여러 번 주고받는 메시지에서 이 4배 차이는 네트워크·CPU 비용으로 직결됨.
  • 반대로 슬롯 수가 너무 적으면 한 슬롯에 너무 많은 키가 몰려 재샤딩 단위가 거칠어짐.

즉 “메시지 크기 ↔ 재샤딩 해상도” 트레이드오프의 균형점이 16384임. 설계자는 대규모 클러스터를 1000 노드 이하 로 가정했기 때문에 이 숫자로 충분히 커버됨.

참고

관련 글