导读
本文介绍redis应用数据结构与物理存储结构,共八种应用数据结构和
一. 内部数据结构
1. sds
sds是redis自己设计的字符串结构有以下特点:
- jemalloc内存管理
- 预分配冗余空间
- 二进制安全(c原生使用\0作为结尾标识,所以无法直接存储\0)
- 动态计数类型(根据字符串长度动态选择结构)
- 功能强大
最为重点是引入了jemalloc,十分高效且能有效在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"但红黑树的二叉树实现明显是可以更快的(红黑树从头到尾都是二分查找)因为红黑树的每一个层级(索引)分布更加均匀,而跳表得益于每个动态随机的层级分布(每个level)层级节点更少从而跳表使用更少的内存
在Redis中的跳表实现,已节点3为例: 每个节点都会存储自己在每个level的情况,同时单向链表链接向后的节点 ,有了这些信息就可以从最高的level往下找到目标;
以上介绍可以总结以下几点:
- 排序快
- 内存占用少
- 范围取值性能好
- 查询效率O(logN)
- 代码相比简单
而在redis中的跳表还使用了一个dict<值,Scroe>哈希表优化实现唯一值检查和快速过滤无效操作,因为查找某个值不是跳表的强项(相比红黑树);
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两个核心操作: 值唯一、取差集并集交集;
值唯一实现内部使用的三种数据结构(intset、listpack、hasht),intset和dict都是可以轻松实现set属性(值唯一),listpack在插入前做查询检查后再插入也可以实现set属性,但listpack的查询效率是O(n)略显差劲,好再listpack升级到dict的阈值不高;
取差集并集交集这实现基于遍历筛选,没有很复杂的点(源码: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,51210241024*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"
计算出的hash值是固定的,可以理解为每个值都只有一次拔高最大连续0的机会,从而变相的去重计数;
但有个问题如果只记录一个出现的最长的连续0那只会被一个hash值顶高,比如一开始出现一个值的hash末尾连续5个0那么就会一开始把次数拔高到64次;
所以使用hash的前14位计算槽位,14位最大表示数字16,384也就是会有16,384槽位。也就是理想状态下会记录16384组,最终统计这些槽位值会得到个更贴近的基数(使用调和平均数算法计算平均数)
图解网站: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底层是跳表,跳表对范围取值时间复杂度较低;
