您當前位置: 南順網絡>> 官方資訊>> 建站知識

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

Redis對象類型簡介

Redis是一種key/value型數據庫,其中,每個key和value都是使用對象表示的。比如,我們執行以下代碼:



redis>SET message "hello redis"


其中的key是message,是一個包含了字符串"message"的對象。而value是一個包含了"hello redis"的對象。

Redis共有五種對象的類型,分別是:


類型常量 對象的名稱

REDIS_STRING 字符串對象

REDIS_LIST 列表對象

REDIS_HASH 哈希對象

REDIS_SET 集合對象

REDIS_ZSET 有序集合對象


Redis中的一個對象的結構體表示如下:


/*

 * Redis 對象

 */

typedef struct redisObject {

 

    // 類型

    unsigned type:4;        

 

    // 不使用(對齊位)

    unsigned notused:2;

 

    // 編碼方式

    unsigned encoding:4;

 

    // LRU 時間(相對于 server.lruclock)

    unsigned lru:22;

 

    // 引用計數

    int refcount;

 

    // 指向對象的值

    void *ptr;

 

} robj;

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


Redis對象底層數據結構

底層數據結構共有八種,如下表所示:


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

REDIS_ENCODING_INT long 類型的整數

REDIS_ENCODING_EMBSTR embstr 編碼的簡單動態字符串

REDIS_ENCODING_RAW 簡單動態字符串

REDIS_ENCODING_HT 字典

REDIS_ENCODING_LINKEDLIST 雙端鏈表

REDIS_ENCODING_ZIPLIST 壓縮列表

REDIS_ENCODING_INTSET 整數集合

REDIS_ENCODING_SKIPLIST 跳躍表和字典

字符串對象

字符串對象的編碼可以是int、raw或者embstr。


如果一個字符串的內容可以轉換為long,那么該字符串就會被轉換成為long類型,對象的ptr就會指向該long,并且對象類型也用int類型表示。


普通的字符串有兩種,embstr和raw。embstr應該是Redis 3.0新增的數據結構,在2.8中是沒有的。如果字符串對象的長度小于39字節,就用embstr對象。否則用傳統的raw對象??梢詮南旅孢@段代碼看出:


#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的好處有如下幾點:

embstr的創建只需分配一次內存,而raw為兩次(一次為sds分配對象,另一次為objet分配對象,embstr省去了第一次)。

相對地,釋放內存的次數也由兩次變為一次。

embstr的objet和sds放在一起,更好地利用緩存帶來的優勢。

需要注意的是,redis并未提供任何修改embstr的方式,即embstr是只讀的形式。對embstr的修改實際上是先轉換為raw再進行修改。


raw和embstr的區別可以用下面兩幅圖所示:





列表對象

列表對象的編碼可以是ziplist或者linkedlist。


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



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



哈希對象



哈希對象的底層實現可以是ziplist或者hashtable。


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


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


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是一個字典,其中的指針dicht ht[2] 指向了兩個哈希表

typedef struct dictht {

    dictEntry **table;

    unsigned long size;

    unsigned long sizemask;

    unsigned long used;

} dictht;

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

dictht中的table用語真正存放元素了,每個key/value對用一個dictEntry表示,放在dictEntry數組中。





集合對象

集合對象的編碼可以是intset或者hashtable。


intset是一個整數集合,里面存的為某種同一類型的整數,支持如下三種長度的整數:


#define INTSET_ENC_INT16 (sizeof(int16_t))

#define INTSET_ENC_INT32 (sizeof(int32_t))

#define INTSET_ENC_INT64 (sizeof(int64_t))

intset是一個有序集合,查找元素的復雜度為O(logN),但插入時不一定為O(logN),因為有可能涉及到升級操作。比如當集合里全是int16_t型的整數,這時要插入一個int32_t,那么為了維持集合中數據類型的一致,那么所有的數據都會被轉換成int32_t類型,涉及到內存的重新分配,這時插入的復雜度就為O(N)了。是intset不支持降級操作。

有序集合對象

有序集合的編碼可能兩種,一種是ziplist,另一種是skiplist與dict的結合。


ziplist作為集合和作為哈希對象是一樣的,member和score順序存放。按照score從小到大順序排列。它的結構不再復述。


skiplist是一種跳躍表,它實現了有序集合中的快速查找,在大多數情況下它的速度都可以和平衡樹差不多。但它的實現比較簡單,可以作為平衡樹的替代品。它的結構比較特殊。下面分別是跳躍表skiplist和它內部的節點skiplistNode的結構體:



/*

 * 跳躍表

 */

typedef struct zskiplist {

    // 頭節點,尾節點

    struct zskiplistNode *header, *tail;

    // 節點數量

    unsigned long length;

    // 目前表內節點的最大層數

    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;

        // 這個層跨越的節點數量

        unsigned int span;

    } level[];

} zskiplistNode;

head和tail分別指向頭節點和尾節點,然后每個skiplistNode里面的結構又是分層的(即level數組)

用圖表示,大概是下面這個樣子:




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


前面說到了,有序集合ZSET是有跳躍表和hashtable共同形成的。


typedef struct zset {

    // 字典

    dict *dict;

    // 跳躍表

    zskiplist *zsl;

} zset;

為什么要用這種結構呢。試想如果單一用hashtable,那可以快速查找、添加和刪除元素,但沒法保持集合的有序性。如果單一用skiplist,有序性可以得到保障,但查找的速度太慢O(log)。

編輯:--ns868