Redis(레디스)의 구현과 내부 구조, 작동 원리 - 1

새로운 프로젝트인 Haffle에서 레디스를 메인 데이터베이스로 사용하기로 결정했다. 꽤 도전적인 선택이고 내 기준에서는 약간의 기술적 도전이기도 하다. 어떻게 해야 레디스로 인스타그램처럼 잘 만들 수 있을까 고민하다가 코드를 한번 씹어먹어보기로 했다. 레디스의 여러 명령어를 사용하면서도 레디스의 구현에 대해서는 무지했는데, 이제부터 레디스에 대한 내부 구조와 세부 구현에 대해 소스 코드를 분석해 보고자 한다. 잘못된 내용이 있을시 알려주길 바란다!

레디스 3.XX 기준 소스코드이다.

레디스 객체

// redis.h

#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

redis.h 에서 레디스가 저장된 데이터를 관리하기위해 사용하는 redisObject의 구조체 형식을 확인할 수 있다. 아니 사실 모든 레디스 운영을 위한 모든 변수도 이걸로 관리된다. redis.h에서 처음으로 나오는 구조체기도 하다. 레디스는 비트필드를 사용하여, type 구별(4비트)과 인코딩 타입 구별(4비트)을 위해, 그리고 LRU를 위한 시간 저장공간(24비트)을 사용하는데, 정말 아끼고 아껴 고작 저걸 다 합쳐서 32비트밖에 안사용한다. 레디스는 메모리에서 동작하고 메모리는 시스템 자원 중 매우 비싼편에 속한다. 이를 알고 최소한으로 사용하려는 노력이 돋보인다. (반성해야한다 나는.) 과거(2.6대)에는 2비트를 notUsed 필드로 남겨뒀는데 3.XX 버전대로 오면서 lru를 위해 할당한 듯 하다. refcount는 해당 객체가 참조당하는 횟수로 파악되고, ptr이 실제 데이터를 가리키는 용도로 사용되는 포인터로 보인다.

여기서 encoding은 무엇인가? type은 또 무엇인가?

레디스의 자료 구조(타입)과 인코딩

// redis.h

/* Object types */
#define REDIS_STRING 0 //스트링
#define REDIS_LIST 1 //리스트
#define REDIS_SET 2 //집합(셋)
#define REDIS_ZSET 3 //정렬된 리스트
#define REDIS_HASH 4 //해시테이블

#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */

redis.h의 179번째 줄 부터 시작하는 상수를 보자. redis는 4개의 비트로 아마 최대 16개의 자료구조 타입을 표현할 수 있을 것이다. 그리고 현재는 위의 5가지를 지원하는 듯 하다. 곧 위치 관련 구조도 지원한다는데, 이곳에 5번으로 추가되지 않을까.

레디스는 인코딩타입으로 현재 9가지를 지원한다.

• RAW
• INT
• 해시테이블
• 집맵(압축된 해시테이블)
• 연결리스트
• 집리스트(압축된 리스트)
• INT형 변수만 있는 집합(셋)일 경우 사용되는 INTSET
• SKIPLIST
• EMBSTR

각각의 인코딩이 무엇인지는 정확히 모르겠지만, 어쨋든 이런 인코딩 타입을 지원하나보다. 데이터를 군더더기 없이 최소한의 공간만 사용해 저장하려는 노력의 일환인 듯 하다.

문자열 데이터 인코딩 따라가기

레디스는 문자열을 저장하기 위해 아래 2가지의 인코딩을 지원한다.

• RAW
• INT

어떻게 동작하는지 살펴보자.

// redis.c

struct redisCommand redisCommandTable[] = {
    {"get",getCommand,2,"rF",0,NULL,1,1,1,0,0},
    {"set",setCommand,-3,"wm",0,NULL,1,1,1,0,0},
    // ... 중략 ... 
    {"pfselftest",pfselftestCommand,1,"r",0,NULL,0,0,0,0,0},
    {"pfadd",pfaddCommand,-2,"wmF",0,NULL,1,1,1,0,0},
    {"pfcount",pfcountCommand,-2,"r",0,NULL,1,-1,1,0,0},
    {"pfmerge",pfmergeCommand,-2,"wm",0,NULL,1,-1,1,0,0},
    {"pfdebug",pfdebugCommand,-3,"w",0,NULL,0,0,0,0,0},
    {"latency",latencyCommand,-2,"arslt",0,NULL,0,0,0,0,0}
};

redis.c에서 문자열 데이터를 저장하는 명령어인 get과 set이 호출됐을때 실행되는 함수를 확인할 수 있다. getCommand과 setCommand이 그것인데, 이 소스를 찾아보자. 먼저 setCommand가 궁금하다.

// t_string.c

static int checkStringLength(redisClient *c, long long size) {
    if (size > 512*1024*1024) {
        addReplyError(c,"string exceeds maximum allowed size (512MB)");
        return REDIS_ERR;
    }
    return REDIS_OK;
}

setCommand를 찾아 뜯어보니, 첫줄에 checkStringLength함수가 보인다. 512메가를 넘는 스트링인가를 검사하는데, redisClient포인터 까지 인자로 받는다. 레디스의 Command와 관련된 모든 함수는 redisClient를 참조한다. 이게 뭘까?

// redis.h

/* With multiplexing we need to take per-client state.
 * Clients are taken in a linked list. */
typedef struct redisClient {
    uint64_t id;            /* Client incremental unique ID. */
    int fd;
    redisDb *db;
    int dictid;
    robj *name;             /* As set by CLIENT SETNAME */
    sds querybuf;
    size_t querybuf_peak;   /* Recent (100ms or more) peak of querybuf size */
    int argc;
    robj **argv;
    struct redisCommand *cmd, *lastcmd;
    int reqtype;
    int multibulklen;       /* number of multi bulk arguments left to read */
    long bulklen;           /* length of bulk argument in multi bulk request */
    list *reply;
    unsigned long reply_bytes; /* Tot bytes of objects in reply list */
    int sentlen;            /* Amount of bytes already sent in the current
                               buffer or object being sent. */
    time_t ctime;           /* Client creation time */
    time_t lastinteraction; /* time of the last interaction, used for timeout */
    time_t obuf_soft_limit_reached_time;
    int flags;              /* REDIS_SLAVE | REDIS_MONITOR | REDIS_MULTI ... */
    int authenticated;      /* when requirepass is non-NULL */
    int replstate;          /* replication state if this is a slave */
    int repl_put_online_on_ack; /* Install slave write handler on ACK. */
    int repldbfd;           /* replication DB file descriptor */
    off_t repldboff;        /* replication DB file offset */
    off_t repldbsize;       /* replication DB file size */
    sds replpreamble;       /* replication DB preamble. */
    long long reploff;      /* replication offset if this is our master */
    long long repl_ack_off; /* replication ack offset, if this is a slave */
    long long repl_ack_time;/* replication ack time, if this is a slave */
    char replrunid[REDIS_RUN_ID_SIZE+1]; /* master run id if this is a master */
    int slave_listening_port; /* As configured with: SLAVECONF listening-port */
    multiState mstate;      /* MULTI/EXEC state */
    int btype;              /* Type of blocking op if REDIS_BLOCKED. */
    blockingState bpop;     /* blocking state */
    long long woff;         /* Last write global replication offset. */
    list *watched_keys;     /* Keys WATCHED for MULTI/EXEC CAS */
    dict *pubsub_channels;  /* channels a client is interested in (SUBSCRIBE) */
    list *pubsub_patterns;  /* patterns a client is interested in (SUBSCRIBE) */
    sds peerid;             /* Cached peer ID. */

    /* Response buffer */
    int bufpos;
    char buf[REDIS_REPLY_CHUNK_BYTES];
} redisClient;

레디스 클라이언트는 각각의 접속한 클라이언트의 상태를 저장하기 위해 사용하는 구조체였다. 이를 이용하여 명령들이나 블록상태, 혹은 pub/sub까지 관리하는 것으로 보인다. 주석을 보니 클라이언트들은 링크드리스트로 관리된다고 한다.

다시 본론으로 돌아와서, setCommand를 찾아보자.

// t_string.c

#define REDIS_SET_NO_FLAGS 0
#define REDIS_SET_NX (1<<0)     /* Set if key not exists. */    // 비트 : 01
#define REDIS_SET_XX (1<<1)     /* Set if key exists. */        // 비트 : 10

void setGenericCommand(redisClient *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) {
    // ... 중략 ...
}

/* SET key value [NX] [XX] [EX <seconds>] [PX <milliseconds>] */
void setCommand(redisClient *c) {
    int j;
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = REDIS_SET_NO_FLAGS;

    for (j = 3; j < c->argc; j++) {
        char *a = c->argv[j]->ptr;
        robj *next = (j == c->argc-1) ? NULL : c->argv[j+1];

        if ((a[0] == 'n' || a[0] == 'N') &&
            (a[1] == 'x' || a[1] == 'X') && a[2] == '\0') {
            flags |= REDIS_SET_NX;
        } else if ((a[0] == 'x' || a[0] == 'X') &&
                   (a[1] == 'x' || a[1] == 'X') && a[2] == '\0') {
            flags |= REDIS_SET_XX;
        } else if ((a[0] == 'e' || a[0] == 'E') &&
                   (a[1] == 'x' || a[1] == 'X') && a[2] == '\0' && next) {
            unit = UNIT_SECONDS;
            expire = next;
            j++;
        } else if ((a[0] == 'p' || a[0] == 'P') &&
                   (a[1] == 'x' || a[1] == 'X') && a[2] == '\0' && next) {
            unit = UNIT_MILLISECONDS;
            expire = next;
            j++;
        } else {
            addReply(c,shared.syntaxerr);
            return;
        }
    }

    c->argv[2] = tryObjectEncoding(c->argv[2]); // 얘는 뭔가?
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

setCommand를 알기 위해서는 setGenericCommand함수도 알아야 한다. 왜냐하면, 아래와 같은 이유다!

setGenericCommand() 함수는 SET 연산을 구현합니다. 이때, 각기다른 옵션과 약간의 변형된 형태도 처리합니다. 이 함수는 SET, SETEX, PSETEX, SETNX를 처리하기 위해 call됩니다.

쟤가 진짜 처리하는 애니까! 그래도 setCommand를 보기로 했으니 먼저 보자. 조금 있다가 setGenericCommand도 함께 보자.

char *a는 명령어 문자열이라 생각하자. NX인지 XX인지, EX인지, PX인지 확인하는 제어문인거 같다. 그냥 넘어가자. 그리고 나면 나오는 tryObjectEncoding이 함수가 무엇을 하는지 찾아야하는데, 찾아가보자.

tryObjectEncoding 함수에 대하여

// obejct.c

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;

    redisAssertWithInfo(NULL,o,o->type == REDIS_STRING); // string 맞는지 확인.

    if (!sdsEncodedObject(o)) return o; // RAW나 EMBSTR 인코딩 된 애들이 아니면, 그냥 반환.

    if (o->refcount > 1) return o; // 혹시 이 string을 참조하는 애가 있는지 확인. 있으면 그냥 반환.

    /* 21자리가 넘는지 확인. 넘으면 INT일 수 없으니까.
     * 그리고 long으로 처리될 수 있는지, string2l 유틸 함수로 시도해봄.
     * 그리고 long으로 처리된 값을 value에 집어넣음. 처리 실패시 0(false)반환. */
    len = sdslen(s);
    if (len <= 21 && string2l(s,len,&value)) {
        if ((server.maxmemory == 0 ||
             (server.maxmemory_policy != REDIS_MAXMEMORY_VOLATILE_LRU &&
              server.maxmemory_policy != REDIS_MAXMEMORY_ALLKEYS_LRU)) &&
            value >= 0 &&
            value < REDIS_SHARED_INTEGERS) // 공유된 INTEGER 값으로 처리 가능한지 확인.
        { // 공유된 INTEGER값으로 처리 가능!
            decrRefCount(o); // 참조를 지우고, 메모리 할당 해제.
            incrRefCount(shared.integers[value]); // 공유된 INTEGER 값 ref count 증가.
            return shared.integers[value]; // 공유된 INTEGER 반환.
        } else { // 공유된 INTEGER론 불가능하지만 long으로 가능하다면,
            if (o->encoding == REDIS_ENCODING_RAW) sdsfree(o->ptr); // 메모리 해제
            o->encoding = REDIS_ENCODING_INT; // INT로 인코딩 타입 변경
            o->ptr = (void*) value; // 위에서 string2l로 만든 value 할당.
            return o;
        }
    }

    if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT) { // 위에꺼 실패하고 EMBSTR 제한 사이즈의 최댓값보다 작으면,
        robj *emb;

        if (o->encoding == REDIS_ENCODING_EMBSTR) return o; // 이미 EMBSTR이면 그냥 반환.
        emb = createEmbeddedStringObject(s,sdslen(s)); // 아니면, EMBSTR로 다시 인코딩 해 생성.
        decrRefCount(o); // 원래 애 메모리 해제
        return emb; // EMBSTR 반환.
    }

    /* 어떤 인코딩도 해낼 수 없었다면, 마지막으로 최대한 공간을 적게 쓰기위해 SDS string을 컴팩션한다. */
    if (o->encoding == REDIS_ENCODING_RAW &&
        sdsavail(s) > len/10)
    {
        o->ptr = sdsRemoveFreeSpace(o->ptr);
    }

    return o;
}

공간을 최대한 절약하기 위해 인코딩을 시도하는 함수다. 뭔저 저 SDS혹은 sds란 단어(함수앞에 엄청 많지 않은가.)에 대해 알아야겠는데, SDS가 뭔지 궁금해서 찾아보니, simple danamic string이라는 라이브러리였다. 이 라이브러리는 C언어를 위한 스트링 라이브러린데, 바이너리 세이프하고, 더 쉽게 C언어에서 스트링을 사용할 수 있게 해준다고 한다. Redis는 이 라이브러릴 사용해 스트링을 표현한다.

+--------+-------------------------------+-----------+
| Header | Binary safe C alike string... | Null term |
+--------+-------------------------------+-----------+
         |
         `-> Pointer returned to the user.

sds는 이런 개념을 사용하여, 헤더에 메타 데이터를 저장할 수 있게 한다. 기존 C언어의 스트링이 사용하다보면 불편한게 한두가지가 아니다보니 쓰는 듯 하다. 아무튼 얘는 이렇게 생겨먹어서, 사용하다보면 공간이 남는 경우가 있는데, redis는 최대한의 메모리 활용을 위해 이 여유분이 10%를 넘으면, Shrinking string(메모리를 컴팩션 하는.) 작업을 통해 최대한 메모리를 아낀다. 이때 호출하는 sds라이브러리의 함수가 바로 sds sdsRemoveFreeSpace(sds s);다. 과거(2.6버전)에는 이 작업이 없었던 것 같은데, 생겼다.

과거에는 EMBSTR 인코딩 타입이 없었으나 새로 생겼다. 이 새로생긴 이상한 이름의 인코딩 타입은, 정말 신박한 아이디어인데, redisObject와 연속적으로 이 sds string을 위치 시키는 방법의 인코딩이다. 즉 연속적인 메모리에 함께 위치한다. 그리고 이 sds string는 수정이 불가능하다. 아래 그림으로 어떤 말인지 살펴보자.

+--------------+-----------+------------+--------+----+
| robj data... | robj->ptr | sds header | string | \0 |
+--------------+-----+-----+------------+--------+----+
                     |                       ^
                     +-----------------------+

이런식이다. 이 경우, 원래 스트링 처리 기법은 그대로 사용할 수 있으면서도, cache locality를 극대화 할 수 있어 유리하다고 한다. 이게 무슨말이냐면, 메모리 주소에 접근할 때, 보통 해당 주소 뿐만 아니라 주변까지 포함한 블록 전부를 캐시에 가져오게 되는데, 이렇게 redisObject와 붙여놓으면 당연히 함께 캐시되니 퍼포먼스상 이득일 수 밖에 없다는 것이다. 또 시스템 콜(매우 느린)에서도 이득인데, 원래 할당을 을 robj위해 한번, robj->ptr을 위해 한번 더, 총2번했어야하는데 이제 한방에 할 수 있다는 퍼포먼스상 이점이 있다. 당연히 초기화나 조회, 메모리 카피시도 매번 유리해진다. 이런 세심함! 레디스의 성능은 여기서 나오나보다.

뿐만 아니라, 코드에서도 이런 세심함은 느껴진다. (물론 다들 이렇게 하긴 할건데… 내가 안하던거라..)

// redis.h

#define redisAssertWithInfo(_c,_o,_e) ((_e)?(void)0 : (_redisAssertWithInfo(_c,_o,#_e,__FILE__,__LINE__),_exit(1)))

#define sdsEncodedObject(objptr) (objptr->encoding == REDIS_ENCODING_RAW || objptr->encoding == REDIS_ENCODING_EMBSTR)

redisAssertWithInfo나 sdsEncodedObject같은 애들을 보면 레디스는 왠만한 애들은 함수를 안쓰고 #define을 이용해 정의했다. 나라면 함수로 만들었을 것 같은데, 어떻게해서든 운영 자원을 아끼려는 노력의 일환으로 보였다.

다시 돌아오자. setCommand로.

// t_string.c

void setCommand(redisClient *c) {

    // ... 중략 ...

    c->argv[2] = tryObjectEncoding(c->argv[2]); // 얘는 뭔가?
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

이제 그 인코딩 된 내용을 c->argv[2]에 집어넣는다는 것을 알게 됐다. 저기에는 robj의 포인터가 저장된다. 아마, 그게 set명령어의 인자로 쓰이는 것 같다. 이제 실제 일을 처리하는 setGenericCommand을 살펴볼 차례다.

// t_string.c

void setGenericCommand(redisClient *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) {
    long long milliseconds = 0; /* initialized to avoid any harmness warning */

    if (expire) {
        if (getLongLongFromObjectOrReply(c, expire, &milliseconds, NULL) != REDIS_OK)
            return;
        if (milliseconds <= 0) {
            addReplyErrorFormat(c,"invalid expire time in %s",c->cmd->name);
            return;
        }
        if (unit == UNIT_SECONDS) milliseconds *= 1000;
    }

    if ((flags & REDIS_SET_NX && lookupKeyWrite(c->db,key) != NULL) ||
        (flags & REDIS_SET_XX && lookupKeyWrite(c->db,key) == NULL))
    {
        addReply(c, abort_reply ? abort_reply : shared.nullbulk);
        return;
    }
    setKey(c->db,key,val);
    server.dirty++;
    if (expire) setExpire(c->db,key,mstime()+milliseconds);
    notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"set",key,c->db->id);
    if (expire) notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,
        "expire",key,c->db->id);
    addReply(c, ok_reply ? ok_reply : shared.ok);
}

expire와 관련된 구현은 다음에 살펴보기로하자. 지금 중요한 것은 setKey함수다. addReply함수는 OK응답을 하는 함수다. 저기를 보면, default가 shared.ok다. 그렇다. SET 커맨드는 실패하지 않는다.

// db.c

void setKey(redisDb *db, robj *key, robj *val) {
    if (lookupKeyWrite(db,key) == NULL) {
        dbAdd(db,key,val);
    } else {
        dbOverwrite(db,key,val);
    }
    incrRefCount(val);
    removeExpire(db,key);
    signalModifiedKey(db,key); // client들에게 변경 이벤트를 알린다.
}

setKey 함수는 고수준의 Set operation을 표현하는 함수다. 이 함수는 현재 해당 키를 가진 object가 있는지 없는지 검사하고, 있다면 overwrite를, 없다면 새 object를 할당하는 역할을 한다. incrRefCount는 해당 값이 1회 참조됨을 의미하며, 저장되면서 key에 참조됐음을 표현한다. 기존에 key에 할당되어있던 expire은 없앤다. (키에 새로운 값이 할당되었으므로 기존에 있던건 제거해야.)

signalModifiedKey는 다음에 알아보도록 하자.

getCommand도 알아보자.

int getGenericCommand(redisClient *c) {
    robj *o;

    if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL)
        return REDIS_OK;

    if (o->type != REDIS_STRING) {
        addReply(c,shared.wrongtypeerr);
        return REDIS_ERR;
    } else {
        addReplyBulk(c,o);
        return REDIS_OK;
    }
}

void getCommand(redisClient *c) {
    getGenericCommand(c);
}

비교적 매우 간단하다. c->argv[1](redis command의 GET다음 인자)가 key다. lookupKeyReadOrReply로 DB를 확인해 해당 키를 조회한 후, 반환한다.

끝

기본적인 구현에 대한 내용은 알아보았다.
천천히 좀 더 자세히 들어가보자. 초반부터 오바하다 지치지 않도록 천천히.

태그 티스토리 redis 레디스 아키텍쳐 내부구조 소스