Redis 之字典和跳表

Redis 之字典和跳表

字典

Redis整个数据库其实就是一个大的字典

set msg "hello world"

以上命令实际上就是设置了数据库字典中一个key为msg，value为“hello world”

dict相关结构定义：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

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

dictEntry是一个单链表实现，next指向下一个结点。v采用了联合，可以使int64_t 或者void * 或者uint64_t。

dictht即使一个哈希表的实现，简单讲就是一个数组，每个数组上指向一条链表，每添加一对键值对，讲key进行hash运算得到一个值，按一定算法映射到数组中，哈希算法必然存在哈希冲突，对于相同的hash的值，挂在同一个链表上。

   idx = h & d->ht[table].sizemask;
   he = d->ht[table].table[idx];

sizemask永远为size-1，因为数组下标从0开始，hash与sizemask与即可计算出数组下标。

size表示数组的大小，used记录已使用结点的数量,rehash时会减少。会用于评估负载因子

注意：这个used统计的只是table数组中的已使用的数量，不会统计链表中的量。

dict里的ht[2],适用于rehash的，根据负载因子，判断是否需要rehash，进行hash表扩容，

if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
    return dictExpand(d, d->ht[0].used*2);
}

rehashidx默认为-1，如果需要rehash，在dictExpand函数里会将它置为0。

d->ht[1] = n;
d->rehashidx = 0;

初始的ht是ht[0],扩容后将新哈希表设置为 1 号哈希表，将字典的 rehash 标识打开开始对字典进行 rehash。

dictType实际上定义了一些操作特定键值对的函数，其中包括复制值，复制键，计算hash等。

hash表的hash算法选取尤为重要，要避免大量的hash冲突，而且分散随机，不然性能退化很严重，dict的hash算法选取了MurmurHash，这个知道一下就好了。

渐进式rehash：

一旦判定需要rehash怎么办？直接rehash吗?redis是单线程的，直接进行rehash，所有的后续请求都会被阻塞到那，redis并没有直接全部rehash，通过rehashidx记录了rehash的数组下标，将整个rehash分散到各个请求中。单步rehash，也支持按时间批量rehash。

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;
    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

单步rehash会分布到find，get，delete, add中

dictEntry *dictFind(dict *d, const void *key)
{
    if (dictIsRehashing(d)) _dictRehashStep(d);
}

dictEntry *dictAddRaw(dict *d, void *key)
{
    if (dictIsRehashing(d)) _dictRehashStep(d);
}
...

注意一点，在进行添加的时候，是需要根据当前是否在rehash，在添加到新ht，不再放旧的。

ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

在删除的时候，同样也要做类似的判断，都需要操作。find的时候，实际上只要没有rehash结束，需要在两个ht里都寻找，因为指向的是指针，所以无论哪一个找到都可以返回了。

if (d->ht[0].used == 0) {
    zfree(d->ht[0].table);
    d->ht[0] = d->ht[1];
    _dictReset(&d->ht[1]);
    d->rehashidx = -1;
    return 0;
}

当rehash结束后，释放掉ht[0]原有内容，重新指向ht[1],重置rehashidx 为-1。

跳表

跳表(skiplist)是一种有序数据结构，双链表结构，在每个节点上维护了多个指向后序节点的指针，可以快速访问节点。在Redis中Z开头命令操作的有序集合的实现都是基于zskiplist的。

实现代码：

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

zskiplistNode：

1. 层级：每个节点记录了多个后序节点的指针，一层一个指向，level包含了多个指向，层越多，访问跨度越大，概率访问速度就越快
2. 前进指针：这个和普通的链表的next等价，指向下一个邻近节点。level[0]指向邻近的节点，方便遍历
3. 跨度：level[i].span 表示指向节点和当前的距离，指向null的span为0，可以根据span来判定某个节点的排位
4. 后退指针：skiplist是个双向链表，可以根据表尾tail从后向前访问，每次只能后退一个节点
5. 分值和成员：score为double型，是人为设定的一个分值，用于排序，obj则是指向具体的内容，同一个表中，分值可以相同，但对象必须唯一，zslInsert的时候找插入位置会去比较：

int compareStringObjectsWithFlags(robj *a, robj *b, int flags) {
    if (a == b) return 0;
    ...
    return strcoll(astr,bstr);
    ...
}

多个跳跃节点组成跳跃表：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

形成类似的结构：

[图片上传失败...(image-f4cc6c-1531746014679)]

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                compareStringObjects(x->level[i].forward->obj,obj) < 0))) {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }

插入这里有讲究，从head的最高的level往下找，

1.如果还比指向的节点大，则继续查找，此时就是一个单链表查找了

2.比指向节点小，则再低一层查找

整个过程其实在不断的缩小查找区间，update[] 记录每层第一个比他大的节点的前一个节点，最终只有两种可能，header和将要插入位置的前一个节点,所以下面初始化会直接指向header。这个思考了很久。

rank[]记录了最后一个比他小的节点和当前指向节点的span跨度和，i 层的起始 rank 值为 i+1 层的 rank 值，层数越低越靠前，rank[0]则表示最终插入点的最终排位

    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }

随机生成一个level层数，实际上为了保证随机性，跳表追求的是概率性平衡 。

如果新节点的层数比表中其他节点的层数都要大，update[i]直接指向header，level[i]的span直接设置为最大length。更新zsl->level为最新。

    x = zslCreateNode(level,score,obj);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        /* update span covered by update[i] as x is inserted here */
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
     /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward) x->level[0].forward->backward = x;
    else zsl->tail = x;
    zsl->length++;

    return x;
}//end zslInsert

for循环里等同于双向链表的插入，以及更新span。跳表是带头结点的，如果0层为header，则x就是第一个节点，backword设为NULL，不是则指向update[0]，如果没有forward则为尾节点，更新zsl的tail，length++。

Redis的实现代码简直是C的典范，没有一行多余代码，就这一个函数，就挺费脑子的，我想《Redis设计和实现》在跳表这一章并没有讲具体的插入，也是因为讲了，还是要费些劲儿理解，不过这书还是一本通俗易懂的书。

写此文耗时间的，当然我的理解也加深了，学习就该脚踏实地，吃透。

skiplist的算法性能分析这又是一个话题，写此文的时候，看到了之前一同事张铁蕾写的skiplist，对问题理解之深。网上大量的都是转载他的文章。

为什么Redis选择了skiplist？原文回答，翻译不过来

点击阅读原文跳转到张铁蕾的原文。