RDB落地全量数据及Redis存储设计 — redis源码分析

Redis是以Hash的方式在内存中组织的,所有的值都统一在一个hash之下,结构如下

redis结构设计

以一种方便理解的说法来说,就是所有的Redis的数据,都是存储在dictht这个结构体里面,size,used,sizemask记录了一些属性,table指向由dictEntery构成的数组,hash数组,使用拉链法处理冲突,字符串转int 用的是 MurmurHash2算法(具体实现见下面 dictGenHashFunction函数)。

dictEntry的定义挺有意思的。

typedef struct dictEntry {

    // 键
    void *key;

    // key的类型
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;
} dictEntry;

key , void 指针,指向的是存储的值的名字,无论是string,还是hash,保存的时候,都有一个对应的指定的名字,就是保存在这里的,union中,保存的是值,无论是hash,还是string,list尽在一个union之中,尚未发现u64以及s64用途,因为是拉链法,所以next指针指向下一个相同key值的entry。

两个void指针,指向的都是一个结构体,robj,其实对于key来说,一个sds就可以了,这里使用robj或许是为了统一化的考虑吧,而对于val,robj则是后续处理的关键,

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的存储设计,一个拉链hash以及void指针的巧妙使用而已。

把结构说了个大概,剩下的,就是如何保存这个结构,把这个巨大的hash保存在文件里面。我们从rdb.c的int rdbSave(char *filename) 开始,filename是保存成的rdb文件名字,不过redis是先生成一个临时文件,待临时文件生成完毕,数据存储好,然后更改文件名,应该是防止丢失覆盖数据的。

创建临时文件,初始化rio,生成hash迭代器,遍历数据库之后,开始进入核心的地方,

        while((de = dictNext(di)) != NULL) {
            sds keystr = dictGetKey(de);
            robj key, *o = dictGetVal(de);
            long long expire;

            // 根据 keystr ,在栈中创建一个 key 对象
            initStaticStringObject(key,keystr);

            // 获取键的过期时间
            expire = getExpire(db,&key);

            // 保存键值对数据
            if (rdbSaveKeyValuePair(&rdb,&key,o,expire,now) == -1) goto werr;
        }

di可以理解为之前提到的hash数组,dictNext的作用,就是从di这个数组中得到下一个dictEntry值,从0开始,一直遍历到最后,没有太多要说的,不过要注意,di的hash数组是有两个的,一个是rehash使用的。

在这个while循环里面,主要得到三个值,一个是keystr,sds结构,一个是o,就是保存值的地方,这里依然使用的robj,因为o的结构比较复杂多变,一会需要特殊处理,所以不像key那样直接将就将robj中存储的sds提出来了。第三个值是expire,键的过期事件,这个时间也是单独一个hash存储的,保存在rdb文件中的,就是这三个值,k,v以及过期事件,now 是当前的时间戳,过期的变量不保存进rdb。

进入rdbSaveKeyValuePair函数,

int rdbSaveKeyValuePair(rio *rdb, robj *key, robj *val,
                        long long expiretime, long long now)
{
    /* Save the expire time
     *
     * 保存键的过期时间
     */
    if (expiretime != -1) {
        /* If this key is already expired skip it
         */
        if (expiretime < now) return 0;

        if (rdbSaveType(rdb,REDIS_RDB_OPCODE_EXPIRETIME_MS) == -1) return -1;
        if (rdbSaveMillisecondTime(rdb,expiretime) == -1) return -1;
    }

    /* Save type, key, value
     *
     * 保存类型,键,值
     */
    if (rdbSaveObjectType(rdb,val) == -1) return -1;
    if (rdbSaveStringObject(rdb,key) == -1) return -1;
    if (rdbSaveObject(rdb,val) == -1) return -1;

    return 1;
}

第一个if不表,后三个if,第一个先保存类型,将来解析的时候,先读取这个,然后确定后面的数据格式。redis共5种数据类型,除了string之外,每种类型底层实现各对应 2 – 3 种数据结构。

  1. List       由压缩列表,双端列表
  2. set         整数列表和hash表
  3. zset       压缩列表和跳跃表,hash表
  4. Hash    压缩列表和hash表

第一个if 将对应的结构类型存储,第二个,将key值存储,直接调用的就是string类型的保存,第三种调用的函数是rdbSaveObject,该函数对val进行了判断,针对不同类型数据,进行不同的处理。

该函数有点长,贴出来一个zset的存储吧,感受下是如何存储的,其他的都是类似的处理。

 } else if (o->type == REDIS_ZSET) {
        /* Save a sorted set value */
        if (o->encoding == REDIS_ENCODING_ZIPLIST) {
            size_t l = ziplistBlobLen((unsigned char*)o->ptr);

            // 以字符串对象的形式保存整个 ZIPLIST 有序集
            if ((n = rdbSaveRawString(rdb,o->ptr,l)) == -1) return -1;
            nwritten += n;
        } else if (o->encoding == REDIS_ENCODING_SKIPLIST) {
            zset *zs = o->ptr;
            dictIterator *di = dictGetIterator(zs->dict);
            dictEntry *de; 

            if ((n = rdbSaveLen(rdb,dictSize(zs->dict))) == -1) return -1;
            nwritten += n;

            // 遍历有序集
            while((de = dictNext(di)) != NULL) {
                robj *eleobj = dictGetKey(de);
                double *score = dictGetVal(de);

                // 以字符串对象的形式保存集合成员
                if ((n = rdbSaveStringObject(rdb,eleobj)) == -1) return -1;
                nwritten += n;

                // 成员分值(一个双精度浮点数)会被转换成字符串
                // 然后保存到 rdb 中
                if ((n = rdbSaveDoubleValue(rdb,*score)) == -1) return -1;
                nwritten += n;
            }
            dictReleaseIterator(di);
        }

zset的保存,之所以选择zset,是因为zset的结构是所有的数据结构中最复杂的,可以看到,zset中,同时使用了hash字典和skiplist两种结构,为了效率,不惜double了内存

typedef struct zset {                                                                                                                                                          

    // 字典,键为成员,值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;

    // 跳跃表,按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;

} zset;

MurmurHash2的实现算法

unsigned int dictGenHashFunction(const void *key, int len) {
    /* 'm' and 'r' are mixing constants generated offline.
     They're not really 'magic', they just happen to work well.  */
    uint32_t seed = dict_hash_function_seed;
    //也是24位的数字
    const uint32_t m = 0x5bd1e995;
    const int r = 24;

    /* Initialize the hash to a 'random' value */
    uint32_t h = seed ^ len; 

    /* Mix 4 bytes at a time into the hash */
    const unsigned char *data = (const unsigned char *)key;

    while(len >= 4) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    /* Handle the last few bytes of the input array  */
    switch(len) {
    case 3: h ^= data[2] << 16;
    case 2: h ^= data[1] << 8;
    case 1: h ^= data[0]; h *= m;
    };   

    /* Do a few final mixes of the hash to ensure the last few
     * bytes are well-incorporated. */
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return (unsigned int)h;
}

图片来自《Redis设计与实现》,并参考了其内容。

Leave a comment

Your email address will not be published.

*