博客 / 詳情

返回

Redis數據結構(一)-Redis的數據存儲及String類型的實現

1 引言

Redis作為基於內存的非關係型的K-V數據庫。因讀寫響應快速、原子操作、提供了多種數據類型String、List、Hash、Set、Sorted Set、在項目中有着廣泛的使用，今天我們來探討下下Redis的數據結構是如何實現的。

2 數據存儲

2.1 RedisDB

Redis將數據存儲在redisDb中，默認0~15共16個db。每個庫都是獨立的空間，不必擔心key衝突問題，可通過select命令切換db。集羣模式使用db0

typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
...
} redisDb;
  • dict：數據庫鍵空間，保存着數據庫中的所有鍵值對
  • expires：鍵的過期時間，字典的鍵為鍵，字典的值為過期事件UNIX時間戳

2.2 Redis哈希表實現

2.2.1 哈希字典dict

K-V存儲我們最先想到的就是map，在Redis中通過dict實現，數據結構如下：

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;
  • type：類型特定函數是一個指向dictType結構的指針，每個dictType結構保存了一簇用於操作特定類型鍵值對的函數，Redis會為用途不同的字典設置不同的類型特定函數。
  • privdata：私有數據保存了需要傳給那些類型特定函數的可選參數
  • ht[2]：哈希表一個包含兩個項的數組，數組中的每個項都是一個dictht哈希表，一般情況下，字典只使用ht[0] 哈希表，ht[1]哈希表只會在對ht[0]哈希表進行rehash時使用
  • rehashidx：rehash 索引，當rehash不在進行時，值為 -1

hash數據存在兩個特點：

  • 任意相同的輸入一定能得到相同的數據
  • 不同的輸入，有可能得到相同的輸出

針對hash數據的特點，存在hash碰撞的問題，dict通過dictType中的函數能夠解決這個問題

typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
...
} dictType;
  • hashFunction：用於計算key的hash值的方法
  • keyCompare：key的值比較方法

2.2.2 哈希表 dictht

dict.h/dictht表示一個哈希表，具體結構如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
  • table：數組指針，數組中的每個元素都是一個指向dict.h/dictEntry結構的指針，每個dictEntry結構保存着一個鍵值對。
  • size：記錄了哈希表的大小，也就是table數組的大小，大小總是2^n
  • sizemask：總是等於size - 1，這個屬性和哈希值一起決定一個鍵應該被放到table數組的哪個索引上面。
  • used：記錄了哈希表目前已有節點（鍵值對）的數量。

鍵值對dict.h/dictEntry

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
  • key：保存着鍵值對中的鍵(SDS類型對象)
  • val：保存着鍵值對中的值，可以是一個uint64\_t整數，或者是一個int64\_t整數，又或者是一個指針指向一個被redisObject包裝的值
  • next：指向下個哈希表節點，形成鏈表指向另一個哈希表節點的指針，這個指針可以將多個哈希值相同的鍵值對連接在一次，以此來解決鍵衝突（collision）的問題

使用hash表就一定會存在hash碰撞的問題，hash碰撞後在當前數組節點形成一個鏈表，在數據量超過hash表長度的情況下，就會存在大量節點稱為鏈表，極端情況下時間複雜度會從O(1)變為O(n)；如果hash表的數據再不斷減少，會造成空間浪費的情況。Redis會針對這兩種情況根據負載因子做擴展與收縮操作：

  • 負載因子：哈希表已保存節點數量/哈希表大小，load_factor = ht[0].used/ht[0].size
  • 擴展操作：
  • 服務器目前沒有在執行BGSAVE命令或者BGREWRITEAOF命令，並且哈希表的負載因子大於等於 1；
  • 服務器目前正在執行BGSAVE命令或者BGREWRITEAOF命令，並且哈希表的負載因子大於等於5；

收縮操作：

  • 當哈希表的負載因子小於 0.1 時， 程序自動開始對哈希表執行收縮操作。

Redis在擴容時如果全量擴容會因為數據量問題導致客户端操作短時間內無法處理，所以採用漸進式 rehash進行擴容，步驟如下：

  1. 同時持有2個哈希表
  2. 將rehashidx的值設置為0,表示rehash工作正式開始
  3. 在rehash進行期間， 每次對字典執行添加、刪除、查找或者更新操作時，程序除了執行指定的操作以外,還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1] ,當rehash工作完成之後，程序將rehashidx屬性的值增一
  4. 某個時間點上，ht[0]的所有鍵值對都會被rehash至ht[1] ，這時程序將rehashidx屬性的值設為-1， 表示rehash操作已完成

在漸進式 rehash 進行期間，字典的刪除（delete）、查找（find）、更新（update）等操作會在兩個哈希表上進行；在字典裏面查找一個鍵的話， 程序會先在 ht[0] 裏面進行查找，如果沒找到的話，就會繼續到ht[1]裏面進行查找；新添加到字典的鍵值對一律會被保存到 ht[1] 裏面，而ht[0]則不再進行任何添加操作：這一措施保證了ht[0]包含的鍵值對數量會只減不增(如果長時間不進行操作時，事件輪詢進行這種操作)，並隨着rehash操作的執行而最終變成空表。

dict.h/redisObject

Typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
}
  • type:4：約束客户端操作時存儲的數據類型，已存在的數據無法修改類型，4bit
  • encoding:4：值在redis底層的編碼模式，4bit
  • lru:LRU_BITS：內存淘汰策略
  • refcount：通過引用計數法管理內存，4byte
  • ptr：指向真實存儲值的地址，8byte

完整結構圖如下：

3 String類型

3.1 String類型使用場景

String 字符串存在有三種類型：字符串，整數，浮點。主要有以下使用場景

1）頁面動態緩存
比如生成一個動態頁面，首次可以將後台數據生成頁面，並且存儲到redis字符串中。再次訪問，不再進行數據庫請求，直接從redis中讀取該頁面。特點是：首次訪問比較慢，後續訪問快速。

2）數據緩存
在前後分離式開發中，有些數據雖然存儲在數據庫，但是更改特別少。比如有個全國地區表。當前端發起請求後，後台如果每次都從關係型數據庫讀取，會影響網站整體性能。
我們可以在第一次訪問的時候，將所有地區信息存儲到redis字符串中，再次請求，直接從數據庫中讀取地區的json字符串，返回給前端。

3）數據統計
redis整型可以用來記錄網站訪問量，某個文件的下載量。（原子自增自減）

4）時間內限制請求次數
比如已登錄用户請求短信驗證碼，驗證碼在5分鐘內有效的場景。當用户首次請求了短信接口，將用户id存儲到redis 已經發送短信的字符串中，並且設置過期時間為5分鐘。當該用户再次請求短信接口，發現已經存在該用户發送短信記錄，則不再發送短信。

5）分佈式session
當我們用nginx做負載均衡的時候，如果我們每個從服務器上都各自存儲自己的session，那麼當切換了服務器後，session信息會由於不共享而會丟失，我們不得不考慮第三應用來存儲session。通過我們用關係型數據庫或者redis等非關係型數據庫。關係型數據庫存儲和讀取性能遠遠無法跟redis等非關係型數據庫。

3.2 String類型的實現——SDS結構

Redis並沒有直接使用C字符串實現String類型，在Redis3.2版本之前通過SDS實現

Typedef struct sdshdr {
int len;
int free;
char buf[];
};
  • len：分配內存空間
  • free：剩餘可用分配空間
  • char[]：value值實際數據

3.3 SDS與C字符串之間的區別

3.3.1 查詢時間複雜度

C獲取字符串長度的複雜度為O(N)。而SDS通過len記錄長度，從C的O(n)變為O(1)。

3.3.2 緩衝區溢出

C字符串不記錄自身長度容易造成緩衝區溢出（buffer overflow）。SDS的空間分配策略完全杜絕了發生緩衝區溢出的可能性,當需要對SDS進行修改時，會先檢查SDS的空間是否滿足修改所需的要求，如果不滿足的話SDS的空間擴展至執行修改所需的大小，然後才執行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小，也不會出現緩衝區溢出問題。

在SDS中，buf數組的長度不一定就是字符數量加一，數組裏面可以包含未使用的字節，而這些字節的數量就由SDS的free屬性記錄。通過未使用空間，SDS實現了空間預分配和惰性空間釋放兩種優化策略：

  • 空間預分配：當對一個SDS進行修改，並且需要對SDS進行空間擴展的時候，程序不僅會為SDS分配修改所必須要的空間，還會為SDS分配額外的未使用空間。擴展SDS 空間之前，會先檢查未使用空間是否足夠， 如果足夠的話，就會直接使用未使用空間，而無須執行內存重分配。如果不夠根據(len + addlen(新增字節)) * 2的方式進行擴容，大於1M時，每次只會增加1M大小。通過這種預分配策略，SDS將連續增長N次字符串所需的內存重分配次數從必定N次降低為最多N次。
  • 惰性空間釋放：惰性空間釋放用於優化SDS的字符串縮短操作：當需要縮短SDS保存的字符串時，程序並不立即使用內存重分配來回收縮短後多出來的字節，而是使用free屬性將這些字節的數量記錄起來，並等待將來使用。

3.3.3 二進制安全

C字符串中的字符必須符合某種編碼（比如 ASCII，並且除了字符串的末尾之外，字符串裏面不能包含空字符， 否則最先被程序讀入的空字符將被誤認為是字符串結尾。

SDS的API都是二進制安全的（binary-safe）：都會以處理二進制的方式來處理SDS存放在buf數組裏的數據，程序不會對其中的數據做任何限制、過濾、或者假設 —— 數據在寫入時是什麼樣的，它被讀取時就是什麼樣。redis不是用這個數組來保存字符，而是用它來保存一系列二進制數據。

3.4 SDS結構優化

String類型所存儲的數據可能會幾byte存在大量這種類型數據，但len、free屬性的int類型會佔用4byte共8byte存儲，3.2之後會根據字符串大小使用sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64數據結構存儲，具體結構如下：

struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
  • unsign char flags：3bit表示類型，5bit表示未使用長度
  • len：表示已使用長度
  • alloc：表示分配空間大小，剩餘空間大小可以使用alloc - len獲得

3.5 字符集編碼

redisObject包裝存儲的value值，通過字符集編碼對數據存儲進行優化，string類型的編碼方式有如下三種：

  • embstr:
    CPU每次按Cache Line 64byte讀取數據，一個redisObject對象為16byte，為填充64byte大小，會向後再讀取48 byte數據。但獲取實際數據時還需要再通過*ptr指針讀取對應內存地址的數據。而一個sdshdr8屬性的信息佔用4byte，其餘44byte可以用來存儲數據。如果value值小於44，byte可以通過一次讀取緩存行獲取數據。
  • int:
    如果SDS小於20位，並且能夠轉換成整型數字，redisObject的*ptr指針會直接進行存儲。
  • raw:
    SDS

4 總結

redis作為k-v數據存儲，因查找和操作的時間複雜度都是O(1)和豐富的數據類型及數據結構的優化，瞭解了這些數據類型和結構更有利於我們平時對於redis的使用。下一期將對其它常用數據類型List、Hash、Set、Sorted Set所使用的ZipList、QuickList、SkipList做進一步介紹，對於文章中不清晰不準確的地方歡迎大家一起討論交流。

作者：盛旭

redis , 數據結構 , 數據存儲 , string
user avatar beibiaobaidehaigui 頭像
1 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.