Redis是一個開源的 key-value 存儲系統，它使用六種底層數據結構構建了包含字元串對象、列表對象、哈希對象、集合對象和有序集合對象的對象系統。今天我們就通過12張圖來全面瞭解一下它的數據結構和對象系統的實現原理。

本文的內容如下：

  • 首先介紹六種基礎數據結構：動態字元串，鏈表，字典，跳躍表，整數集合和壓縮列表。
  • 其次介紹 Redis 的對象系統中的字元串對象（String）、列表對象（List）、哈希對象（Hash）、集合對象（Set）和有序集合對象（ZSet）
  • 最後介紹 Redis 的鍵空間和過期鍵( expire )實現。

數據結構

簡單動態字元串

Redis 使用動態字元串 SDS 來表示字元串值。下圖展示了一個值為 Redis 的 SDS結構 :

  • len: 表示字元串的真正長度（不包含NULL結束符在內）。
  • alloc: 表示字元串的最大容量（不包含最後多餘的那個位元組）。
  • flags: 總是佔用一個位元組。其中的最低3個bit用來表示header的類型。
  • buf: 字元數組。

SDS 的結構可以減少修改字元串時帶來的內存重分配的次數，這依賴於內存預分配和惰性空間釋放兩大機制。

當 SDS 需要被修改，並且要對 SDS 進行空間擴展時，Redis 不僅會為 SDS 分配修改所必須要的空間，還會為 SDS 分配額外的未使用的空間。

  • 如果修改後， SDS 的長度(也就是len屬性的值)將小於 1MB ，那麼 Redis 預分配和 len 屬性相同大小的未使用空間。
  • 如果修改後， SDS 的長度將大於 1MB ，那麼 Redis 會分配 1MB 的未使用空間。

比如說，進行修改後 SDS 的 len 長度為20位元組，小於 1MB，那麼 Redis 會預先再分配 20 位元組的空間， SDS 的 buf數組的實際長度(除去最後一位元組)變為 20 + 20 = 40 位元組。當 SDS的 len 長度大於 1MB時，則只會再多分配 1MB的空間。

類似的，當 SDS 縮短其保存的字元串長度時，並不會立即釋放多出來的位元組，而是等待之後使用。

鏈表

鏈表在 Redis 中的應用非常廣泛，比如列表對象的底層實現之一就是鏈表。除了鏈表對象外，發布和訂閱、慢查詢、監視器等功能也用到了鏈表。

Redis 的鏈表是雙向鏈表，示意圖如上圖所示。鏈表是最為常見的數據結構，這裡就不在細說。

Redis 的鏈表結構的dup 、 free 和 match 成員屬性是用於實現多態鏈表所需的類型特定函數：

  • dup 函數用於複製鏈表節點所保存的值，用於深度拷貝。
  • free 函數用於釋放鏈表節點所保存的值。
  • match 函數則用於對比鏈表節點所保存的值和另一個輸入值是否相等。

字典

字典被廣泛用於實現 Redis 的各種功能，包括鍵空間和哈希對象。其示意圖如下所示。

Redis 使用 MurmurHash2 演算法來計算鍵的哈希值，並且使用鏈地址法來解決鍵衝突，被分配到同一個索引的多個鍵值對會連接成一個單向鏈表。

跳躍表

Redis 使用跳躍表作為有序集合對象的底層實現之一。它以有序的方式在層次化的鏈表中保存元素， 效率和平衡樹媲美 —— 查找、刪除、添加等操作都可以在對數期望時間下完成， 並且比起平衡樹來說， 跳躍表的實現要簡單直觀得多。

跳錶的示意圖如上圖所示，這裡只簡單說一下它的核心思想，並不進行詳細的解釋。

如示意圖所示，zskiplistNode 是跳躍表的節點，其 ele 是保持的元素值，score 是分值，節點按照其 score 值進行有序排列，而 level 數組就是其所謂的層次化鏈表的體現。

每個 node 的 level 數組大小都不同， level 數組中的值是指向下一個 node 的指針和 跨度值 (span)，跨度值是兩個節點的score的差值。越高層的 level 數組值的跨度值就越大，底層的 level 數組值的跨度值越小。

level 數組就像是不同刻度的尺子。度量長度時，先用大刻度估計範圍，再不斷地用縮小刻度，進行精確逼近。

當在跳躍表中查詢一個元素值時，都先從第一個節點的最頂層的 level 開始。比如說，在上圖的跳錶中查詢 o2 元素時，先從o1 的節點開始，因為 zskiplist 的 header 指針指向它。

先從其 level[3] 開始查詢，發現其跨度是 2，o1 節點的score是1.0，所以加起來為 3.0，大於 o2 的score值2.0。所以，我們可以知道 o2 節點在 o1 和 o3 節點之間。這時，就改用小刻度的尺子了。就用level[1]的指針，順利找到 o2 節點。

整數集合

整數集合 intset 是集合對象的底層實現之一，當一個集合只包含整數值元素，並且這個集合的元素數量不多時， Redis 就會使用整數集合作為集合對象的底層實現。

如上圖所示，整數集合的 encoding 表示它的類型，有int16t，int32t 或者int64_t。其每個元素都是 contents 數組的一個數組項，各個項在數組中按值的大小從小到大有序的排列，並且數組中不包含任何重複項。length 屬性就是整數集合包含的元素數量。

壓縮列表

壓縮隊列 ziplist 是列表對象和哈希對象的底層實現之一。當滿足一定條件時，列表對象和哈希對象都會以壓縮隊列為底層實現。

壓縮隊列是 Redis 為了節約內存而開發的，是由一系列特殊編碼的連續內存塊組成的順序型數據結構。它的屬性值有：

  • zlbytes : 長度為 4 位元組，記錄整個壓縮數組的內存位元組數。
  • zltail : 長度為 4 位元組，記錄壓縮隊列表尾節點距離壓縮隊列的起始地址有多少位元組，通過該屬性可以直接確定尾節點的地址。
  • zllen : 長度為 2 位元組，包含的節點數。當屬性值小於 INT16_MAX時，該值就是節點總數，否則需要遍歷整個隊列才能確定總數。
  • zlend : 長度為 1 位元組，特殊值，用於標記壓縮隊列的末端。

中間每個節點 entry 由三部分組成：

  • previousentrylength : 壓縮列表中前一個節點的長度，和當前的地址進行指針運算，計算出前一個節點的起始地址。
  • encoding： 節點保存數據的類型和長度
  • content ：節點值，可以為一個位元組數組或者整數。

對象

上面介紹了 6 種底層數據結構，Redis 並沒有直接使用這些數據結構來實現鍵值資料庫，而是基於這些數據結構創建了一個對象系統，這個系統包含字元串對象、列表對象、哈希對象、集合對象和有序集合這五種類型的對象，每個對象都使用到了至少一種前邊講的底層數據結構。

Redis 根據不同的使用場景和內容大小來判斷對象使用哪種數據結構，從而優化對象在不同場景下的使用效率和內存佔用。

Redis 的 redisObject 結構的定義如下所示。

typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;

其中 type 是對象類型，包括REDISSTRING, REDISLIST, REDISHASH, REDISSET 和 REDIS_ZSET。

encoding是指對象使用的數據結構，全集如下。

字元串對象

我們首先來看字元串對象的實現，如下圖所示。

如果一個字元串對象保存的是一個字元串值，並且長度大於32位元組，那麼該字元串對象將使用 SDS 進行保存，並將對象的編碼設置為 raw，如圖的上半部分所示。如果字元串的長度小於32位元組，那麼字元串對象將使用embstr 編碼方式來保存。

embstr 編碼是專門用於保存短字元串的一種優化編碼方式，這個編碼的組成和 raw 編碼一致，都使用 redisObject 結構和 sdshdr 結構來保存字元串，如上圖的下半部所示。

但是 raw 編碼會調用兩次內存分配來分別創建上述兩個結構，而embstr則通過一次內存分配來分配一塊連續的空間，空間中一次包含兩個結構。

embstr 只需一次內存分配，而且在同一塊連續的內存中，更好的利用緩存帶來的優勢，但是 embstr 是隻讀的，不能進行修改，當一個 embstr 編碼的字元串對象進行 append 操作時， redis 會現將其轉變為 raw 編碼再進行操作。

列表對象

列表對象的編碼可以是 ziplist 或 linkedlist。其示意圖如下所示。

當列表對象可以同時滿足以下兩個條件時，列表對象使用 ziplist 編碼：

  • 列表對象保存的所有字元串元素的長度都小於 64 位元組。
  • 列表對象保存的元素數量數量小於 512 個。

不能滿足這兩個條件的列表對象需要使用 linkedlist 編碼或者轉換為 linkedlist 編碼。

哈希對象

哈希對象的編碼可以使用 ziplist 或 dict。其示意圖如下所示。

當哈希對象使用壓縮隊列作為底層實現時，程序將鍵值對緊挨著插入到壓縮隊列中，保存鍵的節點在前，保存值的節點在後。如下圖的上半部分所示，該哈希有兩個鍵值對，分別是 name:Tom 和 age:25。

當哈希對象可以同時滿足以下兩個條件時，哈希對象使用 ziplist 編碼:

  • 哈希對象保存的所有鍵值對的鍵和值的字元串長度都小於64位元組。
  • 哈希對象保存的鍵值對數量小於512個。

不能滿足這兩個條件的哈希對象需要使用 dict 編碼或者轉換為 dict 編碼。

集合對象

集合對象的編碼可以使用 intset 或者 dict。

intset 編碼的集合對象使用整數集合最為底層實現，所有元素都被保存在整數集合裡邊。

而使用 dict 進行編碼時，字典的每一個鍵都是一個字元串對象，每個字元串對象就是一個集合元素，而字典的值全部都被設置為NULL。如下圖所示。

當集合對象可以同時滿足以下兩個條件時，對象使用 intset 編碼:

  • 集合對象保存的所有元素都是整數值。
  • 集合對象保存的元素數量不超過512個。

否則使用 dict 進行編碼。

有序集合對象

有序集合的編碼可以為 ziplist 或者 skiplist。

有序集合使用 ziplist 編碼時，每個集合元素使用兩個緊挨在一起的壓縮列表節點表示，前一個節點是元素的值，第二個節點是元素的分值，也就是排序比較的數值。

壓縮列表內的集合元素按照分值從小到大進行排序，如下圖上半部分所示。

有序集合使用 skiplist 編碼時使用 zset 結構作為底層實現，一個 zet 結構同時包含一個字典和一個跳躍表。

其中，跳躍表按照分值從小到大保存所有元素，每個跳躍表節點保存一個元素，其score值是元素的分值。而字典則創建一個一個從成員到分值的映射，字典的鍵是集合成員的值，字典的值是集合成員的分值。通過字典可以在O(1)複雜度查找給定成員的分值。如下圖所示。

跳躍表和字典中的集合元素值對象都是共享的，所以不會額外消耗內存。

當有序集合對象可以同時滿足以下兩個條件時，對象使用 ziplist 編碼：

  • 有序集合保存的元素數量少於128個；
  • 有序集合保存的所有元素的長度都小於64位元組。

否則使用 skiplist 編碼。

資料庫鍵空間

Redis 伺服器都有多個 Redis 資料庫，每個Redis 數據都有自己獨立的鍵值空間。每個 Redis 資料庫使用 dict 保存資料庫中所有的鍵值對。

鍵空間的鍵也就是資料庫的鍵，每個鍵都是一個字元串對象，而值對象可能為字元串對象、列表對象、哈希表對象、集合對象和有序集合對象中的一種對象。

除了鍵空間，Redis 也使用 dict 結構來保存鍵的過期時間，其鍵是鍵空間中的鍵值，而值是過期時間，如上圖所示。

通過過期字典，Redis 可以直接判斷一個鍵是否過期，首先查看該鍵是否存在於過期字典，如果存在，則比較該鍵的過期時間和當前伺服器時間戳，如果大於，則該鍵過期，否則未過期。

原文地址 ：

十二張圖帶你瞭解 Redis 的數據結構和對象系統?

mp.weixin.qq.com圖標

博客地址：

十二張圖帶你瞭解 Redis 的數據結構和對象系統?

remcarpediem.net


推薦閱讀：
相關文章