Redis 數據類型底層實現

Redis 的數據庫就是使用字典 (哈希表) 來作爲底層實現的，對數據庫的增刪改查都是構建在字典 (哈希表) 的操作之上的。

typedef struct redisDb { 
    int id;         // 數據庫ID標識
    dict *dict;     // 鍵空間，存放着所有的鍵值對              
    dict *expires;  // 過期哈希表，保存着鍵的過期時間                          
    dict *watched_keys; // 被watch命令監控的key和相應client    
    long long avg_ttl;  // 數據庫內所有鍵的平均TTL（生存時間）     
} redisDb;

每次在 Redis 中創建數據時都會生成兩個對象：鍵對象、值對象。Redis 對象用 redisObject 結構表示，其中類型、編碼和指針記錄了 Redis 五個數據類型和六個底層數據結構的關係。

typedef struct redisObject{
     //類型
     unsigned type:4;
     //編碼
     unsigned encoding:4;
     //指向底層數據結構的指針
     void *ptr;
     //引用計數
     int refcount;
     //記錄最後一次被程序訪問的時間
     unsigned lru:22;
}robj

NO.1

string 對象

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

  1. embstr 的使用只分配一次內存空間（因此 redisObject 和 sds 是連續的），而 raw 需要分配兩次內存空間（分別爲 redisObject 和 sds 分配空間）。

  2. 因爲 redis 中的 embstr 實現爲只讀，所以只要是修改 embstr 對象，修改後的對象一定是 raw 的。

NO.2

list 對象

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

鏈表具有前置節點和後置節點的引用，表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL，通過 len 屬性獲取鏈表長度，鏈表節點使用 void* 指針來保存節點值，可以保存各種不同類型的值。

NO.3

hash 對象

# hash表
typedef struct dictht{
     //哈希表數組
     dictEntry **table;
     //哈希表大小
     unsigned long size;
     //哈希表大小掩碼，用於計算索引值
     //總是等於 size-1
     unsigned long sizemask;
     //該哈希表已有節點的數量
     unsigned long used;
}dictht
# hash表節點
typedef struct dictEntry{
     //鍵
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
     //指向下一個哈希表節點，形成鏈表
     struct dictEntry *next;
}dictEntry
# 字典
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

  1. 在字典中維持一個索引計數器變量 rehashidx，並將設置爲 0，表示 rehash 開始。

  2. 在 rehash 期間每次對字典進行增加、查詢、刪除和更新操作時，除了執行指定命令外；還會將 ht[0] 中 rehashidx 索引上的值 rehash 到 ht[1]，操作完成後 rehashidx+1。

  3. 字典操作不斷執行，最終在某個時間點，所有的鍵值對完成 rehash，這時將 rehashidx 設置爲 - 1，表示 rehash 完成。

  4. 在漸進式 rehash 過程中，字典會同時使用兩個哈希表 ht[0] 和 ht[1]，所有的更新、刪除、查找操作也會在兩個哈希表進行。例如要查找一個鍵的話，服務器會優先查找 ht[0]，如果不存在，再查找 ht[1]，諸如此類。此外當執行新增操作時，新的鍵值對一律保存到 ht[1]，不再對 ht[0] 進行任何操作，以保證 ht[0] 的鍵值對數量只減不增，直至變爲空表。

NO.4

set 對象

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

NO.5

zset 對象

  1. 由很多層結構組成

  2. 每一層都是一個有序的鏈表，排列順序爲由高層到底層，都至少包含兩個鏈表節點，分別是前面的 head 節點和後面的 nil 節點

  3. 最底層的鏈表包含了所有的元素

  4. 如果一個元素出現在某一層的鏈表中，那麼在該層之下的鏈表也全都會出現（上一層的元素是當前層的元素的子集）

  5. 鏈表中的每個節點都包含兩個指針，一個指向同一層的下一個鏈表節點，另一個指向下一層的同一個鏈表節點

typedef struct zskiplistNode {
     //層
     struct zskiplistLevel{
           //前進指針
           struct zskiplistNode *forward;
           //跨度
           unsigned int span;
     }level[];
     //後退指針
     struct zskiplistNode *backward;
     //分值
     double score;
     //成員對象
     robj *obj;
} zskiplistNode
typedef struct zskiplist{
     //表頭節點和表尾節點
     structz skiplistNode *header, *tail;
     //表中節點的數量
     unsigned long length;
     //表中層數最大的節點的層數
     int level;
}zskiplist;

typedef struct zset{
     //跳躍表
     zskiplist *zsl;
     //字典
     dict *dice;
} zset;

NO.6

內存回收和共享

  1. 創建一個新對象，屬性 refcount 初始化爲 1

  2. 對象被一個新程序使用，屬性 refcount 加 1

  3. 對象不再被一個程序使用，屬性 refcount 減 1

  4. 當對象的引用計數值變爲 0 時，對象所佔用的內存就會被釋放

定期刪除 + 惰性刪除

定期刪除： redis 默認是每隔 100ms 就隨機抽取一些設置了過期時間的 key，檢查其是否過期，如果過期就刪除。

惰性刪除 ： 當去查詢已經過期的 key 時，Redis 纔會對其刪除。

  1. volatile-lru   利用 LRU 算法移除設置過過期時間的 key (LRU: 最近使用 Least Recently Used)

  2. allkeys-lru   利用 LRU 算法移除任何 key

  3. volatile-random 移除設置過過期時間的隨機 key

  4. allkeys-random  移除隨機 key

  5. volatile-ttl   移除即將過期的 key(minor TTL)

  6. noeviction  不移除任何 key，只是返回一個寫錯誤 ，默認選項

  7. volatile-lfu：從所有配置了過期時間的鍵中移除使用頻率最少的鍵

  8. allkeys-lfu：從所有鍵中移除使用頻率最少的鍵

NO.7

降低內存佔用的幾種方式

降低內存佔用有助於減少創建快照和加載快照的時間、提升載入 AOF 文件和重新文件的效率、縮短主從同步所需的時間等！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/l1YoGzvMwcW8j9444Mi85A

猜你喜歡