广东微信网站推广哪家专业,wordpress 七牛云图床,购物网站设计的意义,系统管理在哪里找怎么找导读
本文介绍redis应用数据结构与物理存储结构,共八种应用数据结构和
一. 内部数据结构
1. sds
sds是redis自己设计的字符串结构有以下特点:
jemalloc内存管理预分配冗余空间二进制安全(c原生使用\0作为结尾标识,所以无法直接存储\0)动态计数类型(根据字符串长度动态选择…导读
本文介绍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,00098,00027.5%范围查询 1000 元素45,00032,00040.6%查询 1 元素110,000125,000-13%内存占用 (10w 元素)45MB52MB-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个桶:
12KB12,288B98,304bit
98,304÷616,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 类型数据的底层存储结构是为了在 内存效率、范围查询性能 和 有序性维护 之间取得平衡。
typedef struct rax {raxNode *head; //根节点uint64_t numele;//数据量uint64_t numnodes;//节点数量void *metadata[]; //元数据
} rax;typedef struct raxNode {uint32_t iskey:1;uint32_t isnull:1; uint32_t iscompr:1;uint32_t size:29; //以上:节点标记位unsigned char data[]; //实际节点数据:存储listpack结构数据
} raxNode;data内使用listpack存储节点数据,并不是常规的二叉树 追加到listpack 若当前listpack未满默认限制约 4096字节直接追加新消息。 若已满创建新的listpack并在Rax树中插入新叶子节点。
二. 应用数据结构
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:
特性listpackdict哈希表内存占用低连续存储无指针开销高指针、元数据、哈希表桶开销100个值内存占用2.2KB12KB查询效率O(n)需遍历O(1)哈希直接定位插入/删除效率中等需内存重排高直接操作节点但扩容有抖动适用场景小数据字段数少值长度短大数据字段多查询频繁自动转换阈值hash-max-listpack-entries默认512hash-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实现并不复杂:
指令时间复杂度补充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次,从而得到一个基数),而我们只需要记录最大的才是正的次数就可推测出本次游戏大概进行了多少组;
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向前递增对实际的存储结构有很大的帮助因为前置数字最大限度保持一致使用基数树作为存储结构时能够减少内存与基于时间范围查询
性能
Processed between 0 and 1 ms - 74.11%
Processed between 1 and 2 ms - 25.80%
Processed between 2 and 3 ms - 0.06%
Processed between 3 and 4 ms - 0.01%
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 格式为 时间戳-序列号需支持高效范围查询如 XRANGE。内存压缩消息 ID 具有大量公共前缀相同时间戳适合前缀树压缩。动态扩展Stream 可能频繁插入新消息需低开销的动态结构调整。
采用了基数树作为存储结构 Stream的默认ID生成方案具有大量前缀(时间戳)、有序向前递进,stream只需删除末尾(没有随机删除的需求),只需摘除节点即可。 同时时间戳前缀可以实现基于时间定位与范围取值。
