Redis 无疑是一个大量消耗内存的数据库，因此 Redis 引入了一些设计巧妙的数据结构进行内存压缩来减轻负担。ziplist、quicklist 以及 intset 是其中最常用最重要的压缩存储结构。
Redis对外提供了 string, list, hash, set, zset等数据类型，每种数据类型可能存在多种不同的底层实现，这些底层数据结构被称为编码(encoding)。
以 list 类型为例，其经典的实现方式为双向链表(linkedlist)。双向链表的每个节点拥有一个前向指针一个后向指针，在64位系统下每个节点占用了 2 * 64bit = 16 Byte 的额外空间。因此当 list 中元素较少时会使用 ziplist 作为底层数据结构。
object encoding <key></key> 命令可以查看某个 key 的编码类型:
127.0.0.1:6379> set a 1
OK
127.0.0.1:6379> object encoding a
"int"
127.0.0.1:6379> rpush l 1
(integer) 1
127.0.0.1:6379> object encoding l
"ziplist"
先总结一下各种数据结构可以使用的编码类型，下文再对这些压缩类型进行详细说明:
- string
- raw: 动态字符串(SDS)
- embstr: 优化内存分配的字符串编码
- int: 整数
- list
- linkedlist
- ziplist
- quicklist
- set
- hashtable
- intset
- hash
- ziplist
- hashtable
- zset(sortedset)
- ziplist
- skiplist
本文接下来将详细说明各种压缩编码的原理以及编码决定规则。
ziplist 是一段连续内存，类似于数组结构。当元素比较少时使用数组结构不仅节省内存，而且遍历操作的开销也不大。因此 list, hash, zset 在元素较少时都采用 ziplist 存储。
ziplist 存储为一段裸二进制数据(unsigned char *)， 可以看到源代码中大量使用宏进行定义，虽然节省了大量内存但是代码可读性较低。
ziplist 的结构:
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
</zlend></entry></entry></entry></zllen></zltail></zlbytes>
- zlbytes: uint32 型, 存储整个ziplist当前被分配的空间，包含自身占用的4个字节。
- zltail: uint32 型, 存储ziplist中最后一个entry相对头部的偏移量, 用于直接访问尾端元素避免遍历。
- zllen: uint16 型, 记录 ziplist 中元素的个数
- entry: 实际存储元素的单元
- zlend: 魔法数字 255 标记 ziplist 的结尾, 没有 entry 以 0xff 开头不会出现误判的问题
entry 是实际存储数据的单元, 可以存储 int 或 string 类型数据。在存储 string 类型数据时 entry 的结构为:
- prevlen: 表示前一个 entry 的长度，用于从后向前遍历。
- encoding: 存储当前 entry 的数据类型和长度
- entry-data: 实际的数据部分
当存储 int 类型的数据时, 数据(entry-data)会被合并到 encoding 内部，此时没有 entry-data 字段。
当前一个元素长度小于254（255用于zlend）时，prevlen长度为1个字节，值为前一个entry的长度；如果长度大于等于254，prevlen 用5个字节表示，第一字节设置为254，后面4个字节存储一个小端的无符号整型，表示前一个entry的长度。
encoding 用来表示 entry 的数据类型和长度。encoding 的全部定义可以在 ziplist.c 中找到。
下面列出几种 encoding 的示例，encoding 中的字母表示一个bit:
- 00pppppp: encoding 的长度为一个字节，后6位表示字符串的长度。因为长度最多6位，因此字符串的长度不超过63
- 01pppppp qqqqqqqq: encoding 的长度为两个字节, 后14位存储字符串的长度，因此字符串的长度不超过16383
- 11000000: encoding为3个字节，后2个字节表示一个int16
- 1110000: encoding为4个字节，后3个字节表示一个有符号整型
- 11111111: zlend
前面提到每个 entry 都会有一个 prevlen 字段存储前一个 entry 的长度。如果内容小于 254 字节，prevlen 用 1 字节存储，否则就是 5 字节。这意味着如果某个 entry 经过了修改操作从 253 字节变成了 254 字节，那么它的下一个 entry 的 prevlen 字段就要更新，从 1 个字节扩展到 5 个字节；如果这个 entry 的长度本来也是 253 字节，那么后面 entry 的 prevlen 字段还得继续更新。这种现象被称为 ziplist 的 级联更新，添加、修改、删除元素的操作都有可能导致级联更新。
ziplist 不会预留扩展空间，每次插入一个新的元素就需要调用 realloc 扩展内存, 并可能需要将原有内容拷贝到新地址。
综上，ziplist 是一个使用连续内存存储数据，类似于数组的数据结构。可以 O(1) 的时间复杂度访问首尾元素。因为 entry 长度不确定，可以向前或向后顺序访问，不能随机访问。因为级联更新的现象的存在，添加、修改、删除元素操作的复杂度在 O(n) 到 O(n^2) 之间。
在满足下列条件时， list, hash 和 sortedset 三种结构会采用 ziplist 编码:
- list: value 字节数
ziplist 存储 list 时每个元素会作为一个 entry; 存储 hash 时 key 和 value 会作为相邻的两个 entry; 存储 zset 时 member 和 score 会作为相邻的两个entry。
当不满足上述条件时，ziplist 会升级为 linkedlist, hashtable 或 skiplist 编码。在任何情况下大内存的编码都不会降级为 ziplist。
Redis 3.2 版本引入了 quicklist 作为 list 的底层实现，不再使用 linkedlist 和 ziplist 实现。 quicklist 是 ziplist 组成的双向链表，它的每个节点都是一个 ziplist。
quicklist 是结合了 linkedlist 和 ziplist 优点的产物:
- linkedlist 便于进行增删改操作但是内存占用较大
- ziplist 内存占用较少，但是因为每次修改都可能触发 realloc 和 memcopy, 并且可能导致级联更新。因此修改操作的效率较低，在 ziplist 较长时这个问题更加突出。
于是每个节点上 ziplist 的大小变成了一个需要折中的难题:
- ziplist 越小，quicklist 越接近于 linkedlist。此时存储效率下降，但是修改操作的效率较高。
- ziplist 越大，quicklist 越接近于 ziplist。此时存储效率上升，但是修改操作的效率降低。
redis 根据 list-max-ziplist-size 配置项来决定节点上 ziplist 的长度。
当 list-max-ziplist-size 为正值的时候，表示按照数据项个数来限定每个 quicklist 节点上的 ziplist 长度。比如，当这个参数配置成5的时候，表示每个 quicklist 节点的ziplist 最多包含5个数据项。
当为负值的时候，表示按照占用字节数来限定每个节点上的 ziplist 长度。这时，它只能取 -1 到 -5 这五个值:
- -5: 每个节点上的 ziplist 大小不能超过64 KB
- -4: 每个节点上的 ziplist 大小不能超过 32 KB。
- -3: 每个节点上的 ziplist 大小不能超过16 Kb。
- -2: 每个节点上的 ziplist 大小不能超过8 Kb。这是 redis 的默认设置。
- -1: 每个节点上的 ziplist 大小不能超过4 Kb。
压缩中间节点
对于一个很长的列表而言，最常使用的是其两端的数据，中间数据被访问的概率较低。因此，quicklist 允许将中间的节点使用 LZF 算法进行压缩以节省内存。
list-compress-depth 表示quicklist两端不被压缩的节点个数:
- 0: 表示都不压缩。这是Redis的默认值。
- 1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
- 2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。
- 以此类推…
当集合中的元素均为整数且元素数少于 set-max-intset-entries 时，redis 采用 inset 编码存储集合。当插入非整数元素或元素数超过阈值后，intset 会升级为 hashtable 编码进行存储。
intset 是整数元素组成的有序数组, 可以支持 O(logn) 级别的查询。
intset 的内存结构与 ziplist 类似是一段的内存。它由三个部分组成:
- encoding: 表示intset中的每个数据元素用几个字节来存储。它有三种可能的取值：
- INTSET_ENC_INT16表示每个元素用2个字节存储
- INTSET_ENC_INT32表示每个元素用4个字节存储
- INTSET_ENC_INT64表示每个元素用8个字节存储。
- length: 表示intset中的元素个数。encoding和length两个字段构成了intset的头部（header）。
- contents: 表示实际存储的内容。它是一个C语言的柔性数组(flexible array member)。
需要注意的是，每次添加元素 intset 都会检查是否需要将 INTSET_ENCODING 升级为更长的整数。与每个 entry 拥有独立 encoding 的 ziplist 不同，inset 中所有成员使用统一的 encoding。
Original: https://www.cnblogs.com/Finley/p/13423846.html
Author: -Finley-
Title: Redis 内存压缩原理
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/529392/
转载文章受原作者版权保护。转载请注明原作者出处！