redis-七大資料結構

文章目錄

• 1、SDS
• • SDS 與C字元串的差別
  • • • 完全杜絕緩沖區溢出
      • 減少修改字元串時的記憶體重配置設定次數
      • 二進制安全
      • 相容部分C字元串函數
• 2、雙端連結清單
• • 重點概述
• 3、hashtable
• • 重點概述
• 4、跳表
• • 跳躍表的實作
  • Redis skiplist和經典skiplist對比
  • Redis為什麼用跳表而不用哈希表和平衡樹？
• 5、壓縮清單（ziplist）
• 6、整數集合intset
• • 整數集合的組成
  • 更新
• 7、quicklist
• • 為什麼需要quicklist？
  • 如何提高存儲效率
  • quicklist的資料結構定義

1、SDS

String編碼方式：embstr和raw底層就是SDS

SDS定義

SDS 與C字元串的差別

C字元串	SDS
擷取字元串長度的複雜度為O(N)	擷取字元串長度的複雜度為O(1)
API是不安全的，可能會造成緩沖區溢出	API是安全的，不會造成緩沖區溢出
修改字元串N次必然需要執行N次記憶體重配	空間預配置設定(記憶體重配置設定次數從必定N次降低為最多N次) 惰性空間釋放(優化縮短操作)
隻能儲存文本資料	可以儲存二進制或文本資料，以len屬性判斷結束而不是\0
可以使用<string.h>庫中的函數	可以使用<string.h>庫中一部分的函數

完全杜絕緩沖區溢出

與C字元串不同， SDS的空間配置設定政策

完全杜絕了發生緩沖區溢出的可能性

怎麼做到的？自動擴容

減少修改字元串時的記憶體重配置設定次數

因為

C字元串的長度和底層數組的長度

之間存在着這種關聯性 ，是以每次增長或者縮短一個C字元串 ， 程式都總要對儲存這個C字元串的數組進行一次

記憶體重配置設定

操作。

怎麼做到的？未使用空間

SDS 通過未使用空間解除了字元串長度和底層數組長度之間的關聯。

在 SDS 中，buf 數組的長度不一定就是字元數量加一，數組裡面可以包含未使用的位元組，而這些位元組的數量就由 SDS 的

free

屬性記錄。

通過

未使用空間

， SDS 實作了

空間預配置設定和惰性空間釋放

兩種優化政策.

1、空間預配置設定(記憶體重配置設定次數從必定N次降低為最多N次)

空間預配置設定用于優化 SDS 的字元串增長操作： 當SDS的 API 對一個 SDS 進行修改，并且需要對 SDS 進行空間擴充的時候，程式不僅會為 SDS 配置設定修改所必須的空間，還會為 SDS 配置設定額外的未使用空間。

其中，額外配置設定的未使用空間數量由以下公式決定：

1. 如果對 SDS 進行修改之後，SDS 的長度（len 屬性的值）小于 1MB，那麼程式配置設定和 len 屬性同樣大小的未使用空間，這時 SDS len 屬性的值将和 free 屬性的值相同。

2. 如果對SDS進行修改之後， SDS 的長度将大于等于1M那麼程式會配置設定 1MB的未使用空間。

   通過空間預配置設定政策，Redis 可以減少連續執行字元串增長操作所需的記憶體重配置設定次數。

   在擴充 SDS空間之前， SDSAPI會先檢查未使用空間是否足夠， 如果足夠的話， API 就會直接使用未使用空間， 而無須執行記憶體重配置設定。

   通過空間預配置設定， SDS将連續增長N次字元串所需的記憶體重配置設定次數從必定N次降低為最多N次

2、惰性空間釋放(優化SDS 的字元串縮短操作)

當 SDS的API需要縮短 SDS儲存的字元串時， 程式

并不立即

使用記憶體重配置設定來回收 縮短後多出來的位元組， 而是使用

free屬性

将這些位元組的數量記錄起來，

并等待将來使用

。

通過惰性空間釋放政策， SDS避免了縮短字元串時所需的記憶體重配置設定操作， 并為将來可能有的增長操作提供了優化。與此同時， SDS也提供了相應的API， 讓我們可以在有需要時， 真正地釋放 SDS的未使用空間， 是以不用擔心惰性空間釋放政策會造成記憶體浪費。

二進制安全

C字元串中的字元必須符合某種編碼（比如ASCII）， 并且除了字元串的末尾之外， 字元串裡面不能包含空字元， 否則最先被程式讀入的空字元将被誤認為是字元串結尾， 這些限制使得C字元串隻能儲存文本資料， 而不能儲存像圖檔、 音頻、 視訊、 壓縮檔案這樣的二進制資料。

雖然資料庫一般用于儲存文本資料， 但使用資料庫來儲存二進制資料的場景也不少見， 是以， 為了確定Redis可以适用于各種不同的使用場景， SDS的API都是二進制安全的 ， 所有SDS API都會以處理二進制的方式來處理SDS存放在buf數組裡的資料 ， 程式不會對其中的資料做任何限制、 過濾、 資料在寫入時是什麼樣的， 它被讀取時就是什麼樣。

這也是我們将SDS的buf屬性稱為位元組數組的原因，即 Redis不是用這個數組來儲存字元， 而是用它來儲存二進制資料。

通過使用二進制安全的SDS， 而不是C字元串， 使得Redis不僅可以儲存文本資料， 還可以儲存任意格式的二進制資料。

相容部分C字元串函數

雖然SDS的API都是二進制安全的， 但它們一樣遵循C字元串以空字元結尾的慣例： 這些API總會将SDS儲存的資料的末尾設定為空字元， 并且總會在為buf數組配置設定空間時多配置設定一個位元組來容納這個空字元， 這是為了讓那些儲存文本資料的SDS可以重用一部分<string.h＞庫定義的函數。 進而避免了不必要的代碼重複。

SDS API

2、雙端連結清單

重點概述

• 連結清單被廣泛用于實作 Redis 的各種功能， 比如清單鍵、 釋出與訂閱、 慢查詢、 螢幕等。
• 每個連結清單節點由一個 listNode 結構來表示， 每個節點都有一個指向前置節點和後置節點的指針， 是以 Redis 的連結清單實作是

  雙端連結清單

  。
• 每個連結清單使用一個 list 結構來表示， 這個結構帶有表頭節點指針、 表尾節點指針，以及連結清單長度等資訊。
• 因為連結清單表頭節點的前置節點和表尾節點的後置節點都指向 NULL ， 是以 Redis 的連結清單實作是

  無環連結清單

  。
• 通過為連結清單設定不同的類型特定函數， Redis 的連結清單可以用于儲存各種不同類型的值。
• 每個

  雙端連結清單

  節點都儲存了一個

  字元串對象

  ， 而每個字元串對象都儲存了一個

  清單元素

  ，如下所示：

  

Redis的連結清單實作的特性可以總結如下：

• 雙端：連結清單節點帶有prev和next指針， 擷取某個節點的

  前置節點和後置節點

  的複雜度都是O(1)。
• 無環： 表頭節點的prev指針和表尾節點的next 指針都指向NULL， 對連結清單的通路以NULL為終點。

• 帶表頭指針和表尾指針

  通過list結構的head指針和tail指針， 程式擷取連結清單的表頭節點和表尾節點的複雜度為O(1)。

• 帶連結清單長度計數器

  程式使用list結構的len屬性來對list持有的連結清單節點進行計數， 程式擷取連結清單中節點數量的複雜度為 0(1 ）。

• 多态：連結清單節點使用 void＊指針來儲存節點值， 并且可以通過list結構的

  dup、free、 match

  三個屬性為節點值設定類型特定函數， 是以連結清單可以用于儲存各種不同類型的值。

API

3、hashtable

重點概述

• 字典被廣泛用于實作 Redis 的各種功能， 其中包括

  資料庫

  和

  哈希鍵

  ，當一個哈希鍵包含的鍵值對比較多， 又或者鍵值對中的元素都是比較長的字元串時， Redis就會使用

  hashtable

  作為

  哈希鍵

  的底層實作
• Redis 中的字典使用哈希表作為底層實作， 每個字典帶有兩個哈希表 ，一個平時使用， 另一個僅在進行

  rehash

  時使用。
• 哈希表使用

  鍊位址法

  來解決鍵沖突， 被配置設定到同一個索引上的多個鍵值對會連接配接成一個單向連結清單。
• 在對哈希表進行擴充或者收縮操作時， 程式需要将現有哈希表包含的所有鍵值對

  rehash

  到新哈希表裡面， 并且這個 rehash 過程并不是一次性地完成的， 而是

  漸進式

  地完成的

4、跳表

• 跳躍表（ skiplist ）是一種

  有序

  的資料結構， 它通過在每個節點中維持多個指向其他節點的指針， 進而達到快速通路節點的目的。
• 跳躍表支援

  平均 O(logN）

  、

  最壞O(N)

  複雜度的節點查找， 還可以通過順序性操作來批量處理節點。
• 在大部分情況下 ， 跳躍表的效率可以和平衡樹相媲美， 并且因為跳躍表的實作比平衡樹要來得更為簡單， 是以有不少程式都使用跳躍表來代替平衡樹。
• Redis 使用跳躍表作為

  sorted set

  的底層實作之一，如果一個有序集合包含的元素數量比較多， 又或者有序集合中元素的成員長度超過一定門檻值， Redis 就會使用跳躍表來作為

  sorted set

  的底層實作。
• skiplist隻用在兩個地方，一個是實作

  有序集合鍵

  ， 另 一個是在

  叢集節點

  中用作

  内部資料結構

  。
• redis的跳躍表底層實作由

  zskiplist和zskiplistNode

  兩個結構組成，其中zskiplist用于儲存跳躍表資訊（比如表頭節點、表尾節點、 長度）， 而zskiplistNode則用于表示跳躍表節點。
• 每個跳躍表節點的層高都是1至32之間的随機數。
• 在同一個跳躍表中， 多個節點可以包含相同的分值， 但每個節點的成員對象必須是唯一的。
• 跳躍表中的節點按照

  分值從小到大

  進行排序， 當分值相同時， 節點按照

  成員對象從小到大

  進行排序。

跳躍表的實作

zskiplistNode 和zskiplist 共同實作skiplist

zskiplist 包含的屬性：

header ：指向跳躍表的表頭節點。

tail ：指向跳躍表的表尾節點。

level：記錄目前跳躍表内， 層數最大的那個節點的層數（表頭節點的層數不在内）

length：記錄跳躍表的長度（表頭節點不計算在内）

zskiplistNode 結構， 該結包含以下屬性：

層（level ）

：節點中用 Ll 、 L2 、 L3 等字樣标記節點的各個層， Ll 代表第一層， L2代表第二層， 以此類推。

每個層都帶有兩個屬性：

前進指針和跨度

。 在上面的圖檔中， 連線上帶有數字的箭頭就代表前進指針， 而那個數字就是跨度。 當程式從表頭向表尾進行周遊時， 通路會沿着層的前進指針進行。

• 前進指針

  用于通路位于

  表尾

  方向的其他節點，

• 跨度

  則記錄了前進指針所指向節點和目前節點的

  距離

  。

後退指針

：節點中用BW字樣标記節點的後退指針， 它指向位于目前節點的前一個節點。 後退指針在程式從表尾向表頭周遊時使用。

分值（ score ）

：各個節點中的1.0、 2.0和3.0是節點所儲存的分值。 在跳躍表中，節點按各自所儲存的分值

從小到大排列

。

成員對象（obj）

：各個節點中的ol、 o2和o3是節點所儲存的成員對象。

Redis skiplist和經典skiplist對比

• Redis skiplist的分數(score)允許重複，經典skiplist是不允許的
• 在比較時，不僅比較分數（skiplist的key），還比較資料本身（skiplist的value）。在Redis的skiplist實作中，資料本身的内容唯一辨別這份資料，而不是由key來唯一辨別。另外，當多個元素分數相同的時候，還需要根據

  資料内容

  來進字典排序。
• 第1層連結清單不是一個單向連結清單，而是一個雙向連結清單。這是為了

  友善以倒序方式

  擷取一個範圍内的元素。
• 在skiplist中可以很友善地計算出每個元素的排名(rank)

Redis為什麼用跳表而不用哈希表和平衡樹？

不用哈希表原因：因為哈希表不能範圍查找

skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。是以，在哈希表上隻能做單個key的查找，不适宜做範圍查找

不用平衡樹原因：在做範圍查找的時候，平衡樹比skiplist操作要複雜

• 在平衡樹上，我們找到指定範圍的小值之後，還需要以

  中序周遊

  的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這裡的

  中序周遊

  并不容易實作。
• 在skiplist上進行範圍查找就非常簡單，隻需要在找到小值之後，對第1層連結清單進行若幹步的周遊就可以實作。

skiplist插入和删除更簡單

平衡樹的插入和删除操作可能引發子樹的調整，邏輯複雜，而skiplist的插入和删除隻需要修改相鄰節點的指針，操作簡單又快速。

記憶體占用更小

從記憶體占用上來說，skiplist比平衡樹更小一些。一般來說，平衡樹每個節點包含2個指針（分别指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis裡的實作一樣，取p=1/4，那麼平均每個節點包含1.33個指針，比平衡樹更有優勢。

從算法實作難度上來比較，skiplist比平衡樹要簡單得多。

5、壓縮清單（ziplist）

可以存儲任意二進制串、資料無序、可以對每個資料項進行不同的變長編碼

結構如下：

表頭有三個字段：

zlbytes

清單長度、

zltail

清單尾的偏移量、

zllen

清單中的

entry

個數，

表尾還有一個

zlend

表示

清單結束。

壓縮清單之是以能節省記憶體，就在于它是用一系列連續的entry儲存資料。

這些entry會挨個兒放置在記憶體中，不需要再用額外的指針進行連接配接，這樣就可以節省指針所占用的空間。

每個entry的中繼資料包括下面幾部分：

• prev_len，表示前一個entry的長度。prev_len有兩種取值情況：

  1位元組或5位元組

  。取值1位元組時，表示上一個entry的長度小于254位元組。雖然1位元組的值能表示的數值範圍是0到255，但是壓縮清單中zlend的取值預設是255，是以，就預設用255表示整個壓縮清單的結束，其他表示長度的地方就不能再用255這個值了。是以，當上一個entry長度小于254位元組時，prev_len取值為1位元組，否則，就取值為5位元組。
• len：表示自身長度，4位元組；
• encoding：表示編碼方式，1位元組；
• content：儲存實際資料。

連鎖更新

添加新節點到壓縮清單， 或者從壓縮清單中删除節點， 可能會引發

連鎖更新

操作，但這種操作出現的幾率并不高。

• 首先， 壓縮清單裡要恰好有多個連續的、 長度介于250位元組至253位元組之間的節點，連鎖更新才有可能被引發， 在實際中， 這種情況并不多見；
• 其次， 即使出現連鎖更新， 但隻要被更新的節點數量不多， 就不會對性能造成任何影響：比如說， 對三五個節點進行連鎖更新是絕對不會影響性能的；

6、整數集合intset

• 整數集合是

  集合鍵set

  的底層實作之一，當一個集合

  隻包含整數值元素

  ， 并且這個集合的元素數量不多時， Redis 就會使用整數集合作為集合鍵的底層實作。
• 整數集合的底層實作為

  數組

  ， 這個數組以

  有序、 無重複

  的方式儲存集合元素， 在有需要時， 程式會根據新添加元素的類型， 改變這個數組的類型。
• 更新操作為整數集合帶來了操作上的靈活性， 井且盡可能地節約了記憶體。
• 整數集合隻支援更新操作， 不支援降級操作。

整數集合的組成

整數集合（ intset ）是 Redis 用于儲存

整數值

的集合抽象資料結構

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
           

• length屬性

  記錄了整數集合包含的 元素數量，encoding和length兩個字段構成了intset的頭部（header）。

• encoding屬性

  有三種取值int16_t、int32_t、int64_t

• contents 數組

  是整數集合的底層實作，整數集合的每個元素都是 contents 數組的一個數組項， 各個項在數組中

  按值從小到大

  有序地排列， 并且數組中

  不包含任何重複項

  。

  是一個

  柔性數組

  ，表示intset的header後面緊跟着資料元素。這個數組的總長度（即總位元組數）等于

  encoding * length

  。柔性數組在Redis的很多資料結構的定義中都出現過（例如sds,quicklist, skiplist），用于表達一個

  偏移量

  。contents需要單獨為其配置設定空間，這部分記憶體不包含在intset結構當中。

更新

每當我們要将一個新元素添加到整數集合裡面， 并且新元素的類型比整數集合現有所有元素的類型都要長時， 整數集合需要先進行更新（ upgrade ）， 然後才能将新元素添加到整數集合裡面。

更新整數集合并添加新元素共分為三步進行：

• 根據新元素的類型， 擴充整數集合底層數組的空間大小 并為新元素配置設定空間。
• 将底層數組現有的所有元素都轉換成與新元素相同的類型， 并将類型轉換後的元素放置到正确的位上， 而且在放置元素的過程中， 需要繼續維持底層數組的

  有序性質不變

  。
• 将新元素添加到底層數組裡面。

更新的好處：

• 提升整數集合的靈活性
• 盡可能地節約記憶體

7、quicklist

為什麼需要quicklist？

• 雙向連結清單的缺點

  • 記憶體開銷比較大

    （它在每個節點上除了要儲存資料之外，還要額外儲存兩個指針）

  • 容易産生記憶體碎片

    （雙向連結清單的各個節點是單獨的記憶體塊，位址不連續）。

• ziplist的缺點

  它不利于修改操作，每次資料變動都會引發一次記憶體的

  realloc

  。特别是當ziplist長度很長的時候，一次realloc可能會導緻大批量的資料拷貝，進一步降低性能。

于是，結合了

雙向連結清單和ziplist

的優點，quicklist就應運而生了。

如何提高存儲效率

quicklist是一個連結清單，連結清單的每個節點都是一個ziplist。

比如，一個包含3個節點的quicklist，如果每個節點的ziplist又包含4個資料項，那麼對外表現上，這個list就總共包含12個資料項。

這就帶來了一個新問題，到底一個quicklist節點包含多長的ziplist合适呢？

比如，同樣是存儲12個資料項，既可以是一個quicklist包含3個節點，而每個節點的ziplist又包含4個資料項，也可以是一個quicklist包含6個節點，而每個節點的ziplist又包含2個資料項。

這又是一個需要找平衡點的難題。我們隻從

存儲效率

上分析一下：

• 每個quicklist節點上的ziplist越短，則記憶體碎片越多。

  記憶體碎片多了，有可能在記憶體中産生很多無法被利用的小碎片，進而降低存儲效率。這種情況的極端是每個quicklist節點上的ziplist隻包含一個資料項，這就蛻化成一個普通的雙向連結清單了。

• 每個quicklist節點上的ziplist越長，則為ziplist配置設定大塊連續記憶體空間的難度就越大。

  有可能出現記憶體裡有很多小塊的空閑空間（它們加起來很多），但卻找不到一塊足夠大的空閑空間配置設定給ziplist的情況。這同樣會降低存儲效率。這種情況的極端是整個quicklist隻有一個節點，所有的資料項都配置設定在這僅有的一個節點的ziplist裡面。這其實蛻化成一個ziplist了。

是以一個quicklist節點上的ziplist要保持一個合理的長度，那到底多長合理呢？

Redis提供了一個配置參數

list-max-ziplist-size

，就是為了讓使用者可以來根據自己的情況進行調整。

list-max-ziplist-size n
           

• 當n取正值的時候，表示按照資料項個數來限定每個quicklist節點上的ziplist長度。比如，當這個參數配置成5的時候，表示每個quicklist節點的ziplist最多包含5個資料項。
• 當n取負值的時候，表示按照占用位元組數來限定每個quicklist節點上的ziplist長度。這時，它隻能取-1到-5這五個值，每個值含義如下：
  • -5: 每個quicklist節點上的ziplist大小不能超過64 Kb。（注：1kb => 1024 bytes）
  • -4: 每個quicklist節點上的ziplist大小不能超過32 Kb。
  • -3: 每個quicklist節點上的ziplist大小不能超過16 Kb。
  • -2: 每個quicklist節點上的ziplist大小不能超過8 Kb。（-2是Redis給出的預設值）
  • -1: 每個quicklist節點上的ziplist大小不能超過4 Kb。

當清單很長的時候，最容易被通路的很可能是兩端的資料，中間的資料被通路的頻率比較低（通路起來性能也很低）。是以list還提供了一個

list-compress-depth選項

，能夠把中間的資料節點進行壓縮，進而進一步節省記憶體空間。

list-compress-depth n
           

這個參數表示一個quicklist兩端

不被壓縮

的

quicklist雙向連結清單

的

節點個數

。

參數list-compress-depth的取值n含義如下：

• 0: 是個特殊值，表示都不壓縮。這是Redis的預設值。
• 1: 表示quicklist兩端各有1個節點不壓縮，中間的節點壓縮。
• 2: 表示quicklist兩端各有2個節點不壓縮，中間的節點壓縮。
• 依此類推…

由于0是個特殊值，很容易看出quicklist的頭節點和尾節點總是不被壓縮的，以便于在表的兩端進行快速存取。

quicklist的資料結構定義

quicklistNode結構代表quicklist的一個節點，其中各個字段的含義如下：

• prev: 指向連結清單前一個節點的指針。
• next: 指向連結清單後一個節點的指針。
• zl: 資料指針。如果目前節點的資料沒有壓縮，那麼它指向一個ziplist結構；否則，它指向一個quicklistLZF結構。
• sz: 表示zl指向的ziplist的總大小（包括zlbytes, zltail,zllen, zlend和各個資料項）。需要注意的是：如果ziplist被壓縮了，那麼這個sz的值仍然是壓縮前的ziplist大小。
• count: 表示ziplist裡面包含的資料項個數。這個字段隻有16bit。稍後我們會一起計算一下這16bit是否夠用。
• encoding: 表示ziplist是否壓縮了（以及用了哪個壓縮算法）。目前隻有兩種取值：2表示被壓縮了（而且用的是LZF壓縮算法），1表示沒有壓縮。
• container: 是一個預留字段。本來設計是用來表明一個quicklist節點下面是直接存資料，還是使用ziplist存資料，或者用其它的結構來存資料（用作一個資料容器，是以叫container）。但是，在目前的實作中，這個值是一個固定的值2，表示使用ziplist作為資料容器。
• recompress: 當我們使用類似lindex這樣的指令檢視了某一項本來壓縮的資料時，需要把資料暫時解壓，這時就設定recompress=1做一個标記，等有機會再把資料重新壓縮。
• attempted_compress: 這個值隻對Redis的自動化測試程式有用。我們不用管它。
• extra: 其它擴充字段。目前Redis的實作裡也沒用上。

quicklistLZF結構表示一個被壓縮過的ziplist。其中：

• sz: 表示壓縮後的ziplist大小。
• compressed: 是個柔性數組，存放壓縮後的ziplist位元組數組。

真正表示quicklist的資料結構是同名的quicklist這個struct：

• head: 指向頭節點（左側第一個節點）的指針。
• tail: 指向尾節點（右側第一個節點）的指針。
• count: 所有ziplist資料項的個數總和。
• len: quicklist節點的個數。
• fill: 16bit，ziplist大小設定，存放list-max-ziplist-size參數的值。
• compress: 16bit，節點壓縮深度設定，存放list-compress-depth參數的值。