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

 typedef struct listNode {
 ​
     // 前置节点
     struct listNode *prev;
 ​
     // 后置节点
     struct listNode *next;
 ​
     // 节点的值
     void *value;
 ​
 } listNode;

 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 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;

 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 dictType {
 ​
     // 计算哈希值的函数
     unsigned int (*hashFunction)(const void *key);
 ​
     // 复制键的函数
     void *(*keyDup)(void *privdata, const void *key);
 ​
     // 复制值的函数
     void *(*valDup)(void *privdata, const void *obj);
 ​
     // 对比键的函数
     int (*keyCompare)(void *privdata, const void *key1, const void *key2);
 ​
     // 销毁键的函数
     void (*keyDestructor)(void *privdata, void *key);
 ​
     // 销毁值的函数
     void (*valDestructor)(void *privdata, void *obj);
 ​
 } dictType;

 # 使用字典设置的哈希函数，计算键 key 的哈希值
 hash = dict->type->hashFunction(key);
 ​
 # 使用哈希表的 sizemask 属性和哈希值，计算出索引值
 # 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
 index = hash & dict->ht[x].sizemask;

 # 负载因子 = 哈希表已保存节点数量 / 哈希表大小
 load_factor = ht[0].used / ht[0].size

 

跳跃表的实现

跳跃表由两部分组成：zskiplist、zskiplistNode

跳跃表节点

跳跃表节点的实现由 redis.h/zskiplistNode 结构定义：

 typedef struct zskiplistNode {
 ​
     // 后退指针
     struct zskiplistNode *backward;
 ​
     // 分值
     double score;
 ​
     // 成员对象
     robj *obj;
 ​
     // 层
     struct zskiplistLevel {
 ​
         // 前进指针
         struct zskiplistNode *forward;
 ​
         // 跨度
         unsigned int span;
 ​
     } level[];
 ​
 } zskiplistNode;

1.层

跳跃表节点的数组，每个节点的数组可以保存多个元素，用于表示层数。没个元素中包含了指向下一个节点的指针以及两个节点间的跨度。

一般来说，层的数量越多，访问节点的速度就会越快

2.前进指针

从表的表头方向指向表的表尾方向，用于遍历链表，当读到空时结束遍历

3.跨度

用于记录两个节点间的距离

作用是快速定位某个节点的前一个节点

跨度的大小也会影响跳跃表的性能，跨度过大会导致空间浪费，跨度过小会影响查找性能

4.后退指针

每次只能后退一个节点

5.分值与成员

节点的分值（score属性）：double类型，跳跃表的所有节点都是按照分值排序的

节点的成员变量（obj属性）：指针，指向一个字符串对象，对象里面保存了一个SDS值

 

跳跃表

跳跃表通常使用一个zskiplist结构来持有这些节点

 typedef struct zskiplist{
     
     //表头节点和表尾节点
     structz skiplistNode *header, *tail;
     
     //表中节点的数量
     unsigned long length;
     
     //表中层数最大的节点的层数
     int level;
 } zskiplist;

 

跳跃表的API

 

 

整数集合

集合键的底层实现之一，只用于保存整数值元素

整数集合的实现（intset）

每个 intset.h/intset 结构表示一个整数集合：

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

contents 数组是整数集合的底层实现： 整数集合的每个元素都是 contents 数组的一个数组项（item）， 各个项在数组中按值的大小从小到大有序地排列， 并且数组中不包含任何重复项。

length 属性记录了整数集合包含的元素数量， 也即是 contents 数组的长度。

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组， 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值：

• 如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t 类型的整数值 （最小值为 -32,768 ，最大值为 32,767 ）。

• 如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个项都是一个 int32_t 类型的整数值 （最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。

• 如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个项都是一个 int64_t 类型的整数值 （最小值为 -9,223,372,036,854,775,808 ，最大值为 9,223,372,036,854,775,807 ）。

 

升级

目的：

解决新元素插入整数集合时，新元素过长，集合存储空间不足

步骤：

1. 根据新元素的类型， 扩展整数集合底层数组的空间大小， 并为新元素分配空间。

2. 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。

3. 将新元素添加到底层数组里面。

 

升级的好处

提升灵活性

通常一个数据结构中只使用一种类型的值

而整数集合可以通过升级底层数组来适应新的元素，防止出现类型错误，这种做法非常的灵活

节约内存

整数集合既可以让集合能同时保存三种不同类型的值， 又可以确保升级操作只会在有需要的时候进行， 这可以尽量节省内存。

 

降级

整数集合不支持降级

 

整数集合的API

 

 

 

压缩列表

是列表键和哈希键的底层实现之一，用来存储较小的整数值或长度较短的字符串

 

压缩列表的构造

压缩列表的各个组成部分及用途

 

• zlbytes

  • 类型：uint32_t

  • 长度：4 字节

  • 用途：记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend 的位置时使用

• zltail

  • 类型：uint32_t

  • 长度：4 字节

  • 用途：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址

• zllen

  • 类型：uint16_t

  • 长度：2 字节

  • 用途：记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。

• entryX

  • 类型：列表节点

  • 长度：不定

  • 用途：压缩列表包含的各个节点，节点的长度由节点保存的内容决定。

• zlend

  • 类型：uint8_t

  • 长度：1字节

  • 用途：特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

 

压缩列表节点的构成

每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成

 

previous_entry_length

作用：以字节为单位，记录了压缩列表前一个节点的长度，可以根据当前节点的起始地址来计算出前一个节点的起始地址。

• 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节： 前一节点的长度就保存在这一个字节里面。

• 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE（十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。

压缩列表的从表尾向表头遍历操作就是使用这一原理实现的： 只要我们拥有了一个指向某个节点起始地址的指针， 那么通过这个指针以及这个节点的 previous_entry_length 属性， 程序就可以一直向前一个节点回溯， 最终到达压缩列表的表头节点。

 

encoding

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度：

• 一字节、两字节或者五字节长， 值的最高位为 00 、 01 或者 10 的是字节数组编码： 这种编码表示节点的 content 属性保存着字节数组， 数组的长度由编码除去最高两位之后的其他位记录；

• 一字节长， 值的最高位以 11 开头的是整数编码： 这种编码表示节点的 content 属性保存着整数值， 整数值的类型和长度由编码除去最高两位之后的其他位记录；

 

 

content

节点的 content 属性负责保存节点的值， 节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding 属性决定。

 

连锁更新

原因：由于previous_entry_length的特性，新加入的节点大于或等于254，导致下一个节点的previous_entry_length需要修改，修改后又大于或等于254，由此往复，出现需要连续修改大量的previous_entry_length（也有可能由于删除而导致连锁更新）

但是，由于一连串250左右的节点出现几率很小，且重新分配的时间复杂的为O(N)，所以连锁更新的复杂度为O(N)，不必担心连锁更新会影响性能

 

压缩列表API

 

 

对象

对象类型与编码

Redis中的对象使用redisObject结构来表示：

该结构中和保存数据有关的三个属性分别是 type 属性、 encoding 属性和 ptr 属性：

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

 

 

类型

• 当我们称呼一个数据库键为“字符串键”时， 我们指的是“这个数据库键所对应的值为字符串对象”；

• 当我们称呼一个键为“列表键”时， 我们指的是“这个数据库键所对应的值为列表对象”

type属性：

 

TYPE命令：

 

 

编码和底层实现

ptr指向底层实现

encoding记录了对象使用的编码

 

属性的值为下面常量中的一个：

 

 

每种类型的对象至少含有两种不同的编码：

 

 

不同编码的对象所对应的 OBJECT ENCODING 命令输出：

 

 

通过 encoding 属性来设定对象所使用的编码， 而不是为特定类型的对象关联一种固定的编码， 极大地提升了 Redis 的灵活性和效率， 因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码， 从而优化对象在某一场景下的效率

 

字符串对象

字符串对象的编码可以是int、raw或者embstr

• 如果字符串对象保存的是整数值，那么编码设置为int

• 如果字符串对象保存的是字符串值，并且字节长度大于39字节，那么编码设置为raw

• 如果字符串对象保存的是字符串值，并且字节长度小于等于39字节，那么编码设置为embstr

 

使用 embstr 编码的字符串对象来保存短字符串值有以下好处：

1. embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。

2. 释放 embstr 编码的字符串对象只需要调用一次内存释放函数， 而释放 raw 编码的字符串对象需要调用两次内存释放函数。

3. 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面， 所以这种编码的字符串对象比起 raw 编码的字符串对象能够更好地利用缓存带来的优势。

 

字符串对象保存各种类型值得编码方式：

 

 

编码的转换

int 编码的字符串对象和 embstr 编码的字符串对象在条件满足的情况下， 会被转换为 raw 编码的字符串对象。

• 对于int编码的字符串对象，我们执行一些命令，使得不再是整数值，而是一个字符串值，那么将从int转变为raw类型

• embstr编码的字符串对象实际上是只能读的，当我们对embstr编码的对象执行任何操作时，都会将对象编码从embstr转变为raw

 

字符串命令的实现

 

 

列表对象

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

• ziplist编码的列表对象是使用压缩列表作为底层实现的

• linkedlist编码的列表对象是使用双端链表作为底层实现的

 

编码转换

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

1. 列表对象保存的所有字符串元素的长度都小于 64 字节；

2. 列表对象保存的元素数量小于 512 个；

不能满足这两个条件的列表对象需要使用 linkedlist 编码。

注意：以上两个条件的上限是可以修改的，具体需查看配置文件

 

当使用ziplist编码的对象无法满足上面的两个条件中的任意一个时，对象编码装换操作将被执行，原本保存在压缩列表里面的元素将会被移到双端列表中。ziplist编码也会变成linkedlist编码

 

列表命令的实现

 

 

 

 

哈希对象

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

ziplist编码的哈希对象，有新的键值加入哈希对象时，程序先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值得压缩对象节点保存到压缩列表表尾

hashtable编码的哈希对象，哈希对象每个字典键值对保存一个哈希键值对

 

编码装换

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

1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；

2. 哈希对象保存的键值对数量小于 512 个；

不能满足这两个条件的哈希对象需要使用 hashtable 编码。

注意：以上两个条件的上限是可以修改的，具体需查看配置文件

转换方式与列表对象转换相同

 

哈希命令的实现

 

 

集合对象

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

hashtable编码的集合对象，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字符串的值则是全部设置为NULL；

 

编码的转换

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

1. 集合对象保存的所有元素都是整数值；

2. 集合对象保存的元素数量不超过 512 个；

不能满足这两个条件的集合对象需要使用 hashtable 编码。

注意：第二个条件的上限是可以修改的，具体需查看配置文件

转换方式与列表对象转换相同

 

集合命令的实现

 

 

有序集合对象

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

ziplist编码的有序集合对象，第一个节点保存元素的成员，二第二个节点保存元素的分值。压缩列表内的集合元素按分值从小到大进行排序

skiplist编码的有序集合使用zset结构作为底层实现，zset结构包含一个字典和一个跳跃表

 

skiplist编码的有序集合同时使用字典和跳跃表的原因：

1. 跳跃表和字典都会使用指针指向同一个元素和分值，不会造成空间浪费

2. 单独使用字典时，虽然查找操作的时间复杂度为O(1)，但是当需要对集合对象进行范围性操作时，需要的时间复杂度较高，且需要而外的内存空间

3. 单独使用跳跃表时，范围操作的时间复杂度较小，但是查找起来相比字典会低很多

 

编码的转换

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

1. 有序集合保存的元素数量小于 128 个；

2. 有序集合保存的所有元素成员的长度都小于 64 字节；

不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

注意：以上两个条件的上限是可以修改的，具体需查看配置文件

转换方式与列表对象转换相同

 

有序集合命令的实现

 

 

类型检查与命令多态

Redis 中用于操作键的命令基本上可以分为两种类型。

其中一种命令可以对任何类型的键执行， 比如说 DEL 命令、 EXPIRE 命令、 RENAME 命令、 TYPE 命令、 OBJECT 命令， 等等

而另一种命令只能对特定类型的键执行， 比如说：

• SET 、 GET 、 APPEND 、 STRLEN 等命令只能对字符串键执行；

• HDEL 、 HSET 、 HGET 、 HLEN 等命令只能对哈希键执行；

• RPUSH 、 LPOP 、 LINSERT 、 LLEN 等命令只能对列表键执行；

• SADD 、 SPOP 、 SINTER 、 SCARD 等命令只能对集合键执行；

• ZADD 、 ZCARD 、 ZRANK 、 ZSCORE 等命令只能对有序集合键执行；

诸如此类。

 

类型检查的实现

目的：

为了实现对特定类型的键使用相应的命令，需要先检查输入键的类型。

实现：

类型特定命令所进行的类型检查是通过 redisObject 结构的 type 属性来实现的

 

多态命令的实现

Redis除了根据对象的类型来判断键是否能够执行该命令之外，还会根据值对象的编码方式来选择正确的命令

 

内存回收

Redis自己创建了一个应用计数技术来实现内存的回收机制，程序可以通过跟踪对象的应用计数信息，在适当的时候自动释放对象并进行内存回收

每个对象的引用计数信息由 redisObject 结构的 refcount 属性记录：

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

对象的引用计数信息会随着对象的使用状态而不断变化：

• 在创建一个新对象时， 引用计数的值会被初始化为 1 ；

• 当对象被一个新程序使用时， 它的引用计数值会被增一；

• 当对象不再被一个程序使用时， 它的引用计数值会被减一；

• 当对象的引用计数值变为 0 时， 对象所占用的内存会被释放。

修改对象引用计数的API

 

 

对象共享

除了用于实现引用计数内存回收机制之外， 对象的引用计数属性还带有对象共享的作用

 

在 Redis 中， 让多个键共享同一个值对象需要执行以下两个步骤：

1. 将数据库键的值指针指向一个现有的值对象；

2. 将被共享的值对象的引用计数增一。

 

目前来说，Redis会在初始化服务器时创建一万个字符串对象，这些对象包含了0~9999

创建共享字符串对象的数量可以通过修改 redis.h/REDIS_SHARED_INTEGERS 常量来修改

 

例外，数据结构中嵌套了字符串对象的，也可以使用这些共享字符串对象

 

为什么Redis不使用包含共享字符串的对象？

• 由于当服务器考虑将共享对象设置为键的值对象时，需要先检查共享对象与待创建的目标对象是否完全一致。而越复杂的对象，对比起来所需要的复杂度越高，消耗的CPU时间也会越高

 

对象的空转时长

除了前面介绍过的 type 、 encoding 、 ptr 和 refcount 四个属性之外， redisObject 结构包含的最后一个属性为 lru 属性， 该属性记录了对象最后一次被命令程序访问的时间：

 typedef struct redisObject {
 ​
     // ...
 ​
     unsigned lru:22;
 ​
     // ...
 ​
 } robj;

OBJECT IDLETIME 命令可以打印出给定键的空转时长， 这一空转时长就是通过将当前时间减去键的值对象的 lru 时间计算得出的

 

如果服务器打开了 maxmemory 选项， 并且服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru ， 那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时， 空转时长较高的那部分键会优先被服务器释放， 从而回收内存