Redis对象类型与底层数据结构

一、Redis对象类型概述1.1 Redis数据类型总览Redis提供了丰富的数据类型用于不同的业务场景对象类型说明典型场景String字符串缓存、计数器、分布式锁List双向链表队列、消息队列、最新列表Hash哈希表存储对象、购物车Set无序集合好友关系、抽奖Zset有序集合排行榜Stream流数据类型消息队列、事件流HyperLogLog基数统计UV统计二、String类型详解2.1 三种底层编码查看命令OBJECT ENCODING keyString类型根据数据特性分为三种底层实现 ----------------------------------------------- | String 类型 | ----------------------------------------------- | | | int raw embstr | | | | | | | | | | | | v v v | | 整数 长字符串 短字符串 | | 20字节以内 大于44字节 44字节以内 | -----------------------------------------------2.2 int编码触发条件字符串长度小于等于20字节内容是纯整数示例SET num 12345678901234567890 OBJECT ENCODING num - int 存储形式直接以long型整数存储节省内存特点直接存储为C语言的long类型最高效的存储方式INCR/INCRBY等命令直接在整数上操作2.3 raw编码触发条件字符串长度大于44字节示例SET article 这是一段很长的文章内容... 长度超过44字节 OBJECT ENCODING article - raw 存储形式SDSSimple Dynamic String动态字符串SDS结构struct sdshdr { int len; // 已用长度 int free; // 剩余空间 char buf[]; // 实际存储字符的数组 }为什么是44字节embstr和raw的分界线是44字节原因 - embstr只分配一次内存header data连续 - raw需要分配两次内存header和data分开 - 44字节时embstr刚好能用一次内存分配 - 超过44字节embstr反而浪费内存2.4 embstr编码触发条件字符串长度小于等于44字节示例SET name zhangsan OBJECT ENCODING name - embstr 存储形式嵌入式字符串一次内存分配内存布局对比raw编码两次内存分配 --------------------- | sdshdr | SDS头 | --------------------- | char[] | 实际字符串 | - 另一块内存 --------------------- embstr编码一次内存分配 --------------------- | redisObject | sdshdr | ---------------------------- | | char[] | | 整体连续 | 实际字符串 | ----------------------------embstr的优势只需一次内存分配效率更高数据连续存储缓存友好适合短字符串存储三、List类型详解3.1 quicklist双向链表List的底层实现是quicklist 本质上是双向链表 每个节点是ziplist压缩列表 兼顾快速访问和紧凑存储quicklist结构--------------------------------------------- | head | ... | node | ... | tail | | pointer| | ---- | | pointer | ------------------------------------------- | v --------------- | ziplist | | (压缩列表) | ---------------3.2 ziplist压缩列表ziplist的特点连续内存块节省空间每个节点记录前一个节点长度支持双向遍历内存布局紧凑ziplist结构-------------------------------------------- |zlbytes |zltail |zllen| entry1 |...| entryN |zlend| |总长度 |末元素偏移|数量| 内容 |...| 内容 |0xFF| --------------------------------------------节点entry结构------------------------------- | previous| content | encoding | | length | (数据) | (编码) | ------------------------------- | └── 记录前一个节点长度支持从后向前遍历压缩列表的局限新增/修改需要移动后续元素节点过长时效率下降四、Hash类型详解4.1 两种底层编码Hash类型根据数据量自动选择编码 --------------------------------------------- | Hash 类型 | --------------------------------------------- | | | 元素数量 512 | | 且字段长度 64字节 | | | | | v | | ziplist压缩列表 | | (优化存储空间) | | | | | | 超过任一条件 | | v | | dict哈希表 | | (优化查询性能) | ---------------------------------------------4.2 ziplist编码触发条件节点数量小于等于512每个字段字符串长度小于等于64字节存储结构key: *** -------------------------------------------- | field1 | value1 |...|field2 |...|field3 |...|zlend| | name | zhang | | age | |city | |0xFF | --------------------------------------------ziplist存储Hash的特点字段和值交替存储新增字段到列表头部节省内存但查询需要遍历4.3 dict编码触发条件节点数量大于512或字段字符串长度大于64字节dict结构哈希表----------------------------------------- | dict结构 | ----------------------------------------- | hashTable[] | | -------------------------------- | | | slot 0 | slot 1 | slot 2 | slot 3 | | | -------------------------------- | | | | | v | | ---------------- | | | dictEntry | | | | key - value | | | ---------------- | -----------------------------------------dict的特点O(1)时间复杂度查询内存开销比ziplist大适合大量字段的场景五、Set类型详解5.1 两种底层编码Set类型根据元素特性选择编码 --------------------------------------------- | Set 类型 | --------------------------------------------- | | | 元素都是整数 | | 且元素数量 512 | | | | | v | | intset整数集合 | | | | | | 不满足 | | v | | dict字典 | ---------------------------------------------5.2 intset整数集合触发条件所有元素都是整数元素数量不超过512个intset结构---------------------------------------- |encoding|length | [] | 整数数组 | | INT16 | 5 |0 3 5 7 | 按升序排列 | ----------------------------------------特点使用紧凑的整数数组存储节省内存支持二分查找5.3 dict编码触发条件元素包含字符串或元素数量超过512dict实现Set----------------------------------------- | dict实现Set | ----------------------------------------- | key *** | | value NULL只用key | | | | 特性 | | 1. 元素唯一性key不重复 | | 2. 元素无序通过hash保证唯一 | | 3. 快速查找O(1)时间复杂度 | -----------------------------------------Set特有操作差集、交集、并集的实现SINTER setA setB | -- 遍历setA的dict -- 检查元素是否在setB的dict中 -- 返回都存在的元素 SDIFF setA setB | -- 遍历setA的dict -- 检查元素是否不在setB中 -- 返回setA有setB没有的元素六、Zset类型详解6.1 两种底层编码Zset根据数据量选择编码 --------------------------------------------- | Zset 类型 | --------------------------------------------- | | | 元素数量 128 | | 且member长度 64字节 | | | | | v | | ziplist压缩列表 | | (每个元素同时存储member和score) | | | | | | 超过任一条件 | | v | | skiplist dict | | (跳表排序 字典快速查找) | ---------------------------------------------6.2 ziplist编码触发条件元素数量小于等于128每个member长度小于等于64字节存储结构--------------------------------------------------------- | member1 | score1 |...| member2 |...| member3 |...|zlend| | alice | 850 | | bob | | carol | |0xFF | --------------------------------------------------------- score按从小到大排列特点member和score交替存储按score排序节省内存6.3 skiplist跳表编码触发条件元素数量大于128或member长度大于64字节跳表结构Level 3: [head] ---------------------- [node: carol] Level 2: [head] ---- [node: bob] ---- [node: carol] Level 1: [head] ---- [node: alice] -- [node: carol] Level 0: [head] ---- [node: alice] -- [node: bob] ----- [node: carol] 跳跃alice(850) - bob(950) - carol(1200)跳表实现原理跳表是一种多级索引的结构 Level 0: 包含所有元素有序 Level 1: 每隔一个元素选一个 Level 2: 每隔两个元素选一个 ... 查找从最高层开始逐层向下逼近 1. 从Level 3开始发现alice target继续前进 2. 到达bob target继续前进 3. carol target下降到Level 2 4. ... 逐步定位到目标位置 时间复杂度 - 查找O(log n) - 插入O(log n) - 删除O(log n) 空间复杂度 - 每层节点数递减n/2 n/4 n/8 ... 2n - 空间复杂度O(n)为什么Zset需要skiplist dictZset需要支持两种操作 1. 按排名查找ZRANGE 0 9 - 需要跳表 2. 按member查scoreZSCORE - 需要dict 单一数据结构的不足 - 纯跳表无法O(1)查member - 纯dict无法按排名有序 解决方案skiplist dict组合 ----------------------------------------- | Zset同时维护两个结构 | | | | 跳表member - score (用于排序) | | 字典member - score (用于快速查找) | | | | 更新时同时维护两个结构 | | 空间换时间思想 | -----------------------------------------内存布局----------------------------------------------- | skiplist节点 | ----------------------------------------------- | dictEntry (key*** valuescore) | | -------------------------------------------- | | struct zset { | | | | dict *dict; // member - score | | | | skiplist *zsl; // 排序用 | | | | }; | | | -------------------------------------------- ----------------------------------------------- dict和skiplist共享member字符串score在两处都存储七、编码转换规则汇总7.1 String类型转换条件编码说明长度20且为整数int整数存储最省空间长度44embstr一次内存分配高效长度44rawSDS动态字符串7.2 List类型转换条件编码默认quicklistziplist节点7.3 Hash类型转换条件编码说明元素512 且 字段64字节ziplist节省空间元素512 或 字段64字节dict优化查询性能7.4 Set类型转换条件编码说明全整数且元素512intset紧凑存储其他情况dict支持任意类型7.5 Zset类型转换条件编码说明元素128 且 member64字节ziplist节省空间元素128 或 member64字节skiplistdict兼顾排序和查找八、Redis数据结构设计思想8.1 为什么需要动态选择编码内存与性能的权衡Redis是内存数据库 - 内存是稀缺资源 - 需要尽可能节省内存占用 单线程事件循环 - 需要快速响应命令 - 操作延迟直接影响性能两种优化策略策略1空间优化节点少时 -- ziplist紧凑连续存储节省内存 但插入删除需要移动元素O(n) 策略2性能优化节点多时 -- dict/skiplist指针跳转O(1)或O(log n) 但需要额外内存存储索引 Redis的选择 数据少时用空间换时间ziplist 数据多时用时间换空间dict/skiplist8.2 空间换时间思想的应用场景1Zset的skiplist dict空间开销 - 跳表节点每层指针 score member - 字典节点key value 指针 时间收益 - 按排名查找O(log n) 跳表 - 按member查找O(1) 字典 结论用2倍内存换取高效查询场景2quicklist的ziplist节点默认每个ziplist节点最大64KB - 节点太小指针开销大 - 节点太大内存碎片多 配置参数list-max-ziplist-size -2 - -2表示单个节点最大8KB8.3 编码转换的影响转换是单向的Hash: ziplist - dict 一旦数据量超过阈值变成dict后 即使数据减少也不会变回ziplist Set: intset - dict 同理dict不会变回intset业务建议数据量稳定的场景编码转换影响小数据量波动的场景提前预估容量九、查看Redis内部结构9.1 查看对象编码# 查看单个key的编码类型OBJECT ENCODING key# 查看key的内存占用MEMORY USAGE key# 查看key的所有信息DEBUG OBJECT key9.2 编码类型对照表OBJECT ENCODING返回值实际数据结构int整数embstr嵌入式字符串rawSDS动态字符串quicklist快速列表ziplist压缩列表intset整数集合hashtable哈希表skiplist跳表9.3 配置参数# String类型阈值一般不需调整string-max-int-size512# Hash类型阈值hash-max-ziplist-entries512hash-max-ziplist-value64# List类型阈值每个ziplist节点大小list-max-ziplist-size-2# Set类型阈值set-max-intset-entries512# Zset类型阈值zset-max-ziplist-entries128zset-max-ziplist-value64十、面试追问FAQ问题答案Redis为什么用跳表而不是红黑树跳表实现简单区间查找更高效调节参数可控制性能为什么要两种编码数据少用空间优化数据多用性能优化动态切换embstr为什么限制44字节embstr一次内存分配44字节刚好能用一次分配完成压缩列表的优缺点优点内存紧凑缺点插入删除需要移动元素ziplist什么时候会连锁更新连续插入/删除长度接近255的节点时可能触发Redis对象和底层编码的关系一个对象类型可以对应多种编码根据数据量动态选择根据零声教育教学写作https://github.com/0voice