歡迎光臨
每天分享高質量文章

Redis概念以及底層資料結構

(點選上方快速關註並設定為星標,一起學Python)

作者:Worktile高階工程師 龔林傑     連結:

https://worktile.com/blog/tech/tech-redis

Redis 簡介

REmote DIctionary Server(Redis) 是一個由SalvatoreSanfilippo寫的key-value儲存系統。

Redis是一個開源的使用ANSI C語言編寫、遵守BSD協議、支援網路、可基於記憶體亦可持久化的日誌型、Key-Value資料庫,並提供多種語言的API。

它通常被稱為資料結構伺服器,因為值(value)可以是字串(String), 雜湊(Map), 串列(list), 集合(sets) 和有序集合(sorted sets)等型別。

Redis特點

Redis 是完全開源免費的,遵守BSD協議,是一個高效能的key-value資料庫。

Redis 與其他 key – value 快取產品有以下三個特點:

  • Redis支援資料的持久化,可以將記憶體中的資料保持在磁碟中,重啟的時候可以再次載入進行使用。

  • Redis不僅僅支援簡單的key-value型別的資料,同時還提供list,set,zset,hash等資料結構的儲存。

  • Redis支援資料的備份,即master-slave樣式的資料備份。

Redis 優勢

效能極高 – Redis能讀的速度是110000次/s,寫的速度是81000次/s 。

豐富的資料型別 – Redis支援 Strings, Lists, Hashes, Sets 及 Ordered Sets 資料型別操作。

原子 – Redis的所有操作都是原子性的,同時Redis還支援對幾個操作全並後的原子性執行。

豐富的特性 – Redis 還支援 publish/subscribe, 佇列,key 過期等等特性。

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中的一個物件的結構體表示如下:

typedef struct redisObject {

    // 型別
    unsigned type:4;

    // 編碼方式
    unsigned encoding: 4;

    // 取用計數
    int refcount;

    // 指向物件的值
    void *ptr;

} robj;

type表示了該物件的物件型別,即上面五個中的一個。但為了提高儲存效率與程式執行效率,每種物件的底層資料結構實現都可能不止一種。encoding就表示了物件底層所使用的編碼。

  • Redis物件底層資料結構

  • 字串物件

符串物件的編碼可以是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 44
robj *createStringObject(char *ptr, size_t len) {
    if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else  
        return createRawStringObject(ptr,len);
}

embstr的好處有如下幾點:

  1. embstr的建立只需分配一次記憶體,而raw為兩次(一次為sds分配物件,另一次為objet分配物件,embstr省去了第一次)。
  2. 相對地,釋放記憶體的次數也由兩次變為一次。
  3. embstr的objet和sds放在一起,更好地利用快取帶來的優勢。

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

  • 串列物件

串列物件的編碼可以是ziplist或者linkedlist

1、ziplist是一種壓縮連結串列,它的好處是更能節省記憶體空間,因為它所儲存的內容都是在連續的記憶體區域當中的。當串列物件元素不大,每個元素也不大的時候,就採用ziplist儲存但當資料量過大時就ziplist就不是那麼好用了。因為為了保證他儲存內容在記憶體中的連續性,插入的複雜度是O(N),即每次插入都會重新進行realloc。如下圖所示,物件結構中ptr所指向的就是一個ziplist整個ziplist只需要malloc一次,它們在記憶體中是一塊連續的區域。

2、linkedlist是一種雙向連結串列。

它的結構比較簡單,節點中存放pre和next兩個指標,還有節點相關的資訊。

當每增加一個node的時候,就需要重新malloc一塊記憶體。

  • 雜湊物件

雜湊物件的底層實現可以是ziplist或者hashtable。

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

hashtable的是由dict這個結構來實現的, dict是一個字典,其中的指標dicht ht[2] 指向了兩個雜湊表

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;
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 *essay-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陣列)

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

總結

以上簡單介紹了Redis的簡介,特性以及五種物件型別和五種物件型別的底層實現。事實上,Redis的高效性和靈活性正是得益於同一個物件型別採用不同的底層結構,並且在必要的時候對二者進行轉換,還有就是各種底層結構對記憶體的合理利用。

    已同步到看一看
    贊(0)

    分享創造快樂