概念

Redis作為一個開源的用C編寫的非關係型資料庫，基於優秀的CRUD效率，常用於軟體系統的緩存，其本身提供了以下五種數據格式：

  • string：字元串
  • list：列表
  • hash：散列表
  • set：無序集合
  • zset：有序集合

接下來我們就要針對這五種數據結構，來分析其底層的結構

這裡選用的版本是redis-5.0.4，所以可能有很多地方和如今網路上的其他博文不太一致，不同的地方我會在文中指出

string

因為redis使用c語言開發，所以自然沒有java和c++的那些字元串類庫，在redis中，其自己定義了一種字元串格式，叫做SDS（Simple Dynamic String），即簡單動態字元串

這個結構定義在sds.h中：

typedef char *sds;

但是這個sds類型僅作為參數和返回值使用，並不是真正用於操作的類型，真正核心的部分是下面的這些類：

struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};

除掉第一個結構體（已經棄用），sds具體類型的結構可以分為以下部分：

  • len：已使用的長度，即字元串的真實長度
  • alloc：除去標頭和終止符( )後的長度
  • flags：低3位表示字元串類型，其餘5位未使用（我暫時沒發現redis在哪裡使用過這個屬性）
  • buf[]：存儲字元數據

這裡和老版本做一下對比，因為我手頭只有4.x和5.x的版本，它們sds的實現是一致的，但是據其他人說sds之前的版本實現方式不同，有時間我會去下載下來看一下，其將字元串分為以下部分：

  • len：buf中已經佔有的長度（表示此字元串的實際長度）
  • free：buf中未使用的緩衝區長度
  • buf[]：實際保存字元串數據的地方

redis同時寫重寫了大量的與sds類型相關的方法，那redis為什麼要這麼下功夫呢，有以下4個優點：

  • 降低獲取字元串長度的時間複雜度到O(1)
  • 減少了修改字元串時的內存重分配次數
  • 兼容c字元串的同時，提高了一些字元串工具方法的效率
  • 二進位安全（數據寫入的格式和讀取的格式一致）

list

我們查看源文件可以看到有兩個list，一個是ziplist，字面意是壓縮列表，另一個是quicklist，字面意是快速列表，在redis中直接使用的是quicklist，但是我們先來看ziplist

ziplist

ziplist並不是一個類名，其結構是下面這樣的： <zlbytes><zltail><entries><entry>...<entry><zlend>

其中各部分代表的含義如下：

  • zlbytes：4個位元組（32bits），表示ziplist佔用的總位元組數
  • zltail：4個位元組（32bits），表示ziplist中最後一個節點在ziplist中的偏移位元組數
  • entries：2個位元組（16bits），表示ziplist中的元素數
  • entry：長度不定，表示ziplist中的數據
  • zlend：1個位元組（8bits），表示結束標記，這個值固定為ff（255）

這些數據均為小端存儲，所以可能有些人查看數據的二進位流與其含義對應不上，其實是因為讀數據的方式錯了

ziplist內部採取數據壓縮的方式進行存儲，壓縮方式就不是重點了，我們僅從宏觀來看，ziplist類似一個封裝的數組，通過zltail可以方便地進行追加和刪除尾部數據、使用entries可以方便地計算長度

但是其依然有數組的缺點，就是當插入和刪除數據時會頻繁地引起數據移動，所以就引出了quicklist數據類型

quicklist

其核心數據結構如下：

typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* ziplist所有節點的個數 */
unsigned long len; /* quicklistNode節點的個數 */
int fill : 16; /* 單個節點的填充因子 */
unsigned int compress : 16; /* 壓縮端結點的深度 */
} quicklist;

我們可以明顯地看出，quicklist是一個雙向鏈表的結構，但是內部又涉及了ziplist，我們可以這麼說，在宏觀上，quicklist是一個雙向鏈表，在微觀上，每一個quicklist的節點都是一個ziplist

在redis.conf中，可以使用下面兩個參數來進行優化：

  • list-max-ziplist-size：表示每個quicklistNode的位元組大小。默認為2，表示8KB
  • list-compress-depth：表示quicklistNode節點是否要壓縮。默認為0，表示不壓縮

這種存儲方式的優點和鏈表的優點一致，就是插入和刪除的效率很高，而鏈表查詢的效率又由ziplist來進行彌補，所以quicklist就成為了list數據結構的首選

hash

hash這種結構在redis的使用時最為常見，在redis中，hash這種結構有兩種表示：zipmap和dict

zipmap

zipmap其格式形如下面這樣： <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

各部分的含義如下：

  • zmlen：1個位元組，表示zipmap的總位元組數
  • len：1~5個位元組，表示接下來存儲的字元串長度
  • free：1個位元組，是一個無符號的8位數，表示字元串後面的空閑未使用位元組數，由於修改與鍵對應的值而產生

這其中相鄰的兩個字元串就分別是鍵和值，比如在上面的例子中，就表示"foo" => "bar", "hello" => "world"這樣的對應關係

這種方式的缺點也很明顯，就是查找的時間複雜度為O(n)，所以只能當作一個輕量級的hashmap來使用

dict

這種方式就適於存儲大規模的數據，其格式如下：

typedef struct dict {
dictType *type;/* 指向自定義類型的指針，可以存儲各類型數據 */
void *privdata; /* 私有數據的指針 */
dictht ht[2];/* 兩個hash表，一般只有h[0]有效，h1[1]只在rehash的時候才有值 */
long rehashidx; /* -1：沒有在rehash的過程中，大於等於0：表示執行rehash到第幾步 */
unsigned long iterators; /* 正在遍歷的迭代器個數 */
} dict;

如果我們不想更深入的話了解到這種程度就可以了，其中真正存儲數據的是dictEntry結構，如下：

typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;

很明顯是一個鏈表，我們知道這是採用鏈式結構存儲就足夠了

這種方式會消耗較多的內存，所以一般數據較少時會採用輕量級的zipmap

set

在redis中，我們可以查看intset.h文件，這是一個存儲整數的集合，其結構如下：

typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;

其中各欄位含義如下：

  • encoding：數據編碼格式，表示每個數據元素用幾個位元組存儲（可取的值有2、4，和8）
  • length：元素個數
  • contents：柔性數組，這部分內存單獨分配，不包含在intset中

具體的操作我們就不詳細展開了，了解集合這種數據結構的應該都很清楚，我們這裡說一下，intset有一個數據升級的概念，比方說我們有一個16位整數的set，這時候插入了一個32位整數，所以就導致整個集合都升級為32位整數，但是反過來卻不行，這也就是柔性數組的由來

如果集合過大，會採用dict的方式來進行存儲

原文轉載於：juejin.im/post/5cee9fdf


推薦閱讀：
相关文章