《Redis 设计与实现》读书笔记

索引

Redis 设计与实现[1] – 数据结构与对象

Redis 设计与实现[2] – 单机数据库的实现

Redis 设计与实现[3] – 多机数据库的实现

1 简单动态字符串

Redis 没有直接使用 C 语言传统的字符串表示，而是自己构建了一种简单动态字符串（SDS），使用 SDS 作为 REdis 的默认字符串表示。

1.1 SDS 定义

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

1.2 SDS 与 C 字符串的区别

• 常数复杂度获取字符串的长度
• 杜绝缓冲区溢出
• 减少修改字符串时带来的内存重分配次数
• 二进制安全
• 兼容部分 C 字符串函数

2 链表

链表在 Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。

2.1 Redis 链表结构

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;

由一个 list 结构和三个 listNode 结构组成的链表如下图所示：

2.2 Redis 链表特性

• 双端
• 无环
• 带表头指针和表尾指针
• 带链表长度计数器
• 多态

3 字典

字典，是一种用于保存键值对的抽象数据结构，在字典中一个键可以和一个值进行关联，这些关联的键和值就称为键值对。Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

3.1 字典实现

Redis 中的字典结构为：

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

ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

下图展示一个普通状态下的字典，其中红框中的是哈希表：

3.2 哈希

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

4 跳跃表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均 O(logN)，最坏 O(N) 的复杂度的节点查找。Redis 使用跳跃表作为有序集合键的底层实现之一。

跳跃表是由 zskiplistNode 和 zskiplist 两个结构定义，其中 zskiplistNode（灰框） 结构用于表示跳跃表节点，zskiplist（红框） 结构用于保存跳跃表节点的相关信息，如下表所示：

• zskiplist

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

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

  level：记录目前跳跃表内，层数最大的那个节点的层数

  length：记录跳跃表的长度

• zskiplistNode

  level：层

  backward：后退指针

  score：分值

  obj：成员对象

5 整数集合

整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现，它可以保存类型为 int16_t、int32_t、int64_t 的整数值。

5.1 整数集合结构

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

5.2 升级

当我们要将一个新的元素添加到整数集合里面，并且新元素的类型比整数集合现有的所有元素的类型都要长，整数集合需要先进行升级，然后才能将新元素添加到整数集合里面。

升级方式：

• 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
• 将底层数组现在的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位置上，并且在放置元素过程中，需要维持底层数组的有序性质不变
• 将新元素添加到底层数组里面

升级优点：

• 提升整数集合的灵活性
• 节约内存

6 压缩列表

压缩列表是列表键和哈希键的底层实现之一，当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做列表建的底层实现。此外，当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就会使用压缩列表来做哈希键的底层实现。

7 对象

Redis 对象类型：字符串对象REDIS_STRING、列表对象REDIS_LIST、哈希对象REDIS_HASH、集合对象REDIS_SET、有序集合对象REDIS_ZSET

7.1 对象类型与编码

Redis 中的每个对象都是一个 redisObject 结构表示：

type struct redisObject {
    // 类型
    unsigned type:4;
    
    // 编码
    unsigned encoding:4;
    
    // 指向底层实现数据结构的指针
    void *ptr;
    
    //...
} robj;

通过 encoding 属性来设置对象所使用的编码，可以使得 Redis 根据不同的使用场景为一个对象设置不同的编码，从而优化对象在某一场景下的效率，举个例子，在列表对象包含的元素较少的时候，Redis 使用压缩列表作为列表对象的底层实现：

• 因为压缩列表比双端列表更节约内存，并且在元素数量较少的时候，在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中
• 随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失，对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表。

7.2 字符串对象

字符串对象的编码可以是 int,raw,embstr

• 如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 类型来表示，那么编码设置为 int
• 如果字符串对象对象保存是一个字符串值，并且这个字符串值的长度大于 32 字节，那么字符串对象将使用 SDS 来保存这个字符串值，并将对象的编码设置为 raw
• 如果保存的字符串值的长度小于等于 32 字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串值（分配内存和释放内存均从 raw 的两次降为一次）
• long double 浮点型也是作为字符串值来保存的

7.3 列表对象

列表对象的编码可以是 ziplist 或者 linkedlist

• ziplist 每个压缩列表节点（entry）保存一个列表元素
• linkedlist 每个双端链表节点（node）都保存一个字符串对象，每个字符串对象都保存一个列表元素

列表对象同时满足以下两个条件的时候列表对象使用 ziplist 编码：

• 列表对象保存的所有字符串元素的长度都小于 64 字节
• 列表对象保存的元素数量小于 512 个

7.4 哈希对象

哈希对象的编码可以是 ziplist 或者 hashtable

• ziplist 编码的哈希对象使用压缩表作为底层实现，保存同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；先添加的在表头方向，后添加的在表尾方向
• hashtable 使用字典作为底层实现，每个键值对都使用一个字典键值对来保存：字典的每个键都是一个字符串对象，对象中保存了键值对的键；字典中每个值都是字符串对象，对象中保存了键值对的值

哈希对象同时满足以下两个条件时，哈希对象使用 ziplist 编码：

• 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节
• 哈希对象保存的键值对数量小于 512个

7.5 集合对象

集合对象的编码可以是 intset 或者 hashtable

• inset 编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面
• hashtable 编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含一个集合元素，而字典的值则全部被设置为 NULL

当集合对象可以同时满足以下两个条件时，对象使用 intset 编码：

• 集合对象保存的所有元素都是整数值
• 集合对象保存的元素数量不超过 512 个

7.6 有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist

• ziplist 编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一个的压缩列表节点来保存，第一个节点保存元素的成员，第二个节点保存元素的分值，元素按照分值从小到大进行排序
• skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个zset 结构同时包含一个字典和一个跳跃表

有序集合对象同时满足以下两个条件使用 ziplist 编码：

• 有序集合保存的元素数量小于 128 个
• 有序集合保存的所有元素成员的长度都小于 64 字节

7.7 检查类型

任何类型的键都可以执行的命令：

DEL、EXPIRE、RENAME、TYPE、OBJECT

只能对特定类型的键执行：

7.8 内存

内存回收

Redis 构建了一个引用计数计数实现的内存回收机制。

typedef struct redisObject {
    // 引用计数
    int refcount;
}robj;

• 创建一个新对象，引用计数值被初始化为 1
• 当一个对象被一个新程序使用时，它的引用计数值会被加 1
• 当一个对象不在被一个程序使用时，它的应用计数值 减 1
• 当对象引用计数值变为 0，对象所占用的内存会被释放

对象共享

Redis 让多个键共享同一个值对象需要执行的步骤为：

• 将数据库键的值指针指向一个现有的值对象
• 将被共享的值对象的应用计数+1