English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
前略
圧縮リスト（ziplist）は、一連の特別にエンコードされたメモリブロックから成り立つリストで、Redisのデータストレージ最適化には非常に重要な役割を果たします。この記事では、Redisで非常に多く使用されるデータ構造である圧縮リストziplistについて説明します。このデータ構造はRedisの中で至る所に存在しており、過分ではありません。リスト以外にも、他の多くのデータ構造がこれを使用して中間として使用されます。例えば、前の記事で言及されたSortedSetなどです。ここではさらに詳しく説明します。
一、圧縮リストziplistデータ構造の概要
まず、ziplistの構造を全体として見てみましょう。以下の図を参照してください：
圧縮リストziplist構造図
フィールドが多いことやバイトサイズが異なることが分かりますが、これが圧縮リストの要です。以下に順次要約します。
| フィールド | の意味 |
|---|---|
| zlbytes | このフィールドは圧縮リストの最初のフィールドで、無符号整数で、4バイトを占有し、全体の圧縮リストが占めるバイト数（自分自身も含めて）を示します。 |
| zltail | 無符号整数で、4バイトを占有します。圧縮リストの先頭から最後のentry（zlendではない）までのオフセットを保存し、リストの末尾に素早くジャンプするシーンで使用されます。 |
| zllen | 無符号整数で、2バイトです。圧縮リストに含まれるentryの総数を保存するために使用されます。 |
| zlend | 特別なentryは、圧縮リストの末尾を表すために使用されます。1バイトを占有し、値は常に255。 |
ziplistの先頭と末尾を要約すると、次に重要なentryフィールドについて説明します。
一般的には、entryはprevlen、encoding、entryから成り立っています。-data三个字段组成，但当entry是个很小的整数时，会根据编码省略掉entry-フィールドから成り立っていますが、entryが非常に小さい整数の場合、エンコードに応じてentryを省略することができます。
フィールドです。以下に順次まとめます：
次にフィールドencoding：現在の要素の内容に応じて異なるエンコード方式を適用します。以下の通りです：
1、要素の内容が文字列の場合、encodingの値は以下の通りです：
00xx xxxx ：00で始まる場合は、その文字列の長さが6ビットを表現します。
01xx xxxx | xxxx xxxx ：01の先頭が、文字列の長さが14ビットを表現し、これは14ビットは大端形式で保存されます。
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10の先頭が、次の4バイトが文字列の長さを表すことを示します。これは32ビットは大端形式で保存されます。
2、要素の内容が数字の場合、encodingの値は以下の通りです：
1100 0000：数字が占める次の2バイトです。
1101 0000：数字が占める次の4バイトです。
1110 0000：数字が占める次の8バイトです。
1111 0000 ：数字が占める次の3バイトです。
1111 1110 ：数字が占める次の1バイトです。
1111 1111 ：圧縮リンクリストの最後の要素（特別なエンコード）
1111 xxxx ：後ろ4ビットは0~12の整数を表現します。00001110と1111の3種類が既に占めているため、ここでのxxxxの4バイトは0000に限定されます。1~1101に表現します。10進数に変換すると、数字1~13、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]
上記は16進数で表現された2、52つの要素で構成される圧縮リンクリストです。
次に、この圧縮リストの末尾に文字列要素Hello Worldを挿入します。まず、その文字列をどうエンコードするかを見てみましょう。約束されたエンコード規則に従って、まず前の要素の長さをバイトで表現します。ここでは前の要素は5、合計で2バイトを使用しますので、まず前の要素の長さ0を1バイトで表現します2、次に文字列のエンコードについて見てみましょう。追加する文字列の長さは11（スペースも含めます）をバイナリに変換すると、1011、文字列のエンコード規則に従って、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
二、圧縮リストziplistコマンドソースコード解析
上記のエンコード規則を理解した後、圧縮リストziplistの部分操作のソースコードを見てみましょう。この記事では、圧縮リストの基本原理を、リストの作成、要素の挿入、要素の削除、要素の検索の4つの操作でまとめます。
まずは作成について：
//zlbytes、zltail、zllenで構成される圧縮リストのヘッダサイズを定義します
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//圧縮リストを作成し、そのリストへのポインタを返します
unsigned char *ziplistNew(void) {
//ここでは+1これは尾要素が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;
}
圧縮リストの作成のロジックは非常にシンプルで、ヘッダとタイルを含む固定サイズのスペースを確保し、リストのコンテキストを初期化することです
作成と比較して、要素の追加のソースコードは非常に長くなります、理解しやすくするために、ソースコードを見る前に自分で要素の追加のロジックを整理しておきます
上記の3つのステップは主要なステップですが、それ以外には末尾ノードのオフセットを更新する、リストの要素数を変更するなどの操作もあります。もちろん、圧縮リストが配列に基づいているため、要素を挿入したり削除したりする際にはメモリコピーも避けられません
上記のステップをまとめると、次に一つずつソースコードを分析し始めます、長いので少しずつ見ていきましょう：
//以下の4つのパラメータはそれぞれ、圧縮リスト、挿入位置（新しい要素が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 < 4) {}}
nextdiff = 0;
forcelarge = 1;
}
//根据新计算出的数组大小进行扩容，由于新数组的地址可能会改变，因此这里记录旧的偏移量
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//在新数组上计算插入位置
p = zl+offset;
//如果新插入的元素不在链表末尾
if (p[0] != ZIP_END) {
//将新元素及其后续元素复制到新的数组中，-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 は後続要素の長さが変更されたことを示し、したがって、後続要素の後続要素を連鎖更新する必要があります
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);
}
//圧縮リストに保存される要素数+1
ZIPLIST_INCR_LENGTH(zl,1;
return zl;
}
挿入する要素のロジックを分析した後、深呼吸しました。本当に長くて、詳細もたくさんあります。
次に削除する要素のプロセスを見てみましょう。追加と比較して、削除は少し簡単です。現在の要素をクリアしてから、後続の要素を順次コピーします（これが配列とリストの二つのデータ構造の違いです）。次に、連鎖更新が必要かどうかを確認します。以下のコード：
//引数は以下の通り：圧縮リスト、削除する要素の初期位置、削除する要素の数
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++) {}}
//削除した合計長さを計算します
p += zipRawEntryLength(p);
//実際に削除された要素の数を計算します
deleted++;
}
//削除する必要がある要素のバイト数
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);
//削除する要素の後続要素が1個以上ある場合、新しい末尾要素のオフセットには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);
}
//配列のサイズを変更します
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) {
//2つの数字が等しい場合、要素のポインタを返します。
return p;
}
}
}
//スキップする必要がある要素の数をリセットします。
skipcnt = skip;
} else {
//要素をスキップします。
skipcnt--;
}
//次の要素を巡回します。
p = q; + len;
}
//リスト全体を巡回し、要素が見つかりませんでした。
return NULL;
}
ここで、圧縮リストの作成、追加、削除、検索の4つの基本操作の原理をまとめました。
第3章：圧縮リストziplistデータ構造のまとめ
ziplistの圧縮リストがRedisで非常に広範囲に使用されています。これはRedisで最も特徴的なデータ構造の一つです。このデータ構造の核は、記事の最初の部分でまとめたエンコード規則です。これらの内容を理解し、その後のソースコードを簡単に見て理解を深めることができます。
源コードの部分は実際に少し長過ぎます。本当に耐心が必要です。私が読んでいる過程でも頭が痛くなりました。源コードに興味がある場合は、私の方法に従って、まず特定の操作（例えば、上記で述べた要素の挿入）が必要なことがどれだけあるかを整理し、その後コードを見るとより理解しやすくなるでしょう。
最後に、一つ的小問題を残します。Redisのziplistがメモリ効率が非常に高いことを考えると、なぜユーザーに通常のリスト構造を提供する必要があるのでしょうか？
これは標準的な答えではありません。各人が異なる意見を持っています。
まとめ
これでこの記事のすべての内容が終わりました。この記事の内容が皆さんの学習や仕事に参考になることを願っています。何か疑問があれば、コメントを残して交流してください。ありがとう、呐喊チュートリアルのサポートに感謝します。
声明：この記事の内容はインターネットから取得され、著作権者に帰属します。インターネットユーザーによって自発的に貢献し、自己でアップロードされました。このサイトは所有権を持ちません。また、人間のエディタによって編集されていません。著作権侵害の内容が見つかった場合は、メールを送信してください：notice#oldtoolbag.com（メール送信時、#を@に置き換えてください。申し訳ありませんが、関連する証拠を提供し、一旦確認されると、このサイトは侵害された内容をすぐに削除します。）