对象编码Redis底层使用ziplist、skiplist和quicklist三种list结构实现相关对象。顾名思义，ziplist更节省空间，skiplist注重搜索效率，quicklist牺牲空间和时间。在典型的双向链表中，我们有称为节点的结构，它代表列表中的每个值。每个节点都具有三个属性：指向列表中上一个和下一个节点的指针，以及指向节点中字符串的指针。而每个值字符串值实际上存储为三个部分：一个表示长度的整数，一个表示剩余空闲字节数的整数，以及字符串本身后跟一个空字符。可以看出，链表中的每一项都占据了一块独立的内存，各项之间通过地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，地址指针也会额外占用内存。这就是普通链表的内存浪费问题。另外，在普通链表中进行随机查找操作时，其时间复杂度为O(n)，这对于注重效率的Redis来说也是无法接受的。这是普通链表查找效率太低的问题。针对以上两个问题，Redis设计了ziplist（压缩列表）、skiplist（跳跃列表）和快速链表进行相关优化。1ziplist对于ziplist来说，它需要解决的是内存浪费的问题。也就是说，它的设计目标是节省空间，提高存储效率。基于此，Redis对它进行了特殊的设计，使其成为一个经过特殊编码的双向链表。将表中的每一项存储在一个连续的地址空间中，一个ziplist整体占用一大块内存。它是列表（list），但不是链表（linkedlist）。另外，为了在细节上节省内存，ziplist对值的存储采用了变长编码的方式，大致意思就是对于大的整数，多用一些字节来存储，而对于小的整数，则少用一些字节来存储。正是为了这种高效率的存储，ziplist有很多位级的操作，使得代码更加晦涩难懂。不过没关系，我们这一节的目标之一就是了解ziplist相对于普通链表做了哪些优化，可以更好的节省篇幅。接下来，让我们正式了解一下压缩列表的结构。1.1压缩列表的结构一个压缩列表可以包含任意数量的节点（条目），每个节点可以存储一个字节数组或一个整数值。ziplist的各个组成部分如图1-1所示，相关字段说明如下：zlbytes：4个字节，表示ziplist占用的总字节数（包括zlbytes本身占用的4个字节）。zltail：4字节，表示ziplist表中最后一项距离链表起始地址多少字节，即表尾节点的偏移量。通过该字段，程序可以快速确定尾节点的地址。zllen：2个字节：表示ziplist中的节点数。需要注意的是，由于这个字段只有16bit，所以可以表示的最大值是2^16-1。一旦列表节点数超过这个值，就需要遍历整个压缩列表来获取实际的节点数。entry：表示ziplist的节点。长度是可变的，由保存的内容决定。需要注意的是，链表的节点（表项）也有自己的数据结构，后面会详细解释。zlend：ziplist的结束标记，值固定为255，用于标记zip列表的结束。图1-2是一个有五个节点的压缩列表：列表的zlbytes属性值为0xd2（十进制为210），表示压缩列表的总长度为210字节。链表zltail属性的值为0xb3，（十进制179），表示尾节点距链表起始地址179字节。如果链表的起始地址是p，那么指针p+179=entry5的地址。列表zllen属性的值为0x5（十进制5），表示压缩列表包含5个节点。1.2链表节点结构源码如下（ziplist.c）：typedefstructzlentry{unsignedintprevrawlensize,prevrawlen;unsignedintlensize,len;无符号整数标头大小；无符号字符编码；unsignedchar*p;}zlentry;1-3、显示压缩列表节点的结构。prevrawlen：表示前一个节点占用的总字节数。这个字段是为了让ziplist可以前后遍历。encoding：该字段记录了节点的content属性中存储的数据类型。lensize：该字段记录节点保存数据的长度。headersize：该字段记录了节点头的大小。*p：该字段记录指向节点保存内容的指针。1.3压缩链表是如何节省内存的回到我们最初对普通链表的认识。在普通链表中，每个节点包含：一个表示长度的整数和一个表示剩余空闲字节数的整数。字符串本身以空字符结尾。以图1-4为例：图1-4是一个普通链表的三个节点。三个节点中，每个节点实际存储的内容只有1个字节，但是除了实际存储的内容外，它们还需要有：3个指针——占用3个字节2个整数——占用2个字节内容字符串——占用1个空间byteendingnullcharacter-占用1byte由此看来，存储3个字节的数据至少需要21个字节的开销。可见这样的存储效率很低。另一方面，普通链表通过前向和后向指针关联节点，地址不连续。当有多个节点时，容易产生内存碎片，减少内存占用。最后，普通链表对存储单元的操作粒度是字节。这样存储小整数或字符串时，实际上每个字节都有很多空间，这是浪费。就像上面三个节点中用来存储剩余空闲字节的整数一样，实际存储空间只需要1位，但是用1个字节来表示剩余空间的大小，在这个字节中，剩下的7位就浪费掉了.那么，Redis是如何使用ziplist对普通链表进行改造的呢？通过以下两个方面：一方面，ziplist使用一整块连续的内存，避免内存碎片，提高内存利用率。另一方面，ziplist将存储单元的操作粒度从字节降低到比特，有效解决了存储小数据时单个字节浪费比特的问题。2skiplistSkiplist是一种有序的数据结构，通过在每个节点中维护多个指向其他节点的指针来达到快速访问节点的目的。跳表本质上是一种查找结构，用于解决算法中的查找问题。即根据指定的值，快速找到它的位置。此外，我们知道“查找”问题的解决方案通常分为两大类：平衡树和哈希表。有趣的是，skiplist的搜索结构由于其特殊性，不属于上述两类。但在大多数情况下，它的效率与平衡树相当，而且跳表的实现更简单，所以很多程序都使用跳表代替平衡树。本节不介绍跳表的定义和原理。感兴趣的童鞋可以参考这里。知道了跳表是什么以及它有什么作用，接下来我们就来看看如何在redis中实现跳表。在server.h中可以找到skiplist的源码，如下：typedefstructzskiplist{structzskiplistNode*header,*tail;无符号长长度；intlevel;}zskiplist;typedefstructzskiplistNode{robj*obj;双倍分数；结构zskiplistNode*向后；结构zskiplistLevel{结构zskiplistNode*转发;无符号整数跨度；}level[];}zskiplistNode;Redis中的skiplist与普通的skiplist相比，在结构上并没有太大区别，但是在一些细节上有一些区别如下：分数（score）可以重复。也就是说，Redis中的skiplist是允许score字段重复的，而普通的skiplist是不允许重复的。一级链表不是单向链表，而是双向链表。该方法可以倒序获取范围内的元素。比的时候，除了比分数，还要比数据本身。在Redis的skiplist中，数据的内容本身就是数据的唯一标识，而不是score字段的唯一标识。另外，当多个元素得分相同时，也需要根据数据内容进行字典排序。3quicklist对于quicklist，在quicklist.c中有如下描述：Adoublylinkedlistofziplists是一个双向链表，是由ziplist组成的双向链表。相关源代码结构可能在quicklist.h中查找，如下：/*quicklistNode是一个32字节的结构，描述了一个quicklist的ziplist。*我们使用位字段将quicklistNode保持在32字节。*count:16bits,max65536(maxzlbytesis65k,somaxcountactually<32k).*编码：2位，RAW=1，LZF=2。*容器：2位，NONE=1，ZIPLIST=2。*重新压缩：1位，bool，如果节点临时解压缩以供使用，则为真。*attempted_compress:1bit,boolean,用于测试时验证。*额外：12位，免费供将来使用；填充32位的剩余部分*/typedefstructquicklistNode{structquicklistNode*prev;结构quicklistNode*下一个;无符号字符*zl；无符号整数sz；/*以字节为单位的ziplist大小*/unsignedintcount:16;/*ziplist中的项目数*/unsignedintencoding:2;/*RAW==1或LZF==2*/unsignedintcontainer:2;/*NONE==1或ZIPLIST==2*/unsignedintrecompress:1;/*这个节点是之前的压缩包ssed？*/unsignedintattempted_compress:1;/*节点不能压缩；太小*/unsignedintextra:10;/*为将来使用窃取更多位*/}quicklistNode;/*quicklistLZF是一个4+N字节的结构，其中包含“sz”，后跟“compressed”。*'sz'是'compressed'字段的字节长度。*'compressed'是总（压缩）长度为'sz'的LZF数据*注意：未压缩的长度存储在quicklistNode->sz中。*当quicklistNode->zl被压缩时，node->zl指向一个quicklistLZF*/typedefstructquicklistLZF{unsignedintsz;/*LZF大小（以字节为单位）*/charcompressed[];}quicklistLZF;/*quicklist是一个32字节的结构（在64位系统上）描述一个quicklist。*'count'是条目总数。*'len'是快速列表节点的数量。*'compress'是：如果禁用压缩，则为-1，否则它是在quicklist末尾未压缩的quicklistNodes的数量。*'fill'是用户请求的（或默认的lt)填充因子。*/typedefstructquicklist{quicklistNode*head;快速列表节点*尾巴；无符号长计数；/*所有ziplist中所有条目的总数*/unsignedintlen;/*快速列表节点数*/intfill:16;/*单个节点的填充因子*/unsignedintcompress:16;/*结束节点的深度不压缩;0=off*/}quicklist;上面在介绍链表的时候说过，链表是由多个节点组成的，对于quicklist来说，它的每个节点都是一个ziplist。quicklist的设计其实就是我们文章开头说的，是空间和时间的妥协。与普通链表相比，ziplist主要优化了两点：减少内存开销和减少内存碎片。俗话说，事情总是有两个方面的。Ziplist通过连续内存解决了普通链表的内存碎片问题，但同时也带来了新的问题：不利于修改操作。由于ziplist是一整块连续的内存，每次数据变化都会引起内存重新分配。当ziplist非常大时，每次reallocation都会产生大量的数据拷贝操作，降低性能。于是结合了双向链表和ziplist的优点，就有了quicklist。quicklist的基本思想是给每个节点的ziplist分配一个合适的大小，避免因为数据拷贝导致性能下降。这是另一个需要找到平衡点的难题。先分析一下存储效率：每个quicklist节点上的ziplist越短，内存碎片越多。但是，如果内存碎片过多，很可能会产生很多无法利用的小内存碎片，降低存储效率。每个quicklist节点上的ziplist越长，就越难为ziplist分配大块连续内存。可能会出现内存中有很多更小的内存块，但是找不到足够大的空闲空间来分配给ziplist。这也降低了存储效率。可以看出，quicklist节点上的ziplist需要保持一个合理的长度。这里的合理性取决于实际的应用场景。基于此，Redis提供了一个配置参数，可以让用户根据情况进行调整：list-max-ziplist-size-2这个参数可以取正值也可以取负值。当它取正值时，表示每个quicklist节点上的ziplist的长度是根据数据项的数量来限制的。例如配置为2时，表示quicklist的每个节点上的ziplist最多包含2个数据项。当取负值时，表示ziplist在每个quicklist节点上的长度是根据占用的字节数来限制的。此时它的取值范围为[-1,-5]，每个值对应不同的含义：-1：每个quicklist节点上ziplist的大小不能超过4Kb；-2：每个quicklist节点上ziplist的大小不能超过8Kb（默认）；-3：每个quicklist节点上ziplist的大小不能超过16Kb；-4：每个quicklist节点上ziplist的大小不能超过32Kb；-5：每个quicklist节点上ziplist的大小不能超过64Kb以上；总结起来，普通链表存在两个问题：内存利用率低和内存容易碎片化。ziplist使用连续内存，减少内存碎片，提高内存利用率。Skiplist可以实现和平衡树一样的搜索效率，实现相对简单。quicklist吸收了普通链表和压缩链表的优点，在保证性能的前提下尽可能提高内存利用率。
