Redis底层数据结构

1. 类型与编码

1.1 对象类型

对象类型	类型常量	TYPE命令的输出
String	REDIS_STRING	“string”
List	REDIS_LIST	“list”
Hash	REDIS_HASH	“hash”
Set	REDIS_SET	“set”
Sorted Set	REDIS_ZSET	“zset”

1.2 对象编码

编码常量	底层数据结构	TYPE命令的输出
REDIS_ENCODING_INT	long 类型的整数	“int”
REDIS_ENCODING_EMBSTR	embstr 编码的简单动态字符串	“embstr”
REDIS_ENCODING_RAW	简单动态字符串	“raw”
REDIS_ENCODING_HT	字典	“hashtable”
REDIS_ENCODING_LINKEDLIST	双端链表	“linkedlist”
REDIS_ENCODING_ZIPLIST	压缩列表	“ziplist”
REDIS_ENCODING_QUICKLIST	快速链表	“quicklist”
REDIS_ENCODING_INTSET	整数集合	“intset”
REDIS_ENCODING_SKIPLIST	跳跃表和字典	“skiplist”

1.3 类型与编码的对应关系

对象类型	对象编码	满足条件
String	int	整数字符串
String	embstr	字符长度 <= 44
String	raw	字符长度 > 44
List	ziplist	元素个数 <= list-max-ziplist-size 且元素长度 <= list-max-ziplist-value
List	linkedlist	元素个数 > list-max-ziplist-size 或元素长度 > list-max-ziplist-value
List	quicklist	3.2及以上版本
Hash	ziplist	字段个数 <= hash-max-ziplist-size 且字段长度 <= hash-max-ziplist-value
Hash	hashtable	字段个数 > hash-max-ziplist-size 或字段长度 > hash-max-ziplist-value
Set	intset	集合保存的元素全是整数且元素个数 <= set-max-intset-entries
Set	hashtable	集合保存的元素不全是整数或元素个数 > set-max-intset-entries
Sorted Set	ziplist	有序集合保存的元素数量 <= zset-max-ziplist-entries 且有序集合保存的所有元素成员的长度都 <= zset-max-ziplist-value
Sorted Set	skiplist	有序集合保存的元素数量 > zset-max-ziplist-entries 且有序集合保存的所有元素成员的长度都 > zset-max-ziplist-value

2. 数据结构

2.1 SDS

SDS的数据结构定义如下：

struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];

};

相比C字符串，SDS具有以下优点：

O(1)复杂度获取字符串长度。
杜绝缓冲区溢出。
减少修改字符串长度时所需的内存重分配次数。
二进制安全。
兼容部分 C 字符串函数。

2.2 链表

链表的数据结构定义如下：

typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所包含的节点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

} list;

链表的节点的数据结构定义如下：

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

链表被广泛用于实现 Redis 的各种功能，比如列表键、发布与订阅、慢查询、监视器等等。实现特性如下：

双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ，对链表的访问以 NULL 为终点。
带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O(1) 。
多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

2.3 字典

字典的数据结构定义如下：

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

字典的哈希表的数据结构定义如下：

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

字典被广泛用于实现 Redis 的各种功能，其中包括数据库和哈希键。实现特性如下：

Redis 中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个用于平时使用，另一个仅在进行 rehash 时使用。
当字典被用作数据库的底层实现，或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面，并且这个 rehash 过程并不是一次性地完成的，而是渐进式地完成的。

2.4 跳跃表

跳跃表的数据结构定义如下：

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

跳跃表的节点的数据结构定义如下：

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

跳跃表是有序集合的底层实现之一，除此之外它在 Redis 中没有其他应用。实现特性如下：

Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成，其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度），而 zskiplistNode 则用于表示跳跃表节点。
每个跳跃表节点的层高都是 1 至 32 之间的随机数。
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

2.5 整数集合

整数集合的数据结构定义如下：

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

整数集合是集合键的底层实现之一，实现特性如下：

整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
整数集合只支持升级操作，不支持降级操作。