1. 簡介

Redis是一個(gè)基于內(nèi)存的非關(guān)系型的鍵值對(duì)數(shù)據(jù)庫，因它基于內(nèi)存的特性所以它的速度比傳統(tǒng)的關(guān)系型數(shù)據(jù)庫快，除此之外它還具有許多特性：

• 支持事務(wù)
• 支持AOF和RDB持久化
• 支持多種數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)
• 流水線、發(fā)布\訂閱功能
• 主從復(fù)制
• 內(nèi)存回收

本文講的是Redis豐富的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)原理

實(shí)現(xiàn)

五種基本類型

Redis是一個(gè)鍵值對(duì)數(shù)據(jù)庫，而鍵都是字符串（Redis內(nèi)部實(shí)現(xiàn)的簡單動(dòng)態(tài)字符串）類型，值有5種基本類型，分別是：

• STRING（字符串）
• LIST（列表）
• SET（集合）
• ZSET（有序集合）
• HASH（哈希）

不同類型的不同實(shí)現(xiàn)

redisObject

在Redis中，這5種基本類型的對(duì)象都是封裝在robj這個(gè)結(jié)構(gòu)體中，源碼如下：

typedef struct redisObject {
    // 類型
    unsigned type:4;

    // 編碼
    unsigned encoding:4;

    // 對(duì)象最后一次被訪問的時(shí)間
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用計(jì)數(shù)，用于內(nèi)存回收與對(duì)象共享
    int refcount;

    // 指向?qū)嶋H值的指針
    void *ptr;
} robj;

// 通過調(diào)用createObject方法可以創(chuàng)建其對(duì)象
robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->encoding = OBJ_ENCODING_RAW;
    o->ptr = ptr;
    o->refcount = 1;

    /* Set the LRU to the current lruclock (minutes resolution), or
     * alternatively the LFU counter. */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}

下面解釋下各個(gè)屬性：

type

該屬性表示對(duì)象的類型，占4個(gè)bit，源碼如下：

#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

在Redis中通過使用TYPE命令可以獲得其類型

127.0.0.1:6379> TYPE key

string

encoding

該屬性表示該類型的對(duì)象具體的實(shí)現(xiàn)，這樣做的目的是為了使在不同場(chǎng)景下靈活使用不同的數(shù)據(jù)結(jié)構(gòu)

#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 */

在Redis中通過使用OBJECT ENCODING命令可以獲得其編碼

127.0.0.1:6379> OBJECT ENCODING key

“embstr”

lru

該屬性記錄該對(duì)象最近一次被訪問的時(shí)間，如果服務(wù)器打開了maxmemory選項(xiàng)，并且服務(wù)器用于內(nèi)存回收的算法為volatile-lru或allkeys-lru，當(dāng)占用內(nèi)存超過maxmemory設(shè)置的上限時(shí)，最早被訪問的會(huì)先被釋放。

在Redis中通過使用OBJECT IDLETIME命令可以獲得其lru時(shí)間

127.0.0.1:6379> OBJECT IDLETIME key

(integer) 10155

refcount

該屬性有兩個(gè)作用：

• 用于引用計(jì)數(shù)實(shí)現(xiàn)內(nèi)存回收，該屬性值表示對(duì)象被多少個(gè)程序引用，當(dāng)對(duì)象被創(chuàng)建時(shí)，該屬性值為1，當(dāng)該值為0時(shí)對(duì)象占用的內(nèi)存會(huì)被回收。
• 用于對(duì)象共享，比如Redis在初始化服務(wù)器時(shí)就會(huì)創(chuàng)建0到9999的字符串對(duì)象用于對(duì)象共享，每當(dāng)使用set命令創(chuàng)建一個(gè)新字符串對(duì)象，如果要?jiǎng)?chuàng)建的字符串已經(jīng)存在則將指向值的指針指向該字符串對(duì)象，并將該對(duì)象的refcount加1。

127.0.0.1:6379> OBJECT REFCOUNT key

(integer) 2

REDIS_STRING（字符串）

Redis的字符串一共有三種實(shí)現(xiàn)方式，分別適用于不同場(chǎng)景，其中有一種實(shí)現(xiàn)是簡單動(dòng)態(tài)字符串，簡稱SDS，下面的結(jié)構(gòu)體sdshdr就表示一個(gè)SDS，它具有以下幾個(gè)優(yōu)點(diǎn)：

• 常數(shù)時(shí)間獲取字符串長度
• 自動(dòng)擴(kuò)容
• 預(yù)分配空間以減少內(nèi)存重新分配次數(shù)
• 二進(jìn)制安全
• 重用部分C語言函數(shù)庫

struct sdshdr {
 // buf 中已占用空間的長度
 int len;

 // buf 中剩余可用空間的長度
 int free;

 // 數(shù)據(jù)空間
 char buf[];
};

INT

當(dāng)字符串保存的是一個(gè)可以用long類型來表示的整數(shù)時(shí)，那么robj對(duì)象里的屬性ptr的類型void *就會(huì)被替換為long，而encoding的值會(huì)設(shè)置為int表示該字符串的實(shí)現(xiàn)方式是整型。

127.0.0.1:6379> SET key 88

OK

127.0.0.1:6379> OBJECT ENCODING key

“int”

EMBSTR

在目前最新版本中，當(dāng)字符串保存的是一個(gè)小于等于44個(gè)字節(jié)的字符串時(shí)，那么robj對(duì)象里的屬性ptr就會(huì)指向一個(gè)SDS對(duì)象，而encoding的值會(huì)設(shè)置為embstr表示該字符串的實(shí)現(xiàn)方式是SDS（簡單動(dòng)態(tài)字符串）。embstr是一種用來保存短字符串的編碼方式，embstr編碼通過調(diào)用一次內(nèi)存分配函數(shù)來創(chuàng)建一塊連續(xù)的內(nèi)存空間，即redisObject對(duì)象和它的ptr指針指向的SDS對(duì)象是連續(xù)的。不過embstr編碼的字符串對(duì)象是只讀性的，一旦對(duì)其指向APPEND命令追加字符串會(huì)導(dǎo)致其變?yōu)?code>raw編碼實(shí)現(xiàn)。

embstr編碼創(chuàng)建的內(nèi)存塊結(jié)構(gòu)

127.0.0.1:6379> SET key value

OK

127.0.0.1:6379> OBJECT ENCODING key

“embstr”

RAW

在目前最新版本中，當(dāng)字符串對(duì)象保存的是一個(gè)超過44個(gè)字節(jié)的字符串時(shí)，那么robj對(duì)象里的屬性ptr就會(huì)指向一個(gè)SDS對(duì)象，而encoding的值會(huì)設(shè)置為raw表示該字符串的實(shí)現(xiàn)方式是SDS（簡單動(dòng)態(tài)字符串）。raw編碼的字符串對(duì)象是可讀可寫的，對(duì)其指向APPEND命令追加字符串會(huì)不會(huì)導(dǎo)致其實(shí)現(xiàn)改變，如果追加的字符串的長度超過其free屬性值，會(huì)在追加前重新進(jìn)行內(nèi)存空間分配。

127.0.0.1:6379> SET key value

OK

127.0.0.1:6379> OBJECT ENCODING key

“raw”