Redis 之字典和跳表

字典

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

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

dict相关结构定义：

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

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

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

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

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

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

rehashidx默认为-1，如果需要rehash，在dictExpand函数里会将它置为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。

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

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

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

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

跳表

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

实现代码：

zskiplistNode：

层级：每个节点记录了多个后序节点的指针，一层一个指向，level包含了多个指向，层越多，访问跨度越大，概率访问速度就越快

前进指针：这个和普通的链表的next等价，指向下一个邻近节点。level[0]指向邻近的节点，方便遍历

跨度：level[i].span 表示指向节点和当前的距离，指向null的span为0，可以根据span来判定某个节点的排位

后退指针：skiplist是个双向链表，可以根据表尾tail从后向前访问，每次只能后退一个节点

分值和成员：score为double型，是人为设定的一个分值，用于排序，obj则是指向具体的内容，同一个表中，分值可以相同，但对象必须唯一，zslInsert的时候找插入位置会去比较：

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

形成类似的结构：

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

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

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

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

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

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

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

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

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

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

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

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