[Redis] Hacking Strings

https://redis.io/topics/internals-sds

 

Hacking Strings

Redis에서 사용하는 strings는 sds.c에 구현되어 있습니다. (sds는 Simple Dynamic String의 약자다)

sds.h에 sdshdr C 구조체로 정의되어있습니다.

struct sdshdr {
    long len;
    long free;
    char buf[];
}

character형 배열 buf는 실제 문자열이 저장되는 공간입니다.

len은 buf에 실제로 저장된 문자열 길이를 저장하고 있고, 이 필드로 인해 문자열의 길이를 조회하는 건 O(1)로 할 수 있습니다.

free는 buf에서 추가적으로 사용 가능한 공간을 저장합니다.

len과 free 필드는 buf의 메타데이터를 저장하고 있다고 생각하면 됩니다.

 

Create Redis Strings

새로운 데이터 타입인 sds는 sds.h에 정의되어있고, character 포인터의 별칭을 의미합니다.

typedef char *sds;

sds.c에 정의된 sdsnewlen 함수는 새로운 Redis String을 생성합니다.

sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
#ifdef SDS_ABORT_ON_OOM
    if (sh == NULL) sdsOomAbort();
#else
    if (sh == NULL) return NULL;
#endif
    sh->len = initlen;
    sh->free = 0;
    if (initlen) {
        if (init) memcpy(sh->buf, init, initlen);
        else memset(sh->buf,0,initlen);
    }
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

Redis string은 sdshdr 구조체의 변수입니다. 하지만 sdsnewlen 함수는 character 포인터를 리턴합니다.

약간의 설명이 필요한 꼼수입니다.

아래처럼 sdsnewlen을 이용해서 Redis string을 생성한다고 가정하겠습니다.

sdsnewlen("redis", 5);

len, free 뿐만 아니라 buf character형 배열까지, sdshdr 구조체의 필드들의 메모리를 할당합니다.

sh = zmalloc(sizeof(struct sdshdr)+initlen+1); // initlen is length of init argument.

sdsnewlen 함수가 정상 실행되면 아래와 같은 결과가 됩니다.

-----------
|5|0|redis|
-----------
^     ^
sh   sh->buf

 

sdsnewlen 함수를 호출하면 sh->buf 가 리턴됩니다.
Redis string의 sh 포인터가 필요해지면 어떻게 해야 할까요?

sh 포인터가 필요하지만 리턴 받은 값은 sh->buf 뿐입니다. sh-buf을 이용해서 sh를 가져올 수 있을까요?

네!! 포인터 산술 연산을 이용하면 됩니다.

위에 아스키로 그림을 보면 sh-buf에서 두 개의 long 크기만큼 빼면 sh를 가져올수 있습니다.

두개의 long 크기는 sdshdr 구조체 크기입니다. 

sdslen 함수에서 트릭을 어떻게 썼는지 보겠습니다.

size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    return sh->len;
}

이 트릭을 알고 있으면 sds.c에 구현된 나머지 부분을 쉽게 이해할 수 있습니다.

Redis string 구현은 character형 포인터만 허용하는 인터페이스 뒤에 숨어있습니다.

Redis 문자열의 사용자는 Redis string에 사용하는 character 형 포인터가 어떻게 구현되어있고 계산하는지 알 필요가 없습니다.