Redis 内存压缩原理

2024-05-27 19:27:05 200

本文内容纲要：

-了解编码类型

-ziplist

-quicklist

-intset

Redis无疑是一个大量消耗内存的数据库，因此Redis引入了一些设计巧妙的数据结构进行内存压缩来减轻负担。ziplist、quicklist以及intset是其中最常用最重要的压缩存储结构。

了解编码类型

Redis对外提供了string,list,hash,set,zset等数据类型，每种数据类型可能存在多种不同的底层实现，这些底层数据结构被称为编码(encoding)。

以list类型为例，其经典的实现方式为双向链表(linkedlist)。双向链表的每个节点拥有一个前向指针一个后向指针，在64位系统下每个节点占用了2*64bit=16Byte的额外空间。因此当list中元素较少时会使用ziplist作为底层数据结构。

objectencoding<key>命令可以查看某个key的编码类型:

127.0.0.1:6379>seta1
OK
127.0.0.1:6379>objectencodinga
"int"
127.0.0.1:6379>rpushl1
(integer)1
127.0.0.1:6379>objectencodingl
"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存储为一段裸二进制数据(unsignedchar*)，可以看到源代码中大量使用宏进行定义，虽然节省了大量内存但是代码可读性较低。

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
01ppppppqqqqqqqq: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

Redis3.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大小不能超过64KB
-4:每个节点上的ziplist大小不能超过32KB。
-3:每个节点上的ziplist大小不能超过16Kb。
-2:每个节点上的ziplist大小不能超过8Kb。这是redis的默认设置。
-1:每个节点上的ziplist大小不能超过4Kb。

压缩中间节点

对于一个很长的列表而言，最常使用的是其两端的数据，中间数据被访问的概率较低。因此，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语言的柔性数组(flexiblearraymember)。

需要注意的是，每次添加元素intset都会检查是否需要将INTSET_ENCODING升级为更长的整数。与每个entry拥有独立encoding的ziplist不同，inset中所有成员使用统一的encoding。

本文内容总结：了解编码类型，ziplist，quicklist，intset，

原文链接：https://www.cnblogs.com/Finley/p/13423846.html