1. 介紹

眾所周知，redis是一個開源、短小、高效的key-value儲存系統，相對於memcached，redis能夠支援更加豐富的資料結構，包括：

字串（string）雜湊表（map）列表（list）集合（set）有序集（zset）

主流的key-value儲存系統，都是在系統內部維護一個hash表，因為對hash表的操作時間複雜度為O(1)。如果資料增加以後，導致衝突嚴重，時間複雜度增加，則可以對hash表進行rehash，以此來保證操作的常量時間複雜度。

那麼，對於這樣一個基於hash表的key-value儲存系統，是如何提供這麼豐富的資料結構的呢？這些資料結構在記憶體中如何儲存呢？這篇文章將用大量的圖片演示redis的記憶體佈局和資料儲存。

2. redisServer

在redis系統內部，有一個redisServer結構體的全域性變數server，server儲存了redis服務端所有的資訊，包括當前程序的PID、伺服器的埠號、資料庫個數、統計資訊等等。當然，它也包含了資料庫資訊，包括資料庫的個數、以及一個redisDb陣列。

struct redisServer {    ……    redisDb *db;    int dbnum;                      /* Total number of configured DBs */    ……}

顯然，dbnum就是redisDb陣列的長度，每一個數據庫，都對應於一個redisDb，在redis的客戶端中，可以透過select N來選擇使用哪一個資料庫，各個資料庫之間互相獨立。例如：可以在不同的資料庫中同時存在名為”redis”的key。

從上面的分析中可以看到，server是一個全域性變數，它包含了若干個redisDb，每一個redisDb是一個keyspace，各個keyspace互相獨立，互不干擾。

下面來看一下redisDb的定義：

/* Redis database representation. There are multiple databases identified * by integers from 0 (the default database) up to the max configured * database. The database number is the 'id' field in the structure. */typedef struct redisDb {    dict *dict;                 /* The keyspace for this DB */    dict *expires;              /* Timeout of keys with a timeout set */    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */    dict *ready_keys;           /* Blocked keys that received a PUSH */    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */    struct evictionPoolEntry *eviction_pool;    /* Eviction pool of keys */    int id;                     /* Database ID */    long long avg_ttl;          /* Average TTL, just for stats */} redisDb;

redis的每一個數據庫是一個獨立的keyspace，因此，我們理所當然的認為，redis的資料庫是一個hash表。但是，從redisDb的定義來看，它並不是一個hash表，而是一個包含了很多hash表的結構。之所以這樣做，是因為redis還需要提供除了set、get以外更加豐富的功能(例如：鍵的超時機制)。我們今天只關注最重要的資料結構：

typedef struct redisDb {    dict *dict;                 /* The keyspace for this DB */    ……} redisDb;

redisDb與redisServer的關係如下所示：

下面再看dict的定義：

typedef struct dict {    ……    dictht ht[2];    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    ……} dict;

dict包含了兩個hash表，這樣做的目的是為了支援漸進式的rehash，即：在大多數情況下，只使用第一個hash表，如果第一個hash表的資料太多，則需要執行rehash。

dict與redisDb、redisServer的關係如下：

下面看一下dictht的定義，至此，我們總算見到了redis的hash表，與絕大多數的hash表沒有什麼兩樣：

dictht與dict、redisDb、redisServer之間的關係如下：

redis對hash表的節點也進行了簡單的封裝，hash表的每一個節點都是一個dictEntry，redis的hash表看起來是這樣：

總結： redis記憶體有一個全域性變數redisServer server，該變數包含若干個資料庫，每個資料庫都用一個redisDb表示，redisDb包含若干個字典，其中，儲存資料的是dict* dict，dict內部包含兩個hash表，一般情況下面，我們只會使用ht[0]，在rehash時，我們會同時使用兩個hash表，hash表的每一項，都是一個dictEntry結構體的變數。

從宏觀角度來看，redis的資料儲存應該是這樣的：

3. 儲存不同的資料型別

在上一節中，詳細介紹了redis的hash表以及核心資料結構之間的關係，至此，以及對redis儲存資料有了一個初步的印象，但是，到目前為止還沒有回答文章最開始的問題：redis如何儲存不同的資料結構？

要理解redis如何儲存不同的資料結構，首先來看一下redisObject的定義：

typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */    int refcount;    void *ptr;} robj;

其中，type是邏輯資料型別，即redis提供給使用者的字串、列表、hash表等。type的取值如下：

/* Object types */#define REDIS_STRING 0#define REDIS_LIST 1#define REDIS_SET 2#define REDIS_ZSET 3#define REDIS_HASH 4

type雖然很關鍵，但是，在我們這篇文章中，更多的需要關注encoding欄位，該欄位的含義是邏輯資料型別的具體實現。encoding的取值如下：

#define REDIS_ENCODING_RAW 0     /* Raw representation */#define REDIS_ENCODING_INT 1     /* Encoded as integer */#define REDIS_ENCODING_HT 2      /* Encoded as hash table */#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */#define REDIS_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */

例如，對於list這種資料型別，在redis內部，可以使用ziplist實現（更加省記憶體），也可以使用linkedlist實現。

在滿足以下兩個條件時，使用ziplist實現，否則，使用linkedlist實現。

列表物件儲存的所有字串元素的長度都小於64位元組列表物件儲存的元素數量小於512

再次強調：對於同一種資料型別，redis內部提供了多種實現，不同的實現適用於不同的場景，且使用者只能透過redis.conf檔案進行有限的控制，具體使用哪一種實現，完全是redis內部決定。可以透過object encoding key檢視當前key的內部編碼，即內部實現。

這篇文章介紹redis的記憶體佈局，自然更應該關係的是內部的具體實現，而不是邏輯資料型別。不管是邏輯型別(type)還是具體實現(encoding)，都儲存在redisObject中，redisObject相當於是所有資料結構的父類，redis的hash表的每一個項都是dictEntry，而每一個dictEntry，都指向一個redisObject。

redis在資料的存取時，首先透過key找到對應的dictEntry，接著透過dictEntry獲取redisObject物件，然後透過redisObject的encoding的取值，對redisObject的ptr指標進行強制型別轉換。

例如： 對於一個簡短的list，redis很有可能使用的是quicklist儲存，因此，在讀取list的資料時，redis首先透過key找到dictEntry，然後透過dictEntry找到redisObject， 透過redisObject的encoding對ptr指標進行強制型別轉換，在本例中，將ptr強制轉換為quicklist，轉換為quicklist以後，就能夠獲取head和tail指標，可以使用head和tail訪問資料。