Redis 基本数据结构

Question

Redis中基本的数据结构，以及底层实现。包括字符串、链表、跳跃表、字典等等，这些数据机构是 Redis 实现 字符串、有序集合等等对象的基础。

简单动态字符串（SDS）

全称是 Simple Dynamic String，是Redis自己实现的一种字符串数据结构：

struct sdshdr {
    int len; // 记录buf中已使用字节的数量
    int free; // 记录buf中未使用字节的数量
    char buf[]; // 字节数组，用于保存字符串
}

Redis在保存字符串时，底层使用的就是 SDS。相比于普通的 C 字符串，它有以下的特性和好处：

• 常数复杂度获取字符串长度（直接取 len 属性）
• 对字符串进行修改（比如拼接）时会先检查容量是否满足要求，如果容量不够会先扩容，避免了缓冲区溢出
• 空间预分配（多分配一些空闲空间）和惰性空间释放（缩短字符串时不立即释放多余的空间）可以减少内存重分配的次数，提升性能
• 二进制安全，可以存储任意格式的数据，因为读取字符串不是靠空字符\0来判断结束，而是依靠len属性

链表

Redis 中的列表，底层实现就是用的链表。

typedef stuct list {
    listNode *head; // 表头节点
    listNode *tail; // 表尾节点
    unsigned long len; // 节点数量
    // 下面还有三个函数：
    // dup 用于节点值复制
    // free用于释放节点值
    // match用于对比节点值和另一个值
} list;

Redis 的链表实现的特性可以总结如下：

• 双端链表
• 无环，表头的prev指针和表尾的next指针都指向null
• 带有表头指针和表尾指针
• 带有链表长度计数器
• 多态，可以保存不同类型的值

字典

Redis 作为一种键值对数据库，它的数据库底层实现本身就是字典；Redis 中还有哈希键这种数据类型，字典也是其中一种底层实现。

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

// 字典数据结构定义
typedef struct dict {
    // 为多态字典设置
    dictType *type;
    void privdata;

    // 哈希表
    dictht ht[2];
    int trehashidx; // rehash索引，当rehash不在进行中时，值为-1
} dict;

Redis 的字典这种数据结构底层主要就是两张哈希表，ht[0]和ht[1]，其中一般情况下只使用ht[0]哈希表，只有在进行rehash的时候才会用到ht[1]哈希表。

当要添加一个新的键值对时，会先计算出key的哈希值，然后计算出在哈希表中的索引值，将其放到哈希表的对应索引上。当多个键产生冲突时，Redis 会使用拉链地址法解决冲突，即多个索引相同的节点用单向链表保存，新节点总是被添加到链表的表头位置。

为了让哈希表的负载因子维持在一个合理的范围内，需要进行rehash操作，进行扩展或收缩。当进行rehash操作时，会使用到 ht[1] 哈希表，首先计算出需要给 ht[1] 分配的空间，然后将 ht[0] 中的所有键值对 rehash 到 ht[1] 上，迁移完成后，释放ht[0]，将 ht[1] 设置为 ht[0]，在 ht[1] 创建一个空白哈希表。

为了避免影响服务器性能，整个rehash操作是渐进式完成的。开始 rehash 时，会将 rehashidx 设置为0，逐渐递增，从0开始将ht[0]哈希表上的键值对 rehash 到 ht[1]，完成之后将 rehashidx 置为-1，在这个过程中，如果需要查找，会先找ht[0]再找ht[1]，而新添加的键值对一律会被保存到ht[1]。

跳跃表

跳跃表（skiplist）是 Redis 有序集合的底层实现之一。同一个跳跃表中多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。跳跃表中的节点按照分值大小进行排序，分值相同是按照成员对象的大小进行排序。

整数集合

当一个只包含整数的集合中的元素数量不多时，redis 就会使用整数集合（intset）作为集合的底层实现：

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; // 集合包含的元素数量
    int8_t contents[]; // 保存元素的数组
} intset;

contents 数组是保存集合元素的地方，按照从小到大的顺序有序排列，并且不存在重复项。

如果新添加到集合的元素的类型比集合中现有元素的类型都要长时（比如现有元素最长是int32，要添加int64），整个集合需要先进行升级，扩展空间大小，将现有元素转换成新的类型并放到正确的位置上，然后添加新元素。时间复杂度为O(N)。整数集合不支持降级操作。

整数集合的好处在于支持整数的各种类型（int16, int32, int64）十分灵活，并且只有在需要的时候才会升级，节省内存。

压缩列表

当redis中的列表或者哈希键只包含少量元素，并且每个元素要么是小整数值，要么是短字符串时，redis就会使用压缩列表（ziplist）这种数据结构作为底层实现。压缩列表是由连续内存块组成的顺序型数据结构，包含多个节点，每个节点保存一个字节数组或者一个整数值。

压缩列表的每个节点有 previous_entry_length、encoding、content 三个属性。previous_entry_length 记录了前一个节点的长度，所以可以从后往前遍历列表（压缩列表有一个zltail属性记录了表尾节点距起始地址的偏移量，可以确定表尾节点的地址）。encoding 用不同的编码表示存放的不同类型。

添加或删除节点，可能会在压缩列表中引发连锁更新（略），但出现几率不高并且总节点数并不多，不会影响性能。

对象

上面介绍的链表、字典等都是Redis中的底层数据结构，Redis在这些数据结构的基础上实现了对象。在Redis中，一共有字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。在创建键值对时，键就是一个字符串对象，而值就是上面的五种对象之一。

typedef struct redisObject {
    unsigned type:4; // 类型，五种类型之一
    unsigned encoding:4; // 编码，表示底层使用了什么数据结构实现，因为一种对象类型可能有不同的实现
    void *ptr; // 指向底层实现数据结构的指针
    // ...
} robj;

字符串对象（string）

字符串对象的编码有int, raw, embstr三种，其中int用来保存整数值；raw用来保存比较长的字符串值，embstr用来保存长度小于等于39字节的字符串值。浮点数也是作为字符串值来存储的。embstr相比于raw的好处是字符串对象和指针指向的sdshdr底层结构是在一片连续的内存空间，申请和释放都只需要一次，性能更好。

int和embstr在条件满足的情况下，会被转换成raw编码的对象。比如使用append在int后面追加了一个字符串值。而embstr是只读的，因此进行修改总是会变成raw编码的对象。

列表对象（list）

列表的底层实现是链表或者压缩列表。当列表中的元素数量比较少并且每个元素的长度也比较小时，会使用压缩列表，不满足条件时会从压缩列表转换为链表

哈希对象（hash）

类似列表，底层实现是压缩列表或者hashtable，当使用压缩列表实现时，同一个哈希对象的键和值是相邻的，保存键的节点在前。

集合对象（set）

当所有元素都是整数值时并且元素数量不多时，使用intset实现，否则使用hashtable作为底层实现。

有序集合对象（sorted set）

底层实现是压缩列表或者跳跃表。当使用压缩列表时，每个集合元素用两个相邻的节点来保存，第一个节点保存元素的成员（member），第二个节点保存元素的分值（score）。当使用跳跃表作为底层实现时，会同时使用字典，跳跃表中按照分值从小到大保存元素，字典中键为元素的成员，值为对应的分值。

同时使用跳跃表和字典实现是为了让范围型操作和查找操作都能更快的执行。

其他

多态命令的实现

执行命令比如 del，expire，lrange 等之前，会先检查需要操作的对象类型，然后决定是否返回错误或者如何执行

内存回收

基于引用计数的内存回收机制，每个对象的计数信息在 refcount 属性中维护。创建时初始化为1，不再被程序使用时减一，被新程序使用时加一。计数值变为0时内存会被释放。

对象共享

redis 在初始化服务器时，会创建 0 到 9999 的一万个字符串对象，当有这些范围内的字符串对象被创建时，就会直接共享这些对象，引用计数+1，而不会创建新的对象。

对象的空转时长

每个对象还有一个 lru 属性记录了最后一次被程序访问的时间，可以用 object ideltime 打印出空转时长。