推荐书籍《redis设计与实现》

基础数据结构

简单动态字符串 (SDS)

内容物

1. len: 已用字节数量，保存的字符串长度

   • 不包括\0，好处是可以重用一部分C库函数；
   • 获取长度仅需O(1)时间复杂度。
   • 杜绝缓冲区溢出

2. free: 未用字节的数量

   • 和C字符串相比，减少修改字符串的内存重分配次数

     • 空间预分配

       1. 如果进行修改之后，SDS的len将变成13字节，那么程序也会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1=27字节（额外的一字节用于保存空字符）。
       2. 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。举个例子，如果进行修改之后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度将为30MB+1MB+1byte。

     • 惰性空间释放

       比如sdstrim之后没有释放多出来的空间，而是放入free中，需要的时候可以显式释放。

3. buf: 字节数组。

• 二进制安全

  保存的时候是什么样子，读取的时候就是什么样子。可以写入空字符。都是用二进制方式来处理数据的。使用len判断是否结束而不是’\0’。

链表

内容物

node内有：前节点，后节点，值。

list内有：表头、表尾节点，节点值复制、释放、对比函数。

特点

双端，无环，有头尾，有长度，多态（用void*指针来保存值）。

字典

内容物

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于size-1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash索引
    // 当rehash不在进行时，值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

用拉链法解决冲突。拉成单链表，没有尾指针，新节点加在链表头部。

rehash

目的是维持负载因子在合理范围内。步骤如下：

1. 分配空间，收缩分配第一个大于ht[0].used的2ⁿ，扩展分配第一个大于ht[0].used*2的2ⁿ
2. 把ht[0]的键值对全部重新计算位置，放到ht[1]上面。
3. 释放ht[0]，ht[1]变成ht[0]，ht[1]创建空白表。

渐进式rehash

1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。

2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。

3）在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时（都先在ht[0]上，查不到再去ht[1]），程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。

4）随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

跳表

作用：快速访问节点，平均O（logN）、最坏O（N）复杂度的查找。实现简单。

内容物

• header：指向跳跃表的表头节点。

• tail：指向跳跃表的表尾节点。

• level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。

• length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

节点

typedef struct zskiplistNode {
    // 层
    struct zskiplistLevel {
        // 前进指针，用于访问位于表尾方向的其他节点
        struct zskiplistNode *forward;
        // 跨度，记录了前进指针所指向节点和当前节点的距离
        unsigned int span;
    } level[];
    // 后退指针，指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
    struct zskiplistNode *backward;
    // 分值，在表内从小到大排列。
    double score;
    // 成员对象，指向一个SDS对象，分值相同的按照这个从小到大再排序，要求每个值都不同。
    robj *obj;
} zskiplistNode;

创建节点的时候，根据幂次定律随机生成1-32的值作为level数组的大小。

压缩链表

顺序型数据结构。每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成。