一. 數(shù)據(jù)結(jié)構(gòu)

我們知道redis有5種基本類型：string、list、hash、set、zset，我們來看一下他們是怎么實(shí)現(xiàn)的。

1. 簡單動態(tài)字符串（Simple Dynamic String，SDS）

Redis中的可變字符串都是由SDS實(shí)現(xiàn)，比如鍵值對的鍵和值，list的鍵和list中的字符串等...。

SDS結(jié)構(gòu)

可以看到它由三部分組成：

• free（表示空閑字節(jié)數(shù)）
• len（表示字符串長度）
• buf（指向字符數(shù)組，存在占位符兼容C語言字符串，但它對用戶、free、len不可見；并且buf中可能包含多余的空字節(jié)）

SDS的內(nèi)存優(yōu)化策略：
（1）空間預(yù)分配

• SDS只在free空間不夠時，才進(jìn)行擴(kuò)容
• 擴(kuò)容的SDS的長度小于1M時，分配的空間時len的2倍，如“redis”，會分配11個字節(jié)的buf（包含占位符）；
• SDS的長度大于1M時，每次多分配1M。

（2）惰性空間釋放
SDS字符串變短時，并不馬上縮短buf長度，而是通過free字段暫時保存著部分字節(jié)。

SDS的優(yōu)點(diǎn)如下：

• 獲取長度的復(fù)雜度為O(1)，適合于Redis高性能的場景
• 通過free字段，我們可以杜絕緩沖區(qū)溢出
• 減少字符串修改帶來的內(nèi)存重分配次數(shù)
• 可以存儲二進(jìn)制信息
• 兼容部分C字符串函數(shù)

2.鏈表

（1）在Redis中，鏈表應(yīng)用于列表鍵、發(fā)布與訂閱、慢查詢、監(jiān)視器。
（2）redis的list，是雙向鏈表，且包含鏈表長度等信息。

3.字典

（1）在Redis中，字典使用時非常廣泛的，Redis數(shù)據(jù)庫的底層就是使用字典實(shí)現(xiàn)；字典也是hash、set的底層實(shí)現(xiàn)之一。（redis有0-15，16個數(shù)據(jù)庫，默認(rèn)連接0數(shù)據(jù)庫，可以通過select 2 切換數(shù)據(jù)庫）
（2）在Redis中，字典中哈希表的實(shí)現(xiàn)和JDK中HashMap的實(shí)現(xiàn)類似，數(shù)組用于保存鍵值對節(jié)點(diǎn)，當(dāng)發(fā)生沖突時，采用鏈表法解決沖突。
（3）字典中包含兩個哈希表ht0、ht1，一個多余的哈希表用于rehash。
（4）漸進(jìn)式rehash，每次更新操作，都會對其所在的id位置進(jìn)行復(fù)制到備份節(jié)點(diǎn)。（防止哈希表過大，復(fù)制影響性能）

4.跳躍表

跳躍表的查詢效率可以和平衡樹媲美，并且是實(shí)現(xiàn)更簡單，所以不少程序使用跳躍表代替平衡樹，它支持平均O(logN)，最壞O(N)的復(fù)雜度。
（1）Redis采用跳躍表作為有序集合（zset）的底層實(shí)現(xiàn)之一（當(dāng)zset中元素較多，或者成員是比較長的字符串的時候）；
（2）跳躍表的實(shí)現(xiàn)：跳躍表由若干個跳躍表節(jié)點(diǎn)組成。

skiplist

5.整數(shù)集合

（1）整數(shù)集合(intset)是集合鍵的底層實(shí)現(xiàn)之一，當(dāng)一個集合只包含整數(shù)值，且元素樹木不多時，Redis就會采用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)。
（2）intset由一個int變量表示編碼類型，一個int8數(shù)組表示存儲的數(shù)據(jù)，實(shí)際存儲的類型由編碼決定，還有一個表示長度的int變量

intset

（3）intset只支持編碼的升級，不支持降級。

6.壓縮列表

（1）壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一；列表鍵或哈希鍵只包含少量元素時，會使用壓縮列表；
（2）壓縮列表的每個節(jié)點(diǎn)氛圍三部分：前一節(jié)點(diǎn)長度、編碼、content；
通過前一節(jié)點(diǎn)長度我們可以從任意位置遍歷列表（可能是1字節(jié)，可能是5字節(jié)，比較trick的技巧），編碼由編碼前兩位決定編碼長度，content記錄內(nèi)容；
（3）連鎖更新，刪除或新增節(jié)點(diǎn)，導(dǎo)致list中的元素長度連續(xù)變化，造成連鎖更新；不過連鎖更新的性能雖然比較差，但是出現(xiàn)的幾率是很小的。

7.對象

Redis沒有采用底層的數(shù)據(jù)結(jié)構(gòu)直接表示數(shù)據(jù)類型，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)造了一個對象系統(tǒng)，這樣做的好處有：

• 采用對象封裝，方便編寫代碼，方便使用；
• 封裝為對象，可以優(yōu)化其在不同場景下的使用效率；
• 實(shí)現(xiàn)了基于引用計(jì)數(shù)的內(nèi)存回收機(jī)制；
• 可以基于引用計(jì)數(shù)實(shí)現(xiàn)對象共享機(jī)制；
• 對象包含訪問時間，當(dāng)內(nèi)存超過maxmemory時，可以優(yōu)先剔除未訪問時間較長的鍵。

Redis中的對象都是由一個RedisObject的數(shù)據(jù)結(jié)構(gòu)表示，與保存數(shù)據(jù)有關(guān)的是type、encoding、*ptr三個屬性，分別表示類型、編碼、實(shí)際數(shù)據(jù)的指針。

RedisObject

（1）類型
Redis數(shù)據(jù)庫保存的是鍵值對，鍵是“字符串對象”，而值可能是“字符串對象”，“列表對象”，“哈希對象”，“集合對象”，“有序集合對象”。
type命令查看的實(shí)際是值的類型。
（2）編碼
*ptr指向的數(shù)據(jù)所采用的數(shù)據(jù)結(jié)構(gòu)由“編碼”決定，每個Redis的數(shù)據(jù)對象都有多種編碼方式。
編碼為Redis提供了在性能和存儲空間之前平衡的靈活性，在不同的場景下，可以使用不同的編碼，以適應(yīng)當(dāng)前的場景。

1.字符串對象

字符串對象有int、raw、embstr三種編碼。
一個比較特殊的是embstr和raw，他們都是SDS類型，但不同的是raw分兩次創(chuàng)建redisObject和sdshdr結(jié)構(gòu)，embstr一次分配內(nèi)存創(chuàng)建，這樣分配、釋放內(nèi)存更快，并且更容易利用緩存；另外，embstr是只讀的。

2.列表對象

列表對象有ziplist、linkedlist兩種編碼。
滿足2個條件使用ziplist，不滿足則使用linkedlist：
（1）列表對象保存的所有字符串元素小于64字節(jié)；
（2）列表元素?cái)?shù)目小于512個；

3.哈希對象

列表對象有ziplist、hashtable兩種編碼。
使用ziplist存儲鍵值對時，鍵先入隊(duì)，值再入隊(duì)。
滿足2個條件使用ziplist，不滿足則使用hashtable：
（1）哈希表中保存的所有字符串元素小于64字節(jié)；
（2）哈希表中元素?cái)?shù)目小于512個；

4.集合對象

集合對象的編碼可以時intset或者h(yuǎn)ashtable。
滿足2個條件使用intset，不滿足則使用hashtable：
（1）集合中保存的元素都是整數(shù)值；
（2）集合中元素?cái)?shù)目小于512個；

5.有序集合對象（zset根據(jù)元素的分值進(jìn)行排序）

有序集合的編碼可以是ziplist或者skiplist（該編碼方式同時存在skiplist和hashtable兩種數(shù)據(jù)結(jié)構(gòu)）

滿足2個條件使用ziplist，不滿足則使用skiplist：
（1）有序集合中保存的所有元素成員小于64字節(jié)；
（2）有序集合中元素?cái)?shù)目小于128個；

skiplist同時存在skiplist和hashtable兩種編碼，skiplist用于對有序集合進(jìn)行范圍操作，hashtable用于查找給定成員的分值。skiplist和hashtable共享相同元素的成員和分值，不浪費(fèi)額外的內(nèi)存。
同時使用這兩種編碼是為了兼顧隨機(jī)查詢和范圍查詢。

類型檢查與命令多態(tài)

類型由值對象的type決定，多態(tài)選擇由值對象的編碼類型決定。

llen命令執(zhí)行過程

內(nèi)存回收

redisObject內(nèi)部有一個參數(shù)refcount，記錄該對象的引用數(shù)目。
引用計(jì)數(shù)為0時，對象所占內(nèi)存會被回收。
object refcount B 可以得到對象的引用數(shù)目。

對象共享

redisObject可以通過refcount數(shù)字維護(hù)對象的共享。
redisObject會共享0-9999的字符串對象。

對象的空轉(zhuǎn)時長

redisObject還有一個參數(shù)——lru，用來記錄對象最后一次被訪問的時間。
object idletime B可以得到對象的空轉(zhuǎn)時長。

二. 單機(jī)數(shù)據(jù)庫實(shí)現(xiàn)

1.數(shù)據(jù)庫

1.Redis數(shù)據(jù)庫概述

Redis數(shù)據(jù)庫由redisServer數(shù)據(jù)結(jié)構(gòu)內(nèi)的redisDb數(shù)組保存。
Redis默認(rèn)有16個數(shù)據(jù)庫，可以通過select 0，... ，select 15來選擇，默認(rèn)連接的是數(shù)據(jù)庫0。

2.Redis數(shù)據(jù)庫的結(jié)構(gòu)

• Redis是一個鍵值對數(shù)據(jù)庫，redisDb結(jié)構(gòu)中實(shí)際是用一個字典dict存儲所有的鍵值對，也就是我們平時使用的鍵值對。
• redisDb結(jié)構(gòu)中expires字典保存了數(shù)據(jù)庫中所有鍵的過期時間。
• 過期鍵刪除策略：
  三種可能的策略：
  （1）定時刪除：
  創(chuàng)建鍵的時候，創(chuàng)建定時器，到時間刪除這個鍵，因?yàn)橄腃PU（需要用到redis的時間事件機(jī)制，復(fù)雜度O(n)）
  （2）惰性刪除：
  訪問這個鍵的時候才看它的過期時間，過期了才刪除，節(jié)省CPU，但是可能會占用大量內(nèi)存，造成內(nèi)存泄漏。
  （3）定期刪除：
  每隔一段時間，執(zhí)行一次刪除過期鍵的操作，并通過限制刪除操作的時長和頻率減少對CPU的影響。
  Redis結(jié)合使用“惰性刪除”和“定期刪除”兩種策略。
  其中定期刪除，會在規(guī)定時間內(nèi)，分多次遍歷服務(wù)器中的各個數(shù)據(jù)庫，隨機(jī)檢查一些鍵的過期時間，并刪除其中的過期鍵。

持久化中，刪除鍵的處理：
RDB不會保存過期的鍵；由RDB或AOF恢復(fù)數(shù)據(jù)的時候，也不會寫入過期的鍵；一個鍵被刪除后，會向AOF加DEL命令。
從服務(wù)器發(fā)現(xiàn)鍵過期也不會刪除它，而是等待主服務(wù)器的DEL命令。

2.持久化

1.RDB持久化（Redis DataBase）

（1）RDB文件的創(chuàng)建與載入
Redis中有SAVE和BGSAVE兩個命令可以生成RDB快照，其中SAVE使用當(dāng)前進(jìn)程會阻塞其他Redis命令，而BGSAVE會新起一個子進(jìn)程。同時他們之間是互斥的。
Redis啟動時，會檢測RDB文件是否存在，存在的話就自動載入。
（2）間隔保存
Redis可以設(shè)置save參數(shù)，定制規(guī)則，定期的對Redis進(jìn)行BGSAVE。（一個周期性操作）
（3）RDB存儲的是實(shí)際數(shù)據(jù)壓縮后的結(jié)果

RDB文件存儲結(jié)構(gòu)

2.AOF持久化（Append Only File）

（1）AOF存儲的是客戶端發(fā)來的命令；
（2）AOF時機(jī)
Redis就是一個事件循環(huán)，每個循環(huán)中，先處理文件事件，再處理時間事件，在結(jié)束循環(huán)之前，會調(diào)用flushAppendOnlyFile函數(shù)，考慮是否將aof_buf中的內(nèi)容寫入和保存到AOF文件里。
關(guān)于flushAppendOnlyFile的行為，有三種方式：

• always：每次都進(jìn)行同步
• everysec：每秒進(jìn)行同步（默認(rèn)）

• no：何時同步由操作系統(tǒng)決定

  
  
  Redis事件循環(huán)
  
  

  （3）AOF文件的載入
  RedisServer只能接收客戶端的命令，所以，載入AOF文件需要建立一個偽客戶端與Server通信。
  （4）AOF重寫
  隨著執(zhí)行的命令越來越多，AOF日志會膨脹，BGREWRITE命令能夠重寫AOF日志，即新的日志與原日志執(zhí)行結(jié)果相同，但所占空間更?。▽?shí)際上后臺創(chuàng)建一個子進(jìn)程，直接讀數(shù)據(jù)，變?yōu)槊睿?/p>

3.事件

Redis服務(wù)器是一個事件驅(qū)動程序，它包含兩類事件：文件事件、時間事件。
文件事件：Redis服務(wù)器與客戶端（以及其他Redis服務(wù)器）通信所產(chǎn)生的事件；
時間事件：Redis的一些操作需要在給定事件執(zhí)行（比如serverCon），即對定時操作的抽象。

1. 文件事件

Redis文件事件處理器基于Reactor模式使用IO多路復(fù)用技術(shù)，單線程監(jiān)聽多個套接字；當(dāng)發(fā)生網(wǎng)絡(luò)事件時，根據(jù)事件類型，選擇合適的文件事件處理器，處理該網(wǎng)絡(luò)事件；
（1）“單線程”和“IO多路復(fù)用”保證了該通信模型的高性能；
（2）Reactor模式保證了單線程設(shè)計(jì)的簡單性和擴(kuò)展性；
（3）不同的事件由不同的處理器進(jìn)行處理。

文件事件處理器

注：
Reactor模式首先是事件驅(qū)動的，有一個或多個并發(fā)輸入源，有一個Service Handler，有多個Request Handlers；這個Service Handler會同步的將輸入的請求（Event）多路復(fù)用的分發(fā)給相應(yīng)的Request Handler。（以往，我認(rèn)為Reactor模型必然是多線程的。）
Reactor模型的優(yōu)勢：
解耦、提升復(fù)用性、模塊化、可移植性、事件驅(qū)動、細(xì)力度的并發(fā)控制等。

2. 時間事件

Redis中時間事件有兩種：周期性時間事件，定時事件事件。
Redis目前只使用“周期性時間事件”，在Redis中就是serverCon函數(shù)。

實(shí)現(xiàn)：
Redis將所有的時間事件都放在一個無序鏈表上，每次遍歷整個鏈表，執(zhí)行所有到期的事件對應(yīng)的處理器（實(shí)際上Redis只有serverCon一個事件，無序鏈表退化為指針，不影響性能）。

serverCon的實(shí)例：

• 更新服務(wù)器各類統(tǒng)計(jì)信息
• 清理數(shù)據(jù)庫內(nèi)過期鍵值對
• 關(guān)閉、清理失效的連接
• 嘗試進(jìn)行AOF或RDB持久化
• 主從服務(wù)器之間的同步

3. 事件的調(diào)度與執(zhí)行

當(dāng)服務(wù)器未關(guān)閉時，循環(huán)執(zhí)行如下步驟：

• 限時等待文件事件到達(dá)
• 處理到達(dá)的文件事件

• 處理到達(dá)的時間事件（所以時間事件可能稍有延遲）

  
  
  文件事件和時間事件調(diào)度流程

4.客戶端與服務(wù)器

三. 集群實(shí)現(xiàn)

1.復(fù)制

Redis可以使用SLAVEOF命令或者設(shè)置slaveof選項(xiàng)，讓一個服務(wù)器去復(fù)制（replicate）另一個Redis服務(wù)器。

Redis 2.8以前的實(shí)現(xiàn)

Redis主從同步分為兩個步驟：
（1）同步（SYNC）
從服務(wù)器向主服務(wù)器發(fā)送SYNC命令，主服務(wù)器通過BGSAVE生成一個RDB快照，發(fā)送給從服務(wù)器，從服務(wù)器從RDB快照中恢復(fù)數(shù)據(jù)。
（2）命令傳播
同步完畢后， 主服務(wù)器會把新執(zhí)行的寫操作發(fā)送給從服務(wù)器，以保持二者的一致狀態(tài)。
實(shí)際上，從服務(wù)器相當(dāng)于主服務(wù)器的客戶端。

缺陷：
主從服務(wù)器初次復(fù)制是沒有問題的，但是如果主從服務(wù)斷開連接，從服務(wù)器再次連上時，需要再次獲得主服務(wù)器當(dāng)前的RDB，這就可能導(dǎo)致，只丟失了一小部分?jǐn)?shù)據(jù)，卻耗費(fèi)大量資源重新復(fù)制。

Redis 2.8及以后的實(shí)現(xiàn)

Redis2.8用PSYNC代替了SYNC，PSYNC會根據(jù)情況選擇“全量同步”或者“部分同步”。
具體實(shí)現(xiàn)：在server端設(shè)置固定大小的緩沖區(qū)，并且每條語句在主服務(wù)器端都有對應(yīng)的偏移量，從服務(wù)器端也記錄當(dāng)前的偏移量；重連時，若偏移量在緩沖區(qū)內(nèi)，則進(jìn)行“部分同步”，也就是把緩沖區(qū)內(nèi)的更新語句發(fā)給從服務(wù)器；另外還要記錄從服務(wù)器的id。（復(fù)制偏移量、復(fù)制積壓緩沖區(qū)、從服務(wù)ID）

2.Sentinel

哨兵是Redis的高可用性解決方案，由一個或多個Sentinel組成的哨兵系統(tǒng)可以見識任意多個主服務(wù)器以及其下的從服務(wù)器；當(dāng)主服務(wù)器下線時，會將其下的某個從服務(wù)器代替其為主服務(wù)器。（故障自動遷移）

• Sentinel是一個運(yùn)行在特殊模式下的Redis服務(wù)器，只是啟動時的命令不同，并且在啟動時指定了主服務(wù)器的地址端口。

• Sentinel向主服務(wù)器發(fā)送INFO命令來獲取從服務(wù)器信息，Sentinel每十秒向主服務(wù)器和從服務(wù)器發(fā)送INFO命令（命令連接）；

• Sentinel還會向主從服務(wù)器的指定頻道發(fā)送信息，再從訂閱這些主從服務(wù)器該頻道上的信息，以此來獲得其他Sentinel的信息（遇到本Sentinel的消息會丟棄）；維護(hù)主服務(wù)器到Sentinel列表的映射（用于后續(xù)的主管下線和客觀下線）。

• 主管下線和客觀下線。
  （1）主管下線：
  Sentinel會每秒向其他服務(wù)器（Sentinel、Master、Slave）發(fā)送Ping消息，當(dāng)超過一定時間無響應(yīng)，會判斷該服務(wù)主管下線（各Sentinel時間期限配置可能不同）
  （2）客觀下線
  Sentinel發(fā)現(xiàn)某服務(wù)下線，則通過向其他Sentinel發(fā)送查詢命令，確認(rèn)該服務(wù)是否下線，超過指定數(shù)目確認(rèn)后，認(rèn)為該服務(wù)客觀下線。（概數(shù)目可配置）。
  （Sentinel的三個定時任務(wù)：INFO 、發(fā)送指定頻道消息、Ping）

• 領(lǐng)頭Sentinel選擇
  實(shí)際上是Raft算法的實(shí)現(xiàn)。

• 故障自動轉(zhuǎn)移
  （1）選取從服務(wù)器為主服務(wù)器，根據(jù)最近應(yīng)答時間、復(fù)制偏移量、優(yōu)先級、默認(rèn)排序等規(guī)則選取
  （2）設(shè)置其他從服務(wù)器
  （3）設(shè)置重新上線的主服務(wù)器

3.集群

• Redis啟動后，添加其他節(jié)點(diǎn)進(jìn)入集群；
• Redis集群采用哈希槽分配數(shù)據(jù)到各個節(jié)點(diǎn)，總共16384個哈希槽；
• Redis接收到一個命令，會查看這個key是否在自己的哈希槽內(nèi)，在就返回，不在就返回一個Moved響應(yīng)，讓客戶端到合適的節(jié)點(diǎn)取數(shù)據(jù)；
• 集群中主節(jié)點(diǎn)下線后，從節(jié)點(diǎn)能夠升級為主節(jié)點(diǎn)，代替主節(jié)點(diǎn)之前的作用（也是Raft協(xié)議實(shí)現(xiàn)）。

至此，我們看到了Redis使用的四種架構(gòu)：Redis單機(jī)、Redis主從、Redis Sentinel、Redis集群。

四. 其他功能的實(shí)現(xiàn)

1. 發(fā)布訂閱功能

可以在Redis發(fā)布訂閱“頻道”，也可以訂閱“模式”（頻道是一個字符串鍵，模式則是一個正則匹配表達(dá)式，用來匹配符合條件的頻道）。下面來看下具體的實(shí)現(xiàn)：
（1）訂閱頻道
SUBSCRIBE命令可以訂閱一個或多個頻道，UNSUBSCRIBE可以退訂一個或多個頻道；具體的實(shí)現(xiàn)是，在pubsub_channels字典上查看該頻道是否存在，若不存在則在插入key為頻道名和value為空鏈表的元素，并在鏈表上加入該客戶端信息；若存在則直接找到對應(yīng)的鏈表加入客戶端信息（退訂相反操作）。
（2）訂閱模式
PSUBSCRIBE訂閱模式，PUNSUBSCRIBE退訂模式。
Redis中存在pubsub_patterns的鏈表用于保存模式，鏈表中每個元素存儲了模式以及該模式對應(yīng)的客戶端鏈表。
（3）發(fā)送消息
Publish 發(fā)送消息，會將對應(yīng)的頻道以及匹配到的模式，鏈表上的客戶端得到，然后向他們發(fā)送該消息。（會遍歷模式鏈表）
（4）查看訂閱信息
通過PUBSUB命令可以查看頻道與模式的訂閱信息。

2. 事務(wù)功能

（1）Redis事務(wù)

    MULTI開啟事務(wù)
    EXEC執(zhí)行事務(wù)
    DISCARD放棄事務(wù)
    WATCH實(shí)現(xiàn)樂觀鎖，當(dāng)被WATCH的值改變事務(wù)提交失敗

（2）Redis事務(wù)的實(shí)現(xiàn)
如下圖，當(dāng)服務(wù)端的Client對象處于事務(wù)狀態(tài)時，會特殊處理上述四個命令，遇到其他命令則先入隊(duì)列，而不提交。

Redis事務(wù)的實(shí)現(xiàn)

（3）Redis事務(wù)總是具有ACI特性，當(dāng)運(yùn)行在AOF模式下，且appendfsync為always時，也具有D特性。

3. 慢查詢?nèi)罩?/h2>

SLOWLOG GET 可以查看Redis的慢查詢?nèi)罩荆ㄦ湵韺?shí)現(xiàn)）。
可以設(shè)置時間閾值、以及最多保存的日志條數(shù)。

4. Lua腳本

Redis2.6引入了對Lua腳本的支持，redis客戶端可以執(zhí)行Lua腳本，原子的執(zhí)行任務(wù)。