Redis 源码学习（一）：常用数据结构

简介

本系列通过 redis 3.2.x 源代码分析 redis 程序
redis 通过 io 复用同时服务多个 client ；降低网络 io 等待时间
内部通过一个主循环顺序处理命令，实现单线程处理，避免了加锁带来的性能消耗以及降低程序维护的复杂度

本章主要介绍 redis 的基础数据结构：

1. 对象 object
2. 动态字符串 sds
3. 哈希表 dict

Object

redis 所有的数据都被包装成了 object，然后保存到 db
db 实际上是在内存中维护的一个哈希表 dict
server.h 中定义了 redis 的 object 结构以及相关函数

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

/* Redis object implementation */
void decrRefCount(robj *o);
void decrRefCountVoid(void *o);
void incrRefCount(robj *o);
robj *resetRefCount(robj *obj);
void freeStringObject(robj *o);
void freeListObject(robj *o);
void freeSetObject(robj *o);
void freeZsetObject(robj *o);
void freeHashObject(robj *o);
robj *createObject(int type, void *ptr);
robj *createStringObject(const char *ptr, size_t len);
robj *createRawStringObject(const char *ptr, size_t len);
robj *createEmbeddedStringObject(const char *ptr, size_t len);
robj *dupStringObject(robj *o);
int isObjectRepresentableAsLongLong(robj *o, long long *llongval);
robj *tryObjectEncoding(robj *o);
robj *getDecodedObject(robj *o);
size_t stringObjectLen(robj *o);
robj *createStringObjectFromLongLong(long long value);
robj *createStringObjectFromLongDouble(long double value, int humanfriendly);
robj *createQuicklistObject(void);
robj *createZiplistObject(void);
robj *createSetObject(void);
robj *createIntsetObject(void);
robj *createHashObject(void);
robj *createZsetObject(void);
robj *createZsetZiplistObject(void);
int getLongFromObjectOrReply(client *c, robj *o, long *target, const char *msg);
int checkType(client *c, robj *o, int type);
int getLongLongFromObjectOrReply(client *c, robj *o, long long *target, const char *msg);
int getDoubleFromObjectOrReply(client *c, robj *o, double *target, const char *msg);
int getLongLongFromObject(robj *o, long long *target);
int getLongDoubleFromObject(robj *o, long double *target);
int getLongDoubleFromObjectOrReply(client *c, robj *o, long double *target, const char *msg);
char *strEncoding(int encoding);
int compareStringObjects(robj *a, robj *b);
int collateStringObjects(robj *a, robj *b);
int equalStringObjects(robj *a, robj *b);
unsigned long long estimateObjectIdleTime(robj *o);
#define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)

robj包括

1. 数据类型
   
2. 编码类型
   
3. lru 信息
   
4. 引用计数
   
5. 数据指针

robj 中数据都是以 void * 的方式保存，获取之后转换成对应类型   
比如：    
int *integer_data = robj->ptr; 是获取一个整数指针  
char *str_data = robj->ptr; 获取一个字符串（字节数组）指针    
Person *struct_data = robj->ptr; 获取一个自定义数据结构指针  

robj 通过引用计数管理内存

void decrRefCount(robj *o);
void incrRefCount(robj *o);

当程序需要引用 object ，通过调用 incrRefCount 可以防止外部释放掉 object
在使用完之后调用 decrRefCount ；当引用计数递减到 1 decrRefCount 会触发 free 内存操作

SDS sample dynamic string

redis 中动态字符串数据结构
sds.c sds.h

sds 是非常常用的数据类型，包括每次从命令行接收的 args 也是通过 sds 包装后传给 command 回调函数的

void demoCmd(client *c)
{
    long long id;
    if (!string2ll(c->argv[1]->ptr, sdslen(c->argv[1]->ptr), &id)) {
        addReply(c, shared.err);
        return;
    }
    ...
}

sds 中包含了字符串常用的函数：

sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t len);
sds sdscatlen(sds s, const void *t, size_t len);
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);
sds sdscpy(sds s, const char *t);

sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, int start, int end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);
void sdsIncrLen(sds s, int incr);
sds sdsRemoveFreeSpace(sds s);
size_t sdsAllocSize(sds s);
void *sdsAllocPtr(sds s);

/* Export the allocator used by SDS to the program using SDS.
 * Sometimes the program SDS is linked to, may use a different set of
 * allocators, but may want to allocate or free things that SDS will
 * respectively free or allocate. */
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

sds 的信息存储在串开头的前面，根据不同的初始化长度，创建不同的sds头

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // 通过初始长度获取 type 定义
    char type = sdsReqType(initlen); 
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); // 通过 type 获取头结构体的大小
    unsigned char *fp; /* flags pointer. */

    // 初始化的内存：sds头+初始长度+1
    sh = s_malloc(hdrlen+initlen+1); 
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    // s 是要返回的首地址，这个首地址是去掉头部的，所以我们在外部可以直接将 sds 当做 const char* 使用
    s = (char*)sh+hdrlen;  
    fp = ((unsigned char*)s)-1;
    // 根据不同的 sds type 编辑头部信息
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

释放 sds 内存需要使用 sdsfree 函数；注意，不是 sds_free 函数

/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    // 释放的内存空间从 s 初始地址向前找到他的头部地址，再开始释放
    s_free((char*)s-sdsHdrSize(s[-1]));
}

util 中包含了 string2ll、string2l、ll2string、d2string 字符串和整数转换的函数

int ll2string(char *s, size_t len, long long value);
int string2ll(const char *s, size_t slen, long long *value);
int string2l(const char *s, size_t slen, long *value);
int d2string(char *buf, size_t len, double value);

哈希表

redis 中的直接查找都是使用这个哈希表，包括指令查找
源文件：dict.c dict.h

哈希存储流程：

1. 通过hash 函数将数据分到 k 桶
   
2. hash 值冲突的情况，将数据在 k 桶内按照链表存储
   
3. 字符串哈希算法：MurmurHash2；大小写敏感字符串哈希算法：djb hash；32位整数哈希算法：Thomas Wang’s 32 bit Mix Function
   
4. 长整数建议使用 dictGenHashFunction ，也就是 MurmurHash2 算法；将大整数转成字符串再进行哈希
   

hash 接口定义

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;

hashFunction 哈希函数，决定k进入哪一个哈希桶
keyDup key 复制；NULL 为不复制，直接使用传入的key内存地址
valDup value 复制；NULL 为不复制，直接使用传入的 value 内存地址
keyCompare 哈希冲突下，查找数据的 key 比较函数
keyDestructor 当成员被从哈希表删除，在这里进行 key 内存销毁
valDestructor 当成员被从哈希表删除，在这里进行 value 内存销毁

哈希查找流程：

1. 首先通过 hashFunction 计算出哈希 k 桶
   
2. 通过 keyCompare 对 k 桶数据一次进行精确比较，并返回符合的值