redis源码阅读ziplist

　　ziplist1。介绍
　　首先是官方介绍：
　　Theziplistisaspeciallyencodedduallylinkedlistthatisdesignedtobeverymemoryefficient。Itstoresbothstringsandintegervalues，whereintegersareencodedasactualintegersinsteadofaseriesofcharacters。ItallowspushandpopoperationsoneithersideofthelistinO（1）time。However，becauseeveryoperationrequiresareallocationofthememoryusedbytheziplist，theactualcomplexityisrelatedtotheamountofmemoryusedbytheziplist。
　　ziplist是一个经过特殊编码的双向链表，旨在提高内存效率。它可以储存字符串和整型值，其中，整型值被编码为实际整数而不是作为字符储存。ziplist可以在O（1）的时间内，在其左侧和右侧进行pop和push操作。但是，实际每个操作都需要重新分配ziplist使用的内存，因此实际的复杂性与ziplist使用的内存量有关。1。1。内存分布
　　每个ziplist占用的内存布局如下：
　　其中，zlbytes是一个无符号整数，表示当前ziplist占用的总字节数。zltail是ziplist最后一个entry的指针相对于ziplist最开始的偏移量。通过它，不需要完全遍历ziplist就可以对最后的entry进行操作。zllen是ziplist的entry数量。当zllen比2162大时，需要完全遍历entry列表来获取entry的总数目。zlend是一个单字节的特殊值，等于255，标识着ziplist的内存结束点。1。2。entry
　　ziplist每个entry都有一个header，header中有两部分内容。第一部分内容是前一个entry的字节数prevrawlen。第二部分内容是该entry的编码encoding，如果是字符串编码，会附带储存其长度len。每一个entry中的结构如下，content为entry实际储存的数据，包括整型和字符串。
　　第一部分中，上一个entry的长度prevrawlen使用如下方式编码：如果其长度小于254字节，entry使用一个字节储存如果其长度大于等于254字节，当前entry使用5个字节。第一个字节设置为254，表示后面的四个字节储存的是上一个entry的长度
　　第二部分信息编码形式encoding取决于当前entry数据类型：如果需要储存的数据是字符串，这部分信息的前两位设置为对应的编码，后续内容储存字符串的长度如果需要储存的数据是整数，这部分信息的前两位设置为11，之后的两位用来确定整数类型。例如：00pppppp1byte
　　长度小于等于63字节的string，后6位储存其长度
　　01ppppppqqqqqqqq2bytes
　　长度小于等于16383字节的string，后14位储存其长度
　　10qqqqqqqqrrrrrrrrsssssssstttttttt5bytes
　　长度大于等于16384字节的string，后32位储存其长度
　　110000001byte
　　Integerencodedasint16t（2bytes）。
　　110100001byte
　　Integerencodedasint32t（4bytes）。
　　111000001byte
　　Integerencodedasint64t（8bytes）。
　　111100001byte
　　Integerencodedas24bitsigned（3bytes）。
　　111111101byte
　　Integerencodedas8bitsigned（1byte）。
　　1111xxxx（withxxxxbetween0000and1101）immediate4bitinteger。
　　xxxx这四位中，0000、1111、1110都不能使用，因此其编码后的值范围为113。
　　11111111Endofziplist。2。函数和宏实现2。1。宏定义
　　redis就是通过一堆宏定义来加速程序执行的。2。1。1。ZIPISSTR（enc）
　　通过entry中的编码enc来判断当前entry中持有的数据类型是不是stringdefineZIPISSTR（enc）（（（enc）ZIPSTRMASK）ZIPSTRMASK）
　　ZIPSTRMASK是0b00110000，将它与enc进行AND操作，如果enc是string类型，那么其前两位应该是00、01或10，因此计算之后的数值应该小于ZIPSTRMASK的。2。1。2。ZIPLISTBYTES（zl）
　　这个宏就是把ziplist最开头的zlbytes提取出来，代码也很简单，通过指针取zl对应的值。defineZIPLISTBYTES（zl）（（（uint32t）（zl）））2。1。3。ZIPLISTTAILOFFSET（zl）
　　这个宏是提取ziplist的zltail内容，它的指针则是对zl偏移一个uint32t大小（zlbytes的长度）获得的。defineZIPLISTTAILOFFSET（zl）（（（uint32t）（（zl）sizeof（uint32t））））2。1。4。ZIPLISTLENGTH（zl）
　　获取zllen的内容，其指针地获取同上，只不过需要偏移两个uint32t的内存大小。defineZIPLISTLENGTH（zl）（（（uint16t）（（zl）sizeof（uint32t）2）））2。1。5。ZIPLISTENTRY相关
　　redis使用三个宏来定位ziplist中entry的首尾位置。
　　首先计算了ziplist中第一个entry到ziplist开头的偏移地址，其实就是zlbytes、zltail和zllen占用的内存大小。defineZIPLISTHEADERSIZE（sizeof（uint32t）2sizeof（uint16t））
　　接下来通过宏获得ziplist第一个entry的指针地址。defineZIPLISTENTRYHEAD（zl）（（zl）ZIPLISTHEADERSIZE）
　　那么ziplist的最后一个entry的指针地址也可以通过2。1。3的宏获得。defineZIPLISTENTRYTAIL（zl）（（zl）intrev32ifbe（ZIPLISTTAILOFFSET（zl）））
　　entry列表的地址边界也可以获得，ziplist最后是一个字节的zlend，因此，zl偏移zlbytes1就可以获得其指针了。defineZIPLISTENTRYEND（zl）（（zl）intrev32ifbe（ZIPLISTBYTES（zl））1）2。1。6。ZIPLISTINCRLENGTH（zl，incr）
　　这个宏用来调整ziplist的entry数量，即zllen。因为ziplist每次只pop或push一个数据，因此这个宏的incr一般为1或1。
　　代码如下，当ZIPLISTLENGTH（zl）大于UINT16MAX时，就已经不再更新zllen了，之后统计ziplist长度就需要进行遍历。defineZIPLISTINCRLENGTH（zl，incr）｛if（ZIPLISTLENGTH（zl）UINT16MAX）ZIPLISTLENGTH（zl）intrev16ifbe（intrev16ifbe（ZIPLISTLENGTH（zl））incr）；｝
　　我当时迷糊了好久，为啥第三行代码ZIPLISTLENGTH（zl）的结果可以直接赋值呢？我翻了好久也没翻出来，突然发现，ZIPLISTLENGTH（zl）是宏定义。它在编译时是将定义的代码直接插入到第三行代码中的，这样就可以进行指针赋值了。2。1。7。ZIPENTRYENCODING（ptr，encoding）
　　这个宏是用来设置entry的encoding字段，具体entry的结构见后续章节。
　　代码如下：defineZIPENTRYENCODING（ptr，encoding）do｛（encoding）（ptr〔0〕）；if（（encoding）ZIPSTRMASK）（encoding）ZIPSTRMASK；｝while（0）
　　代码中第三行，如果encoding小于ZIPSTRMASK（0b11000000），就通过AND操作将encoding后6位设置为0。2。1。8。ZIPDECODELENGTH（ptr，encoding，lensize，len）
　　这个宏的实现目标为：根据encoding设置lensize，即len占用的字节数；根据ptr指向的数据设置len。
　　接下来介绍lensize和len的设置，具体编码参考1。2章的encoding格式：如果encodingZIPSTR06B（0b00000000），它的lensize为1，len即为ptr〔0〕的后六位。如果encodingZIPSTR14B（0b01000000），lensize为2，len为（（ptr〔0〕0x3f）8）ptr〔1〕。如果encodingZIPSTR32B（0b11000000），lensize为5，len为ptr〔1〕ptr〔4〕组成的uint64类型整数。否则的话encoding0b11000000，说明其是数字，则调用zipIntSize（encoding）设置它的len，lensize为1。staticunsignedintzipIntSize（unsignedcharencoding）｛switch（encoding）｛caseZIPINT8B：return1；caseZIPINT16B：return2；caseZIPINT24B：return3；caseZIPINT32B：return4；caseZIPINT64B：return8；default：return0；4bitimmediate｝assert（NULL）；return0；｝2。1。9。ZIPDECODEPREVLENSIZE（ptr，prevlensize）和ZIPDECODEPREVLEN（ptr，prevlensize，prevlen）
　　在1。2章节中，entry会记录上一个entry的大小，如果超过254则使用5个字节来储存其长度，否则只使用1个字节就够了。因此，ZIPDECODEPREVLENSIZE（ptr，prevlensize）就是用来设置entry中的prevlensize字段。defineZIPDECODEPREVLENSIZE（ptr，prevlensize）do｛if（（ptr）〔0〕ZIPBIGLEN）｛（prevlensize）1；｝else｛（prevlensize）5；｝｝while（0）；
　　那ZIPDECODEPREVLEN（ptr，prevlensize，prevlen）就很简单了，就是把ptr〔1〕ptr〔4〕的数据复制到prevlen。defineZIPDECODEPREVLEN（ptr，prevlensize，prevlen）do｛ZIPDECODEPREVLENSIZE（ptr，prevlensize）；if（（prevlensize）1）｛（prevlen）（ptr）〔0〕；｝elseif（（prevlensize）5）｛assert（sizeof（（prevlensize））4）；memcpy（（prevlen），（（char）（ptr））1，4）；memrev32ifbe（prevlen）；｝｝while（0）；2。2。函数
　　ziplist的函数实现，从ziplist的创建、插入等操作开始叙述。2。2。1。charziplistNew（void）
　　顾名思义，这个函数就是产生一个新的ziplist。
　　代码：unsignedcharziplistNew（void）｛unsignedintbytesZIPLISTHEADERSIZE1；unsignedcharzlzmalloc（bytes）；ZIPLISTBYTES（zl）intrev32ifbe（bytes）；ZIPLISTTAILOFFSET（zl）intrev32ifbe（ZIPLISTHEADERSIZE）；ZIPLISTLENGTH（zl）0；zl〔bytes1〕ZIPEND；returnzl；｝
　　见1。1章节ziplist的内存结构，ziplist初始时没有entry，因此其结构中只存在zlbytes、zltail、zllen和zlend四个，其中，zlbytes和zltail分别占用4个字节，zllen占用2个字节，zlend占用一个字节。因此代码中的bytes计算得11个字节。
　　分配完对应的内存后，使用上一章的宏定义设置ziplist的相关参数。
　　最后，把zl〔bytes1〕即最后一个字节设置为0xff，即ZIPEND。2。2。2。zlentryzipEntry（unsignedcharp）
　　这个函数用来生成一个新的entry，entry的结构如下：typedefstructzlentry｛prevrawlen表示上一个entry的大小、prevrawlensize表示prevrawlen占用的字节数unsignedintprevrawlensize，prevrawlen；len表示当前entry的长度lensize表示len占用的字节数unsignedintlensize，len；headersize表示entry的头部占用字节数headersizeprevrawlensizelensizeunsignedintheadersize；encoding表示当前entry使用的编码unsignedcharencoding；p指向的数据是当前entry的实际内容，包括prevrawlen、encoding和contentunsignedcharp；｝zlentry；
　　因此，zipEntry的实现也很简单，entry的prevrawlen和len都储存在p指向的地址中，使用2。1。9的相关宏进行设置。
　　上面的entry结构是便于同前端交互而实现的结构，实际ziplist中的entry中只有prevrawlen、lenencoding以及数据content组成。2。2。3。数据插入
　　ziplist支持从头部和尾部进行数据的插入，这两种方法都需要使用ziplistInsert实现。函数签名如下：unsignedcharziplistInsert（unsignedcharzl，unsignedcharp，unsignedchars，unsignedintslen）
　　函数中zl就是实际的ziplist实体，p为需要插入的entry指针位置，s为需要插入的字符串，长度为slen。
　　实现逻辑如下：计算prevlensize和prevlen，如果p在zl的最后位置，则通过ptail进行计算，否则直接通过p就可以计算得到。if（p〔0〕！ZIPEND）｛如果p不是zl的最后位置，新数据是插在p后面的，因此通过p可以获得prevlensize和prevlenZIPDECODEPREVLEN（p，prevlensize，prevlen）；｝else｛p是zl的最后位置新数据插入在ptail后面那么需要获取ptail的长度给prevlenunsignedcharptailZIPLISTENTRYTAIL（zl）；if（ptail〔0〕！ZIPEND）｛prevlenzipRawEntryLength（ptail）；｝｝使用zipTryEncoding（s，slen，value，encoding）判断能否将s字符串转换为数字，并设置相应的encoding；如果无法转换，ziplist将使用字符串编码方式进行储存。使用ziplistResize（zl，curlenreqlennextdiff）增加zl的内存，并进行内存移动操作，留出可以放置新entry的空间。新entry下一跳entry的prevlen需要进行调整，在1。2章节中，prevrawlen可能为1或5个字节。在本节中，如果新entry的长度len一个字节就够编码，而下一跳entry的prerawlen之前使用5个字节编码，那么就需要进行内存的调整。具体见ziplistCascadeUpdate（zl，preqlen）的代码实现。根据需要插入的数据类型（string或整数）添加到ziplist中，并增加zllen。2。2。4。查找
　　函数签名如下，p为需要查找的entry列表起点，vstr为需要查找的数据，长度为vlen，每次查找时跳过skip个entry进行匹配。例如，skip2，第一次比较entry0，那么entry1、entry2都会跳过不进行比较，下一次直接比较entry3。unsignedcharziplistFind（unsignedcharp，unsignedcharvstr，unsignedintvlen，unsignedintskip）
　　这个函数的实现思路为，从第一个entry依次遍历到最后一个entry，即p〔0〕ZIPEND。通过宏定义获取p指向entry的prevlensize、lensize和len。qpprevlensizelensize，得到当前entry的数据所在地址。根据encoding，进行分别比较。如果为string，则使用memcmp比较，否则使用zipTryEncoding将vstr转为整数进行比较。在循环中，使用skipcnt进行跳过。将pqlen，指向下一个entry。2。2。5。遍历
　　在对ziplist进行遍历时需要获取下一个entry的地址，遍历分前向和后向遍历，因此，ziplist也有两种实现方式。unsignedcharziplistNext（unsignedcharzl，unsignedcharp）unsignedcharziplistPrev（unsignedcharzl，unsignedcharp）
　　在ziplistNext中，如果p已经遍历到zl的最后位置ZIPEND，下一个entry就是NULL；否则的话使用zipRawEntryLength获取p的entry占用字节数，然后将p向后移动相应的字节。如果移动后p指向ZIPEND，则返回NULL。
　　在ziplistPrev中，如果p指向ZIPEND，那么p的上一个entry就是zltail指向的entry，将其返回即可；如果p是zl的第一个entry，那么返回NULL；否则的话使用ZIPDECODEPREVLEN计算当前entry中的prevlen，将pprevlen并返回。2。2。6。删除
　　函数签名如下，删除从p开始的num个entry，并返回删除后的ziplist。unsignedcharziplistDelete（unsignedcharzl，unsignedcharp，unsignedintnum）
　　实现思路如下：计算需要删除的entry占用的内存字节数totlen。如果totlen为0，直接返回zl如果totlen0，说明需要进行内存的移动。删除entry时，第num1个entry的prevrawlen就需要重新调整，可能从1字节变为5字节，因此需要使用zipPrevLenByteDiff函数判断需要调整的字节数nextdiff，然后p向前移动nextdiff个字节数。重新设置zlbytes、zllen、zltail等参数，返回zl2。2。7。entry数量
　　获取zl中entry的数量就比较简单了。如果zllen小于UINT16MAX，直接就可以返回zllen；否则的话需要从第一个entry遍历到最后一个entry进行统计。代码就不贴了，可以看源代码中的ziplistLen（unsignedcharzl）函数。总结
　　ziplist当数据量比较大的时候，其查找还是很消耗资源的，需要进行完全遍历，时间复杂度最坏情况为O（n）；它的插入和删除的时间复杂度也并不一致是O（1）。因此在使用时也需要配合其他数据结构使用。
　　刚开始接触ziplist的时候不知道它的具体原理是什么，但是只要了解ziplist的内存分布以及entry的内存分布，它的相关函数实现逻辑基本就了然于胸了，不过具体的细节还是需要阅读源码来提高理解的。