Redis快速表、圧縮表、双方向チェーン表（重点的にquicklistを紹介する）
前言
最近『Redisのデザインと実現』という本を読んでいますが、本当に良かったです。あっという間に夢中になりました。ありがとうございます。しかし、勉強している時に発見された問題は、サーバーにインストールされているのはRedis 5.09バージョンで、著者が紹介しているのはRedis 3.0バージョンで、最初の部分がデータ構造と対象チャプタの間にいくつかの違いがあります。つまり、redis外部に露出されたリスト構造の下で使用されるデータ構造の問題です。本には記録がないので、インターネットで資料を調べて勉強しました。自分でまとめて自分のノートにします。
違います
この違いは、リリースの前に、zplistとlinkedlistコードをリストキーとして使用しています。その後、Qicklistというデータ構造を採用して、その下に実現します。
zplistを選ぶ時：リストオブジェクトに保存されているすべての文字列要素の長さは64バイト以下である。 リストオブジェクトに保存されている要素量は512個未満の です。
上のはzplistを下の層として選ぶために必要な条件です。満足していないなら、linkedlistを下の層として使用します。
私がインストールする時はredis 5.09バージョンですので、上のいくつかの命令の実行結果は違います。
zplistとlinkedlistは紹介しません。本にあります。quicklistを見に来ました。
quicklistの実現もzplistとlinkedlistに依存して実現され、二つの構造の結合である。それはzplistをセグメント化して記憶します。つまり、quicklistNodeノードに分けて保存します。各quicklistNodeはzplistを指し、次いでquicklistNodeの間は双方向ポインタで接続されています。大まかな構造を見てみましょう。
この構造を見て疑問があるかもしれません。この構造はどういう意味ですか？なぜ一部のノードはzplistで、あるものはquicklistZFですか？ どうしてquicklistの頭と尾はそれぞれ2つのノードがzplistで、残りの中間はquicklistZFですか？ はなぜ、各quicklistNodeノードのzplist内部のデータの個数が一致しないのですか？ なぜ底のデータ構造をquicklistに最適化しますか？
上の問題を解決する前に、まず第一の問題を解決します。つまりredisはなぜリストキーの下のデータ構造をquicklistに最適化しますか？
実はこの原因は二つの面から考えられます。 zplistという構造で、内部のデータ記憶は連続的な空間です。そうすると、メモリの大きな部分が必要です。例えば、私達は多くのデータを記憶したいですが、メモリには要求に合った連続的な記憶空間がなく、多くの不連続な小さな空間があります。 はlinkedlistという構造について説明します。データの保存は連続を要求しないので、上の弊害を避けることができます。しかし、このようにして以来、各ノードは一つのメモリを割り当てています。それは大量のメモリの断片を引き起こす可能性があります。 以上の二つの考えから、redisは3.2バージョン以降にこの状況を最適化し、quicklistというデータ構造が出てきました。quicklistは実はセグメントのzplistです。なぜこのように言いますか？実はquicklist格納データの基本単位はquicklistNodeであり、各quicklistNodeのコンテンツエリアはzplistデータ構造で記憶されています。つまり上の図のように展示されています。
なぜ各quicklistNodeノードのzplist内部のデータの個数が一致しないですか？
今はquicklistに転化しましたが、まだ考慮が必要です。quicklistNodeのzplistの内容はどうなりますか？一つのzipistはどれぐらいのデータを保存しますか？上の二つの点と同じ考えです。 zplistの中のコンテンツの割り当てが少ないと、つまりlinkedlistの方向に発展し、多くのメモリの断片が発生する可能性があります。 ですが、zplist内のコンテンツの割り当てが多くなれば、問題も発生します。大きなメモリ空間が必要です。 redisデザイナーはもう私達に考えてくれました。その構成ファイルにはこのようなパラメータがあります。
この構成を見て、このパラメータを説明します。正の値を設定することも、負の値を設定することもできます。
正数を取るときは、データの個数に応じてquicklistノードのzipplist長を定義することを示しています。例えば、私達は4に設定します。各zipplistのデータ項目は最大5つを超えてはいけないと説明しています。
負の数を取るとき、占有バイトによってquicklsitノード上のzplist長を定義することを表します。このとき、-1から-5までの5つの値しか取れません。各値の意味は以下の通りです。
1）、−5：各quicklistノードのzplistサイズは64 kbを超えてはいけません。1 kb==1024 byte)
2)、-4：各quicklsitノードのzplistサイズは32 kbを超えてはいけません。
3)、-3：各quicklsitノードのzplistサイズは16 kbを超えてはいけません。
4)、-2：各quicklsitノードのzplistサイズは8 kbを超えてはいけません。
5)、-1：各quicklsitノードのzplistサイズは4 kbを超えてはいけません。
だから問題が発生します。zplistメモリにはデータの個数が一致しないという問題があります。自分でパラメータ値を設定することもできます。
この構造はどういう意味ですか？なぜ一部のノードはzplistで、あるものはquicklistZFですか？
ここにもう一つの構成パラメータが現れました。
このパラメータの評価の意味は以下の通りです。
0：特殊な値です。圧縮しないという意味です。これはredisのデフォルトです。
1：quicklistの両端にそれぞれ一つのノードが圧縮されないことを示し、中間ノードが圧縮を行う。
2：quicklistの両端に2つのノードが圧縮されないことを示し、中間ノードが圧縮を行う。
3：quicklistの両端に3つのノードが圧縮されないことを示し、中間ノードが圧縮する…
これをもって類推する
つまり問題が発生します。両端のノードはzplistで、中間ノードはquicklistZFです。
上のredisプロファイルのデフォルトの構成を見てみます。
ソースの構造を簡単に理解する
上の図を通して簡単にquicklistの保存方法を説明します。下の階には二つの構造があります。一つはquicklistNodeです。下は私が探していたソースコードです。簡単に見られます。
締め括りをつける
全体としてquicklistはzplistとlinkedlistの両方の利点の組み合わせであり、redisのリストキーの下のメモリをさらに最適化する。
この記事はRedis快速表、圧縮表、双方向チェーン表（Qicklistを重点的に紹介します）について紹介しています。もっと関連するRedis快速表、圧縮表、双方向チェーン表の内容は以前の文章を検索してください。または以下の関連記事を引き続きご覧ください。これからもよろしくお願いします。
最近『Redisのデザインと実現』という本を読んでいますが、本当に良かったです。あっという間に夢中になりました。ありがとうございます。しかし、勉強している時に発見された問題は、サーバーにインストールされているのはRedis 5.09バージョンで、著者が紹介しているのはRedis 3.0バージョンで、最初の部分がデータ構造と対象チャプタの間にいくつかの違いがあります。つまり、redis外部に露出されたリスト構造の下で使用されるデータ構造の問題です。本には記録がないので、インターネットで資料を調べて勉強しました。自分でまとめて自分のノートにします。
違います
この違いは、リリースの前に、zplistとlinkedlistコードをリストキーとして使用しています。その後、Qicklistというデータ構造を採用して、その下に実現します。
redis3.2 ：zplistとlinkedlistをリストキーとして使って下の階に実現する時、彼らの間に選択基準があります。zplistを選ぶ時：
上のはzplistを下の層として選ぶために必要な条件です。満足していないなら、linkedlistを下の層として使用します。
127.0.0.1:6379> rpush blah "hello" "world" "again"
3
127.0.0.1:6379> object encoding blah
ziplist
127.0.0.1:6379> rpush blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
4
127.0.0.1:6379> object encoding blah
linkedlist
redis3.2 ：これはquicklistというデータ構造に関連していますが、本には記録がないので、資料を調べて自分のブログにまとめました。私がインストールする時はredis 5.09バージョンですので、上のいくつかの命令の実行結果は違います。
127.0.0.1:6379> rpush blah "hello" "world" "again"
3
127.0.0.1:6379> object encoding blah
quicklist
127.0.0.1:6379> rpush blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
4
127.0.0.1:6379> object encoding blah
quicklist
zplistとlinkedlistは紹介しません。本にあります。quicklistを見に来ました。
quicklistの実現もzplistとlinkedlistに依存して実現され、二つの構造の結合である。それはzplistをセグメント化して記憶します。つまり、quicklistNodeノードに分けて保存します。各quicklistNodeはzplistを指し、次いでquicklistNodeの間は双方向ポインタで接続されています。大まかな構造を見てみましょう。
この構造を見て疑問があるかもしれません。
上の問題を解決する前に、まず第一の問題を解決します。つまりredisはなぜリストキーの下のデータ構造をquicklistに最適化しますか？
実はこの原因は二つの面から考えられます。
なぜ各quicklistNodeノードのzplist内部のデータの個数が一致しないですか？
今はquicklistに転化しましたが、まだ考慮が必要です。quicklistNodeのzplistの内容はどうなりますか？一つのzipistはどれぐらいのデータを保存しますか？上の二つの点と同じ考えです。
この構成を見て、このパラメータを説明します。正の値を設定することも、負の値を設定することもできます。
正数を取るときは、データの個数に応じてquicklistノードのzipplist長を定義することを示しています。例えば、私達は4に設定します。各zipplistのデータ項目は最大5つを超えてはいけないと説明しています。
負の数を取るとき、占有バイトによってquicklsitノード上のzplist長を定義することを表します。このとき、-1から-5までの5つの値しか取れません。各値の意味は以下の通りです。
1）、−5：各quicklistノードのzplistサイズは64 kbを超えてはいけません。1 kb==1024 byte)
2)、-4：各quicklsitノードのzplistサイズは32 kbを超えてはいけません。
3)、-3：各quicklsitノードのzplistサイズは16 kbを超えてはいけません。
4)、-2：各quicklsitノードのzplistサイズは8 kbを超えてはいけません。
5)、-1：各quicklsitノードのzplistサイズは4 kbを超えてはいけません。
だから問題が発生します。zplistメモリにはデータの個数が一致しないという問題があります。自分でパラメータ値を設定することもできます。
この構造はどういう意味ですか？なぜ一部のノードはzplistで、あるものはquicklistZFですか？
ここにもう一つの構成パラメータが現れました。
list-max-ziplist-size実は、チェーンが長い時、一番頻繁にアクセスするのは両端のデータで、中間訪問の頻度が低いので、中間部分のノードを圧縮して、スペースを節約できます。上で述べたlist-compless-depthはこれをセットしに来ました。このパラメータの評価の意味は以下の通りです。
0：特殊な値です。圧縮しないという意味です。これはredisのデフォルトです。
1：quicklistの両端にそれぞれ一つのノードが圧縮されないことを示し、中間ノードが圧縮を行う。
2：quicklistの両端に2つのノードが圧縮されないことを示し、中間ノードが圧縮を行う。
3：quicklistの両端に3つのノードが圧縮されないことを示し、中間ノードが圧縮する…
これをもって類推する
つまり問題が発生します。両端のノードはzplistで、中間ノードはquicklistZFです。
上のredisプロファイルのデフォルトの構成を見てみます。
ソースの構造を簡単に理解する
上の図を通して簡単にquicklistの保存方法を説明します。下の階には二つの構造があります。一つはquicklistNodeです。下は私が探していたソースコードです。簡単に見られます。
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;
unsigned int sz; /* ziplist size in bytes */
unsigned int count : 16; /* count of items in ziplist */
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
typedef struct quicklistLZF {
unsigned int sz; /* LZF size in bytes*/
char compressed[];
} quicklistLZF;
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* total count of all entries in all ziplists */
unsigned int len; /* number of quicklistNodes */
int fill : 16; /* fill factor for individual nodes */
unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;
締め括りをつける
全体としてquicklistはzplistとlinkedlistの両方の利点の組み合わせであり、redisのリストキーの下のメモリをさらに最適化する。
この記事はRedis快速表、圧縮表、双方向チェーン表（Qicklistを重点的に紹介します）について紹介しています。もっと関連するRedis快速表、圧縮表、双方向チェーン表の内容は以前の文章を検索してください。または以下の関連記事を引き続きご覧ください。これからもよろしくお願いします。