무지의 시작
문득 강의를 듣다가 Redis의 Cluster 구조에서는 각 노드에 어떻게 데이터가 분배되는지가 궁금해졌다. 사실은 클러스터 구조에서 mod16384 연산을 통해 얻은 해싱 값이 특정 해시 슬롯에 저장이 된다고 착각하는 바람에 시간을 너무 많이 썻고 결국은 내 오해였다는 헤프닝이었지만,, 분명 나중에 까먹을거같아서 다시 정리해보기로 했다. 질문은 내가 GPT한테 잘 정리해서 물어봤고 대답도 잘 받았따. 일단 정리는 안하고 복붙을 하고 나중에 정리하려고 한다.
물론 이는 내가 DB의 Cluster 구조를 잘 모른 상태로 고민을 한참 했어서... 삽질을 아주 기똥차게 해댔다..
질문폭격1
강의를 들으면서 제가 아는 해시 테이블의 개념과 조금 헷갈려서 질문을 남깁니다.
일반적으로 해시 테이블은 특정한 값이 들어오면 어떤 연산을 통해 해싱을 합니다. 그리고 해싱된 값을 통해 이 데이터가 어떠한 버킷의 어떤 슬롯에 담기는지를 정하게 됩니다.
그리고 여기에서 논리적으로 해시충돌이 일어나면 이를 해결할 수 있습니다. 여기에서는 데이터가 실제로 담기기 때문에 이러한 충돌이 발생할 수 있고 해결 또한 해야하죠.
근데 Redis의 클러스터에서는 어떤 데이터가 들어온다면 모듈러 연산을 통해 얻은 해시 값이 특정 노드에 속하는지를 판단한다고 강의를 들었습니다.
예) 노드 A : 0~ 4819 노드 B: 4820~16383
이 때 해싱을 통해 얻은 값이 4819라면 해당 데이터는 노드A에 속하게 되고 노드A에 연결된 DB에 데이터가 저장이 되겠죠 ?
이 때 해쉬 슬롯은 단순히 너는 노드A로 가라. 너는 노드B로 가라 라고 연결다리 역할만 하는건지 궁금합니다.
실제로 해쉬 슬롯은 노드를 나누기 위한 논리적인 숫자에 불과하며 실제 슬롯에는 그 어떠한 값도 저장하고 있지 않는 것인지가 너무 헷갈립니다.. 제가 해쉬 테이블의 개념만 너무 생각해서 그런건지 잘 모르겠습니다 ..
추가적으로 실제 DB에서는 Hash Table 방식으로 데이터를 처리한다고 했으니 실질적인 해시 충돌인 여기에서 일어나면서 해결 또한 이 지점에서 하겠죠 ?
답변1
- "해시 슬롯은 단순히 연결 다리 역할만 하는가?"
네, 맞습니다. Redis 클러스터에서 해시 슬롯(Hash Slot)은 단순히 키를 기준으로 데이터가 어느 노드로 가야 할지 매핑하는 논리적 개념입니다.
해시 슬롯 자체에는 데이터가 저장되지 않습니다.
해시 슬롯은 CRC16(key) % 16384 계산을 통해 나온 해시 값을 어느 노드에 배치할지를 결정하는 역할만 수행합니다.
따라서, 해시 슬롯은 노드를 나누기 위한 논리적인 숫자일 뿐, 그 자체에는 어떤 값도 저장되지 않습니다.
이를 해시 테이블의 기본 개념과 혼동하기 쉽지만, Redis 클러스터에서의 해시 슬롯은 매핑 정보의 중개자 역할이라고 보시면 됩니다.
- "실제 데이터는 어디에 저장되는가?"
해시 슬롯이 매핑한 노드에서, 데이터는 Redis 서버의 내부 DB에 저장됩니다.
Redis의 내부 DB는 Hash Table 구조를 사용합니다.
키를 통해 데이터를 저장하거나 조회하며, 해시 충돌이 발생할 경우 내부적으로 이를 처리합니다.
즉, 실제 해시 충돌은 해시 슬롯이 아니라 각 노드의 Hash Table에서 발생하며, 처리도 해당 Hash Table에서 이루어집니다.
노드 A, 노드 B는 서로 독립적인 Hash Table을 가지고 있으며, 키가 매핑된 데이터는 해당 노드의 Hash Table에서 저장 및 관리됩니다.
- "해시 충돌은 어디에서 발생하며, 어떻게 해결되는가?"
해시 충돌은 Redis의 클러스터 외부에서 발생하는 것이 아니라, 각 노드 내부의 Hash Table에서 발생합니다.
예를 들어, 동일한 해시 슬롯(예: 4819번)에 매핑된 키 key1과 key2가 노드 A로 보내졌다고 가정합니다.
노드 A 내부에서는 이 키-값 쌍이 Hash Table에 저장되는데, Hash Table의 버킷 충돌이 발생할 수 있습니다.
Redis는 이러한 충돌을 해결하기 위해 Separate Chaining(체이닝) 방식을 사용합니다:
버킷마다 연결 리스트(Linked List)를 만들어 동일한 버킷에 매핑된 데이터를 저장합니다.
따라서, 실제 해시 충돌과 그 해결 과정은 해시 슬롯이 아니라 각 노드의 Hash Table에서 이루어진다고 이해하시면 됩니다.
- Redis 클러스터의 해시 슬롯과 해시 테이블의 차이점
해시 슬롯 (Hash Slot)
역할: 데이터가 어느 노드에 저장될지 결정하는 논리적 매핑 개념.
데이터 저장 여부: 저장하지 않음.
해시 슬롯은 "어떤 키가 어떤 노드로 가야 한다"는 정보만 제공합니다.
개수: 고정적으로 16384개로 설정되어 있으며, 클러스터의 논리적 파티션 단위입니다.
노드 내부의 해시 테이블
역할: 실제 데이터를 저장하거나 조회.
데이터 저장 여부: 저장함.
각 노드의 Hash Table에는 실제 데이터가 저장됩니다.
해시 충돌 해결: Separate Chaining 방식으로 처리. - 질문에 대한 요약 답변
해시 슬롯은 단순히 노드를 나누기 위한 논리적인 숫자에 불과한가?
맞습니다. 해시 슬롯은 데이터를 특정 노드에 매핑하기 위한 논리적 연결 다리일 뿐, 데이터를 직접 저장하지 않습니다.
실제 데이터는 어디에 저장되며, 해시 충돌은 어디서 발생하는가?
데이터는 매핑된 노드의 Hash Table에 저장됩니다.
해시 충돌은 각 노드의 Hash Table에서 발생하며, Separate Chaining 방식을 사용해 충돌을 해결합니다.
해시 슬롯과 실제 DB(노드의 Hash Table)의 역할은 어떻게 다른가?
해시 슬롯은 논리적 매핑 정보를 제공하며, 데이터 저장은 하지 않습니다.
실제 데이터 저장과 관리(충돌 해결 포함)는 각 노드의 Hash Table에서 수행됩니다.
그 외 내가 Cluster 구조를 알지 못했을 때 질문한 내용
내가 궁금한 부분은 해쉬 슬롯 하나의 구조가 내부적으로 어떻게 이루어져 있기 떄문에 여러 개의 Key-Value 쌍의 값을 거의 용량이 허락하는 한 무한대로 저장할 수 있는지 궁금해. 하나의 해쉬 슬롯에 여러 데이터가 쌓이면 결국에는 O(1)의 시간복잡도가 아닌 선형 방식의 시간 복잡도 O(N)이 되게 되잖아 ?
예: 5461번 해시 슬롯은 현재 노드 B가 담당 중이라면, 해당 키와 데이터를 노드 B에 저장합니다.
너가 이렇게 말했는데 노드B는 해당 데이터를 어디에다가 저장하는거야 ?
각 노드에 배정된 해쉬 슬롯에는 어떤 데이터가 저장되고 어떠한 구조로 이루어져있는지 궁금해
만약 a,b 라는 데이터가 해싱을 통해 똑같이 5481의 해싱값을 얻었다면 Redis에서는 이를 어떻게 처리해 ?
그리고 Hash Slot은 Redis 내부에서 관리하는 일종의 값으로 데이터가 어느 샤드에 매핑이 될지에 대한 정보만 아주 간략하게 담고 있는거야 ?
아니면 해시 슬롯에 매핑된는 해쉬값을 통해서 이 데이터는 노드B로 가시오.. 라고 안내만 해주고 이 데이터가 노드B에 저장되어있다는 정보 자체를 아예 가지고 있지 않고 통신이 끝나면 삭제해버려 ?
답변
좋은 질문입니다! Redis의 내부 동작 원리를 깊이 파악하고 싶어 하시는 것 같아, 하나씩 명확히 정리해드릴게요.
- 해시 슬롯에 데이터가 어떻게 저장되는지
해시 슬롯(Hash Slot)은 Redis 클러스터의 논리적 개념입니다.
키를 해싱해서 얻은 결과 값을 어떤 샤드(노드)에 매핑할지 결정하는 역할만 합니다.
해시 슬롯 자체에는 실제 데이터가 저장되지 않습니다.
즉, 해시 슬롯은 매핑 정보만 담고 있으며, 데이터를 저장하지 않습니다. - 노드(샤드)에 데이터가 어떻게 저장되는지
데이터가 매핑된 샤드(노드)는 Redis 내부의 실제 데이터 저장소로, 다음과 같은 구조로 데이터를 저장합니다:
Redis는 내부적으로 Hash Table 구조를 사용합니다.
노드(샤드)에 할당된 데이터는 키-값 쌍 형태로 Hash Table에 저장됩니다.
키 값이 동일한 해시 슬롯에 매핑되더라도 노드의 Hash Table에서 키 충돌을 처리할 수 있습니다. - 키 충돌이 발생하면 어떻게 처리하는가?
예를 들어, a와 b라는 데이터가 동일한 해시 슬롯(예: 5481번)에 매핑된 경우:
해시 슬롯의 역할:
해시 슬롯은 "이 데이터는 노드 B로 가시오"라는 역할만 합니다.
즉, a와 b 모두 노드 B로 전달됩니다.
노드 B 내부에서의 처리:
노드 B는 내부적으로 Hash Table 구조를 사용합니다.
동일한 해시 슬롯에 매핑된 키(a, b)는 해시 충돌이 발생할 수 있습니다.
해시 충돌을 처리하기 위해 Redis는 Separate Chaining(체이닝) 방식을 사용합니다:
각 버킷(Hash Table의 슬롯)에 연결 리스트(Linked List)를 사용해 데이터를 저장합니다.
동일한 슬롯에 매핑된 데이터는 이 연결 리스트에 추가됩니다.
결과:
a와 b는 동일한 슬롯(5481번)에 매핑되었지만, 노드 B의 Hash Table 내에서 다른 위치에 저장됩니다.
따라서 데이터를 조회하거나 저장하는 시간 복잡도는 여전히 평균적으로 O(1)에 가깝습니다.
(해시 충돌이 많을수록 O(N)에 가까워지지만, Redis는 성능 최적화를 위해 효율적인 Hash Table 구현을 사용합니다.)
4. 해시 슬롯의 역할
해시 슬롯은 데이터가 어느 샤드에 매핑될지 안내만 하는 역할입니다.
예: 키 a의 해싱 결과가 5481번 슬롯이라면, 해당 슬롯이 노드 B에 매핑되었다는 정보를 가지고 있습니다.
해시 슬롯은 매핑 정보만 유지하며, 실제 데이터를 저장하지 않습니다.
데이터가 노드로 전달되면, 해시 슬롯은 역할을 끝내고 삭제되거나 참조되지 않습니다.
5. 정리
해시 슬롯 자체는 데이터를 저장하지 않는다.
해시 슬롯은 키가 어느 노드로 가야 하는지 논리적으로 결정하는 매핑 정보만 유지합니다.
"키 a는 노드 B로 가시오"라는 역할을 수행하고, 데이터가 저장된 후에는 해시 슬롯이 추가 정보를 유지하지 않습니다.
노드(샤드)가 데이터를 저장한다.
데이터를 매핑받은 노드는 Hash Table 구조를 통해 데이터를 저장합니다.
동일한 해시 슬롯에 매핑된 데이터는 노드 내부의 Hash Table에서 충돌 처리를 통해 저장됩니다.
해시 슬롯과 노드의 관계는 매핑 정보만 공유한다.
해시 슬롯은 단순히 "이 키는 어느 노드로 가야 한다"는 논리적 경로 역할을 합니다.
데이터를 저장하는 것은 오직 해당 노드(샤드)의 역할입니다.
6. 추가로 이해를 돕는 예시
키를 저장하는 과정:
키 a → CRC16(a) % 16384 = 5481 → 5481번 슬롯 → 노드 B로 저장.
키 b → CRC16(b) % 16384 = 5481 → 동일하게 5481번 슬롯 → 노드 B로 저장.
노드 B는 자체 Hash Table에서 a와 b를 저장.
해시 슬롯은 매핑 정보만 유지:
해시 슬롯은 "5481번 슬롯은 노드 B가 담당"이라는 매핑 정보를 유지합니다.
데이터를 저장한 후 해시 슬롯은 역할을 끝내며, 데이터를 유지하지 않습니다.
실제 데이터는 노드의 Hash Table에 저장:
a와 b는 노드 B의 Hash Table에 별도로 저장되며, 충돌이 발생하면 체이닝 방식으로 처리됩니다.
결론
해시 슬롯은 데이터 배치를 위한 논리적 매핑 도구일 뿐, 데이터를 저장하지 않습니다.
데이터는 매핑된 노드(샤드)의 Hash Table에 저장됩니다.
동일한 슬롯에 매핑된 키들이 노드 내부에서 충돌할 경우 체이닝 방식으로 관리됩니다.
이로 인해 Redis 클러스터는 효율적인 데이터 분산과 높은 성능을 제공합니다. 😊
개념적으로는 해쉬 테이블에서의 버킷 = 노드 라고 생각해도 된다. 그러나 엄밀히 말하면 버킷은 해쉬 슬롯의 집합으로 실제 데이터가 저장되는 공간이고, 각 노드는 노드에 대응되는 DB에 데이터가 저장되게 된다.
따라서, 자료구조 관점에서 보면 버킷은 실제 데이터를 저장하는 하나의 큰 공간이니 노드와 같다고 볼 수는 없는거다. 왜냐하면 실제로 16384개의 해쉬 슬롯은 단순히 연결 역할만 하고 데이터를 담는 인스턴스는 자신만의 DB가 있으니까 말이다.
