Redis 核心篇：唯快不破的秘密
“天下武功，無堅不摧，唯快不破！
”
學習一個技術，通常只接觸了零散的技術點，沒有在腦海里建立一個完整的知識框架和架構體系，沒有系統(tǒng)觀。這樣會很吃力，而且會出現(xiàn)一看好像自己會，過后就忘記，一臉懵逼。
跟著「碼哥字節(jié)」一起吃透 Redis，深層次的掌握 Redis 核心原理以及實戰(zhàn)技巧。一起搭建一套完整的知識框架，學會全局觀去整理整個知識體系。
系統(tǒng)觀其實是至關重要的，從某種程度上說，在解決問題時，擁有了系統(tǒng)觀，就意味著你能有依據(jù)、有章法地定位和解決問題。
Redis 全景圖
全景圖可以圍繞兩個維度展開，分別是：
應用維度：緩存使用、集群運用、數(shù)據(jù)結構的巧妙使用
系統(tǒng)維度：可以歸類為三高
高性能：線程模型、網(wǎng)絡 IO 模型、數(shù)據(jù)結構、持久化機制； 高可用：主從復制、哨兵集群、Cluster 分片集群； 高拓展：負載均衡
Redis 系列篇章圍繞如下思維導圖展開，這次從 《Redis 唯快不破的秘密》一起探索 Redis 的核心知識點。
唯快不破的秘密
65 哥前段時間去面試 996 大廠，被問到「Redis 為什么快？」
“65 哥：額，因為它是基于內存實現(xiàn)和單線程模型
”
面試官：還有呢？
“65 哥：沒了呀。
”
很多人僅僅只是知道基于內存實現(xiàn)，其他核心的原因模凌兩可。今日跟著「碼哥字節(jié)」一起探索真正快的原因，做一個唯快不破的真男人！
Redis 為了高性能，從各方各面都進行了優(yōu)化，下次小伙伴們面試的時候，面試官問 Redis 性能為什么如此高，可不能傻傻的只說單線程和內存存儲了。
根據(jù)官方數(shù)據(jù)，Redis 的 QPS 可以達到約 100000（每秒請求數(shù)），有興趣的可以參考官方的基準程序測試《How fast is Redis？》，地址：https://redis.io/topics/benchmarks
橫軸是連接數(shù)，縱軸是 QPS。此時，這張圖反映了一個數(shù)量級，希望大家在面試的時候可以正確的描述出來，不要問你的時候，你回答的數(shù)量級相差甚遠！
完全基于內存實現(xiàn)
“65 哥：這個我知道，Redis 是基于內存的數(shù)據(jù)庫，跟磁盤數(shù)據(jù)庫相比，完全吊打磁盤的速度，就像段譽的凌波微步。對于磁盤數(shù)據(jù)庫來說，首先要將數(shù)據(jù)通過 IO 操作讀取到內存里。
”
沒錯，不論讀寫操作都是在內存上完成的，我們分別對比下內存操作與磁盤操作的差異。
磁盤調用棧圖
內存操作
內存直接由 CPU 控制，也就是 CPU 內部集成的內存控制器，所以說內存是直接與 CPU 對接，享受與 CPU 通信的最優(yōu)帶寬。
Redis 將數(shù)據(jù)存儲在內存中，讀寫操作不會因為磁盤的 IO 速度限制，所以速度飛一般的感覺！
最后以一張圖量化系統(tǒng)的各種延時時間（部分數(shù)據(jù)引用 Brendan Gregg）
高效的數(shù)據(jù)結構
“65 哥：學習 MySQL 的時候我知道為了提高檢索速度使用了 B+ Tree 數(shù)據(jù)結構，所以 Redis 速度快應該也跟數(shù)據(jù)結構有關。
”
回答正確，這里所說的數(shù)據(jù)結構并不是 Redis 提供給我們使用的 5 種數(shù)據(jù)類型：String、List、Hash、Set、SortedSet。
在 Redis 中，常用的 5 種數(shù)據(jù)類型和應用場景如下：
String： 緩存、計數(shù)器、分布式鎖等。 List： 鏈表、隊列、微博關注人時間軸列表等。 Hash： 用戶信息、Hash 表等。 Set： 去重、贊、踩、共同好友等。 Zset： 訪問量排行榜、點擊量排行榜等。
上面的應該叫做 Redis 支持的數(shù)據(jù)類型，也就是數(shù)據(jù)的保存形式。「碼哥字節(jié)」要說的是針對這 5 種數(shù)據(jù)類型，底層都運用了哪些高效的數(shù)據(jù)結構來支持。
“65 哥：為啥搞這么多數(shù)據(jù)結構呢？
”
當然是為了追求速度，不同數(shù)據(jù)類型使用不同的數(shù)據(jù)結構速度才得以提升。每種數(shù)據(jù)類型都有一種或者多種數(shù)據(jù)結構來支撐，底層數(shù)據(jù)結構有 6 種。
Redis hash 字典
Redis 整體就是一個 哈希表來保存所有的鍵值對，無論數(shù)據(jù)類型是 5 種的任意一種。哈希表，本質就是一個數(shù)組，每個元素被叫做哈希桶，不管什么數(shù)據(jù)類型，每個桶里面的 entry 保存著實際具體值的指針。
整個數(shù)據(jù)庫就是一個全局哈希表，而哈希表的時間復雜度是 O(1)，只需要計算每個鍵的哈希值，便知道對應的哈希桶位置，定位桶里面的 entry 找到對應數(shù)據(jù)，這個也是 Redis 快的原因之一。
那 Hash 沖突怎么辦？
當寫入 Redis 的數(shù)據(jù)越來越多的時候，哈希沖突不可避免，會出現(xiàn)不同的 key 計算出一樣的哈希值。
Redis 通過鏈式哈希解決沖突：也就是同一個 桶里面的元素使用鏈表保存。但是當鏈表過長就會導致查找性能變差可能，所以 Redis 為了追求快，使用了兩個全局哈希表。用于 rehash 操作，增加現(xiàn)有的哈希桶數(shù)量，減少哈希沖突。
開始默認使用 hash 表 1 保存鍵值對數(shù)據(jù)，哈希表 2 此刻沒有分配空間。當數(shù)據(jù)越來多觸發(fā) rehash 操作，則執(zhí)行以下操作：
給 hash 表 2 分配更大的空間； 將 hash 表 1 的數(shù)據(jù)重新映射拷貝到 hash 表 2 中； 釋放 hash 表 1 的空間。
值得注意的是，將 hash 表 1 的數(shù)據(jù)重新映射到 hash 表 2 的過程中并不是一次性的，這樣會造成 Redis 阻塞，無法提供服務。
而是采用了漸進式 rehash，每次處理客戶端請求的時候，先從 hash 表 1 中第一個索引開始，將這個位置的 所有數(shù)據(jù)拷貝到 hash 表 2 中，就這樣將 rehash 分散到多次請求過程中，避免耗時阻塞。
SDS 簡單動態(tài)字符
“65 哥：Redis 是用 C 語言實現(xiàn)的，為啥還重新搞一個 SDS 動態(tài)字符串呢？
”
字符串結構使用最廣泛，通常我們用于緩存登陸后的用戶信息，key = userId，value = 用戶信息 JSON 序列化成字符串。
C 語言中字符串的獲取 「MageByte」的長度，要從頭開始遍歷，直到 「\0」為止，Redis 作為唯快不破的男人是不能忍受的。
C 語言字符串結構與 SDS 字符串結構對比圖如下所示：
SDS 與 C 字符串區(qū)別
O(1) 時間復雜度獲取字符串長度
C 語言字符串布吉路長度信息，需要遍歷整個字符串時間復雜度為 O(n)，C 字符串遍歷時遇到 '\0' 時結束。
SDS 中 len 保存這字符串的長度，O(1) 時間復雜度。
空間預分配
SDS 被修改后，程序不僅會為 SDS 分配所需要的必須空間，還會分配額外的未使用空間。
分配規(guī)則如下：如果對 SDS 修改后，len 的長度小于 1M，那么程序將分配和 len 相同長度的未使用空間。舉個例子，如果 len=10，重新分配后，buf 的實際長度會變?yōu)?10(已使用空間)+10(額外空間)+1(空字符)=21。如果對 SDS 修改后 len 長度大于 1M，那么程序將分配 1M 的未使用空間。
惰性空間釋放
當對 SDS 進行縮短操作時，程序并不會回收多余的內存空間，而是使用 free 字段將這些字節(jié)數(shù)量記錄下來不釋放，后面如果需要 append 操作，則直接使用 free 中未使用的空間，減少了內存的分配。
二進制安全
在 Redis 中不僅可以存儲 String 類型的數(shù)據(jù)，也可能存儲一些二進制數(shù)據(jù)。
二進制數(shù)據(jù)并不是規(guī)則的字符串格式，其中會包含一些特殊的字符如 '\0'，在 C 中遇到 '\0' 則表示字符串的結束，但在 SDS 中，標志字符串結束的是 len 屬性。
zipList 壓縮列表
壓縮列表是 List 、hash、 sorted Set 三種數(shù)據(jù)類型底層實現(xiàn)之一。
當一個列表只有少量數(shù)據(jù)的時候，并且每個列表項要么就是小整數(shù)值，要么就是長度比較短的字符串，那么 Redis 就會使用壓縮列表來做列表鍵的底層實現(xiàn)。
ziplist 是由一系列特殊編碼的連續(xù)內存塊組成的順序型的數(shù)據(jù)結構，ziplist 中可以包含多個 entry 節(jié)點，每個節(jié)點可以存放整數(shù)或者字符串。
ziplist 在表頭有三個字段 zlbytes、zltail 和 zllen，分別表示列表占用字節(jié)數(shù)、列表尾的偏移量和列表中的 entry 個數(shù)；壓縮列表在表尾還有一個 zlend，表示列表結束。
struct ziplist<T> {
int32 zlbytes; // 整個壓縮列表占用字節(jié)數(shù)
int32 zltail_offset; // 最后一個元素距離壓縮列表起始位置的偏移量，用于快速定位到最后一個節(jié)點
int16 zllength; // 元素個數(shù)
T[] entries; // 元素內容列表，挨個挨個緊湊存儲
int8 zlend; // 標志壓縮列表的結束，值恒為 0xFF
}
如果我們要查找定位第一個元素和最后一個元素，可以通過表頭三個字段的長度直接定位，復雜度是 O(1)。而查找其他元素時，就沒有這么高效了，只能逐個查找，此時的復雜度就是 O(N)
雙端列表
Redis List 數(shù)據(jù)類型通常被用于隊列、微博關注人時間軸列表等場景。不管是先進先出的隊列，還是先進后出的棧，雙端列表都很好的支持這些特性。
Redis 的鏈表實現(xiàn)的特性可以總結如下：
雙端：鏈表節(jié)點帶有 prev 和 next 指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復雜度都是 O（1）。 無環(huán)：表頭節(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL，對鏈表的訪問以 NULL 為終點。 帶表頭指針和表尾指針：通過 list 結構的 head 指針和 tail 指針，程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復雜度為 O（1）。 帶鏈表長度計數(shù)器：程序使用 list 結構的 len 屬性來對 list 持有的鏈表節(jié)點進行計數(shù)，程序獲取鏈表中節(jié)點數(shù)量的復雜度為 O（1）。 多態(tài)：鏈表節(jié)點使用 void* 指針來保存節(jié)點值，并且可以通過 list 結構的 dup、free、match 三個屬性為節(jié)點值設置類型特定函數(shù)，所以鏈表可以用于保存各種不同類型的值。
后續(xù)版本對列表數(shù)據(jù)結構進行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。
quicklist 是 ziplist 和 linkedlist 的混合體，它將 linkedlist 按段切分，每一段使用 ziplist 來緊湊存儲，多個 ziplist 之間使用雙向指針串接起來。
這也是為何 Redis 快的原因，不放過任何一個可以提升性能的細節(jié)。
skipList 跳躍表
sorted set 類型的排序功能便是通過「跳躍列表」數(shù)據(jù)結構來實現(xiàn)。
跳躍表（skiplist）是一種有序數(shù)據(jù)結構，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速訪問節(jié)點的目的。
跳躍表支持平均 O（logN）、最壞 O（N）復雜度的節(jié)點查找，還可以通過順序性操作來批量處理節(jié)點。
跳表在鏈表的基礎上，增加了多層級索引，通過索引位置的幾個跳轉，實現(xiàn)數(shù)據(jù)的快速定位，如下圖所示：
當需要查找 40 這個元素需要經(jīng)歷 三次查找。
整數(shù)數(shù)組（intset）
當一個集合只包含整數(shù)值元素，并且這個集合的元素數(shù)量不多時，Redis 就會使用整數(shù)集合作為集合鍵的底層實現(xiàn)。結構如下：
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素數(shù)量
uint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}intset;
contents 數(shù)組是整數(shù)集合的底層實現(xiàn)：整數(shù)集合的每個元素都是 contents 數(shù)組的一個數(shù)組項（item），各個項在數(shù)組中按值的大小從小到大有序地排列，并且數(shù)組中不包含任何重復項。length 屬性記錄了整數(shù)集合包含的元素數(shù)量，也即是 contents 數(shù)組的長度。
合理的數(shù)據(jù)編碼
Redis 使用對象（redisObject）來表示數(shù)據(jù)庫中的鍵值，當我們在 Redis 中創(chuàng)建一個鍵值對時，至少創(chuàng)建兩個對象，一個對象是用做鍵值對的鍵對象，另一個是鍵值對的值對象。
例如我們執(zhí)行 SET MSG XXX 時，鍵值對的鍵是一個包含了字符串“MSG“的對象，鍵值對的值對象是包含字符串"XXX"的對象。
redisObject
typedef struct redisObject{
//類型
unsigned type:4;
//編碼
unsigned encoding:4;
//指向底層數(shù)據(jù)結構的指針
void *ptr;
//...
}robj;
其中 type 字段記錄了對象的類型，包含字符串對象、列表對象、哈希對象、集合對象、有序集合對象。
對于每一種數(shù)據(jù)類型來說，底層的支持可能是多種數(shù)據(jù)結構，什么時候使用哪種數(shù)據(jù)結構，這就涉及到了編碼轉化的問題。
那我們就來看看，不同的數(shù)據(jù)類型是如何進行編碼轉化的：
String：存儲數(shù)字的話，采用 int 類型的編碼，如果是非數(shù)字的話，采用 raw 編碼；
List：List 對象的編碼可以是 ziplist 或 linkedlist，字符串長度 < 64 字節(jié)且元素個數(shù) < 512 使用 ziplist 編碼，否則轉化為 linkedlist 編碼；
注意：這兩個條件是可以修改的，在 redis.conf 中：
list-max-ziplist-entries 512
list-max-ziplist-value 64
Hash：Hash 對象的編碼可以是 ziplist 或 hashtable。
當 Hash 對象同時滿足以下兩個條件時，Hash 對象采用 ziplist 編碼：
Hash 對象保存的所有鍵值對的鍵和值的字符串長度均小于 64 字節(jié)。 Hash 對象保存的鍵值對數(shù)量小于 512 個。
否則就是 hashtable 編碼。
Set：Set 對象的編碼可以是 intset 或 hashtable，intset 編碼的對象使用整數(shù)集合作為底層實現(xiàn)，把所有元素都保存在一個整數(shù)集合里面。
保存元素為整數(shù)且元素個數(shù)小于一定范圍使用 intset 編碼，任意條件不滿足，則使用 hashtable 編碼；
Zset：Zset 對象的編碼可以是 ziplist 或 zkiplist，當采用 ziplist 編碼存儲時，每個集合元素使用兩個緊挨在一起的壓縮列表來存儲。
Ziplist 壓縮列表第一個節(jié)點存儲元素的成員，第二個節(jié)點存儲元素的分值，并且按分值大小從小到大有序排列。
當 Zset 對象同時滿足一下兩個條件時，采用 ziplist 編碼：
Zset 保存的元素個數(shù)小于 128。 Zset 元素的成員長度都小于 64 字節(jié)。
如果不滿足以上條件的任意一個，ziplist 就會轉化為 zkiplist 編碼。注意：這兩個條件是可以修改的，在 redis.conf 中：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64
單線程模型
“65 哥：為什么 Redis 是單線程的而不用多線程并行執(zhí)行充分利用 CPU 呢？
”
我們要明確的是：Redis 的單線程指的是 Redis 的網(wǎng)絡 IO 以及鍵值對指令讀寫是由一個線程來執(zhí)行的。 對于 Redis 的持久化、集群數(shù)據(jù)同步、異步刪除等都是其他線程執(zhí)行。
至于為啥用單線程，我們先了解多線程有什么缺點。
多線程的弊端
使用多線程，通常可以增加系統(tǒng)吞吐量，充分利用 CPU 資源。
但是，使用多線程后，沒有良好的系統(tǒng)設計，可能會出現(xiàn)如下圖所示的場景，增加了線程數(shù)量，前期吞吐量會增加，再進一步新增線程的時候，系統(tǒng)吞吐量幾乎不再新增，甚至會下降！
在運行每個任務之前，CPU 需要知道任務在何處加載并開始運行。也就是說，系統(tǒng)需要幫助它預先設置 CPU 寄存器和程序計數(shù)器，這稱為 CPU 上下文。
這些保存的上下文存儲在系統(tǒng)內核中，并在重新計劃任務時再次加載。這樣，任務的原始狀態(tài)將不會受到影響，并且該任務將看起來正在連續(xù)運行。
切換上下文時，我們需要完成一系列工作，這是非常消耗資源的操作。
另外，當多線程并行修改共享數(shù)據(jù)的時候，為了保證數(shù)據(jù)正確，需要加鎖機制就會帶來額外的性能開銷，面臨的共享資源的并發(fā)訪問控制問題。
引入多線程開發(fā)，就需要使用同步原語來保護共享資源的并發(fā)讀寫，增加代碼復雜度和調試難度。
單線程又什么好處？
不會因為線程創(chuàng)建導致的性能消耗； 避免上下文切換引起的 CPU 消耗，沒有多線程切換的開銷； 避免了線程之間的競爭問題，比如添加鎖、釋放鎖、死鎖等，不需要考慮各種鎖問題。 代碼更清晰，處理邏輯簡單。
單線程是否沒有充分利用 CPU 資源呢？
官方答案：因為 Redis 是基于內存的操作，CPU 不是 Redis 的瓶頸，Redis 的瓶頸最有可能是機器內存的大小或者網(wǎng)絡帶寬。既然單線程容易實現(xiàn)，而且 CPU 不會成為瓶頸，那就順理成章地采用單線程的方案了。原文地址：https://redis.io/topics/faq。
I/O 多路復用模型
Redis 采用 I/O 多路復用技術，并發(fā)處理連接。采用了 epoll + 自己實現(xiàn)的簡單的事件框架。epoll 中的讀、寫、關閉、連接都轉化成了事件，然后利用 epoll 的多路復用特性，絕不在 IO 上浪費一點時間。
“65 哥：那什么是 I/O 多路復用呢？
”
在解釋 IO 多慮復用之前我們先了解下基本 IO 操作會經(jīng)歷什么。
基本 IO 模型
一個基本的網(wǎng)絡 IO 模型，當處理 get 請求，會經(jīng)歷以下過程：
和客戶端建立建立 accept;從 socket 種讀取請求 recv;解析客戶端發(fā)送的請求 parse;執(zhí)行 get指令；響應客戶端數(shù)據(jù)，也就是 向 socket 寫回數(shù)據(jù)。
其中，bind/listen、accept、recv、parse 和 send 屬于網(wǎng)絡 IO 處理，而 get 屬于鍵值數(shù)據(jù)操作。既然 Redis 是單線程，那么，最基本的一種實現(xiàn)是在一個線程中依次執(zhí)行上面說的這些操作。
關鍵點就是 accept 和 recv 會出現(xiàn)阻塞，當 Redis 監(jiān)聽到一個客戶端有連接請求，但一直未能成功建立起連接時，會阻塞在 accept() 函數(shù)這里，導致其他客戶端無法和 Redis 建立連接。
類似的，當 Redis 通過 recv() 從一個客戶端讀取數(shù)據(jù)時，如果數(shù)據(jù)一直沒有到達，Redis 也會一直阻塞在 recv()。
阻塞的原因由于使用傳統(tǒng)阻塞 IO ，也就是在執(zhí)行 read、accept 、recv 等網(wǎng)絡操作會一直阻塞等待。如下圖所示：
IO 多路復用
多路指的是多個 socket 連接，復用指的是復用一個線程。多路復用主要有三種技術：select，poll，epoll。epoll 是最新的也是目前最好的多路復用技術。
它的基本原理是，內核不是監(jiān)視應用程序本身的連接，而是監(jiān)視應用程序的文件描述符。
當客戶端運行時，它將生成具有不同事件類型的套接字。在服務器端，I / O 多路復用程序（I / O 多路復用模塊）會將消息放入隊列（也就是 下圖的 I/O 多路復用程序的 socket 隊列），然后通過文件事件分派器將其轉發(fā)到不同的事件處理器。
簡單來說：Redis 單線程情況下，內核會一直監(jiān)聽 socket 上的連接請求或者數(shù)據(jù)請求，一旦有請求到達就交給 Redis 線程處理，這就實現(xiàn)了一個 Redis 線程處理多個 IO 流的效果。
select/epoll 提供了基于事件的回調機制，即針對不同事件的發(fā)生，調用相應的事件處理器。所以 Redis 一直在處理事件，提升 Redis 的響應性能。
Redis 線程不會阻塞在某一個特定的監(jiān)聽或已連接套接字上，也就是說，不會阻塞在某一個特定的客戶端請求處理上。正因為此，Redis 可以同時和多個客戶端連接并處理請求，從而提升并發(fā)性。
唯快不破的原理總結
“65 哥：學完之后我終于知道 Redis 為何快的本質原因了，「碼哥」你別說話，我來總結！一會我再點贊和分享這篇文章，讓更多人知道 Redis 快的核心原理。
”
純內存操作，一般都是簡單的存取操作，線程占用的時間很多，時間的花費主要集中在 IO 上，所以讀取速度快。 整個 Redis 就是一個全局 哈希表，他的時間復雜度是 O(1)，而且為了防止哈希沖突導致鏈表過長，Redis 會執(zhí)行 rehash 操作，擴充 哈希桶數(shù)量，減少哈希沖突。并且防止一次性 重新映射數(shù)據(jù)過大導致線程阻塞，采用 漸進式 rehash。巧妙的將一次性拷貝分攤到多次請求過程后總，避免阻塞。 Redis 使用的是非阻塞 IO：IO 多路復用，使用了單線程來輪詢描述符，將數(shù)據(jù)庫的開、關、讀、寫都轉換成了事件，Redis 采用自己實現(xiàn)的事件分離器，效率比較高。 采用單線程模型，保證了每個操作的原子性，也減少了線程的上下文切換和競爭。 Redis 全程使用 hash 結構，讀取速度快，還有一些特殊的數(shù)據(jù)結構，對數(shù)據(jù)存儲進行了優(yōu)化，如壓縮表，對短數(shù)據(jù)進行壓縮存儲，再如，跳表，使用有序的數(shù)據(jù)結構加快讀取的速度。 根據(jù)實際存儲的數(shù)據(jù)類型選擇不同編碼
下一篇「碼哥字節(jié)」將帶來 《Redis 日志篇：無畏宕機快速恢復的殺手锏》，關注我，獲取真正的硬核知識點。
另外技術讀者群也開通了，群里有很多大廠大佬，后臺回復「加群」獲取「碼哥字節(jié)」作者微信，一起成長交流。
以上就是 Redis 唯快不破的秘密詳解，覺得不錯請點贊、分享，「碼哥字節(jié)」感激不盡。
往期推薦