温州建设集团官方网站,石家庄在线制作网站,样品门展厅设计图片,电子商务网站基础建设压缩列表的最大特点#xff0c;就是它被设计成一种内存紧凑型的数据结构#xff0c;占用一块连续的内存空间#xff0c;不仅可以利用 CPU 缓存#xff0c;而且会针对不同长度的数据#xff0c;进行相应编码#xff0c;这种方法可以有效地节省内存开销。 但是#xff0c;…压缩列表的最大特点就是它被设计成一种内存紧凑型的数据结构占用一块连续的内存空间不仅可以利用 CPU 缓存而且会针对不同长度的数据进行相应编码这种方法可以有效地节省内存开销。 但是压缩列表的缺陷也是有的
不能保存过多的元素否则查询效率就会降低新增或修改某个元素时压缩列表占用的内存空间需要重新分配甚至可能引发连锁更新的问题。 因此Redis 对象List 对象、Hash 对象、Zset 对象包含的元素数量较少或者元素值不大的情况才会使用压缩列表作为底层数据结构。
压缩列表结构设计
压缩列表是 Redis 为了节约内存而开发的它是由连续内存块组成的顺序型数据结构有点类似于数组。
压缩列表在表头有三个字段
zlbytes记录整个压缩列表占用对内存字节数zltail记录压缩列表「尾部」节点距离起始地址由多少字节也就是列表尾的偏移量zllen记录压缩列表包含的节点数量zlend标记压缩列表的结束点固定值 0xFF十进制255。
在压缩列表中如果我们要查找定位第一个元素和最后一个元素可以通过表头三个字段zllen的长度直接定位复杂度是 O(1)。而查找其他元素时就没有这么高效了只能逐个查找此时的复杂度就是 O(N) 了因此压缩列表不适合保存过多的元素。 另外压缩列表节点entry的构成如下
压缩列表节点包含三部分内容 prevlen记录了「前一个节点」的长度目的是为了实现从后向前遍历 encoding记录了当前节点实际数据的「类型和长度」类型主要有两种字符串和整数。 data记录了当前节点的实际数据类型和长度都由 encoding 决定 当我们往压缩列表中插入数据时压缩列表就会根据数据类型是字符串还是整数以及数据的大小会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息这种根据数据大小和类型进行不同的空间大小分配的设计思想正是 Redis 为了节省内存而采用的。 分别说下prevlen 和 encoding 是如何根据数据的大小和类型来进行不同的空间大小分配。 压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」而且 prevlen 属性的空间大小跟前一个节点长度值有关比如 如果前一个节点的长度小于 254 字节那么 prevlen 属性需要用 1 字节的空间来保存这个长度值 如果前一个节点的长度大于等于 254 字节那么 prevlen 属性需要用 5 字节的空间来保存这个长度值 encoding 属性的空间大小跟数据是字符串还是整数以及字符串的长度有关如下图下图中的 content 表示的是实际数据即本文的 data 字段 如果当前节点的数据是整数则 encoding 会使用 1 字节的空间进行编码也就是 encoding 长度为 1 字节。通过 encoding 确认了整数类型就可以确认整数数据的实际大小了比如如果 encoding 编码确认了数据是 int16 整数那么 data 的长度就是 int16 的大小。 如果当前节点的数据是字符串根据字符串的长度大小encoding 会使用 1 字节/2字节/5字节的空间进行编码encoding 编码的前两个 bit 表示数据的类型后续的其他 bit 标识字符串数据的实际长度即 data 的长度。
连锁更新
压缩列表除了查找复杂度高的问题还有一个问题。 压缩列表新增某个元素或修改某个元素时如果空间不不够压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时可能会导致后续元素的 prevlen 占用空间都发生变化从而引起「连锁更新」问题导致每个元素的空间都要重新分配造成访问压缩列表性能的下降。 前面提到压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配 ● 如果前一个节点的长度小于 254 字节那么 prevlen 属性需要用 1 字节的空间来保存这个长度值 ● 如果前一个节点的长度大于等于 254 字节那么 prevlen 属性需要用 5 字节的空间来保存这个长度值 现在假设一个压缩列表中有多个连续的、长度在 250253 之间的节点如下图
因为这些节点长度值小于 254 字节所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。 这时如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点即新节点将成为 e1 的前置节点如下图 因为 e1 节点的 prevlen 属性只有 1 个字节大小无法保存新节点的长度此时就需要对压缩列表的空间重分配操作并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。 多米诺牌的效应就此开始。 e1 原本的长度在 250253 之间因为刚才的扩展空间此时 e1 的长度就大于等于 254 了因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。 正如扩展 e1 引发了对 e2 扩展一样扩展 e2 也会引发对 e3 的扩展而扩展 e3 又会引发对 e4 的扩展… 一直持续到结尾。 这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」就像多米诺牌的效应一样第一张牌倒下了推动了第二张牌倒下第二张牌倒下又推动了第三张牌倒下…
压缩列表的缺陷
空间扩展操作也就是重新分配内存因此连锁更新一旦发生就会导致压缩列表占用的内存空间要多次重新分配这就会直接影响到压缩列表的访问性能。 所以说虽然压缩列表紧凑型的内存布局能节省内存开销但是如果保存的元素数量增加了或是元素变大了会导致内存重新分配最糟糕的是会有「连锁更新」的问题。 因此压缩列表只会用于保存的节点数量不多的场景只要节点数量足够小即使发生连锁更新也是能接受的。 虽说如此Redis 针对压缩列表在设计上的不足在后来的版本中新增设计了两种数据结构quicklistRedis 3.2 引入 和 listpackRedis 5.0 引入。这两种数据结构的设计目标就是尽可能地保持压缩列表节省内存的优势同时解决压缩列表的「连锁更新」的问题。
