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

相关文章

来自专栏Java 源码分析

数据结构Queue

​ 栈和队列其实是相同的,只是名字不一样 入栈换成了入队(enqueue),出栈换成了出队(dequeue)。语义 是不同的。入队操作向队尾添加元素,而出...

2475
来自专栏开发技术

排序之快速排序(上)

希尔排序相当于直接插入排序的优化,它们同属于插入排序类,堆排序相当于简单选择排序的优化,它们同属于选择排序类。而快速排序其实就是冒泡排序的升级,它们都属于交换...

573
来自专栏我的博客

字符串相关知识集锦

常用函数 1.数据库安全方面 addslashes — 使用反斜线引用字符串,返回字符串,该字符串为了数据库查询语句等的需要在某些字符前加上了反斜线。这些字符...

3277
来自专栏Golang语言社区

Python基本运算符

什么是操作符? 简单的回答可以使用表达式4 + 5等于9,在这里4和5被称为操作数,+被称为操符。 Python语言支持操作者有以下几种类型。 算术运算符 比较...

3487
来自专栏书山有路勤为径

词语模式_哈希表

已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符 串str中的单词与pattern中的字符一一对应...

674
来自专栏Python小屋

详解Python函数式编程之map、reduce、filter

map()、reduce()、filter()是Python中很常用的几个函数,也是Python支持函数式编程的重要体现。不过,在Python 3.x中,red...

3106
来自专栏王亚昌的专栏

printf格式控制符[备忘]

(1)输出格式控制综述:     printf的格式控制的完整格式:%  -  0  m.n  l或h     ①%:格式说明的起始符号,不可缺少。   ...

672
来自专栏猿人谷

运算符优先级

优先级 运算符 名称或含义 使用形式 结合方向 说明 1 [] 数组下标 数组名[常量表达式]...

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

【算法】堆排序学习笔记

参考资料 《算法(第4版)》          — — Robert Sedgewick, Kevin Wayne 什么是二叉堆 在了解堆排序之前, 最重要的当...

2098
来自专栏轮子工厂

快速搞定8大排序算法

862

扫描关注云+社区