Redis | 第一部分：數據結構與對象 上篇《Redis設計與實現》

• 2021 年 11 月 17 日
• 筆記
• Redis學習筆記, 學習筆記

前言

參考資料：《Redis設計與實現 第二版》；

本篇筆記按照書里的脈絡，將知識點分為四個部分。其中第一部分數據結構與對象分為上中下篇，上篇包括：SDS、鏈表和字典；中篇包括跳躍表、整數集合和壓縮列表；下篇為對象；

1. 簡單動態字元串

• Redis構建一種名為簡單動態字元串（SDS）的抽象類型，並將SDS作為Redis的默認字元串表示；
• 除了用作字元串值外，SDS還被用作緩衝區buffer，如：AOF模組中的AOF緩衝區、客戶端狀態中的輸入緩衝區；

1.1 SDS的定義

• SDS的定義在sds.h/sdshdr結構：

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

1.2 空間預分配與惰性空間釋放

• SDS相比C字元串的優點：
  • 在常數時間複雜度內獲取字元串長度；
  • 杜絕緩衝區溢出（空間預分配）；
  • 減少修改字元串時帶來的記憶體重分配次數（空間預分配）；
  • 可保存二進位（使用len值判斷字元串是否結束而不是 \0 ）；
  • 兼容部分C字元串函數（在字元串末尾保留空字元 \0）
• 通過未使用空間free，SDS實現空間預分配和惰性空間釋放：
  • 空間預分配：用於SDS字元串增長。修改後小於1MB，則 len = free；反之分配1MB額外空間；
  • 惰性空間釋放：用於SDS字元串縮短。即在有需要時才回收記憶體；

1.3 SDS的API

2. 鏈表

• C語言沒有內置鏈表，所以Redis構建自己的鏈表；
• 鏈表在Redis里的應用：發布與訂閱、慢查詢、監視器、Redis伺服器保存多個客戶端、列表鍵底層等、構建客戶端輸出緩衝區（output buffer）；

2.1 鏈表與節點的定義

• 鏈表節點的定義與實現在adlist.h/listNode結構里；

  typedef struct listNode {
      //前置節點
      struct listNode *prev;
      //後置節點
      struct listNode *next;
      //節點的值
      void *value;
  } listNode;
  

• 鏈表的定義在adlist.h/list中：

  typedef struct list {
      //表頭節點
      listNode *head;
      //表尾節點
      listNode *tail;
      //鏈表所包含的節點數量
      unsigned long len;
      //節點值複製函數
      void *(*dup)(void *ptr);
      //節點值釋放函數
      void (*free)(void *ptr);
      //節點值對比函數
      int (*match)(void *ptr, void *key);
  } list;
  

2.2 鏈表的API

3. 字典

• 字典，又稱符號表、關聯數組、映射，用於保存鍵值對；
• Redis自己構建字典；
• 字典在Redis里的應用：Redis資料庫底層、哈希鍵的底層實現等；
• Redis的字典使用哈希表作為底層實現；

3.1 哈希表與哈希節點

• 字典所使用的哈希表的定義，在dict.h/dictht結構中：

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

  • table是一個數組，數組的每個元素都是指向dict.h/dictEntry結構的指針；

• 哈希表節點的定義，在dict.h/dictEntry結構；

  typedef struct dictEntry {
      //鍵
      void *key;
      //值
      union{
          void *val;
          uint64_t u64;
          int64_t s64;
      } v;
      //指向下個哈希表節點，形成鏈表
      struct dictEntry *next;
  } dictEntry;
  

  • next值的作用：將多個哈希值相同的鍵值對連接，解決鍵衝突問題（collision）；

3.2 字典

• 字典的定義，在dict.h/dict結構：

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

  • type和privdata屬性：針對不同類型鍵值對，為創建多態字典而設置；
  • type屬性：是一個指向dictType的指針，Redis為用途不同的字典設置不同的dictType結構體，進而設置不同的類型特定函數；
  • privdata屬性：保存了需要傳給類型特定函數的可選參數；
  • ht[2]屬性：每一項是dictht哈希表，一般字典只用ht[0]哈希表。對ht[0]進行rehash時使用ht[1]；
  • trehashidx屬性：記錄當前rehash的進度；

3.3 哈希演算法

• Redis計算哈希值與索引值的方法：

  # 使用字典設置哈希函數，計算key的哈希值
  hash = dict -> type -> hashFunction(key)
  
  # 使用哈希表的sizemask屬性和哈希值，計算索引值
  # 根據情況不同，ht[x]可以是ht[0]或者ht[1]
  index = hash & dict -> ht[x].sizemask
  

• 當字典被用作資料庫底層實現，或哈希鍵底層實現時，Redis使用MurmurHash2演算法計算鍵的哈希值；

3.4 解決鍵衝突

• 鍵衝突：有兩個或以上的鍵被分配到哈希表數組的同一個索引；
• Redis使用鏈地址法解決鍵衝突問題；
• 鏈地址法：dictEntry哈希節點裡有個next屬性，可以用其將索引值相同的節點連成鏈表；
  • 出於速度考慮，將新節點添加到鏈表表頭，O(1)；

3.5 rehash

• 通過執行rehash（重新散列）來擴展和收縮哈希表；
• rehash的步驟：
  • 1）為ht[1]分配空間，若擴展，則ht[1].size為第一個大於等於ht[0].used*2的 2ⁿ。若收縮，則ht[1].size為第一個大於等於ht[0].used的 2ⁿ；
  • 2）將ht[0]中的所有鍵值對rehash到ht[1]上；
  • 3）遷移完後，釋放ht[0]，將ht[1]設置為ht[0]，創建一個空白哈希表ht[1]；
• 哈希表擴展與收縮的時機：
  • 負載因子的計算：load_factor = ht[0].used / ht[0].size；
  • 擴展：伺服器沒有執行BGSAVE和BGREWRITEAOF命令，並且負載因子大於等於1；
  • 擴展：伺服器正在執行BGSAVE和BGREWRITEAOF命令，並且負載因子大於等於5；
    • 避免在執行該命令（子進程存在期間）時進行擴展操作，避免不必要的記憶體寫入操作；
  • 收縮：負載因子小於0.1；

3.6 漸進式rehash

• 當鍵值對成萬上億時，需要分多次、漸進式完成rehash；
• 漸進式rehash的步驟：
  • 1）為ht[1]分配空間；
  • 2）將字典的索引計數器變數rehashidx設置為0，表示rehash正式開始；
  • 3）rehash期間，每個對字典操作完成後，將rehashidx++；
  • 4）當ht[0]中的所有鍵值對rehash到ht[1]後，rehashidx設置為 -1；
• 漸進式hash期間：
  • 查找操作先查ht[0]，再查ht[1]；
  • 新增操作只在ht[1]新增，保證ht[0]只減不增；

3.7 字典的API

最後

新人製作，如有錯誤，歡迎指出，感激不盡！
歡迎關注公眾號，會分享一些更日常的東西！
如需轉載，請標註出處！