Redis의 정수 집합(intset) 관련 파일은 intset.h와 intset.c로 구성되어 있습니다.
intset은 정렬된 정수 배열과 유사한 작업을 수행하지만, 데이터 유형에 따라 메모리 최적화가 이루어집니다.
- 데이터 구조
1 typedef struct custom_set {
2 uint32_t format;
3 uint32_t size;
4 int8_t elements[];
5 } custom_set;
custom_set 구조는 가변 길이 구조체로, size 멤버가 현재 요소 개수를 저장하고 format 멤버가 현재 정수 타입을 나타냅니다. 사용 가능한 타입은 다음과 같습니다:
1 #define SET_FMT_SHORT (sizeof(int16_t))
2 #define SET_FMT_INT (sizeof(int32_t))
3 #define SET_FMT_LONG (sizeof(int64_t))
타입 판별 로직은 다음과 같습니다:
1 static uint8_t determineFormat(int64_t val) {
2 if (val < INT32_MIN || val > INT32_MAX)
3 return SET_FMT_LONG;
4 else if (val < INT16_MIN || val > INT16_MAX)
5 return SET_FMT_INT;
6 else
7 return SET_FMT_SHORT;
8 }
정렬된 데이터 구조는 다음과 같이 표현됩니다:
1 /*
2 +--------+--------+--------...--------------+
3 |format | size |elements(format*size)|
4 +--------+--------+--------...--------------+
5 */
데이터는 항상 리틀엔디안 형식으로 저장되며, 머신의 바이트 순서와 무관하게 처리됩니다. endianconv.h 파일에는 다음과 같은 정의가 포함되어 있습니다:
1 #if (BYTE_ORDER == LITTLE_ENDIAN)
2 #define memrev16ifbe(p) ((void)(0))
3 #define memrev32ifbe(p) ((void)(0))
4 #define memrev64ifbe(p) ((void)(0))
5 #define intrev16ifbe(v) (v)
6 #define intrev32ifbe(v) (v)
7 #define intrev64ifbe(v) (v)
8 #else
9 #define memrev16ifbe(p) memrev16(p)
10 #define memrev32ifbe(p) memrev32(p)
11 #define memrev64ifbe(p) memrev64(p)
12 #define intrev16ifbe(v) intrev16(v)
13 #define intrev32ifbe(v) intrev32(v)
14 #define intrev64ifbe(v) intrev64(v)
15 #endif
구체적인 구현은 endianconv.c 파일에서 확인할 수 있습니다.
- 생성 과정
1 custom_set *createSet(void) {
2 custom_set *cs = zmalloc(sizeof(custom_set));
3 cs->format = intrev32ifbe(SET_FMT_SHORT);
4 cs->size = 0;
5 return cs;
6 }
새로 생성된 집합은 비어 있으며, 기본적으로 최소 크기의 타입을 사용합니다. 구조는 다음과 같습니다:
1 /* 여기서 '-'는 1바이트를 나타냅니다.
2 +----+----+
3 | 16 | 0 |
4 +----+----+
5 */
- 연산
다음과 같은 집합이 존재한다고 가정합니다:
1 /*
2 +----+----+--+--+--+--+--+--+--+
3 | 16 | 7 | 1| 2| 3| 4| 5| 7| 8|
4 +----+----+--+--+--+--+--+--+--+
5 |elements
6
7 */
6을 삽입하려면 다음 함수를 호출해야 합니다:
1 /* 정수 삽입 */
2 custom_set *addValue(custom_set *cs, int64_t val, uint8_t *result) {
3 uint8_t fmt = determineFormat(val);
4 uint32_t pos;
5 if (result) *result = 1;
6
7 /* 타입 업그레이드 처리 */
8 if (fmt > intrev32ifbe(cs->format)) {
9 return upgradeAndInsert(cs, val);
10 } else {
11 /* 이미 존재하는 값일 경우 중단 */
12 if (searchSet(cs, val, &pos)) {
13 if (result) *result = 0;
14 return cs;
15 }
16
17 cs = resizeSet(cs, intrev32ifbe(cs->size)+1);
18 if (pos < intrev32ifbe(cs->size)) moveTail(cs, pos, pos+1);
19 }
20
21 setElement(cs, pos, val);
22 cs->size = intrev32ifbe(intrev32ifbe(cs->size)+1);
23 return cs;
24 }
6은 short 타입으로 저장 가능하므로, 기존 타입과 동일합니다. 삽입 위치를 찾기 위해 이진 탐색 알고리즘을 사용합니다:
1 static uint8_t searchSet(custom_set *cs, int64_t val, uint32_t *pos) {
2 int min = 0, max = intrev32ifbe(cs->size)-1, mid = -1;
3 int64_t current = -1;
4
5 if (intrev32ifbe(cs->size) == 0) {
6 if (pos) *pos = 0;
7 return 0;
8 } else {
9 if (val > getElement(cs, max)) {
10 if (pos) *pos = intrev32ifbe(cs->size);
11 return 0;
12 } else if (val < getElement(cs, 0)) {
13 if (pos) *pos = 0;
14 return 0;
15 }
16 }
17
18 while(max >= min) {
19 mid = ((unsigned int)min + (unsigned int)max) >> 1;
20 current = getElement(cs, mid);
21 if (val > current) {
22 min = mid+1;
23 } else if (val < current) {
24 max = mid-1;
25 } else {
26 break;
27 }
28 }
29
30 if (val == current) {
31 if (pos) *pos = mid;
32 return 1;
33 } else {
34 if (pos) *pos = min;
35 return 0;
36 }
37 }
정렬된 데이터를 기반으로 이진 탐색이 수행됩니다. 삽입 위치는 5번 인덱스로 결정됩니다. 이후 메모리 확장을 수행합니다:
1 static custom_set *resizeSet(custom_set *cs, uint32_t len) {
2 uint32_t size = len*intrev32ifbe(cs->format);
3 cs = zrealloc(cs, sizeof(custom_set)+size);
4 return cs;
5 }
확장 후 데이터는 다음과 같이 구성됩니다:
1 /*
2 +----+----+--+--+--+--+--+--+--+--+
3 | 16 | 7 | 1| 2| 3| 4| 5| 7| 8| |
4 +----+----+--+--+--+--+--+--+--+--+
5 pos | 0| 1| 2| 3| 4| 5| 6| 7|
6 */
기존 요소를 한 칸 뒤로 이동시킵니다:
1 static void moveTail(custom_set *cs, uint32_t from, uint32_t to) {
2 void *src, *dst;
3 uint32_t bytes = intrev32ifbe(cs->size)-from;
4 uint32_t fmt = intrev32ifbe(cs->format);
5
6 if (fmt == SET_FMT_LONG) {
7 src = (int64_t*)cs->elements+from;
8 dst = (int64_t*)cs->elements+to;
9 bytes *= sizeof(int64_t);
10 } else if (fmt == SET_FMT_INT) {
11 src = (int32_t*)cs->elements+from;
12 dst = (int32_t*)cs->elements+to;
13 bytes *= sizeof(int32_t);
14 } else {
15 src = (int16_t*)cs->elements+from;
16 dst = (int16_t*)cs->elements+to;
17 bytes *= sizeof(int16_t);
18 }
19 memmove(dst, src, bytes);
20 }
이동 후 데이터는 다음과 같습니다:
1 /*
2 +----+----+--+--+--+--+--+--+--+--+
3 | 16 | 7 | 1| 2| 3| 4| 5| 7| 7| 8|
4 +----+----+--+--+--+--+--+--+--+--+
5 pos | 0| 1| 2| 3| 4| 5| 6| 7|
6 */
마지막으로 지정된 위치에 값을 설정합니다:
1 static void setElement(custom_set *cs, int pos, int64_t val) {
2 uint32_t fmt = intrev32ifbe(cs->format);
3
4 if (fmt == SET_FMT_LONG) {
5 ((int64_t*)cs->elements)[pos] = val;
6 memrev64ifbe(((int64_t*)cs->elements)+pos);
7 } else if (fmt == SET_FMT_INT) {
8 ((int32_t*)cs->elements)[pos] = val;
9 memrev32ifbe(((int32_t*)cs->elements)+pos);
10 } else {
11 ((int16_t*)cs->elements)[pos] = val;
12 memrev16ifbe(((int16_t*)cs->elements)+pos);
13 }
14 }
값을 추가한 후 크기는 다음과 같이 변경됩니다:
1 /*
2 +----+----+--+--+--+--+--+--+--+--+
3 | 16 | 8 | 1| 2| 3| 4| 5| 6| 7| 8|
4 +----+----+--+--+--+--+--+--+--+--+
5 pos | 0| 1| 2| 3| 4| 5| 6| 7|
6 */
65536과 같은 값을 추가할 경우 기존 타입이 부족해 업그레이드가 필요합니다:
1 static custom_set *upgradeAndInsert(custom_set *cs, int64_t val) {
2 uint8_t currFmt = intrev32ifbe(cs->format);
3 uint8_t newFmt = determineFormat(val);
4 int size = intrev32ifbe(cs->size);
5 int prepend = val < 0 ? 1 : 0;
6
7 /* 타입 변경 및 메모리 확장 */
8 cs->format = intrev32ifbe(newFmt);
9 cs = resizeSet(cs, intrev32ifbe(cs->size)+1);
10
11 /* 뒤에서 앞쪽으로 데이터 이동 */
12 while(size--)
13 setElement(cs, size+prepend, getElementEncoded(cs, size, currFmt));
14
15 /* 값 삽입 */
16 if (prepend)
17 setElement(cs, 0, val);
18 else
19 setElement(cs, intrev32ifbe(cs->size), val);
20 cs->size = intrev32ifbe(intrev32ifbe(cs->size)+1);
21 return cs;
22 }
정수 범위를 초과하는 경우, 양수는 마지막에 음수는 처음에 삽입됩니다. 업그레이드 후 기존 데이터는 새로운 타입으로 재배치됩니다.
삭제 연산:
1 custom_set *removeValue(custom_set *cs, int64_t val, int *result) {
2 uint8_t fmt = determineFormat(val);
3 uint32_t pos;
4 if (result) *result = 0;
5
6 if (fmt <= intrev32ifbe(cs->format) && searchSet(cs, val, &pos)) {
7 uint32_t len = intrev32ifbe(cs->size);
8
9 /* 삭제 처리 */
10 if (result) *result = 1;
11
12 /* 뒤쪽 데이터 앞쪽으로 이동 */
13 if (pos < (len-1)) moveTail(cs, pos+1, pos);
14 cs = resizeSet(cs, len-1);
15 cs->size = intrev32ifbe(len-1);
16 }
17 return cs;
18 }
요소를 찾은 후 뒤쪽 데이터를 앞으로 이동시키고 메모리 크기를 조정합니다.
Redis 5.0.7 다운로드 링크
http://download.redis.io/releases/redis-5.0.7.tar.gz
소스 코드 분석 순서 참조:
https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst