prinsip senarai nota kajian redis

ListNode:

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

Senarai:

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: Ciri-ciri senarai terpaut

Akiklik dwiarah: nod senarai terpaut Dengan pacuan roda hadapan Kerumitan masa untuk mendapatkan nod pendahulu dan nod pengganti oleh penunjuk pengganti ialah O(1 Penunjuk pendahulu nod kepala dan penunjuk pengganti nod ekor kedua-duanya menghala ke NULL, dan akses kepada nod). senarai terpaut berakhir dengan NULL.

Pembilang panjang: Kerumitan masa untuk mendapatkan bilangan nod melalui atribut len ​​struktur Senarai ialah O(1).
Memandangkan senarai masih menghadapi masalah peruntukan memori yang tidak berterusan dan pemecahan memori, adakah terdapat cara untuk mengoptimumkan ingatan mereka?

redis compressed list

ZipList bukanlah struktur data asas, ia adalah struktur storan data yang direka oleh Redis sendiri. Ia agak serupa dengan tatasusunan, menyimpan data melalui ruang ingatan berterusan.

Berbeza daripada tatasusunan, ia membenarkan elemen senarai yang disimpan untuk menduduki ruang memori yang berbeza. Apabila ia datang kepada perkataan mampatan, perkara pertama yang semua orang mungkin fikirkan ialah menjimatkan memori. Sebab mengapa struktur storan ini menjimatkan memori adalah kerana ia dibandingkan dengan tatasusunan.

Kita semua tahu bahawa tatasusunan memerlukan saiz ruang storan yang sama untuk setiap elemen Jika kita ingin menyimpan rentetan dengan panjang yang berbeza, kita mesti menggunakan ruang storan yang diduduki oleh rentetan panjang maksimum sebagai setiap elemen tatasusunan rentetan. Saiz ruang (jika ia adalah 50 bait).

Jadi apabila menyimpan rentetan kurang daripada 50 bait panjang dalam nilai nombor aksara, sebahagian daripada ruang storan akan dibazirkan. Kelebihan

array ialah ia menduduki ruang yang berterusan dan boleh menggunakan cache CPU dengan baik untuk mengakses data dengan cepat.

Jika kita ingin mengekalkan kelebihan array ini dan menjimatkan ruang storan, maka kita boleh memampatkan tatasusunan:

Namun, terdapat masalah, kita tidak tahu ketika melintasi mampat senarai Apakah saiz memori yang diduduki oleh setiap elemen, jadi adalah mustahil untuk mengira kedudukan permulaan tertentu bagi elemen seterusnya.

Tetapi kemudian saya berfikir mengenainya, jika kita boleh mempunyai panjang setiap elemen sebelum mengaksesnya, bukankah masalah ini akan diselesaikan?

Seterusnya, mari lihat cara Redis menggabungkannya dengan melaksanakan ZipList sambil mengekalkan kelebihan tatasusunan dan menjimatkan memori.

• 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

Terdapat juga medan pengisian, yang bermaksud kapasiti maksimum setiap node quicknode. juga dikonfigurasikan kepada nilai lain. Sebagai contoh, apabila nilai ialah 5, senarai zip setiap nod quicklistNode mengandungi paling banyak 5 item data

Saiz maksimum nod ziplist ialah 4kbziplist nod Saiz maksimum ialah 32kb

nilai	makna
- 2	Nod senarai zip maksimum ialah 8kb
-3	nod maksimum zip
	-4
-5	saiz maksimum nod senarai zip ialah 64kb

disediakan konfigurasi?

• Semakin pendek senarai zip, semakin banyak pemecahan memori akan berlaku, menjejaskan kecekapan storan. Apabila senarai zip hanya menyimpan satu elemen, senarai pantas akan merosot menjadi senarai terpaut dua kali Lebih panjang senarai zip, lebih sukar untuk memperuntukkan ruang memori berterusan yang besar untuk senarai zip, yang akan menyebabkan banyak blok kecil ruang memori akan diduduki. . Membazir, apabila senarai pantas hanya mempunyai satu nod dan semua elemen disimpan dalam senarai zip, senarai pantas menjadi senarai zip

• Kesimpulan

Walaupun kami tidak memahami sepenuhnya kod sumbernya, kami juga boleh lulus artikel ini Mari kita biasakan dengan idea reka bentuk redis. Dan ketahui cara ia dioptimumkan langkah demi langkah. Mari kita dapatkan idea umum tentang prestasi.