Redis内部データ構造総括(4)quicklist

redis対外データ構造タイプlistの最下位はquicklistである
quicklist構造の定義

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;

Listがサポートする操作は
O(1)時間的複雑度のlpush:左側(すなわちリストヘッダ)にlpopを挿入する:左側(すなわちリストヘッダ)にrpushを削除する:右側(すなわちリストテール)にrpopを挿入する:右側(すなわちリストテール)に削除する
... O(N)複雑度のlindex:ある場所の要素linsertを取る:ある要素の前後に挿入する
...
両端での追加と削除を容易にする秩序あるリストであり、中間位置へのアクセスの時間的複雑さはO(N)であり、これは双方向チェーンテーブルの特徴である.
quicklistはziplistからなる双方向チェーンテーブルです.すなわちquicklistの各ノードはziplistである.
双方向チェーンテーブルは両端でpushとpopを行うのに便利ですが、メモリのオーバーヘッドが大きいです.
①各ノードは、データの保存に加えて2つのポインタを保存する.
②各ノードは個別のメモリブロックであり、アドレスが不連続であり、フラグメントが発生しやすい.
 
ziplistは連続したメモリであり、ストレージ効率が高い.しかし、修正が不便で、データが変動するたびにreallocが発生します.特にziplistが長い場合、reallocは大量のデータコピーを引き起こし、パフォーマンスを低下させる可能性があります.
redis.confの配置は、系ええが最大いくつかのデータ項目と両端にどれだけのノードが圧縮されていないかを表す.

list-max-ziplist-size -2
list-compress-depth 0

list-max-ziplist-size -2
正の値をとると、ノードにはziplistの長さといういくつかのデータ項目が含まれることを示します.負の値をとると、-1~-5しか取れません.
-5各ノードziplistのサイズ≦64 KBバイト(bytes)
-4                                              32
-3                                              16
-2 8(デフォルト)
-1                                                4
list-compress-depth 0
リストが長い場合、最もアクセス可能なデータは両端のデータであるため、メモリを節約して圧縮できるように、パラメータはquicklist両端が圧縮されないノード数を表し、採用した圧縮アルゴリズムはLZFであり、無損圧縮アルゴリズムである.
0非圧縮(デフォルト)
1 quicklistの両端にそれぞれ1つのノードが圧縮されない
...
n quicklist両端にそれぞれn個のノードが圧縮されない