IT评测·应用市场-qidao123.com技术社区

标题: Redis7.0八种数据结构底层原理 [打印本页]
作者: 瑞星    时间: 2025-2-14 15:30
标题: Redis7.0八种数据结构底层原理
导读

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

一. 内部数据结构

1. sds

sds是redis自己设计的字符串结构有以下特点:

最为重点是引入了jemalloc,十分高效且能有用在redis的场景中减少内存碎片;

不同的字符串长度使用的结构不同最高可以节流18字节;
2. dict

redis的hash表实现

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

采用渐进式扩容数组，但数组需要扩容或缩容时开发数组2,使用数组2存储新数组，在后续操作掷中数组1的bucket时，只复制掷中的bucket数据到数组2;
同时主线程在每次循环任务时会分配1毫秒协助尚未复制的;

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


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


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

主数据结构上分两快:

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)的唯一值聚集，头部存储值的编码类型与长度，其他位置都存储实际数据，由于数组内的数据大小都严酷是头部设置的编码类型所以没有分隔符，同时从小到大存储，所以可以用二分快速查找值。

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

从这点可以发现一些题目,每次添加值都需要扩容内存,为了保持步长一样所有数据都要保持一样的编码类型导致浪费内存;
优点也明显,内存占用少、查询效率O(log n)
核心操作时间复杂度:
操作时间复杂度对应指令查询值O(log n)SISMEMBER添加值O(n)SADD 6. skiplist

跳表是zset的核心数据结构，有序且读写操作效率保持O(logN),从贴出来的代码能出来它不是一个存储在连续内存快的实现(对比listpack和intset）；
  1. /* ZSET使用特殊版本的跳表 */
  2. typedef struct zskiplistNode {
  3.     sds ele;//实际值
  4.     double score;//分数
  5.     struct zskiplistNode *backward;//最上层的前一位(例如node3的最上层前一位是node1)
  6.     struct zskiplistLevel {
  7.         struct zskiplistNode *forward;//向后的node(例如层级1的node3:向后是node4->node5->node6)
  8.         unsigned long span;
  9.     } level[];//存储这个node所在的所有层级(例如节点3那么这个level将只有两个槽位,别存储level1和level2)
  10. } zskiplistNode;
  12. typedef struct zskiplist {
  13.     struct zskiplistNode *header, *tail;//头与尾（最大或最小值）
  14.     unsigned long length;  //存储的数据量
  15.     int level;//跳表深度(也就是索引层数量)
  16. } zskiplist;
  18. typedef struct zset {
  19.     dict *dict;        //<值:Score>(为了快速检查是否唯一)
  20.     zskiplist *zsl;//跳表
  21. } zset;
复制代码

zset是有序&唯一的数据结构,这两特性决定了需要频繁排序和确认唯一,对于保持有序重点对比的是红黑树(也是java中TreeMap的内部实现方法):
操作跳表 (QPS)红黑树 (QPS)优势插入 10w 元素125,00098,000+27.5%范围查询 1000 元素45,00032,000+40.6%查询 1 元素110,000125,000-13%内存占用 (10w 元素)45MB52MB-13.5%代码实现量200行500+行150% 红黑树的树深和跳表的level都可以理解成一个组合的索引,同样是定位"4"但红黑树的二叉树实现明显是可以更快的(红黑树重新到尾都是二分查找)由于红黑树的每一个层级(索引)分布更加匀称,而跳表得益于每个动态随机的层级分布(每个level)层级节点更少从而跳表使用更少的内存

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

以上介绍可以总结以下几点:

而在redis中的跳表还使用了一个dict<值,Scroe>哈希表优化实现唯一值检查和快速过滤无效操作,由于查找某个值不是跳表的刚强(相比红黑树);
7. HyperLogLog(Dense稠密存储&SPARSE稀疏)

理解数据结构前需要先理解HyperLogLog算法原理(请先看下方的[应用数据结构->HyperLogLog])
  1. struct hllhdr {
  2.         char magic[4]; /* 魔法值由于识别结构体"HYLL" */
  3.         uint8_t encoding; /* 编码:HLL_DENSE(稠密) or HLL_SPARSE(稀疏). */
  4.         uint8_t notused[3]; /* 预留字段,暂无使用 */
  5.         uint8_t card[8]; /* 缓存统计结果 */
  6.         uint8_t registers[]; /* 实际存储 */
  7. }
复制代码
registers[]存储的就是桶数据,以稠密存储为例,会一口气申请12KB,6位为一个桶一共16,384个桶:
  1. 12KB=12,288B=98,304bit
  2. 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）标识块类型：
操作码二进制格式占用字节描述XZERO01xxxxxx xxxxxxxx2B表现连续 16384 个桶的值为 0（最大覆盖范围，仅用于初始化）ZERO00xxxxxx1B表现连续 1~64 个桶的值为 0，长度由低 6 位（xxxxxx）表现VAL1vvvvvv11B表现 1 个桶的非零值，值由高 5 位（vvvvv）存储，低 1 位（l）固定为 1 只有槽位1001是3示例:

示例中使用XZERO表现0-1000的桶都是0,使用VAL表现第1001个桶是3,末了又使用XZERO表现剩余的15382个桶都是0;
不再一次性开发所有桶的内存,一但超过阈值再转换为密集存储,从而在空间与时间上有较好的平衡:
性能与内存对比
指标稀疏编码（小基数）密集编码内存占用300B ~ 3KB固定 12KBPFADD 耽误较高（需遍历块）极低（直接位操作）适用场景基数 < 10000基数 ≥ 10000 或高并发 Radix tree(基数树)

Redis 选择 Rax树（基数树，Radix Tree） 作为 Stream 类型数据的底层存储结构，是为了在 内存效率、范围查询性能 和 有序性维护 之间取得平衡。
  1. typedef struct rax {
  2.     raxNode *head; //根节点
  3.     uint64_t numele;//数据量
  4.     uint64_t numnodes;//节点数量
  5.     void *metadata[]; //元数据
  6. } rax;
  8. typedef struct raxNode {
  9.     uint32_t iskey:1;
  10.     uint32_t isnull:1;
  11.     uint32_t iscompr:1;
  12.     uint32_t size:29;  
  13.     //以上:节点标记位
  14.     unsigned char data[]; //实际节点数据:存储listpack结构数据
  15. } raxNode;
复制代码
data内使用listpack存储节点数据,并不是常规的二叉树

追加到listpack：
若当前listpack未满（默认限制约 4096字节），直接追加新消息。
若已满，创建新的listpack，并在Rax树中插入新叶子节点。
二. 应用数据结构

0. 存储框架

Redis是个KV数据库,它的最外层是16,384个solt(也就是一致性hash的槽位),每个槽位中是实际存储dictkey:应用数据结构的数据(hash表);
当执行以下指令后:
  1. LSET key1 index value
  2. SET key2 value
  3. HSET key10 field value
复制代码
实际在redis中的存储结构会是:

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

基于sds,没啥好说的
2. Hash


使用dict不难理解,自己Hash类型就是一个哈希表;
在小数据量使用listpack是为在空间与时间上做平衡,listpack使用两个entry为一组分别存储kv:

特性listpackdict（哈希表）内存占用低（连续存储，无指针开销）高（指针、元数据、哈希表桶开销）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;

以下文指令切入
  1. 127.0.0.1:6379> ZADD zsetKey 1 "apple" 2 "banana" 3 "orange"
  2. (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）;
  1.   SETBIT key 7 1 #第八位设置为1
复制代码
以上指令在第8bit设置为1,Bitmap申请内存并非一口气申请最大512M,而且根据当前要设置的最大逐步申请新的sds;
bitmap实现并不复杂:
指令时间复杂度补充SETBITO(1)GETBITO(1)BITCOUNTO(N)遍历BITPOSO(N)扫描BITFIELDO(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次,从而得到一个基数),而我们只需要记录最大的才是正的次数就可推测出本次游戏大概进行了多少组;
  1. 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底层是跳表,跳表对范围取值时间复杂度较低;
9. Stream

Streams 是一种仅追加的数据结构。基本写入命令（称为 XADD）将新条目追加到指定的流中。
默认会使用-生成每条消息的id，生成的id向前递增，对实际的存储结构有很大的资助（由于前置数字最大限度保持一致，使用基数树作为存储结构时能够减少内存与基于时间范围查询）
性能：
  1. Processed between 0 and 1 ms -> 74.11%
  2. Processed between 1 and 2 ms -> 25.80%
  3. Processed between 2 and 3 ms -> 0.06%
  4. Processed between 3 and 4 ms -> 0.01%
  5. Processed between 4 and 5 ms -> 0.02%
复制代码
99.9% 的哀求的耽误为 <= 2 毫秒，异常值仍旧非常接近平均值。
数据量数据大小占用内存100w1KB1.1G100W250B285.4M   实测插入100w条仅需30秒，qps3.3w
  到此可以总结出redis stream对比kafka：
维度rediskafka数量级别GPB高可用有可能丢失可以做到不丢失功能底子丰富单点stream只单节点多分区qps5w左右（受限只能在一台呆板上）百万级别 Stream 的核心需求

采用了基数树作为存储结构

Stream的默认ID生成方案具有大量前缀(时间戳)、有序向前递进,stream只需删除末端(没有随机删除的需求),只需摘除节点即可。
同时时间戳前缀可以实现基于时间定位与范围取值。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4