Redis 设计与实现-数据结构和对象篇

发表于 分类于 阅读次数：
Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库，并提供多种语言的 API。本文主要介绍 Redis 的数据结构和对象，数据结构包括简单动态字符串、链表、字典、跳跃表和整数集合，对象是通过数据结构实现的 Redis 对象，在 Redis 中，数据库的键值对、列表、集合、有序集合等数据结构都是通过对象来实现的。本文的内容主要来自《Redis 设计与实现》一书。

数据结构

简单动态字符串 (simple dynamic string, SDS)

用处：
(1) 用于保存数据库中的字符串值
(2) 用作缓冲区(buffer)：比如 AOF 模块中的 AOF 缓冲区和客户端状态中的输入缓冲区

1
2
3
4
5
6
// .sds.h/sdshdr
struct sdshdr {
    int len;    // <1>
    int free;   // <2>
    char buf[]; // <3>
}

<1> 记录 buf 数组中巳使用字节的数量，等于 SDS 所保存字符串的长度
<2> 记录 buf 数组中未使用字节的数量
<3> 字节数组， 用于保存字符串

SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的 1 字节空间，这 1 字节不计算在 SDS 的 len 属性里面(其实应该也不计算在 free 属性里)，并且为空字符分配额外的 1 字节空间，以及添加空字符到字符串末尾等操作，这都是由 SDS 函数自动完成的。

SDS 的内存分配策略

  1. 空间预分配：用于优化 SDS 的字符串增长操作
    • 对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必需的空间，还会为 SDS 分配额外的未使用空间。通过这种预分配策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。
      • 修改后长度 (len) 小于 1MB，将分配和 len 属性同样大小的未使用空间 (len = free)。Tips：还需要额外的一个字节用于保存空字符。
      • 修改后长度 (len) 大于等于 1MB，分配 1MB 的额外空间。Tips：还需要额外的一个字节用于保存空字符。
  2. 惰性空间释放：用于优化 SDS 的字符串缩短操作
    • 程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。
    • SDS 也提供了相应的 API 让用户能够真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

SDS 与 C 字符串的区别

  1. SDS 可以通过常数复杂度获取字符串长度
  2. SDS 杜绝了缓冲区溢出
    • 当 SDS API需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求
    • 如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作
  3. SDS 减少了修改字符串时带来的内存重分配次数
    • 每次增长或者缩短一个 C 字符串，程序总要对保存这个 C 字符串的数组进行一次内存重分配操作。增长字符串需要先通过内存重分配来扩展底层数组的空间大小，如果忘了这一步就会产生缓冲区溢出；缩减字符串时程序需要通过内存重分配来释放字符串不再使用的那部分空间，如果忘了这一步就会产生内存泄漏。
    • Redis 作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果频繁采用内存重分配，这会对性能造成影响。所以 SDS 通过空间预分配策略减少连续执行字符串增长操作所需的内存重分配次数，惰性空间释放策略避免了缩短字符串时所需的内存重分配操作和为将来可能有的增长操作提供了优化。
  4. 二进制安全
    • C 字符串中的字符必须符合某种编码，且不能包含空字符，从而使得 C 字符串只能保存文本数据而不能保存二进制数据(图片、音频、 视频、压缩文件等)。
    • SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，而且所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤或者假设。因此 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据，因此可以适用于各种不同的使用场景。
  5. SDS 兼容部分 C 字符串函数
    • SDS 的 API 遵循 C 字符串以空字符结尾的惯例，将 SDS 保存的数据的末尾设置为空字符，并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符，这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。

链表 (linkedlist)

用处：
(1) 当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现；
(2) 除此之外，发布与订阅、慢查询、监视器等功能也用到了链表；
(3) Redis 服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区(output buffer)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// .adlist.h/listNode
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); // 节点值对比函数
}

Redis 链表特性

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

字典 (dict)

用处：
(1) Redis 的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的；
(2) 字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希键的底层实现；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// .dict.h/dictht
// 哈希表节点
typedef struct dictEntry {
    void *key;          // key
    union {
        void *val;
        uint64_t u64;
        int64_t s64
    } v;                // value
    struct dictEntry *next; // 指向下个哈希表节点，形成链表
}

// 哈希表
typedef struct dictht {
    dictEntry **table;      // 哈希表数组

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

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 *keyl, const void *key2);
    // 销毁键的函数
    void (*keyDestructor) (void *privdata, void *key);
    // 销毁值的函数
    void (*ValDestructor) (void *privdata, void *obj);
} dictType;

// 字典
typedef struct dict {
    dictType *type;     // 类型特定函数 <1> <2>
    void *privdata;     // 私有数据 <3>
    dictht ht[2];       // 哈希表 <4>

    int rehashidx;      // rehash索引
}

<1> type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的
<2> type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。
<3> privdata 属性保存了需要传给那些类型特定函数的可选参数。
<4> ht 属性是一个包含两个项的数组，数组中的每个项都是一个dictht 哈希表。一般情况下，字典只使用 ht[O] 哈希表， ht[l] 哈希表只会在对 ht[O] 哈希表进行 rehash 时使用。
<5> 当 rehash 不进行时，值为 -1。

普通情况下的字典

哈希算法

  1. 先根据键值对的键计算出哈希值和索引值，哈希值 & sizemask = 索引值
  2. 根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面
  3. 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 使用 MunnurHash2 算法来计算键的哈希值。
  4. 解决键冲突：Redis 的哈希表使用链地址法(separate chaining)来解决键冲突。因为 dictEntry 节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置(复杂度为O(1)), 排在其他已有节点的前面。

rehash

  1. 哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子(load factor)维持在一个合理的范围之内，程序需要对哈希表的大小进行相应的扩展或者收缩。
  2. 为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量(ht[0].used)
    • 扩展操作：ht[1] 的大小为第一个大于等于 ht[0].used*2 的 2 的 n 次方
    • 收缩操作：ht[1] 的大小为第一个大于等于 ht[0].used 的 2 的 n 次方
  3. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上。
  4. ht[0] 包含的所有键值对都迁移到 ht[1] 之后(ht[0] 变为空表)，释放 ht[0]，将 ht[1] 设置为 ht[0], 并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。
  5. 什么时候进行 rehash
    • 扩展操作
      • 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1
      • 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5
      • 在执行 BGSAVE 命令或者 BGREWRITEAOF 命令的过程 中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制(copy-on­write)技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。
    • 收缩操作
      • 哈希表的负载因子小于 0.1
    • 负载因子计算：负载因子＝哈希表巳保存节点数量／哈希表大小 或者 load_factor = ht[0].used / ht[0].size
  6. 渐进式 rehash：ht[0] 迁移到 ht[1] 过程并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

渐进式 hash

  1. 为字典的 ht[l] 哈希表分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表
  2. 维持一个索引计数器变量 rehashidx，设置其值为 0，表示 rehash 工作开始。
  3. 在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1], 当 rehash 工作完成之后，程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被 rehash 至 ht[1], 这时程序将 rehashidx 属性的值设为 -1, 表示 rehash 操作已完成。
  5. 渐进式 rehash 过程中，删除、查找、更新等操作会在两个哈希表上进行；而添加操作只在 ht[1] 上进行。

跳跃表 (skiplist)

用处：
(1) Redis 使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员(member)是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现；
(2) 另一个用处是在集群节点中用作内部数据结构。

跳跃表

1
2
3
4
5
6
7
8
9
// redis.h/zskiplistNode
// 跳跃表结构
typedef struct zskiplist {
    structz skiplistNode *header, *tail;    // <1> <2>

    unsigned long length;                   // <3>

    int level;                              // <4>
} zskiplist

<1> header: 指向跳跃表的表头节点。表头节点构造和普通节点相同，但 后退指针、分值和成员对象实际上不会使用。
<2> tail: 指向跳跃表的表尾节点。
<3> level: 记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
<4> length: 记录跳跃表的长度，即跳跃表目前包含节点的数量（表头节点不计算在内）。

1
2
3
4
5
6
7
8
9
10
11
12
// redis.h/zskiplistNode
// 跳跃表节点
typedef struct zskiplistNode {
    struct zskiplistLevel {             // <1>
        struct zskiplistNode *forward;  // <2>
        unsigned int span;              // <3>
    } level[];

    struct zskiplistNode *backward;     // <4>
    double score;                       // <5>
    robj *obj;                          // <6>
}

<1> 层：level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。每次创建一个新跳跃表节点的时候，程序都根据幕次定律(power law, 越大的数出现的概率越小) 随机生成一个介于 1 和 32 之间的值作为level 数组的大小(层高度)
<2> 前进指针：每个层都有一个指向表尾方向的前进指针，用于从表头向表尾方向访问节点
<3> 跨度：记录了前进指针所指向节点和当前节点的距离。指向 NULL 的所有前进指针的跨度都为 0, 因为它们没有连向任何节点。跨度可用于计算排位(rank)：查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
<4> 后退指针：指向位于当前节点的前一个节点，用于从表尾向表头遍历时使用。
<5> 分值：跳跃表中，节点按各自所保存的分值从小到大排列。分值相同的节点将按照成员对象在字典序中的大小来进行排序。
<6> 成员对象：指向一个字符串对象，而字符串对象则保存着一个 SDS 值。

整数集合 (intset)

用处：
(1) 整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

1
2
3
4
5
6
// intset.h/intset
typedef struct intset {
    uint32_t encoding;  // 编码方式 <1>
    uint32_t length;    // 集合包含的元素数量
    int8_t contents[];  // 保存元素的数组 <2>
}

<1> contents 数组的真正类型取决于 encoding 属性的值：encoding 的取值可以为 INTSET_ENC_INT16/INTSET_ENC_INT32/INTSET_ENC_INT32
<2> contents 数组是整数集合的底层实现：整数集合的每个元素都是 contents 数组的一个数组项(item), 各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。另外，虽然属性声明为 int8_t，数组里不保存任何 int8_t 的值。

升级操作

  1. 将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级(upgrade), 然后才能将新元素添加到整数集合里面。
  2. 步骤
    • (1) 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
    • (2) 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
    • (3) 将新元素添加到底层数组里面。修改 encoding 属性；修改 length 属性
  3. 因为每次添加新元素都可能会引起升级，每次升级都需要对底层数组中已有的所有元素进行类型转换，所以时间复杂度为 O(N)。
  4. 引发升级的新元素长度总是比当前所有元素的长度都大，即新元素要么大于所有现有元素(防止在底层数组最末尾，索引 length-1)，要么就小于所有现有元素(放置在底层数组最开头，索引 0)。
  5. 好处
    • (1) 提升整数集合的灵活性：整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将 int16_t、int32_t 或者 int64_t 类型的整数添加到集合中，而不必担心出现类型错误
    • (2) 尽可能地节约内存：集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存
  6. 整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

压缩列表 (ziplist)

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。一个压缩列表可以包含任意多个节点(entry). 每个节点可以保存一个字节数组或者一个整数值。

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

压缩列表组成部分

压缩列表

  1. zlbytes, uint32_t, 4 字节, 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用
  2. zltail, uint32_t, 4 字节, 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址
  3. zllen, uint16_t, 2 字节, 记录了压缩列表包含的节点数量：当这个属性的值小于 UINT16_MAX(65535) 时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出
  4. entryX, 列表结点, 长度不定, 压缩列表包含的各个节点，节点的长度由节点保存的内容决定
  5. zlend, uint8_t, 1 字节, 特殊值 0xFF(十进制255), 用于标记压缩列表的末端

压缩列表节点构成

压缩列表节点

  1. previous_entry_length: 以字节为单位， 记录了压缩列表中前一个节点的长度，属性长度可以为 1 字节或者 5 字节。
    • 如果前一节点的长度小于 254 字节，属性长度为 1 字节
    • 如果前一节点的长度大于等于 254 字节，属性长度为 5 字节，其中第一个字节会被设置为 0xFE(十进制值254)，后四个字节用于保存前一节点的长度。
  2. encoding: 记录了节点的 content 属性所保存数据的类型以及长度，长度使用 1、2 或者 5 字节存储，类型使用 1 字节存储。
    字节数组编码和整数编码
  3. content: 负责保存节点的值，节点值可以是一个字节数组或者整数

压缩列表特性

  1. 从表尾到表头遍历操作：可以通过节点的 previous_entry_length 属性获取到前一个节点的起始地址。
  2. 连锁更新
    • 考虑一种情况，压缩列表中的节点都介于 250 字节和 253 字节之间，这时候添加一个新节点(不小于254字节)，由于 previous_entry_length 会从 1 字节扩展到 5 字节，会依次对所有节点进行更新和空间重分配操作；同理，删除操作也会导致连锁更新。
    • 连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作，而每次空间重分配的最坏复杂度为 O(N), 所以连锁更新的最坏复杂度为 O(stem:[N^2])。
    • 连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的，最坏情况下不仅要求恰好有多个连续的长度介于 250-253 字节且需要更新的节点足够多，因此平均复杂度可以视为 O(N)。
    • ziplistPush、ziplistInsert、ziplistDelete 和 ziplistDeleteRange 四个函数都有可能会引发连锁更新

二进制位数组 (bitarray)

位数组操作命令

  1. SETBIT <key> <offset> <value>: 为位数组指定偏移量上的二进制位设置值，位数组的偏移量从 0 开始计数， 而二进制位的值则可以是 0 或者 1
  2. GETBIT <key> <offset>: 用于获取位数组指定偏移量上的二进制位的值
  3. BITCOUNT <key> [start] [end]: 统计位数组里面， 值为1的二进制位的数量
  4. BITOP <operation> <destkey> <key> [key ...]: 对多个位数组进行运算。operation 可以是 AND、OR、NOT、XOR 这四种操作中的任意一种

位数组

位数组实现

  1. Redis 使用字符串对象来表示位数组，并使用 SDS 结构的操作函数来处理位数组

  2. buf 数组是逆序保存位数组，从而简化 SETBIT 命令实现

  3. GETBIT <bitarray> <offset> 命令

    • (1) 计算 byte = ceil(offset / 8), byte 值记录了 offset 偏移量指定的二进制位保存在位数组的哪个字节
    • (2) 计算 bit = (offset mod 8) + 1, bit 值记录了 offset 偏移量指定的二进制位是 byte 字节的第儿个二进制位。
    • (3) 根据 byte 值和 bit 值，在位数组 bitarray 中定位 offset 偏移量指定的二进制位，返回这个位的值。

  4. SETBIT <bitarray> <offset> <value> 命令

    • (1) 计算 len = ceil(offset / 8) + 1, len 值记录了保存 offset 偏移量指定的二进制位至少需要多少字节
    • (2) 检查 bitarray 键保存的位数组 SDS 的长度是否小于 len, 如果是的话，将 SDS 的长度扩展为 len 字节，并将所有新扩展空间的二进制位的值设置为 0
    • (3) 计算 byte = ceil(offset / 8), byte 值记录了 offset 偏移量指定的二进制位保存在位数组的哪个字节
    • (4) 计算 bit = (offset mod 8) + 1, bit 值记录了 offset 偏移量指定的二进制位是 byte 字节的第儿个二进制位
    • (5) 根据 byte 值和 bit 值，在 bitarray 键保存的位数组中定位 offset 偏移量指定的二进制位，首先将指定二进制位现在值保存在 oldvalue 变量，然后将新值 value 设置为这个二进制位的值。
    • (6) 向客户端返回 oldvalue 变量的值
    • SETBIT 命令执行的所有操作都可以在常数时间内完成，所以该命令的时间复杂度为 O(1)。

  5. BITCOUNT 命令

    • 遍历算法：遍历位数组中的每个二进制位，并在遇到值为 1 的二进制位时，将计数器的值增一，复杂度较高。
    • 查表算法：建立八位长的键到 1 数量的映射，一次读入 8 个位，并通过查表直接知道这个值包含了多少个值为 1 的位，效率比遍历法提升了 8 倍。可以通过修改映射中 key 的位数，实现空间换时间。
    • variable-precision SWAR 算法: 单纯的计算操作，不使用额外的内存 +
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // 32位长度位数组 SWAR
    uint32_t swar(uint32_t i) {
        // 步骤1: 按每两个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量
        i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
        // 步骤2: 按每四个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        // 步骤3: 按每八个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重最。
        i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
        // 步骤4:
        // i*(0x01010101) 语句计算出 bitarray 的汉明重量并记录在二进制位的最高八位
        // >>24 语句则通过右移运算，将 bitarray 的汉明重量移动到最低八位，得出的结果就是 bitarray 的汉明重量
        i = (i*(0x01010101) >> 24);
        return i;
    }
    • Redis 使用查表和 variable-precision SWAR 两种算法实现 BITCOUNT 命令
      • 查表算法使用键长为 8 位的表，表中记录了从00000000 到 11111111 在内的所有二进制位的汉明重量
      • variable-precision SWAR: 每次循环中载人 128 个二进制位，然后调用四次 32 位 variable-precision SWAR 算法来计算这 128 个二进制位的汉明重量
      • 未处理的二进制位的数量小于 128 位时使用查表算法，未处理的二进制位的数量大于等于 128 位时，使用 variable-precision SWAR 算法

  6. BITOP 命令

    • (1) 创建一个空白的位数组 value, 用于保存操作的结果。
    • (2) 对一个或多个位数组的第n个字节(n从0开始)执行操作，结果存到对应的 value 字节

对象

Redis 对象系统包含字符串对象(REDIS_STRING)、列表对象(REDIS_LIST)、哈希对象(REDIS_HASH)、集合对象(REDIS_SET)和有序集合(REDIS_ZSET)。

对于 Redis 数据库保存的键值对来说，键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的任意其中一种。

当我们称呼一个键为“列表键”时，我们指的是“这个数据库键所对应的值为列表对象”。对一个数据库键执行 TYPE 命令时，命令返回的结果为数据库键对应的值对象的类型，而不是键对象的类型。

对象的 ptr 指针指向对象的底层实现数据结构，而这些数据结构由对象的 encoding 属性决定。encoding 属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现。使用 OBJECT ENCODING 命令可以查看一个数据库键的值对象的编码。

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

1
2
3
4
5
6
7
8
9
typedef struct redisObject {
    unsigned type:4;        // 类型
    unsigned encoding:4;    // 编码
    void *ptr;              // 指向底层实现数据结构的指针

    ...
    int refcount;           // 引用计数
    unsigned lru:22;        // 对象最后一次被命令程序访问的时间
}

字符串对象

字符串对象是 Redis 五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

字符串对象编码

  1. int: 如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 类型来表示，那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面(将void• 转换成long)，并将字符串对象的编码设置为int。
  2. raw: 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于 32 字节，那么字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值，并将对象的编码设置为raw。
  3. embstr：如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于 32 字节， 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。
  4. 注意：可以用 long double 类型表示的浮点数在 Redis 中也是作为字符串值来保存的。如果我们要保存一个浮点数到字符串对象里面，那么程序会先将这个浮点数转换成字符串值，然后再保存转换所得的字符串值。

embstr 编码

  1. 专门用于保存短字符串的一种优化编码方式，这种编码和 raw 编码一样，都使用 redisObject 结构和 sdshdr 结构来表示字符串对象。而且 embstr 编码的字符串对象执行命令时产生效果和对 raw 编码的字符串对象执行命令产生的效果是相同的。
  2. raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构，而 embstr 编码只通过一次内存分配函数来分配一块连续的空间，空间中依次包含 redisObject 结构和 sdshdr 结构。
  3. embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次，而且由于所有数据都保存在一块连续的内存中，能够更好地利用缓存带来的优势。

编码转换

  1. 向一个保存整数值的字符串对象追加了一个字符串值，因为追加操作只能对字符串值执行，所以程序会先将之前保存的整数值转换为字符串值，然后再执行追加操作，操作的执行结果就是一个 raw 编码的、保存了字符串值的字符串对象：
  2. Redis 没有为 embstr 编码的字符串对象编写任何相应的修改程序，所以 embstr编码的字符串对象实际上是只读的。对embstr编码的字符串对象执行任何修改命令时，程序会先将对象的编码从 embstr 转换成 raw, 然后再执行修改命令。因为这个原因，embstr 编码的字符串对象在执行修改命令之后，总会变成一个raw编码的字符串对象。

列表对象

列表对象编码

  1. 列表对象的编码可以是 ziplist 或者 linkedlist
  2. ziplist 编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点(entry)保存了一个列表元素。使用 ziplist 编码的列表对象满足 (1) 保存的所有字符串元素的长度都小于64字节 (2) 列表对象保存的元素数量小于 512 个
    ziplist编码的列表对象
  3. linkedlist 编码的列表对象使用双端链表作为底层实现，每个双端链表节点(node)都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。不满足 ziplist 编码条件时则使用 linkedlist 编码
    linkedlist编码的列表对象
  4. 编码条件中的两个上限值可以通过配置文件中关于 list-max-ziplist-value 和 list-max-ziplist-entries 选项进行修改。

编码转换

  1. 对于使用 ziplist 编码的列表对象来说，当使用 ziplist 编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有列表元素都会被转移并保存到双端链表里面，对象的编码也会从 ziplist 变为 linkedlist。

哈希对象

哈希对象编码

  1. 哈希对象的编码可以是 ziplist 或者 hashtable。
  2. ziplist 编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾。
    • 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后。
    • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
    • ziplist 编码的哈希对象需要满足以下两个条件 (1) 所有键值对的键和值的字符串长度都小于 64 字节 (2) 保存的键值对数量小于 512 个。
  3. hashtable 编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存
    • 字典的每个键都是一个字符串对象，对象中保存了键值对的键。
    • 字典的每个值都是一个字符串对象，对象中保存了键值对的值。
    • 不满足 ziplist 编码条件时则使用 hashtable 编码。
  4. 编码条件中的两个上限值可以通过配置文件中关于 hash-max-ziplist-value 和 hash-max-ziplist-entries 选项进行修改。

编码转换

  1. 对于使用 ziplist 编码的列表对象来说，当使用 ziplist 编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有键值对都会被转移并保存到字典里面，对象的编码也会从 ziplist 变为 hashtable

集合对象

集合对象编码

  1. 集合对象的编码可以是 intset 或者 hashtable
  2. intset 编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。intset 编码的集合对象满足下面两个条件: (1) 集合对象保存的所有元素都是整数值；(2) 集合对象保存的元素数量不超过 512 个。
  3. hashtable 编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，字典的值全部设置为 NULL。
  4. 编码条件中的上限值可以通过配置文件中关于 set-max-intset­-entries 选项进行修改。

编码转换

  1. 对于使用 intset 编码的集合对象来说，当使用 intset 编码所需的两个条件的任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在整数集合中的所有元素都会被转移并保存到字典里面，并且对象的编码也会从 intset 变为 hashtable

有序集合对象

有序集合对象编码

  1. 有序集合对象的编码可以是 ziplist 或者 skiplist
  2. ziplist 编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员 (member), 而第二个元素则保存元素的分值 (score)。集合元素按分值从小到大进行排序。
  3. skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个 zset 结构同时包含一个字典和一个跳跃表。
    • 跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的 object 属性保存了元素的成员，而跳跃表节点的 score 属性则保存了元素的分值。
    • 字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。
    • 通过跳跃表可以对有序集合进行范围型操作，通过字典可以用 O(1) 复杂度查找给定成员的分值
    • 两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存
  4. ziplist 编码的集合对象满足下面两个条件
    • (1) 有序集合保存的元素数量小于 128 个
    • (2) 有序集合保存的所有元素成员的长度都小于 64 字节
  5. 编码条件中的上限值可以通过配置文件中关于 zset-max-ziplist-entries 选项和 zset-max-ziplist-value 选项进行修改。

编码转换

  1. 对于使用 intset 编码的集合对象来说，当使用 intset 编码所需的两个条件的任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在整数集合中的所有元素都会被转移并保存到字典里面，并且对象的编码也会从 intset 变为 hashtable。

对象的检查、回收、共享

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

  1. 可以对任何类型的键执行，比如说 DEL 命令、EXPIRE 命令、RENAME 命令、TYPE 命令、OBJECT 命令
  2. 只能对特定类型的键执行
    • SET、GET、APPEND、STRLEN 等命令只能对字符串键执行；
    • HDEL、HSET、HGET、HLEN 等命令只能对哈希键执行；
    • RPUSH 、LPOP 、LINSERT、LLEN 等命令只能对列表键执行；
    • SADD、SPOP、SINTER、SCARD 等命令只能对集合键执行；
    • ZADD、ZCARD、ZRANK、ZSCORE 等命令只能对有序集合键执行；

类型检查实现

  1. 类型特定命令所进行的类型检查是通过 redisObject 结构的 type 属性来实现的
  2. 在执行一个类型特定命令之前，服务器会先检查输人数据库键的值对象是否为执行命令所需的类型，如果是的话，服务器就对键执行指定的命令；否则拒绝执行命令，并向客户端返回一个类型错误。
  3. 多态命令：Redis 除了会根据值对象的类型来判断键是否能够执行指定命令之外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令
    • 基于类型的多态: DEL、EXPIRE、TYPE 等命令，可以同时用于处理多种不同类型的键
    • 基于编码的多态: 一个命令可以同时用于处理多种不同编码。例如 LLEN 命令，对 ziplist 编码的列表对象调用 ziplistLen 函数，对 linkedlist 编码的列表对象调用 listLength 函数

内存回收

  1. 引用计数 (reference counting): 程序通过跟踪对象的引用计数信息， 在适当的时候自动释放对象并进行内存回收
    • 在创建一个新对象时，引用计数的值会被初始化为1
    • 当对象被一个新程序使用时，它的引用计数值会被增一
    • 当对象不再被一个程序使用时，它的引用计数值会被减一
    • 当对象的引用计数值变为 0 时，对象所占用的内存会被释放

对象共享

  1. Redis中支持让多个键共享同一个值对象，这是通过引用计数机制实现的
    • (1) 将数据库键的值指针指向一个现有的值对象
    • (2) 将被共享的值对象的引用计数(redisObject 结构中的 refcount 属性)增一。
  2. 共享对象机制对于节约内存非常有帮助，数据库中保存的相同值对象越多，对象共享机制就能节约越多的内存
  3. 目前 Redis 会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值为 0 到 9999 的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。创建共享字符串对象的数量可以通过修改 redis.h/REDIS_SHARED_INTEGERS 常量来修改。
  4. 使用 OBJECT REFCOUNT 命令查看键的值对象的引用计数

对象的空转时长

  1. redisObject 结构中的 lru 属性记录了对象最后一次被命令程序访问的时间
  2. 空转时长：通过将当前时间减去键的值对象的 lru 时间计算得出的。可以通过 OBJECT IDLETIME 命令输出。
  3. 如果服务器打开了 maxmemory 选项，并且服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru, 那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。