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

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

単一リンク リスト

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

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

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

ノードを追加します:

#ノードの削除:

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

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

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

3. 次に、

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

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

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