《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 条评论
登录 后参与评论

相关文章

来自专栏测试开发架构之路

C语言之函数

  结构化程序设计主张按功能来分析需求,主要原则自顶向下,逐步求精,模块化等。 主张按功能把软件系统逐步细分,每个功能都负责对数据进行一次处理,每个功能接收一些...

3414
来自专栏web前端

Vuejs --04 计算属性

一、使用原因      1、模板中表达式很便利,但实际上只适用于简单的运算,不适宜放入太多逻辑运算,例如: <div id="example"> {{ mess...

2007
来自专栏null的专栏

挑战数据结构与算法面试题——统计上排数在下排出现的次数

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 本题应该是一个确定的问题,即上排的是个数是题目中给定的...

3136
来自专栏吾爱乐享

java之学习vector类的特有功能

1242
来自专栏Python爬虫与数据挖掘

Python正则表达式初识(五)

正则表达式的内容很丰富,今天小编继续给大家分享Python正则表达式的基础知识。今天要给大家的讲的特殊字符是竖线“|”。竖线“|”实质上是一个或的关系。

712
来自专栏cs

xml基本知识点

xml, Extensible Markup Language,可扩展的标记语言。 ? xml文档结构.jpg xml文档的规则 1.0 xml文档必须以一个...

3325
来自专栏五分钟学算法

看完这个你还不会 插入排序 么

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

933
来自专栏进击的君君的前端之路

面向对象、this

1173
来自专栏nimomeng的自我进阶

Block官方文档

a) 像函数一样有定义好的参数 b) 有返回值 c) 能从定义的作用域中捕获状态(值) d) ...

1012
来自专栏开发与安全

从零开始学C++之从C到C++(一):const与#define、结构体对齐、函数重载name mangling、new/delete 等

一、bool 类型 逻辑型也称布尔型,其取值为true(逻辑真)和false(逻辑假),存储字节数在不同编译系统中可能有所不同,VC++中为1个字节。 声明方式...

1840

扫码关注云+社区