Redis源码阅读之数据结构

2016-05-12 | 阅读：次

文件	内容
`sds.h` 和 `sds.c`	Redis 的动态字符串实现。
`adlist.h` 和 `adlist.c`	Redis 的双端链表实现。
dict.h 和 dict.c	Redis 的字典实现。
`server.h` 中的 `zskiplist` 结构和 `zskiplistNode` 结构，以及 t_zset.c 中所有以 zsl 开头的函数，比如 zslCreate 、 zslInsert 、 zslDeleteNode ，等等。	Redis 的跳跃表实现。
hyperloglog.c 中的 hllhdr 结构，以及所有以 hll 开头的函数。	Redis 的 HyperLogLog 实现。

adlist

adlist是个基本的双端链表。支持自定义dup、match方法，用于复制list和在list中搜索，其他部分倒是没有什么特别的。

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

写java习惯了，看c的实现真的是感觉处处都是黑科技啊。但是这样确实能够大量减少代码量，而且记得之前看过一句话，代码量和bug数量是绝对成正比的。

dict

redis的dict和JDK中的类似，同样采用了数组+链表的方式保存entry，但是redis中因为把所有并发请求都串行化了，所以在编码的时候不需要考虑并发冲突。基于这个优势，redis在内存中维护了两个hashtable对象ht[0]和ht[1]，平时entry都保存在ht[0]中，当需要进行hash表扩容的时候，打开rehash标记并把数据从ht[0]中取出，挨个转移到ht[1]中。每次的hash操作如find、getRandom、add、remove都会步进式的执行这个rehash操作，redis后台也会有定时任务辅助执行rehash操作，定时的rehash操作会在时间段内用100的步长进行操作。这里会有个判断条件，如果发现当前dict的安全迭代器的数量不是0，表示当前有人在安全模式下迭代dict，就不能进行rehash操作了。相比较而言，JDK8中的rehash操作就复杂多了，需要做各种并发冲突的避免。

作为对比，可以看下java8中的HashMap扩容实现。

server.h

server.h中定义了一些比较重要的结构体，比如zskiplist

rockiee

rockiee's stone

Redis源码阅读之数据结构

目录

adlist

dict

server.h