[입 개발] Redis internal : Redis Dictionary Type 에 관해서

Redis 는 기본적으로 Hash 형태로 데이터를 관리하지만, 내부적으로 관리가 필요한 정보들 역시, 내부적으로는 Dictionary 라고 부르는 Hash 형태로 관리하고 있습니다. 그런데 이 Dictionary 에 대한 핸들링이, 관리되는 데이터의 종류에 따라서 다르게 처리되어야 할 때가 있습니다. 아마 오늘 글을 그냥 Redis를 쓰시는 분 입장에서는 별 내용이 없고, Redis 소스를 건드리시는 분들에게는 아주 살짝 도움이 될듯합니다.

보통 대부분의 언어에서는 함수 오버라이딩등을 이용한 폴리모피즘을 이용해서 이런 방식의 요구사항을 좀 수월하게 처리하게 되어 있습니다. 그러나 C 에서는… 기본적으로 이런 방식이 제공되지 않지만, 함수 포인터를 이용해서 이런 방식을 구현할 수 있습니다. 가장 유명한 예가, 리눅스 커널의 VFS 같은 부분을 보면 됩니다.

cluster.c 의 clusterInit 코드를 보면 다음과 같이 dictCreate 함수를 이용해서 dictionary를 생성하는 것을 볼 수 있습니다.

    server.cluster->nodes = dictCreate(&clusterNodesDictType,NULL);
    server.cluster->nodes_black_list =
        dictCreate(&clusterNodesBlackListDictType,NULL);

dictCreate 함수를 살펴보면 다음과 같이 dictType, privDataPtr 두개의 파라매터를 가지고, 결과로 dict 를 넘겨줍니다.

dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

    _dictInit(d,type,privDataPtr);
    return d;
}

먼저 dict 구조체부터 살펴보도록 하겠습니다.

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

dict 구조체는 dictType 과 dictht 두개를 가집니다. 여기서 dictht는 dict의 테이블 확장시에 사용하기 위한 것입니다. 그럼 이 dict 안에 있는 dictType은 뭘까요? dictType은 다음과 같이 정의되어 있습니다.

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

dictType 을 보시면 hashFuction, keyDup, valDup, keyCompare, keyDestructor, valDestructor 같은 값들이 정의되어 있습니다. 즉, 함수포인터를 가지고 있기 때문에, 여기서 가리키는 함수의 동작이 다르면, 같은 형태로 보이더라도 서로 다르게 동작하게 할 수 있습니다.

그리고 현재 Redis 에는 다음과 같이 8개의 dictType이 정의되어 있습니다.

  • dictType setDictType;
  • dictType clusterNodesDictType;
  • dictType clusterNodesBlackListDictType;
  • dictType dbDictType;
  • dictType shaScriptObjectDictType;
  • dictType hashDictType;
  • dictType replScriptCacheDictType;

dictType 구조체 안에서 특히 keyCompare 를 통해서 해당 키를 찾아내게 됩니다.
예를 들어서, 내부적으로 실제 키들을 저장하는 곳에서는 dbDictType 을 사용합니다. dbDictType을 보면 다음과 같습니다.

/* Db->dict, keys are sds strings, vals are Redis objects. */
dictType dbDictType = {
    dictSdsHash,                /* hash function */
    NULL,                       /* key dup */
    NULL,                       /* val dup */
    dictSdsKeyCompare,          /* key compare */
    dictSdsDestructor,          /* key destructor */
    dictRedisObjectDestructor   /* val destructor */
};

dbDictType에서는 Key의 비교를 위해서는 dictSdsKeyCompare 를 사용하고, dictSdsKeyCompare는 다음과 같이 구현되어 있습니다.

int dictSdsKeyCompare(void *privdata, const void *key1,
        const void *key2)
{
    int l1,l2;
    DICT_NOTUSED(privdata);

    l1 = sdslen((sds)key1);
    l2 = sdslen((sds)key2);
    if (l1 != l2) return 0;
    return memcmp(key1, key2, l1) == 0;
}

그리고 Redis Command 를 저장하는 곳에서 사용하는 commandTableDictType 에서는 대소문자 구분이 필요없을 때는 dictSdsKeyCaseCompare 를 사용합니다.

int dictSdsKeyCaseCompare(void *privdata, const void *key1,
        const void *key2)
{
    DICT_NOTUSED(privdata);

    return strcasecmp(key1, key2) == 0;
}

위와 같은 형태에서 dictFind를 살펴보면 내부적으로 dictType 함수포인터를 이용하게 됩니다.

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

#define dictCompareKeys(d, key1, key2) \
    (((d)->type->keyCompare) ? \
        (d)->type->keyCompare((d)->privdata, key1, key2) : \
        (key1) == (key2))

위의 dictCompareKeys가 내부적으로 dictType의 keyCompare를 이용하는 것을 볼 수 있습니다. 그런데 여기서 조심해야 하는 것들이 있습니다. 실제 dictFind 에서 key를 넘겨줄 때, dictSdsKeyCompare 는 key가 무조건 sds type이어야 하지만, dictSdsKeyCaseCompare 에서는 실제 값만 비교하므로, 단순 string 이어도 가능합니다. 말 그대로 가능만 합니다. 그런데, 뭔가 잘못 쓰기 시작하면… Redis가 뻥뻥 죽어나가는 걸 보실 수 있을껍니다.

그래서 cluster.c 소스를 보면, 무조건 key가 sds 형태여야 하기 때문에 발생하는 사소한 오버헤드도 존재합니다. 뭐, 그러나 자주 발생하지는 않으니… 그냥 패스를 ㅎㅎㅎ