Redis 數據結構與內存管理策略（下）

Redis 數據結構與內存管理策略（下）

標簽： Redis Redis數據結構 Redis內存管理策略 Redis數據類型 Redis類型映射

• Redis 數據類型特點與使用場景
  • String、List、Hash、Set、Zset
  • 案例：滬江團購系統大促 hot-top 接口 cache 設計
• Redis 內存數據結構與編碼
  • OBJECT encoding key、DEBUG OBJECT key
  • 簡單動態字符串（simple dynamic string）
  • 鏈表（linked list）
  • 字典（dict）
  • 跳表（skip list）
  • 整數集合（int set）
  • 壓縮表（zip list）
  • Redis Object 類型與映射
• Redis 內存管理策略
  • 鍵 過期時間、生存時間
  • 過期鍵刪除策略
  • AOF 、RDB 處理過期鍵策略
  • Redis LRU 算法
• Redis 持久化方式
  • RDB (Redis DataBase)
  • AOF (Append-only file)

字典（dict）

dict 字典是基于 hash算法 來實現，是 Hash 數據類型的底層存儲數據結構。我們來看下 redis 3.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 結束。

跳表（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 分值，每個分值都會按照順序排列。

整數集合（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 整數將觸發升級，一旦升級成功不會觸發降級操作。

壓縮表（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 數據類型的底層壓縮閾值控制。

Redis Object 類型與映射

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

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 種數據類型與底層數據結構和編碼的對應關系，但是這種對應關系在每一個版本中都會有可能發生變化，這也是 redisObject 的靈活性所在，有著 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 鍵空間 。每一個 redis client 只能屬于一個 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 的過期時間。

鍵 過期時間、生存時間

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

EXPIRE 命令可以設置某個 key 多少秒之后過期
PEXPIRE 命令可以設置某個 key 多少毫秒之后過期

EXPIREAT 命令可以設置某個 key 在多少秒時間戳之后過期
PEXPIREAT 命令可以設置某個 key 在多少毫秒時間戳之后過期

PERSIST 命令可以移除鍵的過期時間

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

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

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

過期鍵刪除策略

在使用 redis 的時候我們最關心的就是鍵是如何被刪除的，如何高效的準時的刪除某個鍵。其實 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 。

AOF 、RDB 處理過期鍵策略

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

當 redis 使用 RDB 方式持久化時，每次持久化的時候就會檢查這些即將被持久化的 key 是否已經過期，如果過期將直接忽略，持久化那些沒有過期的鍵。當 redis 作為 master 主服務器 啟動的時候，在載入 rdb 持久化鍵時也會檢查這些鍵是否過期，將忽略過期的鍵，只載入沒過期的鍵。

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

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

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 文件。

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__ 方法。

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 用來控制命令刷盤機制。現在操作系統都有文件 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-size 64mb 這兩個配置前者是文件增長百分比來進行 rewrite ，后者是按照文件大小增長進行 rewrite 。