1. 压缩列表
压缩列表是redis重要的一种底层结构,这个不懂也得知道点...
1.1. 概念
压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构
1.2. 组成
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 记录整个压缩列表占用的内存字节数,在对压缩列表进行内存重分配,或者计算zlend的位置时使用 |
| zltail | uint32_t | 4字节 | 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节,通过这个偏移量,程序无须遍历整个压缩列表就可以确定表尾节点的地址 |
| zllen | uint16_t | 2字节 | 记录了压缩列表包含的节点数量,当这个属性的值小于 UINT16_MAX(65535)时,这个属性的值就是压缩列表包含节点的数量,当这个值等于UINT16_MAX时,节点的真实数量需要遍历整个压缩列表才能计算得出 |
| entryX | 列表节点 | 不定 | 压缩列表包含的各个节点,节点的长度由节点保存的内存决定 |
| zlend | uint8_t | 1字节 | 特殊值0xFF(十进制255),用于标记压缩列表的末端 |
1.3. 示例
- 列表zlbytes属性的值为0xd2(十进制210),表示压缩列表的总长度为210字节
- 列表zltail属性的值为0xb3(十进制179),表示如果我们有一个指向压缩列表起始地址的指针p,那么只要用指针p加上偏移量179,就可以计算出表尾节点entry5的地址
- 列表zllen属性的值为0x5(十进制5),表示压缩列表包含五个节点
1.4. 节点
- previous_entry_length：每个节点会使用一个或者五个字节来描述前一个节点占用的总字节数，如果前一个节点占用的总字节数小于 254，那么就用一个字节存储，反之如果前一个节点占用的总字节数超过了 254，那么一个字节就不够存储了，这里会用五个字节存储并将第一个字节的值存储为固定值 254 用于区分。
- encoding：压缩列表可以存储 16位、32位、64位的整数以及字符串，encoding 就是用来区分后面的 content 字段中存储于的到底是哪种内容，分别占多少字节
- content：没什么特别的，存储的就是具体的二进制内容，整数或者字符串。
1.4.1. encoding存储
分为两种
字节数组编码
| 编码 | 编码长度 | content类型 |
|---|---|---|
| 00xxxxxx | 一个字节 | 长度小于 63 字节的字节数组 |
| 01xxxxxx xxxxxxxx | 两个字节 | 长度小于 16383 字节的字节数组 |
| 10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx | 五个字节 | 长度小于 4294967295 的字节数组 |
整数编码
| 编码 | 编码长度 | content类型 |
|---|---|---|
| 11000000 | 1字节 | int16_t类型的整数 |
| 11010000 | 1字节 | int32_t类型的整数 |
| 11100000 | 1字节 | int64_t类型的整数 |
| 11110000 | 1字节 | 24位有符号整数 |
| 11111110 | 1字节 | 8位有符号整数 |
| 1111xxxx | 1字节 | 使用这一编码的节点没有相应的content属性,因为编码本身的xxxx四个位已经保存了一个介于0和12之间的值,所以它无须content属性 |
1.4.2. content
节点的content属性负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的encoding属性决定
- 编码的最高两位00表示节点保存的是一个字节数组
- 编码的后六位001011记录了字节数组的长度11
- content属性保存着节点的值
注意,整型数据的编码是固定11开头的八位二进制,而字符串类型的编码都是非固定的,因为它还需要通过后面的二进制位得到字符串的长度,稍有区别
1.5. 连锁更新
previous_entry_length属性记录了前一个节点的长度,如果前一个节点长度小于254个字节,那么previous_entry_length属性需要用一个字节长度来保存这个长度值
现在假如一个压缩列表,有许多连续的,长度介于250~253字节之间的节点e1至eN
现在这些节点的previous_entry_length都只需要1字节长的,如果这时候我将长度为254的新节点new设置为压缩列表的表头节点,那么new就是e1的前置节点..
那么此时e1的previous_entry_length需要进行扩展,因为1节点肯定不够的,更新后,e1超出了254,所以e2的previous_entry_length也需要更新...
这样就会导致所有节点都会发生更新..
Redis将这种在特殊情况下产生的连续多次空间扩展操作称之为 "连锁更新"
因为连锁更新在最坏的情况下需要对压缩列表执行N次空间重分配操作,而每次空间重分配的最坏复杂度为O(N),所以连锁更新最坏的复杂度为O(N²)
但是,尽管连锁更新的复杂度较高,但它真正造成性能问题的几率非常低.因为很难恰好所有节点连续且长度都介于250字节到253字节之间..一般对几个节点进行连锁更新是不会影响性能的!
1.6. 总结
- 压缩列表是一种为节约内存而开发的顺序型数据结构
- 压缩列表被用作列表键和哈希键的底层实现之一
- 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值
- 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引起连锁更新操作,但这种操作出现的几率并不高
以上是我从各方渠道总结而来..大部分摘自
这本书