个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
29
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章redis源码分析教程之压缩链表ziplist详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
前言 。
压缩列表（ziplist）是由一系列特殊编码的内存块构成的列表，它对于Redis的数据存储优化有着非常重要的作用。这篇文章总结一下redis中使用非常多的一个数据结构压缩链表ziplist。该数据结构在redis中说是无处不在也毫不过分，除了链表以外，很多其他数据结构也是用它进行过渡的，比如前面文章提到的SortedSet。下面话不多说了，来一起看看详细的介绍吧.
1、压缩链表ziplist数据结构简介 。
首先从整体上看下ziplist的结构，如下图:
压缩链表ziplist结构图 。
可以看出字段很多，字节大小也不同，但这也就是压缩链表的精髓所在了，我们依次总结一下.
。
| 字段 | 含义 |
|---|---|
| zlbytes | 该字段是压缩链表的第一个字段，是无符号整型，占用4个字节。用于表示整个压缩链表占用的字节数（包括它自己）。 |
| zltail | 无符号整型，占用4个字节。用于存储从压缩链表头部到最后一个entry（不是尾元素zlend）的偏移量，在快速跳转到链表尾部的场景使用。 |
| zllen | 无符号整型，占用2个字节。用于存储压缩链表中包含的entry总数。 |
| zlend | 特殊的entry，用来表示压缩链表的末尾。占用一个字节，值恒为255。 |
。
总结为ziplist的头跟尾，下面再总结一下重中之重的entry字段.
一般来说，一个entry由prevlen，encoding，entry-data三个字段组成，但当entry是个很小的整数时，会根据编码省略掉entry-data字段。下面依次进行总结:
首先是字段prevlen：表示前一个entry的长度，有两种编码方式.
然后是字段encoding：它会根据当前元素内容的不同会采用不同的编码方式，如下:
1、如果元素内容为字符串，encoding的值分别为:
00xx xxxx ：00开头表示该字符串的长度用6个bit表示.
01xx xxxx | xxxx xxxx ：01开头表示字符串的长度由14bit表示，这14个bit采用大端存储.
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10开头表示后续的四个字节为字符串长度，这32个bit采用大端存储.
2、如果元素内容为数字，encoding的值分别为:
1100 0000：表示数字占用后面2个字节.
1101 0000：表示数字占用后面4个字节.
1110 0000：表示数字占用后面8个字节.
1111 0000 ：表示数字占用后面3个字节.
1111 1110 ：表示数字占用后面1个字节.
1111 1111 ：表示压缩链表中最后一个元素（特殊编码）.
1111 xxxx ：表示只用后4位表示0~12的整数，由于0000，1110跟1111三种已经被占用，也就是说这里的xxxx四位只能表示0001~1101，转换成十进制就是数字1~13，但是redis规定它用来表示0~12，因此当遇到这个编码时，我们需要取出后四位然后减1来得到正确的值.
最后是字段entry-data：如果元素的值为字符串，则保存元素本身的值。如果元素的值为很小的数字（按上面编码规则即0~12），则没有该字段.
压缩链表的编码非常复杂，但这也正是该数据结构的精髓所在，一起来看一个例子吧:
注：这个例子是redis源码中提到的 。
|
1
2
3
4
5
6
|
//由元素2，5组成的压缩链表
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
| | | | | |
zlbytes zltail entries "2" "5" end
//字符串"Hello World"编码后的内容
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
|
上面是一段用十六进制表示2，5两个元素组成的压缩链表.
接下来我们在这个压缩链表末尾插入一个字符串元素Hello World，先看看该如何编码该字符串，按照约定的编码规则，首先要用字节表示前一个元素的长度，这里前一个元素时5，总共占用了两个字节，因此首先用一个字节表示前一个元素的长度02，接下来是字符串的编码，我们要加入的字符串长度为11（空格也算），转换成二进制就是1011，按照字符串的编码规则，使用0000 1011表示，转为十六进制就是0b，最后再加上我们字符串本身的ASCII码，综合起来就得出该字符串的编码：[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64].
此时整个压缩链表就变为:
|
1
2
3
|
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 48 65 6c 6c 6f 20 57 6f 72 6c 64] [ff]
| | | | | | |
zlbytes zltail entries "2" "5" "Hello World" end
|
2、压缩链表ziplist命令源码分析 。
搞明白上面的编码规则以后，我们再来看下压缩链表ziplist的部分操作源码，本文就创建压缩链表，插入元素，删除元素，查找元素四个操作来总结一下压缩链表的基本原理.
首先是创建:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//定义由zlbytes，zltail跟zllen组成的压缩链表的头大小
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*
2
+sizeof(uint16_t))
//创建一个压缩链表，并且返回指向该链表的指针
unsigned
char
*ziplistNew(
void
) {
//这里之所以+1是因为尾元素占用一个字节，这也是一个压缩链表最小尺寸
unsigned
int
bytes = ZIPLIST_HEADER_SIZE+
1
;
//分配内存
unsigned
char
*zl = zmalloc(bytes);
//设置链表大小
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//设置最后一个元素的偏移量
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//设置元素个数
ZIPLIST_LENGTH(zl) =
0
;
//设置尾元素（上面只是申请空间）
zl[bytes-
1
] = ZIP_END;
return
zl;
}
|
创建压缩链表的逻辑很简单，就是申请固定的包含头尾节点的空间，然后初始化链表上下文.
与创建相比，添加元素的源码就非常冗长了，为了便于理解，在看源码之前我们先自己梳理一下添加元素的逻辑.
上面三步是核心步骤，其余的还有更新尾节点偏移量，修改链表元素个数等操作。当然，由于压缩链表是基于数组实现的，因此在插入或删除元素的时候内存拷贝也是必不可少的.
总结好上面的步骤以后，我们开始一步一步分析源码，比较长，慢慢看:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
//四个参数依次是：压缩链表，插入位置（新元素插入p元素后面），元素值，元素长度
unsigned
char
*__ziplistInsert(unsigned
char
*zl, unsigned
char
*p, unsigned
char
*s, unsigned
int
slen) {
//这里是保存当前链表的长度
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned
int
prevlensize, prevlen =
0
;
size_t offset;
int
nextdiff =
0
;
unsigned
char
encoding =
0
;
long
long
value =
123456789
;
zlentry tail;
//1. 这段逻辑目的就是获取前置元素的长度
if
(p[
0
] != ZIP_END) {
//如果插入位置的元素不是尾元素,则获取该元素的长度
//这里为了后面使用方便进行了拆分，prevlensize保存encoding字段的长度，prevlen保存元素本身的长度
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
}
else
{
//如果插入位置的元素是尾元素，那么需要把新元素插入链表尾端
//获取到链表最后一个元素（注：最后一个元素不等于尾元素）
unsigned
char
*ptail = ZIPLIST_ENTRY_TAIL(zl);
if
(ptail[
0
] != ZIP_END) {
//如果最后一个元素不是尾元素，则该元素为新元素的前置元素，获取该元素长度
prevlen = zipRawEntryLength(ptail);
}
//否则说明链表还没有任何元素，即新元素的前置元素长度为0
}
//2. 对新元素进行编码，获取新元素的总大小
if
(zipTryEncoding(s,slen,&value,&encoding)) {
//如果是数字，则按数字进行编码
reqlen = zipIntSize(encoding);
}
else
{
//元素长度即为字符串长度
reqlen = slen;
}
//新元素总长度为值的长度加上前置元素跟encoding元素的长度
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//如果插入的位置不是链表尾，则要对新元素的后续元素的prevlen字段进行判断
//根据上面的编码规则，该字段可能需要扩容
int
forcelarge =
0
;
nextdiff = (p[
0
] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) :
0
;
if
(nextdiff == -
4
&& reqlen <
4
) {
nextdiff =
0
;
forcelarge =
1
;
}
//按照新计算出的数组大小进行扩容，由于新数组的地址可能会改变，因此这里记录旧的偏移量
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//在新数组上计算插入位置
p = zl+offset;
//如果新插入的元素不是在链表末尾
if
(p[
0
] != ZIP_END) {
//把新元素后继元素复制到新的数组中，-1为尾元素
memmove(p+reqlen,p-nextdiff,curlen-offset-
1
+nextdiff);
//新元素的后继元素的prevlen字段
if
(forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//更新最后一个元素的偏移量
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//当新元素的后继元素不止有一个时，新的尾元素偏移量需要加上nextdiff
zipEntry(p+reqlen, &tail);
if
(p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
}
else
{
//新元素插入到链表尾端，更新尾端偏移量
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff !=0表示后继元素的长度发生变化，因此我们需要级联更新后继元素的后继元素
if
(nextdiff !=
0
) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
//把新元素写入链表
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if
(ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
}
else
{
zipSaveInteger(p,value,encoding);
}
//压缩链表存储元素数量+1
ZIPLIST_INCR_LENGTH(zl,
1
);
return
zl;
}
|
分析完插入元素的逻辑，长舒一口气，真的很长，细节也很多.
接下来在再看下删除元素的过程，与添加相比，删除相对要简单一些，清空当前元素以后，需要把后继元素一个一个拷贝上来（这也是数组跟链表两个数据结构的差别），然后注意是否需要级联更新，上代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
//参数依次为：压缩链表，删除元素的其实位置，删除元素的个数
unsigned
char
*__ziplistDelete(unsigned
char
*zl, unsigned
char
*p, unsigned
int
num) {
unsigned
int
i, totlen, deleted =
0
;
size_t offset;
int
nextdiff =
0
;
zlentry first, tail;
//读取p指向的元素保存在first中
zipEntry(p, &first);
for
(i =
0
; p[
0
] != ZIP_END && i < num; i++) {
//统计总共删除的长度
p += zipRawEntryLength(p);
//统计实际删除元素的个数
deleted++;
}
//需要删除元素的字节数
totlen = p-first.p;
if
(totlen >
0
) {
if
(p[
0
] != ZIP_END) {
//判断元素大小是否有改变
nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
//修改删除元素之后的元素的prevlen字段
p -= nextdiff;
zipStorePrevEntryLength(p,first.prevrawlen);
//更新末尾元素的偏移量
ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//当删除元素的后继元素不止有一个时，新的末尾元素偏移量需要加上nextdiff
zipEntry(p, &tail);
if
(p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//把后面剩余的元素移动至前面
memmove(first.p,p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-
1
);
}
else
{
//直接删除到链表末尾，因此不需要内存拷贝，只需修改最后一个元素的偏移量
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//resize数组大小
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//修改链表元素个数
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0表示元素大小发生变化，需要进行级联更新
if
(nextdiff !=
0
)
zl = __ziplistCascadeUpdate(zl,p);
}
return
zl;
}
|
最后我们看下元素的查找操作:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
//参数依次为：压缩链表，要查找元素的值，要查找元素的长度，每次比较之间跳过的元素个数
unsigned
char
*ziplistFind(unsigned
char
*p, unsigned
char
*vstr, unsigned
int
vlen, unsigned
int
skip) {
int
skipcnt =
0
;
unsigned
char
vencoding =
0
;
long
long
vll =
0
;
//只要还没到尾元素就不断循环
while
(p[
0
] != ZIP_END) {
unsigned
int
prevlensize, encoding, lensize, len;
unsigned
char
*q;
//查询链表当前元素的prevlen字段
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//查询链表当前元素的encoding字段
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
//已到达需要比较的元素位置
if
(skipcnt ==
0
) {
//如果链表中的当前元素时字符串
if
(ZIP_IS_STR(encoding)) {
//跟要查找的字符串进行比较
if
(len == vlen && memcmp(q, vstr, vlen) ==
0
) {
//匹配成功，则要查找元素的指针
return
p;
}
}
else
{
//如果当前元素为数字且vencoding为0
if
(vencoding ==
0
) {
//尝试对要查找的值进行数字编码
if
(!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
//如果编码失败，则说明要查找的元素根本不是数字
//然后把vencoding设置为最大值，起一个标记作用
//也就是说后面就不用尝试把要查找的值编码成数字了
vencoding = UCHAR_MAX;
}
assert
(vencoding);
}
//如果vencoding != UCHAR_MAX，则说明要查找的元素成功编码为数字
if
(vencoding != UCHAR_MAX) {
//按数字取出当前链表中的元素
long
long
ll = zipLoadInteger(q, encoding);
if
(ll == vll) {
//如果两个数字相等，则返回元素指针
return
p;
}
}
}
//重置需要跳过的元素个数
skipcnt = skip;
}
else
{
//跳过元素
skipcnt--;
}
//遍历下个元素
p = q + len;
}
//遍历完整个链表，没有找到元素
return
NULL;
}
|
到这里就把压缩链表的创建，添加，删除，查找四个基本操作原理总结完了.
3、压缩链表ziplist数据结构总结 。
压缩链表ziplist在redis中的应用非常广泛，它算是redis中最具特色的数据结构了。该数据结构的精髓其实就在于文章第一部分总结的编码规则，先理清楚这部分内容，后面的源码可以简单看下加深理解.
不得不说源码部分着实有点冗长，确实需要耐心，我自己在读的过程中也很头大。如果对源码感兴趣的话，建议按我的方法，先自己梳理某个操作（例如上面提到的插入元素）需要做哪些事情，然后再看代码可能会更好理解一些.
最后留一个小问题，既然redis中的ziplist对内存利用率如此之高，那为什么还要提供普通的链表结构供用户使用呢？ 这个问题没有标准答案，仁者见仁智者见智吧~ 。
总结 。
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对我的支持.
原文链接：http://www.jianshu.com/p/565795f43eed 。
最后此篇关于redis源码分析教程之压缩链表ziplist详解的文章就讲到这里了,如果你想了解更多关于redis源码分析教程之压缩链表ziplist详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
29
4
0
ACO.Visualization项目 本项目演示蚁群算法求解旅行商问题的可视化过程，包括路径上的信息素浓度、蚁群的运动过程等。项目相关的代码：https://github.com/anycad/A
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题，以便用事实和引用来回答。 关闭 7 年前。
我需要用Sql数据库制作并包含的PHP票务系统源码用户客户端和管理员。我需要个人 CMS 的这个来源。谢谢你帮助我。 最佳答案 我在不同的情况下使用了 osticket。 这里: http://ost
我的场景:我想在日志文件中写入发生异常的部分代码(例如，发生异常的行前 5 行和行后 5 行 - 或者至少是该方法的所有代码)。 我的想法是用 C# 代码反编译 pdb 文件，并从该反编译文件中找到一
RocketMQ设定了延迟级别可以让消息延迟消费，延迟消息会使用 SCHEDULE_TOPIC_XXXX 这个主题，每个延迟等级对应一个消息队列，并且与普通消息一样，会保存每个消息队列的消费进度
先附上Hystrix源码图 在微服务架构中，根据业务来拆分成一个个的服务，服务与服务之间可以相互调用（RPC），在Spring Cloud可以用RestTemplate+Ribbon和
此篇博客学习的api如标题，分别是： current_url 获取当前页面的url； page_source 获取当前页面的源码； title 获取当前页面的titl
? 1 2
1、前言 作为一个数据库爱好者，自己动手写过简单的sql解析器以及存储引擎，但感觉还是不够过瘾。<<事务处理-概念与技术>>诚然讲的非常透彻，但只能提纲挈领，不能让你
gory"> 目录 运行时信号量机制 semaphore 前言 作用是什么 几个主要的方法 如何实现
自己写的一个评论系统源码分享给大家，包括有表情，还有评论机制。用户名是随机的 针对某一篇文章进行评论 function subcomment() {
一、概述 StringBuilder是一个可变的字符串序列，这个类被设计去兼容StringBuffer类的API，但不保证线程安全性，是StringBuffer单线程情况下的一个替代实现。在可能的情
一、概述 System是用的非常多的一个final类。它不能被实例化。System类提供了标准的输入输出和错误输出流；访问外部定义的属性和环境变量；加载文件和库的方法；以及高效的拷贝数组中一部分元素
在JDK中，String的使用频率和被研究的程度都非常高，所以接下来我只说一些比较重要的内容。 一、String类的概述 String类的声明如下： public final class Str
一、概述 Class的实例代表着正在运行的Java应用程序的类和接口。枚举是一种类，而直接是一种接口。每一个数组也属于一个类，这个类b被反射为具有相同元素类型和维数的所有数组共享的类对象。八大基本树
一、概述 Compiler这个类被用于支持Java到本地代码编译器和相关服务。在设计上，这个类啥也不做，他充当JIT编译器实现的占位符。 放JVM虚拟机首次启动时，他确定系统属性java.comp
一、概述 StringBuffer是一个线程安全的、可变的字符序列，跟String类似，但它能被修改。StringBuffer在多线程环境下可以很安全地被使用，因为它的方法都是通过synchroni
一、概述 Enum是所有Jav中枚举类的基类。详细的介绍在Java语言规范中有说明。 值得注意的是，java.util.EnumSet和java.util.EnumMap是Enum的两个高效实现，
一、概述 此线程指的是执行程序中的线程。 Java虚拟机允许应用程序同时执行多个执行线程。 每个线程都有优先权。 具有较高优先级的线程优先于优先级较低的线程执行。 每个线程可能也可能不会被标记为守
一、抽象类Number 类继承关系 这里面的原子类、BigDecimal后面都会详细介绍。 属性和抽象方法 二、概述 所有的属性，最小-128，最大127，SIZE和BYTES代码比
我是一名优秀的程序员,十分优秀！