随笔分类
整数集合
intset
集合键的底层实现之一
当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会选择整数集合作为集合键的底层实现.
实现
整数集合是Redis用于保存整数值的集合抽象数据结构
可以保存类型为int16_t,int32_t,int64_t的整数值,并且可以来保证集合中不会出现重复元素.
typedef struct intset {
// 编码方式
// INTSET_ENC_INT16 --> int16_t -32768 ~ 32767
// INTSET_ENC_INT32 --> int32_t -2147483648 ~ 2147483647
// INTSET_ENC_INT64 --> int64_t -9223372036854775808 ~ 9223372036854775807
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组 --> 默认从小到大进行排序
// 类型虽然为int8_t,但contents类型真正取决于encoding属性的值.
int8_t contents[];
} intset;
升级
每当我们新增一个新元素到整数集合里,且新元素的类型比整数集合现有所有元素类型都要长时,整数集合需要先进行升级(upgrade)
,然后才能将新元素添加到整数集合里面.
升级整数集合并添加新元素共分为三步进行:
- 根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
- 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,而且在放置元素的过程中,需要继续
维持底层数组的有序性质
保持不变 - 将新元素添加到底层数组里面.
如图
将int16_t转换为int32_t
最后来添加新元素
最后,程序将整数集合encoding属性的值从INTSET_ENC_INT16改为INTSET_ENC_INT32,并且将length属性的值从3改为4,设置完成之后的整数集合如图所示:
因为每次向整数集合添加新元素都有可能会引起升级,而每次升级都需要对底层数组中已有的元素进行类型转换,故时间复杂度实际上为O(N)
.
好处
-
提升整数集合的灵活性
C语言是静态类型语言,为了避免类型错误,通常不会将类型不同的值放在同一个数据结构里
而有了自动升级来适应新元素的机制存在,所以我们可以随意地将int16_t,int32_t,int64_t类型的整数添加到集合中,而不必去担心类型错误,这种方式十分灵活
-
节约内存
整数集合可以让集合同时保存多种不同类型的值,又可以确保升级操作只有在有需要时才会进行,这样能尽量节省内存.
降级
整数集合不支持降级操作,一旦对数组进行了升级,编码就会一直保持升级后的状态.
压缩列表
ziplist
作为列表键和哈希键的底层实现之一
lake:0>RPUSH rlist 1 2 3 6 1024 "xge" "cxu3" "2du4"
"8"
lake:0>OBJECT ENCODING rlist
"quicklist" # quicklist是ziplist 和 linkedlist 的混合体,它将linkedlist按段切分,每一段使用ziplist来紧凑存储,多个ziplist使用多个双向指针串接起来.
当一个列表键只包含少量列表项,并且每个列表项要么是小整数集,或是长度比较短的字符串,那么Redis就会使用ziplist
作为列表键的底层实现.
lake:0>hmset hlst name "liangye" age 15
"OK"
lake:0>OBJECT ENCODING hlst
"ziplist"
当一个哈希键只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会选择ziplist
作为哈希键的底层实现.
构成
压缩列表
ziplist
是Redis为了节约内存
而开发的,是由一系列特殊编码的连续内存块
组成的顺序性(sequential)数据结构. 一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值.
属性 | 类型 | 长度 | 用途 |
---|---|---|---|
zlbytes | uint32_t | 4字节 | 记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配,或者计算zlend的位置时使用 |
zltail | uint32_t | 4字节 | 记录压缩列表尾结点距离压缩列表起始地址有多少个字节:通过这个偏移量,程序无需遍历整个压缩列表就可以确定表尾结点的地址 |
zllen | uint16_t | 2字节 | 记录了压缩列表包含的节点数量:当这个数量小于UINT16_MAX(65535)时,这个属性的值便是压缩列表所包含节点的数量;当这个值等于UINT16_MAX(65535)时,节点的真实数量需要遍历整个压缩列表 才能计算出 |
entryX | 列表结点 | 不定 | 压缩列表包含的各个节点,节点的长度由节点保存的内容决定 |
zlend | uint8_t | 1字节 | 特殊值0xFF(十进制255),用于标记压缩列表的尾部 |
列表结点
每个压缩列表结点可以保存一个字节数组或者一个整数值
每一个压缩列表结点都有previous_entry_length、encoding、content三个部分组成
-
previous_entry_length: 记录压缩列表前一个节点的长度,其属性的长度可以是1字节或者5字节:
- 如果前一节点的长度小于254字节,那么previous_entry_length属性的长度为1字节:前一个节点的长度就记录在这一个字节里面
- 如果前一个节点的长度大于等于254字节,那么previous_entry_length属性的长度为5字节:其中属性的第一字节被设置为0xFE(十进制254),而之后的四个字节用于保存前一节点的长度.
程序可以指针运算,根据当前节点的起始地址计算出前一个节点的起始地址,压缩列表的往前回溯原理于此
-
encoding: 记录了节点的content属性所保存数据的类型以及长度
-
content: 负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度有节点的encoding属性决定.
连锁更新
前述,previous_entry_length的长度取决于前一个节点的长度,当新增表头节点,且列表中存在连续的、长度介于250字节至253字节之间的节点时,此时后续节点的previous_entry_length长度会变成5字节,此时便有可能存在超过254节点的情况,这时便会触发后续节点的空间重分配
操作(即为,连锁更新
)
这是一种极端的操作,连续对压缩列表进行了多次的空间重分配操作
除了添加新节点可能会触发连锁更新外,删除节点同理也有可能会触发连锁更新.
连锁更新在最坏情况下需要对列表进行N次的空间重分配,而每次空间重分配的最坏复杂度为O(N),所以连锁更新的最坏复杂度为O(N^2)
.
要注意的是,尽管连锁更新的复杂度较高,但它真正造成性能问题的几率是很低的:
- 首先,压缩列表里要恰好有多个连续的、长度介于250字节至253字节之间的节点,连锁更新才有可能被引发,在实际中,这种情况并不多见.
- 其次,即使出现了连锁更新,但只要被更新的节点数量不多,就不会对性能造成任何影响