Redis 内存压缩原理

Ashes 2020-08-03

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 的编码类型:

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

ziplist 是一段连续内存,类似于数组结构。当元素比较少时使用数组结构不仅节省内存,而且遍历操作的开销也不大。因此 list, hash, zset 在元素较少时都采用 ziplist 存储。

ziplist 的源码可以在: redis/ziplist.c 中找到。

ziplist 存储为一段裸二进制数据(unsigned char *), 可以看到源代码中大量使用宏进行定义,虽然节省了大量内存但是代码可读性较低。

ziplist 的结构:

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
  • 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 字节数 <= list-max-ziplist-value 且 元素数 <= list-max-ziplist-entries
  • hash: value 字节数 <= hash-max-ziplist-value 且 元素数 <= hash-max-ziplist-entries
  • zset: value 字节数 <= zset-max-ziplist-value 且 元素数 <= zset-max-ziplist-entries

ziplist 存储 list 时每个元素会作为一个 entry; 存储 hash 时 key 和 value 会作为相邻的两个 entry; 存储 zset 时 member 和 score 会作为相邻的两个entry。

当不满足上述条件时,ziplist 会升级为 linkedlist, hashtable 或 skiplist 编码。在任何情况下大内存的编码都不会降级为 ziplist。

quicklist

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个节点不压缩,中间的节点压缩。
  • 以此类推...

intset

当集合中的元素均为整数且元素数少于 set-max-intset-entries 时,redis 采用 inset 编码存储集合。当插入非整数元素或元素数超过阈值后,intset 会升级为 hashtable 编码进行存储。

intset 的源码可以在: redis/intset.c 中找到。

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。

相关推荐

DiamondTao / 0评论 2020-08-30