京東二面:Redis為什么快?我說Redis是純內(nèi)存操作的,然后他對我笑了笑
引言
Redis是一個高性能的開源內(nèi)存數(shù)據(jù)庫,以其快速的讀寫速度和豐富的數(shù)據(jù)結(jié)構(gòu)支持而聞名。作為一個輕量級、靈活的鍵值存儲系統(tǒng),Redis在各種應(yīng)用場景下都展現(xiàn)出了驚人的性能優(yōu)勢。無論是作為緩存工具、會話管理組件、消息傳遞媒介,還是在實時數(shù)據(jù)處理任務(wù)和復(fù)雜的分布式系統(tǒng)架構(gòu)中,Redis均扮演了至關(guān)重要的角色。而Redis為什么快的原因也是我們嘗嘗遇見的高頻面試問題。接下來我們就一起探討一下Redis快的原因。
本文將深入探討Redis之所以快速處理大規(guī)模數(shù)據(jù)的原因。我們將從Redis基于內(nèi)存操作的特性、高效的內(nèi)存數(shù)據(jù)結(jié)構(gòu)、單線程模型、I/O多路復(fù)用技術(shù)、底層模型和優(yōu)化技術(shù)、持久化機制以及網(wǎng)絡(luò)通信協(xié)議等多個方面進行分析和討論。通過深入了解Redis內(nèi)部機制和性能優(yōu)化技術(shù),我們可以更好地理解Redis之所以快速的根本原因,以及如何在實際應(yīng)用中充分發(fā)揮其優(yōu)勢。
完全基于內(nèi)存
Redis作為一種內(nèi)存導(dǎo)向型數(shù)據(jù)庫系統(tǒng),其關(guān)鍵特性在于將所有數(shù)據(jù)實體,包括鍵值對及其相關(guān)的復(fù)雜數(shù)據(jù)結(jié)構(gòu),完全寄宿于內(nèi)存之中。相較于依賴磁盤存儲的傳統(tǒng)數(shù)據(jù)庫系統(tǒng),Redis巧妙地運用內(nèi)存的高速讀寫特性,顯著提升了系統(tǒng)的響應(yīng)速率與整體性能表現(xiàn)。
內(nèi)存相對于磁盤具備無可比擬的讀寫速度優(yōu)勢,使得Redis能夠即時、高效地處理數(shù)據(jù)存取。在讀取操作層面,Redis無需經(jīng)過耗時的磁盤I/O過程,只需在內(nèi)存空間內(nèi)迅速定位所需數(shù)據(jù),從而顯著降低了訪問延遲;而在寫入操作時,Redis同樣直接作用于內(nèi)存區(qū)域,新數(shù)據(jù)能即刻生效,僅在執(zhí)行持久化策略時,例如RDB快照或AOF日志記錄,數(shù)據(jù)才會被異步地或按需地同步至磁盤,以確保即使在系統(tǒng)重啟后數(shù)據(jù)仍能得以恢復(fù),但此過程并不會妨礙Redis在常規(guī)操作中維持其卓越的性能表現(xiàn)。
說到這,我們就會想到,一臺服務(wù)器的內(nèi)存不是無限的,相反的是比較緊張的,Redis基于內(nèi)存操作,那么Redis究竟是如何在有限內(nèi)存空間中進行精細且高效的內(nèi)存管理呢?
過期鍵刪除
Redis支持為鍵設(shè)置過期時間(TTL),并且在鍵過期后會通過兩種方式自動刪除它們:
- 惰性刪除(Lazy Expire):在訪問某個鍵時,Redis會檢查該鍵是否已經(jīng)過期,如果已經(jīng)過期,則在訪問時將其刪除。這意味著只有當(dāng)有客戶端嘗試訪問過期的鍵時,Redis才會執(zhí)行刪除操作。這種方式的優(yōu)勢在于避免了不必要的操作,只有在需要時才進行刪除,但缺點是可能會導(dǎo)致過期鍵在一段時間內(nèi)仍然占用內(nèi)存。
- 定期刪除(Active Expire):Redis周期性地(默認每秒10次)隨機抽取一部分鍵,并檢查它們的過期時間。如果發(fā)現(xiàn)某個鍵已經(jīng)過期,則立即將其刪除。這種方式可以保證過期鍵在一定時間內(nèi)被及時刪除,避免了過期鍵長時間占用內(nèi)存。但定期刪除會帶來額外的CPU消耗,因為需要在每次抽取時檢查鍵的過期時間。
這兩種方式結(jié)合起來,可以有效地管理和清理過期鍵,保證Redis的內(nèi)存使用在合理范圍內(nèi)。同時,我們在日常開發(fā)中可以根據(jù)具體業(yè)務(wù)場景和需求調(diào)整過期策略的配置,以達到最佳的性能和內(nèi)存利用率。
內(nèi)存淘汰策略
內(nèi)存淘汰策略是Redis用于釋放內(nèi)存空間的一種機制,當(dāng)內(nèi)存空間不足時(達到或超過了配置的maxmemory),Redis會根據(jù)預(yù)先設(shè)置的淘汰策略來選擇要刪除的鍵,從而釋放內(nèi)存空間。通過合理選擇和配置內(nèi)存淘汰策略,可以有效地管理內(nèi)存使用,防止內(nèi)存溢出,并保證系統(tǒng)的穩(wěn)定性和性能。
常見的內(nèi)存淘汰策略:
- LRU(最近最少使用):LRU策略會刪除最近最少被訪問的鍵。Redis會記錄每個鍵最后一次被訪問的時間戳,并定期檢查這些時間戳,選擇最久未被訪問的鍵進行刪除。LRU策略適用于緩存場景,通常最久未被訪問的鍵可能是最不常用的,因此刪除這些鍵可以釋放更多的內(nèi)存空間。
- LFU(最不經(jīng)常使用):LFU策略會刪除最不經(jīng)常被訪問的鍵。Redis會記錄每個鍵被訪問的頻率,并定期檢查這些頻率,選擇訪問頻率最低的鍵進行刪除。LFU策略適用于對訪問頻率較低的鍵進行淘汰,從而釋放內(nèi)存空間。
- TTL(鍵的過期時間):TTL策略會刪除已經(jīng)過期的鍵。Redis會定期檢查鍵的過期時間,并刪除已經(jīng)過期的鍵。通過設(shè)置鍵的過期時間,可以自動清理不再需要的數(shù)據(jù),釋放內(nèi)存空間。
- 隨機刪除:隨機刪除策略會隨機選擇一些鍵進行刪除。雖然這種策略不考慮鍵的使用頻率或過期時間,但在某些情況下可能會是一種簡單且有效的淘汰方式,尤其是在內(nèi)存空間不足時。
- 淘汰固定數(shù)量的鍵:淘汰固定數(shù)量的鍵策略會選擇要刪除的鍵的數(shù)量,然后按照一定的規(guī)則(如LRU或LFU)來選擇要刪除的鍵。這種策略可以保證每次淘汰都釋放固定數(shù)量的內(nèi)存空間。
當(dāng)Redis的內(nèi)存使用達到配置的maxmemory限制時,就會觸發(fā)內(nèi)存淘汰策略,以釋放內(nèi)存空間。合理選擇內(nèi)存淘汰策略,并根據(jù)系統(tǒng)的需求設(shè)置maxmemory參數(shù),可以有效地管理內(nèi)存使用,保證系統(tǒng)的穩(wěn)定性和性能。通過合理配置內(nèi)存限制和內(nèi)存淘汰策略,可以有效地管理Redis的內(nèi)存使用,保證系統(tǒng)在內(nèi)存空間不足時能夠及時釋放內(nèi)存,避免因內(nèi)存溢出而導(dǎo)致系統(tǒng)性能下降或者崩潰。
修改內(nèi)存maxmemory只需要在redis.conf配置文件中配置maxmemory-policy參數(shù)即可。
內(nèi)存碎片管理
內(nèi)存碎片整理是指對Redis中的內(nèi)存空間進行重新排列和整理,以減少內(nèi)存碎片的數(shù)量和大小。內(nèi)存碎片是指已分配但不再使用的內(nèi)存塊,這些內(nèi)存塊雖然被標(biāo)記為已分配,但實際上并未被有效利用,造成了內(nèi)存的浪費。
在Redis中,由于數(shù)據(jù)的增刪改查操作不斷進行,會導(dǎo)致內(nèi)存空間中出現(xiàn)大量的內(nèi)存碎片。這些內(nèi)存碎片雖然單個很小,但如果積累起來會導(dǎo)致內(nèi)存碎片化,降低內(nèi)存利用率,影響系統(tǒng)的性能和穩(wěn)定性。
為了解決內(nèi)存碎片化的問題,Redis會定期進行內(nèi)存碎片整理操作。內(nèi)存碎片整理過程包括以下幾個步驟:
- 遍歷內(nèi)存空間:Redis會遍歷整個內(nèi)存空間,檢查每個內(nèi)存塊的狀態(tài),包括已分配和未分配的內(nèi)存塊。
- 合并相鄰的空閑內(nèi)存塊:Redis會嘗試合并相鄰的空閑內(nèi)存塊,將它們合并成一個更大的內(nèi)存塊。這樣可以減少內(nèi)存碎片的數(shù)量,提高內(nèi)存利用率。
- 移動數(shù)據(jù):如果有必要,Redis可能會將數(shù)據(jù)從一個內(nèi)存塊移動到另一個內(nèi)存塊,以便更好地組織內(nèi)存空間。這個過程可能會比較耗時,因為需要將數(shù)據(jù)從一個位置復(fù)制到另一個位置。
- 釋放不再使用的內(nèi)存塊:最后,Redis會釋放那些不再使用的內(nèi)存塊,以便它們可以被重新分配給新的數(shù)據(jù)。
通過定期進行內(nèi)存碎片整理操作,Redis可以保持內(nèi)存空間的連續(xù)性,減少內(nèi)存碎片化的程度,提高內(nèi)存利用率,從而提高系統(tǒng)的性能和穩(wěn)定性。但是,內(nèi)存碎片整理過程可能會消耗一定的系統(tǒng)資源,尤其是在內(nèi)存碎片較多的情況下。所以,通常情況下,Redis會選擇在系統(tǒng)負載較低的時候進行碎片整理操作,以避免對系統(tǒng)性能產(chǎn)生不利影響。
高效的內(nèi)存數(shù)據(jù)結(jié)構(gòu)
Redis作為一個內(nèi)存數(shù)據(jù)庫系統(tǒng),提供了豐富且高效的內(nèi)存數(shù)據(jù)結(jié)構(gòu),包括字符串(String)、列表(List)、集合(Set)、有序集合(Sorted Set)、哈希(Hash)等。這些數(shù)據(jù)結(jié)構(gòu)不僅具有簡單易用的特點,還能夠在內(nèi)存中高效地存儲和操作數(shù)據(jù),為Redis的快速性能提供了堅實的基礎(chǔ)。
動態(tài)字符串
動態(tài)字符串是一種能夠動態(tài)擴展長度的字符串實現(xiàn)方式。在許多編程語言和數(shù)據(jù)結(jié)構(gòu)中都有類似的實現(xiàn),如C語言中的動態(tài)數(shù)組(dynamic array)。而SDS是Redis中的一種簡單動態(tài)字符串結(jié)構(gòu),它是一種動態(tài)大小的字節(jié)數(shù)組,用于存儲和操作字符串?dāng)?shù)據(jù)。SDS是Redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ),也是字符串?dāng)?shù)據(jù)結(jié)構(gòu)的底層實現(xiàn)。它的結(jié)構(gòu)如下:
/*
* redis中保存字符串對象的結(jié)構(gòu)
*/
struct sdshdr {
//用于記錄buf數(shù)組中使用的字節(jié)的數(shù)目,和SDS存儲的字符串的長度相等
int len;
//用于記錄buf數(shù)組中沒有使用的字節(jié)的數(shù)目
int free;
//字節(jié)數(shù)組,用于儲存字符串
char buf[]; //buf的大小等于len+free+1,其中多余的1個字節(jié)是用來存儲’\0’的
};
在C語言中傳統(tǒng)字符串是使用長度為N+1的字符數(shù)組來表示長度為 的字符串,并且字符串?dāng)?shù)組的最后一個元素總是空字符'\0'。
如果我們想要獲取上述CODERACADEMY的長度,我們需要從頭開始遍歷,直到遇到 '\0' 為止。
而Redis的SDS的數(shù)據(jù)結(jié)構(gòu)使用一個len字段記錄當(dāng)前字符串的長度,使用free表示空閑的長度。想要獲取長度只需要獲取len字段即可。
我們可以看出C語言獲取字符串長度的時間復(fù)雜度為O(N),而SDS獲取字符串長度的時間復(fù)雜度為O(1)。除此之外,SDS相對于C語言字符串還有如下區(qū)別:
特征 | C語言字符串 | SDS |
類型 | 靜態(tài)字符數(shù)組 | 動態(tài)字符串結(jié)構(gòu) |
內(nèi)存管理 | 需手動分配和釋放內(nèi)存 | 自動擴展和釋放內(nèi)存 |
存儲空間 | 需要提前預(yù)留足夠的空間 | 根據(jù)需要動態(tài)調(diào)整大小 |
長度計算 | 需要遍歷整個字符串計算長度 | O(1)復(fù)雜度直接獲取字符串長度 |
二進制安全 | 不二進制安全 | 二進制安全 |
緩沖區(qū)溢出保護 | 不提供緩沖區(qū)溢出保護 | 提供緩沖區(qū)溢出保護 |
操作復(fù)雜度 | 操作復(fù)雜度隨字符串長度增加而增加 | 操作復(fù)雜度不受字符串長度影響 |
可拓展性 | 不易擴展,需要手動處理內(nèi)存擴展 | 自動擴展,支持動態(tài)調(diào)整大小 |
細說下來,SDS相對于C語言字符串有如下優(yōu)點:
- 二進制安全: SDS可以存儲任意二進制數(shù)據(jù),而不僅僅是文本字符串。這意味著SDS可以存儲包括圖片、視頻、音頻等在內(nèi)的各種二進制數(shù)據(jù),而不會受到特殊字符或者空字符的限制,具有更廣泛的適用性。
- 動態(tài)擴展: SDS的大小可以根據(jù)存儲的字符串長度動態(tài)調(diào)整,可以根據(jù)實際需要動態(tài)分配和釋放內(nèi)存空間。這種動態(tài)擴展的能力使得SDS能夠處理任意長度的字符串?dāng)?shù)據(jù),而不受到固定大小的限制。
- O(1)復(fù)雜度的操作: SDS支持常數(shù)時間復(fù)雜度的操作,包括添加字符、刪除字符、修改字符等。無論字符串的長度是多少,這些操作的時間開銷都是固定的,具有高效的性能。
- 緩沖區(qū)溢出保護: SDS在存儲字符串時,會自動添加一個空字符('\0')作為字符串的結(jié)束標(biāo)志,保證字符串的有效性和安全性。這種緩沖區(qū)溢出保護能夠防止緩沖區(qū)溢出的問題,提高了系統(tǒng)的穩(wěn)定性和安全性。
- 惰性空間釋放: 當(dāng)SDS縮短字符串時,并不會立即釋放多余的空間,而是將多余的空間保留下來,以備后續(xù)的再利用。這種惰性空間釋放的策略可以減少內(nèi)存分配和釋放的開銷,提高內(nèi)存利用率。
這些優(yōu)點使得SDS在Redis中被廣泛應(yīng)用于存儲和操作字符串?dāng)?shù)據(jù),為Redis的高性能和高可靠性提供了堅實的基礎(chǔ)。
雙端鏈表
Redis中的雙端鏈表是一種經(jīng)過優(yōu)化的數(shù)據(jù)結(jié)構(gòu),用于存儲有序的元素集合。它具有雙向鏈接的特性,每個節(jié)點都包含指向前一個節(jié)點和后一個節(jié)點的指針。
雙端鏈表中的節(jié)點是鏈表的基本構(gòu)建單元,它存儲了鏈表中的數(shù)據(jù)元素以及指向前一個節(jié)點和后一個節(jié)點的指針。在Redis中,雙端鏈表節(jié)點的定義通常如下:
typedef struct listNode {
struct listNode *prev; // 指向前一個節(jié)點的指針
struct listNode *next; // 指向后一個節(jié)點的指針
void *value; // 存儲的數(shù)據(jù)元素
} listNode;
雙端鏈表中的節(jié)點包含了以下幾個關(guān)鍵屬性:
- prev指針:prev指針是指向前一個節(jié)點的指針,它指向鏈表中當(dāng)前節(jié)點的前一個節(jié)點。如果當(dāng)前節(jié)點是鏈表的頭節(jié)點,則prev指針為NULL。通過prev指針,可以在雙端鏈表中方便地向前遍歷節(jié)點。
- next指針:next指針是指向后一個節(jié)點的指針,它指向鏈表中當(dāng)前節(jié)點的后一個節(jié)點。如果當(dāng)前節(jié)點是鏈表的尾節(jié)點,則next指針為NULL。通過next指針,可以在雙端鏈表中方便地向后遍歷節(jié)點。
- value數(shù)據(jù)域:value數(shù)據(jù)域用于存儲鏈表節(jié)點所包含的數(shù)據(jù)元素。這個數(shù)據(jù)元素可以是任意類型的數(shù)據(jù),因此在Redis中的雙端鏈表中,通常使用void *類型來表示。這種設(shè)計使得雙端鏈表可以存儲任意類型的數(shù)據(jù)元素。
通過這些屬性,雙端鏈表節(jié)點構(gòu)成了鏈表的基本組成部分,它們通過prev和next指針連接在一起,形成了雙向鏈接的鏈表結(jié)構(gòu)。
對于鏈表中描述鏈表整體屬性的元數(shù)據(jù),它的結(jié)構(gòu)如下:
typedef struct list {
listNode *head; // 頭節(jié)點指針
listNode *tail; // 尾節(jié)點指針
unsigned long len; // 鏈表長度
// 其他字段...
} list;
從結(jié)構(gòu)中可以看出元數(shù)據(jù)中還有兩個特殊的節(jié)點:頭節(jié)點(head node)和尾節(jié)點(tail node),它們分別位于鏈表的頭部和尾部。而他們的作用如下:
- 頭節(jié)點(head node):頭節(jié)點是雙端鏈表中的第一個節(jié)點,也是鏈表的入口。它通常用于存儲鏈表的起始位置信息,以便快速定位鏈表的起始位置。在雙端鏈表中,頭節(jié)點的特點是沒有前一個節(jié)點,即頭節(jié)點的prev指針為NULL。頭節(jié)點通常用于存儲鏈表的頭部元數(shù)據(jù)或者哨兵節(jié)點。
- 尾節(jié)點(tail node):尾節(jié)點是雙端鏈表中的最后一個節(jié)點,也是鏈表的結(jié)束位置。它通常用于存儲鏈表的結(jié)束位置信息,以便快速定位鏈表的結(jié)束位置。在雙端鏈表中,尾節(jié)點的特點是沒有后一個節(jié)點,即尾節(jié)點的next指針為NULL。尾節(jié)點通常用于存儲鏈表的尾部元數(shù)據(jù)或者哨兵節(jié)點。
在Redis中,通常會使用頭節(jié)點和尾節(jié)點來表示雙端鏈表的起始位置和結(jié)束位置,以方便對鏈表進行操作。Redis中的雙端鏈表常見操作如下:
- 頭節(jié)點(head):表示雙端鏈表的頭部節(jié)點,通過頭節(jié)點可以快速定位鏈表的起始位置,通常用于添加和刪除鏈表的頭部元素。
- 尾節(jié)點(tail):表示雙端鏈表的尾部節(jié)點,通過尾節(jié)點可以快速定位鏈表的結(jié)束位置,通常用于添加和刪除鏈表的尾部元素。
通過頭節(jié)點和尾節(jié)點,可以方便地對雙端鏈表進行頭部插入、尾部插入、頭部刪除、尾部刪除等操作,從而實現(xiàn)了對雙端鏈表的高效操作。
除了上述頭尾節(jié)點以外,鏈表的元數(shù)據(jù)中還有l(wèi)en參數(shù),這個參數(shù)用于記錄鏈表的當(dāng)前長度。每當(dāng)鏈表中添加或刪除節(jié)點時,Redis會相應(yīng)地更新len字段的值,以反映鏈表的當(dāng)前長度。這個參數(shù)與SDS里類似,獲取鏈表長度時不用再遍歷整個鏈表,直接拿到len值就可以了,這個時間復(fù)雜度是 O(1)。
壓縮列表
Redis中的壓縮列表(ziplist)是一種特殊的數(shù)據(jù)結(jié)構(gòu),用于存儲列表和哈希數(shù)據(jù)類型中的元素。壓縮列表通過將多個小的數(shù)據(jù)單元壓縮在一起,以節(jié)省內(nèi)存空間,并提高訪問效率。
對于壓縮列表,它的主要作用如下:
- 緊湊的存儲形式: 壓縮列表以一種緊湊的方式存儲數(shù)據(jù),將多個元素緊密地排列在一起,節(jié)省了存儲空間。在壓縮列表中,相鄰的元素可以共享同一個內(nèi)存空間,這種緊湊的存儲形式可以大大減少內(nèi)存的消耗。
- 靈活的編碼方式: 壓縮列表中的每個元素都可以采用不同的編碼方式進行存儲,包括整數(shù)編碼、字符串編碼和字節(jié)數(shù)組編碼等。根據(jù)元素的類型和大小,壓縮列表會選擇合適的編碼方式來存儲數(shù)據(jù),以進一步節(jié)省內(nèi)存空間。
- 快速的隨機訪問: 壓縮列表支持快速的隨機訪問操作,可以通過下標(biāo)索引來訪問壓縮列表中的任意元素。由于壓縮列表采用緊湊的存儲形式,因此可以通過簡單的偏移計算來實現(xiàn)快速的元素訪問,具有較高的訪問效率。
- 動態(tài)調(diào)整大?。?壓縮列表支持動態(tài)調(diào)整大小,可以根據(jù)實際需要自動擴展或收縮內(nèi)存空間。當(dāng)壓縮列表中的元素數(shù)量增加時,可以動態(tài)地分配額外的內(nèi)存空間,以容納更多的元素;當(dāng)元素數(shù)量減少時,可以釋放多余的內(nèi)存空間,以節(jié)省內(nèi)存資源。
- 適用于小型數(shù)據(jù)集: 壓縮列表適用于存儲小型數(shù)據(jù)集,例如長度較短的列表或者哈希表。由于壓縮列表采用緊湊的存儲形式,并且支持快速的隨機訪問,因此特別適合于存儲數(shù)量較少但訪問頻繁的數(shù)據(jù)。
字典
在Redis中,字典(dictionary)是一種用于存儲鍵值對數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),也稱為哈希表(hash table)。字典是Redis中最常用的數(shù)據(jù)結(jié)構(gòu)之一,具有快速查找、動態(tài)調(diào)整大小、哈希沖突處理、迭代器支持等特點,適用于各種數(shù)據(jù)存儲和操作需求,實現(xiàn)鍵值對存儲和快速查找。
字典以鍵值對的形式存儲數(shù)據(jù),每個鍵都與一個值相關(guān)聯(lián)。在Redis中,鍵和值都可以是任意類型的數(shù)據(jù),如字符串、整數(shù)、列表或哈希表。
字典利用哈希表實現(xiàn),具備快速查找的特性。通過將鍵映射到哈希表的索引位置,字典能以常數(shù)時間復(fù)雜度(O(1))內(nèi)查找、插入和刪除鍵值對,即使在大型數(shù)據(jù)集中也能保持高效。
此外,字典支持動態(tài)調(diào)整大小,隨著鍵值對數(shù)量的變化,能自動擴展或收縮內(nèi)存空間,以適應(yīng)數(shù)據(jù)量的變化。
在存儲數(shù)據(jù)時,如果產(chǎn)生了哈希沖突,字典可以采用開放尋址法或鏈表法等策略,根據(jù)哈希表的大小和負載因子選擇合適的沖突解決方法,確保查找性能高效。
跳躍表
跳躍表(Skip List)是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu),它利用多級索引來加速查找操作,類似于平衡樹,但實現(xiàn)起來更加簡單,具有較好的平均查找性能。在Redis中,跳躍表用于有序集合(Sorted Set)數(shù)據(jù)類型的實現(xiàn),提供了高效的有序數(shù)據(jù)存儲和檢索功能。
跳躍表通過維護多級索引,每個級別的索引都是原始鏈表的子集,用于快速定位元素。每個節(jié)點在不同級別的索引中都有一個指針,通過這些指針,可以在不同級別上進行快速查找,從而提高了查找效率。
跳躍表的平均查找性能為O(log n),與平衡樹相當(dāng),但實現(xiàn)起來更加簡單。跳躍表通過多級索引來實現(xiàn)快速查找,使得查找時間隨著數(shù)據(jù)量的增加而呈對數(shù)增長。但是跳躍表的空間復(fù)雜度相對較高,因為它需要額外的空間來維護多級索引。不過跳躍表的空間占用通常是合理的,且具有可控性,可以根據(jù)實際需求調(diào)整級別和索引節(jié)點的數(shù)量,以平衡空間和性能的需求。
除此之外,跳躍表支持動態(tài)調(diào)整大小,可以根據(jù)實際需要自動擴展或收縮內(nèi)存空間。當(dāng)有序集合中的元素數(shù)量增加時,跳躍表會動態(tài)地增加級別和索引節(jié)點,以提高查找效率;當(dāng)元素數(shù)量減少時,可以收縮跳躍表的大小,以節(jié)省內(nèi)存資源。并且跳躍表的插入和刪除操作具有較高的效率,通過維護多級索引,可以在O(log n)的時間復(fù)雜度內(nèi)完成插入和刪除操作。
單線程模型
Redis中的單線程模型是指Redis在其核心數(shù)據(jù)處理部分采用單一的主線程來執(zhí)行網(wǎng)絡(luò)IO操作、接收客戶端命令請求、執(zhí)行命令操作以及返回結(jié)果。Redis服務(wù)端的網(wǎng)絡(luò)IO和鍵值對讀寫操作都由一個線程統(tǒng)一負責(zé),而諸如持久化、集群數(shù)據(jù)同步等任務(wù)則是由其他線程來執(zhí)行。在單線程模型下,Redis服務(wù)器是單線程運行的,即每個客戶端的請求都是依次順序執(zhí)行的。
而使用單線程所帶來的好處:
- 避免上下文切換:多線程環(huán)境下,線程間的上下文切換會帶來額外的CPU開銷。Redis通過單線程模型消除了多線程環(huán)境下的上下文切換成本,使得CPU資源更多地用于執(zhí)行實際的命令處理。
- 簡化數(shù)據(jù)操作的并發(fā)控制:單線程模型確保了同一時間內(nèi)只有一個操作在處理數(shù)據(jù),因此不需要使用鎖機制來保護數(shù)據(jù)的完整性,避免了多線程編程中常見的鎖競爭和死鎖問題,從而提高了系統(tǒng)的執(zhí)行效率。
- 內(nèi)存操作性能優(yōu)越:Redis是一個基于內(nèi)存操作的數(shù)據(jù)庫,大部分操作都在內(nèi)存中完成,本身就有很高的執(zhí)行速度。單線程模型下,內(nèi)存操作無需考慮并發(fā)控制,因此能夠?qū)崿F(xiàn)更高的內(nèi)存讀寫效率。
在日常開發(fā)中,我們通常會使用并發(fā)編程來提高服務(wù)的吞吐量。這時,我們可能會產(chǎn)生一個疑問:Redis的單線程模型是否能夠充分利用CPU資源呢?
實際上,由于Redis是基于內(nèi)存的操作,使用Redis時,CPU很少會成為瓶頸。相反,Redis主要受限于服務(wù)器內(nèi)存和網(wǎng)絡(luò)帶寬。例如,在典型的Linux系統(tǒng)上,通過使用pipelining技術(shù),Redis能夠?qū)崿F(xiàn)較高的吞吐量,每秒可以處理大量的請求。因此,如果應(yīng)用程序主要使用O(N)或O(log(N))的命令,它幾乎不會對CPU資源造成過多的負載。綜上所述,考慮到單線程模型的實現(xiàn)簡單且CPU很少成為瓶頸,因此采用單線程方案是合理的選擇。
單線程模型限制了Redis的并發(fā)能力。由于只有一個線程在處理請求,無法充分利用多核處理器的性能優(yōu)勢,所以可能到達服務(wù)端的請求不可能被立即處理。那么Redis是如何保證單線程的資源利用率和處理效率呢?
IO多路復(fù)用技術(shù):Redis通過使用IO多路復(fù)用技術(shù)(如epoll、kqueue或select等),在一個線程內(nèi)同時監(jiān)聽多個socket連接,當(dāng)有網(wǎng)絡(luò)事件發(fā)生時(如讀寫就緒),再逐一處理。這樣可以處理大量并發(fā)連接,并在單線程中高效地調(diào)度網(wǎng)絡(luò)事件,使得單線程也能應(yīng)對高并發(fā)場景。所以Redis服務(wù)端,整體來看,就是一個以事件驅(qū)動的程序,它的操作都是基于事件的方式進行的。Redis的事件驅(qū)動架構(gòu)如圖:
Redis的事件驅(qū)動架構(gòu)是一種基于非阻塞I/O多路復(fù)用技術(shù)設(shè)計的高效處理并發(fā)請求的機制。在Redis中,事件驅(qū)動架構(gòu)通過監(jiān)聽和處理各種網(wǎng)絡(luò)I/O事件以及定時事件,使得Redis服務(wù)端能夠在一個線程內(nèi)高效地服務(wù)于多個客戶端連接,并執(zhí)行相關(guān)的命令操作。
事件驅(qū)動架構(gòu)主要由以下幾個組成部分構(gòu)成:
- 套接字(Socket):套接字是客戶端與Redis服務(wù)端之間進行通信的基礎(chǔ)接口,用于雙向數(shù)據(jù)傳輸。
- I/O多路復(fù)用:Redis服務(wù)端通過使用如epoll、kqueue等I/O多路復(fù)用技術(shù),可以同時監(jiān)聽多個套接字上的讀寫事件。當(dāng)某個客戶端的套接字上有數(shù)據(jù)可讀或可寫時,內(nèi)核會通知Redis服務(wù)端,而無需Redis反復(fù)檢查每一個套接字狀態(tài)。
Redis默認使用的IO多路復(fù)用技術(shù)確實是epoll。其主要優(yōu)點如下:
- 并發(fā)連接限制相比于select和poll,epoll沒有預(yù)設(shè)的并發(fā)連接數(shù)限制,能夠處理的并發(fā)連接數(shù)只受限于系統(tǒng)資源,適合處理大規(guī)模并發(fā)連接。
- 內(nèi)存拷貝優(yōu)化epoll采用事件注冊機制,僅關(guān)注和通知就緒的文件描述符,無需像select和poll那樣在每次調(diào)用時都拷貝整個文件描述符集合,從而減少了內(nèi)存拷貝的開銷。
- 活躍連接感知epoll提供了水平觸發(fā)(level-triggered)和邊緣觸發(fā)(edge-triggered)兩種模式,可以更準確地感知活躍連接,僅當(dāng)有事件發(fā)生時才喚醒處理,避免了無效的輪詢操作,提升了事件處理的效率。
- 高效事件處理epoll利用紅黑樹存儲待監(jiān)控的文件描述符,并使用內(nèi)核層面的回調(diào)機制,當(dāng)有文件描述符就緒時,會直接通知應(yīng)用程序,從而減少了CPU空轉(zhuǎn)和上下文切換的成本。
- 文件事件分派器(File Event Demultiplexer):文件事件分派器是Redis事件驅(qū)動的核心組件,它負責(zé)將內(nèi)核傳遞過來的就緒事件分發(fā)給對應(yīng)的處理器。在Redis中,每個套接字都關(guān)聯(lián)了一個或多個事件處理器,如客戶端連接請求處理器、命令請求處理器和命令響應(yīng)處理器等。
- 事件處理器(Event Handlers):事件處理器是Redis中處理特定事件的實際執(zhí)行者。當(dāng)文件事件分派器接收到一個就緒事件時,它會調(diào)用對應(yīng)的事件處理器來執(zhí)行相應(yīng)操作,如讀取客戶端的命令請求,執(zhí)行命令并對結(jié)果進行編碼,然后將響應(yīng)數(shù)據(jù)寫回客戶端。
而對于Redis中設(shè)計的事件主要分為兩個大類:
- 文件事件(File Events):主要對應(yīng)網(wǎng)絡(luò)I/O操作,包括客戶端連接請求(AE_READABLE事件)、客戶端命令請求(AE_READABLE事件)和服務(wù)端命令回復(fù)(AE_WRITABLE事件)。
- 時間事件(Time Events):對應(yīng)定時任務(wù),如鍵值對過期檢查、持久化操作等。所有時間事件都被存放在一個無序鏈表中,每當(dāng)時間事件執(zhí)行器運行時,會遍歷鏈表并處理已到達預(yù)定時間的事件。
通過事件驅(qū)動架構(gòu),Redis能夠在一個線程內(nèi)并發(fā)處理大量客戶端請求,而無需為每個客戶端創(chuàng)建獨立的線程。此外,由于Redis的高效內(nèi)存管理、數(shù)據(jù)結(jié)構(gòu)優(yōu)化和單線程模型,避免了多線程環(huán)境下的鎖競爭和上下文切換開銷,從而實現(xiàn)了極高的吞吐量和響應(yīng)速度。
在Redis 6.x版本中,雖然引入了多線程處理網(wǎng)絡(luò)IO的部分,但核心命令執(zhí)行依然保持單線程事件驅(qū)動的模型,以維持Redis原有的性能優(yōu)勢。
IO多路復(fù)用模型
IO多路復(fù)用的核心在于內(nèi)核關(guān)注的是應(yīng)用程序的文件描述符而非直接監(jiān)控連接本身。客戶端運行時產(chǎn)生的不同事件類型的套接字操作,會被內(nèi)核捕獲。在服務(wù)器端,I/O多路復(fù)用機制負責(zé)收集這些事件并將它們加入事件隊列,隨后通過文件事件分發(fā)器分發(fā)至對應(yīng)事件處理器進行處理。
以Redis為例,在其單線程模型下,內(nèi)核不間斷地監(jiān)測所有客戶端socket的連接請求和數(shù)據(jù)傳輸狀況。只要檢測到任何socket上有待處理的動作,便會立即將控制權(quán)轉(zhuǎn)交給Redis線程。這樣一來,盡管僅依靠單線程,Redis仍能有效地處理多個并發(fā)的IO流。
select/epoll等IO多路復(fù)用技術(shù)提供了一種基于事件觸發(fā)的回調(diào)模式,每當(dāng)有不同事件發(fā)生時,Redis能夠迅速調(diào)用相應(yīng)的事件處理器,始終保持在處理事件的狀態(tài),從而提升了其響應(yīng)速度。
由于Redis線程并不會因為等待某個特定socket的IO操作完畢而停滯,它可以流暢地在多個客戶端間切換,即時響應(yīng)每個客戶端的不同請求,從而實現(xiàn)在單線程環(huán)境下對大量并發(fā)連接的有效處理和高并發(fā)性能。
簡單高效的通信協(xié)議
Redis Cluster在集群內(nèi)部通信中借鑒了Gossip協(xié)議的理念,采用了一種基于Gossip風(fēng)格的消息傳播機制。這種機制能夠有效地將集群狀態(tài)和節(jié)點信息在集群中的各個節(jié)點間進行快速傳播和同步。類比于流行病的傳播模型,Gossip協(xié)議允許節(jié)點隨機選擇鄰居節(jié)點進行通信,從而在全網(wǎng)狀結(jié)構(gòu)中快速傳播更新。
Redis Cluster、Consul和Apache Cassandra等分布式系統(tǒng)都采用了Gossip協(xié)議或者類似的機制來維護集群的健康狀態(tài)和一致性。通過Gossip協(xié)議,節(jié)點們可以高效地共享和更新集群的元數(shù)據(jù),如節(jié)點加入、離開、故障轉(zhuǎn)移等信息。
然而,純粹的Gossip協(xié)議在實踐中可能存在信息冗余的問題,即已接收到某一信息的節(jié)點在后續(xù)的傳播中可能會收到相同的信息。為了避免這種冗余和提高通信效率,這些系統(tǒng)通常會對Gossip協(xié)議進行優(yōu)化,例如在節(jié)點間記錄已知信息的狀態(tài),避免重復(fù)傳播已知的更新。即便如此,Gossip協(xié)議仍然是在大規(guī)模分布式系統(tǒng)中實現(xiàn)高可用性和強一致性的有效手段,其高效性體現(xiàn)在只需局部通信即可逐漸達成全局一致性,同時具備良好的擴展性和容錯性。
總結(jié)
最后,我們來總結(jié)一下,如何在面試中回答Redis為什么快的原因:
- 純內(nèi)存操作:Redis利用內(nèi)存進行數(shù)據(jù)存儲,其操作基于內(nèi)存讀寫,由于內(nèi)存訪問速度遠超硬盤,使得Redis在處理數(shù)據(jù)時具有極高的讀寫速度。特別是對于簡單的存取操作,由于線程在內(nèi)存中執(zhí)行的時間非常短,主要的時間消耗在于網(wǎng)絡(luò)I/O,因此Redis在處理大量快速讀寫請求時表現(xiàn)出卓越的性能。
- 單線程模型:Redis采用單線程模型處理客戶端請求,這一設(shè)計確保了操作的原子性,避免了多線程環(huán)境下的上下文切換和鎖競爭問題。這使得Redis在處理命令請求時能夠保持高度的確定性和一致性,同時也簡化了編程模型,降低了并發(fā)控制的復(fù)雜性。
- IO多路復(fù)用技術(shù):Redis通過采用IO多路復(fù)用模型,如epoll,能夠在一個線程中高效地處理多個客戶端連接。單線程輪詢監(jiān)聽多個套接字描述符,并將數(shù)據(jù)庫的讀、寫、連接建立和關(guān)閉等操作轉(zhuǎn)化為事件,通過自定義的事件分離器和事件處理器來高效地處理這些事件,從而避免了在等待IO操作時的阻塞。
- 高效數(shù)據(jù)結(jié)構(gòu):
- Redis的整體設(shè)計圍繞高效數(shù)據(jù)結(jié)構(gòu)展開,其中包括但不限于全局哈希表(字典),該結(jié)構(gòu)提供O(1)的平均時間復(fù)雜度,并通過rehash操作動態(tài)調(diào)整哈希桶數(shù)量,減少哈希沖突,采用漸進式rehash避免一次性操作過大導(dǎo)致的阻塞。
- 除此之外,Redis還廣泛應(yīng)用了多種優(yōu)化過的數(shù)據(jù)結(jié)構(gòu),如壓縮表(ziplist)用于存儲短數(shù)據(jù)以節(jié)省內(nèi)存,跳躍表(skiplist)用于有序集合提供快速的范圍查詢,以及其他如列表、集合等數(shù)據(jù)結(jié)構(gòu),均針對不同場景進行深度優(yōu)化,確保了在讀取和操作數(shù)據(jù)時的高性能。