Redis底層資料結構
目标：
- 掌握Redis資料類型的底層資料結構
- 了解LRU
- 能夠編寫Redis事務處理，了解弱事務
- 了解Redis樂觀鎖及秒殺的實作
Redis記憶體模型 Redis記憶體統計
127.0.0.1:6379># Memoryinfo memory
#Redis配置設定的記憶體總量,包括虛拟記憶體(位元組)
used_memory:853464
#占作業系統的記憶體，不包括虛拟記憶體(位元組)
used_memory_rss:12247040
#記憶體碎片比例 如果小于0說明使用了虛拟記憶體
mem_fragmentation_ratio:15.07
#Redis使用的記憶體配置設定器
mem_allocator:jemalloc-5.1.0
Redis記憶體配置設定 資料：作為資料庫，資料是最主要的部分；這部分占用的記憶體會統計在 used_memory 中。Redis 使用鍵值對存儲資料，其中的值（對象）包括 5 種類型，即字元串、哈希、清單、集合、有序集合。這 5 種類型是 Redis 對外提供的，實際上，在 Redis 内部，每種類型可能有 2 種或更多的内部編碼實作 程序： Redis 主程序本身運作肯定需要占用記憶體，如代碼、常量池等等；這部分記憶體大約幾M，在大多數生産環境中與 Redis 資料占用的記憶體相比可以忽略。這部分記憶體不是由 jemalloc 配置設定，是以不會統計在 used_memory 中。補充說明：除了主程序外，Redis 建立的子程序運作也會占用記憶體，如 Redis 執行 AOF、RDB 重寫時建立的子程序。當然，這部分記憶體不屬于 Redis 程序，也不會統計在 used_memory 和 used_memory_rss 中。 緩沖記憶體：緩沖記憶體包括用戶端緩沖區、複制積壓緩沖區、AOF 緩沖區等；其中，用戶端緩沖區存儲用戶端連接配接的輸入輸出緩沖；複制積壓緩沖區用于部分複制功能；AOF 緩沖區用于在進行 AOF 重寫時，儲存最近的寫入指令。在了解相應功能之前，不需要知道這些緩沖的細節；這部分記憶體由 jemalloc 配置設定，是以會統計在used_memory 中。 記憶體碎片：記憶體碎片是 Redis 在配置設定、回收實體記憶體過程中産生的。例如，如果對資料的更改頻繁，而且資料之間的大小相差很大，可能導緻 Redis 釋放的空間在實體記憶體中并沒有釋放。但 Redis 又無法有效利用，這就形成了記憶體碎片，記憶體碎片不會統計在 used_memory 中。記憶體碎片的産生與對資料進行的操作、資料的特點等都有關；此外，與使用的記憶體配置設定器也有關系：如果記憶體配置設定器設計合理，可以盡可能的減少記憶體碎片的産生。如果 Redis 伺服器中的記憶體碎片已經很大，可以通過安全重新開機的方式減小記憶體碎片：因為重新開機之後，Redis 重新從備份檔案中讀取資料，在記憶體中進行重排，為每個資料重新選擇合适的記憶體單元，減小記憶體碎片。 Redis資料結構 Redis 沒有直接使用 C 字元串(即以空字元’\0’結尾的字元數組)作為預設的字元串表示，而是使用了SDS。SDS 是簡單動态字元串(Simple Dynamic String)的縮寫。它是自己建構了一種名為 簡單動态字元串（simple dynamic string,SDS）的抽象類型，并将 SDS 作為Redis的預設字元串表示。 簡單動态字元串（simple dynamic string,SDS） 定義：
struct sdshdr{
//記錄buf數組中已使用位元組的數量
//等于 SDS 儲存字元串的長度
int len;
//記錄 buf 數組中未使用位元組的數量
int free;
//位元組數組，用于儲存字元串
char buf[];
}
buf數組的長度=free+len+1
好處：
SDS 在 C 字元串的基礎上加入了 free 和 len 字段，帶來了很多好處：
擷取字元串長度：SDS 是 O(1)，C 字元串是 O(n)。
緩沖區溢出：使用 C 字元串的 API 時，如果字元串長度增加（如 strcat 操作）而忘記重新配置設定記憶體，很容易造成緩沖區的溢出。而 SDS 由于記錄了長度，相應的 API 在可能造成緩沖區溢出時會自動重新配置設定記憶體，杜絕了緩沖區溢出。
修改字元串時記憶體的重配置設定：對于 C 字元串，如果要修改字元串，必須要重新配置設定記憶體（先釋放再申請），因為如果沒有重新配置設定，字元串長度增大時會造成記憶體緩沖區溢出，字元串長度減小時會造成記憶體洩露。而對于 SDS，由于可以記錄 len 和 free，是以解除了字元串長度和空間數組長度之間的關聯，可以在此基礎上進行優化。空間預配置設定政策（即配置設定記憶體時比實際需要的多）使得字元串長度增大時重新配置設定記憶體的機率大大減小；惰性空間釋放政策使得字元串長度減小時重新配置設定記憶體的機率大大減小。
存取二進制資料：SDS 可以，C 字元串不可以。因為 C 字元串以空字元作為字元串結束的辨別，而對于一些二進制檔案（如圖檔等）。内容可能包括空字元串，是以 C 字元串無法正确存取；而 SDS 以字元串長度 len 來作為字元串結束辨別，是以沒有這個問題。此外，由于 SDS 中的 buf 仍然使用了 C 字元串（即以’\0’結尾），是以 SDS 可以使用 C 字元串庫中的部分函數。但是需要注意的是，隻有當 SDS 用來存儲文本資料時才可以這樣使用，在存儲二進制資料時則不行（’\0’不一定是結尾）。
使用：所有的key；資料裡的字元串；AOF緩沖區和使用者輸入緩沖。
連結清單定義
typedef struct listNode {
//前置節點
struct listNode *prev;
//後置節點
struct listNode *next;
//節點的值
void *value;
}listNode
typedef struct list {
//表頭節點
listNode.head;
//表尾節點
listNode.tail;
//連結清單所包含的節點數量
unsigned long len;
//節點值複制函數
void *(*dup)(void *ptr);
//節點值釋放函數
void *(*free)(void *ptr);
//節點值對比函數
int (*match)(void *ptr,void *key);
} list;
Redis連結清單優勢：
①、雙向：連結清單具有前置節點和後置節點的引用，擷取這兩個節點時間複雜度都為O(1)。與傳統連結清單（單連結清單）相比，Redis連結清單結構的優勢有：普通連結清單（單連結清單）：節點類保留下一節點的引用。連結清單類隻保留頭節點的引用，隻能從頭節點插入删除
②、無環：表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL,對連結清單的通路都是以 NULL結束。
③、帶連結清單長度計數器：通過 len 屬性擷取連結清單長度的時間複雜度為 O(1)。
④、多态：連結清單節點使用 void* 指針來儲存節點值，可以儲存各種不同類型的值。
連結清單和清單差別
linkedlist和arraylist
連結清單在Redis中的應用非常廣泛，清單(List)的底層實作之一就是雙向連結清單。此外釋出與訂閱、慢查詢、螢幕等功能也用到了連結清單。
字典 字典又稱為符号表或者關聯數組、或映射（map），是一種用于儲存鍵值對的抽象資料結構。字典中的每一個鍵 key 都是唯一的，通過 key 可以對值來進行查找或修改。Redis 的字典使用哈希表作為底層實作。哈希（作為一種資料結構），不僅是 Redis 對外提供的 5 種對象類型的一種（hash），也是 Redis 作為 Key-Value 資料庫所使用的資料結構。
typedef struct dictht{
//哈希表數組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計算索引值
//總是等于 size-1
unsigned long sizemask;
//該哈希表已有節點的數量
unsigned long used;
}dictht
/*哈希表是由數組 table 組成，table 中每個元素都是指向 dict.h/dictEntry 結構，
dictEntry 結構定義如下：
*/
typedef struct dictEntry{
//鍵
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一個哈希表節點，形成連結清單
struct dictEntry *next;
}dictEntry
typedef struct zskiplistNode {
//層
struct zskiplistLevel{
//前進指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
//後退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
} zskiplistNode
--連結清單
typedef struct zskiplist{
//表頭節點和表尾節點
structz skiplistNode *header, *tail;
//表中節點的數量
unsigned long length;
//表中層數最大的節點的層數
int level;
}zskiplist;
整數集合
整數集合（intset）是集合（set）的底層實作之一，當一個集合（set）隻包含整數值元素，并且這個集合的元素不多時，Redis就會使用整數集合(intset)作為該集合的底層實作。整數集合（intset）是
Redis用于儲存整數值的集合抽象資料類型，它可以儲存類型為int16_t、int32_t 或者int64_t 的整數值，并且保證集合中不會出現重複元素。
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素數量
uint32_t length;
//儲存元素的數組
int8_t contents[];
}intset;
壓縮清單
壓縮清單（ziplist）是清單鍵和哈希鍵的底層實作之一。當一個清單隻包含少量清單項時，并且每個清單項時小整數值或短字元串，那麼Redis會使用壓縮清單來做該清單的底層實作。
壓縮清單（ziplist）是Redis為了節省記憶體而開發的，是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構，一個壓縮清單可以包含任意多個節點（entry），每個節點可以儲存一個位元組數組或者一個整數值。放到一個連續記憶體區。
previous_entry_ength： 記錄壓縮清單前一個位元組的長度。
encoding：節點的encoding儲存的是節點的content的内容類型
content：content區域用于儲存節點的内容，節點内容類型和長度由encoding決定。
對象
前面我們講了Redis的資料結構，Redis不是用這些資料結構直接實作Redis的鍵值對資料庫，而是基于這些資料結建構立了一個對象系統。包含字元串對象，清單對象，哈希對象，集合對象和有序集合對象。根據對象的類型可以判斷一個對象是否可以執行給定的指令，也可針對不同的使用場景，對象設定有多種不同的資料結構實作，進而優化對象在不同場景下的使用效率。Redis中的每個對象都是由如下結構表示（列出了與儲存資料有關的三個屬性）
typedef struct redisObject {
unsigned type:4;//類型 五種對象類型
unsigned encoding:4;//編碼
void *ptr;//指向底層實作資料結構的指針
//...
int refcount;//引用計數
//...
unsigned lru:22;//記錄最後一次被指令程式通路的時間
//...
}robj;
type
type 字段表示對象的類型，占 4 個比特；目前包括 REDIS_STRING(字元串)、REDIS_LIST (清單)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。當我們執行 type 指令時，便是通過讀取 RedisObject 的 type 字段獲得對象的類型，如下所示：
127.0.0.1:6379> type a1 string
encoding
encoding 表示對象的内部編碼，占 4 個比特。對于 Redis 支援的每種類型，都有至少兩種内部編碼，例如對于字元串，有 int、embstr、raw 三種編碼。通過 encoding 屬性，Redis 可以根據不同的使用場景來為對象設定不同的編碼，大大提高了 Redis 的靈活性和效率。
以清單對象為例，有壓縮清單和雙端連結清單兩種編碼方式；
如果清單中的元素較少，Redis 傾向于使用壓縮清單進行存儲，因為壓縮清單占用記憶體更少，而且比雙端連結清單可以更快載入。
當清單對象元素較多時，壓縮清單就會轉化為更适合存儲大量元素的雙端連結清單。
通過 object encoding 指令，可以檢視對象采用的編碼方式，如下所示：
127.0.0.1:6379> object encoding a1 "int"
lru
lru 記錄的是對象最後一次被指令程式通路的時間，占據的比特數不同的版本有所不同（如 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 的作用，主要在于對象的引用計數和記憶體回收。
當建立新對象時，refcount 初始化為 1；當有新程式使用該對象時，refcount 加 1；當對象不再被一個新程式使用時，refcount 減 1；當 refcount 變為 0 時，對象占用的記憶體會被釋放。
Redis 中被多次使用的對象(refcount>1)，稱為共享對象。Redis 為了節省記憶體，當有一些對象重複出現時，新的程式不會建立新的對象，而是仍然使用原來的對象。這個被重複使用的對象，就是共享對象。目前共享對象僅支援整數值的字元串對象。共享對象的引用次數可以通過 object refcount 指令檢視，如下所示。指令執行的結果頁佐證了隻有0~9999 之間的整數會作為共享對象。
127.0.0.1:6379> object refcount a1 (integer) 2147483647
ptr
ptr 指針指向具體的資料，比如：set hello world，ptr 指向包含字元串 world 的 SDS。
綜上所述，RedisObject 的結構與對象類型、編碼、記憶體回收、共享對象都有關系。
