Redis 研究ノート - リストの原則

#基本関数のリスト

##説明#BLPOP key1、key2、... タイムアウト##移動して入手##LPUSHX キーの値##LRANGE キー srart stop##

グラフの出典: https://www.cnblogs.com/amyzhu/p/13466311.html

単一リンク リスト

Redis のリストの実装を学ぶ前に、まず単一リンク リストの実装方法を見てみましょう:

それぞれのノードには、次のノードを指す後方ポインタ (参照) があり、最後のノードは終了を示す NULL を指し、開始を示す最初のノードを指す Head (ヘッド) ポインタがあります。

これと同様ですが、新規作成と削除には O(1) のみが必要です。 ですが、検索には O(n) 時間がかかります。逆検索はできないため、検索を開始する必要があります。見逃したら最初から。

ノードを追加します:

#ノードの削除:

##二重リンク リスト

二重リンク リスト (二重リンク リストとも呼ばれる) はリンク リストの一種であり、その各データ ノードには 2 つのポインタがあり、それぞれ直接後続ノードと直接先行ノードを指します。したがって、二重リンク リスト内の任意のノードから開始して、その先行ノードおよび後続ノードに簡単にアクセスできます。

機能:

1. 挿入または削除するたびに特定のノードが選択された場合、2 つではなく 4 つのノード参照を処理する必要があるため、一方向リンク リストと比較すると実装が難しくなります。 , 必然的にメモリを占有します スペースが大きくなります。

2. #最初から最後までトラバースでき、最後から最初までトラバースできます

##これにより、redis が前後の両方を横断できるという問題が解決されるようです。

3. 次に、

redis のリンク リスト

がどのように処理されるかを見てみましょう:

構造定義のソース コードを見てみましょう

ListNode:

typedef struct listNode
{
    // 前驱节点
    struct listNode *prev;
    // 后继节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

List:

typedef struct listNode
{
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void *(*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr,void *key)
} list;

redis リンク リストの特徴:

• 双方向非巡回: リンク リスト ノードには、ノードのノードを取得するための先行ポインタと後続ポインタがあります。先行ノードと後続ノードの時間計算量はO(1)であり、先頭ノードの先行ポインタと末尾ノードの後続ポインタはともにNULLを指し、連結リストへのアクセスはNULLで終了する。

• Length カウンタ: List 構造体の len 属性を通じてノード数を取得する時間計算量は O(1) です。

list には依然として不連続なメモリ割り当てとメモリの断片化の問題があるため、メモリを最適化する方法はあるでしょうか?

redis 圧縮リスト

ZipList は基本的なデータ構造ではなく、Redis 自体によって設計されたデータ ストレージ構造です。これは配列に似ており、連続したメモリ空間を通じてデータを保存します。

配列とは異なり、格納されたリスト要素が異なるメモリ空間を占有することができます。圧縮という言葉に関しては、誰もが最初にメモリの節約を思い浮かべるかもしれません。このストレージ構造がメモリを節約する理由は、それが配列と比較されるためです。

配列では各要素の記憶領域が同じサイズである必要があることは誰もが知っていますが、異なる長さの文字列を格納したい場合は、その文字列が占有している記憶領域を使用する必要があります。文字列配列の各要素の記憶領域のサイズ (50 バイトの場合)。

したがって、文字値が 50 バイト未満の文字列を保存すると、記憶領域の一部が無駄になります。

配列の利点は、連続した領域を占有し、CPU キャッシュを有効に活用してデータに迅速にアクセスできることです。

アレイのこの利点を維持し、ストレージ領域を節約したい場合は、アレイを圧縮できます:

しかし、問題があり、圧縮されたリストを走査するとき、各要素が占有するメモリ サイズがわからないため、次の要素の特定の開始位置を計算できません。

しかし、考えてみたら、各要素にアクセスする前にその長さを知ることができれば、この問題は解決するのではないか？

次に、Redis が ZipList を実装することで配列の利点を維持し、メモリを節約する方法を見てみましょう。

• zlbytes：压缩列表的字节长度，是uint32_t类型，占4字节，因此压缩列表最多有232-1字节，可以通过该值计算zlend的位置，也可以在内存重新分配的时候使用。

• zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，是uint32_t类型，占4字节，可以通过该值快速定位到列表尾元素的位置。

• zllen：压缩列表元素的个数，是uint16_t类型，占2字节，表示最多存储的元素个数为216-1=65 535，如果需要计算总数量，则需要遍历整个压缩列表。

• entryx：压缩列表存储的元素，既可以是字节数组，也可以是整数，长度不限。

• zlend：压缩列表的结尾，是uint8_t类型，占1字节，恒为0xFF。

• previous_entry_length：表示前一个元素的字节长度，占1字节或者5字节，当前元素的长度小于254时用1字节，大于等于254时用5字节，previous_entry_length 字段的第一个字节固定是0xFE，后面的4字节才是真正的前一个元素的长度。

• encoding：表示元素当前的编码，有整数或者字节数。为了节省内存，encoding字段长度可变。

• content：表示当前元素的内容。

ZipList变量的读取和赋值都是通过宏来实现的，代码片段如下：

//返回整个压缩列表的总字节
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

//返回压缩列表的tail_offset变量，方便获取最后一个节点的位置
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

//返回压缩列表的节点数量
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

//返回压缩列表的表头的字节数
//（内存字节数zlbytes，最后一个节点地址ztail_offset,节点总数量zllength）
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

//返回压缩列表最后结尾的字节数
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

//返回压缩列表首节点地址
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

//返回压缩列表尾节点地址
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

//返回压缩列表最后结尾的地址
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

对此，可以通过定义的结构体和对应的操作定义知道大概 redis 设计 压缩list 的思路；

这种方式虽然节约了空间，但是会存在每次插入和创建存在内存重新分配的问题。

quicklist

quicklist是Redis 3.2中新引入的数据结构，能够在时间效率和空间效率间实现较好的折中。Redis中对quciklist的注释为A doubly linked list of ziplists。顾名思义，quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。

当ziplist节点个数过多，quicklist退化为双向链表，一个极端的情况就是每个ziplist节点只包含一个entry，即只有一个元素。当ziplist元素个数过少时，quicklist可退化为ziplist，一种极端的情况就是quicklist中只有一个ziplist节点。

quicklist 结构定义:

typedef struct quicklist {
    // 指向quicklist的首节点
    quicklistNode *head;
    // 指向quicklist的尾节点
    quicklistNode *tail;
    // quicklist中元素总数
    unsigned long count;        /* total count of all entries in all ziplists */
    // quicklistNode节点个数
    unsigned long len;          /* number of quicklistNodes */
    // ziplist大小设置，存放list-max-ziplist-size参数的值
    int fill : 16;              /* fill factor for individual nodes */
    // 节点压缩深度设置，存放list-compress-depth参数的值
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: 4;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

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;

redis为了节省内存空间，会将quicklist的节点用LZF压缩后存储，但这里不是全部压缩，可以配置compress的值，compress为0表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩；compress如果是1，表示从两端开始，有1个节点不做LZF压缩。compress默认是0(不压缩)，具体可以根据你们业务实际使用场景去配置。

redis 的配置文件可以配置该参数

list-compress-depth 0

コマンド
リストの	#最初の要素を削除して取得します。リストに要素がない場合はブロックされます。リストはタイムアウトになるか、要素がポップされるまで待機します。 ##BRPOP key1 [key2 ] タイムアウト
リストの最後の要素 リストに要素がない場合、リストは待機がタイムアウトになるかポップアップ要素が表示されるまでブロックされます。見つかった。
#BRPOPLPUSH ソース宛先タイムアウト	リスト A からポップポップされた要素を別のリストに挿入して返す値。リストに要素がない場合、待機がタイムアウトになるかポップ可能な要素が見つかるまで、リストはブロックされます。
LIndex key index	通过索引获取列表中的元素
Linsert key before/after pivot value	在列表的元素前或者后插入元素
LLEN key	获取列表长度
LPOP key	移出并获取列表的第一个元素
LPUSH キーの値 1、値 2、…	#1 つまたは複数の値がリストの先頭に挿入されます
##既存のリストの先頭に値を挿入
#リストの指定範囲内の要素を取得	##LREM キー カウント値
リスト要素の削除	##LSET キー インデックス値
インデックスによるリスト要素の値の設定	LTRIMキー スタート ストップ	リストのプルーニングとは、指定された範囲内の要素のみがリストに保持され、指定された範囲内にない要素が削除されることを意味します。インデックスは 0 から始まり、範囲は 0 を含みます。
RPOP キー	リストを削除最後の # 要素、戻り値は削除された要素です
RPOPPUSHソース宛先	リストの #最後の要素 # を削除して置き換えます。要素は次のとおりです。別のリストに追加され、
RPUSH キー value1 value2 ……	# を返します。 #リストの最後に 1 つ以上の値を追加します
##RPUSHX キーの値	既存のリストに値を追加する

##意味0

##値
##特別な値は圧縮なしを意味します	1
##クイックリストの両端に 1 つあります。ノードは圧縮されていません。中間ノードは圧縮されます	#2
クイックリストの両端の 2 つのノードは圧縮されておらず、中央のノードは圧縮されています	#n	クイックリストの両端には圧縮されていないノードが n 個あり、中央のノードは圧縮されています

各クイックノード ノードの最大容量を意味する塗りつぶしフィールドもあります。 、異なる値それぞれには異なる意味があり、デフォルトは -2 ですが、もちろん他の値に設定することもできます;

##list-max-ziplist-size -2

値が正の数の場合、quicklistNode ノードのジップリストの長さを示します。たとえば、この値が 5 の場合、各 QuicklistNode ノードの ziplist には最大 5 つのデータ項目が含まれます。

値が負の数、quicklistNode ノードの ziplist の長さがバイト数に応じて制限されていることを示します。オプションの値は -1 ～ -5 です。

##-2-3##-4

#値	意味
#-1	ziplist ノードの最大数ジップリスト ノードの最大数は 4kb
## です。 # 8kb
ziplist ノードの最大数は16kb
##ziplist ノードの最大値は 32kb
#-5	##ジップリスト ノードの最大サイズは 64kb

なぜ構成が提供されるのですか?

• #zipリストが短いほど、より多くのメモリ断片が発生し、ストレージ効率に影響します。ジップリストに 1 つの要素のみが格納されている場合、クイックリストは二重リンク リストに縮退します。ジップリストのメモリ スペース。値が大きいほど、メモリ スペースの小さなブロックがより多く浪費されます。クイックリストにノードが 1 つしかなく、すべての要素がジップリストに格納されている場合、クイックリストはジップリストに縮退します。

#結論

• ##ソース コードを完全に理解しているわけではありませんが、Redis の設計アイデアについて理解することはできます。この記事。そしてそれがどのように段階的に最適化されるかを理解してください。パフォーマンスの一般的な概念を理解しましょう。

以上がRedis 研究ノート - リストの原則の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。