主頁 > 知識庫 > redis源碼分析教程之壓縮鏈表ziplist詳解

redis源碼分析教程之壓縮鏈表ziplist詳解

前言

壓縮列表（ziplist）是由一系列特殊編碼的內(nèi)存塊構成的列表，它對于Redis的數(shù)據(jù)存儲優(yōu)化有著非常重要的作用。這篇文章總結一下redis中使用非常多的一個數(shù)據(jù)結構壓縮鏈表ziplist。該數(shù)據(jù)結構在redis中說是無處不在也毫不過分，除了鏈表以外，很多其他數(shù)據(jù)結構也是用它進行過渡的，比如前面文章提到的SortedSet。下面話不多說了，來一起看看詳細的介紹吧。

一、壓縮鏈表ziplist數(shù)據(jù)結構簡介

首先從整體上看下ziplist的結構，如下圖：

壓縮鏈表ziplist結構圖

可以看出字段很多，字節(jié)大小也不同，但這也就是壓縮鏈表的精髓所在了，我們依次總結一下。

字段	含義
zlbytes	該字段是壓縮鏈表的第一個字段，是無符號整型，占用4個字節(jié)。用于表示整個壓縮鏈表占用的字節(jié)數(shù)（包括它自己）。
zltail	無符號整型，占用4個字節(jié)。用于存儲從壓縮鏈表頭部到最后一個entry（不是尾元素zlend）的偏移量，在快速跳轉到鏈表尾部的場景使用。
zllen	無符號整型，占用2個字節(jié)。用于存儲壓縮鏈表中包含的entry總數(shù)。
zlend	特殊的entry，用來表示壓縮鏈表的末尾。占用一個字節(jié)，值恒為255。

總結為ziplist的頭跟尾，下面再總結一下重中之重的entry字段。

一般來說，一個entry由prevlen，encoding，entry-data三個字段組成，但當entry是個很小的整數(shù)時，會根據(jù)編碼省略掉entry-data字段。下面依次進行總結：

首先是字段prevlen：表示前一個entry的長度，有兩種編碼方式。

當長度小于255字節(jié)時，用一個字節(jié)存儲。
當長度大于等于255時，用五個字節(jié)進行存儲，其中第一個字節(jié)會被設置為255表示前一個entry的長度由后面四個字節(jié)表示。

然后是字段encoding：它會根據(jù)當前元素內(nèi)容的不同會采用不同的編碼方式，如下：

1、如果元素內(nèi)容為字符串，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開頭表示后續(xù)的四個字節(jié)為字符串長度，這32個bit采用大端存儲。

2、如果元素內(nèi)容為數(shù)字，encoding的值分別為：

1100 0000：表示數(shù)字占用后面2個字節(jié)。

1101 0000：表示數(shù)字占用后面4個字節(jié)。

1110 0000：表示數(shù)字占用后面8個字節(jié)。

1111 0000 ：表示數(shù)字占用后面3個字節(jié)。

1111 1110 ：表示數(shù)字占用后面1個字節(jié)。

1111 1111 ：表示壓縮鏈表中最后一個元素（特殊編碼）。

1111 xxxx ：表示只用后4位表示0~12的整數(shù)，由于0000，1110跟1111三種已經(jīng)被占用，也就是說這里的xxxx四位只能表示0001~1101，轉換成十進制就是數(shù)字1~13，但是redis規(guī)定它用來表示0~12，因此當遇到這個編碼時，我們需要取出后四位然后減1來得到正確的值。

最后是字段entry-data：如果元素的值為字符串，則保存元素本身的值。如果元素的值為很小的數(shù)字（按上面編碼規(guī)則即0~12），則沒有該字段。

壓縮鏈表的編碼非常復雜，但這也正是該數(shù)據(jù)結構的精髓所在，一起來看一個例子吧：

注：這個例子是redis源碼中提到的

//由元素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"編碼后的內(nèi)容
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

上面是一段用十六進制表示2，5兩個元素組成的壓縮鏈表。

首先前四個字節(jié)表示整個ziplist占用的字節(jié)數(shù)，因為redis采用小端存儲，所以15個字節(jié)表示為0f 00 00 00。
接下來的4個字節(jié)表示末尾元素偏移量，是從ziplist頭（zlbytes）開始到最后一個元素（注：不是尾節(jié)點）的偏移量，也是采用小端存儲，因此表示為0c 00 00 00。
再后面是由兩個字節(jié)組成的表示元素個數(shù)的zllen字段，在我們這個例子中有兩個元素，加上小端存儲，所以表示為02 00。
接下來是元素本身，首先由一個變長的字端表示前一個元素的長度，2作為第一個元素，它前一個元素的大小就是0，因此占用一個字節(jié)00。按照我們上面說的編碼規(guī)則，元素2跟5屬于0~12之間的數(shù)字，需要使用1111 xxxx格式進行編碼，2轉成二進制為0010，再加上1就是0011（加1的原因上面已經(jīng)說明），組合起來元素2就表示為00 f3。同理元素5表示為02 f6。
最后就是尾元素，使用未被占用的編碼1111 1111即255。

接下來我們在這個壓縮鏈表末尾插入一個字符串元素Hello World，先看看該如何編碼該字符串，按照約定的編碼規(guī)則，首先要用字節(jié)表示前一個元素的長度，這里前一個元素時5，總共占用了兩個字節(jié)，因此首先用一個字節(jié)表示前一個元素的長度02，接下來是字符串的編碼，我們要加入的字符串長度為11（空格也算），轉換成二進制就是1011，按照字符串的編碼規(guī)則，使用0000 1011表示，轉為十六進制就是0b，最后再加上我們字符串本身的ASCII碼，綜合起來就得出該字符串的編碼：[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]。

此時整個壓縮鏈表就變?yōu)椋?/p>

[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

二、壓縮鏈表ziplist命令源碼分析

搞明白上面的編碼規(guī)則以后，我們再來看下壓縮鏈表ziplist的部分操作源碼，本文就創(chuàng)建壓縮鏈表，插入元素，刪除元素，查找元素四個操作來總結一下壓縮鏈表的基本原理。

首先是創(chuàng)建：

//定義由zlbytes，zltail跟zllen組成的壓縮鏈表的頭大小
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//創(chuàng)建一個壓縮鏈表，并且返回指向該鏈表的指針
unsigned char *ziplistNew(void) {
 //這里之所以+1是因為尾元素占用一個字節(jié)，這也是一個壓縮鏈表最小尺寸
 unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
 //分配內(nèi)存
 unsigned char *zl = zmalloc(bytes);
 //設置鏈表大小
 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
 //設置最后一個元素的偏移量
 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
 //設置元素個數(shù)
 ZIPLIST_LENGTH(zl) = 0;
 //設置尾元素（上面只是申請空間）
 zl[bytes-1] = ZIP_END;
 return zl;
}

創(chuàng)建壓縮鏈表的邏輯很簡單，就是申請固定的包含頭尾節(jié)點的空間，然后初始化鏈表上下文。

與創(chuàng)建相比，添加元素的源碼就非常冗長了，為了便于理解，在看源碼之前我們先自己梳理一下添加元素的邏輯。

首先我們要找到指定插入位置的前一個元素的大小，因為該屬性是新元素的組成部分之一。
然后我們要對當前元素進行編碼來獲得相應的encoding字段跟實際元素值的字段。
新插入元素的后繼元素的prevlen字段要更新，因為它前面的元素已經(jīng)改變。這里可能引起級聯(lián)更新（刪除元素也有該問題），原因就是prevlen字段大小是可變的。

上面三步是核心步驟，其余的還有更新尾節(jié)點偏移量，修改鏈表元素個數(shù)等操作。當然，由于壓縮鏈表是基于數(shù)組實現(xiàn)的，因此在插入或刪除元素的時候內(nèi)存拷貝也是必不可少的。

總結好上面的步驟以后，我們開始一步一步分析源碼，比較長，慢慢看：

//四個參數(shù)依次是：壓縮鏈表，插入位置（新元素插入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)) {
 //如果是數(shù)字，則按數(shù)字進行編碼
 reqlen = zipIntSize(encoding);
 } else {
 //元素長度即為字符串長度
 reqlen = slen;
 }
 //新元素總長度為值的長度加上前置元素跟encoding元素的長度
 reqlen += zipStorePrevEntryLength(NULL,prevlen);
 reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

 //如果插入的位置不是鏈表尾，則要對新元素的后續(xù)元素的prevlen字段進行判斷
 //根據(jù)上面的編碼規(guī)則，該字段可能需要擴容
 int forcelarge = 0;
 nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
 if (nextdiff == -4  reqlen  4) {
 nextdiff = 0;
 forcelarge = 1;
 }
 //按照新計算出的數(shù)組大小進行擴容，由于新數(shù)組的地址可能會改變，因此這里記錄舊的偏移量
 offset = p-zl;
 zl = ziplistResize(zl,curlen+reqlen+nextdiff);
 //在新數(shù)組上計算插入位置
 p = zl+offset;
 //如果新插入的元素不是在鏈表末尾
 if (p[0] != ZIP_END) {
 //把新元素后繼元素復制到新的數(shù)組中，-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表示后繼元素的長度發(fā)生變化，因此我們需要級聯(lián)更新后繼元素的后繼元素
 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);
 }
 //壓縮鏈表存儲元素數(shù)量+1
 ZIPLIST_INCR_LENGTH(zl,1);
 return zl;
}

分析完插入元素的邏輯，長舒一口氣，真的很長，細節(jié)也很多。

接下來在再看下刪除元素的過程，與添加相比，刪除相對要簡單一些，清空當前元素以后，需要把后繼元素一個一個拷貝上來（這也是數(shù)組跟鏈表兩個數(shù)據(jù)結構的差別），然后注意是否需要級聯(lián)更新，上代碼：

//參數(shù)依次為：壓縮鏈表，刪除元素的其實位置，刪除元素的個數(shù)
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++) {
  //統(tǒng)計總共刪除的長度
  p += zipRawEntryLength(p);
  //統(tǒng)計實際刪除元素的個數(shù)
  deleted++;
 }
 //需要刪除元素的字節(jié)數(shù)
 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 {
   //直接刪除到鏈表末尾，因此不需要內(nèi)存拷貝，只需修改最后一個元素的偏移量
   ZIPLIST_TAIL_OFFSET(zl) =
    intrev32ifbe((first.p-zl)-first.prevrawlen);
  }
  //resize數(shù)組大小
  offset = first.p-zl;
  zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
  //修改鏈表元素個數(shù)
  ZIPLIST_INCR_LENGTH(zl,-deleted);
  p = zl+offset;
  //nextdiff != 0表示元素大小發(fā)生變化，需要進行級聯(lián)更新
  if (nextdiff != 0)
   zl = __ziplistCascadeUpdate(zl,p);
 }
 return zl;
}

最后我們看下元素的查找操作：

//參數(shù)依次為：壓縮鏈表，要查找元素的值，要查找元素的長度，每次比較之間跳過的元素個數(shù)
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;
 //只要還沒到尾元素就不斷循環(huán)
 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 {
    //如果當前元素為數(shù)字且vencoding為0
    if (vencoding == 0) {
     //嘗試對要查找的值進行數(shù)字編碼
     if (!zipTryEncoding(vstr, vlen, vll, vencoding)) {
      //如果編碼失敗，則說明要查找的元素根本不是數(shù)字
      //然后把vencoding設置為最大值，起一個標記作用
      //也就是說后面就不用嘗試把要查找的值編碼成數(shù)字了
      vencoding = UCHAR_MAX;
     }
     assert(vencoding);
    }
    //如果vencoding != UCHAR_MAX，則說明要查找的元素成功編碼為數(shù)字
    if (vencoding != UCHAR_MAX) {
     //按數(shù)字取出當前鏈表中的元素
     long long ll = zipLoadInteger(q, encoding);
     if (ll == vll) {
      //如果兩個數(shù)字相等，則返回元素指針
      return p;
     }
    }
   }
   //重置需要跳過的元素個數(shù)
   skipcnt = skip;
  } else {
   //跳過元素
   skipcnt--;
  }
  //遍歷下個元素
  p = q + len;
 }
 //遍歷完整個鏈表，沒有找到元素
 return NULL;
}

到這里就把壓縮鏈表的創(chuàng)建，添加，刪除，查找四個基本操作原理總結完了。

三、壓縮鏈表ziplist數(shù)據(jù)結構總結

壓縮鏈表ziplist在redis中的應用非常廣泛，它算是redis中最具特色的數(shù)據(jù)結構了。該數(shù)據(jù)結構的精髓其實就在于文章第一部分總結的編碼規(guī)則，先理清楚這部分內(nèi)容，后面的源碼可以簡單看下加深理解。

不得不說源碼部分著實有點冗長，確實需要耐心，我自己在讀的過程中也很頭大。如果對源碼感興趣的話，建議按我的方法，先自己梳理某個操作（例如上面提到的插入元素）需要做哪些事情，然后再看代碼可能會更好理解一些。

最后留一個小問題，既然redis中的ziplist對內(nèi)存利用率如此之高，那為什么還要提供普通的鏈表結構供用戶使用呢？
這個問題沒有標準答案，仁者見仁智者見智吧~

總結

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。

您可能感興趣的文章:

詳解Redis中的List類型
Python操作redis實例小結【String、Hash、List、Set等】
解決Spring session(redis存儲方式)監(jiān)聽導致創(chuàng)建大量redisMessageListenerContailner-X線程問題
Redis List列表的詳細介紹
redis 獲取 list 中的所有元素操作

標簽：衡水蘭州仙桃湖南湘潭黃山崇左銅川

巨人網(wǎng)絡通訊聲明：本文標題《redis源碼分析教程之壓縮鏈表ziplist詳解》，本文關鍵詞；如發(fā)現(xiàn)本文內(nèi)容存在版權問題，煩請?zhí)峁┫嚓P信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡，涉及言論、版權與本站無關。