Redis - 底層數據結構

来源:https://www.cnblogs.com/fatedeity/archive/2023/04/12/17308543.html
-Advertisement-
Play Games

Redis 構造了多種底層數據結構供使用，不同的數據類型有可能使用到多種底層數據結構存儲，因此，需要理解為何 Redis 會有這樣的設計，理解每個底層數據結構的概念之後，就能知曉在極端性能上如何做取捨。 ...


簡介

Redis 的底層數據結構主要以下幾種：

  • SDS(Simple Dynamic String, 簡單動態字元串)
  • ZipList(壓縮列表)
  • QuickList(快表)
  • Dict(字典)
  • IntSet(整數集合)
  • ZSkipList(跳躍表)

簡單動態字元串

在 Redis 中，並不會直接使用 C 語言自帶的字元串結構作為實際的存儲結構，而只是將字元串作為字面量使用，大多數情況使用自定義的 SDS 來表示字元串。

SDS 主要用於儲存 Redis 的預設字元串表示、AOF 模塊中的 AOF 緩衝區、客戶端狀態輸入緩衝區。它的定義如下：

struct sdshdr {
    int len;        // 記錄 buf 數組中已使用位元組的數量，等於 SDS 所保存的字元串的長度
    int alloc;      // 記錄 buf 數組中未使用位元組的數量
    char buf[];     // 位元組數組，用於保存字元串
};

優點

相對於 C 語言的字元串實現，Redis 實現的 SDS 有以下優點：

  • 通過記錄 len 屬性，實現常數級時間複雜度獲取字元串長度
  • 通過檢查 len 屬性，避免字元串在修改時出現緩衝區溢出的情況
  • 通過記錄 len 屬性和 alloc 屬性，對於修改字元串實現了空間預分配和惰性空間釋放
  • 實際存儲的 buf 是一個位元組數組，可以實現 SDS 安全操作二進位數據
  • SDS 仍然以 \0 作為字元串結尾的標識，這樣可以重用 C 語言字元串的部分函數

空間預分配

當 SDS 修改時需要擴展空間大小，程式不僅會為 SDS 擴展修改所需的空間，還會為 SDS 分配額外的未使用空間。這額外空間一般是 len 的大小，最大不超過 1MB。

這樣可以減少連續執行字元串增長操作所需的記憶體重分配次數。

惰性空間釋放

當 SDS 修改時需要縮短空間大小，程式並不會立即將多出來的空間進行空間重分配，而是使用 alloc 屬性將這些空間大小記錄下來，以待後續使用。

而且 SDS 也提供手動釋放未使用空間的方法，這樣可以避免浪費記憶體。

壓縮列表

ZipList 實際是由一系列特殊編碼的連續記憶體塊組成的順序型數據結構，是 Hash 類型底層實現的一種方式。

結構

一個 ZipList 結構由 zlbytes、zltail、zllen、entries、zlend 這些屬性組成，這些屬性順序連接在一起組成了 ZipList：

ZipList 結構

zlbytes 用於記錄 ZipList 占用的記憶體位元組數，在對 ZipList 進行記憶體重分配或者計算 zlend 的位置時使用。

zltail 記錄了 ZipList 表尾結點距離 ZipList 的起始地址有多少個位元組，Redis 可以通過這個屬性快速確定表尾結點的地址。

zllen 記錄了 ZipList 包含的結點數量，當這個屬性小於 UINT16_MAX(65535) 時，這個值就是 ZipList 包含的結點數量；這個屬性大於 UINT16_MAX 時，則需要遍歷整個 ZipList 才能計算得出結點數量。一個 ZipList 可以包含任意多個結點，每個結點可以保存一個位元組數組或者一個整數值。

zlend 定義了特殊值 OxFF 用於標記 ZipList 的末端。

優點

ZipList 是一種節省記憶體的列表結構，對於普通的數組來說，其中每個元素占用的空間大小取決於最大的元素，而 ZipList 解決了這個問題。

因此，ZipList 在設計的時候，儘量讓每個元素按照實際的內容大小存儲，所以增加了 encoding 屬性，使得程式可以根據不同的 encoding 屬性來細化存儲大小。

由於數組每個元素都占用相同的記憶體空間，在遍曆數組時非常方便。

而 ZipList 每個元素存儲的記憶體空間不一樣，為瞭解決倒序遍歷的問題，增加了 prevlen 屬性來定位上一個元素的起始位置。

缺點

ZipList 內部的數據存儲是一段連續的空間，並且沒有預留記憶體空間，在移除結點時也是立即縮容，這表示每次寫操作都會進行記憶體分配操作。

第二個缺點就是，在某種情況下，ZipList 會出現連鎖更新的問題。

連鎖更新

ZipList 存儲了 prevlen 屬性表示前一個元素的長度，如果前一個元素長度小於 254 個位元組，則 prevlen 使用 1 個位元組保存這個長度值，如果前一個結點大於 254 個位元組，則 prevlen 使用 5 個位元組保存這個長度值。

如果 ZipList 中正好存在連續多個長度介於 250~253 個位元組的結點，這時需要在 ZipList 前面插入一個大於等於 254 個位元組的新結點，後一個結點的 prevlen 需要從 1 個位元組轉換成 5 個位元組，則後一個結點也會大於等於 254 個位元組，後續的結點以此類推，將會造成這部分結點出現連續更新。

快表

Redis 在 3.2 版本之後新增了快表數據結構，它是一種以 ZipList 為結點的雙端鏈表結構，可以理解成分段的 ZipList 鏈接在一起。

快表結構

在 3.2 版本之前，Redis 使用 ZipList 或 LinkedList 來實現 List 類型，並且有一個選擇的標準：

  • 保存的所有字元串元素的長度都小於 64 位元組，且保存的元素數量小於 512 個，選擇使用 ZipList
  • 否則使用 LinkedList 數據結構替代 ZipList

ZipList 要求有一段連續的記憶體空間，而使用 LinkedList 分配記憶體又會出現大量的記憶體碎片，因此 QuickList 對此做了優化，既避免出現大量的記憶體碎片，又避免一次性占用記憶體過大。

字典

字典在 Redis 中的應用非常廣泛，比如 Redis 的資料庫就是使用字典來作為底層實現的，對資料庫的增、刪、改、查操作都是構建在對字典的操作之上的。

哈希表結點

字典存儲數據的最小結構就是哈希表結點，Redis 中的哈希表結點使用 dictEntry 結構表示，每個 dictEntry 都保存著一個鍵值對：

typedef struct dictEntry {
    void *key;                  // 鍵值對的鍵
    union {                     // 鍵值對的值
        void *val;              // 可以是一個指針
        uint64_t u64;           // 可以是一個 uint64_t 整數
        int64_t s64;            // 可以是一個 int64_t 整數
    } v;

    struct dictEntry *next;     // 指向下個哈希表節點，形成鏈表
} dictEntry;

這裡值得註意的就是，next 指針會指向下一個哈希表結點，而它的功能就是用於解決哈希衝突，由此可見 Redis 的哈希表解決哈希衝突的方法是鏈地址法。

哈希表

哈希表是由多個哈希表結點組成的，Redis 中自定義的哈希表結構如下：

typedef struct dictht {
    dictEntry **table;          // 哈希表數組
    unsigned long size;         // 哈希表大小
    unsigned long sizemask;     // 哈希表大小掩碼，用於計算索引值，總是等於 size - 1
    unsigned long used;         // 該哈希表已有節點的數量
} dictht;

一般的，哈希表的物理存儲結構都是數組，Redis 的哈希表結構也是如此，而這個結點數組中的每個元素都是一個指向 dictEntry 結構的指針。

字典結構

Redis 為了使哈希表結構更加具有通用性，最後是在自定義的 dictht 哈希表結構外層再包一層字典結構，即是 dict 結構：

typedef struct dict {
    dictType *type;     // 類型特定函數
    void *privdata;     // 私有數據
    dictht ht[2];       // 哈希表
    int rehashidx;      // rehash 索引，當 rehash 不在進行時，值為 -1
} dict;

這裡展示了另一個 dictType 的結構，其實這個結構保存了一簇用於操作特定類型鍵值對的函數，Redis 會為用途不同的字典設置不同的類型特定函數。以下是 dictType 的結構定義：

typedof struct dictType {
    unsigned int (*hashFunction)(const void *key);                          // 計算哈希值的函數
    void *(*keyDup)(void *privData, const void *key);                       // 複製鍵的函數
    void *(*valDup)(void *privData, const void *obj);                       // 複製值的函數
    int (*keyCompare)(void *privData, const void *key1, const void *key2);  // 對比鍵的函數
    void *(*keyDestructor)(void *privData, const void *key);                // 銷毀鍵的函數
    void *(*keyDestructor)(void *privData, const void *obj);                // 銷毀值的函數
} dictType;

其實 dict 結構的 type 屬性和 privdata 屬性是針對不同類型的鍵值對，為創建多態字典而設置的。其中 privData 屬性保存了需要傳給那些類型特定函數的可選參數。

需要註意一下，字典結構的 ht 屬性是一個長度為 2 的數組，也就是說，這個字典結構存儲了兩個 dictType 結構，其中一個用於存儲實際使用的哈希表，另一個用於存儲重新哈希的臨時哈希表。

這個重新哈希還涉及到了 rehashidx 屬性，表示的是重新哈希當前的進度。

哈希演算法

當要將一個新的鍵值對添加到字典裡面時，程式會先根據鍵值對的鍵計算出哈希值和索引值，然後再根據索引值，將包含新鍵值對的哈希表結點放到哈希表數組的指定索引上。

Redis 計算哈希值和索引值的流程是：通過 dict 中的 type 屬性找到計算哈希值的函數，然後通過函數計算出對應的哈希值；確定對應的 dictht 結構之後，再根據 sizemask 和哈希值計算出索引值。

Redis 使用 MurmurHash2 演算法計算鍵的哈希值，其優點就是對於有規律的輸入值也能給出很好的隨機分佈性，並且演算法的計算速度也非常快。

哈希衝突

相同的哈希值會計算出相同的索引值，這就會導致哈希衝突。

Redis 使用了鏈地址法解決哈希衝突，每一個哈希表結點都有一個 next 指針，多個衝突的哈希表結點就會使用這個 next 指針構成一個單向鏈表，這就解決了鍵衝突的問題。

這裡需要註意一點，由於哈希表結點不存儲鏈表的尾結點，為了速度考慮，哈希衝突時構建的單向鏈表使用頭插法插入一個鏈表結點。

重新哈希

隨著操作不斷執行，哈希表保存的數據會逐漸增多或減少，為了讓哈希表的負載因數維持在一個合理的範圍內，Redis 會在必要的時候進行重新哈希的操作。

重新哈希指的是重新計算哈希表結點的哈希值和索引值，然後將鍵值對放到 ht 數組的另一個哈希表中。

Redis 對哈希表進行擴展操作的兩個條件如下：

  • 伺服器目前沒有正在執行 BGSAVE 命令或 BGREWRITEAOF 命令，並且哈希表的負載因數大於等於 1。
  • 伺服器目前正在執行 BGSAVE 命令或 BGREWRITEAOF 命令，並且哈希表的負載因數大於等於 5。

其中負載因數 = 哈希表已保存結點數量 / 哈希表大小。

另一方面，當哈希表的負載因數小於 0.1 時，Redis 會自動開始對哈希表進行收縮操作。

Redis 做自動擴展的條件包含兩種情況的原因是，執行 BGSAVE 和 BGREWRITEAOF 命令的是伺服器的子進程，而大多數操作系統都採用寫時複製技術以優化子進程的使用效率，所以在子進程存在期間，伺服器會提高執行擴展操作所需的負載因數。

漸進式重新哈希

為了避免因為重新哈希導致停止服務的情況，Redis 做重新哈希不是一次性完成的，而是分多次、漸進式地完成的。這也是 dict 結構中存在 ht 數組的原因。

漸進式重新哈希的好處在於它採取了分而治之的方式，將重新哈希所需的計算工作均攤到對字典的每個添加、刪除、查找和更新操作上，從而避免集中式重新哈希而帶來的龐大計算量。

整數集合

整數集合被 Redis 用於保存整數值的不重覆集合，以下是整數集合的實現：

typedef struct intset {
    uint32_t encoding;      // 編碼方式
    uint32_t length;        // 集合包含的元素數量
    int8_t contents[];      // 保存元素的數組
} intset;

其中 contents 數組中存儲的是整數集合中的元素，各個項按照從小到大進行排列，且數組中不包含任何重覆值。

length 屬性記錄了整數集合包含的元素個數，也相當於 contents 的數組長度。

encoding 記錄著整數集合的編碼方式，雖然 contents 的定義是 int8_t 類型，但實際上 contents 數組存儲元素的真正類型取決於 encoding 的值。

升級

整數集合的 contents 屬性可以存儲 int16、int32 或 int64 三種類型之一的數值，如果原本只存儲了 int16 類型的 contents 數組插入一個 int32 類型的數值，這時就涉及到整數集合的升級操作。

每當要將一個整數插入到整機集合中時，Redis 都會先判斷新元素的類型是否會比已存在的元素類型長，如果存在這種情況，整數集合需要先進行升級，才能將新元素添加到整數集合裡面。具體的步驟如下：

  1. 根據新元素的類型，擴展整數集合底層數組的空間大小，併為新元素分配空間；
  2. 將現有元素都轉換成與新元素的類型相同，並將轉換類型後的數值放置到正確的位上，並保持原數組的順序不變；
  3. 最後改變 encoding 的值，並將 length 加 1。

整數集合的升級操作是不可逆的，一旦對數組進行了升級，編碼就會一直保持升級後的狀態。

升級的好處

整數集合的升級策略有兩個好處，一個是提升整數集合的靈活性，另一個是儘可能地節約記憶體。

因為 C 語言是靜態類型語言，不同類型的整數值需要用不同的數組存儲，而整數集合通過升級策略將有原本不同類型的整數添加到同一個數組中，減少了類型錯誤的情況。

同樣的，整數集合通過使用一個數組存儲了三種不同類型的整數，又確保升級操作只會在有需要的時候進行，這可以儘量節省記憶體。

跳錶

跳錶是一種有序的數據結構，它通過在每個結點中維持多個指向其他結點的指針，從而達到快速訪問結點的目的。

跳錶結構

Redis 的跳錶包括了兩個結構，一個是跳錶結點的結構，另一個是存儲跳錶結點的外部結構。

跳錶結點

以下是跳錶結點的結構定義：

typedef struct zskiplistNode {
    struct zskiplistLevel {             // 索引層
        struct zskiplistNode *forward;  // 前進指針
        unsigned int span;              // 跨度
    } level[];
    robj *obj;                          // 成員對象
    double score;                       // 分值
    struct zskiplistNode *backward;     // 後退指針
} zskiplistNode;

這裡只是一個跳錶結點的結構，概念比較多。

跳錶的 zskiplistLevel 是一個數組，數組的長度表示結點有多少層索引，其中每個元素都包含一個指向其他結點的指針，程式可以通過這些指針加快訪問其他結點的速度。每次創建一個新的跳錶結點的時候，程式都會根據冪次定律隨機生成一個介於 1 和 32 之間的值作為數組的大小。

forward 是指每個索引層都包含指向下一個具有相同高度索引層的結點。也可以將前進指針理解成鏈表的 next 指針，從相同層級的角度上看，每一個相同層級的結點都組成了類似於鏈表的結構。

span 記錄了兩個結點之間的距離，實際上是用來計算排位的：在查找某個結點的過程中，將沿途訪問過的所有層的跨度累積起來，得到的結果就是目標結點在跳躍表的排位。

backward 用於從表尾向表頭訪問結點，對於最底層的鏈表來說，前進指針和後退指針使得這個鏈表成為一個雙向鏈表。

結點的 score 即是 Redis 的有序集合中的分值。結點的成員是一個指向 SDS 對象的指針，這個 SDS 對象存儲當前結點的值。對於相同分值的成員，Redis 會按照成員對象在字典序中的大小來進行排序，成員對象較小的結點會排在前面，而成員對象較大的結點會排在後面。

跳錶

僅使用多個跳錶結點就可以實現跳錶，但是新增外部跳錶結構可以使得程式更方便處理跳錶。Redis 的跳錶結構如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    // 頭節點，尾節點
    unsigned long length;                   // 節點數量
    int level;                              // 目前表內節點的最大層數
} zskiplist;

其中 head 指針和 tail 指針分別指向跳錶的表頭和表尾，通過這兩個指針，Redis 定位跳錶表頭結點和表尾結點的時間複雜度為 \(O(1)\)。

通過記錄 length 屬性，Redis 可以在 \(O(1)\) 的時間複雜度內返回跳錶的長度。

跳錶使用 level 屬性記錄了表內結點的最大層數，但這個是不包含表頭結點的層高的。

首發於「程式員翔仔」，點擊查看更多。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Java語言在Spark3.2.4集群中使用Spark MLlib庫完成XGboost演算法
    一、概述 XGBoost是一種基於決策樹的集成學習演算法，它在處理結構化數據方面表現優異。相比其他演算法，XGBoost能夠處理大量特征和樣本，並且支持通過正則化控制模型的複雜度。XGBoost也可以自動進行特征選擇並對缺失值進行處理。 二、代碼實現步驟 1、導入相關庫 import org.apach ...
  • Java語言在Spark3.2.4集群中使用Spark MLlib庫完成朴素貝葉斯分類器
    一、貝葉斯定理 貝葉斯定理是關於隨機事件A和B的條件概率，生活中，我們可能很容易知道P（A|B），但是我需要求解P（B|A），學習了貝葉斯定理，就可以解決這類問題，計算公式如下： P（A）是A的先驗概率 P（B）是B的先驗概率 P（A|B）是A的後驗概率（已經知道B發生過了） P（B|A）是B的後驗 ...
  • 給技術新人的ODPS優化建議
    數據開發基本都是從陌生到熟悉，但是寫多了就會發現各種好用的工具/函數，也會發現各種坑，本文分享了作者從拿到數據到數據開發到數據監控的一些實操經驗。 ...
  • 雲圖說｜雲資料庫GaussDB如何做到卓越性能
    摘要：對於資料庫來說，性能一直被視為最關鍵的部分。GaussDB作為華為自主創新研發的分散式關係型資料庫，那麼華為雲資料庫GaussDB在提升資料庫性能方面都有哪些黑科技呢？ 本文分享自華為雲社區《【雲圖說】第275期 雲資料庫GaussDB如何做到卓越性能》，作者：閱識風雲。 對於資料庫來說，性能 ...
  • 基於chunjun純鈞的增量數據同步問題排查【博客園-實習小生】
    ☞ 商品介面的定義 價格、庫存量、發貨地點等。此外，它還可以提供商品的詳細信息，包括商品的圖片、詳細描述、規格參數、售後服務等。這些信息可以幫助用戶更好地瞭解商品，從而更好地選擇商品。 其次，電商平臺商品詳情介面的實現原理是基於RESTful API。RESTful API是一種基於HTTP協議的A ...
  • 數據開發提效有秘訣！離線開發BatchWorks 六大典型場景拆解
    回顧大數據的發展歷程，一句話概括就是海量數據的高效處理。在當今快節奏、不斷變化的市場環境下，優秀的開發效率已經成為企業數字化轉型的必備條件。 數棧離線開發BatchWorks 是一款專註離線數據ELT開發的產品，採用先進的大數據生態底層技術，具備高性能且功能豐富的大數據處理能力，對大數據離線計算、數 ...
  • 活動 | GreatSQL社區亮相2023 DTC 分享開源技術成果實踐
    4月7-8日，年度資料庫行業盛會——2023數據技術嘉年華（DTC 2023）如期而至。 此次盛會匯聚了全國各地數千名數據領域學術精英、領袖人物、技術專家、從業者和技術愛好者，共同見證行業蓬勃發展、生態融合共贏、技術迭代升級及市場風雲變遷。 GreatSQL作為萬里資料庫主導成立的開源資料庫社區，首 ...
  • ORACLE如何查看用戶管理備份與恢復的記錄
    在Oracle資料庫中，如果我們使用用戶管理備份與恢復（User-Managed Backup and Recovery）方式去備份還原資料庫的話，如何獲取用戶管理備份與恢復的記錄信息呢？例如，我要查看某個資料庫實例做用戶管理備份的記錄。一般使用下麵腳本。似乎用戶管理備份比較“簡單”，目前我查了相關 ...
一周排行
    -Advertisement-
    Play Games
  • C# + WPF 音頻播放器 界面優雅，體驗良好
    前言 本文介紹一款使用 C# 與 WPF 開發的音頻播放器，其界面簡潔大方，操作體驗流暢。該播放器支持多種音頻格式（如 MP4、WMA、OGG、FLAC 等），並具備標記、實時歌詞顯示等功能。 另外，還支持換膚及多語言（中英文）切換。核心音頻處理採用 FFmpeg 組件，獲得了廣泛認可，目前 Git ...
  • OAuth2.0授權-gitee授權碼模式
    OAuth2.0授權驗證-gitee授權碼模式 本文主要介紹如何筆者自己是如何使用gitee提供的OAuth2.0協議完成授權驗證並登錄到自己的系統，完整模式如圖 1、創建應用 打開gitee個人中心->第三方應用->創建應用 創建應用後在我的應用界面，查看已創建應用的Client ID和Clien ...
  • FastReport.OpenSource .Net下開源免費報表列印組件
    解決了這個問題：《winForm下，fastReport.net 從.net framework 升級到.net5遇到的錯誤“Operation is not supported on this platform.”》 本文內容轉載自：https://www.fcnsoft.com/Home/Sho ...
  • 如何在 ASP.NET Core Web API 方法執行前後 “偷偷“ 作一些 “壞“ 事？初識 ActionFilterAttribute
    國內文章 WPF 從裸 Win 32 的 WM_Pointer 消息獲取觸摸點繪製筆跡 https://www.cnblogs.com/lindexi/p/18390983 本文將告訴大家如何在 WPF 裡面，接收裸 Win 32 的 WM_Pointer 消息，從消息裡面獲取觸摸點信息，使用觸摸點 ...
  • 在 ASP.NET Core Web API 中使用異常篩選器捕獲和統一處理異常
    前言 給大家推薦一個專為新零售快消行業打造了一套高效的進銷存管理系統。 系統不僅具備強大的庫存管理功能，還集成了高性能的輕量級 POS 解決方案，確保頁面載入速度極快，提供良好的用戶體驗。 項目介紹 Dorisoy.POS 是一款基於 .NET 7 和 Angular 4 開發的新零售快消進銷存管理 ...
  • AbpHelper CLI積累與實戰分享
    ABP CLI常用的代碼分享 一、確保環境配置正確 安裝.NET CLI： ABP CLI是基於.NET Core或.NET 5/6/7等更高版本構建的，因此首先需要在你的開發環境中安裝.NET CLI。這可以通過訪問Microsoft官網下載並安裝相應版本的.NET SDK來實現。 安裝ABP ...
  • 記一次HttpClient使用問題分析
    問題 問題是這樣的：第三方的webapi，需要先調用登陸介面獲取Cookie，訪問其它介面時攜帶Cookie信息。 但使用HttpClient類調用登陸介面，返回的Headers中沒有找到Cookie信息。 分析 首先，使用Postman測試該登陸介面，正常返回Cookie信息，說明是HttpCli ...
  • .NET周刊【9月第3期 2024-09-15】
    國內文章 關於.NET在中國為什麼工資低的分析 https://www.cnblogs.com/thinkingmore/p/18406244 .NET在中國開發者的薪資偏低，主要因市場需求、技術棧選擇和企業文化等因素所致。歷史上，.NET曾因微軟的閉源策略發展受限，儘管後來推出了跨平臺的.NET ...
  • 我的網站集成ElasticSearch初體驗
    在WPF開發應用中，動畫不僅可以引起用戶的註意與興趣，而且還使軟體更加便於使用。前面幾篇文章講解了畫筆（Brush），形狀（Shape），幾何圖形（Geometry），變換（Transform）等相關內容，今天繼續講解動畫相關內容和知識點，僅供學習分享使用，如有不足之處，還請指正。 ...
  • 第23篇 委托的概述
    什麼是委托？ 委托可以說是把一個方法代入另一個方法執行，相當於指向函數的指針；事件就相當於保存委托的數組； 1.實例化委托的方式： 方式1：通過new創建實例： public delegate void ShowDelegate(); 或者 public delegate string ShowDe ...
所有分類