《Redis设计与实现》读书笔记(六) ——Redis中的压缩列表

《Redis设计与实现》读书笔记(六) ——Redis中的压缩列表

(原创内容,转载请注明来源,谢谢)

一、概述

压缩列表(ziplist)是列表键(list)和哈希键(hash)底层的实现之一。当列表项较少,且每项要么是小的整数值,要么是长度比较短的字符串,则使用ziplist。当哈希的键值对较少,且每个键值对都是小整数或短字符串,也是使用ziplist。

二、压缩列表构成

压缩列表是redis为了节约内存开发的,由一系列特殊编码的连续内存块组成的顺序型数据结构。每个压缩列表有多个节点(entry),节点可以保存一个字节数组或者整数值。

压缩列表各个组成部分,如下图所示:

1)zlbytes:uint32_t类型,4个字节,记录整个ziplist占字节数,当对ziplist内存重分配,或者计算zlend时使用。

2)zltail:uint32_t类型,4个字节,记录表尾节点(entry)距离表头节点(entry)多少字节,通过此偏移量,不用遍历表就可以确定表尾节点位置。

3)zllen:uint16_t类型,2个字节,记录ziplist包含的节点(entry)数量,当该值小于65535时,其值就是节点数量,但是当其大于该值,则要遍历表才可以知道节点真实数量。

4)entryX:列表节点类型,长度不确定。每个entry是压缩列表的节点,长度由其保存的内容确定。

5)zlend:uint8_t类型,1个字节,特殊值0xFF(十进制255),标记ziplist的结尾。

压缩列表实例如下图所示:

0x50是十进制的80,即该ziplist80字节,节点的头和尾的距离是0x3C(十进制60),长度是3(3个节点)。

三、压缩列表节点构成

1、节点成份

压缩列表节点可以保存一个字节数组或者一个整数。

1)字节数组

长度小于等于26-1、214-1、232-1字节的字节数组均可。

2)整数

4位长且0~12之间的无符号整数、1字节的有符号整数、3字节的有符号整数、uint16_t、uint32_t、uint64_t的整数。

每个节点都是由previous_entry_length、encoding、content三部分组成。

如下图所示:

2、previous_entry_length

字节的previous_entry_length属性,以字节为单位,记录ziplist中前一个节点的长度。该属性的长度是1字节或5字节。

当前一个节点长度小于254字节,则该属性是1字节;如果前一个节点大于254,则该属性是5字节,第一字节是0xFE(十进制254),后面四个字节用于表示前一节点长度。

如前一节点长度是5字节,则previous_entry_length=0x05;前一节点的长度是10086字节,则previous_entry_length=0xFE00002766(后面8位才是表示真实的长度)。

previous_entry_length属性用于计算出该节点前一个节点的内存位置,以便于从表尾向表头进行遍历。

3、encoding

encoding记录了节点content的属性所保存的类型和长度。下表中的下划线_表示留空,a、b、x表示实际的二进制(0或1都可以)。

1)1字节长,以11开头的值,是整数编码。除掉开头的11,剩下的6位表示的10进制的值,用于表示整数的类型和长度。

如下表所示:

2)1、2、5字节长,以00、01、10开头的值,表示字节数组编码。除掉开头的两个数字,剩余的数字表示的值,用于表示字节数组的类型和长度。

如下表所示:

4、content

content保存节点具体的值,可以是一个字节数组或者一个整数,值的类型和长度由上面的encoding决定。

如encoding=00001011(表示长度是11的字节数组),则content可以是“helloworld”;encoding=11000000(表示int16_t类型整数),则content可以是10086。

四、连锁更新

考虑到一种特殊情况,ziplist中有多个连续的、长度在250~253字节的节点e1~eN,则所有节点的previous_entry_length属性都是1字节。

此时,将一个大于254字节的节点插入到e1之前,则e1的previous_entry_length需要扩充到5字节。

而这样会造成一个麻烦,此时由于e1增加了4个字节,导致其从250~253字节变成了254~257字节,则e2的previous_entry_length也需要扩充到5字节。这样的更新会一直连锁到eN为止。

上述情况称为连锁更新(cascadeupdate)。除了新增,删除节点也有可能导致连锁更新。

连锁更新的最坏情况下对ziplist进行N次空间重分配,每次重分配最坏的复杂度是O(N),所以连锁更新的时间复杂度是O(N2)。

虽然如此,但是由于多个连续节点长度都在250~253字节出现的情况很少,而部分连续节点的更新也不会耗很多时间,因而ziplist的效率仍然很高。

——written by linhxx 2017.08.31

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏破晓之歌

JS 事件绑定、事件监听、事件委托详细介绍 转

在JavaScript的学习中,我们经常会遇到JavaScript的事件机制,例如,事件绑定、事件监听、事件委托(事件代理)等。这些名词是什么意思呢,有什么作用...

773
来自专栏逻辑熊猫带你玩Python

Python | 6大数据类型方法归纳总结(上)

在Python 3里,只有一种整数类型 int,表示为长整型,没有 python2 中的 Long。

834
来自专栏老马寒门IT

02-老马jQuery教程-jQuery事件处理

在DOM中DOM0级绑定事件的方式是直接给事件属性赋值,但是这样有个缺点就是每次指定的事件处理程序会把之前的覆盖掉。

2020
来自专栏无所事事者爱嘲笑

vue要点记录(待更新)

1233
来自专栏JetpropelledSnake

Python入门之函数的形式参数与实参/参数的具体使用方法

 本篇目录:     一、 函数参数之形式参数与实参     二、 函数参数的具体使用 #1、位置参数:按照从左到右的顺序定义的参数 位置形参:...

4086
来自专栏运维小白

9.4sed(上)

sed工具 sed -n '5'p test.txt sed -n '1,5'p test.txt sed -n '1,$'p test.txt sed -n ...

1748
来自专栏Pythonista

python内建函数

abs()函数返回数字(可为普通型、长整型或浮点型)的绝对值。如果给出复数,返回值就是该复数的模。例如:

811
来自专栏彭湖湾的编程世界

【数据结构】实现字典API:有序数组和无序链表

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

2665
来自专栏前端儿

Array 数组常用方法

Array.join()方法将数组中所有元素都转化为字符串并连接在一起,返回最后生成的字符串。可以自己指定分隔的符号,如果不指定,默认使用逗号

761
来自专栏Bingo的深度学习杂货店

Python3 编程注意点

整除 3//2 数字转字符串 str(number),字符串转数字 int(str) 字符串所有方法不修改字符串本身 .title() .upper() .l...

3225

扫码关注云+社区