Redis面试必知必会（上）：基本数据结构和对象系统

1.基本数据结构

Redis 有一套独有的对象系统来实现自己的键值对数据库，对象系统中包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。这五种类型对象的实现则是基于最底层的数据结构，包括：简单动态字符串、链表、字典、跳跃表、整数集合和压缩列表。

本节的第一部分介绍基本数据结构，第二部分介绍对象系统。

1.1.简单动态字符串

1.1.1.应用场景

1.1.2.结构

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

1.1.3.内存示例

1.1.4.补充内容

sds 与 C 字符串的共同点和区别

• 共同点

1. 二者都使用长度为 N+1 的字符数组表示长度为 N 的字符串，且最后一个元素总是空字符 ‘\0’。

• 区别

内存分配规则

• 空间预分配

空间预分配用于优化 SDS 的字符串增长操作： 当 SDS 的 API 对一个 SDS 进行修改， 并且需要对 SDS 进行空间扩展的时候， 程序不仅会为 SDS 分配修改所必须要的空间， 还会为 SDS 分配额外的未使用空间：

1. 如果对 SDS 进行修改之后， SDS 的长度（也即是 len 属性的值）将小于 1 MB ， 那么程序分配和 len 属性同样大小的未使用空间；
2. 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。

• 惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用。

与此同时， SDS 也提供了相应的 API ， 让我们可以在有需要时， 真正地释放 SDS 里面的未使用空间， 所以不用担心惰性空间释放策略会造成内存浪费。

1.2.双端链表

1.2.1.应用场景

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

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

1.2.3.内存示例

1.2.4.补充内容

• 多态

  链表节点使用 void* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

1.3.字典

1.3.1.应用场景

• redis 的数据库底层结构
• 哈希键底层实现

1.3.2.结构

// 哈希表
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;

1.3.3.内存示例

1.3.4.补充内容

• 哈希算法

  一个键值对要添加到字典里，需要先通过哈希算法计算出哈希值，然后根据哈希值计算出键值要插入的键值对对应与哈希表中的下标，然后插入到哈希表中。Redis 使用的哈希算法为 MurmerHash2。

• 解决键冲突

  计算出插入下标后，如果发现该下标处已经有数据了，需要将插入的数据接在已有数据后形成单链表，通过单链表解决键冲突。

• 渐进式 rehash

  随着操作不断进行，哈希表中的键值对会不断增多或减少，为了让负载因子维持在一个合理范围内，需要对哈希表对大小进行相应扩展或收缩，这就需要用到渐进式 rehash 方法。分为四步：

  1. 为 ht[1] 分配空间， 让字典同时持有 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 操作已完成。
     

1.4.跳跃表

1.4.1.应用场景

• 代替平衡树

  在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单

• 有序集合键的底层实现

  如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳跃表来作为有序集合键的底层实现。

1.4.2.结构

// 跳跃表
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;

1.4.3.内存示例

1.5.整数集合

1.5.1.应用场景

• 集合键

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

1.5.2.结构

typedef struct intset {
    // 编码方式 -- INTSET_ENC_INT16｜INTSET_ENC_INT32｜INTSET_ENC_INT64
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组 -- contents 数组的真正类型取决于 encoding 属性的值
    int8_t contents[];
} intset;

1.5.3.内存示例

1.5.4.补充内容

• 升级（upgrade）

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

  1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。以添加一个 int32_t 的整数 65535 为例，升级后数组大小将是 32 * 4 = 128 位：
     

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

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

1.6.压缩列表

1.6.1.应用场景

• 列表键

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

• 哈希键

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

1.6.2.结构

• 压缩列表

• 节点

每个压缩列表节点可以保存一个字节数组或者一个整数值， 其中， 字节数组可以是以下三种长度的其中一种：

1. 长度小于等于 63 字节的字节数组；
2. 长度小于等于 16383 字节的字节数组；
3. 长度小于等于 4294967295 字节的字节数组；

而整数值则可以是以下六种长度的其中一种：

1. 4 位长，介于 0 至 12 之间的无符号整数；
2. 1 字节长的有符号整数；
3. 3 字节长的有符号整数；
4. int16_t 类型整数；
5. int32_t 类型整数；
6. int64_t 类型整数。

每个压缩列表节点都由三个部分组成:

• previous_entry_length

  记录了压缩列表中前一个节点的长度，属性本身占用1 字节或者 5 字节。

  • 1字节：前一节点的长度小于 254 字节，前一节点的长度就保存在属性的这一个字节里。
  • 5字段：前一节点的长度大于等于 254 字节，属性的第一字节会被设置为 0xFE（十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。

• encoding

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

  • 值的最高位为 00 、 01 或者 10：表示节点的 content 属性保存的是字节数组，元素的长度分别对应一字节、两字节或者五字节；
  • 值的最高位为 11：表示节点的 content 属性保存着整数值， 元素的类型和长度由编码除去最高两位之后的其他位记录。

• content

  属性负责保存节点的值， 节点值可以是一个字节数组或者整数。

1.6.3.内存示例

1.6.4.补充内容

• 连锁更新

背景：

每个节点的 previous_entry_length 属性都记录了前一个节点的长度：

• 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
• 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

现在， 考虑这样一种情况： 在一个压缩列表中， 有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN，然后在表头节点加一个长度大于等于 254 字节的新节点：

因为 e1 的 previous_entry_length 属性仅长 1 字节， 它没办法保存新节点 new 的长度， 所以程序将对压缩列表执行空间重分配操作， 并将e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长，现在 e1 的总长度超过了 254 字节，程序需要对压缩列表执行空间重分配操作：

同理，e1 的扩展又会引发 e2 的扩展，e2 的扩展会引发 e3 的扩展 …… 这就是连锁更新。除了添加新节点可能会引发连锁更新之外， 删除节点也可能会引发连锁更新。

要注意的是， 尽管连锁更新的复杂度较高， 但它真正造成性能问题的几率是很低的：

• 首先， 压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点， 连锁更新才有可能被引发， 在实际中， 这种情况并不多见；
• 其次， 即使出现连锁更新， 但只要被更新的节点数量不多， 就不会对性能造成任何影响： 比如说， 对三五个节点进行连锁更新是绝对不会影响性能的；

因为以上原因， ziplist Push 等命令的平均复杂度仅为 O(N) ， 在实际中， 我们可以放心地使用这些函数， 而不必担心连锁更新会影响压缩列表的性能。

2.对象系统

Redis 使用对象来表示数据库中的键和值， 每次当我们在 Redis 的数据库中新创建一个键值对时， 我们至少会创建两个对象， 一个对象用作键值对的键（键对象）， 另一个对象用作键值对的值（值对象）。

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

typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // 引用计数
    int refcount;
    // 空转时长
    unsigned lru:22;
    // ...
} robj;

• type 和 encoding：类型和编码
  其中 type 支持 6 中类型，每种类型支持的编码方式如下图所示：
  
• refcount：引用计数

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

1. 将数据库键的值指针指向一个现有的值对象；
2. 将被共享的值对象的引用计数增一。

举个例子， 字符串对象 A 和 B 都包含整数值 100，此时 A 和 B 会共享该字符串对象，如下图所示：

除了对象的引用计数从之前的 1 变成了 2 之外， 其他属性都没有变化。

因为 C 语言并不具备自动的内存回收功能， 所以 Redis 在自己的对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制， 通过这一机制， 程序可以通过跟踪对象的引用计数信息， 在适当的时候自动释放对象并进行内存回收。

• lru：空转时长

空转时长指当前时间和对象最后一次被命令程序访问的时间之间的差值。

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

2.1.字符串对象

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

• embstr 和 raw 的区别

  分配内存的方式不同，raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构， 而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间， 空间中依次包含 redisObject 和 sdshdr 两个结构。

2.2.列表对象

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

2.3.哈希对象

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

2.4.集合对象

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

2.5.有序集合对象

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