到底有多快

根據(jù)官方數(shù)據(jù)，Redis 的 QPS 可以達(dá)到約 100000（每秒請求數(shù)），有興趣的可以參考官方的基準(zhǔn)程序測試《How fast is Redis？》，地址：https://redis.io/topics/benchmarks

基于內(nèi)存實現(xiàn)

Redis 是基于內(nèi)存的數(shù)據(jù)庫，跟磁盤數(shù)據(jù)庫相比，完全吊打磁盤的速度。不論讀寫操作都是在內(nèi)存上完成的，我們分別對比下內(nèi)存操作與磁盤操作的差異。

磁盤調(diào)用

內(nèi)存操作

內(nèi)存直接由 CPU 控制，也就是 CPU 內(nèi)部集成的內(nèi)存控制器，所以說內(nèi)存是直接與 CPU 對接，享受與 CPU 通信的最優(yōu)帶寬。
最后以一張圖量化系統(tǒng)的各種延時時間（部分?jǐn)?shù)據(jù)引用 Brendan Gregg）

高效的數(shù)據(jù)結(jié)構(gòu)

學(xué)習(xí) MySQL 的時候我知道為了提高檢索速度使用了 B+ Tree 數(shù)據(jù)結(jié)構(gòu)，所以 Redis 速度快應(yīng)該也跟數(shù)據(jù)結(jié)構(gòu)有關(guān)。
在 Redis 中，常用的 5 種數(shù)據(jù)類型和應(yīng)用場景如下：

• String： 緩存、計數(shù)器、分布式鎖等。
• List： 鏈表、隊列、微博關(guān)注人時間軸列表等。
• Hash： 用戶信息、Hash 表等。
• Set： 去重、贊、踩、共同好友等。
• Zset： 訪問量排行榜、點擊量排行榜等。

上面是 Redis 支持的數(shù)據(jù)類型，也就是數(shù)據(jù)的保存形式。針對這 5 種數(shù)據(jù)類型，底層運用了高效的數(shù)據(jù)結(jié)構(gòu)來支持。

為了追求速度，不同數(shù)據(jù)類型使用不同的數(shù)據(jù)結(jié)構(gòu)速度才得以提升。每種數(shù)據(jù)類型都有一種或者多種數(shù)據(jù)結(jié)構(gòu)來支撐，底層數(shù)據(jù)結(jié)構(gòu)有 6 種。

Redis hash 字典

Redis 整體就是一個哈希表來保存所有的鍵值對，無論數(shù)據(jù)類型是 5 種的任意一種。

整個數(shù)據(jù)庫就是一個全局哈希表，而哈希表的時間復(fù)雜度是 O(1)，只需要計算每個鍵的哈希值，便知道對應(yīng)的哈希桶位置，定位桶里面的 entry 找到對應(yīng)數(shù)據(jù)，這個也是 Redis 快的原因之一。

那 Hash 沖突怎么辦？
當(dāng)寫入 Redis 的數(shù)據(jù)越來越多的時候，哈希沖突不可避免，會出現(xiàn)不同的 key 計算出一樣的哈希值。

Redis 通過鏈?zhǔn)焦＝鉀Q沖突：也就是同一個 桶里面的元素使用鏈表保存。但是當(dāng)鏈表過長就會導(dǎo)致查找性能變差可能，所以 Redis 為了追求快，使用了兩個全局哈希表。用于 rehash 操作，增加現(xiàn)有的哈希桶數(shù)量，減少哈希沖突。

開始默認(rèn)使用 hash 表 1 保存鍵值對數(shù)據(jù)，哈希表 2 此刻沒有分配空間。當(dāng)數(shù)據(jù)越來多觸發(fā) rehash 操作，則執(zhí)行以下操作：

1、給 hash 表 2 分配更大的空間；
2、將 hash 表 1 的數(shù)據(jù)重新映射拷貝到 hash 表 2 中；
3、釋放 hash 表 1 的空間。

值得注意的是，將 hash 表 1 的數(shù)據(jù)重新映射到 hash 表 2 的過程中并不是一次性的，這樣會造成 Redis 阻塞，無法提供服務(wù)。

而是采用了漸進(jìn)式 rehash，每次處理客戶端請求的時候，先從 hash 表 1 中第一個索引開始，將這個位置的 所有數(shù)據(jù)拷貝到 hash 表 2 中，就這樣將 rehash 分散到多次請求過程中，避免耗時阻塞。

SDS 簡單動態(tài)字符

字符串結(jié)構(gòu)使用最廣泛，通常我們用于緩存登陸后的用戶信息，key = userId，value = 用戶信息 JSON 序列化成字符串。

C 語言字符串結(jié)構(gòu)與 SDS 字符串結(jié)構(gòu)對比圖如下所示：

SDS優(yōu)勢：
1、SDS 中 len 保存這字符串的長度，O(1) 時間復(fù)雜度查詢字符串長度信息。C語言從頭開始遍歷，直到 「\0」為止，時間復(fù)雜度為 O(n)。

2、空間預(yù)分配：SDS 被修改后，程序不僅會為 SDS 分配所需要的必須空間，還會分配額外的未使用空間。

3、惰性空間釋放：當(dāng)對 SDS 進(jìn)行縮短操作時，程序并不會回收多余的內(nèi)存空間，而是使用 free 字段將這些字節(jié)數(shù)量記錄下來不釋放，后面如果需要 append 操作，則直接使用 free 中未使用的空間，減少了內(nèi)存的分配。

zipList 壓縮列表

壓縮列表是 List 、hash、 sorted Set 三種數(shù)據(jù)類型底層實現(xiàn)之一。

當(dāng)一個列表只有少量數(shù)據(jù)的時候，并且每個列表項要么就是小整數(shù)值，要么就是長度比較短的字符串，那么 Redis 就會使用壓縮列表來做列表鍵的底層實現(xiàn)。

ziplist 是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型的數(shù)據(jù)結(jié)構(gòu)，ziplist 中可以包含多個 entry 節(jié)點，每個節(jié)點可以存放整數(shù)或者字符串。

quicklist

后續(xù)版本對列表數(shù)據(jù)結(jié)構(gòu)進(jìn)行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

quicklist 是 ziplist 和 linkedlist 的混合體，它將 linkedlist 按段切分，每一段使用 ziplist 來緊湊存儲，多個 ziplist 之間使用雙向指針串接起來。

skipList 跳躍表

sorted set 類型的排序功能便是通過「跳躍列表」數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。

跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達(dá)到快速訪問節(jié)點的目的。

跳表在鏈表的基礎(chǔ)上，增加了多層級索引，通過索引位置的幾個跳轉(zhuǎn)，實現(xiàn)數(shù)據(jù)的快速定位，如下圖所示

整數(shù)數(shù)組（intset）

當(dāng)一個集合只包含整數(shù)值元素，并且這個集合的元素數(shù)量不多時，Redis 就會使用整數(shù)集合作為集合鍵的底層實現(xiàn)。結(jié)構(gòu)如下：

contents 數(shù)組是整數(shù)集合的底層實現(xiàn)：整數(shù)集合的每個元素都是 contents 數(shù)組的一個數(shù)組項（item），各個項在數(shù)組中按值的大小從小到大有序地排列，并且數(shù)組中不包含任何重復(fù)項。length 屬性記錄了整數(shù)集合包含的元素數(shù)量，也即是 contents 數(shù)組的長度。

單線程模型

我們要明確的是：Redis 的單線程指的是 Redis 的網(wǎng)絡(luò) IO 以及鍵值對指令讀寫是由一個線程來執(zhí)行的。 對于 Redis 的持久化、集群數(shù)據(jù)同步、異步刪除等都是其他線程執(zhí)行。

至于為啥用單線程，我們先了解多線程有什么缺點。

多線程的弊端

使用多線程，通?？梢栽黾酉到y(tǒng)吞吐量，充分利用 CPU 資源。

但是，使用多線程后，沒有良好的系統(tǒng)設(shè)計，可能會出現(xiàn)如下圖所示的場景，增加了線程數(shù)量，前期吞吐量會增加，再進(jìn)一步新增線程的時候，系統(tǒng)吞吐量幾乎不再新增，甚至?xí)陆?/p>

在運行每個任務(wù)之前，CPU 需要知道任務(wù)在何處加載并開始運行。也就是說，系統(tǒng)需要幫助它預(yù)先設(shè)置 CPU 寄存器和程序計數(shù)器，這稱為 CPU 上下文。

這些保存的上下文存儲在系統(tǒng)內(nèi)核中，并在重新計劃任務(wù)時再次加載。這樣，任務(wù)的原始狀態(tài)將不會受到影響，并且該任務(wù)將看起來正在連續(xù)運行。

切換上下文時，我們需要完成一系列工作，這是非常消耗資源的操作。

另外，當(dāng)多線程并行修改共享數(shù)據(jù)的時候，為了保證數(shù)據(jù)正確，需要加鎖機(jī)制就會帶來額外的性能開銷，面臨的共享資源的并發(fā)訪問控制問題。

單線程又什么好處？

1、不會因為線程創(chuàng)建導(dǎo)致的性能消耗；
2、避免上下文切換引起的 CPU 消耗，沒有多線程切換的開銷；
3、避免了線程之間的競爭問題，比如添加鎖、釋放鎖、死鎖等，不需要考慮各種鎖問題。
4、代碼更清晰，處理邏輯簡單。

單線程是否沒有充分利用 CPU 資源呢？

官方答案：因為 Redis 是基于內(nèi)存的操作，CPU 不是 Redis 的瓶頸，Redis 的瓶頸最有可能是機(jī)器內(nèi)存的大小或者網(wǎng)絡(luò)帶寬。既然單線程容易實現(xiàn)，而且 CPU 不會成為瓶頸，那就順理成章地采用單線程的方案了。原文地址：https://redis.io/topics/faq。

I/O 多路復(fù)用模型

Redis 采用 I/O 多路復(fù)用技術(shù)，并發(fā)處理連接。采用了 epoll + 自己實現(xiàn)的簡單的事件框架。epoll 中的讀、寫、關(guān)閉、連接都轉(zhuǎn)化成了事件，然后利用 epoll 的多路復(fù)用特性，絕不在 IO 上浪費一點時間。

在解釋 IO 多慮復(fù)用之前我們先了解下基本 IO 操作會經(jīng)歷什么。

基本 IO 模型
一個基本的網(wǎng)絡(luò) IO 模型，當(dāng)處理 get 請求，會經(jīng)歷以下過程：
1、和客戶端建立建立 accept;
2、從 socket 種讀取請求 recv;
3、解析客戶端發(fā)送的請求 parse;
4、執(zhí)行 get 指令；
5、響應(yīng)客戶端數(shù)據(jù)，也就是 向 socket 寫回數(shù)據(jù)。

其中，bind/listen、accept、recv、parse 和 send 屬于網(wǎng)絡(luò) IO 處理，而 get 屬于鍵值數(shù)據(jù)操作。既然 Redis 是單線程，那么，最基本的一種實現(xiàn)是在一個線程中依次執(zhí)行上面說的這些操作。

關(guān)鍵點就是 accept 和 recv 會出現(xiàn)阻塞，當(dāng) Redis 監(jiān)聽到一個客戶端有連接請求，但一直未能成功建立起連接時，會阻塞在 accept() 函數(shù)這里，導(dǎo)致其他客戶端無法和 Redis 建立連接。

類似的，當(dāng) Redis 通過 recv() 從一個客戶端讀取數(shù)據(jù)時，如果數(shù)據(jù)一直沒有到達(dá)，Redis 也會一直阻塞在 recv()。

阻塞的原因由于使用傳統(tǒng)阻塞 IO ，也就是在執(zhí)行 read、accept 、recv 等網(wǎng)絡(luò)操作會一直阻塞等待。如下圖所示：

IO 多路復(fù)用

多路指的是多個 socket 連接，復(fù)用指的是復(fù)用一個線程。多路復(fù)用主要有三種技術(shù)：select，poll，epoll。epoll 是最新的也是目前最好的多路復(fù)用技術(shù)。

它的基本原理是，內(nèi)核不是監(jiān)視應(yīng)用程序本身的連接，而是監(jiān)視應(yīng)用程序的文件描述符。

當(dāng)客戶端運行時，它將生成具有不同事件類型的套接字。在服務(wù)器端，I / O 多路復(fù)用程序（I / O 多路復(fù)用模塊）會將消息放入隊列（也就是 下圖的 I/O 多路復(fù)用程序的 socket 隊列），然后通過文件事件分派器將其轉(zhuǎn)發(fā)到不同的事件處理器。

簡單來說：Redis 單線程情況下，內(nèi)核會一直監(jiān)聽 socket 上的連接請求或者數(shù)據(jù)請求，一旦有請求到達(dá)就交給 Redis 線程處理，這就實現(xiàn)了一個 Redis 線程處理多個 IO 流的效果。

select/epoll 提供了基于事件的回調(diào)機(jī)制，即針對不同事件的發(fā)生，調(diào)用相應(yīng)的事件處理器。所以 Redis 一直在處理事件，提升 Redis 的響應(yīng)性能。

Redis 線程不會阻塞在某一個特定的監(jiān)聽或已連接套接字上，也就是說，不會阻塞在某一個特定的客戶端請求處理上。正因為此，Redis 可以同時和多個客戶端連接并處理請求，從而提升并發(fā)性。

總結(jié)

1、基于內(nèi)存實現(xiàn)
2、使用I/O多路復(fù)用
3、單線程模型
4、高效的數(shù)據(jù)結(jié)構(gòu)