日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比南豐網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式南豐網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋南豐地區(qū)。費用合理售后完善，10年實體公司更值得信賴。

1、Redis List 是什么

作為 Java 開發(fā)者的你，看到這個詞并不陌生。在 Java 開發(fā)中幾乎每天都會使用這個數(shù)據(jù)結(jié)構(gòu)。

Redis 的 List 與 Java 中的 LinkedList 類似，是一種線性的有序結(jié)構(gòu)，可以按照元素被推入列表中的順序來存儲元素，能滿足先進先出的需求，這些元素既可以是文字數(shù)據(jù)，又可以是二進制數(shù)據(jù)。

你可以把他當做隊列、棧來使用。

2、修煉心法

我叫 Redis，在 C 語言中，并沒有現(xiàn)成的鏈表結(jié)構(gòu)，所以 antirez 為我專門設(shè)計了一套實現(xiàn)方式。

關(guān)于 List 類型的底層數(shù)據(jù)結(jié)構(gòu)，可謂英雄輩出，antirez 大佬一直在優(yōu)化，創(chuàng)造了多種數(shù)據(jù)結(jié)構(gòu)來保存。

從一開始早期版本使用 linkedlist（雙端列表）和 ziplist（壓縮列表）作為 List 的底層實現(xiàn)，到 Redis 3.2 引入了由 linkedlist + ziplist 組成的 quicklist，再到 7.0 版本的時候使用 listpack 取代 ziplist。

MySQL：“為何弄了這么多數(shù)據(jù)結(jié)構(gòu)呀？”

antirez 所做的這一切都是為了在內(nèi)存空間開銷與訪問性能之間做取舍和平衡，跟著我去吃透每個類型的設(shè)計思想和不足，你就明白了。

linkedlist（雙端列表）

在 Redis 3.2 版本之前，List 的底層數(shù)據(jù)結(jié)構(gòu)由 linkedlist 或者 ziplist 實現(xiàn)，優(yōu)先使用 ziplist 存儲。

當列表對象滿足以下兩個條件的時候，List 將使用 ziplist 存儲，否則使用 linkedlist。

• List 的每個元素的占用的字節(jié)小于 64 字節(jié)。
• List 的元素數(shù)量小于 512 個。

鏈表的節(jié)點使用 adlist.h/listNode結(jié)構(gòu)來表示。

typedef struct listNode {
    // 前驅(qū)節(jié)點
    struct listNode *prev;
    // 后驅(qū)節(jié)點
    struct listNode *next;
    // 指向節(jié)點的值
    void *value;
} listNode;

listNode 之間通過 prev 和 next 指針組成雙端鏈表。除此之外，我還提供了 adlist.h/list 結(jié)構(gòu)提供了頭指針 head、尾指針 tail 以及一些實現(xiàn)多態(tài)的特定函數(shù)。

typedef struct list {
    // 頭指針
    listNode *head;
    // 尾指針
    listNode *tail;
    // 節(jié)點值的復(fù)制函數(shù)
    void *(*dup)(void *ptr);
    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);
    // 節(jié)點值比對是否相等
    int (*match)(void *ptr, void *key);
    // 鏈表的節(jié)點數(shù)量
    unsigned long len;
} list;

linkedlist 的結(jié)構(gòu)如圖 2-5 所示。

Redis 的鏈表實現(xiàn)的特性總結(jié)如下。

• 雙端：鏈表節(jié)點帶有 prev 和 next 指針，獲取某個節(jié)點的前置節(jié)點和后繼節(jié)點的復(fù)雜度都是 O(1)。
• 無環(huán)：表頭節(jié)點的 prev 指針和尾節(jié)點的 next 指針都指向 NULL，對鏈表的訪問以 NULL 為結(jié)束。
• 帶表頭指針和表尾指針：通過 list 結(jié)構(gòu)的 head 指針和 tail 指針，程序獲取鏈表的頭節(jié)點和尾節(jié)點的復(fù)雜度為 O(1)。
• 使用 list 結(jié)構(gòu)的 len 屬性來對記錄節(jié)點數(shù)量，獲取鏈表中節(jié)點數(shù)量的復(fù)雜度為 O(1)。

MySQL：“看起來沒啥問題呀，為啥還要 ziplist 呢？”

你知道的，我在追求快和節(jié)省內(nèi)存的方向上無所不及，有兩個原因?qū)е铝?ziplist 的誕生。

• 普通的 linkedlist 有 prev、next 兩個指針，當存儲數(shù)據(jù)很小的情況下，指針占用的空間會超過數(shù)據(jù)占用的空間，這就離譜了，是可忍孰不可忍。
• linkedlist 是鏈表結(jié)構(gòu)，在內(nèi)存中不是連續(xù)的，遍歷的效率低下。

ziplist（壓縮列表）

為了解決上面兩個問題，antirez 創(chuàng)造了 ziplist 壓縮列表，是一種內(nèi)存緊湊的數(shù)據(jù)結(jié)構(gòu)，占用一塊連續(xù)的內(nèi)存空間，提升內(nèi)存使用率。

當一個列表只有少量數(shù)據(jù)的時候，并且每個列表項要么是小整數(shù)值，要么就是長度比較短的字符串，那么我就會使用 ziplist 來做 List 的底層實現(xiàn)。

ziplist 中可以包含多個 entry 節(jié)點，每個節(jié)點可以存放整數(shù)或者字符串，結(jié)構(gòu)如圖 2-6 所示。

• zlbytes，占用 4 個字節(jié)，記錄了整個 ziplist 占用的總字節(jié)數(shù)。
• zltail，占用 4 個字節(jié)，指向最后一個 entry 偏移量，用于快速定位最后一個 entry。
• zllen，占用 2 字節(jié)，記錄 entry 總數(shù)。
• entry，列表元素。
• zlend，ziplist 結(jié)束標志，占用 1 字節(jié)，值等于 255。

因為 ziplist 頭尾元數(shù)據(jù)的大小是固定的，并且在 ziplist 頭部 zllen 記錄了最后一個元素的位置，所以，當在 ziplist 中查找第一個或最后一個元素的時候，能以 O(1) 時間復(fù)雜度找到。

而查找中間元素時，只能從列表頭或者列表尾遍歷，時間復(fù)雜度就是 O(N)。

接下來看真正存儲數(shù)據(jù)的 entry 結(jié)構(gòu)長啥樣。

正常來說有三部分構(gòu)成  。

prevlen

記錄前一個 entry 占用字節(jié)數(shù)，能實現(xiàn)逆序遍歷就是靠這個字段確定往前移動多少字節(jié)拿到上一個 entry 首地址。

這部分會根據(jù)上一個 entry 的長度進行變長編碼（為了節(jié)省內(nèi)存操碎了心），變長方式如下。

• 前一個 entry 的字節(jié)大小小于 254（255 用于 zlend），prevlen 長度為 1 字節(jié)，值等于上一個 entry 的長度。
• 前一個 entry 的字節(jié)大小大于等于 254，prevlen 占用 5 字節(jié)，第一個字節(jié)設(shè)置為 254 作為一個標識，后面四字節(jié)組成一個 32 位的 int 值，用于存放上一個 entry 的字節(jié)長度。

encoding

簡言之用于表示當前 entry 的類型和長度，當前 entry 的長度和值是根據(jù)保存的是 int 還是 string 以及數(shù)據(jù)的長度共同來決定。

前兩位用于表示類型，當前兩位值為 “11” 則表示 entry 存放的是 int 類型數(shù)據(jù)，其他表示存儲的是 string。

entry-data

實際存放數(shù)據(jù)的區(qū)域，需要注意的是，如果 entry 中存儲的是 int 類型，encoding 和 entry-data 會合并到 encoding 中，沒有 entry-data 字段。

此刻結(jié)構(gòu)就變成了  。

MySQL：“為什么說 ziplist 省內(nèi)存？”

1. 與 linkedlist 相比，少了 prev、next 指針。
2. 通過 encoding 字段針對不同編碼來細化存儲，盡可能做到按需分配，當 entry 存儲的是 int 類型時，encoding 和 entry-data 會合并到 encoding ，省掉了 entry-data 字段。
3. 每個 entry-data 占據(jù)內(nèi)存大小不一樣，為了解決遍歷問題，增加了 prevlen 記錄上一個 entry 長度。遍歷數(shù)據(jù)時間復(fù)雜度是 O(1)，但是數(shù)據(jù)量很小的情況下影響不大。

MySQL：“聽起來很完美，為啥還搞什么 quicklist ”

既要又要還要的需求是很難實現(xiàn)的，ziplist 節(jié)省了內(nèi)存，但是也有不足。

• 不能保存過多的元素，否則查詢性能會大大降低，O(N) 時間復(fù)雜度。
• ziplist 存儲空間是連續(xù)的，當插入新的 entry 時，內(nèi)存空間不足就需要重新分配一塊連續(xù)的內(nèi)存空間，引發(fā)連鎖更新的問題。

連鎖更新

每個 entry 都用 prevlen 記錄了上一個 entry 的長度，從當前 entry B 前面插入一個新的 entry A 時，會導(dǎo)致 B 的 prevlen 改變，也會導(dǎo)致 entry B 大小發(fā)生變化。entry B 后一個 entry C 的 prevlen 也需要改變。以此類推，就可能造成了連鎖更新。

連鎖更新會導(dǎo)致 ziplist 的內(nèi)存空間需要多次重新分配，直接影響 ziplist 的查詢性能。于是乎在 Redis 3.2 版本引入了 quicklist。

quicklist

quicklist 是綜合考慮了時間效率與空間效率引入的新型數(shù)據(jù)結(jié)構(gòu)。結(jié)合了原先 linkedlist 與 ziplist 各自的優(yōu)勢，本質(zhì)還是一個鏈表，只不過鏈表的每個節(jié)點是一個 ziplist。

數(shù)據(jù)結(jié)構(gòu)定義在 quicklist.h? 文件中，鏈表由 quicklist? 結(jié)構(gòu)體定義，每個節(jié)點由 quicklistNode 結(jié)構(gòu)體定義（源碼版本為 6.2，7.0 版本使用 listpack 取代了 ziplist）。

quicklist 是一個雙向鏈表，所以每個 quicklistNode 都有前序指針（*prev?）、后序指針（*next?）。每個節(jié)點是 ziplist，所以還有一個指向 ziplist 的指針 *zl。

typedef struct quicklistNode {
    // 前序節(jié)點指針
    struct quicklistNode *prev;
    // 后序節(jié)點指針
    struct quicklistNode *next;
    // 指向 ziplist 的指針
    unsigned char *zl;
    // ziplist 字節(jié)大小
    unsigned int sz;
    // ziplst 元素個數(shù)
    unsigned int count : 16;
    // 編碼格式，1 = RAW 代表未壓縮原生ziplist，2=LZF 壓縮存儲
    unsigned int encoding : 2;
    // 節(jié)點持有的數(shù)據(jù)類型，默認值 = 2 表示是 ziplist
    unsigned int container : 2;
    // 節(jié)點持有的 ziplist 是否經(jīng)過解壓， 1 表示已經(jīng)解壓過，下一次操作需要重新壓縮。
    unsigned int recompress : 1;
    // ziplist 數(shù)據(jù)是否可壓縮，太小數(shù)據(jù)不需要壓縮
    unsigned int attempted_compress : 1;
    // 預(yù)留字段
    unsigned int extra : 10;
} quicklistNode;

quicklist 作為鏈表，定義了 頭、尾指針，用于快速定位表表頭和鏈表尾。

typedef struct quicklist {
    // 鏈表頭指針
    quicklistNode *head;
    // 鏈表尾指針
    quicklistNode *tail;
    // 所有 ziplist 的總 entry 個數(shù)
    unsigned long count;
    // quicklistNode 個數(shù)
    unsigned long len;
    int fill : QL_FILL_BITS;
    unsigned int compress : QL_COMP_BITS;
    unsigned int bookmark_count: QL_BM_BITS;
    // 柔性數(shù)組，給節(jié)點添加標簽，通過名稱定位節(jié)點，實現(xiàn)隨機訪問的效果
    quicklistBookmark bookmarks[];
} quicklist;

結(jié)合 quicklist 和 quicklistNode定義，quicklist 鏈表結(jié)構(gòu)如下圖所示。

從結(jié)構(gòu)上看，quicklist 就是 ziplist 的升級版，優(yōu)化的關(guān)鍵點在于控制好每個 ziplist 的大小或者元素個數(shù)。

• quicklistNode 的 ziplist 越小，可能會造成更多的內(nèi)存碎片，極端情況下是每個 ziplist 只有一個 entry，退化成了 linkedlist。
• quicklistNode 的 ziplist 過大，極端情況下一個 quicklist 只有一個 ziplist，退化成了 ziplist。連鎖更新的性能問題就會暴露無遺。

合理配置很重要，Redis 提供了 list-max-ziplist-size -2。

當 list-max-ziplist-size 為負數(shù)時表示限制每個 quicklistNode 的 ziplist 的內(nèi)存大小，超過這個大小就會使用 linkedlist 存儲數(shù)據(jù)，每個值有以下含義：

• -5：每個 quicklist 節(jié)點上的 ziplist 大小最大 64 kb <--- 正常環(huán)境不推薦
• -4：每個 quicklist 節(jié)點上的 ziplist 大小最大 32 kb <--- 不推薦
• -3：每個 quicklist 節(jié)點上的 ziplist 大小最大 16 kb <--- 可能不推薦
• -2：每個 quicklist 節(jié)點上的 ziplist 大小最大 8 kb <--- 不錯
• -1：每個 quicklist 節(jié)點上的 ziplist 大小最大 4kb <--- 不錯

默認值為 -2，也是官方最推薦的值，當然你可以根據(jù)自己的實際情況進行修改。

MySQL：“搞了半天還是沒能解決連鎖更新的問題嘛”

別急，飯要一口口吃，路要一步步走，步子邁大了容易扯著蛋。

ziplist 是緊湊型數(shù)據(jù)結(jié)構(gòu)，可以有效利用內(nèi)存。但是每個 entry 都用 prevlen 保留了上一個 entry 的長度，所以在插入或者更新時可能會出現(xiàn)連鎖更新影響效率。

于是 antirez 又設(shè)計出了“鏈表 + ziplist” 組成的 quicklist 來避免單個 ziplist 過大，降低連鎖更新的影響范圍。

可畢竟還是使用了 ziplist，本質(zhì)上無法避免連鎖更新的問題，于是乎在 5.0 版本設(shè)計出另一個內(nèi)存緊湊型數(shù)據(jù)結(jié)構(gòu) listpack，于 7.0 版本替換掉 ziplist。

listpack

出現(xiàn) listpack 的原因是因為用戶上報了一個 Redis 崩潰的問題，但是 antirez 并沒有找到崩潰的明確原因，猜測可能是 ziplist 結(jié)構(gòu)導(dǎo)致的連鎖更新導(dǎo)致的，于是就想設(shè)計一種簡單、高效的數(shù)據(jù)結(jié)構(gòu)來替換 ziplist 這個數(shù)據(jù)結(jié)構(gòu)。

MySQL：“l(fā)istpack 是啥？”

?listpack 也是一種緊湊型數(shù)據(jù)結(jié)構(gòu)，用一塊連續(xù)的內(nèi)存空間來保存數(shù)據(jù)，并且使用多種編碼方式來表示不同長度的數(shù)據(jù)來節(jié)省內(nèi)存空間。

源碼文件 listpack.h對 listpack 的解釋：A lists of strings serialization format，意思是一種字符串列表的序列化格式，可以把字符串列表進行序列化存儲，可以存儲字符串或者整形數(shù)字。

先看 listpack 的整體結(jié)構(gòu)。

一共四部分組成，tot-bytes、num-elements、elements、listpack-end-byte。

• tot-bytes，也就是 total bytes，占用 4 字節(jié)，記錄 listpack 占用的總字節(jié)數(shù)。
• num-elements，占用 2 字節(jié)，記錄 listpack elements 元素個數(shù)。
• elements，listpack 元素，保存數(shù)據(jù)的部分。
• listpack-end-byte，結(jié)束標志，占用 1 字節(jié)，值固定為 255。

MySQL：“好家伙，這跟 ziplist 有啥區(qū)別？別以為換了個名字，換個馬甲我就不認識了”

聽我說完！確實有點像，listpack 也是由元數(shù)據(jù)和數(shù)據(jù)自身組成。最大的區(qū)別是 elements 部分，為了解決 ziplist 連鎖更新的問題，element 不再像 ziplist 的 entry 保存前一項的長度。

• encoding-type，元素的編碼類型，會不同長度的整數(shù)和字符串編碼。
• element-data，實際存放的數(shù)據(jù)。
• element-tot-len，encoding-type + element-data 的總長度，不包含自己的長度。

?每個 element 只記錄自己的長度，不像 ziplist 的 entry，記錄上一項的長度。當修改或者新增元素的時候，不會影響后續(xù) element 的長度變化，解決了連鎖更新的問題。

從 linkedlist、 ziplist 到“鏈表 + ziplist” 構(gòu)成的 quicklist，再到 listpack 結(jié)構(gòu)。可以看到，設(shè)計的初衷都是能夠高效的使用內(nèi)存，同時避免性能下降。

本文轉(zhuǎn)載自微信公眾號「碼哥字節(jié)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼哥字節(jié)公眾號。

分享名稱：RedisList底層三種數(shù)據(jù)結(jié)構(gòu)原理剖析
路徑分享：http://m.5511xx.com/article/dpsjchc.html