到底有多快

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

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

Redis 是基于內(nèi)存的數(shù)據(jù)庫(kù)杂瘸，跟磁盤(pán)數(shù)據(jù)庫(kù)相比倒淫，完全吊打磁盤(pán)的速度。不論讀寫(xiě)操作都是在內(nèi)存上完成的败玉，我們分別對(duì)比下內(nèi)存操作與磁盤(pán)操作的差異敌土。

磁盤(pán)調(diào)用

內(nèi)存操作

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

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

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

• String： 緩存悠夯、計(jì)數(shù)器癌淮、分布式鎖等。
• List： 鏈表沦补、隊(duì)列乳蓄、微博關(guān)注人時(shí)間軸列表等。
• Hash： 用戶(hù)信息夕膀、Hash 表等栓袖。
• Set： 去重、贊店诗、踩裹刮、共同好友等。
• Zset： 訪問(wèn)量排行榜庞瘸、點(diǎn)擊量排行榜等捧弃。

上面是 Redis 支持的數(shù)據(jù)類(lèi)型，也就是數(shù)據(jù)的保存形式。針對(duì)這 5 種數(shù)據(jù)類(lèi)型违霞，底層運(yùn)用了高效的數(shù)據(jù)結(jié)構(gòu)來(lái)支持嘴办。

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

Redis hash 字典

Redis 整體就是一個(gè)哈希表來(lái)保存所有的鍵值對(duì)眼五，無(wú)論數(shù)據(jù)類(lèi)型是 5 種的任意一種妆艘。

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

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

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

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

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

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

而是采用了漸進(jìn)式 rehash润文，每次處理客戶(hù)端請(qǐng)求的時(shí)候，先從 hash 表 1 中第一個(gè)索引開(kāi)始殿怜，將這個(gè)位置的 所有數(shù)據(jù)拷貝到 hash 表 2 中典蝌，就這樣將 rehash 分散到多次請(qǐng)求過(guò)程中，避免耗時(shí)阻塞头谜。

SDS 簡(jiǎn)單動(dòng)態(tài)字符

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

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

SDS優(yōu)勢(shì)：
1、SDS 中 len 保存這字符串的長(zhǎng)度末荐，O(1) 時(shí)間復(fù)雜度查詢(xún)字符串長(zhǎng)度信息侧纯。C語(yǔ)言從頭開(kāi)始遍歷新锈，直到 「\0」為止甲脏，時(shí)間復(fù)雜度為 O(n)。

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

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

zipList 壓縮列表

壓縮列表是 List 、hash徙菠、 sorted Set 三種數(shù)據(jù)類(lèi)型底層實(shí)現(xiàn)之一讯沈。

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

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

quicklist

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

quicklist 是 ziplist 和 linkedlist 的混合體，它將 linkedlist 按段切分，每一段使用 ziplist 來(lái)緊湊存儲(chǔ)囚衔，多個(gè) ziplist 之間使用雙向指針串接起來(lái)挖腰。

skipList 跳躍表

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

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

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

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

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

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

單線程模型

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

至于為啥用單線程廷支，我們先了解多線程有什么缺點(diǎn)。

多線程的弊端

使用多線程栓辜，通沉蹬模可以增加系統(tǒng)吞吐量，充分利用 CPU 資源啃憎。

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

在運(yùn)行每個(gè)任務(wù)之前辉阶，CPU 需要知道任務(wù)在何處加載并開(kāi)始運(yùn)行先壕。也就是說(shuō)瘩扼，系統(tǒng)需要幫助它預(yù)先設(shè)置 CPU 寄存器和程序計(jì)數(shù)器，這稱(chēng)為 CPU 上下文垃僚。

這些保存的上下文存儲(chǔ)在系統(tǒng)內(nèi)核中集绰，并在重新計(jì)劃任務(wù)時(shí)再次加載。這樣谆棺，任務(wù)的原始狀態(tài)將不會(huì)受到影響栽燕，并且該任務(wù)將看起來(lái)正在連續(xù)運(yùn)行。

切換上下文時(shí)改淑，我們需要完成一系列工作碍岔，這是非常消耗資源的操作。

另外朵夏，當(dāng)多線程并行修改共享數(shù)據(jù)的時(shí)候蔼啦，為了保證數(shù)據(jù)正確，需要加鎖機(jī)制就會(huì)帶來(lái)額外的性能開(kāi)銷(xiāo)仰猖，面臨的共享資源的并發(fā)訪問(wèn)控制問(wèn)題捏肢。

單線程又什么好處？

1亮元、不會(huì)因?yàn)榫€程創(chuàng)建導(dǎo)致的性能消耗猛计；
2唠摹、避免上下文切換引起的 CPU 消耗爆捞，沒(méi)有多線程切換的開(kāi)銷(xiāo)；
3勾拉、避免了線程之間的競(jìng)爭(zhēng)問(wèn)題煮甥，比如添加鎖、釋放鎖藕赞、死鎖等成肘，不需要考慮各種鎖問(wèn)題。
4斧蜕、代碼更清晰双霍，處理邏輯簡(jiǎn)單。

單線程是否沒(méi)有充分利用 CPU 資源呢批销？

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

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

Redis 采用 I/O 多路復(fù)用技術(shù)仲锄，并發(fā)處理連接。采用了 epoll + 自己實(shí)現(xiàn)的簡(jiǎn)單的事件框架湃鹊。epoll 中的讀儒喊、寫(xiě)、關(guān)閉币呵、連接都轉(zhuǎn)化成了事件澄惊，然后利用 epoll 的多路復(fù)用特性，絕不在 IO 上浪費(fèi)一點(diǎn)時(shí)間富雅。

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

基本 IO 模型
一個(gè)基本的網(wǎng)絡(luò) IO 模型，當(dāng)處理 get 請(qǐng)求没佑，會(huì)經(jīng)歷以下過(guò)程：
1毕贼、和客戶(hù)端建立建立 accept;
2、從 socket 種讀取請(qǐng)求 recv;
3蛤奢、解析客戶(hù)端發(fā)送的請(qǐng)求 parse;
4鬼癣、執(zhí)行 get 指令；
5啤贩、響應(yīng)客戶(hù)端數(shù)據(jù)待秃，也就是 向 socket 寫(xiě)回?cái)?shù)據(jù)。

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

關(guān)鍵點(diǎn)就是 accept 和 recv 會(huì)出現(xiàn)阻塞春叫，當(dāng) Redis 監(jiān)聽(tīng)到一個(gè)客戶(hù)端有連接請(qǐng)求肩钠，但一直未能成功建立起連接時(shí)，會(huì)阻塞在 accept() 函數(shù)這里暂殖，導(dǎo)致其他客戶(hù)端無(wú)法和 Redis 建立連接舒萎。

類(lèi)似的吴侦，當(dāng) Redis 通過(guò) recv() 從一個(gè)客戶(hù)端讀取數(shù)據(jù)時(shí)迂求，如果數(shù)據(jù)一直沒(méi)有到達(dá)传货，Redis 也會(huì)一直阻塞在 recv()。

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

IO 多路復(fù)用

多路指的是多個(gè) socket 連接徐矩，復(fù)用指的是復(fù)用一個(gè)線程滞时。多路復(fù)用主要有三種技術(shù)：select，poll滤灯，epoll坪稽。epoll 是最新的也是目前最好的多路復(fù)用技術(shù)。

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

當(dāng)客戶(hù)端運(yùn)行時(shí)豫尽，它將生成具有不同事件類(lèi)型的套接字篙梢。在服務(wù)器端，I / O 多路復(fù)用程序（I / O 多路復(fù)用模塊）會(huì)將消息放入隊(duì)列（也就是 下圖的 I/O 多路復(fù)用程序的 socket 隊(duì)列）美旧，然后通過(guò)文件事件分派器將其轉(zhuǎn)發(fā)到不同的事件處理器渤滞。

簡(jiǎn)單來(lái)說(shuō)：Redis 單線程情況下，內(nèi)核會(huì)一直監(jiān)聽(tīng) socket 上的連接請(qǐng)求或者數(shù)據(jù)請(qǐng)求榴嗅，一旦有請(qǐng)求到達(dá)就交給 Redis 線程處理妄呕，這就實(shí)現(xiàn)了一個(gè) Redis 線程處理多個(gè) IO 流的效果。

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

Redis 線程不會(huì)阻塞在某一個(gè)特定的監(jiān)聽(tīng)或已連接套接字上，也就是說(shuō)厅贪，不會(huì)阻塞在某一個(gè)特定的客戶(hù)端請(qǐng)求處理上。正因?yàn)榇搜疟觯琑edis 可以同時(shí)和多個(gè)客戶(hù)端連接并處理請(qǐng)求养涮，從而提升并發(fā)性。

總結(jié)

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