Redis의 String이 빠른 이유

Redis String 데이터 구조의 구현체에 대해서 알아보는 글입니다.

C에서 문자열을 구현해야 하면, 보통은 표준 C 라이브러리로 libc를 이용할 것 이다.
Redis를 만든 살바토르 산필리포는 Redis의 String을 구현하며 libc를 사용하지 않고 직접 문자열 라이브러리를 만들었다.
SDS(Simple Dynamic Strings)라는 라이브러리다.  이 글에서는 libc를 사용하지 않고 왜 문자열 라이브러리를 다시 만들게 되었는지, sds가 가지는 장점과 구현체가 어떻게 구성되어있는지 알아본다.
 
SDS (Simple Dynamic Strings) https://github.com/antirez/sds
Redis에서 문자열을 관리하는 라이브러리
Redis는 Binary Safe한 특징이 있다. 모든 데이터를 담을 수 있어 mp4와 같은 비정형 데이터도 저장할 수 있다.
(물론 크기의 문제만 없다면 말이다. Key와 Value가 가질 수 있는 최대 크기는 글의 말미에서 언급한다)
더불어 String엔 특수 문자, NULL 을 문자열에 포함할 수 있어야 한다.
libc를 이용해 Redis String을 구현했다면 여기서 문제가 발생한다.
C의 char * 로 String을 구현하면 Binary Safe하지 않게 된다.
이 이유는 NULL값을 Null-terminated string으로 인식하기 때문이다.
NULL("\0")값이 들어간 "roharon\0" 문자열을 저장하는 경우엔 아래와 같이 저장된다.

의도와 달리 인덱스 7에 있는 '\0' NULL 값이 Null terminated String 으로 인식된다. 따라서 이러한 형태에선 NULL값을 String으로 표현할 수 없다.

또한 문자열 크기 확인하려면  Null-terminated string을 발견할 때 까지 카운트 해야한다.
O(n)의 시간복잡도를 가지며 성능 저하의 요인이 된다.
SDS에선 표준 C 라이브러리인 libc에서 힙 할당 문자열을 추가하면서
사용하기 쉽고, Binary Safe하며, 더 효율적으로 계산 처리하고, C언어 문자열 함수와 호환되게 하였다.
 

sds header 구조체

간단히 sds의 header에 대해서 보려고 한다.

sds.h

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

len (uintN_t)

• 문자열의 길이를 저장함
• 👉 문자열 길이를 구하는데 시간 복잡도 O(1)

alloc (uintN_t)

• 헤더와 null terminated string (\0)값을 제외한 길이

flags (unsigned char)

• unsigned char 타입으로 8Bits(2Bytes)에서 LSB(가장 낮은 위치의 Bit) 3개를 사용함

buf (char)

• flags 다음의 첫번째 byte를 가리킴

sds (char *)

• "roharon" 가 저장되는 배열

long이 아닌 uint16_t 와 같이 사용하는 이유

C99 에서 추가된 stdint.h 의 구현체로, 32bit, 64bit 관계 없이 모든 플랫폼에서 동일한 Bit 크기를 가짐
이들을 Primitive System Data Type이라고 부른다.

예) long 타입의 경우 32-bit OS 에서 크기는 32bit인데 64-bit OS에선 64bit.

• long은 int 타입과 크기가 같거나 커야할 뿐이지, 반드시 64bit라고 정의되진 않음
  플랫폼간 이식성을 보장하고자 intN_t 를 사용함

따라서, Redis String 타입으로 "roharon\0" 을 저장한다면, 아래와 같이 SDS가 구성된다.

 

그런데 뒤에 Free Space가 있다.
SDS를 통해 할당하는 메모리 크기는
헤더(sdshdr) 크기 + 사용하는 문자열의 크기 + null terminated string 크기 일 것 같은데,
Free Space가 추가로 생긴다.

Free Space는 아래와 같이 문자열을 붙일 때 발생한다.

sentence = sdsempty();
sentence = sdscat(sentence, "My name is")
sentence = sdscat(sentence, "Aaron Roh")

문자열이 추가될 때 마다 문자열을 재할당할 수도 있지만 이러한 구현 방식은 성능적으로 좋지 않다.
빈번한 메모리 확보와 회수는 성능 저하의 원인이 된다.
이런 점을 해결하고자, preallocation 알고리즘을 사용한다.
문자열이 커지면, 사용할 메모리 공간으로 <최소로 필요한 공간>의 2배를 미리 할당하는 방식이다.
30 Bytes 크기의 문자열에 2 Bytes 의 문자열을 이어 붙인다고 해보자
이 경우, 최소 공간인 32 Bytes 의 2배가 되는 64 Bytes 크기를 할당한다.

 

그럼 문자열을 합칠 때 최소로 필요한 공간이 1GB 이라면

다행히 할당에 대한 hard limit이 있는데, sds.h 에서 SDS_MAX_PREALLOC 매크로 상수로 정의되어 있다.
sds/sds.h at master · antirez/sds (github.com)

// sds.h
#define SDS_MAX_PREALLOC (1024*1024)

SDS_MAX_PREALLOC 상수가 1024*1024 로 정의되어 1MB를 표현한다.
1MB를 넘기지 않은 경우엔 아래 내용으로 2배로 할당하고, 넘긴 경우엔 SDS_MAX_PREALLOC 크기 만큼 공간을 할당하는 로직이다. 

// sds.c

reqlen = newlen = (len+addlen);
  if (newlen < SDS_MAX_PREALLOC)
     newlen *= 2;
  else
     newlen += SDS_MAX_PREALLOC;

 
SDS에선 SDS_MAX_PREALLOC 값인 1MB로 문자열의 크기가 제한이 되었는데,
그럼 Redis의 키의 값에 대한 최대 크기로 얼만큼을 가질 수 있을까? 

Redis의 t_string.c 에서 checkStringLength 정적 함수를 확인할 수 있다.

    if (total > server.proto_max_bulk_len || total < size || total < append) {
        addReplyError(c,"string exceeds maximum allowed size (proto-max-bulk-len)");
        return C_ERR;
    }

proto_max_bulk_len 값에 따라 저장할 수 있는 최대 사이즈가 결정된다
https://github.com/redis/redis/blob/e7a3d3d152c251cc25aed3d89a47a525812e72de/src/t_string.c#L40%EF%BB%BF

    createLongLongConfig("proto-max-bulk-len", NULL, DEBUG_CONFIG | MODIFIABLE_CONFIG, 1024*1024, LONG_MAX, server.proto_max_bulk_len, 512ll*1024*1024, MEMORY_CONFIG, NULL, NULL), /* Bulk request max size */

config.c 에서 (512*1024*1024) 값을 제공하고 있어 최대 크기는 512MB로 결정된다.
https://github.com/redis/redis/blob/e4d183afd33e0b2e6e8d1c79a832f678a04a7886/src/config.c#L3185
만일 최대 크기를 512MB 보다 크게 설정하길 원한다면, redis.conf에서 proto-max-bulk-len 값을 지정하면 된다.

 

---

레퍼런스

• https://github.com/antirez/sds
• https://github.com/redis/redis/blob/e7a3d3d152c251cc25aed3d89a47a525812e72de/src/t_string.c#L40