Redis内部数据结构详解(4)——zi
本篇导读：本文是《Redis内部数据结构详解》系列的第四篇，介绍ziplist。ziplist的操作相对来讲比较复杂，建议本文分两次浏览：先一口气读完ziplist的数据结构的介绍，这一部分基本不包括代码，应当可以在10分钟内读完；然后建议你休息片刻，并将本文收藏。然后在时间充裕的时候再浏览后半部份。祝浏览愉快！
在本文中，我们首先介绍一个新的Redis内部数据结构——ziplist，然后在文章后半部份我们会讨论一下在robj,dict和ziplist的基础上，Redis对外暴露的hash结构是怎样构建起来的。
我们在讨论中还会涉及到两个Redis配置（在nf中的ADVANCEDCONFIG部份）：
hash-max-ziplist-entrieshash-max-ziplist-value64本文的后半部份会对这两个配置做详细的解释。
什么是ziplistRedis官方对ziplist的定义是（出自ziplist.c的文件头部注释）：
storesbothstringsandintegervalues,allowspushandpopoperationsoneithersideofthelistinO(1)time.
翻译一下就是说：ziplist是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效力。ziplist可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供push和pop操作。
实际上，ziplist充分体现了Redis对存储效力的寻求。一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或援用）连接起来。这类方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。而ziplist却是将表中每一项寄存在前后连续的地址空间内，一个ziplist整体占用一大块内存。它是一个表（list），但其实不是一个链表（linkedlist）。
另外，ziplist为了在细节上节省内存，对值的存储采取了变长的编码方式，大概意思是说，对大的整数，就多用一些字节来存储，而对小的整数，就少用一些字节来存储。我们接下来很快就会讨论到这些实现细节。
ziplist的数据结构定义ziplist的数据结构组成是本文要讨论的重点。实际上，ziplist还是略微有点复杂的，它复杂的地方就在于它的数据结构定义。一旦理解了数据结构，它的一些操作也就比较容易理解了。
我们接下来先从总体上介绍一下ziplist的数据结构定义，然后举一个实际的例子，通过例子来解释ziplist的构成。如果你看懂了这一部分，本文的任务就算完成了一大半了。
从宏观上看，ziplist的内存结构以下：
zlbyteszltailzllenentry...entryzlend
各个部份在内存上是前后相邻的，它们分别的含义以下：
zlbytes:32bit，表示ziplist占用的字节总数（也包括zlbytes本身占用的4个字节）。
zltail:32bit，表示ziplist表中最后一项（entry）在ziplist中的偏移字节数。zltail的存在，使得我们可以很方便地找到最后一项（不用遍历全部ziplist），从而可以在ziplist尾端快速地履行push或pop操作。
zllen:16bit，表示ziplist中数据项（entry）的个数。zllen字段由于只有16bit，所以可以表达的最大值为2^。这里需要特别注意的是，如果ziplist中数据项个数超过了16bit能表达的最大值，ziplist依然可以来表示。那怎样表示呢？这里做了这样的规定：如果zllen小于等于2^（也就是不等于2^），那末zllen就表示ziplist中数据项的个数；否则，也就是zllen等于16bit全为1的情况，那末zllen就不表示数据项个数了，这时候要想知道ziplist中数据项总数，那末必须对ziplist从头到尾遍历各个数据项，才能计数出来。
entry:表示真正寄存数据的数据项，长度不定。一个数据项（entry）也有它自己的内部结构，这个稍后再解释。
zlend:ziplist最后1个字节，是一个结束标记，值固定等于。
上面的定义中还值得注意的一点是：zlbytes,zltail,zllen既然占据多个字节，那末在存储的时候就有大端（bigendian）和小端（littleendian）的区分。ziplist采取的是小端模式来存储，这在下面我们介绍具体例子的时候还会再详细解释。
我们再来看一下每个数据项entry的构成：
prevrawlenlendata
我们看到在真正的数据（data）前面，还有两个字段：
prevrawlen:表示前一个数据项占用的总字节数。这个字段的用途是为了让ziplist能够从后向前遍历（从后一项的位置，只需向前偏移prevrawlen个字节，就找到了前一项）。这个字段采取变长编码。
len:表示当前数据项的数据长度（即data部份的长度）。也采取变长编码。
那末prevrawlen和len是怎样进行变长编码的呢？各位读者打起精神了，我们终究讲到了ziplist的定义中最繁琐的地方了。
先说prevrawlen。它有两种可能，或是1个字节，或是5个字节：
如果前一个数据项占用字节数小于，那末prevrawlen就只用一个字节来表示，这个字节的值就是前一个数据项的占用字节数。
如果前一个数据项占用字节数大于等于，那末prevrawlen就用5个字节来表示，其中第1个字节的值是（作为这种情况的一个标记），而后面4个字节组成一个整型值，来真正存储前一个数据项的占用字节数。
有人会问了，为何没有的情况呢？
这是由于：已定义为ziplist结束标记zlend的值了。在ziplist的很多操作的实现中，都会根据数据项的第1个字节是否是来判断当前是否是到达ziplist的结尾了，因此一个正常的数据的第1个字节（也就是prevrawlen的第1个字节）是不能够取这个值的，否则就冲突了。
而len字段就更加复杂了，它根据第1个字节的不同，总共分为9种情况（下面的表示法是按二进制表示）：
00pppppp-1byte。第1个字节最高两个bit是00，那末len字段只有1个字节，剩余的6个bit用来表示长度值，最高可以表示63(2^)。
01pppppp-2bytes。第1个字节最高两个bit是01，那末len字段占2个字节，总共有14个bit用来表示长度值，最高可以表示(2^)。
10__rrrrrrrrsssssssstttttttt-5bytes。第1个字节最高两个bit是10，那末len字段占5个字节，总共使用32个bit来表示长度值（6个bit舍弃不用），最高可以表示2^。需要注意的是：在前3种情况下，data都是按字符串来存储的；从下面第4种情况开始，data开始变成按整数来存储了。
-1byte。len字段占用1个字节，值为0xC0，后面的数据data存储为2个字节的int16_t类型。
-1byte。len字段占用1个字节，值为0xD0，后面的数据data存储为4个字节的int32_t类型。
-1byte。len字段占用1个字节，值为0xE0，后面的数据data存储为8个字节的int64_t类型。
-1byte。len字段占用1个字节，值为0xF0，后面的数据data存储为3个字节长的整数。
-1byte。len字段占用1个字节，值为0xFE，后面的数据data存储为1个字节的整数。
xxxx--(xxxx的值在和之间)。这是一种特殊情况，xxxx从1到13一共13个值，这时候就用这13个值来表示真正的数据。注意，这里是表示真正的数据，而不是数据长度了。也就是说，在这种情况下，后面不再需要一个单独的data字段来表示真正的数据了，而是len和data合二为一了。另外，由于xxxx只能取和这13个值了（其它可能的值和其它情况冲突了，比如和分别同前面第7种第8种情况冲突，跟结束标记冲突），而小数值应当从0开始，因此这13个值分别表示0到12，即xxxx的值减去1才是它所要表示的那个整数数据的值。
好了，ziplist的数据结构定义，我们介绍了完了，现在我们看一个具体的例子。
上图是一份真实的ziplist数据。我们逐项解读一下：
这个ziplist一共包括33个字节。字节编号从byte[0]到byte[32]。图中每一个字节的值使用16进制表示。
头4个字节（0x2）是按小端（littleendian）模式存储的zlbytes字段。什么是小端呢？就是指数据的低字节保存在内存的低地址中（参见维基百科词条Endianness{:target=_blank}）。因此，这里zlbytes的值应当解析成0x，用十进制表示正好就是33。
接下来4个字节（byte[4..7]）是zltail，用小端存储模式来解释，它的值是0xD（值为29），表示最后一个数据项在byte[29]的位置（那个数据项为0x05FE14）。
再接下来2个字节（byte[8..9]），值为0x，表示这个ziplist里一共存有4项数据。
接下来6个字节（byte[10..15]）是第1个数据项。其中，prevrawlen=0，由于它前面没有数据项；len=4，相当于前面定义的9种情况中的第1种，表示后面4个字节按字符串存储数据，数据的值为name。
接下来8个字节（byte[16..23]）是第2个数据项，与前面数据项存储格式类似，存储1个字符串tielei。
接下来5个字节（byte[24..28]）是第3个数据项，与前面数据项存储格式类似，存储1个字符串age。
接下来3个字节（byte[29..31]）是最后一个数据项，它的格式与前面的数据项存储格式不太一样。其中，第1个字节prevrawlen=5，表示前一个数据项占用5个字节；第2个字节=FE，相当于前面定义的9种情况中的第8种，所以后面还有1个字节用来表示真正的数据，并且以整数表示。它的值是20（0x14）。
最后1个字节（byte[32]）表示zlend，是固定的值（0xFF）。
总结一下，这个ziplist里存了4个数据项，分别为：
字符串:name
字符串:tielei
字符串:age
整数:20
（好吧，被你发现了~~tielei实际上固然不是20岁，他哪有那末年轻啊......）
实际上，这个ziplist是通过两个hset命令创建出来的。这个我们后半部份会再提到。
好了，既然你已经浏览到这里了，说明你还是很有耐心的（其实我写到这里也已累得不行了）。可以先把本文收藏，休息一下，回头再看后半部份。
接下来我要贴一些代码了。
ziplist的接口我们先不着急看实现，先来挑几个ziplist的重要的接口，看看它们长甚么模样：
unsignedchar*ziplistNew(void);unsignedchar*ziplistMerge(unsignedchar**first,unsignedchar**second);unsignedchar*ziplistPush(unsignedchar*zl,unsignedchar*s,unsignedintslen,intwhere);unsignedchar*ziplistIndex(unsignedchar*zl,intindex);unsignedchar*ziplistNext(unsignedchar*zl,unsignedchar*p);unsignedchar*ziplistPrev(unsignedchar*zl,unsignedchar*p);unsignedchar*ziplistInsert(unsignedchar*zl,unsignedchar*p,unsignedchar*s,unsignedintslen);unsignedchar*ziplistDelete(unsignedchar*zl,unsignedchar**p);unsignedchar*ziplistFind(unsignedchar*p,unsignedchar*vstr,unsignedintvlen,unsignedintskip);unsignedintziplistLen(unsignedchar*zl);我们从这些接口的名字就可以粗略猜出它们的功能，下面简单解释一下：
ziplist的数据类型，没有用自定义的struct之类的来表达，而就是简单的unsignedchar*。这是由于ziplist本质上就是一块连续内存，内部组成结构又是一个高度动态的设计（变长编码），也没法用一个固定的数据结构来表达。
ziplistNew:创建一个空的ziplist（只包括zlbyteszltailzllenzlend）。
ziplistMerge:将两个ziplist合并成一个新的ziplist。
ziplistPush:在ziplist的头部或尾端插入一段数据（产生一个新的数据项）。注意一下这个接口的返回值，是一个新的ziplist。调用方必须用这里返回的新的ziplist，替换之前传进来的旧的ziplist变量，而经过这个函数处理以后，原来旧的ziplist变量就失效了。为何一个简单的插入操作会致使产生一个新的ziplist呢？这是由于ziplist是一块连续空间，对它的追加操作，会引发内存的realloc，因此ziplist的内存位置可能会产生变化。实际上，我们在之前介绍sds的文章中提到过类似这类接口使用模式（参见sdscatlen函数的说明）。
ziplistIndex:返回index参数指定的数据项的内存位置。index可以是负数，表示从尾端向前进行索引。
ziplistNext和ziplistPrev分别返回一个ziplist中指定数据项p的后一项和前一项。
ziplistInsert:在ziplist的任意数据项前面插入一个新的数据项。
ziplistDelete:删除指定的数据项。
ziplistFind:查找给定的数据（由vstr和vlen指定）。注意它有一个skip参数，表示查找的时候每次比较之间要跳过几个数据项。为何会有这么一个参数呢？其实这个参数的主要用途是当用ziplist表示hash结构的时候，是依照一个field，一个value来顺次存入ziplist的。也就是说，偶数索引的数据项存field，奇数索引的数据项存value。当依照field的值进行查找的时候，就需要把奇数项跳过去。
ziplistLen:计算ziplist的长度（即包括数据项的个数）。
ziplist的插入逻辑解析ziplist的相干接口的具体实现，还是有些复杂的，限于篇幅的缘由，我们这里只结合代码来讲授插入的逻辑。插入是很有代表性的操作，通过这部份来一窥ziplist内部的实现，其它部份的实现我们也就会很容易理解了。
ziplistPush和ziplistInsert都是插入，只是对插入位置的限定不同。它们在内部实现都依赖一个名为__ziplistInsert的内部函数，其代码以下（出自ziplist.c）:
staticunsignedchar*__ziplistInsert(unsignedchar*zl,unsignedchar*p,unsignedchar*s,unsignedintslen){size_tcurlen=intrev32ifbe(ZIPLIST_BYTES(zl)),reqlen;unsignedintprevlensize,prevlen=0;size_toffset;intnextdiff=0;unsignedcharencoding=0;longlongvalue=;zlentrytail;/*Findoutprevlenforthe*entrythatisinserted.*/if(p[0]!=ZIP_END){ZIP_DECODE_PREVLEN(p,prevlensize,prevlen);}else{unsignedchar*ptail=ZIPLIST_ENTRY_TAIL(zl);if(ptail[0]!=ZIP_END){prevlen=zipRawEntryLength(ptail);}}/*Seeiftheentrycanbeencoded*/if(zipTryEncoding(s,slen,value,encoding)){/*encodingissettothe*appropriateintegerencoding*/reqlen=zipIntSize(encoding);}else{/*encodingisuntouched,*howeverzipEncodeLengthwilluse*thestringlengthtofigureout*howtoencodeit.*/reqlen=slen;}/*Weneedspaceforboththelength*ofthepreviousentryand*thelengthofthepayload.*/reqlen+=zipPrevEncodeLength(NULL,prevlen);reqlen+=zipEncodeLength(NULL,encoding,slen);/*Whentheinsertpositionisnot*equaltothetail,weneedto*makesurethatthenextentrycan*holdthisentryslengthin*itsprevlenfield.*/nextdiff=(p[0]!=ZIP_END)?zipPrevLenByteDiff(p,reqlen):0;/*Storeoffsetbecausearealloc*maychangetheaddressofzl.*/offset=p-zl;zl=ziplistResize(zl,curlen+reqlen+nextdiff);p=zl+offset;/*Applymemorymovewhennecessary*andupdatetailoffset.*/if(p[0]!=ZIP_END){/*Subtractonebecauseof*theZIP_ENDbytes*/memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);/*Encodethisentrysraw*lengthinthenextentry.*/zipPrevEncodeLength(p+reqlen,reqlen);/*Updateoffsetfortail*/ZIPLIST_TAIL_OFFSET(zl)=intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);/*Whenthetailcontainsmore*thanoneentry,weneedtotake*nextdiffinaccountaswell.*Otherwise,achangeinthe*sizeofprevlendoesnthavean*effectonthe*tail*offset.*/zipEntry(p+reqlen,tail);if(p[reqlen+adersize+n]!=ZIP_END){ZIPLIST_TAIL_OFFSET(zl)=intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);}}else{/*Thiselementwillbethenewtail.*/ZIPLIST_TAIL_OFFSET(zl)=intrev32ifbe(p-zl);}/*Whennextdiff!=0,theraw*lengthofthenextentryhaschanged,so*weneedtocascadetheupdate*throughouttheziplist*/if(nextdiff!=0){offset=p-zl;zl=__ziplistCascadeUpdate(zl,p+reqlen);p=zl+offset;}/*Writetheentry*/p+=zipPrevEncodeLength(p,prevlen);p+=zipEncodeLength(p,encoding,slen);if(ZIP_IS_STR(encoding)){memcpy(p,s,slen);}else{zipSaveInteger(p,value,encoding);}ZIPLIST_INCR_LENGTH(zl,1);returnzl;}我们来简单解析一下这段代码：
这个函数是在指定的位置p插入1段新的数据，待插入数据的地址指针是s，长度为slen。插入后构成一个新的数据项，占据原来p的配置，原来位于p位置的数据项和后面的所有数据项，需要统一向后移动，给新插入的数据项留出空间。参数p指向的是ziplist中某一个数据项的起始位置，或在向尾端插入的时候，它指向ziplist的结束标记zlend。
函数开始先计算出待插入位置前一个数据项的长度prevlen。这个长度要存入新插入的数据项的prevrawlen字段。
然后计算当前数据项占用的总字节数reqlen，它包括3部份：prevrawlen,len和真正的数据。其中的数据部份会通过调用zipTryEncoding先来尝试转成整数。
由于插入致使的ziplist对内存的新增需求，除待插入数据项占用的reqlen以外，还要斟酌原来p位置的数据项（现在要排在待插入数据项以后）的prevrawlen字段的变化。本来它保存的是前一项的总长度，现在变成了保存当前插入的数据项的总长度。这样它的prevrawlen字段本身需要的存储空间也可能发生变化，这个变化可能是变大也可能是变小。这个变化了多少的值nextdiff，是调用zipPrevLenByteDiff计算出来的。如果变大了，nextdiff是正值，否则是负值。
现在很容易算出来插入后新的ziplist需要多少字节了，然后调用ziplistResize来重新调剂大小。ziplistResize的实现里会调用allocator的zrealloc，它有可能会造成数据拷贝。
现在额外的空间有了，接下来就是将原来p位置的数据项和后面的所有数据都向后移动，并为它设置新的prevrawlen字段。另外，还可能需要调剂ziplist的zltail字段。
最后，组装新的待插入数据项，放在位置p。
hash与ziplisthash是Redis中可以用来存储一个对象结构的比较理想的数据类型。一个对象的各个属性，正好对应一个hash结构的各个field。
我们在上很容易找到这样一些技术文章，它们会说存储一个对象，使用hash比string要节省内存。实际上这么说是有条件的，具体取决于对象怎样来存储。如果你把对象的多个属性存储到多个key上（各个属性值存成string），固然占的内存要多。但如果你采取一些序列化方法，比如ProtocolBuffers，或ApacheThrift，先把对象序列化为字节数组，然后再存入到Redis的string中，那末跟hash相比，哪一种更省内存，就不一定了。
固然，hash比序列化后再存入string的方式，在支持的操作命令上，还是有优势的：它既支持多个field同时存取（hmset/hmget），也支持依照某个特定的field单独存取（hset/hget）。
实际上，hash随着数据的增大，其底层数据结构的实现是会产生变化的，固然存储效力也就不同。在field比较少，各个value值也比较小的时候，hash采取ziplist来实现；而随着field增多和value值增大，hash可能会变成dict来实现。当hash底层变成dict来实现的时候，它的存储效力就没法跟那些序列化方式相比了。
当我们为某个key第一次履行hsetkeyfieldvalue命令的时候，Redis会创建一个hash结构，这个新创建的hash底层就是一个ziplist。
robj*createHashObject(void){unsignedchar*zl=ziplistNew();robj*o=createObject(OBJ_HASH,zl);o-encoding=OBJ_ENCODING_ZIPLIST;returno;}上面的createHashObject函数，出自object.c，它负责的任务就是创建一个新的hash结构。可以看出，它创建了一个type=OBJ_HASH但encoding=OBJ_ENCODING_ZIPLIST的robj对象。
实际上，本文前面给出的那个ziplist实例，就是由以下两个命令构建出来的。
hsetuser:nametieleihsetuser:age20每履行一次hset命令，插入的field和value分别作为一个新的数据项插入到ziplist中（即每次hset产生两个数据项）。
当随着数据的插入，hash底层的这个ziplist就可能会转成dict。那末到底插入多少才会转呢？
还记得本文开头提到的两个Redis配置吗？
hash-max-ziplist-entrieshash-max-ziplist-value64这个配置的意思是说，在以下两个条件之一满足的时候，ziplist会转成dict：
当hash中的数据项（即field-value对）的数目超过的时候，也就是ziplist数据项超过的时候（请参考t_hash.c中的hashTypeSet函数）。
当hash中插入的任意一个value的长度超过了64的时候（请参考t_hash.c中的hashTypeTryConversion函数）。
Redis的hash之所以这样设计，是由于当ziplist变得很大的时候，它有以下几个缺点：
每次插入或修改引发的realloc操作会有更大的几率造成内存拷贝，从而下降性能。
一旦产生内存拷贝，内存拷贝的本钱也相应增加，由于要拷贝更大的一块数据。
当ziplist数据项过量的时候，在它上面查找指定的数据项就会性能变得很低，由于ziplist上的查找需要进行遍历。
总之，ziplist本来就设计为各个数据项挨在一起组成连续的内存空间，这类结构其实不善于做修改操作。一旦数据产生改动，就会引发内存realloc，可能致使内存拷贝。
下一篇我们将介绍quicklist，敬请期待。
好累啊，求鼓励！
赞美
人赞美
北京那家医院专治白癜风北京白癜风医院治疗方法