南順網絡

redis的(de)五種對象類型及其底層實現

Redis對象類型簡介

Redis是一(yī)種key/value型數據庫，其中，每個key和(hé)value都是使用對象表示的(de)。比如(rú)，我們執行以下代碼：

redis>SET message "hello redis"

其中的(de)key是message，是一(yī)個包含了字符串"message"的(de)對象。而value是一(yī)個包含了"hello redis"的(de)對象。

Redis共有五種對象的(de)類型，分别是：

類型常量 對象的(de)名稱

REDIS_STRING 字符串對象

REDIS_LIST 列表對象

REDIS_HASH 哈希對象

REDIS_SET 集合對象

REDIS_ZSET 有序集合對象

Redis中的(de)一(yī)個對象的(de)結構體表示如(rú)下：

/*

 * Redis 對象

 */

typedef struct redisObject {

    // 類型

    unsigned type:4;        

    // 不使用(對齊位)

    unsigned notused:2;

    // 編碼方式

    unsigned encoding:4;

    // LRU 時間（相對于 server.lruclock）

    unsigned lru:22;

    // 引用計數

    int refcount;

    // 指向對象的(de)值

    void *ptr;

} robj;

type表示了該對象的(de)對象類型，即上面五個中的(de)一(yī)個。但為(wèi)了提高(gāo)存儲效率與程序執行效率，每種對象的(de)底層數據結構實現都可(kě)能不止一(yī)種。encoding就表示了對象底層所使用的(de)編碼。下面先介紹每種底層數據結構的(de)實現，再介紹每種對象類型都用了什麽底層結構并分析他們之間的(de)關系。

Redis對象底層數據結構

底層數據結構共有八種，如(rú)下表所示：

編碼常量 編碼所對應的(de)底層數據結構

REDIS_ENCODING_INT long 類型的(de)整數

REDIS_ENCODING_EMBSTR embstr 編碼的(de)簡單動态字符串

REDIS_ENCODING_RAW 簡單動态字符串

REDIS_ENCODING_HT 字典

REDIS_ENCODING_LINKEDLIST 雙端鏈表

REDIS_ENCODING_ZIPLIST 壓縮列表

REDIS_ENCODING_INTSET 整數集合

REDIS_ENCODING_SKIPLIST 跳躍表和(hé)字典

字符串對象

字符串對象的(de)編碼可(kě)以是int、raw或者embstr。

如(rú)果一(yī)個字符串的(de)內(nèi)容可(kě)以轉換為(wèi)long，那麽該字符串就會被轉換成為(wèi)long類型，對象的(de)ptr就會指向該long，并且對象類型也用int類型表示。

普通的(de)字符串有兩種，embstr和(hé)raw。embstr應該是Redis 3.0新增的(de)數據結構,在2.8中是沒有的(de)。如(rú)果字符串對象的(de)長(cháng)度小于39字節，就用embstr對象。否則用傳統的(de)raw對象。可(kě)以從下面這段代碼看出：

#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39

robj *createStringObject(char *ptr, size_t len) {

    if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)

        return createEmbeddedStringObject(ptr,len);

    else

        return createRawStringObject(ptr,len);

}

embstr的(de)好處有如(rú)下幾點：

embstr的(de)創建隻需分配一(yī)次內(nèi)存，而raw為(wèi)兩次（一(yī)次為(wèi)sds分配對象，另一(yī)次為(wèi)objet分配對象，embstr省去(qù)了第一(yī)次）。

相對地(dì)，釋放內(nèi)存的(de)次數也由兩次變為(wèi)一(yī)次。

embstr的(de)objet和(hé)sds放在一(yī)起，更好地(dì)利用緩存帶來的(de)優勢。

需要注意的(de)是，redis并未提供任何修改embstr的(de)方式，即embstr是隻讀的(de)形式。對embstr的(de)修改實際上是先轉換為(wèi)raw再進行修改。

raw和(hé)embstr的(de)區别可(kě)以用下面兩幅圖所示：

列表對象

列表對象的(de)編碼可(kě)以是ziplist或者linkedlist。

ziplist是一(yī)種壓縮鏈表，它的(de)好處是更能節省內(nèi)存空間，因為(wèi)它所存儲的(de)內(nèi)容都是在連續的(de)內(nèi)存區域當中的(de)。當列表對象元素不大，每個元素也不大的(de)時候，就采用ziplist存儲。但當數據量過大時就ziplist就不是那麽好用了。因為(wèi)為(wèi)了保證他存儲內(nèi)容在內(nèi)存中的(de)連續性，插入的(de)複雜度是O(N)，即每次插入都會重新進行realloc。如(rú)下圖所示，對象結構中ptr所指向的(de)就是一(yī)個ziplist。整個ziplist隻需要malloc一(yī)次，它們在內(nèi)存中是一(yī)塊連續的(de)區域。

linkedlist是一(yī)種雙向鏈表。它的(de)結構比較簡單，節點中存放pre和(hé)next兩個指針，還有節點相關的(de)信息。當每增加一(yī)個node的(de)時候，就需要重新malloc一(yī)塊內(nèi)存。

哈希對象

哈希對象的(de)底層實現可(kě)以是ziplist或者hashtable。

ziplist中的(de)哈希對象是按照key1,value1,key2,value2這樣的(de)順序存放來存儲的(de)。當對象數目不多且內(nèi)容不大時，這種方式效率是很高(gāo)的(de)。

hashtable的(de)是由dict這個結構來實現的(de)

typedef struct dict {

    dictType *type;

    void *privdata;

    dictht ht[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    int iterators; /* number of iterators currently running */

} dict;

dict是一(yī)個字典，其中的(de)指針dicht ht[2] 指向了兩個哈希表

typedef struct dictht {

    dictEntry **table;

    unsigned long size;

    unsigned long sizemask;

    unsigned long used;

} dictht;

dicht[0] 是用于真正存放數據，dicht[1]一(yī)般在哈希表元素過多進行rehash的(de)時候用于中轉數據。

dictht中的(de)table用語真正存放元素了，每個key/value對用一(yī)個dictEntry表示，放在dictEntry數組中。

集合對象

集合對象的(de)編碼可(kě)以是intset或者hashtable。

intset是一(yī)個整數集合，裏面存的(de)為(wèi)某種同一(yī)類型的(de)整數，支持如(rú)下三種長(cháng)度的(de)整數：

#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

intset是一(yī)個有序集合，查找元素的(de)複雜度為(wèi)O(logN)，但插入時不一(yī)定為(wèi)O(logN)，因為(wèi)有可(kě)能涉及到升級操作。比如(rú)當集合裏全是int16_t型的(de)整數，這時要插入一(yī)個int32_t，那麽為(wèi)了維持集合中數據類型的(de)一(yī)緻，那麽所有的(de)數據都會被轉換成int32_t類型，涉及到內(nèi)存的(de)重新分配，這時插入的(de)複雜度就為(wèi)O(N)了。是intset不支持降級操作。

有序集合對象

有序集合的(de)編碼可(kě)能兩種，一(yī)種是ziplist，另一(yī)種是skiplist與dict的(de)結合。

ziplist作為(wèi)集合和(hé)作為(wèi)哈希對象是一(yī)樣的(de)，member和(hé)score順序存放。按照score從小到大順序排列。它的(de)結構不再複述。

skiplist是一(yī)種跳躍表，它實現了有序集合中的(de)快速查找，在大多數情況下它的(de)速度都可(kě)以和(hé)平衡樹差不多。但它的(de)實現比較簡單，可(kě)以作為(wèi)平衡樹的(de)替代品。它的(de)結構比較特殊。下面分别是跳躍表skiplist和(hé)它內(nèi)部的(de)節點skiplistNode的(de)結構體：

/*

 * 跳躍表

 */

typedef struct zskiplist {

    // 頭節點，尾節點

    struct zskiplistNode *header, *tail;

    // 節點數量

    unsigned long length;

    // 目前表內(nèi)節點的(de)最大層數

    int level;

} zskiplist;

/* ZSETs use a specialized version of Skiplists */

/*

 * 跳躍表節點

 */

typedef struct zskiplistNode {

    // member 對象

    robj *obj;

    // 分值

    double score;

    // 後退指針

    struct zskiplistNode *backward;

    // 層

    struct zskiplistLevel {

        // 前進指針

        struct zskiplistNode *forward;

        // 這個層跨越的(de)節點數量

        unsigned int span;

    } level[];

} zskiplistNode;

head和(hé)tail分别指向頭節點和(hé)尾節點，然後每個skiplistNode裏面的(de)結構又是分層的(de)(即level數組)

用圖表示，大概是下面這個樣子(zǐ)：

每一(yī)列都代表一(yī)個節點，保存了member和(hé)score，按score從小到大排序。每個節點有不同的(de)層數，這個層數是在生成節點的(de)時候随機生成的(de)數值。每一(yī)層都是一(yī)個指向後面某個節點的(de)指針。這種結構使得跳躍表可(kě)以跨越很多節點來快速訪問。

前面說到了，有序集合ZSET是有跳躍表和(hé)hashtable共同形成的(de)。

typedef struct zset {

    // 字典

    dict *dict;

    // 跳躍表

    zskiplist *zsl;

} zset;

為(wèi)什麽要用這種結構呢(ne)。試想如(rú)果單一(yī)用hashtable，那可(kě)以快速查找、添加和(hé)删除元素，但沒法保持集合的(de)有序性。如(rú)果單一(yī)用skiplist，有序性可(kě)以得到保障，但查找的(de)速度太慢O（log）。

編輯:--ns868