Redis系列：深刻理解高性能Redis的本質
1 背景
分散式系統繞不開的核心之一的就是數據快取，有了快取的支撐，系統的整體吞吐量會有很大的提升。通過使用快取，我們把頻繁查詢的數據由磁碟調度到快取中，保證數據的高效率讀寫。
當然，除了在記憶體內運行還遠遠不夠，我們今天就以具有代表性的快取中間件Redis為例子，分析下，它是如何達到飛起的效率。
2 Redis高效性能分析
Redis之所以能夠提供超高的執行效率，主要從以下幾個維度來實現的：
- 存儲模式：基於記憶體實現，而非磁碟
- 數據結構：基於不同業務場景的高效數據結構
- 動態字元串(REDIS_STRING)：整數(REDIS_ENCODING_INT)、字元串(REDIS_ENCODING_RAW)
- 雙端列表(REDIS_ENCODING_LINKEDLIST)
- 壓縮列表(REDIS_ENCODING_ZIPLIST)
- 跳躍表(REDIS_ENCODING_SKIPLIST)
- 哈希表(REDIS_HASH)
- 整數集合(REDIS_ENCODING_INTSET)
- 執行緒模型： Redis 的網路 IO 以及鍵值對指令讀寫是由單個執行緒來執行的，避免了不必要的contextswitch和競選
- I/O 模型： 基於I/O多路復用模型，非阻塞的I/O模型
- 恰單的數據編碼： 根據實際數據類型，選擇合理的數據編碼
2.1 官網的性能報告
Redis官方站點中，有對Redis性能做了比較詳細的壓測，可以參考官方這一篇 How fast is Redis?，
在較高的配置基準下（比如 8C 16G +），在連接數為0~10000的時候，最高QPS可達到120000。Redis以超過60000個連接為基準，仍然能夠在這些條件下維持50000個q/s，體現了超高的性能。下圖中橫軸是連接數，縱軸是QPS。
下面這張圖為data size 與整體吞吐量之間的趨向關係：
這個大概可以得出一個容量預估，比如你的服務用戶量是多少，預估峰值QPS是多少，集群需要配置多少個實例（雖然實例的多少不能線性計算），可以大致推算出去。
2.2 基於記憶體實現
Redis的讀寫操作都是在記憶體中實現了，相對其他的持久化存儲（如MySQL、File等，數據持久化在磁碟上），性能會高很多。因為在們在操作數據的時候，需要通過 IO 操作先將數據讀取到記憶體里，增加工作成本。
上面那張圖來源於網路，可以看看他的金字塔模型，越往上執行效率越高，價格也就越貴。下面給出每一層的執行耗時對比：
- 暫存器：0.3 ns
- L1高速快取：0.9 ns
- L2高速快取：2.8 ns
- L3高速快取：12.9 ns
- 主存：120 ns
- 本地二級存儲（SSD）：50~150 us
- 遠程二級存儲：30 ms
這樣可能不直觀，我們舉個L1和SSD的對比，如果L1耗時1s的話，SSD中差不多要15~45小時。
因為 CPU 內部集成了記憶體控制器，所以CPU直接控制了記憶體，給予通訊上的最優頻寬。上面的部分數據引用自《性能之巔：洞悉系統、企業與雲計算》。
2.3 適配多元場景的高效數據結構
在 Redis 快取中，常用的主要數據類型有五種，如下：
- 字元串/REDIS_STRING：適用於 快取、計數、共享Session、IP統計、分散式鎖等。
- 列表/REDIS_LIST： 鏈表、消息隊列、棧、有序的對象列表（如朋友圈的點贊順序列表、評論順序列表）。
- 哈希表/REDIS_HASH： 購物車資訊、用戶資訊、Hash類型的(key, field, value)存儲對象等。
- 集合/REDIS_SET：無序的唯一的鍵值結構： 好友、關注、粉絲、感興趣的人集合等。
- 有序集合/REDIS_ZSET：訪問排行榜、點贊排行、粉絲數排行等。
上面這5種Redis 支援的數據類型，能夠滿足不同業務場景下的數據結構需求。而對於這幾類數據類型的區分和支援，目的無非也是為了效率，具體的業務中使用恰當的數據結構才能保證得到應有的效率。
這5種數據類型都有一種或者多種數據結構來支撐，底層數據結構有 7 種。關係如下：
限免我們對這些數據結構一個個的分析。
2.3.1 SDS 簡單動態字元串
Redis使用簡單動態字元串（simple dynamic string，SDS）來表示字元串，Redis中字元串類型包含的數據結構有：整數（R_INT） 、 字元串（R_RAW）。我們以字元串為例子，常規的字元串，如 “Brand”，如果要獲取他的長度，需要從頭開始遍歷，直至遇到 \0 空字元代表結尾,如 C字元串。
C 字元串結構與 SDS 字元串結構 對比圖 參照如下：
- free屬性的值為0，表示這個SDS沒有分配任何未使用空間。
- len屬性的值為5，表示這個SDS保存了一個5位元組長度的字元串。
- buf是一個char類型的數組，存儲真實的字元串，數組的前五個位元組分別保存了’B’、’r’、’a’、’n’、’d’五個字元，而最後一個位元組則保存了空字元’\0’，代表結尾。
注意：SDS遵循C字元串的慣例以空字元結尾，保存空字元的1位元組不計算在SDS的len屬性中。
比起C字元串，SDS具有以下優點：
-
度獲取字元串長度時間複雜度為O(1) 。
C字元串不記錄自身長度，獲取C字元串長度時必須遍歷整個字元串計數得到，複雜度是O(N)
SDS字元串自身記錄維護len長度屬性，獲得SDS字元串長度的複雜度是O(1) -
杜絕緩衝區溢出。
C字元串不記錄長度，由於兩個C字元串在記憶體存儲上緊鄰，在執行字元串拼接strcat時，如果不提前分配足夠空間，很可能發生修改s1的數據溢出到s2所在的空間中（緩衝區溢出）。
SDS杜絕了緩衝區溢出問題，它記錄了長度，當修改SDS字元串之前，API都會檢查SDS的空間是否滿足修改的要求，不滿足API會自動進行空間擴展。 -
空間預分配，減少修改時的記憶體重分配次數
SDS 被修改後，程式不僅會為 SDS 分配所需要的空間，還會分配額外的未使用空間。這樣，Redis可以減少連續執行字元串增長操作所需的記憶體重分配次數。
具體分配未使用空間如下2種方式：
- 如修改後長度len小於1MB，就分配和len屬性相同大小的未使用空間：free=len。
- 如修改後長度len大於等於1MB，就分配1M的未使用空間：free=1MB。
-
惰性空間釋放
惰性空間釋放，縮短操作時：SDS避免了縮短字元串時所需的記憶體重分配操作，並為將來可能有的增長操作提供了優化。當SDS做縮短操作，不會立刻使用記憶體重分配來收回縮短後多出來的位元組，而是保持在free屬性里。將來如果需要 append 操作，則直接使用 free 中未使用的空間，減少了記憶體的分配步驟。
另外，SDS也提供了API手動進行釋放SDS未使用空間，避免惰性釋放策略會造成記憶體浪費。 -
二進位安全
C字元串的字元必須符合某種編碼，除結尾空字元以外，字元串內部不允許有空字元串，存儲有局限性。而在 Redis 中，不僅可以存儲 String 類型的數據，也可能存儲一些二進位數據。
二進位數據並不是規則的字元串格式，其中會包含一些特殊的字元如 ‘\0’。在 C 中遇到 ‘\0’ 則表示字元串的結束，但SDS不是，它是以len長度標識結尾。 -
兼容部分C字元串函數。
SDS雖然是二進位安全的，但還是秉承C字元串以空字元結尾的特性，很多函數與C字元串一致不需要重寫。
2.3.2 zipList 壓縮列表
通過上面的數據結構關係圖，可以看出，壓縮列表是 List 、Hash、 Set 三種數據類型底層實現之一。
當我們的list列表數據量比較少的時候，且存儲的數據輕量的（如小整數值、短字元串）時候， Redis 就會通過壓縮列表來進行底層實現。
ziplist 是由一系列特殊編碼的連續記憶體塊組成的順序型的數據結構，在列表頭有三個欄位 zlbytes、zltail 和 zllen，列表中有多個entry，表尾還有一個 zlend，我們來具體拆解下：
- zlbytes：表示列表佔用位元組數
- zltail：列表尾的偏移量
- zllen：列表尾的偏移量：列表中的 entry 個數
- entry：存儲區，可以包含多個節點，每個節點可以存放整數或者字元串。
- zlend：表示列表結束。
參考程式碼如下：
struct ziplist<T> {
// 列表佔用位元組數
int32 zlbytes;
// 列表尾的偏移量，用於快速定位到最後一個節點
int32 zltail_offset;
// 列表entry元素個數
int16 zllength;
// 元素內容列表
T[] entries;
// 標誌壓縮列表的結束，值恆為 0xFF
int8 zlend;
}
如果查找定位首個元素或最後1個元素，可以通過表頭zlbytes、zltail_offset元素快速獲取，複雜度是 O(1)。但是查找其他元素時，就沒有這麼高效了，只能逐個查找下去，比如 entry n 的複雜度就是 O(N)。
2.3.3 linklist 雙端列表
Redis List 數據類型經常使用在鏈表、消息隊列、棧、有序的對象列表（如朋友圈的點贊順序列表、評論順序列表、關注時間線）等場景，無論是隊列（先進先出），還是棧（先進後出），雙端列表都能很好的支援。
參考程式碼如下：
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 的鏈表實現的特性可以總結如下：
- 雙端：鏈表節點帶有 prev 和 next 指針，獲取某個節點的前一節點和後一節點的複雜度都是 O(1)。
- 無環：表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL，對鏈表的訪問以 NULL 為終點。
- 表頭指針/表尾指針：通過 list 結構的 head 指針和 tail 指針，獲取鏈表的表頭節點和表尾節點的複雜度為 O(1)。
- 鏈表長度計數器：通過 list 結構的 len 屬性來對 list 的鏈表節點進行計數，獲取節點數量的複雜度為O(1)。
- 多態：鏈表節點使用 void* 指針來保存節點值，並通過 list 結構的 dup、free、match 三個屬性為節點值設置類型特定函數，所以鏈表可以用於保存各種不同類型的值。
使用鏈表的附加空間相對太高，因為64bit系統中指針是8個位元組，所以prev和next指針需要佔據16個位元組，且鏈表節點在記憶體中單獨分配，會加劇記憶體的碎片化，影響記憶體管理效率。
考慮到鏈表的以上缺點，Redis後續版本對列表數據結構進行改造，使用quicklist代替了ziplist和linkedlist。 作為ziplist 和 linkedlist 的混合體，它將 linkedlist 按段切分，每一段使用 ziplist 來緊湊存儲，多個 ziplist 之間使用雙向指針串接起來。
這樣，性能就的得到了更大的提升。
2.3.4 Hhash 字典
無論何種類型（string、list、hash、set、zset），Redis都是以一個Hash結構的形式來保存鍵值對的。整體是一個數組，數組中的每個元素都是一個獨立的對象，被稱為哈系桶，比如圖中1 ~ n, 對應的entry保存著實際具體值的指針。
上圖中的全局哈希表，它的時間複雜度是 O(1)，只需要計算每個鍵的哈希值，便知道對應的哈希桶位置，定位桶中的 entry ，並找到對應數據。這個執行效率就很高了。
為了解決可能存在的衝突，採用了鏈式哈希的做法，也就是同一個桶裡面的元素使用鏈表保存。
2.3.5 intset 整數集合
如果你的集合只有整數值元素，並且數量是輕量的，這時候Redis會使用使用整數集合作為Redis集合的底層數據結構。參考如下程式碼：
typedef struct intset{
// 編碼格式
uint32_t encoding;
// 集合中的元素個數
uint32_t length;
// 保存元素數據
int8_t contents[];
} intset;
我們拆解下：
- encoding： 編碼方式
- length： 數組中元素個數，也就是數組的整體長度
- contents[]： 整數集合，集合的每個元素都是數組的一個數組項（item）。具有以下特點：
- 按值的大小增序排列
- 不包含任何重複項
2.3.6 skipList 跳躍表
skiplist（即跳躍表）是一種有序數據結構，所以它也是ZSet數據類型中的一種，通過在每個節點中維持多個指向其他節點的指針，達到快速定位的目標。
跳躍表的平均的節點搜索，平均時間複雜度是 O(logN)、最差時間複雜度是 O(N)，還可以通過順序性操作來批量處理節點。 跳躍表是基於鏈表的改良，在它基礎上，增加了多層級索引，通過索引不斷跳轉，最終定好位到真實的數據項。這個方式是不是讓大家想到b+tree，理念上有點接近，如下圖所示：
可以看出，需要獲取 68 這個元素需要經歷3次查找，需要獲取 97則需要經歷4次查找。
2.4 單執行緒模型
Redis 的單執行緒主要是指Redis的網路IO和鍵值對讀寫是由一個執行緒來完成的，Redis在處理客戶端的請求時包括獲取 (socket 讀)、解析、執行、內容返回 (socket 寫) 等都由一個順序串列的主執行緒處理，這就是所謂的「單執行緒」。這也是Redis對外提供鍵值存儲服務的主要流程。
但Redis的其他功能， 比如持久化、非同步刪除、集群數據同步等等，其實是由額外的執行緒執行的。 可以這麼說，Redis工作執行緒是單執行緒的。但是，整個Redis來說，是多執行緒的。
2.4.1 為何是單執行緒？
那在主流程中使用單執行緒，主要是出於什麼原因呢？
-
整體吞吐量降低
適當的擴增執行緒，是為了有效的利用cpu的性能，讓它跟記憶體達到一個利用的最優值。但頻繁的Redis讀寫，如果沒有對執行緒進行有效管理，不但對系統的吞吐量沒有提升，反而可能導致下降。
-
CPU上下文切換
在運行任務的時候，CPU需要把任務載入到CPU暫存器中進行計算，當切換到其他thread時，需要將當前上下文存儲在系統內核中，以便後續重新執行計算時再次載入。
就像你做專心做一件事時，頻繁切換，頻繁被打斷，這個代價是非常高的。
如圖中，切換上下文時，我們需要完成一系列工作，save context、switch、restore context等，這種操作越頻繁越是耗費資源。 -
共享資源的並發控制問題
引入了程式執行順序的不確定性，帶來了並發讀寫的一系列問題，增加了系統複雜度。同時可能存在執行緒切換、甚至加鎖解鎖、死鎖造成的性能損耗。 -
記憶體才是核心關注點
對於 Redis 框架來說， 主要的性能瓶頸是記憶體或者網路頻寬，而非 CPU。
2.4.2 單執行緒的好處
- 避免執行緒創建過多導致的性能消耗，反而降低整體吞吐能力。
- 避免上下文切換引起的 CPU 額外的開銷。
- 避免了執行緒之間的競爭問題，如加鎖、解鎖、死鎖等，都會造成性能損耗。
- 無需額外考慮多執行緒帶來的程式複雜度，程式碼更清晰，處理邏輯簡單。
2.4.3 單執行緒是否有效利用CPU
官方這麼說
It』s not very frequent that CPU becomes your bottleneck with Redis, as usually Redis is either memory or network bound. For instance, using pipelining Redis running on an average Linux system can deliver even 1 million requests per second, so if your application mainly uses O(N) or O(log(N)) commands, it is hardly going to use too much CPU.
大概意思是，Redis是完全的純記憶體操作，執行速度是非常快的，CPU通常不會是瓶頸，因為大多數請求不會是CPU密集型的。參考
Redis真正的性能瓶頸在網路IO，也就是客戶端和服務端之間的網路傳輸延遲，因此Redis選擇了單執行緒的IO多路復用來實現它的核心網路模型。
2.5 I/O 多路復用模型
服務端網路編程常見的 I/O 模型有四種：同步阻塞IO（Blocking IO）、同步非阻塞IO（Non-blocking IO）、IO多路復用（IO Multiplexing）、非同步IO（Asynchronous IO）。
Redis 採用的是 I/O 多路復用技術，並發的去處理連接，它的多路復用程式函數有 select、poll、epoll、kqueue。以 epoll （目前最新的也是最好的多路復用技術）函數為例，當客服端執行 read、write、accept、close 等操作命令時，它會將命令封裝成一個個事件，然後利用 epoll 多路復用的特性來避免 I/O 阻塞。
下面我們看看普通 I/O 模型 和 Redis的 I/O 多路復模型的的區別，來分析Redis高頻請求下如何保持高效執行。
2.5.1 普通 I/O 模型
先來看一下傳統的阻塞 I/O 模型到底是如何工作的：當使用 read 或者 write 對某一個文件描述符（File Descriptor：FD)進行讀寫時，如果當前 FD 不可讀或不可寫，整個 Redis 服務就不會對其它的操作作出響應，導致整個服務不可用。
這也就是傳統意義上的，也就是我們在編程中使用最多的阻塞模型：
阻塞模型雖然開發中非常常見也非常易於理解，但是由於它會影響其他 FD 對應的服務，所以在需要處理多個客戶端任務的時候，往往都不會使用阻塞模型。
2.5.2 I/O 多路復用
多路 復用指的是：多個socket連接復用一個執行緒。這種模式下，內核不會去監視應用程式的連接，而是監視文件描述符。
當客戶端發起請求的時候，會生成不同事件類型的套接字。而在服務端，因為使用了 I/O 多路復用技術，所以不是阻塞式的同步執行，而是將消息放入 socket 隊列（參考下圖的 I/O Multiplexing module），然後通過 File event Dispatcher 將其轉發到不同的事件處理器上，如accept、read、send。
綜上，我們得出如下特性：
- 單執行緒模式，內核持續監聽 socket 上的連接及數據請求，一監聽就交予Redis執行緒處理，達到單個執行緒處理多個I/O 流的效果。
- epoll 提供了基於事件的回調機制。不同事件調用對應的事件處理器。Redis可以持續性的高效處理事件，性能同步提升。
- Redis 不阻塞任一客戶端發起的請求，所以可以同時和多個客戶端連接並處理請求，聚幣並發執行的能力。
3 高性能Redis總結
- 基於記憶體實現，而非磁碟，大都是簡單的存取操作，資源主要消耗在 IO 上，所以讀取速度快。
- 數據結構：基於不同業務場景的高效數據結構
- 動態字元串(REDIS_STRING)：整數(REDIS_ENCODING_INT)、字元串(REDIS_ENCODING_RAW)
- 雙端列表(REDIS_ENCODING_LINKEDLIST)
- 壓縮列表(REDIS_ENCODING_ZIPLIST)
- 跳躍表(REDIS_ENCODING_SKIPLIST)
- 哈希表(REDIS_HASH)
- 整數集合(REDIS_ENCODING_INTSET)
- 執行緒模型：Redis 的網路 IO 以及鍵值對指令讀寫是由單個執行緒來執行的，避免了不必要的contextswitch和競選
- I/O 模型：基於I/O多路復用模型，非阻塞的I/O模型
- 恰單的數據編碼：根據實際數據類型，選擇合理的數據編碼
- Redis 本身是一個全局 哈希表，他的時間複雜度是 O(1)，另外為了防止哈希衝突導致鏈表過長，執行 rehash 操作進行擴充，減少哈希衝突。
