Redis7.0八种数据结构底层原理

导读

本文介绍redis应用数据结构与物理存储结构,共八种应用数据结构和

一. 内部数据结构

1. SDS

SDS（Simple Dynamic String，简单动态字符串）是 Redis 自主设计的字符串结构，具备以下显著特点：

• 采用 jemalloc 内存管理机制：借助 jemalloc 这一高效的内存分配器，能够在 Redis 的应用场景中显著减少内存碎片，极大地提升内存使用效率。
• 预分配冗余空间：SDS 会预先分配一定的冗余空间，避免在字符串频繁增长时反复进行内存分配操作，从而提高性能。
• 二进制安全：与 C 语言原生字符串不同，C 语言使用 \0 作为字符串的结尾标识，因此无法直接存储包含 \0 的数据。而 SDS 实现了二进制安全，能够存储任意二进制数据。
• 动态计数类型：SDS 会根据字符串的实际长度动态选择合适的数据结构，在不同场景下合理利用内存资源。
• 功能强大：SDS 除了基本的字符串存储功能外，还提供了丰富的操作接口，满足 Redis 在处理字符串时的多样化需求。

其中，最为关键的是 SDS 引入了 jemalloc 内存管理机制。该机制不仅高效，而且在 Redis 的特定场景中，能够有效减少内存碎片，对提升 Redis 的整体性能起到了至关重要的作用。

不同的字符串长度使用的结构不同最高可以节省18字节;

2. dict

redis的hash表实现

核心结构由两个类型为dictEntry的数组组成，使用开链法的数据结构；

采用 渐进式扩容数组，但数组需要扩容或缩容时开辟数组2,使用数组2存储新数组，在后续操作命中数组1的bucket时，只复制命中的bucket数据到数组2;

同时主线程在每次循环任务时会分配1毫秒协助尚未复制的;

完成所有数组1复制到数组2后，使用2替代1，并空出2为下一次扩容准备

总结点

• 扩容阈值更低，链条均长不过4
• 渐进式rehash，响应时间更加平滑

3. listpack(紧凑集合，双向链表)

紧凑类型集合，在申请的一块连续的内存(byte[])中存储一个集合数据结构， 使用少量的内存但支持所需的集合操作

实现原理

主数据结构上分两快:

• 头 记录数据使用总长度，因为连续的内存快可能有一部分还未使用
• Body 存储实际数据

Body内存储多个条目(实际数据)，每个条目头尾都会记录条目长度，从而实现快速的头尾遍历。此外条目头部会分配一个字节记录条目的类型，这个类型可以减少记录长度的使用内存(小数据量的条目可能8位的int就够记录了，而长的可能需要32位int才够记录)。

核心操作时间复杂度:

操作	时间复杂度	对应指令
头插	O(1)	LPUSH
尾插	O(1)	RPUSH
头取	O(1)	LPOP
尾取	O(1)	RPOP

缺点

因为每个条目的头尾都记录了长度，所以从头和尾顺序操作很快，但涉及集合中间数据数据时间复杂度就会增加:

操作	时间复杂度	对应指令
范围取	O(n)	LRANGE
指定取	O(n)	LINDEX

同时因为基于连续内存快(byte[]数组)，涉及到LINSERT(指定下标插入)就需要重新对内存块的数据做移动操作;

4. quicklist

listpack明显的一个问题是数据量大了对于O(n)时间复杂度指令性能变差，这对于单线程处理指令模型很容易成为性能短板，quicklist为解决这点而设计。

通过 拆分多个小块的listpack(从而可以快速定位范围)，quicklist使用双向链表管理这些小块的listpack，同时quicklist会 根据阈值对listpack进行lzf算法压缩，进一步 缩减内存占用 与 提升效率。

缺点

额外的管理结构内存quicklist(40 byte)、quicklistNode(32 byte)，但在效率的提升面前不值一提

5. intset

这是一个只存储int类型(最大支持64位int)的唯一值集合， 头部存储值的编码类型与长度， 其他位置都存储实际数据，因为数组内的数据大小都严格是头部设置的编码类型所以 没有分隔符，同时从小到大存储，所以可以用二分快速查找值。

从新增值的角度切入有一下核心点:

• 每新增一个值都要开辟新内存
• 如果当前编码类型不够存储新值,那将需要重新对所有数据变更数据结构(INT16->INT32)
• 修改头部数据:当前数据长度

从这点可以发现一些问题,每次 添加值都需要扩容内存,为了保持步长一样所有数据都要 保持一样的编码类型导致浪费内存;

优点也明显, 内存占用少、查询效率O(log n)

核心操作时间复杂度:

操作	时间复杂度	对应指令
查询值	O(log n)	SISMEMBER
添加值	O(n)	SADD

6. skiplist

跳表是zset的核心数据结构， 有序且读写操作效率保持O(logN),从贴出来的代码能出来它不是一个存储在连续内存快的实现(对比listpack和intset）；

/* ZSET使用特殊版本的跳表 */
typedef struct zskiplistNode {
    sds ele;//实际值
    double score;//分数
    struct zskiplistNode *backward;//最上层的前一位(例如node3的最上层前一位是node1)
    struct zskiplistLevel {
        struct zskiplistNode *forward;//向后的node(例如层级1的node3:向后是node4->node5->node6)
        unsigned long span;
    } level[];//存储这个node所在的所有层级(例如节点3那么这个level将只有两个槽位,别存储level1和level2)
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;//头与尾（最大或最小值）
    unsigned long length;  //存储的数据量
    int level;//跳表深度(也就是索引层数量)
} zskiplist;

typedef struct zset {
    dict *dict;	//<值:Score>(为了快速检查是否唯一)
    zskiplist *zsl;//跳表
} zset;

zset是有序&唯一的数据结构,这两特性决定了 需要频繁排序和确认唯一,对于保持有序重点对比的是红黑树(也是java中TreeMap的内部实现方法):

操作	跳表 (QPS)	红黑树 (QPS)	优势
插入 10w 元素	125,000	98,000	+27.5%
范围查询 1000 元素	45,000	32,000	+40.6%
查询 1 元素	110,000	125,000	-13%
内存占用 (10w 元素)	45MB	52MB	-13.5%
代码实现量	200行	500+行	150%

红黑树的树深与跳表的层级（level）都可看作一种组合式索引。在定位元素，比如查找数值“4”时，红黑树凭借其二叉树的实现方式，能够更为迅速地完成定位。这是因为红黑树在查找过程中自始至终都采用二分查找策略，且每一层级（索引）的分布更为均匀。

而跳表则依靠每个层级动态随机的分布特性，使得每个层级的节点数量相对较少。这种结构特点让跳表在存储数据时能够使用更少的内存。

在Redis中的跳表实现,已节点3为例: 每个节点都会存储自己在每个level的情况,同时单向链表链接向后的节点 ,有了这些信息就可以从最高的level往下找到目标;

综合以上介绍，可总结出以下要点：

• 排序高效：能够快速完成数据的排序操作。
• 内存占用低：在存储数据时，所需的内存资源较少。
• 范围取值性能佳：在进行范围取值操作时，具有良好的性能表现。
• 查询效率为 O(logN)：查询操作的时间复杂度为 O(logN)，能在较短时间内完成查询任务。
• 代码相对简洁：实现逻辑相对简单，代码编写和维护的难度较低。

在 Redis 中使用的跳表，为进一步优化性能，还引入了一个 dict<值, Score> 哈希表。借助该哈希表，能够高效地实现唯一值检查，并快速过滤无效操作。这是因为单纯查找某个特定值并非跳表的优势所在（相较于红黑树而言）。

7. HyperLogLog(Dense稠密存储&SPARSE稀疏)

理解数据结构前需要先理解HyperLogLog算法原理(请先看下方的[应用数据结构->HyperLogLog])

struct hllhdr {
	char magic[4]; /* 魔法值由于识别结构体"HYLL" */
	uint8_t encoding; /* 编码:HLL_DENSE(稠密) or HLL_SPARSE(稀疏). */
	uint8_t notused[3]; /* 预留字段,暂无使用 */
	uint8_t card[8]; /* 缓存统计结果 */
	uint8_t registers[]; /* 实际存储 */
}

registers[]存储的就是桶数据,以稠密存储为例,会一口气申请12KB,6位为一个桶一共16,384个桶:

12KB=12,288B=98,304bit
98,304÷6=16,384个桶

桶中记录最长的末尾连续0次数,6bit最高能记录64次,算法只使用hash的末50位所以6bit足够记录最大连续50位0( 节省内存);

SPARSE 稀疏存储

借助稀疏存储结构（Sparse Encoding），在数据量较小时能够显著降低内存占用。其核心原理在于，对连续的零值桶进行压缩表示，同时采用动态编码策略，在内存使用和性能表现之间实现平衡。

稀疏存储在 uint8_t registers[] 中的存储方式与稠密存储存在明显差异，它更为节省内存。在稠密存储方式下，可能需要一次性申请 12KB 的内存空间；而采用稀疏存储时，仅需 2B 即可。

初始化结果实例

稀疏存储的编码结构

Redis 的 HLL 稀疏存储使用 三元组（Triplet） 表示连续的桶状态，通过操作码（Opcode）标识块类型：

操作码	二进制格式	占用字节	描述
XZERO	01xxxxxx xxxxxxxx	2B	表示连续 16384 个桶的值为 0（最大覆盖范围，仅用于初始化）
ZERO	00xxxxxx	1B	表示连续 1~64 个桶的值为 0，长度由低 6 位（xxxxxx）表示
VAL	1vvvvvv1	1B	表示 1 个桶的非零值，值由高 5 位（vvvvv）存储，低 1 位（l）固定为 1

只有槽位1001是3示例:

示例中使用XZERO表示0-1000的桶都是0,使用VAL表示第1001个桶是3,最后又使用XZERO表示剩余的15382个桶都是0;

不再一次性开辟所有桶的内存,一但超过阈值再转换为密集存储,从而在空间与时间上有较好的平衡:

性能与内存对比

指标	稀疏编码（小基数）	密集编码
内存占用	300B ~ 3KB	固定 12KB
PFADD 延迟	较高（需遍历块）	极低（直接位操作）
适用场景	基数 < 10000	基数 ≥ 10000 或高并发

二. 应用数据结构

0. 存储框架

Redis是个KV数据库,它的最外层是16,384个solt(也就是一致性hash的槽位),每个槽位中是实际存储dictkey:应用数据结构的数据(hash表);

当执行以下指令后:

LSET key1 index value
SET key2 value
HSET key10 field value

实际在redis中的存储结构会是:

16384个solt组成一致性hash环,每个sold都是一个db,db内部是Hash表,也就是RedisKV数据库的核心结构;

1. String

基于sds,没啥好说的

2. Hash

使用dict不难理解,本身Hash类型就是一个哈希表;

在小数据量使用listpack是为在空间与时间上做平衡,listpack使用两个entry为一组分别存储kv:

特性	listpack	dict（哈希表）
内存占用	低（连续存储，无指针开销）	高（指针、元数据、哈希表桶开销）
100个值内存占用	2.2KB）	12KB
查询效率	O(n)（需遍历）	O(1)（哈希直接定位）
插入/删除效率	中等（需内存重排）	高（直接操作节点，但扩容有抖动）
适用场景	小数据（字段数少，值长度短）	大数据（字段多，查询频繁）
自动转换阈值	hash-max-listpack-entries（默认512）hash-max-listpack-value（默认64字节）	超出阈值时自动转为 dict
内存碎片	少（连续内存块）	多（动态扩容、指针分散）

3. List

基于上文对 listpack 的介绍，它是一个 紧凑(节省内存)、 小数据量 性能有保障(大数据量性能不好)的数据结构，为了应对大数据量使用 quicklist分段listpack进行管理，但只有到达阈值才会从单个listpack升级到quicklist(也就是一开始List里面只有一个listpack)，同时达到阈值也会降级为一个listpack。

4. Set

SET 的两个核心操作：值唯一与集合运算（取差集、并集、交集）

值唯一的实现

SET 操作要求集合中的值必须唯一，Redis 内部通过三种数据结构来实现这一特性，分别是整数集合（intset）、列表包（listpack）和哈希表（hasht）。整数集合和哈希表都能够轻松满足 SET 的值唯一属性。对于列表包而言，虽然它本身并不直接具备值唯一的特性，但可以在插入元素之前先进行查询检查，确认元素不存在后再执行插入操作，以此实现值唯一的效果。不过，列表包的查询效率为 O(n)，相对较低。好在列表包升级为哈希表的阈值并不高，当元素数量或元素大小达到一定条件时，就会自动升级为哈希表，从而提高查询效率。

取差集、并集、交集的实现

SET 的差集、并集和交集运算主要基于遍历和筛选操作，实现逻辑并不复杂。具体的实现代码可以参考源码文件 t_set.c 中的 sinterGenericCommand 函数，该函数处理了集合间的交集运算，差集和并集的实现逻辑与之类似，都是通过对集合元素进行遍历和比较，筛选出符合条件的元素来完成相应的集合运算。

5. ZSET

zset是一个有序值唯一的集合,内部使用了listpack和skiplist;

以下文指令切入

127.0.0.1:6379> ZADD zsetKey 1 "apple" 2 "banana" 3 "orange"
(integer) 3

根据score(1、2、3)作为排序的优先级,也就是要存储值和对应的score;

其中listpack与上文介绍的数据存储上有些不同:

两个条目一组 分别存储实际值与score,同时listpack也支持查询步长+1的跨越条目查询

同时listpack本身是无序的,但默认最多只会存储64条所以每次获取时才扫描顺序;

而超过64条后会转换为skiplist(跳表);

6. Bitmap

布隆过滤器,内部存储结构是基于sds申请的一大块内存char[],根据客户端给的槽位(bit)并标记1

Bitmap限制最大sds为512M,512 1024 1024* 8 = 4,294,967,296位（即 42.9 亿个bit）;

  SETBIT key 7 1 #第八位设置为1

以上指令在第8bit设置为1,Bitmap申请内存并非一口气申请最大512M,而且根据当前要设置的最大逐步申请新的sds;

bitmap实现并不复杂:

指令	时间复杂度	补充
SETBIT	O(1)
GETBIT	O(1)
BITCOUNT	O(N)	遍历
BITPOS	O(N)	扫描
BITFIELD	O(N)	扫描

7. HyperLogLog

HyperLogLog使用快速、高效的、统计近似 基数,我们直接介绍核心原理:

以上是三组抛筛子游戏,规则是越晚抛出正面的人获胜,换个方向理解就是: 连续抛出最多反的人获胜;在大量的实验后第N次抛出正的概率会根据N的增加概率越小,而根据概率我们可以计算出大概需要多少组才能得到第N次才是正:

第N次才是正	概率	平均抛出次数
第二次	25%	4
第四次	6.25%	16
第六次	1.56%	64

带入HyperLogLog,使用 MurmurHash64A 计算出”user1”的64位hash值,使用后50位模拟抛硬币游戏,即末尾连续的0代表反面,从而得到所需次数( 比如末尾出现了5个0那我们定义为在此之前已经抛了64次,从而得到一个基数),而我们 只需要记录最大的才是正的次数就可推测出本次游戏大概进行了多少组;

PFADD "key" "user1"

计算得出的哈希值是固定不变的，这意味着每个值仅有一次机会使最大连续 0 的数量达到峰值，进而通过这种方式变相地实现去重计数。

然而，这里存在一个问题。若仅记录出现的最长连续 0 的情况，那么计数结果很容易被某一个哈希值拉高。例如，若一开始出现一个值，其哈希值末尾有连续 5 个 0，那么计数次数就会直接被拔高到 64 次。

为解决这一问题，我们 采用哈希值的前 14 位来计算槽位。由于 14 位二进制数所能表示的最大数字为 16,384，这意味着总共会有 16,384 个槽位。在理想情况下，每个槽位都能记录一组数据，这样就能得到 16,384 组记录。最终，通过对这些槽位的值进行统计，并 运用调和平均数算法 来计算平均值，我们便能得到一个更接近真实情况的基数估计值。

图解网站:http://content.research.neustar.biz/blog/hll.html

以上算法基于<伯努利试验>

而存储结构采用了两种:

8. Geospatial

Geospatial可以快速获取给定经纬度附近的对象, 通过对经纬度进行Geohash编码将二维数据转为一维数据:

参考文档:https://cloud.tencent.com/developer/article/1949540

Geohash计算出的hash可以排序,也就是相邻的两个经纬度转换出的hash在数值上也相邻,这个hash可以作为ZSET数据格式的Scroe,ZSET底层是跳表,跳表对范围取值时间复杂度较低;

原文阅读