引言
前幾天剛看完《Redis設計與實作》這本書籍，該書籍也較完整地記錄了Redis的底層設計與相關功能的實作細節，對于更深入了解Redis，該書的确有很大幫助，故記錄一些重要知識點。
資料結構與對象
很多人對于Redis的資料類型基本都了解，一般可分為五大資料類型：String、哈希（Hash）、清單（List）、集合（Set）、有序集合（Zset），Redis資料庫裡面的每個鍵值對都是由對象（Object）組成的，其中：
- 資料庫鍵總是由一個字元串對象（Object）構成
- 資料庫鍵的值則可以是由字元串對象、清單對象、哈希對象、集合對象、有序集合對象五種其中的一種
究其這些資料類型的底層實作細節，則具體由以下這些組成：
簡單動态字元串（SDS）
由于Redis是由C語言編寫的，但Redis并沒有直接使用C語言傳統的字元串表示（一般以空字元結尾的字元數組），而是建構了一種動态字元串（SDS）的抽象類型，并作為預設字元串表示
例如：在用戶端執行
- set k1 v1
Redis在資料庫中建立一個新的鍵值對：其中
鍵為字元串對象，對象底層實作是儲存着一個字元串“k1”的SDS
值為字元串對象，對象底層實作是儲存着一個字元串“v1”的SDS
同理：執行以下操作
鍵為字元串對象，對象底層實作是儲存着一個字元串“k1”的SDS
值為清單對象，清單對象包含三個字元串對象，這三個字元串對象分别由三個SDS實作
SDS的定義
底層資料結構
struct sdshdr{
int len; SDS所儲存的字元串的長度
int free; buf[]數組中未使用的空間
char buf[]; 字元數組
}
SDS與C字元串的差別
- 計數方式不同
C語言對字元串長度的統計，就完全來自周遊，從頭周遊到末尾，直到發現空字元就停止，以此統計出字元串的長度，這樣擷取長度的時間複雜度來說是0（n），但SDS在len屬性中就記錄了SDS本身的長度，是以擷取SDS長度的複雜度為O（1）
- 防止緩沖區溢出
C是不記錄字元串長度的，是以在一旦我們調用了拼接的函數，對兩個字元串進行拼接，如果沒有提前計算好記憶體，是會産生緩存區溢出的，導緻其他區的内容被意外修改，而SDS的空間配置設定政策就杜絕了發生緩沖區溢出的可能性，在拼接前判斷free的長度是否可以放得下，如果長度夠就直接執行，如果不夠，那就先進行擴容。
- 減少修改字元串時帶來的記憶體重配置設定次數
由于C字元串并不記錄自身的長度，是以對于一個包含N個字元的C字元串來說，其底層實作是由一個N+1長度的字元數組組成的，而每次增長或縮短一個C字元串時，需要對字元串進行頻繁的拼接和截斷操作，進行一次記憶體的重配置設定操作，如果我們寫代碼忘記了重新配置設定記憶體，就可能造成緩沖區溢出，以及記憶體洩露。
而Redis為了避免C字元串這樣的缺陷，就分别采用了兩種解決方案：
（1）空間預配置設定
當我們對SDS進行擴充操作的時候，Redis會為SDS配置設定好記憶體，并且根據特定的規則，配置設定多餘的free空間，還有多餘的1位元組空間（這1位元組也是為了存空字元），這樣就可以避免我們連續執行字元串添加所帶來的記憶體配置設定消耗，減少配置設定次數
（2）惰性空間釋放
惰性空間釋放用于優化SDS的字元串的縮短操作，當執行一個字元串縮減的操作後，程式并不立即使用記憶體重配置設定來回收縮短後多出來的位元組，而是用free屬性來将這些位元組的數量記錄起來，并等待将來的使用
- 二進制安全
C語言是通過判斷空字元去判斷一個字元的長度的，是以除了字元串的末尾之外，字元串裡面不能包含字元串，但是有很多資料結構經常會穿插空字元在中間，比如圖檔，音頻，視訊，壓縮檔案的二進制資料。而SDS就不存在這個問題了，由于其資料結構儲存了字元串的長度，是以直接判斷長度即可，是以Redis可以适用于各種不同的處理場景
連結清單
連結清單作為一種常用的資料結構，内置在很多進階語言裡面，因為Redis是使用C語言，并沒有内置這種資料結構，是以Redis建構了自己的連結清單實作
當一個清單鍵包含了數量較多的元素，或者清單包含的元素都是比較長的字元串的時候，Redis就會使用連結清單作為清單鍵的底層實作
資料結構：listNode
typedef struct listNode{
//前置節點
struct listNode *prev;
//後置節點
struct listNode *next;
// 節點的值
void *value;
}listNode;
多個listNode通過前驅指針和後繼指針來組成一個雙端連結清單
資料結構：list
typedef struct list{
//連結清單頭節點
listNode *head;
//連結清單尾節點
listNode *tail;
//連結清單長度
unsigned long len;
}list;
特點：
- 節點通過prev和next指針實作雙端連結清單
- 表頭節點的pre與表尾節點的next都指向NULL，不是個循環連結清單，對連結清單的通路會以NULL結束
- list帶表頭與表尾指針，程式可以快速的擷取表頭與表尾。
- 通過len屬性可以快帶的擷取連結清單的長度。
字典
字典，又稱為符号表、映射，是一種用于儲存鍵值對的抽象資料結構
在字典中，一個鍵（key）可以和一個值（value）進行關聯，每一個鍵都是獨一無二的，程式可以在字典中根據鍵查找與之關聯的值
例如：執行以下指令
在資料庫中建立一個鍵為k1，值為v1的鍵值對，這個鍵值對就儲存在代表資料庫的字典裡面
除了用來表示資料庫之外，字典也是哈希鍵的底層實作之一，當一個哈希鍵包含的鍵值對比較多，又或者鍵值對中的元素都是比較長的字元串時候，Redis就會使用字典作為哈希鍵的底層實作
資料結構：哈希表的節點結構
typedef struct dictEntry{
//鍵
void *key;
//值
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
//指向一個哈希表的節點
struct dictEnty *next;
}dictEnty
資料結構：哈希表結構
typedef struct dictht{
//哈希表的數組
dictEntry **table;
//哈希表的大小
unsigned long size;
//哈希表的掩碼，用于計算索引值
unsigned long sizemask;
//已有的節點數
unsigned long used;
}dictht
雜湊演算法
當要将一個新的鍵值對添加到字典裡面時，程式需要先根據鍵值對的鍵計算出哈希值和索引值，根據索引值，将包含新鍵值對的哈希表節點放到哈希數組的指定索引上
解決鍵沖突
當兩個或以上的鍵被配置設定到同一索引上時，就發生了鍵沖突，Redis的哈希表使用鍊位址法來解決鍵沖突，原理和hashmap的底層原理類似
跳躍表
跳躍表（Skiplist）是一種有序資料結構，他通過在每個節點中維持多個指向其他節點的指針，進而達到快速通路節點的目的
Redis使用跳躍表作為有序集合鍵的底層實作之一，如果一個有序集合包含較多的元素，又或者有序集合中的成員是較長的字元串時候，Redis就會使用跳躍表來作為有序集合的底層實作
使用跳躍表原因
首先，因為 zset 要支援随機的插入和删除，是以它不宜使用數組來實作，關于排序問題，也很容易就想到紅黑樹/ 平衡樹這樣的樹形結構，為什麼 Redis 不使用這樣一些結構呢
- 性能考慮： 在高并發的情況下，樹形結構需要執行一些類似于 rebalance 這樣的可能涉及整棵樹的操作，相對來說跳躍表的變化隻涉及局部
- 實作考慮： 在複雜度與紅黑樹相同的情況下，跳躍表實作起來更簡單，看起來也更加直覺；
具體細節實作：跳躍表實作，這篇文章詳細介紹了跳躍表底層實作細節
整數集合
整數集合（intset）是集合鍵的底層實作之一，當一個集合隻包含整數值元素，并且這個集合的元素數量不多時，Redis就會使用整數集合作為集合鍵的底層實作
資料結構：
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素數量
uint32_t length;
//儲存元素的數組
int8_t contents[];
}
contents數組是整數集合的底層實作：整數集合的每個元素都是該數組的一個數組項，各個項在數組中按值的大小從小到大有序的排列，并且數組中不包含任何重複項
contents數組的真正類型取決于encoding的編碼方式，而編碼方式的選擇取決于整數值的大小
更新
當要将一個新元素添加到整數集合裡面，并且新元素的類型比整數集合現有的所有元素的類型都要長時，整數集合需要先進行更新，然後才能将新元素添加到整數集合裡面。
降級
整數集合不支援降級操作，一旦對數組進行了更新，編碼就會一直按照更新後的編碼方式儲存資料
壓縮清單
壓縮清單（ziplist）是清單鍵和哈希鍵的底層實作之一。
- 當一個清單鍵隻包含少量清單項，并且每個清單項要麼是小整數值，要麼就是長度較短的字元串時，Redis就會使用壓縮清單來做清單鍵的底層實作
- 當一個哈希鍵隻包含少量的鍵值對，并且每個鍵和值要麼是小整數值，要麼就是長度較短的字元串時，Redis就會使用壓縮清單來做哈希鍵的底層實作
壓縮清單是Redis為了節省記憶體而開發的，由一系列特殊編碼的連續記憶體塊組成的順序型資料結構。一個壓縮清單可以包含任意多個節點（entry），每個節點可以儲存一個位元組數組或者一個整數值
對象
Redis資料庫基于上面的資料結建構立了一個對象系統，這個系統包括：字元串對象，清單對象，哈希對象，集合對象，有序集合對象。在 Redis裡每建立一個鍵值對會建立兩個對象，分别為鍵對象與值對象，每個對象都用到了至少一種前面所介紹的資料結構，每個對象都由redisObject結構表示：
typedef struct redisObject{
//類型
unsigned type;
//編碼,底層資料結構
unsigned encoding;
//指向底層實作資料結構的指針
void *ptr;
//引用計數器 通過OBJECT REFCOUNT 可以檢視
int refcount;
//空轉時長 通過OBJECT IDLETIME 可以檢視
unsigned lru;
}robj;
其中type值隻有五種類型，分别為：string，list，hash，set，zset，可以通過TYPE key得到對象的類型。
而encoding用于辨別所使用的底層的資料結構，可能通過
OBJCET ENCODING key
來檢視某個值對象的底層結構。encoding可能的輸出為：int（long類型整數），embstr（embstr編碼的簡單動态字元串）, raw（簡單動态字元串），ht（字典），linkedlist（雙端連結清單），ziplist（壓縮清單），intset（整數集合），skiplist（跳躍表和字典）。
每種類型的對象都至少使用了兩種不同的編碼
字元串對象
字元串的編碼可能是int, embstr, raw這三種之中的一種。
1、為int的情況是存的這個整數值可以用long類型(浮點數不在這個範圍内)來表示。
2、當存的值是字元串，且長度小于39位元組的時候，采用的是embstr結構來存儲，
3、其它情況采用的是raw方式存儲。
embstr與raw的差別為：embstr專門用于存儲短字元串，主要是為了在建立對象的時候隻需要調用一次記憶體配置設定函數，而raw會調用兩次記憶體配置設定函數
清單對象
清單對象的編碼可能是雙端連結清單（linkedlist）或者壓縮清單（ziplist）。
當清單對象同時滿足所有字元串的長度都小于64位元組且元素數量小于512個時，采用的是壓縮清單的方式。其它情況采用雙端清單來進行存儲。
哈希對象
哈希對象的編碼可以是壓縮清單（ziplist）或者hashtable 。
隻有當哈希對象儲存的鍵值對的鍵和值的字元串長度都小于64位元組且對象儲存的鍵數量小于512個，才使用壓縮清單的方式進行存儲，其它情況采用的是hashtable。
當采用壓縮清單來存儲時有如下特點：
- 儲存同一個鍵值對的兩個節點總是緊挨在一起，鍵的節點在前，值的節點在後。
- 增加鍵值對放到壓縮清單表尾。
集合對象
集合對象的編碼可以是intset或者hashtable來實作。
使用intset編碼的條件為集合中的所有元素全為整數值且對象儲存的元素數量不超過512 個。其他情況都是采用hashtable的編碼方式來儲存的資料值
有序集合對象
有序集合對象可以采用壓縮清單（ziplist）或者跳躍表加字典的方式來實作。
當儲存的元素小于128個且每個元素長度都小于64個位元組采壓縮清單的方式來儲存，壓縮清單内在元素按分值大小進行排序，分值小的靠近表頭，每個元素占用兩個節點，第一個節點儲存值，第二個節點儲存分值。其它情況用的是跳躍表+字典的方式儲存
記憶體回收
由于C語言并不具備自動記憶體回收的功能，是以Redis在自己的對象系統中建構了一個引用計數（reference counting）計數實作記憶體回收機制，通過這一機制，程式可以通過跟蹤對象的引用計數資訊，來進行對象的自動回收。
Redis的持久化
持久化概念
Redis 的資料全部存儲在記憶體中，如果突然當機或者程序意外結束，那麼儲存在記憶體中的資料就會全部丢失，是以必須有一套機制來保證 Redis 的資料不會因為故障而丢失，這種機制就是 Redis 的 持久化機制，它會将記憶體中的資料庫狀态儲存到磁盤中。
Redis的兩種持久化機制
一、RDB持久化
Redis 快照是最簡單的 Redis 持久性模式。Redis持久化既可以手動執行，也可以根據伺服器配置選項定期執行。該功能可以将某個時間點上的資料庫狀态儲存到一個RDB檔案中，也就是俗稱的快照，快照作為包含整個資料集的單個 .rdb 檔案生成。
因為RDB檔案是儲存在磁盤中的，是以即使Redis伺服器程序意外退出，隻要RDB檔案還存在磁盤中，Redis伺服器就可以用該RDB檔案來進行還原資料庫。
RDB檔案的建立和載入
有兩個Redis指令可以用于生成RDB檔案，一個是SAVE，另一個是BGSAVE
- SAVE指令會阻塞Redis伺服器程序，直到RDB檔案建立完成，在伺服器程序阻塞期間，伺服器不會處理任何指令請求
- BGSAVE指令則不會阻塞Redis伺服器程序，該指令會派生出一個子程序，然後由子程序負責RDB檔案的建立，伺服器程序（父程序）繼續處理請求
那就存在一個問題，當在建立RDB檔案期間，用戶端這時候有個請求修改了資料庫的資料時，那麼該如何解決這一情況呢？
這時候
作業系統多程序 COW(Copy On Write) 機制
就發揮作用，當子程序做資料持久化，它不會修改現有的記憶體資料結構，它隻是對資料結構進行周遊讀取，然後序列化寫到磁盤中。父程序不一樣，它必須持續服務用戶端請求，然後對記憶體資料結構進行不間斷的修改。
當子程序持久化時，父程序有修改請求，這時候就使用作業系統的 COW 機制來進行
資料段頁面的分離
。資料段是由很多作業系統的頁面組合而成，當父程序對其中一個頁面的資料進行修改時，會将被共享的頁面複制一份分離出來，然後對這個複制的頁面進行修改。這時子程序相應的頁面是沒有變化的，還是程序産生時那一瞬間的資料。
二、AOF持久化
AOF(Append Only File - 僅追加檔案)
，它的工作方式非常簡單：每次執行修改記憶體中資料集的寫操作時，都會記錄 該操作，也就是儲存追加伺服器所執行的寫指令來記錄資料庫狀态。假設 AOF 日志記錄了自 Redis 執行個體建立以來 所有的修改性指令序列，那麼就可以通過對一個空的 Redis 執行個體順序執行所有的指令，也就是 「重放」，來恢複 Redis 目前執行個體的記憶體資料結構的狀态。
當 Redis 收到用戶端修改指令後，會先進行參數校驗、邏輯處理，如果指令沒問題，就立即将該指令文本存儲到 AOF 日志中，也就是說，先執行指令再将日志存盤。
AOF重寫
因為AOF持久化時通過儲存被執行的寫指令來記錄資料庫狀态的，随着伺服器運作時間的流逝，AOF檔案中的内容會越來越多，檔案會越來越大。為了解決AOF檔案體積膨脹的問題，Redis提供了
檔案重寫
功能，新舊兩個AOF檔案所儲存的資料庫狀态相同，但新的AOF檔案不會包含任何浪費空間的備援指令
AOF重寫過程
實際上，AOF檔案重寫并不是對現有的AOF檔案進行任何讀取，分析或者寫入操作。
AOF重寫其原理就是開辟一個子程序對記憶體中資料庫狀态進行周遊，并轉換成一系列 Redis 的操作指令，序列化到一個新的 AOF 日志檔案中。序列化期間，父程序接收的請求會被放進一個
AOF重寫緩沖區
，待序列化完畢後再将操作期間發生的操作從AOF重寫緩沖區取出，追加到這個新的 AOF 日志檔案中，追加完畢後就立即替代舊的 AOF 日志檔案了，
Redis 4.0 混合持久化
重新開機 Redis 時，我們很少使用 rdb 來恢複記憶體狀态，因為會丢失大量資料。我們通常使用 AOF 日志重放，但是重放 AOF 日志性能相對 rdb 來說要慢很多，這樣在 Redis 執行個體很大的情況下，啟動需要花費很長的時間。
Redis 4.0 為了解決這個問題，帶來了一個新的持久化選項——
混合持久化
。将
rdb 檔案
的内容和
增量的 AOF 日志檔案
存在一起。這裡的 AOF 日志不再是全量的日志，而是自持久化開始到持久化結束的這段時間發生的增量 AOF 日志，通常這部分 AOF 日志很小：
于是在 Redis 重新開機的時候，可以先加載 rdb 的内容，然後再重放增量 AOF 日志就可以完全替代之前的 AOF 全量檔案重放，重新開機效率是以大幅得到提升。
事件
Redis伺服器是一個事件驅動程式，伺服器需要處理以下兩類事件
-
檔案事件
Redis伺服器通過套接字與用戶端（或其他Redis伺服器）進行連接配接，而檔案事件就是伺服器對套接字操作的抽象，伺服器與用戶端的通信會産生相應的檔案事件，而伺服器通過監聽并處理這些事件來完成一系列網絡通信操作
-
時間事件
Redis伺服器中的一些操作需要在給定的事件點執行，而時間事件就是伺服器對這類定時操作的抽象
檔案事件：
Redis基于Reactor模式開發了自己的網絡事件處理器，這個處理器稱為
檔案事件處理器
1、檔案事件處理器采用
I/O多路複用
程式來同時監聽多個套接字，并根據套接字目前執行的任務來為套接字關聯不同的事件處理器
2、當被監聽的套接字準備好執行連接配接應答、讀取、寫入、關閉等操作時，與操作相對應的檔案事件就會産生，這時檔案事件處理器就會調用套接字關聯的事件處理器進行處理這些事件
時間事件
Redis的時間事件可分為兩類
- 定時事件：讓一段程式在指定的時間之後執行一次
- 周期性事件：讓一段程式每隔指定時間就執行一次。
總結：
1、檔案事件和時間事件之間是合作關系，伺服器會輪流處理這兩類事件，并且處理事件的過程中也不會進行搶占
2、時間事件的實際處理時間通常會比設定的到達時間晚一些