- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
本文首发于公众号:Hunter后端 原文链接: Redis数据结构三之压缩列表 。
本篇笔记介绍压缩列表.
在 Redis 3.2 版本之前,压缩列表是列表对象、哈希对象、有序集合对象的的底层实现之一.
因为压缩列表本身结构上的一些缺陷,压缩列表这个结构被替换了,但是压缩列表结构本身有一些可取之处,并且替换它的新结构 listpack 与之很相似,所以我们这里还是介绍一下压缩列表的结构和存储 。
压缩列表是 Redis 为了节约内存而开发的,由一个连续内存块组成的顺序型数据结构.
它的组成结构如下:
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend | 。
压缩列表的英文名是 ziplist,所以它的属性都是 zl 开头.
zlbytes 。
zlbytes 长度为 4 字节,记录整个压缩列表占用的内存字节数 。
zltail 。
zltail 长度为 4 字节,记录压缩列表最后一个节点,也就是我们结构示例中的 entryN 到 zlbytes 的地址之间的偏移量.
zllen 。
zllen 长度为 2 字节,记录的是压缩列表包含的节点数量,也就是结构中的 N.
zlend 。
zlend 长度为 1 字节,它的值为 0xFF (十进制 255),用于标记压缩列表的末端.
对于每一个 entry 节点,也就是压缩列表中的元素节点,它的结构示意如下:
| previous_entry_length | encoding | content | 。
previous_entry_length 。
previous_entry_length 属性记录的是压缩列表中前一个节点的长度 。
previous_entry_length 属性本身的长度可以是 1 字节或者 5 字节 。
如果前一节点的长度小于 254 字节,那么 previous_entry_length 属性的长度为 1 字节,前一个节点的长度保存在这个字节里 。
如果前一节点的长度大于等于 254 字节,那么 previous_entry_length 属性的长度为 5 字节,第一个字节被设置成 0xFE(也就是 254),之后的四个字节用于前一节点的长度.
通过 previous_entry_length 属性,我们可以通过当前节点的地址和 previous_entry_length 属性,计算出前一个节点的起始地址,压缩列表的从表尾到表头的遍历操作就是使用这个原理一个节点一个节点往前回溯实现的.
encoding 。
encoding 属性记录了节点的 content 属性所保存数据的类型以及长度.
encoding 的值如果是一字节长,且值的最高位以 11 开头,那么表示是整数编码,表示 content 属性保存着整数值.
encoding 的值为 一字节、两字节、五字节长,且值的最高位为 00、01、10 则表示是字节数组编码 。
content 。
content 属性保存的是节点的值,可以是一个字节数组或者整数,值的类型和长度由节点的 encoding 属性决定.
在压缩列表的节点属性中,previous_entry_length 属性的长度是根据前一节点的长度来进行赋值的,如果前一节点的长度小于 254 字节,那么下一节点的 previous_entry_length 属性长度为 1 字节,如果前一节点的长度大于等于 254 字节,那么下一节点的 previous_entry_length 属性为 5 字节.
那么在这种情况下,就存在一种较为极端的情况,那就是压缩列表中每个节点的长度都在 250 - 253 字节之间,这时候,如果在表头插入一个长度大于等于 254 字节的节点,那么相对应的第二个节点的 previous_entry_length 的长度就要从 1 字节变为 4 字节,那么该节点的整体长度就大于等于 254 字节.
依此类推,压缩列表的每一个节点的长度都会产生连锁反应,长度都会逐个变成大于等于 254 字节长度,程序就需要不断地对压缩列表执行空间重分配的操作.
Redis 将这种在特殊情况下产生的连续多次空间扩展操作称为 连锁更新.
除了新增节点这种情况,还有一种删除节点也可能造成连锁更新的情况,比如有这么几个节点,big 节点的长度大于等于 254 字节,small 节点长度小于254 字节,e1 到 eN 的节点长度都在 250-253 字节之间.
| zlbytes | zltail | zllen | big | small | entry1 | entry2 | ... | entryN | zlend | 。
这时候,删除 small 节点,entry1 节点的前节点的长度就会从 250-253 变成大于等于 254,因此 entry1 节点的 previous_entry_length 长度就会变成 5 字节,entry1 整体长度就会大于等于 254 字节,依次之后每个节点都会这样产生连锁更新.
尽管连锁更新的复杂度较高,但它真正造成性能问题的几率是很低的:
首先,压缩列表里要恰好有多个连续的、长度介于 250-253 字节之间的节点,连锁反应才有可能被引发 。
其次,即使出现连锁更新,但只要被更新的节点数量不多,就不会对性能造成任何影响,比如对只拥有三五个节点的压缩列表进行连锁更新.
压缩列表虽然能节约内存,但仍然存在一些缺点:
如果想获取更多后端相关文章,可扫码关注阅读:
最后此篇关于Redis数据结构三之压缩列表的文章就讲到这里了,如果你想了解更多关于Redis数据结构三之压缩列表的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
如标题所示,ans_list是一个答案列表,ans_index是一个数字(答案在词汇表中的索引,但与atm无关) 这里生成的 tree.anslist 是什么? (例如,仅针对第一个),忽略迭代。 f
我目前将用户的输入存储在逗号分隔的列表中,如下所示: Userid | Options 1 | 1,2,5 用户在一个数组形式中勾选一组选项,然后用逗号连接起来 1,2,5 然后 MySQ
我目前将用户的输入存储在逗号分隔的列表中,如下所示: Userid | Options 1 | 1,2,5 用户在一个数组形式中勾选一组选项,然后用逗号连接起来 1,2,5 然后 MySQ
我想知道如何完全展平列表和包含它们的东西。除其他外,我想出了一个解决方案,它可以将具有多个元素的东西滑倒并将它们放回原处,或者在滑倒后将具有一个元素的东西拿走。 这与 How do I “flatte
我想知道如何完全展平列表和包含它们的东西。除其他外,我想出了一个解决方案,它可以将具有多个元素的东西滑倒并将它们放回原处,或者在滑倒后将带有一个元素的东西拿走。 这与 How do I “flatte
这个问题已经有答案了: Convert nested list to 2d array (3 个回答) 已关闭 7 年前。 java中有没有快捷方式可以转换 List> 到 String[][] ?
我在排序时遇到问题 List> 。我创建了一个自定义比较器,在其中编写了对数据进行排序的代码。 public class CustomComparator implements Comparator
这个问题已经有答案了: 已关闭10 年前。 Possible Duplicate: Java Generics: Cannot cast List to List? 我只是想知道为什么下面的java代
试图想出一个 LINQy 方法来做到这一点,但我什么也没想到。 我有一个对象列表<>,其中包含一个属性,该属性是逗号分隔的字母代码列表: lst[0].codes = "AA,BB,DD" lst[1
假设我有这些任务: points = [] point = (1, 2) 我怎么会这样做: points += point 它工作得很好,并且给了我点 = [1, 2]。但是,如果我这样做: poin
如何在 scala 中将 List[Task[List[Header]]] 类型转换为 Task[List[Header]]。 我有一个方法返回 Task[List[Header]] 并多次调用 do
如何在 Java 中查找二维列表的元素? 我有一个参数为 List> 的函数我想知道如何找到这个列表的行和列。 最佳答案 如果你喜欢 List> obj 然后你就可以像这样访问 obj.get(cur
分配 List到 List工作正常。 分配 List>到 List>不编译。 代码 public class Main { public static void main(String[] a
我正在用 Java 编写一个方法,该方法必须接收并迭代 Serializable 的 List。 有什么区别: public void myMethod(List list) { } 和 public
我看到很多人想用 mvvm 更新网格/列表/树的一部分,但他们不想刷新整个列表。 对于所有遇到此问题的人,我做了以下示例。 希望这对你有用。 最佳答案 这是一个简单的例子。整个代码中最重要的是: Bi
我正在为现有的 C++ 库编写包装器,该库使用列表,其中 T 是自定义结构。我被建议使用 vector 而不是列表,但我试图避免修改库。 为了更好地理解这个场景,我做了一个简单的应用程序,使用一个列表
List list List list 这两种声明有什么区别吗? 谢谢, 最佳答案 是的。 List可以包含所有派生自 Base 的不同事物的混合物. List包含同质项(从某种意义上说,它们必须全部
有人可以尽可能详细地解释以下类型之间的区别吗? List List List 让我更具体一点。我什么时候想使用 // 1 public void CanYouGiveMeAnAnswer(List l
我有一个元组列表,每个元组都是一对列表。所以我的数据看起来像: mylist = [(['foo', 'bar'], ['bar', 'bar']),(['bar', 'bar'],['bar', '
也许是一个时髦的标题,但我遇到了以下问题: 给定一个类型为 (a * b) list 的列表,我想创建一个类型为 (a * b list) list 的新列表。一个例子: 给定列表 let testL
我是一名优秀的程序员,十分优秀!