上一篇【第16篇】跳跃表vs平衡树——Redis为什么不用红黑树下一篇【第18篇】压缩列表——Redis的内存压缩黑科技你有没有想过当你在Redis里执行SADD myset 1 2 3的时候这些整数是怎么存储的如果用哈希表存三个整数光哈希表本身的元数据指针、桶数组、链表节点就比数据本身大了好几倍。Redis当然不会做这种亏本买卖——它有一个专门的秘密武器整数集合intset。一、intset是什么intsetInteger Set是Redis用于存储纯整数集合的一种紧凑数据结构。当Redis的Set对象中所有元素都是整数且元素数量不超过配置阈值时就会使用intset作为底层实现而不是哈希表。它的核心设计思想非常简单把所有整数紧凑地存在一个连续数组里像C语言数组一样高效。哈希表存储方式笨重 ┌─────────────────────────────────────┐ │ Hash Table │ │ ┌─────┐ ┌─────┐ ┌─────┐ │ │ │bucket│ │bucket│ │bucket│ ... │ │ └──┬──┘ └──┬──┘ └──┬──┘ │ │ │ │ │ │ │ ┌──▼──┐ ┌──▼──┐ ┌──▼──┐ │ │ │entry│ │entry│ │entry│ ... │ ← 指针、next指针、key、value... │ └─────┘ └─────┘ └─────┘ │ └─────────────────────────────────────┘ 存3个整数可能需要200字节 intset存储方式紧凑 ┌─────────────────────────────────────┐ │ intset │ │ ┌───┬───┬───┬───┬───┐ │ │ │enc│len│ 1 │ 2 │ 3 │ │ ← 只需要几个字节取决于编码 │ └───┴───┴───┴───┴───┘ │ └─────────────────────────────────────┘ 存3个int16整数只需14字节差距一目了然。二、intset的结构体定义intset的结构非常简洁定义在intset.h中typedefstructintset{uint32_tencoding;// 编码方式INT16/INT32/INT64uint32_tlength;// 元素数量int8_tcontents[];// 柔性数组实际存储整数数据}intset;三个字段清清楚楚encoding当前使用的编码方式决定了contents数组中每个元素占多少字节length集合中元素的数量也就是contents数组的实际使用长度contents柔性数组C语言的trick数组大小在运行时确定紧凑存储所有整数踩坑提示注意contents的类型是int8_t而不是某个具体的整数类型。这是一个占位类型实际存储时根据encoding的值以2字节、4字节或8字节为单位来解读这块内存。这是C语言柔性数组的经典用法。三、三种编码方式intset支持三种编码对应三种整数大小编码宏定义值每元素大小存储范围INTSET_ENC_INT1622字节-32768 ~ 32767INTSET_ENC_INT3244字节-2147483648 ~ 2147483647INTSET_ENC_INT6488字节-2^63 ~ 2^63-1三种编码的内存布局对比INT16编码每个元素2字节 ┌──────────┬────────┬──────┬──────┬──────┬──────┐ │encoding │length │ 1 │ 2 │ 3 │ 5 │ │(4 bytes) │(4bytes)│(2b) │(2b) │(2b) │(2b) │ └──────────┴────────┴──────┴──────┴──────┴──────┘ INT32编码每个元素4字节 ┌──────────┬────────┬──────────┬──────────┬──────────┐ │encoding │length │ 1 │ 2 │ 100000 │ │(4 bytes) │(4bytes)│ (4 bytes)│ (4 bytes)│ (4 bytes)│ └──────────┴────────┴──────────┴──────────┴──────────┘ INT64编码每个元素8字节 ┌──────────┬────────┬──────────────┬──────────────┐ │encoding │length │ 42 │ 9999999999 │ │(4 bytes) │(4bytes)│ (8 bytes) │ (8 bytes) │ └──────────┴────────┴──────────────┴──────────────┘初始创建的intset默认使用INT16编码——毕竟大部分场景下小整数就够了能省就省。四、有序存储为二分查找而生intset中的元素始终按从小到大的顺序排列。这不是偶然而是精心设计——有序数组支持二分查找查找时间复杂度为 O(logN)。// intset的查找实现简化版uint8_tintsetFind(intset*is,int64_tvalue){// 二分查找if(valueintsetGet(is,is-length-1)||valueintsetGet(is,0)){return0;// 不在范围内直接返回}// 标准二分查找intlo0,hiis-length-1;while(lohi){intmid(lohi)/2;int64_tcurintsetGet(is,mid);if(curvalue)return1;elseif(curvalue)lomid1;elsehimid-1;}return0;}intset二分查找示例在 {1, 3, 5, 7, 9, 11, 13} 中查找 7 索引: 0 1 2 3 4 5 6 内容: [ 1 3 5 7 9 11 13 ] ^ 第一次: lo0, hi6, mid3 → is[3]7 7 ✓ 找到了虽然二分查找是 O(logN)但别忘了intset元素数量通常很小默认上限512个实际上查找非常快。五、整数集合升级详解intset最有意思的机制就是编码升级。当你要插入一个新整数而它的值超出了当前编码能表示的范围时intset会自动升级编码方式。升级的触发条件当前编码是INT16存了 {1, 3, 5} 现在插入 70000超过了INT16的32767上限 → 触发升级INT16 → INT32升级的三步过程升级不是简单地把数组变大而是涉及到数据的重新排列第一步空间重分配根据新的编码方式重新计算需要的内存大小然后扩展contents数组。升级前INT163个元素 ┌──────────┬────────┬────┬────┬────┐ │encoding │length │ 1 │ 3 │ 5 │ 总大小: 446 14字节 │ 2 │ 3 │(2b)│(2b)│(2b)│ └──────────┴────────┴────┴────┴────┘ 升级后INT324个元素插入了70000 ┌──────────┬────────┬──────┬──────┬──────┬──────────┐ │encoding │length │ 1 │ 3 │ 5 │ 70000 │ 总大小: 4416 24字节 │ 4 │ 4 │(4b) │(4b) │(4b) │ (4b) │ └──────────┴────────┴──────┴──────┴──────┴──────────┘第二步数据迁移从后往前这是升级最关键的一步。因为元素大小变了比如从2字节变成4字节需要把所有已有元素移动到新位置。迁移是从后往前进行的——这样可以避免覆盖还没迁移的数据。从后往前迁移过程INT16→INT32 原始位置: [0] [2] [4] [6] 字节偏移 1 3 5 目标位置: [0] [4] [8] [12] 字节偏移 1 3 5 70000 迁移顺序: 5 → 3 → 1从后往前 最后: 70000 直接放到位置 [12]// 升级后重新放置元素简化版staticvoidintsetUpgradeAndAdd(intset*is,int64_tvalue){uint8_tcurencis-encoding;uint8_tnewenc_intsetValueEncoding(value);// 计算新元素应该插入的位置intpos(value0)?0:is-length;// 扩展空间is-encodingnewenc;isintsetResize(is,(is-length1)*newenc);// 从后往前迁移已有元素while(is-lengthpos){intsetSet(is,is-length,intsetGetEncoded(is,is-length-1,curenc));is-length--;}// 设置新元素intsetSet(is,pos,value);is-length;}第三步更新encoding和length修改encoding为新的编码方式length加1。升级过程完整图示INT16 → INT32 升级全过程 时间轴 → 步骤1原始状态: [enc2][len3][ 1 ][ 3 ][ 5 ] 字节: 0-3 4-7 8-9 10-11 12-13 步骤2扩展空间: [enc2][len3][ 1 ][ 3 ][ 5 ][ ???? ] 字节: 0-3 4-7 8-11 12-15 16-19 20-23 步骤3从后往前迁移5从offset 12-13移到16-19: [enc2][len3][ 1 ][ 3 ][ ?? ][ 5 ] 字节: 0-3 4-7 8-11 12-15 16-19 20-23 步骤4迁移3从offset 10-11移到12-15: [enc2][len3][ 1 ][ ?? ][ 3 ][ 5 ] 步骤5迁移1从offset 8-9移到8-11: [enc2][len3][ 1 ][ ?? ][ 3 ][ 5 ] 步骤6插入70000更新enc4, len4: [enc4][len4][ 1 ][ 70000][ 3 ][ 5 ]六、升级的好处灵活性与内存节省兼得intset的升级机制是一个很好的按需付费设计方面说明灵活性可以同时存储不同大小的整数不需要预先确定最大值内存节省只在需要时才使用更大的编码小整数场景下不浪费空间自动管理开发者完全不需要关心编码切换Redis自动处理想象一下如果你的集合里存的是用户ID大部分是1-1000的小数字偶尔来一个几百万的ID。如果一开始就用INT64每个ID占8字节但用intset的话大部分时候只用2字节INT16偶尔升级到INT32或INT64。七、只能升级不能降级intset的设计中有一个重要规则编码只能升级永远不能降级。什么意思如果你把一个INT32的intset中最大的那个大数字删掉了intset不会自动降级回INT16。# 演示删除大数字后不会降级127.0.0.1:6379SADD myset123(integer)3127.0.0.1:6379OBJECT ENCODING mysetint16# 小数字INT16编码127.0.0.1:6379SADD myset100000(integer)1127.0.0.1:6379OBJECT ENCODING mysetint32# 升级到INT32127.0.0.1:6379SREM myset100000(integer)1127.0.0.1:6379OBJECT ENCODING mysetint32# 删除后仍然是INT32没有降级为什么不支持降级避免频繁转换的开销如果频繁地添加大数又删除大数会导致频繁的升级/降级操作节省内存的收益不大降级节省的内存通常很少不值得增加代码复杂度简化的设计只升级不降级让代码逻辑更简单也更不容易出bug这种只涨不跌的设计哲学在Redis中很常见——和我们前面讨论的ziplist、skiplist一样Redis倾向于用简单的规则换取代码的可维护性。八、intset → hashtable的升级触发条件intset虽然省内存但它不是万能的。当满足以下任一条件时Redis会将Set的底层实现从intset切换为hashtable条件配置参数默认值元素数量超过阈值set-max-intset-entries512插入了非整数值--触发条件示意 插入元素 │ ├─ 是整数 ─── 否 ───→ 升级为hashtable │ 集合中出现字符串intset无法存储 │ └─ 是整数 │ ├─ 集合元素数 512 → 保持intset │ └─ 集合元素数 ≥ 512 → 升级为hashtable 避免超大intset的O(N)插入开销# 条件1元素数量超过阈值127.0.0.1:6379EVALfor i1,513 do redis.call(SADD,myset,i) end0(integer)513127.0.0.1:6379OBJECT ENCODING mysethashtable# 超过512个元素自动切换# 条件2插入非整数值127.0.0.1:6379SADD myset2123(integer)3127.0.0.1:6379OBJECT ENCODING myset2int16127.0.0.1:6379SADD myset2hello(integer)1127.0.0.1:6379OBJECT ENCODING myset2hashtable# 插入字符串自动切换踩坑提示一旦从intset升级为hashtable即使你删掉了那个字符串元素或者把元素数量减到512以下也不会降级回intset。和只升级不降级的编码策略一样这是Redis的一贯设计。九、intset的API一览Redis为intset提供了一组简洁的API// 创建一个新的intset默认INT16编码intset*intsetNew(void);// 向intset中添加元素可能触发升级intset*intsetAdd(intset*is,int64_tvalue,uint8_t*success);// 从intset中删除元素intset*intsetRemove(intset*is,int64_tvalue,int8_t*success);// 判断元素是否存在uint8_tintsetFind(intset*is,int64_tvalue);// 获取intset中的元素数量uint32_tintsetLen(constintset*is);// 获取intset占用的字节数size_tintsetBlobLen(intset*is);// 随机返回一个元素int64_tintsetRandom(constintset*is);每个API的设计都很直观这里重点提几个点intsetAdd返回新的intset指针因为升级可能需要重新分配内存所以返回的是可能变化的新指针虽然大多数情况下地址不变intsetRemove同样返回新指针删除后可能需要压缩内存intsetRandom用于SRANDMEMBER命令直接通过索引随机访问O(1)复杂度十、实际演示用redis-cli观察intset让我们通过实际的redis-cli操作来验证intset的行为# 创建一个小整数集合127.0.0.1:6379SADD nums12345(integer)5# 查看底层编码127.0.0.1:6379OBJECT ENCODING numsint16# 查看内存占用127.0.0.1:6379MEMORY USAGE nums(integer)56# 非常小# 添加一个大数字触发升级127.0.0.1:6379SADD nums100000(integer)1127.0.0.1:6379OBJECT ENCODING numsint32# 升级到INT32# 添加一个超大数字127.0.0.1:6379SADD nums99999999999999(integer)1127.0.0.1:6379OBJECT ENCODING numsint64# 升级到INT64# 查看内存增长127.0.0.1:6379MEMORY USAGE nums(integer)96# 比之前大了但仍然很小# 验证元素存在性127.0.0.1:6379SISMEMBER nums3(integer)1# 存在127.0.0.1:6379SISMEMBER nums999(integer)0# 不存在# 随机返回一个元素127.0.0.1:6379SRANDMEMBER nums2十一、总结intset的设计哲学可以用一句话概括简单就是美。特性说明存储方式连续有序数组查找O(logN) 二分查找插入O(N)需要移动元素删除O(N)需要移动元素内存极度紧凑接近理论最小值升级只升不降按需扩展降级升级为hashtable不可逆intset不是什么花哨的数据结构它就是C语言里最朴素的数组加上一点自动管理。但正是这种简单带来了极致的内存效率和可预测的性能。在Redis的世界里有时候最简单的方案就是最好的方案。下一篇我们将学习另一个紧凑数据结构——压缩列表ziplist它的设计比intset更复杂也更精彩。准备好了吗上一篇【第16篇】跳跃表vs平衡树——Redis为什么不用红黑树下一篇【第18篇】压缩列表——Redis的内存压缩黑科技