Redis圧縮リンクリストziplistソースコードの詳細説明

圧縮リスト (ziplist) は、特別にエンコードされた一連のメモリ ブロックで構成されるリストで、Redis データ ストレージの最適化において非常に重要な役割を果たします。この記事では主に、Redis でよく使用されるデータ構造である ziplist について説明します。 。このデータ構造は、リンク リストに加えて、前の記事で説明した SortedSet など、他の多くのデータ構造でも redis のいたるところにあると言っても過言ではありません。以下では多くを語る必要はありません。詳細な紹介を見てみましょう。

1. 圧縮リンクリスト ziplist データ構造の紹介

まず、以下に示すように、ziplist 全体の構造を見てみましょう:

圧縮リンクリストのジップリスト構造図

多くのフィールドと異なるバイト サイズがあることがわかりますが、これが圧縮リンク リストの本質です。これらを 1 つずつまとめてみましょう。

符号なし整数。4 バイトを占有します。圧縮されたリンク リストの先頭から最後のエントリ (末尾要素 zlend ではない) までのオフセットを格納するために使用され、リンク リストの末尾にすぐにジャンプできるシナリオで使用されます。 符号なし整数。2 バイトを占有します。圧縮リンクリストに含まれるエントリの総数を格納するために使用されます。 圧縮されたリンク リストの終わりを示すために使用される特別なエントリ。 1 バイトを占め、値は常に 255 です。

フィールド	意味
ズルバイト	このフィールドは、圧縮リンク リストの最初のフィールドであり、符号なし整数であり、4 バイトを占めます。圧縮されたリンク リスト全体 (それ自体を含む) が占めるバイト数を表すために使用されます。

🎜🎜🎜

これはジップリストの先頭と末尾としてまとめられており、最も重要な入力フィールドは以下にまとめられています。

一般に、エントリは prevlen、encoding、entry-data の 3 つのフィールドで構成されます。ただし、エントリが小さい整数の場合、entry-data フィールドはエンコーディングに基づいて省略されます。以下に要約します:

1 つ目はフィールド prevlen です。これは、前のエントリの長さを示します。エンコード方法は 2 つあります。

• 255バイト未満の場合は1バイトで格納されます。

• 
  

• 長さが 255 以上の場合、5 バイトがストレージに使用され、最初のバイトは 255 に設定され、前のエントリの長さが次の 4 バイトで表されることを示します。

次に、フィールドのエンコーディングがあります。次のように、現在の要素の内容に応じて異なるエンコーディング方法が使用されます。 1. 要素の内容が文字列の場合、エンコード値は次のとおりです:

00xx xxxx: 00 で始まる文字列の長さが 6 ビットで表されることを示します。

01xx xxxx |

| 1000 0000 | xxxx xxxx |

2. 要素の内容が数値の場合、エンコード値は次のとおりです:

1100 0000: 数値が次の 2 バイトを占めることを示します。

1101 0000: 数値が次の 4 バイトを占めることを示します。

1110 0000: 数値が次の 8 バイトを占めることを示します。

1111 0000: 数値が次の 3 バイトを占めることを示します。

1111 1110: 数値が次のバイトを占めることを示します。

1111 1111: 圧縮リンク リストの最後の要素を示します (特殊なエンコーディング)。

1111xxxx ：0～12の整数を下4桁のみで表現することを示します。0000、1110、1111は既に占有されているため、ここでのxxxxの4桁は0001～1101しか表現できません。10進数に変換するとただし、redis では 0 ～ 12 を表すために使用されると規定されているため、このエンコードに遭遇した場合は、最後の 4 桁を取り出して 1 を減算して正しい値を取得する必要があります。

最後に、entry-data フィールドがあります。要素の値が文字列の場合、要素自体の値が保存されます。要素の値が非常に小さい数値 (上記のエンコード規則に従って 0 ～ 12) の場合、そのようなフィールドは存在しません。

圧縮されたリンク リストのエンコードは非常に複雑ですが、これがこのデータ構造の本質でもあります。例を見てみましょう:

注: この例は 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"编码后的内容
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

で言及されています 上記は、2 つの要素 2 と 5 で構成される圧縮リンク リストを 16 進数で表したものです。

まず、最初の 4 バイトは、ziplist 全体が占めるバイト数を表します。redis はリトル エンディアン ストレージを使用するため、15 バイトは 0f 00 00 00 として表されます。

• 
  

次の 4 バイトは最後の要素のオフセットを表します。これは、ziplist ヘッダー (zl バイト) から最後の要素までのオフセットです (注: 末尾ノードではありません)。また、リトル エンディアンで格納されるため、0c として表現されます。 00 00 00。

• 
  

次に、要素数を表す 2 バイトで構成される zllen フィールドです。この例では、要素が 2 つとリトル エンディアンのストレージがあるため、02 00 と表されます。

• 
  

次に要素自体です。まず、可変長ワードは前の要素の長さを示します。2 は最初の要素なので、バイトは 00 になります。上で説明したエンコード規則によると、要素 2 と 5 は 0 から 12 までの数値に属しており、1111 を使用する必要があります。 xxxx 形式でエンコードすると、2 は 0010 として 2 進数に変換され、0011 に 1 が加算され（1 を加算する理由は上記で説明されています）、結合された要素 2 は 00 として表現されます。 f3.同様に、要素 5 は 02 f6 と表されます。

• 
  

最後の要素は末尾要素で、空いているコード 1111 1111、つまり 255 を使用します。
次に、この圧縮されたリンク リストの最後に文字列要素 Hello を挿入します。 まず、合意されたエンコード規則に従って、前の要素の長さを表すためにバイトを使用し、合計 2 バイトを占めるので、最初に単語を使用します。このセクションは、前の要素の長さ 02 を表します。次に、追加する文字列の長さは 11 (スペースもカウントされます) です。文字列のエンコード規則、0000 を使用 1011 は、16 進数に変換すると 0b になることを意味します。最後に、文字列自体の ASCII コードを追加すると、文字列のエンコーディングが得られます: [02] [0b] [48 65] 6c 6c 6f 20 57 6f 72 6c 64]。

この時点で、圧縮されたリンク リスト全体は次のようになります:

[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

2. 圧縮リンクリスト ziplist コマンドのソースコード解析

上記のエンコード規則を理解した後、圧縮リンク リスト ziplist の操作ソース コードの一部を見てみましょう。この記事では、圧縮リンク リストの作成、要素の挿入、削除の 4 つの操作を通じて、圧縮リンク リストの基本原理をまとめます。要素、および要素の検索。

まず、

//定义由zlbytes，zltail跟zllen组成的压缩链表的头大小
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//创建一个压缩链表，并且返回指向该链表的指针
unsigned char *ziplistNew(void) {
 //这里之所以+1是因为尾元素占用一个字节，这也是一个压缩链表最小尺寸
 unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
 //分配内存
 unsigned char *zl = zmalloc(bytes);
 //设置链表大小
 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
 //设置最后一个元素的偏移量
 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
 //设置元素个数
 ZIPLIST_LENGTH(zl) = 0;
 //设置尾元素（上面只是申请空间）
 zl[bytes-1] = ZIP_END;
 return zl;
}

を作成します。 圧縮リンク リストを作成するロジックは非常に単純です。先頭ノードと末尾ノードを含む固定スペースを適用し、リンク リスト コンテキストを初期化します。

与创建相比，添加元素的源码就非常冗长了，为了便于理解，在看源码之前我们先自己梳理一下添加元素的逻辑。

• 首先我们要找到指定插入位置的前一个元素的大小，因为该属性是新元素的组成部分之一。

• 
  

• 然后我们要对当前元素进行编码来获得相应的encoding字段跟实际元素值的字段。

• 
  

• 新插入元素的后继元素的prevlen字段要更新，因为它前面的元素已经改变。这里可能引起级联更新（删除元素也有该问题），原因就是prevlen字段大小是可变的。

上面三步是核心步骤，其余的还有更新尾节点偏移量，修改链表元素个数等操作。当然，由于压缩链表是基于数组实现的，因此在插入或删除元素的时候内存拷贝也是必不可少的。

总结好上面的步骤以后，我们开始一步一步分析源码，比较长，慢慢看：

//四个参数依次是：压缩链表，插入位置（新元素插入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)) {
 //如果是数字，则按数字进行编码
 reqlen = zipIntSize(encoding);
 } else {
 //元素长度即为字符串长度
 reqlen = slen;
 }
 //新元素总长度为值的长度加上前置元素跟encoding元素的长度
 reqlen += zipStorePrevEntryLength(NULL,prevlen);
 reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

 //如果插入的位置不是链表尾，则要对新元素的后续元素的prevlen字段进行判断
 //根据上面的编码规则，该字段可能需要扩容
 int forcelarge = 0;
 nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
 if (nextdiff == -4 && reqlen <p>
	分析完插入元素的逻辑，长舒一口气，真的很长，细节也很多。</p><p>
	接下来在再看下删除元素的过程，与添加相比，删除相对要简单一些，清空当前元素以后，需要把后继元素一个一个拷贝上来（这也是数组跟链表两个数据结构的差别），然后注意是否需要级联更新，上代码：</p><pre class="brush:php;toolbar:false">//参数依次为：压缩链表，删除元素的其实位置，删除元素的个数
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  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 {
   //直接删除到链表末尾，因此不需要内存拷贝，只需修改最后一个元素的偏移量
   ZIPLIST_TAIL_OFFSET(zl) =
    intrev32ifbe((first.p-zl)-first.prevrawlen);
  }
  //resize数组大小
  offset = first.p-zl;
  zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
  //修改链表元素个数
  ZIPLIST_INCR_LENGTH(zl,-deleted);
  p = zl+offset;
  //nextdiff != 0表示元素大小发生变化，需要进行级联更新
  if (nextdiff != 0)
   zl = __ziplistCascadeUpdate(zl,p);
 }
 return zl;
}

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

//参数依次为：压缩链表，要查找元素的值，要查找元素的长度，每次比较之间跳过的元素个数
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;
 //只要还没到尾元素就不断循环
 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 {
    //如果当前元素为数字且vencoding为0
    if (vencoding == 0) {
     //尝试对要查找的值进行数字编码
     if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
      //如果编码失败，则说明要查找的元素根本不是数字
      //然后把vencoding设置为最大值，起一个标记作用
      //也就是说后面就不用尝试把要查找的值编码成数字了
      vencoding = UCHAR_MAX;
     }
     assert(vencoding);
    }
    //如果vencoding != UCHAR_MAX，则说明要查找的元素成功编码为数字
    if (vencoding != UCHAR_MAX) {
     //按数字取出当前链表中的元素
     long long ll = zipLoadInteger(q, encoding);
     if (ll == vll) {
      //如果两个数字相等，则返回元素指针
      return p;
     }
    }
   }
   //重置需要跳过的元素个数
   skipcnt = skip;
  } else {
   //跳过元素
   skipcnt--;
  }
  //遍历下个元素
  p = q + len;
 }
 //遍历完整个链表，没有找到元素
 return NULL;
}

到这里就把压缩链表的创建，添加，删除，查找四个基本操作原理总结完了。

三、压缩链表ziplist数据结构总结

压缩链表ziplist在redis中的应用非常广泛，它算是redis中最具特色的数据结构了。该数据结构的精髓其实就在于文章第一部分总结的编码规则，先理清楚这部分内容，后面的源码可以简单看下加深理解。

不得不说源码部分着实有点冗长，确实需要耐心，我自己在读的过程中也很头大。如果对源码感兴趣的话，建议按我的方法，先自己梳理某个操作（例如上面提到的插入元素）需要做哪些事情，然后再看代码可能会更好理解一些。

相关推荐：

深入剖析 redis 数据结构 ziplist

Redis源码分析（六）---ziplist压缩列表

Redis内部数据结构详解之ziplist

以上がRedis圧縮リンクリストziplistソースコードの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。