关于后端:Redis数据结构详解上

提到 Redis，我想大家并不生疏，基本上每个我的项目中都会有它的身影呈现。作为一款性能卓越的中间件，其功能强大，在零碎中常常扮演着非常重要的角色，像缓存、分布式锁和音讯队列等，都是咱们所熟知的性能。Redis 在咱们的我的项目中频繁呈现的起因，次要是它能够晋升零碎的性能，撑持起零碎的高并发。那么 Redis 这么优良的起因是什么呢？这时咱们可能会想到它基于内存的存储介质，多路复用的 IO 形式，以及主模块的单线程模型等等，但往往漠视了一点，就是 Redis 在底层数据结构上的实现。

当提及 Redis 的数据结构，咱们个别会想到 STRING、LIST、SET、ZSET、HASH 等，没错，这些在咱们平时应用 Redis 的过程中，是间接可能感知到的数据结构。不过，这仅仅是从使用者的角度去看，如果从外部实现角度，这些高层的数据结构还依赖于更底层的实现，在 Redis 对象零碎的实现源码中，就能够找到底层数据结构的编码，如下所示。

注：若没作阐明，本文源码参考 Redis 6.0.0 版本。

上面，咱们顺次介绍下 Redis 的底层数据结构，来看看它们是如何实现的。

简略动静字符串

Redis 是采纳 C 语言实现的，但 Redis 并没有间接应用 C 语言中传统的字符串示意，而是本人构建了一个名为简略动静字符串（simple dynamic string，SDS）的形象类型，在 Redis 的不同版本中，其实现也是不同的，咱们先来看一下 2.8 版本的实现。

struct sdshdr {
    int len;
    int free;
    char buf[];};

其中：

与 C 字符串的比拟

那就有一个问题，Redis 为什么构建了本人的字符串类型，它与 C 字符串的区别在哪，有着什么样的劣势呢，上面咱们就来看一下。

1. 升高获取字符串长度的复杂度

• C 字符串：获取字符串长度时，须要对字符串进行遍历，工夫复杂度为 O(n)。
• SDS：其实现中通过 len 属性记录了字符串的长度，使得获取字符串长度的工夫复杂度升高到了 O(1)，这就确保了获取字符串长度不会成为 Redis 的性能瓶颈。

2. 拼接操作安全性

• C 字符串：进行拼接操作时，使用者须要先查看是否调配了足够的空间，如果遗记了，就有可能造成缓冲区溢出，导致其它空间的值被批改。
• SDS：进行字符串批改时，API 会先查看是否有足够的空间，不满足的话，会依照肯定的策略进行空间扩大，而后再执行批改操作，这样就杜绝了缓冲区的溢出。

3. 缩小内存重调配的次数

对于字符串，咱们常常会进行批改操作，变长或者变短，这会波及到内存重调配，可能须要执行零碎调用，如果批改操作执行得比拟频繁，过多的内存重调配操作就会影响到零碎的性能。

• C 字符串：批改 N 次字符串，须要执行 N 次内存重调配。
• SDS：通过 free 属性实现了空间预调配和惰性空间开释，将批改 N 次字符串，须要执行内存重调配的次数从 N 次升高为最多 N 次。
  a. 空间预调配：当要对字符串的长度进行扩大时，如果空间不够，SDS 是会通过肯定的策略调配更多的空间，将未应用的空间记录到 free 属性中，这样就防止下次扩大时再进行申请空间的操作。
  b. 惰性空间开释：当要缩短字符串时，SDS 并不会开释掉其对应的空间，而是记录到 free 属性中，以便于下次扩大空间时应用。

4. 二进制平安

• C 字符串：字符必须合乎某种编码，并且必须以空字符结尾，这就导致其余地位不能呈现空字符，限度了 C 字符串保留的内容只能是文本数据，不能保留图片、音频等二进制数据。
• SDS：尽管也以空字符结尾，但它是以 len 属性的值来判断是否完结，所以能够保留任何格局的二进制数据，数据在写入时是什么样，被读取时就是什么样。

5. 兼容性

SDS 遵循 C 字符串以空字符结尾的常规，这样就能够重用一部分 C 字符串的库函数。

版本优化

下面咱们剖析了 Redis 为何设计了本人的字符串类型，但你认为这样就能够了吗，在 3.2 及之后的版本中，Redis 又对 SDS 进行了降级，上面咱们来看一下。

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];};

其中：

所做优化

• 3.0 及之前的版本，不同的字符串占用的头部都是雷同的，对于短字符串来说，很节约空间，所以 3.2 及之后的版本针对不同长度的字符串进行了类型优化，能够节俭更多内存空间。
• 勾销了编译时的对齐填充，让编译器以紧凑的模式分配内存，进一步节俭了内存空间；而且也能够不便地进行一些操作，比方，要失去该 SDS 的类型，间接向低地址偏移 1 个字节来获取 flags 字段等。

应用场景

Redis 中字符串对象的底层实现之一就应用了 SDS，像 AOF 模块中的 AOF 缓冲区，以及客户端状态中的输出缓冲区，也是由 SDS 实现的。前言中列举的 OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT 也是字符串对象的底层实现，这两种底层构造会在解说 Redis 的对象零碎中解说。

链表

链表提供了高效的节点重排能力，以及程序性的节点拜访形式，而且增删节点只须要批改前后节点的指针，十分不便，能够灵便地调整链表的长度。链表是一种十分常见的数据结构，像高级编程语言中都有它的身影，比方 Java 中的 LinkedList，但 C 语言中却没有内置本人的链表实现，所以 Redis 本人实现了一个链表构造。

实现

typedef struct list {
    listNode *head; // 表头节点
    listNode *tail; // 表尾节点
    void *(*dup)(void *ptr); // 节点值复制函数
    void (*free)(void *ptr); // 节点值开释函数
    int (*match)(void *ptr, void *key); // 节点值比照函数
    unsigned long len; // 链表蕴含的节点数量
} list;
typedef struct listNode {
    struct listNode *prev; // 前置节点
    struct listNode *next; // 后置节点
    void *value; // 节点值
} listNode;

Redis 实现的链表能够总结如下：

• 双端无环链表，以 O(1) 的工夫复杂度获取某个节点的前置节点和后置接点；表头的前置节点和表尾的后置节点为 null，对链表的拜访以 null 完结。
• 以 O(1) 的工夫复杂度获取表头节点和表尾节点。
• 以 O(1) 的工夫复杂度获取链表的长度。
• 节点应用 void* 指针保留节点值，具备多态性，能够用于保留各种不同类型的值，能够通过 list 构造的三个属性（dup、free、match）设置类型特定函数。

应用场景

Redis 中列表对象的底层实现之一就应用了链表，但在 Redis 3.2 之后，被快表取代，除了这个，像 Redis 中的公布与订阅、慢查问、监视器等性能也应用到了链表，以及 Redis 服务器自身的客户端状态信息，以及客户端的输入缓冲区，也都应用到了链表。

字典

同链表一样，C 语言没有像 Java 等高级编程语言一样内置本人的字典实现，所以 Redis 构建了本人的字典实现。Redis 的字典是一个用于保护 key 和 value 映射关系的数据结构，底层应用哈希表实现，一个哈希表里能够有多个哈希节点，每个哈希节点保留了一个键值对。

实现

// 字典构造定义
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 公有数据，保留了须要传给类型特定函数的可选参数
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引 当没有进行 rehash 是，值为 -1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
// 类型特定函数构造定义
typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*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;
// 哈希表构造定义
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;
        double d;
    } v;
    // 指向下个哈希表节点，造成链表
    struct dictEntry *next;
} dictEntry;

从下面字典的构造定义，能够看出，它相似 Java 中的 HashMap。谈到哈希，总会随同一些问题的呈现，比方，采纳的哈希算法，哈希抵触的解决，重哈希等问题，上面咱们来看下 Redis 设计的字典是如何解决这些问题的。

哈希算法

Redis 应用的哈希算法为 MurmurHash 算法；其索引值的计算，依赖于哈希值和 sizemask 属性。当给定一个 KV 值时，其索引值的计算过程如下：

• 首先依据类型特定函数中设置的哈希函数，计算出 key 的哈希值：hash = dict -> type -> hashFunction(key)
• 而后再依据哈希值和 sizemask 属性，计算出索引值：index = hash & dict -> ht[x].sizemask

哈希抵触

从哈希表节点构造定义中，能够看出，Redis 字典解决哈希抵触的办法为链地址法，因为哈希表节点中没有指向链表表尾的指针，所以采纳的是头插法，也就是后插入的节点在后面。

rehash

随着操作的一直执行，哈希表保留的键值对会逐步地增多或者缩小，这时其负载因子可能会在一个不合理的范畴内，太多就会造成哈希抵触的减少，影响查问的效率，太低就会造成空间存储效率的降落，因而当负载因子超过设定的阈值，哈希表就会进行相应的扩大或者膨胀。其中，哈希表的负载因子计算形式为：load_factor = ht[0].used / ht[0].size。

rehash 的条件

• 服务器目前没有流动着的保留 RDB、AOF 重写或者 Redis 加载的模块派生的子过程，比方执行 BGSAVE 或者 BGREWRITEAOF 等命令时，并且负载因子大于等于 1，执行扩大操作。
• 如果存在（1）中所述的过程，比方服务器正在执行 BGSAVE 或者 BGREWRITEAOF 命令，并且负载因子大于等于 5，执行扩大操作。
• 哈希表的负载因子小于 0.1 时，会执行膨胀操作。

能够看出，当 BGSAVE 或者 BGREWRITEAOF 命令执行时，负载因子的阈值会变大，这是因为这两个命令须要创立以后服务器过程的子过程，而大多数操作都采纳写时复制来优化子过程的应用效率，所以这里调整阈值下限，能够防止不必要的内存写入操作，最大限度地节约内存，这一点能够从源码中得悉。

/* This function is called once a background process of some kind terminates,
 * as we want to avoid resizing the hash tables when there is a child in order
 * to play well with copy-on-write (otherwise when a resize happens lots of
 * memory pages are copied). The goal of this function is to update the ability
 * for dict.c to resize the hash tables accordingly to the fact we have o not
 * running childs. */
void updateDictResizePolicy(void) {if (!hasActiveChildProcess())
        dictEnableResize();
    else
        dictDisableResize();}

/* Return true if there are no active children processes doing RDB saving,
 * AOF rewriting, or some side process spawned by a loaded module. */
int hasActiveChildProcess() {
    return server.rdb_child_pid != -1 ||
           server.aof_child_pid != -1 ||
           server.module_child_pid != -1;
}

那 rehash 的扩大和膨胀操作的空间是怎么来决定的呢？

• 如果执行的是扩大操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n；
• 如果执行的是膨胀操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n。

Redis 在执行 rehash 时，也是比拟特地的，它并不是一次性、集中式的实现的，而是分屡次、渐进式地实现。这样做的起因在于，如果哈希表中只有很少的键值对，那么能够霎时将 ht[0] 中的所有数据转移到 h[1] 中，但如果数据的量级达到了百万千万或者亿呢，那么一次性的转移对于 Redis 将是个劫难。这时，rehashidx 这个属性就有了用武之地，当执行 rehash 时，它会记录 rehash 的进度，每次对字典执行增加、删除、查找或者更新时，程序除了会执行指定的操作外，还会将 rehashidx 索引上的键值对从新哈希到 ht[1] 中。特地的，在执行 rehash 期间，增加操作会把新的键值对间接放到 h[1] 中。

应用场景

Redis 中的哈希对象的底层实现之一就是字典，当蕴含的键值对比拟多，或者键值对中的元素都是比拟长的字符串时，Redis 就会应用字典作为哈希对象的底层实现。还有一个重要的用处就是，咱们通过 Redis 提供的 API 操作数据时，数据寄存的数据结构也是字典。

（本文作者：李强）

本文系哈啰技术团队出品，未经许可，不得进行商业性转载或者应用。非商业目标转载或应用本文内容，敬请注明“内容转载自哈啰技术团队”。