Redis記憶體模型(2)：存儲細節

1. 概述先看一下執行時，所涉及的數據模型：（1）dictEntry：Redis是Key Value資料庫，因此對每個鍵值對都會有一個dictEntry，裡面存儲了指向Key和Value的指針；next指向下一個dictEntry，與本Key Value無關。（2）Key：圖中右上角可見，K ...

1. 概述

先看一下執行set hellow world時，所涉及的數據模型：

（1）dictEntry：Redis是Key-Value資料庫，因此對每個鍵值對都會有一個dictEntry，裡面存儲了指向Key和Value的指針；next指向下一個dictEntry，與本Key-Value無關。

（2）Key：圖中右上角可見，Key（”hello”）並不是直接以字元串存儲，而是存儲在SDS結構中。

（3）val：Value(“world”)既不是直接以字元串存儲，也不是像Key一樣直接存儲在SDS中，而是存儲在redisObject中。實際上，不論Value是5種類型的哪一種，都是通過redisObject來存儲的；而redisObject中的type欄位指明瞭Value對象的類型，ptr欄位則指向對象所在的地址。不過可以看出，字元串對象雖然經過了redisObject的包裝，但仍然需要通過SDS存儲。

（4）ptr：ptr指針指向具體的數據，如上圖，ptr指向包含字元串world的SDS。

（5）jemalloc：無論是DictEntry對象，還是redisObject、SDS對象，都需要記憶體分配器（如jemalloc）分配記憶體進行存儲。以DictEntry對象為例，有3個指針組成，在64位機器下占24個位元組，jemalloc會為它分配32位元組大小的記憶體單元。

Redis在編譯時便會指定記憶體分配器；記憶體分配器可以是 libc 、jemalloc或者tcmalloc，預設是jemalloc。
jemalloc作為Redis的預設記憶體分配器，在減小記憶體碎片方面做的相對比較好。jemalloc在64位系統中，將記憶體空間劃分為小、大、巨大三個範圍；每個範圍內又劃分了許多小的記憶體塊單位；當Redis存儲數據時，會選擇大小最合適的記憶體塊進行存儲。

2.redisObject

Redis對象有5種類型；無論是哪種類型，Redis都不會直接存儲，而是通過redisObject對象進行存儲。
redisObject對象非常重要，Redis對象的類型、內部編碼、記憶體回收、共用對象等功能，都需要redisObject支持，下麵將通過redisObject的結構來說明它是如何起作用的。
定義如下（不同版本的Redis可能稍稍有所不同）：

typedef struct redisObject {
　　unsigned type:4;
　　unsigned encoding:4;
　　unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
　　int refcount;
　　void *ptr;
} robj;

redisObject的每個欄位的含義和作用如下：

type
type欄位表示對象的類型，占4個比特；目前包括REDIS_STRING(字元串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。
當我們執行type命令時，便是通過讀取RedisObject的type欄位獲得對象的類型：
encoding
encoding表示對象的內部編碼，占4個比特。對於Redis支持的每種類型，都有至少兩種內部編碼，例如對於字元串，有int、embstr、raw三種編碼。通過encoding屬性，Redis可以根據不同的使用場景來為對象設置不同的編碼，大大提高了Redis的靈活性和效率。
通過object encoding命令，可以查看對象採用的編碼方式：
lru
ru記錄的是對象最後一次被命令程式訪問的時間，占據的比特數不同的版本有所不同（如4.0版本占24比特，2.6版本占22比特）。

通過對比lru時間與當前時間，可以計算某個對象的空轉時間；object idletime命令可以顯示該空轉時間（單位是秒）。object idletime命令的一個特殊之處在於它不會改變對象的lru值。
lru值除了通過object idletime命令列印之外，還與Redis的記憶體回收有關係：如果Redis打開了maxmemory選項，且記憶體回收演算法選擇的是volatile-lru或allkeys—lru，那麼當Redis記憶體占用超過maxmemory指定的值時，Redis會優先選擇空轉時間最長的對象進行釋放。
refcount
refcount記錄的是該對象被引用的次數，類型為整型。refcount的作用，主要在於對象的引用計數和記憶體回收。當創建新對象時，refcount初始化為1；當有新程式使用該對象時，refcount加1；當對象不再被一個新程式使用時，refcount減1；當refcount變為0時，對象占用的記憶體會被釋放。

共用對象
Redis中被多次使用的對象(refcount>1)，稱為共用對象。Redis為了節省記憶體，當有一些對象重覆出現時，新的程式不會創建新的對象，而是仍然使用原來的對象。
目前共用對象僅支持整數值的字元串對象。之所以如此，實際上是對記憶體和CPU（時間）的平衡：共用對象雖然會降低記憶體消耗，但是判斷兩個對象是否相等卻需要消耗額外的時間。對於整數值，判斷操作複雜度為O(1)；對於普通字元串，判斷複雜度為O(n)；而對於哈希、列表、集合和有序集合，判斷的複雜度為O(n^2)。雖然共用對象只能是整數值的字元串對象，但是5種類型都可能使用共用對象。
Redis伺服器在初始化時，會創建10000個字元串對象，值分別是0~9999的整數值；當Redis需要使用值為0~9999的字元串對象時，可以直接使用這些共用對象。10000這個數字可以通過調整參數REDIS_SHARED_INTEGERS（4.0中是OBJ_SHARED_INTEGERS）的值進行改變。
ptr
見上文。
總結
綜上所述，redisObject的結構與對象類型、編碼、記憶體回收、共用對象都有關係；一個redisObject對象的大小為16位元組：
4bit+4bit+24bit+4Byte+8Byte=16Byte。

3. SDS(simple dynamic string, 簡單動態字元串)

Redis沒有直接使用C字元串(即以空字元’\0’結尾的字元數組)作為預設的字元串表示，而是使用了SDS。

SDS結構
結構如下：

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

其中，，buf表示位元組數組，用來存儲字元串；len表示buf已使用的長度，free表示buf未使用的長度。

通過SDS的結構可以看出，buf數組的長度=free+len+1（其中1表示字元串結尾的空字元）；所以，一個SDS結構占據的空間為：free所占長度+len所占長度+ buf數組的長度=4+4+free+len+1=free+len+9。
free及len所占長度指的是存儲具體數值所占用的空間，典型的空間換時間，降低了時間複雜度。

SDS與C字元串比較
SDS在C字元串的基礎上加入了free和len欄位，帶來了以下好處：
1. 獲取字元串長度：SDS是O(1)，C字元串是O(n)
2. 緩衝區溢出：使用C字元串的API時，如果字元串長度增加（如strcat操作）而忘記重新分配記憶體，很容易造成緩衝區的溢出；而SDS由於記錄了長度，相應的API在可能造成緩衝區溢出時會自動重新分配記憶體，杜絕了緩衝區溢出。
3. 修改字元串時記憶體的重分配：對於C字元串，如果要修改字元串，必須要重新分配記憶體（先釋放再申請），因為如果沒有重新分配，字元串長度增大時會造成記憶體緩衝區溢出，字元串長度減小時會造成記憶體泄露。而對於SDS，由於可以記錄len和free，因此解除了字元串長度和空間數組長度之間的關聯，可以在此基礎上進行優化：空間預分配策略（即分配記憶體時比實際需要的多）使得字元串長度增大時重新分配記憶體的概率大大減小；惰性空間釋放策略使得字元串長度減小時重新分配記憶體的概率大大減小。
4. 存取二進位數據：SDS可以，C字元串不可以。因為C字元串以空字元作為字元串結束的標識，而對於一些二進位文件（如圖片等），內容可能包括空字元串，因此C字元串無法正確存取；而SDS以字元串長度len來作為字元串結束標識，因此沒有這個問題。
  
  由於SDS中的buf仍然使用了C字元串（即以’\0’結尾），因此SDS可以使用C字元串庫中的部分函數；但是需要註意的是，只有當SDS用來存儲文本數據時才可以這樣使用，在存儲二進位數據時則不行（’\0’不一定是結尾）。
SDS與C字元串的應用
Redis在存儲對象時，一律使用SDS代替C字元串。例如set hello world，hello和world都是以SDS的形式存儲的。而sadd myset member1 member2 member3，不論是鍵（”myset”），還是集合中的元素（”member1”、 ”member2”和”member3”），都是以SDS的形式存儲。除了存儲對象，SDS還用於存儲各種緩衝區。
只有在字元串不會改變的情況下，如列印日誌時，才會使用C字元串。