Redis源码解析：07压缩列表
? ? ? ? 壓縮列表(ziplist)是列表鍵和哈希鍵的底層實現之一。當列表鍵只包含少量列表項，并且每個列表項要么是小整數值，要么是長度較短的字符串時；或者當哈希鍵只包含少量鍵值對，并且每個鍵值對的鍵和值要么是小整數值，要么是長度較短的字符串時，那么Redis就會使用壓縮列表來做為列表鍵或哈希鍵的底層實現。
?
? ? ? ??壓縮列表是Redis為了節約內存而開發的，可用于存儲字符串和整數值。它是一個順序型數據結構，由一系列特殊編碼的連續內存塊組成。一個壓縮列表可以包含任意多個結點(entry)，每個entry的大小不定，每個entry可保存一個字符串或一個整數值。
?
???????? ziplist的相關實現在都在ziplist.c中。
?
一：ziplist結構
? ? ? ??ziplist的結構如下：
<zlbytes><zltail><zllen><entry1><entry2>...<entryN><zlend>
? ? ? ??zlbytes是一個uint32_t類型的整數，表示整個ziplist占用的內存字節數；
? ? ? ??zltail是一個uint32_t類型的整數，表示ziplist中最后一個entry的偏移量，通過該偏移量，無需遍歷整個ziplist就可以確定尾結點的地址；
? ? ? ??zllen是一個uint16_t類型的整數，表示ziplist中的entry數目。如果該值小于UINT16_MAX(65535)，則該屬性值就是ziplist的entry數目，若該值等于UINT16_MAX(65535)，則還需要遍歷整個ziplist才能得到真正的entry數目；
? ? ? ??entryX表示ziplist的結點，每個entry的長度不定；
? ? ? ??zlend是一個uint8_t類型的整數，其值為0xFF(255)，表示ziplist的結尾。
?
???????? 在ziplist.c中，定義了一系列的宏，可以分別獲取ziplist中存儲的各個屬性，比如：
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)???????? ZIPLIST_BYTES獲取ziplist中的zlbytes屬性；ZIPLIST_TAIL_OFFSET獲取ziplist的zltail屬性；ZIPLIST_LENGTH獲取ziplist的zllen屬性
???????? ZIPLIST_ENTRY_HEAD得到ziplist頭結點的地址；ZIPLIST_ENTRY_TAIL得到ziplist中尾節點的首地址，ZIPLIST_ENTRY_END得到ziplist結尾字節zlend的地址。
???????? 注意，ziplist中所有的屬性值都是以小端的格式存儲的。因此取得ziplist中保存的屬性值后，還需要對內存做字節翻轉才能得到真正的值。intrev32ifbe就是在大端系統下對內存進行字節翻轉的函數。
?
二：entry結構
? ? ? ??每個壓縮列表節點都由previous_entry_length、encoding和content三部分組成。
? ? ? ??previous_entry_length表示前一個entry的字節長度，根據該字段值就可以從后向前遍歷ziplist。
? ? ? ??previous_entry_length字段長度可以是1字節，也可以是5字節。如果前一個entry長度小于254字節，則該字段只占用一個字節；如果前一個entry長度大于等于254字節，則該字段占用5個字節：第一個字節置為0xFE(254)，之后的4個字節保存entry的實際長度（小端格式存儲）。
? ? ? ??之所以用0xFE(254)這個值作為分界點，是因為0xFF(255)被用作ziplist的結束標志，一旦掃描到0xFF，就認為ziplist結束了。
?
? ? ? ??entry的content字段保存節點的實際內容，它可以是一個字符串或者整數，值的類型和長度由encoding屬性決定。
?
? ? ? ??encoding字段記錄了節點的content所保存的數據類型及長度。如果entry中保存的是字符串，則encoding字段的前2個二進制位可以是00、01和10，分別表示不同長度類型的字符串，剩下的二進制位就表示字符串的實際長度；如果entry中的內容為整數，則encoding字段的前2個二進制位都為11，剩下的2個二進制位表示整數的類型。encoding的形式如下：
? ? ? ??00pppppp，1字節，表示長度小于等于63(2^6- 1) 字節的字符串；
? ? ? ??01pppppp|qqqqqqqq，2 字節，表示長度小于等于16383(2^14 - 1) 字節的字符串；
? ? ? ??10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt，5字節，表示長度小于等于4294967295(2^32- 1) 字節的字符串
?
? ? ? ??11000000，1字節，表示int16_t類型的整數；
? ? ? ??11010000，1字節，表示int32_t類型的整數；
? ? ? ??11100000，1字節，表示int64_t類型的整數；
? ? ? ??11110000，1字節，表示24位有符號整數；
? ? ? ??11111110，1字節，表示8位有符號整數；
? ? ? ??1111xxxx，1字節，表示0到12之間的值。使用這一編碼的節點沒有相應的oontont屬性，因為xxxx就可以表示0到12之間的值。因為0000和1110不可用，所以xxxx的取值從0001到1101，也就是1到13之間的值。因此，需要從xxxx減去1，才能得到實際的值。
? ? ? ??注意，所有的整數都是以小端的格式存儲的。
?
三：連鎖更新
? ? ? ??每個節點的previous_entry_length字段記錄了前一個節點的長度。如果前一節點的長度小于254字節，那么previous_entry_length字段占用1個字節；如果前一節點的長度大于等于254字節，那么previous_entry_length字段占用5個字節。
? ? ? ??考慮這樣一種情況：在一個壓縮列表中，有多個連續的、長度介于250字節到253字節之間的節點e1至eN。因所有節點的長度都小于254字節，所以e1至eN節點的previous_entry_length字段都是1字節長。
? ? ? ??這時，如果將一個長度大于等于254字節的新節點new設置為壓縮列表的表頭節點，那么new將成為e1的前置節點，但是因為e1的previous_entry_length字段僅長1字節，沒辦法保存新節點new的長度，所以需要對壓縮列表執行空間重分配操作，將e1節點的previous_entry_length字段從原來的1字節擴展為5字節。
? ? ? ??現在，麻煩的事情來了，原e1的長度介于250字節至253字節之間，e1的previous_entry_length字段變成5個字節后，e1的長度就大于等于254了。從而e2的previous_entry_length字段，也需要從原來的1字節長擴展為5字節長。
? ? ? ??因此，需要再次對壓縮列表執行空間重分配操作，并將e2節點的previous_entry_length屬性從原來的1字節長擴展為5字節長。
? ? ? ??以此類推，為了讓每個節點的previous_entry_length屬性都符合壓縮列表對節點的要求，程序需要不斷地對壓縮列表執行空間重分配操作，直到eN為止。
? ? ? ??Redis將這種在特殊情況下產生的連續多次空間擴展操作稱之為“連鎖更新”(cascade update)。除了添加新節點可能會引發連鎖更新之外，刪除節點也可能會引發連鎖更新。
?
? ? ? ??因為連鎖更新在最壞情況下需要對壓縮列表執行N次空間重分配操作，而每次空間重分配的最壞復雜度為O(N)，所以連鎖更新的最壞復雜度為O(N^2)。
? ? ? ??盡管連鎖更新的復雜度較高，但它真正造成性能間題的幾率是很低的。
? ? ? ??首先，壓縮列表里要恰好有多個連續的、長度介于250字節至253字節之間的節點，連鎖更新才有可能觸發。在實際中，這種情況并不多見；
? ? ? ??其次，即使出現連鎖更新，但只要被更新的節點數量不多，就不會對性能造成任何影響，比如對三五個節點進行連鎖更新是絕對不會影響性能的；
? ? ? ??因此，ziplistPush等函數的平均復雜度僅為O(N)。在實際中，我們可以放心地使用這些函數，而不必擔心連鎖更新會影響壓縮列表的性能。
?
? ? ? ??ziplist變動時，previous_entry_length字段長度可能需要從1字節擴展為5字節，從而會引起連鎖更新，也可能需要從5字節收縮為1字節。這就有可能會發生抖動現象，也就是節點的previous_entry_length字段，不斷的擴展和收縮的現象。Redis中，為了避免這種現象，允許previous_entry_length字段在需要收縮的情況下，保持5字節不變。
?
四：代碼
? ? ? ??Redis中的ziplist實現，并未涉及難以理解的算法。但是因為ziplist本身的編碼需求較多，因而代碼需要處理各種細節，初看之下比較繁雜，分析之后，其實很容易理解。
?
1：連鎖更新
? ? ? ??下面就是處理連鎖更新的代碼，zl指向一個ziplist，p指向其中第一個不需要更新的節點（第一個已經更新過的節點），其后續的節點可能需要更新：
static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;size_t offset, noffset, extra;unsigned char *np;zlentry cur, next;while (p[0] != ZIP_END) {cur = zipEntry(p);rawlen = cur.headersize + cur.len;rawlensize = zipPrevEncodeLength(NULL,rawlen);/* Abort if there is no next entry. */if (p[rawlen] == ZIP_END) break;next = zipEntry(p+rawlen);/* Abort when "prevlen" has not changed. */if (next.prevrawlen == rawlen) break;if (next.prevrawlensize < rawlensize) {/* The "prevlen" field of "next" needs more bytes to hold* the raw length of "cur". */offset = p-zl;extra = rawlensize-next.prevrawlensize;zl = ziplistResize(zl,curlen+extra);p = zl+offset;/* Current pointer and offset for next element. */np = p+rawlen;noffset = np-zl;/* Update tail offset when next element is not the tail element. */if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);}/* Move the tail to the back. */memmove(np+rawlensize,np+next.prevrawlensize,curlen-noffset-next.prevrawlensize-1);zipPrevEncodeLength(np,rawlen);/* Advance the cursor */p += rawlen;curlen += extra;} else {if (next.prevrawlensize > rawlensize) {/* This would result in shrinking, which we want to avoid.* So, set "rawlen" in the available bytes. */zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);} else {zipPrevEncodeLength(p+rawlen,rawlen);}/* Stop here, as the raw length of "next" has not changed. */break;}}return zl; }
? ? ? ??首先獲取ziplist當前的長度curlen；
? ? ? ??然后從p開始輪訓，獲取p指向節點的總長度rawlen，以及編碼該字節長度需要的字節數rawlensize；
? ? ? ??如果p指向的結點沒有后繼結點，直接退出返回；否則，next表示p的后繼節點，next節點的previous_entry_length字段值為next.prevrawlen，該字段長度是next.prevrawlensize。如果next.prevrawlen與rawlen相等，則表示next節點的前繼節點的長度未發生變化，直接退出返回；
?
? ? ? ??如果next.prevrawlensize小于rawlensize，表示next節點的前繼節點的長度，原來小于254字節，現在大于等于254字節了。因此next節點的previous_entry_length字段需要擴展長度，擴展的字節數extra為rawlensize-next.prevrawlensize，利用ziplistResize擴展ziplist的內存空間。注意，擴容前要保存p的偏移量，擴容后利用該偏移量，可以重新得到p的位置。
? ? ? ??如下圖，分別表示擴容前和擴容后的情況：
? ? ? ??如果next節點不是尾節點，則需要更新ziplist的zltail屬性；如果next是尾結點，因為next之前的內容沒有變化，因此無需更新zltail屬性；
? ? ? ??然后開始移動內存，移動的內容是，從next節點的previous_entry_length字段之后的內存開始，到ziplist末尾字節zlend之前的內容：memmove(np+rawlensize, np+next.prevrawlensize, curlen-noffset-next.prevrawlensize-1);
? ? ? ??然后更新next中的previous_entry_length字段為rawlen；
? ? ? ??然后p指向next節點，依次遍歷下一個節點；
????????
? ? ? ??如果next.prevrawlensize大于rawlensize，表示next節點的前繼節點的長度，原來大于等于254字節，現在小于254字節了。為了避免“抖動”，調用zipPrevEncodeLengthForceLarge保持next節點的previous_entry_length字段長度不變，并強制編碼為rawlen，然后退出返回；
?
? ? ? ??如果next.prevrawlensize等于rawlensize，表示next節點的前繼節點的長度，原來小于254字節，現在還是小于254字節，或者原來大于等于254字節，現在還是大于等于254字節。這種情況下，直接將next節點的previous_entry_length字段編碼為rawlen，然后退出返回。
?
2：刪除節點
? ? ? ??下面是刪除節點的代碼，從ziplist中，p指向的節點開始，最多刪除num個節點：
static 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;first = zipEntry(p);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) {/* Storing `prevrawlen` in this entry may increase or decrease the* number of bytes required compare to the current `prevrawlen`.* There always is room to store this, because it was previously* stored by an entry that is now being deleted. */nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);p -= nextdiff;zipPrevEncodeLength(p,first.prevrawlen);/* Update offset for tail */ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);/* When the tail contains more than one entry, we need to take* "nextdiff" in account as well. Otherwise, a change in the* size of prevlen doesn't have an effect on the *tail* offset. */tail = zipEntry(p);if (p[tail.headersize+tail.len] != ZIP_END) {ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);}/* Move tail to the front of the ziplist */memmove(first.p,p,intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);} else {/* The entire tail was deleted. No need to move memory. */ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe((first.p-zl)-first.prevrawlen);}/* Resize and update length */offset = first.p-zl;zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);ZIPLIST_INCR_LENGTH(zl,-deleted);p = zl+offset;/* When nextdiff != 0, the raw length of the next entry has changed, so* we need to cascade the update throughout the ziplist */if (nextdiff != 0)zl = __ziplistCascadeUpdate(zl,p);}return zl; }
? ? ? ??首先將p轉化為zlentry結構的first，然后從p開始向后遍歷num個節點，這樣，就得到了需要刪除的節點數deleted，以及要刪除的總字節數totlen。只有當totlen大于0時，才進行刪除動作，否則直接返回zl；此時p指向最后一個刪除節點的后繼節點；
?
? ? ? ??若此時p不是ziplist的結尾字節，則其指向節點的previous_entry_length字段，需要設置為新值first.prevrawlen。首先計算p指向節點，其新舊previous_entry_length字段長度的差值nextdiff，nextdiff為正，表示p節點的previous_entry_length字段需要擴容，從要刪除的內存中選擇擴容的部分，因此p-=nextdiff，p向前走nextdiff個字節，表示少刪除nextdiff個字節。如果nextdiff為負，表示p節點的previous_entry_length字段需要收縮，因此p-=nextdiff，表示p向后走nextdiff個字節，表示多刪除nextdiff個字節；
? ? ? ??然后重新設置p指向節點的previous_entry_length字段值為first.prevrawlen；
????????
? ? ? ??接下來就是調整zltail屬性，分情況討論：如果遍歷num個節點之后，未做nextdiff調整之前，p指向的節點就是尾結點，如下圖所示（僅以nextdiff為正為例）：
? ? ? ??上圖中，p'表示未做nextdiff調整之前的指針，也就是指向原尾結點的指針，p表示做出nextdiff調整之后的指針。刪除num個節點之后，zltail的值，也就是first.p-zl，因此有：new_zltail = old_zltail - totlen; 刪除后如下圖所示：
? ? ? ??上面的情況，對于nextdiff為負也是成立的，不再贅述。
????????
? ? ? ??如果遍歷num個節點之后，未做nextdiff調整之前，p指向的節點不是尾結點，則新的zltail，等于舊的zltail，減去刪除的總字節數，刪除的總字節數為totlen-nextdiff，因此有：new_zltail = old_zltail - totlen + nextdiff;
?
? ? ? ??更新完zltail屬性后，接下來就是移動內存了，將當前p指向的內存，移動到first.p指向的位置上，移動的內存總數就是，從當前p指向的內存開始，到ziplist結尾字節之前的內容；
?
? ? ? ??如果在遍歷num個節點之后，p指向的字節就是ziplist的結尾字節，則無需移動內存，僅需要重新設置zltail屬性即可，此時的尾結點，是first.p的前繼節點，因此有：new_zltail = first.p - zl -first.prevrawlen;
?
? ? ? ??移動內存，以及設置新的zltail之后，剩下的就是重新為ziplist分配空間，并且設置新的zllen屬性。注意，重新分配ziplist內存之前，保存p的偏移量offset，這樣，在分配空間之后，就可以利用offset重新得到p的位置了；
? ? ? ??如果nextdiff不為0，表示p指向的節點的大小發生了變化，調用__ziplistCascadeUpdate處理后續的節點。
?
3：插入節點
???????? 下面是插入節點的代碼，根據原始數據s，及其長度slen，新建一個ziplist節點，將該節點插入到p之前的位置，也就是，p指向的節點，成為新結點的后繼節點。
static 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; /* initialized to avoid warning. Using a valuethat is easy to see if for some reasonwe use it uninitialized. */zlentry tail;/* Find out prevlen for the entry that is inserted. */if (p[0] != ZIP_END) {ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);} else {unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);if (ptail[0] != ZIP_END) {prevlen = zipRawEntryLength(ptail);}}/* See if the entry can be encoded */if (zipTryEncoding(s,slen,&value,&encoding)) {/* 'encoding' is set to the appropriate integer encoding */reqlen = zipIntSize(encoding);} else {/* 'encoding' is untouched, however zipEncodeLength will use the* string length to figure out how to encode it. */reqlen = slen;}/* We need space for both the length of the previous entry and* the length of the payload. */reqlen += zipPrevEncodeLength(NULL,prevlen);reqlen += zipEncodeLength(NULL,encoding,slen);/* When the insert position is not equal to the tail, we need to* make sure that the next entry can hold this entry's length in* its prevlen field. */nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;/* Store offset because a realloc may change the address of zl. */offset = p-zl;zl = ziplistResize(zl,curlen+reqlen+nextdiff);p = zl+offset;/* Apply memory move when necessary and update tail offset. */if (p[0] != ZIP_END) {/* Subtract one because of the ZIP_END bytes */memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);/* Encode this entry's raw length in the next entry. */zipPrevEncodeLength(p+reqlen,reqlen);/* Update offset for tail */ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);/* When the tail contains more than one entry, we need to take* "nextdiff" in account as well. Otherwise, a change in the* size of prevlen doesn't have an effect on the *tail* offset. */tail = zipEntry(p+reqlen);if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);}} else {/* This element will be the new tail. */ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);}/* When nextdiff != 0, the raw length of the next entry has changed, so* we need to cascade the update throughout the ziplist */if (nextdiff != 0) {offset = p-zl;zl = __ziplistCascadeUpdate(zl,p+reqlen);p = zl+offset;}/* Write the entry */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);return zl; }
? ? ? ? ?首先獲取ziplist當前長度curlen；
???????? 然后得到p指向位置的前繼節點的長度prevlen；
???????? 然后計算新結點中content部分的長度：如果s中的內容能夠表示為整數值，則得到該整數值的長度reqlen，否則，reqlen等于slen；
???????? 根據prevlen，得到新結點的previous_entry_length字段長度，加到reqlen中；
???????? 根據encoding和slen，得到新結點的encoding字段長度，加到reqlen中，至此，reqlen就表示新結點的總長度；
????????
? ? ? ? ? 因新結點將成為p的前繼節點，因此，只要p并非ziplist的結尾字節，就利用zipPrevLenByteDiff，計算p中新舊previous_entry_length字段的長度之差nextdiff，nextdiff為正，表示因新結點的長度大于等于254，p的previous_entry_length字段需要擴容nextdiff個字節；如果nextdiff為負，表示因新結點的長度小于254，p的previous_entry_length字段需要收縮nextdiff個字節；
?
???????? 接下來，利用ziplistResize對ziplist進行擴容，擴容長度為reqlen+nextdiff，擴容之前，保存p的偏移量offset，這樣擴容后根據offset，就可以重新得到p的位置；
?
???????? 如果p并非ziplist的結尾字節，則接下來開始移動內存，從p-nextdiff指向的位置，移動到p+reqlen的位置，移動的字節數為curlen-offset-1+nextdiff；
???????? 然后設置新結點的后繼節點（也就是插入之前，p指向的節點）的previous_entry_length字段；
???????? 然后設置zltail屬性，這里根據p是否是尾結點而區分對待，情況類似與__ziplistDelete中的討論，不再贅述。
?
???????? 如果p就是ziplist的結尾字節，則只需要更新zltail屬性即可；
????????
???????? 如果nextdiff非0，則需要調用__ziplistCascadeUpdate，處理p+reqlen節點開始的連鎖升級或是收縮情況；
???????? 最后，設置插入的新結點的各種字段值，并更新zllen屬性。
?
? ? ? ? ?其他關于ziplist的代碼，可參閱：
https://github.com/gqtc/redis-3.0.5/blob/master/redis-3.0.5/src/ziplist.c
轉載于:https://www.cnblogs.com/gqtcgq/p/7247072.html
總結
以上是生活随笔為你收集整理的Redis源码解析：07压缩列表的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 1. redis简介
- 下一篇： eclipse项目迁移到android