글을 작성하게 된 계기
레디스의 CRC16 알고리즘에 대해 알게 되었고, 이를 정리하기 위해 글을 작성하게 되었습니다.
1. CRC 알고리즘과 레디스
CRC(Cyclic Redundancy Check)는 데이터 전송 중 오류를 검출하기 위해 개발된 알고리즘입니다. 어떤 데이터를 네트워크로 전송/저장할 때, 데이터에 일정한 규칙으로 생성한 체크 값(해시값) 을 붙여 함께 전송합니다. 수신 측에서는 받은 데이터와 체크 값을 이용해 동일한 방식으로 다시 계산하고, 두 값의 일치 여부로 데이터 손상을 판단하죠.
원래는 오류 검출 을 위해 개발되었지만, CRC는 특정 입력 데이터에 대해 항상 동일한 결괏값 을 만들기 때문에, 일종의 해시 함수처럼 사용할 수 있습니다. 특히 빠르고 간단한 특성 덕분에, 일부 시스템에서는 데이터 분산, 테이블 인덱싱, 키 분할 등의 용도로 CRC를 활용합니다. 레디스에서는 같은 키는 항상 같은 서버에 저장 되어야 하는데요, 따라서 키에 대해 해시값을 계산하고, 그 해시 값을 기준으로 0부터 16,383까지 총 16,384개의 슬롯 중 하나에 배정할 때 사용합니다.
1
2
3
4
5
6
7
8
9
[ 전체 16,384개 슬롯 ─ 논리적 해시 공간 ]
+------------+--------------+-------------+
| Node A | Node B | Node C |
| (0~5460) | (5461~10922) |(10923~16383)|
+------------+--------------+-------------+
Key → CRC16 해시 → 슬롯 번호(0-16383) → 해당 노드에 저장
"user:1" → CRC16 = 60000 → 60000 % 16384 = 10832 → Node B
"user:2" → CRC16 = 12000 → 12000 % 16384 = 12000 → Node C
슬롯은 물리적인 저장소나 메모리 공간이 아닌, 단지 키가 어느 레디스 노드에 저장되어야 하는지를 결정하기 위한 논리적인 번호 입니다. 레디스는 클러스터 모드에서 여러 노드에 데이터를 분산 저장하기 위해, 키를 어떤 노드에 배치할지를 결정해야 합니다. 키를 단순히 노드 수로 나눠서 분산하면, 노드를 추가하거나 제거할 때 모든 키의 위치를 바꿔야 해서 실제 서비스에서 큰 비용이 발생하며, 데이터가 한쪽에 치우치는 문제도 생길 수도 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 노드 추가 전(예: Node A, B, C)
┌─────────┬─────────┬─────────┐
│ Node A │ Node B │ Node C │
└─────────┴─────────┴─────────┘
▲ ▲ ▲
key1 % 3 key2 % 3 key3 % 3
# 노드 추가 후 (예: Node D 추가)
┌─────────┬─────────┬─────────┬─────────┐
│ Node A │ Node B │ Node C │ Node D │
└─────────┴─────────┴─────────┴─────────┘
▲ ▲ ▲ ▲
key1 % 4 key2 % 4 key3 % 4 key4 % 4
이러한 문제를 해결하기 위해 레디스는 고정된 16,384개의 슬롯을 먼저 정의합니다. 각 키는 CRC 16 해시값을 계산한 뒤, 16,384로 나눈 나머지를 통해 하나의 슬롯 번호(0~16383)에 매핑됩니다. 이 슬롯 번호는 해당 키가 어느 노드에 저장될지를 결정하는 기준이 됩니다. 예를 들어, user:1000이라는 키가 있다면, 레디스는 이 문자열에 대해 CRC 16 알고리즘으로 해시값을 계산하고, 이를 16384로 나눈 나머지를 구해 슬롯 번호를 정합니다. 이렇게 하면 같은 키는 항상 같은 슬롯에 매핑되므로, 분산 환경에서도 일관성 있게 데이터를 찾을 수 있게 됩니다.
1
2
3
4
5
[입력 키] [CRC16 해시 계산] [슬롯 계산] [결과]
"user:1000" ──▶ 6393 (CRC16 값) ──▶ 6393 % 16384 = 6393 ──▶ 슬롯 6393
│ │ (데이터가 저장될 슬롯)
│ │
└─ 키의 해시값 계산 └─ 총 16384개 슬롯 중
2. CRC16 알고리즘
레디스에서 사용 중인 CRC16을 간단히 살펴보겠습니다. CRC16 값은 입력 데이터 전체 내용을 특정한 방식으로 계산해서 만든 결괏값으로 같은 데이터라면, 항상 똑같은 CRC16 값이 나옵니다. 만약 데이터가 한 글자라도 바뀌면, CRC16 값이 완전히 달라집니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
uint16_t crc16(const char *buf, int len) {
int counter;
uint16_t crc = 0;
for (counter = 0; counter < len; counter++) {
// 1. crc의 상위 8bit(crc >> 8)와 현재 문자(*buf)를 XOR
// 2. 그 결과의 하위 8bit(0~255)를 crc16tab 테이블의 인덱스로 사용
// 3. crc를 8bit 왼쪽으로 shift(<< 8)하여 상위 8bit를 비움
// 4. shift된 crc와 crc16tab에서 꺼낸 값을 XOR하여 새 crc값 생성
crc = (crc << 8) ^ crc16tab[((crc >> 8) ^ *buf++) & 0x00FF];
}
return crc;
}
레디스는 crc16tab 이라는 각 byte(0~255)에 대해 미리 CRC16 연산 결과를 저장한 후, 이를 활용해 반복적으로 계산 속도를 높입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "server.h"
static const uint16_t crc16tab[256]= {
0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,
0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,
0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,
0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,
0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4,
0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc,
0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823,
0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b,
0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12,
0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a,
0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41,
0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49,
0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70,
0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78,
0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f,
0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067,
0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e,
0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256,
0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d,
0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405,
0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c,
0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,
0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab,
0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3,
0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a,
0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92,
0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9,
0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1,
0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,
0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0
};
2-1. 상위 8bit 추출 & XOR 연산
각 문자를 처리할 때, 현재까지의 CRC 값 중 상위 8bit만 뽑아 현재 문자와 XOR 연산을 합니다. 이렇게 만들어진 값(0~255)은 미리 만들어져 있는 crc16tab 테이블의 인덱스로 사용됩니다.
1
2
uint16_t crc = 0x50A5;
uint8_t hi = crc >> 8; // 상위 8bit만 뽑기
2-2. CRC 값 왼쪽으로 시프트
이후 현재 CRC 값은 8bit 왼쪽으로 밀어줍니다. 이를 통해 기존에 쌓여 있던 정보 중 상위 8bit는 버려지고, 그 자리를 새로운 정보로 채웁니다.
1
uint16_t shifted = crc << 8;
이렇게 8bit 왼쪽으로 시프트하면, 이전에 누적된 상위 8bit 정보는 버리고 그 자리를 새로운 데이터로 채울 수 있습니다. 이를 통해 문자마다 고유한 영향을 CRC 값에 남기며, 정보를 깔끔하게 누적시킵니다.
1
2
BEFORE: 0101 0000 1010 0101
AFTER : 1010 0101 0000 0000
2-3. 테이블 값과 XOR하여 새로운 CRC 생성
마지막으로, 테이블에서 꺼낸 값을 이 왼쪽으로 shift된 CRC 값과 XOR해서, 새로운 CRC 값을 만듭니다. 이렇게 문자마다, 이전까지의 CRC 값과 현재 문자를 조합해서 테이블을 참고하고, 그 결과를 누적해 가며 최종적으로 16bit짜리 CRC16 값을 만들어 냅니다.
1
2
3
4
CRC shift : 0xA500 = 1010 0101 0000 0000
테이블 값 : 0x3273 = 0011 0010 0111 0011
-----------------------------
XOR 결과 : 0x8573 = 1000 0101 0111 0011
3. 해시 충돌 처리 방식과 내부 구조체
CRC16은 16bit 함수로 0부터 65,535까지의 해시값을 생성하지만, 레디스는 이 값을 16,384로 나눈 나머지(%) 를 실제 슬롯 번호로 사용합니다. 즉, 서로 다른 키가 동일한 슬롯( 0~16,383)에 할당될 수 있으므로 충돌이 발생할 수 있죠. 하지만 특정 슬롯에 할당된 키들은 해당 노드 내부에서 키값을 직접 비교 하므로, 슬롯 할당이 겹쳐도 데이터를 안전하게 관리할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static dictEntryLink dictFindLinkInternal(dict *d, const void *key, dictEntryLink *bucket) {
dictCmpCache cmpCache = {0};
dictEntryLink link;
uint64_t idx;
int table;
if (bucket) {
*bucket = NULL;
} else {
if (dictSize(d) == 0) return NULL;
}
# 1. 해시값 계산
const uint64_t hash = dictHashKey(d, key, d->useStoredKeyApi);
idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]);
keyCmpFunc cmpFunc = dictGetCmpFunc(d);
_dictRehashStepIfNeeded(d,idx);
# 2. 점진적 리해싱 확인
int tables = (dictIsRehashing(d)) ? 2 : 1;
# 3. 테이블 및 버킷 탐색
for (table = 0; table < tables; table++) {
if (table == 0 && (long)idx < d->rehashidx) continue;
idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
redis_prefetch_read(&d->ht_table[table][idx]);
link = &(d->ht_table[table][idx]);
if (bucket) *bucket = link;
# 4. 연결 리스트 순회 및 실제 키 비교
while(link && *link) {
void *visitedKey = dictGetKey(*link);
redis_prefetch_read(dictGetNext(*link));
# 포인터 주소가 같은지 확인
if (key == visitedKey || cmpFunc( &cmpCache, key, visitedKey))
return link;
# 키가 일치하지 않으면 연결 리스트의 다음 노드로 이동해 비교
link = dictGetNextLink(*link);
}
}
return NULL;
}
1
2
3
4
5
static dictEntryLink dictGetNextLink(dictEntry *de) {
if (entryIsKey(de)) return NULL;
if (entryIsNoValue(de)) return &decodeEntryNoValue(de)->next;
return &de->next;
}
내부 코드를 살펴보면 while 문을 순회하며 포인터 주소가 같은지 확인합니다. 만약 포인터가 다르다면, 키값 자체가 같은지 비교 함수(cmpFunc)로 한 번 더 비교합니다. 키가 일치하지 않으면 연결 리스트의 다음 노드로 이동하여 같은 방식으로 비교를 반복합니다. 이런 과정을 거쳐 키가 일치하는 엔트리를 찾거나, 끝까지 못 찾으면 NULL을 반환합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static dictEntryLink dictFindLinkInternal(dict *d, const void *key, dictEntryLink *bucket) {
......
for (table = 0; table < tables; table++) {
......
while(link && *link) {
void *visitedKey = dictGetKey(*link);
redis_prefetch_read(dictGetNext(*link));
# 포인터 주소가 같은지 확인
if (key == visitedKey || cmpFunc( &cmpCache, key, visitedKey))
return link;
# 키가 일치하지 않으면 연결 리스트의 다음 노드로 이동해 비교
link = dictGetNextLink(*link);
}
}
return NULL;
}
3-1. Dict
레디스에서 키는 기본적으로 해시테이블(dict)을 사용합니다. 이는 레디스 내부에서 dict라는 자료구조로 구현되어 있으며, 모든 레디스의 데이터 key/value 쌍은 이 dict에 저장, 관리 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
struct dict {
dictType *type;
dictEntry **ht_table[2];
unsigned long ht_used[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
/* Keep small vars at end for optimal (minimal) struct padding */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
};
3-2. DictType
dict의 동작 방식은 dictType 이 결정 합니다. 이는 key/value를 어떻게 비교할지, 복사할지, 또는 메모리를 해제할지 등의 동작을 함수 포인터로 정의해놓은 구조체입니다. 예를 들어, key가 문자열이면 문자열끼리 비교하고, 숫자면 숫자끼리 비교하죠. 이를 통해 다양한 데이터 타입에 유연하게 대응할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(dict *d, const void *key);
void *(*valDup)(dict *d, const void *obj);
int (*keyCompare)(dict *d, const void *key1, const void *key2);
void (*keyDestructor)(dict *d, void *key);
void (*valDestructor)(dict *d, void *obj);
int (*expandAllowed)(size_t moreMem, double usedRatio);
/* Allow a dictEntry to carry extra caller-defined metadata. The
* extra memory is initialized to 0 when a dictEntry is allocated. */
size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;
3-3. DictEntry
실제로 각 key-value 데이터 한 쌍을 저장하는 단위는 dictEntry 구조체입니다. 이는 key/value, 다음 엔트리를 가리키는 포인터(next)를 가지고 있습니다. 해시테이블의 같은 버킷( 슬롯)에 여러 개의 key가 들어가면 해시 충돌이 발생할 수 있기 때문에, dictEntry끼리 연결리스트 형태로 이어져서 충돌을 해결합니다.
1
2
3
4
5
6
7
8
9
10
struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; /* Next entry in the same hash bucket. */
};
각 dictEntry는 key 전체 값을 직접 비교하므로, 해시값이 같아도 이를 해결할 수 있습니다.
4. Hash Tag
레디스 클러스터에서는 데이터의 분산 저장을 위해 각 키를 해싱해서 슬롯에 배정합니다. 이때, 레디스에는 해시태그(Hash Tag) 라는 독특한 기능이 있는데, 이는 키 전체가 아닌 키 일부만을 해싱 대상으로 지정 할 수 있도록 합니다.
키 이름에 중괄호({}) 를 사용하면, 중괄호 내부에 들어간 문자열만 해시 계산에 사용 됩니다. 예를 들어, key1:{user1}와 key2:{user1}처럼 키 이름의 일부가 {user1}로 동일하게 들어가 있다면, 이 두 키는 완전히 다른 키 이름임에도 불구하고, 중괄호 안의 user1만 해싱되어 같은 슬롯에 배정됩니다. 즉, 둘 다 같은 노드에 저장됩니다.
1
2
3
# → 같은 슬롯에 저장 - 동일 노드
"key1:{user1}" # {user1}만 해싱 → 슬롯 X
"key2:{user1}" # {user1}만 해싱 → 슬롯 X
이는 분산 환경에서 매우 중요하게 활용됩니다. 예를 들어, 분산 락(Distributed Lock) 이나 멀티 키 연산할 때, 관련된 키들을 의도적으로 같은 슬롯, 같은 노드에 배치할 수 있기 때문입니다. 참고로 같은 슬롯에 있어야만 레디스에서 멀티 키 트랜잭션 또는 Lua 스크립트 같은 원자적 연산을 지원할 수 있습니다.
만약 각각의 키가 서로 다른 슬롯(노드)에 배치되어 있다면, 해당 연산은 에러가 발생하거나 지원되지 않을 수 있습니다.
5. 정리
CRC16 알고리즘은 레디스 클러스터에서 키를 슬롯에 매핑하는 데 사용되는 중요한 해싱 방법입니다. 이를 통해 빠르고 간단하게 해시값을 계산할 수 있어, 대규모 데이터 분산 환경에서도 효율적으로 작동합니다. 또한, 해시 충돌이 발생하더라도 실제 키값을 비교하여 데이터를 안전하게 관리할 수 있습니다. 어려운데 재미있네요. 🚀