↓ 跳过正文
Zenith
Zenith

Redis 底层数据结构

·1240 字·6 分钟
目录
redis - 这篇文章属于一个选集。
§ 1: 本文
§ 2: Redis 执行流程
§ 3: Redis 持久化
§ 4: Redis 场景
§ 5: Redis 缓存异常
§ 6: Redis 集群

String
#

String 是最基本的 key-value 结构，key 是唯一标识，value 是具体的值，value 其实不仅是字符串， 也可以是数字（整数或浮点数），value 最多可以容纳的数据长度是 512M。

image-20260423141300886

String 底层数据结构
#

String 类型的底层的数据结构实现主要是 int 和 SDS（简单动态字符串）。

SDS 和我们认识的 C 字符串不太一样，之所以没有使用 C 语言的字符串表示，因为 SDS 相比于 C 的原生字符串：

  • SDS 不仅可以保存文本数据，还可以保存二进制数据。因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，并且 SDS 的所有 API 都会以处理二进制的方式来处理 SDS 存放在 buf[] 数组里的数据。所以 SDS 不光能存放文本数据，而且能保存图片、音频、视频、压缩文件这样的二进制数据。
  • SDS 获取字符串长度的时间复杂度是 O(1)。因为 C 语言的字符串并不记录自身长度，所以获取长度的复杂度为 O(n)；而 SDS 结构里用 len 属性记录了字符串长度，所以复杂度为 O(1)。
  • Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出。因为 SDS 在拼接字符串之前会检查 SDS 空间是否满足要求，如果空间不够会自动扩容，所以不会导致缓冲区溢出的问题。

为何需要重新封装一个数据结构呢，而不是 C 底层的字符串表示？

C 语言的字符串有如下问题：

  • 每次计算字符串长度的复杂度为O(N)；
  • 对字符串进行追加，需要重新分配内存；
  • 非二进制安全。

在Redis内部，字符串的追加和长度计算很常见，这两个简单的操作不应该成为性能的瓶颈，于是 Redis 封装了一个叫 SDS 的字符串结构，用来解决上述问题。下面我们来看看它是怎样的结构。

首先，Redis 中 SDS 分为 sdshdr8、sdshdr16、sdshdr32、sdshdr64，它们的字段属性都是一样，区别在于应对不同大小的字符串，我们以 sdshdr8 为例：

// from Redis 7.0.8
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[];
};
  • len：当前字符串的真实长度；
  • alloc：SDS 总共分配了多少字节；
  • flags：标志位，低 3 位用来记录当前 SDS 的类型，即当前使用的是 sdshdr5、sdshdr8 还是 sdshdr16 等。高 5 位 保留未使用；
  • buf：柔性数组，用来保存实际的字符串内容或二进制数据;在结构体定义中，柔性数组本身不占用大小，即 sizeof(struct sdshdr8) 的结果是 3 字节，但在实际分配内存时，Redis 会一次性分配一块连续的内存 [头部的3字节] + [alloc指定的容量] + [1字节的'\0']。还是有末尾 \0 的，用来兼容 C 语言标准库。

String 内部编码方式
#

String看起来简单，但实际有三种编码方式，如下图所示：

image-20260423143612060
  • INT 编码：这个很好理解，就是存一个整型，可以用 long 表示的整数就以这种编码存储;
  • EMBSTR 编码：如果字符串小于等于阈值字节，使用EMBSTR编码；
  • RAW 编码：字符串大于阈值字节，则用RAW编码。

EMBSTR 和 RAW 都是由 redisObject 和 SDS 两个结构组成，它们的差异在于，EMBSTR 下 redisObject 和 SDS 是连续的内存，RAW 编码下 redisObject 和 SDS 的内存是分开的。

EMBSTR 优点是 redisObject 和 SDS 两个结构可以一次性分配空间，缺点在于如果重新分配空间，整体都需要再分配，所以 EMBSTR 设计为只读，任何写操作之后 EMBSTR 都会变成 RAW，理念是发生过修改的字符串通常会认为是易变的。

**EMBSTR内存： **

image-20260423143913816

RAW内存：

image-20260423143934433

编码格式的转换：

随着我们的操作，编码可能会转换：

INT -> RAW：当存的内容不再是整数，或者大小超过了long的时候；

EMBSTR->RAW：任何写操作之后 EMBSTR 都会变成 RAW，原因前面有解释。

整体结构如下：

image-20260423143659959

面试
#

Set一个已有的数据会发生什么？
#

回答：

对于 SET 命令，Redis 通常不会去复用旧对象的内存，而是采取“创建新对象，丢弃旧对象”的策略。具体操作：

  • 创建新对象：Redis 会根据你传入的新 value 的大小，重新评估并创建一个全新的 redisObject 和 SDS（根据大小决定是 int、embstr 还是 raw 编码）。
  • 替换字典指针：Redis 的顶层结构是一个巨大的 Hash 表（字典）。Redis 会找到这个 key 对应的哈希槽（dictEntry），将其内部指向 value 的指针，修改为指向刚刚新建的 redisObject。
  • 释放旧对象（引用计数法）：Redis 内部使用引用计数机制来管理内存。新指针指向建立后，旧的 redisObject 的引用计数会被减 1（decrRefCount 函数）。当引用计数降为 0 时，旧的 redisObject 以及它绑定的旧 SDS 会被系统的内存分配器（如 jemalloc）回收。

浮点型在String是用什么表示？
#

回答：

要将一个浮点数放入字符串对象里面，需要先将这个浮点数转换成字符串值，然后再保存转换所得的字符串值，比如浮点数3.14，对应就变成了"3.14"这个字符串。

所以浮点数在字符串对象里面是用字符串值表示的。

String可以有多大？
#

一个 Redis 字符串最大为512MB，但是可以根据 proto-max-bulk-len 参数进行调整。

Redis 字符串是怎么实现的？
#

Redis 字符串底层是 String 对象，String 对象有三种编码方式：INT 型、EMBSTR 型、RAW 型。如果是存一个整型，可以用 long 表示的整数就以 INT 编码存储；如果存字符串，当字符串长度小于等于一个阈值，使用 EMBSTR 编码；字符串大于阈值，则用 RAW 编码。

SDS相比与C原生字符串有何区别？
#

  1. SDS包含已使用容量字段，O(1)时间快速返回有字符串长度，相比之下，C原生字符串需要O(n)。
  2. 有预留空间，在扩容时如果预留空间足够，就不用再重新分配内存，节约性能，缩容时也可以将减少的空间先保留下来，后续可以再使用。
  3. 不再以‘\0’作为字符串结束判断标准，二进制安全，可以很方便地存储一些二进制数据，但还是保留了 ‘\0’，用来兼容原生 C 标准库。

Redis 的 String 有哪些应用场景？
#

  1. 缓存对象：使用 String 来缓存对象可以直接使用整个对象作为 JSON 数据，或者将 Key 进行分离，采用 MSET 进行存储。

  2. 常规计数：因为 Redis 处理命令是单线程，所以执行命令的过程是原子的。因此 String 数据类型适合计数场景，比如计算访问次数、点赞、转发、库存数量等等。

  3. 分布式锁：SET 命令有个 NX 参数可以实现「key不存在才插入」，可以用它来实现分布式锁：

    • 如果 key 不存在，则显示插入成功，可以用来表示加锁成功；
    • 如果 key 存在，则会显示插入失败，可以用来表示加锁失败。
    • 加锁只有一步，但是解锁有两步，先判断锁的 unique_value 是否为加锁客户端，是的话，才将 lock_key 键删除。【需要 Lua 脚本来保证解锁的原子性】

  4. 共享 Session 信息：分布式系统使用同一个 Redis 存储 Session 流程图：

    image-20260423154000281

List
#

List 列表是简单的字符串列表，按照插入顺序排序，可以从头部或尾部向 List 列表添加元素。

列表的最大长度为 $2^{32} - 1$，也即每个列表支持超过 40 亿个元素。

List 底层实现
#

第一阶段
#

List 对象有两种编码方式，一种 ZIPLIST，另一种是 LINKEDLIST。

当满足如下条件时，用 ZIPLIST 编码：

  • 列表对象保存的所有字符串对象长度都小于 64 字节；
  • 列表对象元素个数少于512个，注意，这是 LIST 的限制，而不是 ZIPLIST 的限制；

ZIPLIST底层用压缩列表实现，这里我们假设列表中包含"hello"、“niuniu”、 “mart"三个元素，ZIPLIST编码示意如下：

image-20260423161735255

可以看到，“hello”、“niuniu”、“mart” 都挨在一起，正如其名字一样，ZIPLIST 内存排列得很紧凑，可以有效节约内存空间。

如果不满足ZIPLIST编码的条件，则使用LINKEDLIST编码。为了便于描述，我们还是假设列表中包含"hello"、“niuniu”、“mart"三个元素，如果用LINKEDLIST编码，则是几个String对象的链接结构，结构示意图如下：

image-20260423161815059

可以看到，“hello”、“niuniu”、“mart” 这几个数据是以链表的形式连接在一起，实际上删除更为灵活，但是内存不如ZIPLIST紧凑，所以只有在列表个数或节点数据长度比较大的时候，才会使用LINKEDLIST编码，以加快处理性能，一定程度上牺牲了内存。

第二阶段
#

ZIPLIST是为了在数据较少时节约内存，LINKEDLIST是为了数据多时提高更新效率，ZIPLIST数据稍多时插入数据会导致很多内存复制。但如果节点非常多的情况，LINKEDLIST链表的节点就很多，会占用不少的内存。

第二阶段就引入了 QUICKLIST。QUICKLIST 其实就是 ZIPLIST 和 LINKEDLIST 的结合体。

LINKEDLIST原来是单个节点，只能存一个数据，现在单个节点存的是一个ZIPLIST，即多个数据。

image-20260423161922069

这种方案其实是用 ZIPLIST、LINKEDLIST 综合的结构，取代二者本身。

当数据较少的时候，QUICKLIST 的节点就只有一个，此时其实相当于就是一个 ZIPLIST；

当数据很多的时候，则同时利用了 ZIPLIST 和 LINKEDLIST 的优势。

ZIPLIST 整体架构
#

Redis代码注释中，非常清晰描述了ZIPLIST的结构：

* The general layout of the ziplist is as follows:
*
* <zlbytes> <zltail> <zllen> <entry> <entry> .. <entry> <zlend>

比如这就是有3个节点的 ziplist 结构：

image-20260423163344677
  • zlbytes：表示该 ZIPLIST 一共占了多少字节数，这个数字是包含 zlbytes 本身占据的字节的。
  • zltail：ZIPLIST 尾巴节点相对于 ZIPLIST 的开头（起始指针），偏移的字节数。通过这个字段可以快速定位到尾部节点，例如现在有一个 ZIPLIST，zl 指向它的开头，如果要获取 tail 尾巴节点，即 ZIPLIST 里的最后一个节点，可以 zl + zltail的值，这样定位到它。如果没有尾节点，就定位到 zlend
  • zllen：表示有多少个数据节点，在本例中就有3个节点。
  • entry1~entry3：表示压缩列表数据节点。
  • zlend：一个特殊的entry节点，表示ZIPLIST的结束。

ZIPLIST ENTRIES 定义

<prevlen> <encoding> <entry-data>
  • prevlen：表示上一个节点的数据长度。通过这个字段可以定位上一个节点的起始地址（或者说开头）也就是就是 p-prevlen 可以跳到前一个节点的开头位置，实现从后往前操作，所以压缩列表才可以从后往前遍历。
    • 如果前一节点的长度，也就是前一个 ENTRY 的大小，小于254字节， 那么prevlen属性需要用1字节长的空间来保存这个长度值，255是特殊字符，被 zlend 使用了
    • 如果前一节点的长度大于等于254字节，那么prevlen属性需要用5字节长的空间来保存这个长度值，注意5个字节中的第一个字节为11111110，也就是254，标志这是个5字节的prevlen信息，剩下4字节来表示大小。
  • encoding：编码类型。编码类型里还包含了一个entry的长度信息，可用于正向遍历
  • entry-data：实际的数据。

ZIPLIST更新数据

ZIPLIST提供头尾增减的能力，但是操作平均时间复杂度是O(N)，因为在头部增加一个节点会导致后面节点都往后移动，而尾部插入时间复杂度是O(1)，所以更新的平均时间复杂度，可以看作O(N)。

其中要注意的是更新操作可能带来连锁更新。注意上面所说的增加节点导致后移，不是连锁更新。连锁更新是指这个后移，发生了不止一次，而是多次。

比如增加一个头部新节点，后面依赖它的节点，需要 prevlen 字段记录它的大小，原本只用 1 字节记录，因为更新可能膨胀为 5 字节，然后这个entry的大小就也膨胀了。所以，当这个新数据插入导致的后移完成之后，还需要逐步迭代更新。这种现象就是连锁更新，时间复杂度是O(N^2)

image-20260423164249720

第三阶段
#

连锁更新原因分析

LISTPACK 是为了解决 ZIPLIST 最大的痛点——连锁更新，我们先来看，ZIPLIST 的问题本源。

我们知道，ZIPLIST 需要支持 LIST，LIST 是一种双端访问结构，所以需要能从后往前遍历，上面有讲，ZIPLIST 的数据节点的结构是这样的：

<prevlen> <encoding> <entry-data>

其中，prevlen 就表示上一个节点的数据长度，通过这个字段可以定位上一个节点的数据，可以说，连锁更新问题，就是因为 prevlen 导致的。

对症下药

我们需要一种不记录prevlen，并且还能找到上一个节点的起始位置的办法，Redis使用了很巧妙的一种方式。

我们直接看LISTPACK的节点定义：

<encoding-type><element-data><element-tot-len>
  • encoding-type：编码类型；
  • element-data：数据内容；
  • element-tot-len：存储整个节点除它自身之外的长度。

找到上一个节点的秘密就藏在 element-tot-len：

element-tot-len 所占用的每个字节的第一个 bit 用于标识是否结束。0是结束，1是继续，剩下7个bit来存储数据大小。当我们需要找到当前元素的上一个元素时，我们可以从后向前依次查找每个字节，找到上一个Entry的 element-tot-len 字段的结束标识，就可以算出上一个节点的首位置了。

如果上个节点的element-tot-len为 00000001 10000100，每个字节第一个bit标志是否结束，所以这里的element-tot-len一共就两个字节，大小为0000001 0000100，即132字节。

面试
#

ZIPLIST有什么优点
#

回答：

相比于LINKEDLIST链表式设计，压缩列表的内存都是紧凑排列在一起的，这就带来了几个优点，1.节约内存，2.方便一次性分配，3.遍历时局部性更强

ZIPLIST是怎么压缩数据的？
#

回答：

压缩列表是一块连续的内存空间，元素之间是紧挨着存储的，一个压缩列表中可以包含多个节点（entry），是在连续的内存空间上实现的双端链表，

ZIPLIST下List可以从后往前遍历吗？
#

回答：

ZIPLIST 每个节点中都保存了上一个节点的长度，所以可以用当前节点地址减去上一个节点长度来找到上个节点起始位置，进而实现从后往前的遍历。

ZIPLIST下List如何从前往后遍历吗？
#

回答：

其中 prevlen 是找上一个节点的起始位置，entry-data 是实际的内容，显然，答案就在 encoding 里，encoding 里无论是 String 还是 Int 都是可以知道长度信息的。

在ZIPLIST数据结构下，查询节点个数的时间复杂度是多少？
#

回答：

由于ZIPLIST的header中定义了记录节点数量的字段zllen，所以通常是可以在O(1)时间复杂度直接返回，为什么说通常呢？是因为zllen是2个字节的，当zllen大于65535时，zllen就存不下了，所以真实的节点数量需要遍历来得到。

连锁更新是什么问题？
#

回答：

ZIPLIST每个节点会有个字段记录上一个节点的长度，如果上个节点小于254字节，这个记录字段则是1字节，否则是5。由于更新某个节点，会导致长度变化，如果从小于254变得大于等于254了，则会影响下个节点的长度，依次递推，就像多米诺骨牌一样，这种情况就是连锁更新。

如何解决连锁更新问题？
#

回答：

核心思路就是不去记录上一个节点的长度，而是记录自身长度，使用 LISTPACK 的第三部分 element-tot-len(backlen) 来做特殊化处理(记录 encoding 和 data 的长度)，以便遍历到前一个节点。

Set
#

Redis 的 Set 是一个不重复、无序的字符串集合，这里额外说明一下，如果是 INTSET 编码的时候其实是有序的，不过一般不应该依赖这个，整体还是看成无序来用比较好。

Set 编码方式
#

Redis 出于性能和内存的综合考虑，也支持两种编码方式，如果集合元素都是整数，且元素数量不超过512个，就可以用 INTSET 编码，结构如下图，可以看到INTSET排列比较紧凑，内存占用少，但是查询时需要二分查找。

typedef struct intset {
    uint32_t encoding;  //编码格式
    uint32_t length;    //元素数量
    int8_t contents[];  //保存元素的数组
} intset;
image-20260423170750985

如果不满足 INTSET 的条件，就需要用 HASHTABLE，HASHTABLE 结构如下图，可以看到HASHTABLE查询一个元素的性能很高，能O(1)时间就能找到一个元素是否存在。

image-20260423170830124

INTSET 对应少量整数集合下节约内存，HASHTABLE 适用于需要快速定位某个元素的场景。

面试
#

Set是有序的吗？
#

回答：

Set 的底层实现是整数集合或字典，前者是有序的，后者是无序的。整体来看，建议不依赖 SET 的顺序。

Set编码方式是什么？
#

回答：

Set使用整数集合和字典作为底层编码，当元素都是整数同时元素个数不超过512个，会使用整数集合编码，否则使用字典编码。

Set为什么要用两种编码方式?
#

回答：

Set的底层编码是整数集合和字典，当元素数量小并且全部是整数的时候，会使用整数集合编码，更加的节约内存。元素数量变大会使用字典编码，查找元素的速度会更快。

Hash
#

Redis Hash是一个field、value都为 string 的hash表，存储在 Redis 的内存中。

Redis中每个hash可以存储$2^{32}-1$键值对（40多亿）。

Hash 底层编码
#

Hash底层有两种编码结构，一个是压缩列表，一个是 HASHTABLE。同时满足以下两个条件，用压缩列表：

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

  2. Hash对象元素个数少于512个。

两个条件任何一条不满足，编码结构就用HASHTABLE。

ZIPLIST 之前有讲解过，其实就是在数据量较小时将数据紧凑排列，对应到 Hash，就是将 filed-value当作 entry 放入ZIPLIST，结构如下：

image-20260423171626655

HASHTABLE 在之前无序集合 Set 中也有应用，和 Set 的区别在于，在 Set 中 value 始终为 NULL，但是在 Hash 中，是有对应的值的。

image-20260423171652121

HASHTABLE
#

hash 是 Redis 中的一种数据类型，而 hashtable(哈希表) 是类型的具体底层实现

HASHTABLE 结构
#

Redis 中 HASHTABLE 的结构如下：

// from Redis 5.0.5
/* This is our hash table structure.  */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
image-20260423171931878

最外层是一个封装的 dictht 结构，其中字段含义如下：

  • table：指向实际hash存储。存储可以看做一个数组，所以是 *table 的表示，在C语言中 *table 可以表示一个数组。
  • size：哈希表大小。实际就是dictEntry有多少元素空间。
  • sizemask: 哈希表大小的掩码表示，总是等于 size-1。这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面，规则 Index=hash&sizemask。
  • used：表示已有节点数量。通过这个字段可以很方便地查询到目前 HASHTABLE 元素总量。

dictEntry 结构如下：

typedef struct dictEntry {
    /* void * 类型的 key，可以指向任意类型的键 */
    void *key;
    /* 联合体 v 中包含了指向实际值的指针 *val、无符号的 64 位整数、有符号的 64 位整数，以及 double 双精度浮点数。
     * 这是一种节省内存的方式，因为当值为整数或者双精度浮点数时，由于它们本身就是 64 位的，void *val 指针也是占用 64 位（64 操作系统下），
     * 所以它们可以直接存在键值对的结构体中，避免再使用一个指针，从而节省内存开销（8 个字节）
     * 当然也可以是 void *，存储任何类型的数据，最早 redis1.0 版本就只是 void* */​
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
                                /* 同一个 hash 桶中的下一个条目.
                                 * 通过形成一个链表解决桶内的哈希冲突. */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
                                /* 一块任意长度的数据 (按 void* 的大小对齐),
                                 * 具体长度由 'dictType' 中的
                                 * dictEntryMetadataBytes() 返回. */
} dictEntry;

Hash 表渐进式扩容实现
#

其实为了实现渐进式扩容，Redis 中没有直接把 dictht 暴露给上层，而是再封装了一层：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

可以看到dict结构里面，包含了2个dictht结构，也就是2个HASHTABLE结构。dictEntry是链表结构，也就是用拉链法解决Hash冲突，用的是头插法

image-20260423174234006

实际上平常使用的就是一个HASHTABLE，在触发扩容之后，就会两个HASHTABLE同时使用，详细过程是这样的：

当向字典添加元素时，发现需要扩容就会进行Rehash。Rehash的流程如下：

第一步：准备阶段（分配空间与状态切换）

  • 为字典的新 Hash 表 ht[1] 分配空间。
  • 扩容大小规则：新表大小为第一个大于等于原表 ht[0].used * 2 的 $2^n$（2 的 n 次方幂）。
    • 举例：原表如果 used=500，2 倍就是 1000，那第一个大于 1000 的 2 次方幂则为 1024。ht[1] 的容量就是 1024。
  • 状态变更：此时字典同时持有 ht[0] 和 ht[1] 两个哈希表。字典的偏移索引 rehashidx 从静默状态 -1 设置为 0，标志着 Rehash 工作正式开始。
  • image-20260423172348264

第二步：渐进迁移阶段（分摊工作量）

  • 事件驱动迁移：在 Rehash 进行期间，每次对字典执行增、删、改、查操作时，程序除了执行指定的操作外，还会顺带将 ht[0] 在 rehashidx 索引上的所有键值对迁移到 ht[1] 上。迁移完成后，rehashidx 的值加 1。
  • 定时任务兜底：除了请求驱动，Redis 的定时周期函数（serverCron）也会在后台利用空闲时间进行部分迁移，防止冷数据（迟迟没有被访问的键）一直滞留在原表中。
  • 当你对字典执行增删改查时，触发了单步迁移（n=1）：
    • 如果遇到空桶，它会往下找。
    • 但最多只允许连续找 10 次空桶。
    • 如果连找 10 个全是空的，它会直接放弃本次任务并返回，把剩下的活儿留给下一次字典操作，或者交给后台的 serverCron 定时任务去大批量扫尾。

第三步：Rehash 期间的读写规则（🌟 重点）

因为此时字典同时存在两个 Hash 表，所以数据的操作需要兼顾两边：

  • 查 (Find) / 删 (Delete) / 改 (Update)：程序会先在 ht[0] 中查找目标，如果没找到，会继续去 ht[1] 中查找，找到后再执行相应操作。
  • 增 (Add)：所有的插入操作一律直接写入 ht[1]。这保证了 ht[0] 里的键值对数量只会“只减不增”，最终一定会变成空表，不会出现永远迁移不完的情况。

第四步：完成阶段（指针更替与收尾）

  • 随着字典操作的不断执行，最终在某个时间点，ht[0] 的所有键值对都会被全部迁移至 ht[1]。
  • 每次迁移完一个 bucket 的元素，底层的 Rehash 函数都会检查是否完成了整个迁移。
  • 一旦确认完成：释放 ht[0]，将 ht[1] 的指针赋值给 ht[0]（新表上位），并在 ht[1] 新创建一个空白哈希表，为下一次 Rehash 做准备。
  • 最后，将 rehashidx 重新置为 -1，表示本次 Rehash 圆满结束。

扩容时机
#

Redis提出了一个负载因子的概念，负载因子表示目前 Redis HASHTABLE的负载情况，是游刃有余，还是不堪重负了。我们设负载因子为 k，那么 k=ht[0].used/ht[0].size，也就是使用空间和总空间大小的比例。

Redis会根据负载因子的情况来扩容：

  • 没有执行 BGSAVE 或 BGREWRITEAOF（后台持久化）时，负载因子 $\ge 1$ 触发扩容。
  • 正在执行 BGSAVE 或 BGREWRITEAOF 时，为了避免写时复制 (COW) 造成过多内存消耗，触发阈值会提高，负载因子 $\ge 5$ 时才触发扩容。

缩容时机
#

当负载因子小于0.1，即负载率小于10%，此时进行缩容，新表大小为第一个大于等于原表used的2次方幂。当然，如果有BGSAVE或BGREWRITEAOF这两个复制命令，缩容也会受影响，不会进行。

面试
#

HASHTABLE查找元素总数的平均时间复杂度是多少?
#

dictht 的结构如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemark;
    // 键值对数量
    unsigned long used;
} dictht;

回答：

HASHTABLE 查找元素总数的平均时间复杂度是O(1)，因为HASHTABLE的表头结构中有储存键值对数量的字段used。

HASHTABLE怎么扩容?
#

回答：

首先程序会为HASHTABLE的1号表分配空间，空间大小是第一个大于等于used 两倍的最近二次幂。在rehash进行期间，标记位rehashidx从0开始，每次对字典的键值对执行增删改查操作后，都会将rehashidx位置的数据迁移到1号表，然后将rehashidx加1，随着字典操作的不断执行，最终0号表的所有键值对都会被rehash到1号表上。之后，1号表会被设置成0号表，接着在1号表的位置创建一个新的空白表。

什么时候扩容，什么时候缩容
#

回答：

扩容：

当以下两个条件中的任意一个被满足时，哈希表会自动开始扩容：【k=ht[0].used/ht[0].size】

  • 服务器目前没有在执行BGSAVE或者BGREWRITEAOF，并且负载因子 >= 1
  • 服务器目前正在执行BGSAVE或者BGREWRITEAOF，并且负载因子 >= 5

缩容：

当哈希表的负载因子小于0.1时，程序会自动开始对哈希表进行收缩操作。

跳表
#

为了提升查找的性能，Redis 就引入了跳表，跳表在链表的基础上，给链表增加了多级的索引，通过索引可以一次实现多个节点的跳跃，提高性能。

跳表的结构
#

下面我们来看看跳表他具体的结构是怎样的，我们先看这个示意图：

image-20260423181022774

可以看到，这个图某些节点不光只有一层，如果只用普通链表，只能一步一步往后走，如果用这种有高层的节点，那是不是可以一次多走几步，理论上，层次越高平均步长越大，但并不完全像示意图一样是绝对均衡的，节点的层高其实是概率随机的，

标准的跳表（Redis不是用的标准的跳表，下面会讲）有如下限制：

  1. score 值不能重复；

  2. 只有向前指针，没有回退指针。

在 Redis 中，跳表是用来支持有序集合的，所以 Redis 对跳表做了一些优化，就包括 score 可以重复、增加回退指针，下面我们来看看 Redis 的跳表。

Redis 跳表
#

我们直接看这个示意图，score可以重复并且我们的每个节点多了一下回退指针。

image-20260423181316801

下面我们结合源码，来和示意图对照学习，以加深理解，这是Redis 跳表单个节点的定义：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

我们来看看字段的含义：

  • ele：很熟悉的SDS结构，用来存储数据。
  • score：节点的分数，浮点型数据
  • backward：指向上一个节点的回退指针，支持从表尾向表头遍历，也就是ZREVRANGE这个命令
    • level：是个 zskiplistLevel 结构体数组，zskiplistLevel 这个结构体包含了两个字段，一个是forward，指向该层下个能跳到的节点，span记录了距离下个节点的步数，数组结构就表示每个节点都可能是个多层结构。

面试
#

Redis跳表单个节点有几层？
#

回答：

层次的决定，需要比较随机，才能在各个场景表现出较为平均的性能，这里Redis使用概率均衡的思路来确定新插入节点的层数：

Redis 跳表决定每一个节点，是否能增加一层的概率为25%，而最大层数限制在Redis 5.0是64层，在Redis 7.0是32层。

Redis跳表的性能优化了多少
#

回答：

这个其实可以很容易想到，跳表的查找过程，其实是走高层，行得通跳过去，行不通走相对下层，很像二叉树的另一种表现形式，实际上他们性能也是差不多的，平均时间复杂度都是O(logn)，区别是二叉树最坏情况下也是O(logn)比较稳定，而跳表的最坏时间复杂度是O(N)。当然，实际的生产过程中，体现出来的基本都是跳表的平均时间复杂度。

跳表是什么，和普通的链表有什么区别？
#

回答：

跳表也算链表，不过相对普通链表，增加了多级索引，通过索引可以实现O(logN)的元素查找效率。

聊聊跳表的查找过程
#

回答：

从高级索引往后查找，如果下个节点的数值比目标节点小，则继续找，否则不跳过去，而是用下级索引往下找。

跳表中一个节点的层高是怎么决定的？
#

Redis 采用的是一种基于幂次定律（Power Law）的随机算法。具体流程如下：

  1. 初始层高：每个新插入的节点，默认至少有 1 层。
  2. 随机晋升：程序会生成一个随机数。如果这个随机数满足特定的晋升概率 $p$（Redis 中这个常量是 0.25），那么该节点的层高就增加 1 层。
  3. 循环判断：只要随机数持续满足概率 $p$，层高就会继续不断 +1，直到随机数不再满足条件，或者达到了 Redis 设定的最大层数限制（Redis 5.0 之后最大层数是 64，早期版本是 32）。

ZSet
#

ZSet 底层编码有两种，一种是 ZIPLIST，一种是 SKIPLIST+HASHTABLE。

ZIPLIST我们可以说很熟悉了，之前List、Hash中都有打过交道，同样在，在ZSet中ZIPLIST也是用于数据量比较小时候的内存节省，结构如下：

image-20260423223937737

如果满足如下规则，ZSet就用ZIPLIST编码：

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

两个条件任何一条不满足，编码机构就用 SKIPLIST + HASHTABLE，其中 SKIPLIST 也是底层数据结构。

SKIPLIST是一种可以快速查找的多级链表结构，通过SKIPLIST可以快速定位到数据所在。它的排名操作、范围查询性能都很高。

image-20260423224042915

除了SKIPLIST，Redis还使用了HASHTABLE来配合查询，这样可以在O(1)时间复杂度查到成员的分数值。

image-20260423224100695

注意，同时维护 SkipList 和 HashTable 不会造成两倍内存浪费，Redis 在底层 C 语言源码的实现中，精妙地共享了数据。HashTable 和 SkipList 的节点中，关于 Member（字符串对象）和 Score（双精度浮点数）的值，都是通过指针指向同一块内存地址的。

typedef struct zset {
    dict *dict;      // HashTable，用于 O(1) 查找 member 对应的 score
    zskiplist *zsl;  // SkipList，用于 O(log N) 的范围查找和排序
} zset;

面试
#

ZSet 插入一条数据的时间复杂度？
#

回答：

跳跃表是一种支持多级索引的结构，查询效率可以媲美二分查找，它插入一条数据也是需要先查找，找到之后会进行索引的重建，整体平均时间复杂度是O(logN)。

ZSet 为何使用跳表，相比于其他平衡树有何优点？
#

回答：

相比于 B+ 树：

  • B+树的数据都存在叶子节点中，而且它是多叉树，相同数据量下多叉树的层高比二叉树低，这两个特点使得它适合磁盘存储。而 Redis 是一个内存数据库，B+树层高低的优势荡然无存，所以选择了实现更加简单的跳表。
  • 跳表的插入性能更高，虽然两者的插入平均时间复杂度相当，但是跳表插入数据后只需要修改前进和后退指针即可，而B+树还需要维护树的平衡，细节上有额外开销。

相比于红黑树：

  • ZSet 最常用的操作之一就是提取某个范围的元素，红黑树要先进行范围查询，找到起点后，需要进行中序遍历。在树形结构中进行跨节点的中序遍历，逻辑相对复杂，且由于内存地址不连续，对 CPU 缓存（Cache Line）不够友好。
  • Redis 的底层把跳表的最底层节点通过双向链表连接了起来。找到范围查询的起点后，只需要顺着最底层的链表向后（或向前）遍历即可，就像遍历数组一样简单高效。
  • 足够简单，这是最核心的。
凉柠
作者
凉柠
专注于 Kubernetes、分布式系统与 AI Agent 架构探索。
redis - 这篇文章属于一个选集。
§ 1: 本文
§ 2: Redis 执行流程
§ 3: Redis 持久化
§ 4: Redis 场景
§ 5: Redis 缓存异常
§ 6: Redis 集群