Redis兩種結(jié)構(gòu) listpack 和 quicklist

按照順序，本來應(yīng)該先介紹 quicklist 的結(jié)構(gòu)，quicklist 在 7.0 之前的版本是由雙向鏈表和壓縮列表構(gòu)成的，但是在 7.0 版本已經(jīng)變成了由雙向鏈表和 listpack 實(shí)現(xiàn)，所以在這里我們先介紹一下 listpack 的結(jié)構(gòu)。

1、listpack

listpack 是替換 ziplist 的數(shù)據(jù)結(jié)構(gòu)，所以在結(jié)構(gòu)上兩者是有些相似的，listpack 的結(jié)構(gòu)如下：

| 總字節(jié)長(zhǎng)度 | entry個(gè)數(shù) | entry1 | entry2 | ... | entryN | end |

相比 ziplist，listpack 去除了到尾部節(jié)點(diǎn)，也就是到 entryN 的偏移量，但保留了其他屬性。

對(duì)于單個(gè) entry 元素，其結(jié)構(gòu)如下：

| encoding | content | length |

encoding 表示 content 的編碼，endocing 表示實(shí)際存儲(chǔ)的內(nèi)容，length 表示該 entry 的長(zhǎng)度

避免連鎖更新

使用 listpack 替代 ziplist 的一個(gè)好處是避免了連續(xù)更新的問題。

因?yàn)?ziplist 的每個(gè)元素都有一個(gè)屬性用于保存前一個(gè)節(jié)點(diǎn)元素的長(zhǎng)度，因此前一個(gè)節(jié)點(diǎn)修改后會(huì)可能需要修改后一個(gè)節(jié)點(diǎn)的屬性，但是 listpack 沒有這個(gè)關(guān)聯(lián)關(guān)系，從而避免了影響后續(xù)元素的長(zhǎng)度，也因此避免了連鎖更新的問題。

獲取最后一個(gè)節(jié)點(diǎn)

雖然 listpack 沒有了指向尾部節(jié)點(diǎn)的偏移量，但是同樣可以快速找到 listpack 的尾部節(jié)點(diǎn)，方式是通過 總字節(jié)長(zhǎng)度屬性的值，可以直接獲取到 listpack 的尾部，然后根據(jù) entry 元素尾部的 length 屬性，就可以找到尾部 entry 的起始地址了。

2、 quicklist

在 Redis 3.2 版本，列表對(duì)象的底層實(shí)現(xiàn)變成了由 quicklist 實(shí)現(xiàn)，quicklist 實(shí)際上是壓縮列表和雙向鏈表的組合結(jié)構(gòu)，因?yàn)?quicklist 就是一個(gè)鏈表，而鏈表中每一個(gè)元素就是壓縮列表。

而在 Redis 7.0 版本，quicklst 變成了由雙向鏈表和 listpack 構(gòu)成的結(jié)構(gòu)。

這里直接介紹 quicklist 由雙向鏈表和 listpack 構(gòu)成的結(jié)構(gòu)。

quicklist 的結(jié)構(gòu)和雙向鏈表的結(jié)構(gòu)類似：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count; 
    unsigned long len; 
    ...
} quicklist;

對(duì)于一個(gè) quicklist，它也有指向 quicklist 的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的指針，如結(jié)構(gòu)中的 head 和 tail。

count 屬性統(tǒng)計(jì)每個(gè) quicklist 節(jié)點(diǎn)的 listpack 總數(shù)量的屬性

len 則是統(tǒng)計(jì) quicklist 中 quicklistNode 的數(shù)量的屬性。

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             
    unsigned int count : 16; 
    ...
} quicklistNode;

對(duì)于一個(gè) quicklistNode，擁有指向前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的指針，還有指向其下 listpack 的 entry，以及 sz 表示該 listpack 的總字節(jié)長(zhǎng)度，count 屬性則表示該 listpack 中包含的元素個(gè)數(shù)。

以上就是Redis數(shù)據(jù)結(jié)構(gòu)之listpack和quicklist使用學(xué)習(xí)的詳細(xì)內(nèi)容，更多關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)listpack quicklist的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論