本期內容則會著重講講Redis內存數據結構與編碼，弄清Redis內部到底是如何支持這5種數據類型的。

[[255026]]

一、Redis內存數據結構與編碼

想要弄清楚Redis內部如何支持5種數據類型，也就是要弄清Redis到底是使用什么樣的數據結構來存儲、查找我們設置在內存中的數據。

雖然我們使用5種數據類型來緩存數據，但是Redis會根據我們存儲數據的不同而選用不同的數據結構和編碼。

 

這些數據類型在內存中的數據結構和編碼有很多種，隨著我們存儲的數據類型的不同、數據量的大小不同都會引起內存數據結構的動態調整。

本文只是做數據結構和編碼的一般性介紹，不做過多細節討論，一方面是關于Redis源碼分析的資料網上有很多，還有一個原因就是Redis每一個版本的實現有很大差異，一旦展開細節討論，每一個點每一個數據結構都會很復雜，所以我們這里就不展開討論這些，只是起到拋磚引玉作用。

1、OBJECT encoding key、DEBUG OBJECT key

我們知道使用type命令可以查看某個key是否是5種數據類型之一，但是當我們想查看某個key底層是使用哪種數據結構和編碼來存儲的時候，可以使用OBJECT encoding命令。

 

同樣一個key，由于我們設置的值不同，Redis選用了不同的內存數據結構和編碼。雖然Redis提供String數據類型，但是Redis會自動識別我們cache的數據類型是int還是String。

如果我們設置的是字符串，且這個字符串長度不大于39字節，那么將使用embstr來編碼;如果大于39字節將使用raw來編碼。Redis4.0將這個閥值擴大了45個字節。

除了使用OBJECT encoding命令外，我們還可以使用DEBUG OBJECT命令來查看更多詳細信息。

 

DEBUG OBJECT能看到這個對象的refcount引用計數、serializedlength長度、lru_seconds_idle時間，這些信息決定了這個key緩存清除策略。

2、簡單動態字符串(simple dynamic String)

簡單動態字符串簡稱SDS，在Redis中所有涉及到字符串的地方都是使用SDS實現，當然這里不包括字面量。SDS與傳統C字符串的區別就是SDS是結構化的，它可以高效的處理分配、回收、長度計算等問題。

struct sdshdr { 
    unsigned int len; 
    unsigned int free; 
    char buf[]; 
}; 

這是Redis3.0版本的sds.h頭文件定義，3.0.0之后變化比較大。len表示字符串長度，free表示空間長度，buf數組表示字符串。

SDS有很多優點，比如，獲取長度的時間復雜度O(1)，不需要遍歷所有charbuf[]組數，直接返回len值。

static inline size_t sdslen(const sds s) { 
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); 
    return sh->len; 
} 

當然還有空間分配檢查、空間預分配、空間惰性釋放等，這些都是SDS結構化字符串帶來的強大的擴展能力。

3、鏈表(linked list)

鏈表數據結構我們是比較熟悉的，最大的特點就是節點的增、刪非常靈活。Redis List數據類型底層就是基于鏈表來實現。這是Redis3.0實現。

typedef struct list { 
    listNode *head; 
    listNode *tail; 
    void *(*dup)(void *ptr); 
    void (*free)(void *ptr); 
    int (*match)(void *ptr, void *key); 
    unsigned long len; 
} list; 
 
typedef struct listNode { 
    struct listNode *prev; 
    struct listNode *next; 
    void *value; 
} listNode; 

在Redis3.2.0版本的時候引入了quicklist鏈表結構，結合了linkedlist和ziplist的優勢。

typedef struct quicklist { 
    quicklistNode *head; 
    quicklistNode *tail; 
    unsigned long count;        /* total count of all entries in all ziplists */ 
    unsigned int len;           /* number of quicklistNodes */ 
    int fill : 16;              /* fill factor for individual nodes */ 
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */ 
} quicklist; 
 
typedef struct quicklistNode { 
    struct quicklistNode *prev; 
    struct quicklistNode *next; 
    unsigned char *zl; 
    unsigned int sz;             /* ziplist size in bytes */ 
    unsigned int count : 16;     /* count of items in ziplist */ 
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */ 
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */ 
    unsigned int recompress : 1; /* was this node previous compressed? */ 
    unsigned int attempted_compress : 1; /* node can't compress; too small */ 
    unsigned int extra : 10; /* more bits to steal for future usage */ 
} quicklistNode; 

quicklist提供了靈活性同時也兼顧了ziplist的壓縮能力，quicklist->encoding指定了兩種壓縮算法。quickList->compress表示我們可以進行quicklist node的深度壓縮能力。Redis提供了兩個有關于壓縮的配置：

• List-max-zipList-size：zipList長度控制;
• List-compress-depth：控制鏈表兩端節點的壓縮個數，越是靠近兩端的節點被訪問的機率越大，所以可以將訪問機率大的節點不壓縮，其他節點進行壓縮。

對比Redis3.2的quicklist與Redis3.0，很明顯quicklist提供了更加豐富的壓縮功能。Redis3.0的版本是每個listnode直接緩存值，而quicklistnode還有強大的有關于壓縮能力。

LPUSH list:products:mall 100 200 300 
(integer) 3 
 
OBJECT encoding list:products:mall 
"quicklist" 

4、字典(dict)

dict字典是基于Hash算法來實現，是Hash數據類型的底層存儲數據結構。我們來看下Redis3.0.0版本的dict.h頭文件定義：

typedef struct dict { 
    dictType *type; 
    void *privdata; 
    dictht ht[2]; 
    long rehashidx; 
    int iterators;  
} dict; 
 
typedef struct dictht { 
    dictEntry **table; 
    unsigned long size; 
    unsigned long sizemask; 
    unsigned long used; 
} dictht; 
 
typedef struct dictEntry { 
    void *key; 
    union { 
        void *val; 
        uint64_t u64; 
        int64_t s64; 
        double d; 
    } v; 
    struct dictEntry *next; 
} dictEntry; 

說到Hash table有兩個東西是我們經常會碰到的，首先就是Hash碰撞問題，Redis dict是采用鏈地址法來解決，dictEntry->next就是指向下個沖突key的節點。

還有一個經常碰到的就是rehash的問題，提到rehash我們還是有點擔心性能的。那么Redis實現是非常巧妙的，采用惰性漸進式rehash算法。

在dict struct里有一個ht[2]組數，還有一個rehashidx索引。Redis進行rehash的大致算法是這樣的：

首先會開辟一個新的dictht空間，放在ht[2]索引上，此時將rehashidx設置為0，表示開始進入rehash階段，這個階段可能會持續很長時間，rehashidx表示dictEntry個數。每次當有對某個ht[1]索引中的key進行訪問時，獲取、刪除、更新，Redis都會將當前dictEntry索引中的所有key rehash到ht[2]字典中。一旦rehashidx=-1表示rehash結束。

5、跳表(skip list)

skip list是Zset的底層數據結構，有著高性能的查找排序能力。

我們都知道一般用來實現帶有排序的查找都是用Tree實現，不管是各種變體的B Tree還是B+Tree，本質都是用來做順序查找。

skip list實現起來簡單，性能也與B Tree相接近。

typedef struct zskiplistNode { 
    robj *obj; 
    double score; 
    struct zskiplistNode *backward; 
    struct zskiplistLevel { 
        struct zskiplistNode *forward; 
        unsigned int span; 
    } level[]; 
} zskiplistNode; 
 
 
typedef struct zskiplist { 
    struct zskiplistNode *header, *tail; 
    unsigned long length; 
    int level; 
} zskiplist; 

zskiplistNode->zskiplistLevel->span這個值記錄了當前節點距離下個節點的跨度。每一個節點會有最大不超過zskiplist->level節點個數，分別用來表示不同跨度與節點的距離。

每個節點會有多個forward向前指針，只有一個backward指針。每個節點會有對象__*obj__和score分值，每個分值都會按照順序排列。

6、整數集合(int set)

int set整數集合是set數據類型的底層實現數據結構，它的特點和使用場景很明顯，只要我們使用的集合都是整數且在一定的范圍之內，都會使用整數集合編碼。

SADD set:userid 100 200 300 
(integer) 3 
 
OBJECT encoding set:userid 
"intset" 

int set使用一塊連續的內存來存儲集合數據，它是數組結構不是鏈表結構。

typedef struct intset { 
    uint32_t encoding; 
    uint32_t length; 
    int8_t contents[]; 
} intset; 

intset->encoding用來確定contents[]是什么類型的整數編碼，以下三種值之一：

#define INTSET_ENC_INT16 (sizeof(int16_t)) 
#define INTSET_ENC_INT32 (sizeof(int32_t)) 
#define INTSET_ENC_INT64 (sizeof(int64_t)) 

Redis會根據我們設置的值類型動態sizeof出一個對應的空間大小。如果我們集合原來是int16，然后往集合里添加了int32整數將觸發升級，一旦升級成功不會觸發降級操作。

7、壓縮表(zip list)

zip list壓縮表是List、Zset、Hash數據類型的底層數據結構之一。它是為了節省內存通過壓縮數據存儲在一塊連續的內存空間中。

typedef struct zlentry { 
    unsigned int prevrawlensize, prevrawlen; 
    unsigned int lensize, len; 
    unsigned int headersize; 
    unsigned char encoding; 
    unsigned char *p; 
} zlentry; 

它最大的優點就是壓縮空間，空間利用率很高。缺點就是一旦出現更新可能就是連鎖更新，因為數據在內容空間中都是連續的，最極端情況下就是可能出現順序連鎖擴張。

壓縮列表會由多個zlentry節點組成，每一個zlentry記錄上一個節點長度和大小，當前節點長度lensize和大小len包括編碼encoding。

這取決于業務場景，Redis提供了一組配置，專門用來針對不同的場景進行閾值控制：

hash-max-ziplist-entries 512 
hash-max-ziplist-value 64 
list-max-ziplist-entries 512 
list-max-ziplist-value 64 
zset-max-ziplist-entries 128 
zset-max-ziplist-value 64 

上述配置分別用來配置ziplist作為Hash、List、Zset數據類型的底層壓縮閾值控制。

8、Redis Object類型與映射

Redis內部每一種數據類型都是對象化的，也就是我們所說的5種數據類型其實內部都會對應到Redis Object對象，然后再由Redis Object來包裝具體的存儲數據結構和編碼。

typedef struct redisObject { 
    unsigned type:4; 
    unsigned encoding:4; 
    unsigned lru:REDIS_LRU_BITS;  
    int refcount; 
    void *ptr; 
} robj; 

這是一個很OO的設計，redisObject->type是5種數據類型之一，redisObject->encoding是這個數據類型所使用的數據結構和編碼。

我們看下Redis提供的5種數據類型與每一種數據類型對應的存儲數據結構和編碼。

/* Object types */ 
#define REDIS_STRING 0 
#define REDIS_LIST 1 
#define REDIS_SET 2 
#define REDIS_ZSET 3 
#define REDIS_HASH 4 
 
#define REDIS_ENCODING_RAW 0      
#define REDIS_ENCODING_INT 1     
#define REDIS_ENCODING_HT 2 
#define REDIS_ENCODING_ZIPMAP 3 
#define REDIS_ENCODING_LINKEDLIST 4 
#define REDIS_ENCODING_ZIPLIST 5  
#define REDIS_ENCODING_INTSET 6   
#define REDIS_ENCODING_SKIPLIST 7   
#define REDIS_ENCODING_EMBSTR 8  

REDIS_ENCODING_ZIPMAP 3這個編碼可以忽略了，在特定的情況下有性能問題，在Redis 2.6版本之后已經廢棄，為了兼容性保留。

圖是Redis 5種數據類型與底層數據結構和編碼的對應關系：

 

但是這種對應關系在每一個版本中都會有可能發生變化，這也是Redis Object的靈活性所在，有著OO的這種多態性。

• redisObject->refcount表示當前對象的引用計數，在Redis內部為了節省內存采用了共享對象的方法，當某個對象被引用的時候這個refcount會加1，釋放的時候會減1。
• redisObject->lru表示當前對象的空轉時長，也就是idle time，這個時間會是Redis lru算法用來釋放對象的時間依據?？梢酝ㄟ^OBJECT idletime命令查看某個key的空轉時長lru時間。

二、Redis內存管理策略

Redis在服務端分別為不同的db index維護一個dict，這個dict稱為key space鍵空間。每一個RedisClient只能屬于一個db index，在Redis服務端會維護每一個鏈接的RedisClient。

typedef struct redisClient { 
    uint64_t id; 
    int fd; 
    redisDb *db; 
} redisClient; 

在服務端每一個Redis客戶端都會有一個指向redisDb的指針。

typedef struct redisDb { 
    dict *dict; 
    dict *expires; 
    dict *blocking_keys; 
    dict *ready_keys; 
    dict *watched_keys; 
    struct evictionPoolEntry *eviction_pool; 
    int id; 
    long long avg_ttl; 
} redisDb; 

key space鍵空間就是這里的redisDb->dict。redisDb->expires是維護所有鍵空間的每一個key的過期時間。

1、鍵過期時間、生存時間

對于一個key我們可以設置它多少秒、毫秒之后過期，也可以設置它在某個具體的時間點過期，后者是一個時間戳。例如：

• EXPIRE命令可以設置某個key多少秒之后過期;
• PEXPIRE命令可以設置某個key多少毫秒之后過期;
• EXPIREAT命令可以設置某個key在多少秒時間戳之后過期;
• PEXPIREAT命令可以設置某個key在多少毫秒時間戳之后過期;
• PERSIST命令可以移除鍵的過期時間。

其實上述命令最終都會被轉換成對PEXPIREAT命令。在redisDb->expires指向的key字典中維護著一個到期的毫秒時間戳。

TTL、PTTL可以通過這兩個命令查看某個key的過期秒、毫秒數。

Redis內部有一個事件循環，這個事件循環會檢查鍵的過期時間是否小于當前時間，如果小于則會刪除這個鍵。

2、過期鍵刪除策略

在使用Redis的時候我們最關心的就是鍵是如何被刪除的，如何高效準時地刪除某個鍵。其實Redis提供了兩個方案來完成這件事情：惰性刪除、定期刪除雙重刪除策略。

惰性刪除：當我們訪問某個key的時候，Redis會檢查它是否過期。

robj *lookupKeyRead(redisDb *db, robj *key) { 
    robj *val; 
 
    expireIfNeeded(db,key); 
    val = lookupKey(db,key); 
    if (val == NULL) 
        server.stat_keyspace_misses++; 
    else 
        server.stat_keyspace_hits++; 
    return val; 
} 
 
int expireIfNeeded(redisDb *db, robj *key) { 
    mstime_t when = getExpire(db,key); 
    mstime_t now; 
 
    if (when < 0) return 0; /* No expire for this key */ 
 
    if (server.loading) return 0; 
 
    now = server.lua_caller ? server.lua_time_start : mstime(); 
    if (server.masterhost != NULL) return now > when; 
 
    /* Return when this key has not expired */ 
    if (now <= when) return 0; 
 
    /* Delete the key */ 
    server.stat_expiredkeys++; 
    propagateExpire(db,key); 
    notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,"expired",key,db->id); 
    return dbDelete(db,key); 
} 

定期刪除：Redis通過事件循環，周期性地執行key的過期刪除動作。

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) { 
    /* Handle background operations on Redis databases. */ 
    databasesCron(); 
} 
 
void databasesCron(void) { 
    /* Expire keys by random sampling. Not required for slaves 
     * as master will synthesize DELs for us. */ 
    if (server.active_expire_enabled && server.masterhost == NULL) 
        activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW); 
} 

要注意的是：

• 惰性刪除是每次只要有讀取、寫入都會觸發惰性刪除代碼;
• 定期刪除是由Redis EventLoop來觸發的。Redis內部很多維護性工作都是基于EventLoop。

3、AOF、RDB處理過期鍵策略

既然鍵會隨時存在過期問題，那么涉及到持久化Redis是如何幫我們處理的?

當Redis使用RDB方式持久化時，每次持久化的時候就會檢查這些即將被持久化的key是否已經過期，如果過期將直接忽略，持久化那些沒有過期的鍵。

當Redis作為master主服務器啟動的時候，載入rdb持久化鍵時也會檢查這些鍵是否過期，將忽略過期的鍵，只載入沒過期的鍵。

當Redis使用AOF方式持久化時，每次遇到過期的key Redis會追加一條DEL命令到AOF文件，也就是說只要我們順序載入執行AOF命令文件就會刪除過期的鍵。

如果Redis作為從服務器啟動的話，它一旦與master主服務器建立鏈接就會清空所有數據進行完整同步。當然新版本的Redis支持SYCN2的半同步，如果是已經建立了master/slave主從同步之后，主服務器會發送DEL命令給所有從服務器執行刪除操作。

4、Redis LRU算法

在使用Redis的時候我們會設置maxmemory選項，64位的默認是0不限制。線上的服務器必須要設置的，要不然很有可能導致Redis宿主服務器直接內存耗盡，最后鏈接都上不去。

所以基本要設置兩個配置：

• maxmemory最大內存閾值;
• maxmemory-policy到達閾值的執行策略。

可以通過CONFIG GET maxmemory/maxmemory-policy分別查看這兩個配置值，也可以通過CONFIG SET去分別配置。

• maxmemory-policy有一組配置，可以用在很多場景下：
• noeviction：客戶端嘗試執行會讓更多內存被使用的命令直接報錯;
• allkeys-lru：在所有key里執行lru算法;
• volatile-lru：在所有已經過期的key里執行lru算法;
• allkeys-random：在所有key里隨機回收;
• volatile-random：在已經過期的key里隨機回收;
• volatile-ttl：回收已經過期的key，并且優先回收存活時間(TTL)較短的鍵。

關于cache的命中率可以通過info命令查看鍵空間的命中率和未命中率。

# Stats 
keyspace_hits:33 
keyspace_misses:5 

maxmemory在到達閾值的時候會采用一定的策略去釋放內存，這些策略我們可以根據自己的業務場景來選擇，默認是noeviction 。

Redis LRU算法有一個取樣的優化機制，可以通過一定的取樣因子來加強回收的key的準確度。CONFIG GET maxmemory-samples查看取樣配置，具體可以參考更加詳細的文章。

三、Redis持久化方式

Redis本身提供持久化功能，有兩種持久化機制，一種是數據持久化RDB，一種是命令持久化AOF，這兩種持久化方式各有優缺點，也可以組合使用。一旦組合使用，Redis在載入數據的時候會優先載入aof文件，只有當AOF持久化關閉的時候才會載入rdb文件。

1、RDB(Redis DataBase)

RDB是Redis數據庫，Redis會根據一個配置來觸發持久化：

#save <seconds> <changes> 
 
save 900 1 
save 300 10 
save 60 10000 
 
CONFIG GET save 
1) "save" 
2) "3600 1 300 100 60 10000" 

表示在多少秒之類的變化次數，一旦達到這個觸發條件Redis將觸發持久化動作。

Redis在執行持久化的時候有兩種模式BGSAVE、SAVE：

• BGSAVE是后臺保存，Redis會fork出一個子進程來處理持久化，不會block用戶的執行請求;
• SAVE則會block用戶執行請求。

struct redisServer { 
long long dirty;/* Changes to DB from the last save */ 
time_t lastsave; /* Unix time of last successful save */ 
long long dirty_before_bgsave; 
pid_t rdb_child_pid;/* PID of RDB saving child */ 
struct saveparam *saveparams; /* Save points array for RDB */ 
} 
 
struct saveparam { 
    time_t seconds; 
    int changes; 
}; 

RedisServer包含的信息很多，其中就包含了有關于RDB持久化的信息。

redisServer->dirty至上次save到目前為止的change數。redisServer->lastsave上次save時間。

saveparam struct保存了我們通過save命令設置的參數，time_t是個long時間戳。

typedef __darwin_time_t     time_t; 
 
typedef long    __darwin_time_t;    /* time() */ 
 
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) { 
         for (j = 0; j < server.saveparamslen; j++) { 
            struct saveparam *sp = server.saveparams+j; 
            if (server.dirty >= sp->changes && 
                server.unixtime-server.lastsave > sp->seconds && 
                (server.unixtime-server.lastbgsave_try > 
                 REDIS_BGSAVE_RETRY_DELAY || 
                 server.lastbgsave_status == REDIS_OK)) 
            { 
                redisLog(REDIS_NOTICE,"%d changes in %d seconds. Saving...", 
                    sp->changes, (int)sp->seconds); 
                rdbSaveBackground(server.rdb_filename); 
                break; 
            } 
         } 
} 

Redis事件循環會周期性的執行serverCron方法，這段代碼會循環遍歷server.saveparams參數鏈表。

如果server.dirty大于等于我們參數里配置的變化并且server.unixtime-server.lastsave大于參數里配置的時間，并且server.unixtime-server.lastbgsave_try減去bgsave重試延遲時間，或者當前server.lastbgsave_status== REDIS_OK則執行rdbSaveBackground方法。

2、AOF(Append-only file)

AOF持久化是采用對文件進行追加對方式進行，每次追加都是Redis處理的命令。有點類似command sourcing命令溯源的模式，只要我們可以將所有的命令按照執行順序在重放一遍就可以還原最終的Redis內存狀態。

AOF持久化最大的優勢是可以縮短數據丟失的間隔，做到秒級的丟失率。RDB會丟失上一個保存周期到目前的所有數據，只要沒有觸發save命令設置的save seconds changes閾值數據就會一直不被持久化。

struct redisServer { 
 /* AOF buffer, written before entering the event loop */ 
 sds aof_buf; 
 } 
 
struct sdshdr { 
    unsigned int len; 
    unsigned int free; 
    char buf[]; 
}; 

aof_buf是命令緩存區，采用sds結構緩存，每次當有命令被執行當時候都會寫一次到aof_buf中。有幾個配置用來控制AOF持久化的機制。

appendonly no  
appendfilename "appendonly.aof" 

appendonly用來控制是否開啟AOF持久化，appendfilename用來設置aof文件名。

appendfsync always 
appendfsync everysec 
appendfsync no 

appendfsync用來控制命令刷盤機制?，F在操作系統都有文件cache/buffer的概念，所有的寫入和讀取都會走cache/buffer，并不會每次都同步刷盤，因為這樣性能一定會受影響。所以Redis也提供了這個選項讓我們來自己根據業務場景控制。

• always：每次將aof_buf命令寫入aof文件并且執行實時刷盤。
• everysec：每次將aof_buf命令寫入aof文件，但是每隔一秒執行一次刷盤。
• no：每次將aof_buf命令寫入aof文件不執行刷盤，由操作系統來自行控制。

AOF也是采用后臺子進程的方式進行，與主進程共享數據空間也就是aof_buf，但是只要開始了AOF子進程之后Redis事件循環文件事件處理器會將之后的命令寫入另外一個aof_buf，這樣就可以做到平滑的切換。

AOF會不斷的追加命令進aof文件，隨著時間和并發量的加大aof文件會極速膨脹，所以有必要對這個文件大小進行優化。Redis基于rewrite重寫對文件進行壓縮。

no-appendfsync-on-rewrite no/yes 
auto-aof-rewrite-percentage 100 
auto-aof-rewrite-min-size 64mb 

no-appendfsync-on-rewrite控制是否在bgrewriteaof的時候還需要進行命令追加，如果追加可能會出現磁盤IO跑高現象。

上面說過，當AOF進程在執行的時候原來的事件循環還會正常的追加命令進aof文件，同時還會追加命令進另外一個aof_buf，用來做新aof文件的重寫。這是兩條并行的動作，如果我們設置成yes就不追加原來的aof_buf 因為新的aof文件已經包含了之后進來的命令。

auto-aof-rewrite-percentage和auto-aof-rewrite-min -size64mb這兩個配置前者是文件增長百分比來進行rewrite，后者是按照文件大小增長進行rewrite。