Redis数据结构

对象

Redis并没有直接使用我们之前提到的数据结构实现键值对数据库 ，而实基于这些数据结构构建一个对象，分为字符串对象，列表对象，哈希对象，集合对象，有序集合对象。

Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被释放；另外，Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一对象来节约内存。

对象的类型和编码

redis数据库中的每个键值对的键和值都是一个对象

Redis中的每个对象都由一个redisObject结构表示，该结构中保存数据有关的三个属性分别是type属性，encoding属性，ptr属性：

/*
 * Redis 对象
 */
typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码方式
    unsigned encoding:4;

    // LRU - 24位, 记录最末一次访问时间（相对于lru_clock）; 或者 LFU（最少使用的数据：8位频率，16位访问时间）
    unsigned lru:LRU_BITS; // LRU_BITS: 24

    // 引用计数
    int refcount;

	//指向底层实现数据结构的指针
    void *ptr;

} robj;

每个对象都有相应的类型，这些类型决定了你能对他们操作的指令，比如string类型的对象只能用set命令设置。

每种类型的对象又有两种以上的编码，不同编码可以在不同场景上优化使用效率

这里的每个字段都很重要，比如类型和编码，有一个基于6.0的关系图

比如我们执行一个命令 hset user age 25
在字典上的数据结构大概是这样,为了方便，string类型的对象就简画成了stringobject。

核心就是搞明白，无论是key还是value，都是一个redisObject即可。

Redis垃圾回收

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

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

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

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

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

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

数据类型

ziplist

• ziplist是一种连续，无序的数据结构。

• 压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。

• ziplist可以用于存储字符串或者整数，其中整数是按照二进制表示进行编码的，而不是编码成字符串序列。

• Redis中的hash，List，Zset这几种类型的数据在某些情况下会使用ziplist来存储。

ziplist实现

ziplist不是普通的双向链表， 普通的双向链表每一项都占用独立的一块内存，各项之间用地址指针连接起来，这会造成大量的内存碎片，而且地址指针也占用额外的内存。 ziplist是将表中每一项放在前后连续的地址空间中，一个ziplist整体占用一大块内存，它是一个表（list）， 但其实不是一个链表

另外，ziplist为了在细节上节省内存，对于值的存储采用了变长的编码方式，即对于大的整数，就多用一些字节来存储，对于小的整数就少用一些字节存

下图是一个ziplist编码的实例：

下图是一个双端链表编码的实例：

ziplist 数据节点entry

压缩列表并没有存储指针，那么压缩列表各个节点之间是如何做到两端都能访问的呢？

这就是每个列表节点entry的结构厉害之处，每个entry保存了三个属性，分别是：

<prevlen> <encoding> <entry-data>

• previous_entry_length（前一个节点的长度）
  • 如果前一个节点长度小于254 (<254)，则用1个字节保存这个长度
  • 如果前一个节点长度大于等于254 (>=254)，则采用5个字节长度保存，其中第一个字节为0xfe，后面四个节点才是真实的数据长度；
• encoding（编码）
  • 记录content内容的 数据类型 以及 长度，占1、2或5个字节长度
  • 以’00’, ‘01’, ‘10’ 开头，那么content保存的是字符串
  • 以 ‘11’ 开头则保存的是整数
• contents（保存的内容）
  保存数据的地方，可以是字符串或者整数。

特点

• 缺点：每次插入或删除一个元素时，都需要进行频繁的进行内存的扩展或减小，然后进行数据”搬移”，甚至可能引发连锁更新，造成严重效率的损失。

内存紧凑​​

• 由表头、若干个entry节点和压缩列表尾部标识符zlend组成，通过一系列编码规则，提高内存的利用率，使用于存储整数和短字符串。

• 没有指针开销（相比LinkedList每个节点节省16字节）
  

• 数据连续存储，减少内存碎片，可以极大的提升cpu的缓存命中率

​​操作特性​​：

• 头尾操作O(1)复杂度
• 中间操作O(N)复杂度
• 支持双向遍历（通过prevlen实现）

​​连锁更新问题​​：

每次插入或删除一个元素时，都需要进行频繁的进行内存的扩展或减小，然后进行数据”搬移”，甚至可能引发连锁更新，造成严重效率的损失。

quicklist实现原理

Redis对外暴露的List数据类型，底层实现用的就是quicklist

quicklist的实现是一个双向链表，链表的每一个节点都是一个ziplist， 为什么quicklist要这样设计呢？ 其实也是一个空间和时间的折中

.双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。 首先它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片

ziplist由于是一整块连续内存，所以存储效率很高，但是它不利于修改操作，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能

这样设计的问题， 到底一个quicklist节点包含多长的ziplist合适？这是一个找平衡的问题：

.每个quicklist节点上的ziplist越短，则内存碎片越多，极端情况是一个ziplist只包含一个数据项，这就退化成了普通的双向链表

.每个quicklist节点上的ziplist越长，则为一个ziplist分配大块连续内存的难度就越大，有可能出现内存里有很多小块的内存空间，但却找不到一块足够大的空闲空间分给ziplist。极端情况是整个quicklist只有一个节点，这就退化成了一个ziplist了

skiplist 跳跃列表

跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集（见右边的示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。

skiplist 跳表

跳跃表是Redis特有的数据结构，就是在链表的基础上，增加多级索引提升查找效率。

跳跃表支持平均 O（logN）,最坏 O（N）复杂度的节点查找，还可以通过顺序性操作批量处理节点。

如 ZSet 结构同时包含一个字典和一个跳跃表：

• 跳跃表按score从小到大保存所有集合元素。
• 字典保存着从member到score的映射。这两种结构通过指针共享相同元素的member和score，不会浪费额外内存。
• 层数：包含n个元素的跳跃表，搜索时间复杂度为O(log n)

底层结构

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

skiplist插入

skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。

跳跃列表缺点

跳表的效率比链表高，但是跳表需要额外存储多级索引，所以需要的更多的内存空间。

Redis基本类型底层实现

比如我们执行一个命令 hset user age 25
在字典上的数据结构大概是这样,为了方便，string类型的对象就简画成了stringobject。

1. string: SDS简单动态字符串

SDS简单动态字符串介绍

https://www.51cto.com/article/700992.html

Redis 的SDS字符串是动态字符串，用于存储二进制数据的一种结构, 具有动态扩容的特点，内部结构实现上类似于 Java 的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。例如 key、string 类型的值、sorted set 的 member、hash 的 field 等。

Redis为什么不直接使用C字符串，而要自定义简单动态字符串？

C字符串与Redis的SDS比起来有以下不足：

• 获取字符串长度的时间复杂度为 n
• API是不安全的可能造成缓冲区溢出
• 只能保存文本数据

对的，Redis 3.x 的 SDS 是有 size_t 的，但是具体要分情况：

---

SDS v1-v3

1. SDS v1（很早期）

struct sdshdr1 {
    char len;      // 8-bit 长度
    char buf[];
};

• len 和 free 都是 char，最大只能表示 255 字节。
• 适用于非常短的字符串，几乎不用了。

2. SDS v2

struct sdshdr2 {
    unsigned short len;   // 16-bit
    unsigned short free;  // 16-bit
    char buf[];
};

• 支持最大 64 KB 字符串。

3. SDS v3

struct sdshdr3 {
    size_t len;  // 当前长度
    size_t free; // 剩余空间
    char buf[];
};

• 这里的 size_t 就是标准 C 类型：

  • 32 位系统 → 4 字节
  • 64 位系统 → 8 字节

系统架构	size_t 大小	说明
32 位系统	4 字节 (32 bit)	最大可表示 2³²-1 (~4GB)
64 位系统	8 字节 (64 bit)	最大可表示 2⁶⁴-1 (~16EB)

---

1️⃣ Redis 3.x（SDS v2/v3）——经典 SDS

底层结构：

// sds.h

struct sdshdr {
    int len;       // 当前字符串长度
    int free;      // buf中未使用的字节数
    char buf[];    // 实际存储的字符串数据
};

特点：

• len 与 free 分开存储，访问字符串长度 O(1)，无需 strlen 遍历。
• buf 紧跟 header 存储。
• 支持二进制安全和动态扩容。
• 对小字符串来说，header 占用内存相对大（2 × size_t，一般 8 或 16 字节）。

内存布局示意：

+---------+---------+------------------+
|  len    |  free   |   buf[ ]         |
+---------+---------+------------------+

扩容：len + free 不够时，申请新的空间（通常是原来大小的 2 倍）。

如下图所示为字符串"Aobing"在Redis中的存储形式：

• len 为6，表示这个 SDS 保存了一个长度为6的字符串;
• free 为0，表示这个 SDS 没有剩余空间;
• buf 是个char类型的数组，注意末尾保存了一个空字符’\0’。

buf 尾部自动追加一个’\0’字符并不会计算在 SDS 的len中，这是为了遵循 C 字符串以空字符串结尾的惯例，使得 SDS 可以直接使用一部分string.h库中的函数，如strlen

#include <stdio.h>
#include <string.h>

int main()
{
    char buf[] = {'A','o','b','i','n','g','\0'};
    printf("%s\n",buf);             // Aobing
    printf("%lu\n",strlen(buf));    // 6
    return 0;
}

2️⃣ Redis 4.x — 小对象优化

Redis 4.x 对 SDS 做了微优化，针对 小字符串使用更紧凑的 header。

底层变化：

• 引入短字符串优化（small string optimization）。

• 对短字符串：

  • 使用 1 个 uint8_t 或 2 个字节存长度。

• 长字符串仍用 size_t。

内存布局示意：

短字符串：
+------+--------+
| len  | buf[ ] |
+------+--------+

长字符串：
+---------+---------+--------+
|  len    |  free   | buf[ ] |
+---------+---------+--------+

特点：

• 小对象内存占用减少，缓存命中率提升。
• 扩容策略略微优化，更适合频繁操作小字符串的场景。

---

3️⃣ Redis 6.x — SDS v7（重大变化）

在 Redis 6.x 之前，小字符串（比如 key “id”, “ok” 等）会使用完整的 SDS header（比如 3、5、9 字节 header）。
这些小字符串的数据本身可能只有 2~3 字节，但 header 就占了几倍空间，浪费严重。

Redis 6.x 引入 SDS v7，header 类型可变，内存布局紧凑，支持超大字符串。

• 短字符串(长度小于32)，len和free的长度用1字节即可;
• 长字符串，用2字节或者4字节;
• 超长字符串，用8字节。

共有五种类型的SDS(长度小于1字节、1字节、2字节、4字节、8字节)

底层结构：

• 根据字符串长度自动选择 header 类型：

  • SDS_TYPE_5 → 5 bit 存长度（仅短字符串）
  • SDS_TYPE_8/16/32/64 → 对应 uint8_t/16/32/64 保存 len/free

• buf 紧跟 header。

特点：

• 小字符串头部非常小，节省内存。
• 支持超大字符串，len/free 使用 64 位。
• 二进制安全和动态扩容仍保留。
• 扩容策略保持指数增长，但更智能地根据 header 类型选择。

在 SDS 中新增一个 flags 字段来标识类型，但是没必要使用一个 4 字节的int类型去做!可以使用 1 字节的char类型，通过位运算(3位即可标识2^3种类型)来获取类型。**

// 注意：sdshdr5从未被使用，Redis中只是访问flags。
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 低3位存储类型, 高5位存储长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 1字节 已使用 */
    uint8_t alloc; /* 1字节 总长度，用1字节存储 */
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /*  2 字节 已使用 */
    uint16_t alloc; /* 2 字节 总长度，用2字节存储 */
    unsigned char flags; /* 1字节 低3位存储类型, 高5位预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* 已使用 */
    uint32_t alloc; /* 总长度，用4字节存储 */
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 已使用 */
    uint64_t alloc; /* 总长度，用8字节存储 */
    unsigned char flags; /* 低3位存储类型, 高5位预留 */
    char buf[];
};

SDS 类型	Header 总字节数	len 类型	free 类型	可存最大长度（约）	典型用途
SDS_TYPE_5	1 字节	5 bit（在 type 中）	无	31 字节	极短字符串（节省内存）
SDS_TYPE_8	3 字节（flags1字节）	uint8_t	uint8_t	8 bit = 2⁸ = 256 → 最大 255字节	短字符串
SDS_TYPE_16	5 字节	uint16_t	uint16_t	65,535 (64KB)	中等长度字符串
SDS_TYPE_32	9 字节	uint32_t	uint32_t	4,294,967,295 (≈4GB)	大字符串
SDS_TYPE_64	17 字节	uint64_t	uint64_t	2⁶⁴-1 (≈16 EB)	超大字符串（理论上极限）

示意内存布局：

小字符串 (SDS_TYPE_5):
+--------+--------+
| len(5) | buf[ ] |
+--------+--------+

中字符串 (SDS_TYPE_16/32):
+--------+--------+--------+
| len    | free   | buf[ ] |
+--------+--------+--------+

超大字符串 (SDS_TYPE_64):
+----------+----------+--------+
| len(64)  | free(64) | buf[ ] |
+----------+----------+--------+

如下所示为短字符串(长度小于32)的优化形式：

低三位存储类型，高5位存储长度，最多能标识的长度为32，所以短字符串的长度必定小于32。

无需free字段了，32-len即为free

总结对比（底层数据结构角度）

版本	header 类型	内存布局特点	优化目标
Redis 3.x	固定 len/free	header 占用 2×size_t，buf 紧跟	经典 SDS，访问 O(1)
Redis 4.x	小对象优化	短字符串 header 更小，长字符串保持	节省小字符串内存，提高缓存效率
Redis 6.x	SDS v7，可变 header	header 类型可变（5~64 bit），buf 紧跟	小字符串占用极小，支持超大字符串

---

目前我们似乎得到了一个结构不错的 SDS ，但是我们能否继续进行优化呢?

在 Redis3.x 版本中不同长度的字符串占用的头部是相同的，如果某一字符串很短但是头部却占用了更多的空间，这未免太浪费了。所以我们将 SDS 分为三种级别的字符串：

Redis SDS内存不对齐

在 Redis6.x 的源码中 SDS 的结构体为struct __attribute__ ((__packed__)) 与struct有较大的差别，这其实和我们熟知的对齐填充有关。

在 C 语言中，结构体成员的排列和对齐方式依赖于编译器和平台，目的是为了提高访问内存的效率。 __attribute__ ((__packed__)) 是 GCC 的一个扩展，它告诉编译器不要对结构体进行任何填充，这样所有的成员将紧凑排列。

typedef struct{
     char  c1;
     short s; 
     char  c2; 
     int   i;
} s;

若此结构体中的成员都是紧凑排列的，假设c1的起始地址为0，则s的地址为1，c2的地址为3，i的地址为4。下面用代码论证一下我们的假设。

#include <stdio.h>

typedef struct
{
    char c1;
    short s;
    char c2;
    int i;
} s;

int main()
{
    s a;
    printf("c1 -> %d, s -> %d, c2 -> %d, i -> %d\n",
           (unsigned int)(void *)&a.c1 - (unsigned int)(void *)&a,
           (unsigned int)(void *)&a.s - (unsigned int)(void *)&a,
           (unsigned int)(void *)&a.c2 - (unsigned int)(void *)&a,
           (unsigned int)(void *)&a.i - (unsigned int)(void *)&a);
    return 0;
}
// 结果为：c1 -> 0, s -> 2, c2 -> 4, i -> 8


char c1 占用 1 个字节。
short s 通常占用 2 个字节，但为了对齐，它可能会被放置在 2 字节边界上。
char c2 占用 1 个字节，但为了对齐 int i，它可能会被放置在 4 字节边界上。
int i 通常占用 4 个字节，并且通常会被放置在 4 字节边界上。
编译器对齐的方式是为了确保每个成员都按照其类型的对齐要求放置，这样访问内存更高效。假设 c1 的起始地址为 0，那么成员的内存布局可能如下：

c1 的地址为 0
s 的地址为 2（而不是 1，因为 short 通常要求 2 字节对齐）
c2 的地址为 4（而不是 3，因为 int 通常要求 4 字节对齐）
i 的地址为 8（因为 int 通常要求 4 字节对齐）
这意味着编译器会在 c1 和 s 之间插入一个填充字节，以及在 s 和 c2 之间插入两个填充字节。

(4) sds 更改对齐方式

注意：我们写程序的时候，不需要考虑对齐问题。编译器会替我们选择适合目标平台的对齐策略。

如果我们一定要手动更改对齐方式，一般可以通过下面的方法来改变缺省的对界条件：

• 使用伪指令#pragma pack(n)：C编译器将按照n个字节对齐;
• 使用伪指令#pragma pack()：取消自定义字节对齐方式。
• 另外，还有如下的一种方式(GCC特有语法)：
• __attribute((aligned (n)))：让所作用的结构成员对齐在n字节自然边界上。如果结构体中有成员的长度大于n，则按照最大成员的长度来对齐。
• __attribute__ ((packed))：取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐。

将上述示例代码的结构体更改如下(取消对齐)，再次执行，可以发现取消对齐后和我们的假设就一致了。

(5) Redis为什么不对齐呢?

综上所述我们知道了对齐填充可以提高 CPU 的数据读取效率，作为 IO 频繁的 Redis 为什么选择不对齐呢?

我们再次回顾 Redis6.x 中的 SDS 结构：

有个细节各位需要知道，即 SDS 的指针并不是指向 SDS 的起始位置(len位置)，而是直接指向buf[]，使得 SDS 可以直接使用 C 语言string.h库中的某些函数，做到了兼容，十分nice~。

如果不进行对齐填充，那么在获取当前 SDS 的类型时则只需要后退一步即可flagsPointer = ((unsigned char*)s)-1;相反，若进行对齐填充，由于 Padding 的存在，我们在不同的系统中不知道退多少才能获得flags，并且我们也不能将 sds 的指针指向flags，这样就无法兼容 C 语言的函数了，也不知道前进多少才能得到 buf[]。

SDS相对C字符串的好处

使用它主要有以下好处：

• 读取字符串长度快：获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1) (C语言传统字符串获取长度的时间复杂度为 n)
• 杜绝缓冲区溢出：SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求
• 二进制安全：SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以空字符串来判断是否结束
• 减少内存重新分配次数：对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略

这些好处也就解释了为什么Redis要使用SDS来实现字符串了。

C语言传统字符串获取长度的时间复杂度为 n

C语言传统字符串
C语言传统字符串是以空字符结尾的字符数组。例如：

char str[] = "hello\0";
strlen(str);

实际上这种做法，在很多地方都很常见，例如C++中的标准容器，如vector获取其大小，string获取其长度。

redis中的简单动态字符串定义如下：

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; //记录buf数组中已使用的字节数量
    uint64_t alloc; //分配的buf数组长度，不包括头和空字符结尾
    unsigned char flags; //标志位,标记当前字节数组是 sdshdr8/16/32/64 中的哪一种，占 1 个字节。
    char buf[];//真正存储字符串的地方
};

定义的这些字段有以下一些好处：

• 用单独的变量 len 和 free，可以方便地获取字符串长度和剩余空间；
• 内容存储在动态数组 buf 中，SDS 对上层暴露的指针指向 buf，而不是指向结构体 SDS。因此，上层可以像读取 C 字符串一样读取 SDS 的内容，兼容 C 语言处理字符串的各种函数，-
• 同时也能通过 buf 地址的偏移，方便地获取其他变量；
• 读写字符串不依赖于 \0，保证二进制安全。

比如我们设置的key=“xiaoxu”、value=“code”，存储情况如下图所示：

二进制安全性

‍♂️ 什么是二进制安全性？

二进制安全是指一种数据处理或传输的方式，其中对待数据的处理不会受到数据中包含的二进制数据的影响。在计算机科学和编程中，这个术语通常与字符串的处理有关。

C语言字符串和Redis SDS的二进制安全性问题对比

• C 语言中字符串是以遇到的第一个空字符 \0 来识别是否到末尾，因此其只能保存文本数据，不能保存图片，音频，视频和压缩文件等二进制数据，否则可能出现字符串不完整的问题，所以其是二进制不安全。

• Redis SDS（简单动态字符串）。而SDS使用len属性的值判断字符串是否结束，所以不会受’\0’的影响,保证了二进制安全。

预分配空间减少内存分配次数

实际上，在创建新的sds的时候，它并不仅仅申请要使用的内存，而是额外申请了一些空间，以避免下次修改的时候又需要重新申请内存，减少性能损耗。

比如说，你有一个字符数组：

char str[] = "hello";

现在你想存储helloworld，怎么办？原先的空间已经确定了，没有办法存储这么多字符串，你只能重新申请空间，然后还要把原先的hello拷贝到新申请的空间中去。如果有频繁地修改字符串，就会导致系统中频繁的内存申请，释放，拷贝，这样还能有高效的redis吗？

因此在redis中，如果有这样的情况，分配新的空间的时候，会预分配一些空间，以备下次使用。

3.惰性释放空间
而正因如此，出现字符串缩短的时候，也没有必要直接释放内存，只需要更新字符串，记录当前使用的长度即可，你说，下次字符串又增长的时候，不就又用上了吗？减少分配。

杜绝缓冲区溢出

字符串的拼接操作是使用十分频繁的，在C语言开发中使用char *strcat(char *dest,const char *src)方法将src字符串中的内容拼接到dest字符串的末尾。由于C字符串不记录自身的长度，所有strcat方法已经认为用户在执行此函数时已经为dest分配了足够多的内存，足以容纳src字符串中的所有内容，而一旦这个条件不成立就会产生缓冲区溢出，会把其他数据覆盖掉，Dangerous~。

RedisObject

我们首先来了解一下 Redis 对象头结构体，所有的 Redis 对象都有这样一个 RedisObject 对象头需要占据 16 字节( 4bit + 4bit + 24bit + 4bytes + 8bytes )的存储空间。

/* redisObject — Redis 对象系统的核心结构体
 * 每个键值对的值（value）都被封装成一个 redisObject。
 * 
 * 在 64 位系统上总大小为 16 字节，对齐结构如下：
 * 
 * ┌──────────────────────────────┐
 * │ type(4b) | encoding(4b) | LRU(24b) │ -> 共 4 字节
 * │ refcount (int)                 │ -> 4 字节
 * │ ptr (void*)                    │ -> 8 字节
 * └──────────────────────────────┘
 *              Total: 16 Bytes
 */
typedef struct redisObject {
    unsigned type:4;       /* [4 bits] 对象类型：
                              0=string, 1=list, 2=set, 3=zset, 4=hash 等 */

    unsigned encoding:4;   /* [4 bits] 编码方式：
                              raw, embstr, int, ziplist, quicklist 等 */

    unsigned lru:24;       /* [24 bits = 3 bytes]
                              LRU 时间戳（或 LFU 访问频率计数）
                              用于内存回收策略。*/

    int refcount;          /* [4 bytes]
                              引用计数：用于对象共享与释放。*/

    void *ptr;             /* [8 bytes on 64-bit systems]
                              指向底层实际数据结构，如：
                              - SDS（字符串）
                              - dict（哈希）
                              - quicklist（列表）等 */
} robj;  // sizeof(robj) = 16 bytes (on 64-bit)

字段	大小	对齐后偏移	说明
type + encoding + lru	4 字节	0x00	位域字段合并在一起
refcount	4 字节	0x04	整型引用计数
ptr	8 字节	0x08	指针（8字节）
总计	16 字节		内存对齐后总大小

string的三个编码：embstr、raw 、int

关于string的三个编码的区别

编码方式	存储类型	特点
int	整数（long long）	值可直接放在 robj.ptr 里，不用 SDS，最大数字为2^63-1
raw	SDS 分配在堆上	长字符串（> 44 字节），可修改
embstr	robj + SDS 连续分配	短字符串（≤ 44 字节），一次分配，节省内存碎片

bao test:0>set test111 1
OK
bao test:0>object encoding test111
int

• 如图所示，embstr 存储形式是这样一种存储形式，它将 RedisObject 对象头和 SDS 对象连续存在一起，使用 malloc 方法一次分配。这样可以提升性能、减少碎片。

• 而 raw 存储形式不一样，它需要两次malloc，两个对象头在内存地址上一般是不连续的。（第一次为redisObject，第二次为SDS），相对地，释放内存的次数也由一次变为两次。

而内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。

如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。

当内存分配器分配了 64 空间时，那这个字符串的长度最大可以是多少呢？这个长度就是 44。那为什么是 44 呢？

SDS 结构体中的 content 中的字符串是以字节\0 结尾的字符串，之所以多出这样一个字节，是为了便于直接使用 glibc 的字符串处理函数，以及为了便于字符串的调试打印输出。

看上面这张图可以算出，留给 content 的长度最多只有 45(64-19) 字节了。字符串又是以\0 结尾，所以 embstr 最大能容纳的字符串长度就是 44。

redisObject我们可以看下源码，在server.h中有对于redisObject的定义，关于encoding，string类型有三个编码格式分别为int，embstr，raw这个区别在本文的最后做解释，因为需要有SDS的铺垫才可以。

hash 字典 (ziplist+hash)

https://redisbook.readthedocs.io/en/latest/internal-datastruct/dict.html

字典实现

/*
 * 字典
 *
 * 每个字典使用两个哈希表，用于实现渐进式 rehash
 */
typedef struct dict {

    // 特定于类型的处理函数
    dictType *type;

    // 类型处理函数的私有数据
    void *privdata;

    // 哈希表（2 个）
    dictht ht[2];

    // 记录 rehash 进度的标志，值为 -1 表示 rehash 未进行
    int rehashidx;

    // 当前正在运作的安全迭代器数量
    int iterators;

} dict;

/*
 * 哈希表
 */
typedef struct dictht {

    // 哈希表节点指针数组（俗称桶，bucket）
    dictEntry **table;

    // 指针数组的大小
    unsigned long size;

    // 指针数组的长度掩码，用于计算索引值
    unsigned long sizemask;

    // 哈希表现有的节点数量
    unsigned long used;

} dictht;

table 属性是个数组， 数组的每个元素都是个指向 dictEntry 结构的指针。

每个 dictEntry 都保存着一个键值对， 以及一个指向另一个 dictEntry 结构的指针：

/*
 * 哈希表节点
 */
typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 链往后继节点
    struct dictEntry *next;

} dictEntry;

如果再加上之前列出的 dict 类型，那么整个字典结构可以表示如下：

在上图的字典示例中， 字典虽然创建了两个哈希表， 但正在使用的只有 0 号哈希表， 这说明字典未进行 rehash 状态。

当Hash的数据项较少时,Hash底层才会用压缩列表zipList进行存储数据, 数据增加,底层的zipList会转成dict,

ziplist

上图中可以看到，当数据量比较小的时候，我们会将所有的key及value都当成一个元素，顺序的存入到ziplist中，构成有序。

哈希算法

Redis 目前使用两种不同的哈希算法：

• MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好， 具体信息请参考 MurmurHash 的主页：http://code.google.com/p/smhasher/ 。
• 基于 djb 算法实现的一个大小写无关散列算法：具体信息请参考 http://www.cse.yorku.ca/~oz/hash.html 。

使用哪种算法取决于具体应用所处理的数据：

• 命令表以及 Lua 脚本缓存都用到了算法 2 。
• 算法 1 的应用则更加广泛：数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。

rehash

哈希冲突

哈希表中桶的数量是有限的，当Key的数量较大时自然避免不了哈希冲突(多个Key落在了同一个哈希桶中)。当哈希桶中存在哈希冲突时那么多个Entry就形成了链表，每个链表中有一个Next指针指向了下一个元素。当哈希桶中的链表过长时，那么查询性能会显著降低(链表的查找时间复杂度为O(N))，Redis为了避免类似的问题从而会进行Rehash操作

为了能够减少哈希冲突，其实最直接的做法是增加哈希桶数量从而让元素能够更加均匀的分布在哈希表中。而Redis中的Rehash操作的原理其实也是如此，只不过他的设计更加巧妙。
Redis中其实有两个「全局哈希表」，一开始时默认使用的Hash Table1来存储数据，而Hash Table2并没有分配内存空间。随着Hash Table1中的元素越来越多时，Redis会进行Rehash操作。

首先会给Hash Table2分配一定的内存空间(肯定比哈希表一大)，然后将Hash Table1中的元素重新映射至Hash Table2中，最后会释放Hash Table1。这样来看的话，Redis的Rehash操作的确能减少哈希冲突，但是你有没有想过如果Hash Table1中的元素特别多时，如果这么粗暴的将数据往Hash Table2中搬，那势必会阻塞Redis的主线程进而影响Redis的性能。其实Redis也考虑到了这个问题，那么接下来我们看看Redis是如何解决这种问题的

rehash的步骤

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

因为在进行渐进式 rehash 的过程中， 字典会同时使用 ht[0] 和 ht[1] 两个哈希表， 所以在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。

另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作： 这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表

Redis 渐进式哈希（Progressive Hashing）机制

为什么需要渐进式哈希？​​

• ​​避免阻塞​​：传统 rehash 会一次性迁移所有键值对，导致单次操作耗时剧增（如百万级键值对可能阻塞数秒）。
• 平滑过渡​​：渐进式 rehash 将迁移分摊到多次操作中，保证 Redis 的高响应速度。

渐进式哈希 触发条件

当哈希表（dict结构）满足以下条件时触发：

• 扩容条件
  • 负载因子（used / size）≥ 1
  • 且未执行 BGSAVE/BGREWRITEAOF（此时扩容因子为 5）
• 缩容条件
  • 负载因子 < 0.1（即元素数量远小于哈希表大小）

⚠️ 关键参数

• 默认扩容因子：1（受 hash-max-ziplist-entries 等配置影响）
• BGSAVE 期间扩容因子提高到 5

2. 实现流程

typedef struct dict {
    dictht ht[2];      // 双哈希表
    int rehashidx;      // rehash进度标记（-1表示未进行）
} dict;

Redis 通过 ​​两个哈希表（ht[0] 和 ht[1]）​​ 实现渐进式 rehash：

1. ​​准备阶段​​：

• 分配 ht[1]，大小为第一个 ≥ ht[0].used × 2 的 2^n 值（扩容）或缩容后的合理大小。
• 设置 rehash 标记 rehashidx = 0（表示 rehash 开始）。

2. 渐进迁移阶段​​：

• 每次增删改查操作​​：触发迁移 ht[0] 中 rehashidx 位置的桶（bucket）到 ht[1]，并递增 rehashidx（按桶（bucket）的索引顺序逐步+1​​）。
• ​​定时任务​​：在 Redis 的事件循环中，主动迁移少量桶（避免阻塞主线程）。
• 此期间的新数据直接写入 ht[1]，查询需同时检查 ht[0] 和 ht[1]。​​

3. 完成阶段​​：

• 当 ht[0] 所有元素迁移完毕，释放 ht[0]，将 ht[1] 设为 ht[0]，并重置 rehashidx = -1。

List (3.2前ziplist+linked_list 3.2后quicklist)

3.2 版本前采用ziplist和linkedlist结构
List 是一个有序（按加入的时序排序）的数据结构，一般有序我们会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存。

3.2版本之前采用两种数据结构作为底层实现：

• 压缩列表ziplist
• 双向链表linkedlist

压缩列表相对于双向链表更节省内存，所以再创建列表时，会先考虑压缩列表，并在一定条件下才转化为双向链表。

1. Redis 3.2 之前：双向链表 + 压缩列表

• LinkedList：标准双向链表
• ZipList：连续内存块组成的紧凑结构

特点

• 动态切换条件：
  • 使用ZipList：元素数量 <512 且 每个元素大小 <64字节
  • 否则使用LinkedList

优缺点

类型	优点	缺点
ZipList	内存紧凑，首尾操作O(1)	中间查询O(N)，可能连锁更新
LinkedList	头尾操作O(1)，灵活	指针开销大(16B/节点)，内存碎片

2. Redis 3.2 之后：快速链表(QuickList)

根据上文谈到，ziplist会引入频繁的内存申请和释放，而linkedlist由于指针也会造成内存的浪费，而且每个节点是单独存在的，会造成很多内存碎片，所以结合两个结构的特点，设计了quickList。

数据结构

• QuickList：双向链表 + ZipList分片
  • 每个链表节点是一个ZipList
  • 默认单个ZipList大小限制为8KB

核心优化

• 内存效率：减少指针开销
• 性能平衡：限制ZipList大小降低连锁更新影响

配置参数

• list-max-ziplist-size -2 # 8KB
• list-compress-depth 1 # 首尾各1个节点不压缩

Set（intset、hash）

其底层主要有整数数组（INTSET）和哈希表两种实现方式。当我们创建set的时候如果遇上成员是整形字符串时，会直接使用intset编码存储。intset的数据结构：

• encoding表示编码格式：表示intset中每个元素采用以下哪种方式存储，有三种类型INT16（2字节），INT32（4个字节），INT64（8个字节）
• length：元素个数，表示intset保存在contents中的元素个数
• contents：实际存储的数据

其中：inset为可以理解为整数数组的一个有序集合，其内部是采用二分查找来定位元素位置。实际查询复杂度也就在log(n)

使用inset数据结构需要满足下述两个条件：

• 元素个数少于默认值512 ： set-max-inset-entries 512
• 元素可以用整型表示

zset（ziplist+skiplist）

在redis中是通过两种底层数据结构实现的。

ziplist压缩列表 或者 skipList跳跃表与字典hash_table实现

• ziplist：和 hashtable 和 list 一样，可以配置长度小于一定阈值时，降级成 ziplist 压缩列表实现，ziplist 实现是用一块连续的内存空间，节省了链表实现的前后节点，并且能够顺序查找。
  数量小的时候使用 ziplist 实现，是因为小的连续空间容易申请。

zipList：

满足以下两个条件：

• [score,value]键值对数量少于128个；
• 每个元素的长度小于64字节；

zset 长度越来越大的时候难以申请一块足够大的连续空间，所以转而使用了skiplist 跳跃表实现

skipList:
不满足以上两个条件时使用跳表（组合了hash和skipList）

• hash用来存储value到score的映射，这样就可以在O(1)时间内找到value对应的分数；
• skipList按照从小到大的顺序存储分数；
• skipList每个元素的值都是[score,value]对

虽然同时使用两种结构，但它们会通过指针来共享相同元素的 member 和 score，因此不会浪费额外的内存。

ziplist、skipList 为什么需要转换？

1.zset 的数据结构，为什么数量小的时候使用 ziplist

当刚开始选择了ziplist，会在下面两种情况下转为skipList。

ziplist所保存的元素超过服务器属性server.zset_max_ziplist_entries 的值（默认值为 128）
新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值（默认值为 64）

那我们是否思考一下为什么需要转换呢？

ziplist 是一个紧挨着的存储空间，并且是没有预留空间的，随意对于ziplist优势在于节省空间，是因为小的连续空间容易申请，但是在容量大到一定成度扩容就是影响他的性能的主要原因之一。

基本数据结构 底层实现 总结

大多数情况下，Redis使用简单字符串SDS作为字符串的表示，相对于C语言字符串，SDS具有常数复杂度获取字符串长度，杜绝了缓存区的溢出，减少了修改字符串长度时所需的内存重分配次数，以及二进制安全能存储各种类型的文件，并且还兼容部分C函数。

通过为链表设置不同类型的特定函数，Redis链表可以保存各种不同类型的值，除了用作列表键，还在发布与订阅、慢查询、监视器等方面发挥作用（后面会介绍）。

• string: int、embstr、raw

• hash: Redis的字典底层使用哈希表实现，每个字典通常有两个哈希表，一个平时使用，另一个用于rehash时使用，使用链地址法解决哈希冲突。

• set: 整数集合是集合键的底层实现之一，底层由数组构成，升级特性能尽可能的节省内存。

• zset:跳跃表通常是有序集合的底层实现之一，表中的节点按照分值大小进行排序。

• zset:压缩列表是Redis为节省内存而开发的顺序型数据结构，通常作为列表键和哈希键的底层实现之一。

布隆过滤器

位图bitmap

HyperLogLog

以下是针对不同 Redis 概率型数据结构在大 Key 风险、解决方案灵活性和内存效率方面的对比，特别加入哈希冲突影响的详细分析：

---

概率型数据结构对比表（含哈希冲突分析）

数据结构	大Key风险	解决方案灵活性	内存效率	哈希冲突影响
字符串位图	高	低	高	无冲突，但精度固定，仅适合精确二进制状态存储
标准布隆过滤器	中	中	中	多哈希函数降低冲突概率，但误判率随元素增加而上升
可扩展布隆过滤器	低	高	中	动态分片减少单一大Key，但跨分片查询可能轻微增加冲突概率
HyperLogLog	低	低	极高	依赖哈希近似基数统计，冲突概率较高但误差可控（标准误差0.81%）
Count-Min Sketch	中	中	中	哈希冲突会导致频率统计偏大，需通过增加宽度/深度权衡精度

---

哈希冲突对各结构的具体影响

1. 布隆过滤器

   • 冲突表现：误判（假阳性）
   • 缓解方式：
     • 增加位数组大小（m）和哈希函数数量（k）
     • 公式：p ≈ (1 - e^(-kn/m))^k
     • 代价：内存占用上升，计算开销增加

2. HyperLogLog

   • 冲突表现：基数统计误差
   • 特性：
     • 使用64位哈希函数，冲突概率极低
     • 误差固定为约0.81%（分桶算法补偿冲突影响）
   • 不可消除：误差是设计妥协，但内存效率无可替代（1.5KB可统计±2^64元素）

3. Count-Min Sketch

   • 冲突表现：频率统计值偏大
   • 优化手段：
     • 增加矩阵宽度（减少冲突）和深度（多哈希函数取最小）
     • 公式：误差 ≤ N * e^(-w)（N为总元素数，w为宽度）

4. 字符串位图

   • 无冲突：严格一对一映射，但功能局限（仅布尔状态）

---

选择建议

1. 优先内存效率 → HyperLogLog

   • 适合：UV统计等允许误差的场景
   • 避免：需要精确判断存在性的场景

2. 平衡精度与内存 → 可扩展布隆过滤器

   • 适合：动态增长的数据集（如用户标签）
   • 优势：自动分片避免大Key，误判率可控

3. 精确频率统计 → Count-Min Sketch + 布隆过滤器组合

   • 示例：

     # 先用布隆过滤判断存在性
     BF.EXISTS user_actions 123  
     # 再用CMS统计频率
     CMS.INCRBY action_count 123 1
     

4. 极致节省内存 → 压缩位图（RLE/Roaring Bitmap）

   • 适合：稀疏布尔状态（如用户在线记录）
   • 工具：通过Redis模块或客户端库实现