Redis 是如何保證高效查詢的？

爲什麼 Redis 比較快

Redis 中的查詢速度爲什麼那麼快呢？

1、因爲它是內存數據庫；

2、歸功於它的數據結構；

3、Redis 中是單線程；

4、Redis 中使用了多路複用。

Redis 中的數據結構

這裏借用一張來自 [Redis 核心技術與實戰] Redis 中數據結構和底層結構的對應圖片

1、簡單動態字符串

Redis 中並沒有使用 C 中 char 來表示字符串，而是引入了 簡單動態字符串（Simple Dynamic Strings，SDS）來存儲字符串和整型數據。那麼 SDS 對比傳統的字符串有什麼優點呢？

先來看下 SDS 的結構

struct sdshdr {
    // 記錄 buf 數組中已使用字節的數量
    // 等於 SDS 保存字符串的長度，不包含'\0'
    long len;
    
    // 記錄buf數組中未使用字節的數量
    long free;
    
    // 字節數組，用於保存字符串
    char buf[];
};

舉個栗子：

使用 SDS 存儲了一個字符串 hello, 對應的 len 就是 5，同時也申請了 5 個爲未使用的空間，所以 free 就是 5。

在 3.2 版本後，sds 會根據字符串實際的長度，選擇不同的數據結構，以更好的提升內存效率。當前 sdshdr 結構分爲 5 種子類型，分別爲 sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。其中 sdshdr5 只有 flags 和 buf 字段，其他幾種類型的 len 和 alloc 採用從 uint8_t 到 uint64_t 的不同類型，以節省內存空間。

SDS 對比 c 字符串的優勢
SDS 可以常數級別獲取字符串的長度

因爲結構裏面已經記錄了字符串的長度，所以獲取字符串的長度複雜度爲 O(1)，c 中字符串沒記錄長度，需要遍歷整個長度，複雜度爲 O(N)。

杜絕緩衝區溢出

如果在修改字符的時候，沒有分配足夠的內存大小，就很容易造成緩存溢出，內存越界。

strcat 函數常見的錯誤就是數組越界，即兩個字符串連接後，長度超過第一個字符串數組定義的長度，導致越界。

SDS 中的空間分配策略可以杜絕這種情況，當對 SDS 進行修改時，API 會檢查 SDS 的空間是否滿足修改所需的要求，如果不滿足的話，API 會自動將 SDS 的空間擴展至執行修改所需的大小，然後才執行實際的修改操作。空間的申請是自動完成的，所以就避免了緩存溢出。

減少修改字符串時帶來的內存分配次數

對於 C 字符串來說，如果修改字符串的長度，都需要重新執行內存分配操作；但是對於 Redis 數據庫來說，如果頻繁執行內存分配 / 釋放操作，必然會對性能產生一定影響。爲了避免 C 字符串的缺陷，SDS 採用了空間預分配和惰性空間釋放兩種優化策略。

空間預分配

空間預分配用於優化 SDS 的字符串增長操作，當 SDS 的 api 對 SDS 進行修改，同時需要進行空間擴展的時候，除了會給 SDS 分配修改需要的空間，同時還會給 SDS 分配額外的未使用空間。

1、如果對 SDS 修改之後，SDS 的長度小於1MB, 那麼程序分配和 len 同樣大小的未使用空間，也就是這時候 SDS 中的 len 和 free 長度相同；

2、如果對 SDS 修改之後，SDS 的長度大於等於1MB, 那麼程序分配1MB的未使用空間。

在對 SDS 空間進行擴展的時候，首先會判斷未使用空間的大小是否能滿足要求，如果足夠，就不用在進行內存分配了，這樣能夠減少內存的重新分配的次數。

惰性空間釋放

惰性空間釋放用於優化 SDS 字符串的縮短操作，當 SDS 的 API 需要縮短 SDS 保護的字符串時，程序並不會立即使用內存重分配來回收縮短後多出來的內存，而是使用 free 屬性將這些字節的數量記錄起來，等待之後的重新使用。

二進制安全

對於 C 字符串來說，字符串中不能包含空字符，否則最先被程序讀入的空字符串被誤認爲是字符串結尾，這使得 C 字符串只能保存文本數據，而不能保存圖片、音視頻等二進制文件。對於 SDS 來說，所有 SDS 都會以處理二進制的方式來處理 SDS 保存在 buf 數組中的內容，程序不會對裏面的內容做任何限制。

兼容部分 C 字符串函數

SDS 末尾設置空字符的操作使得它可以和部分 C 字符串函數兼容。

2、鏈表

鏈表是一種很常見的數據結構，在很多高級語言中都能看到，Redis 中的 list 就用到了雙向鏈表，當一個列表鍵包含了數量比較多的元素，或者是列表中包含的元素都是比較長的字符串的時，Redis 就會使用鏈表作爲 list 的底層實現。

這裏雙向鏈表不展開討論了。

3、字典

redisDb 主要包括 2 個核心 dict 字典、3 個非核心 dict 字典、dbID 和其他輔助屬性。2 個核心 dict 包括一個 dict 主字典和一個 expires 過期字典。主 dict 字典用來存儲當前 DB 中的所有數據，它將 key 和各種數據類型的 value 關聯起來，該 dict 也稱 key space。過期字典用來存儲過期時間 key，存的是 key 與過期時間的映射。日常的數據存儲和訪問基本都會訪問到 redisDb 中的這兩個 dict。

所以對於任何類型的數據查詢都需要經過一次 dict 的查詢，也就是 hash 的過程。通過這個 dict 將 key 映射到對應的數據類型的 value 中。

3 個非核心 dict 包括一個字段名叫 blocking_keys 的阻塞 dict，一個字段名叫 ready_keys 的解除阻塞 dict，還有一個是字段名叫 watched_keys 的 watch 監控 dict。

Redis 的字典使用哈希表作爲底層實現，一個哈希表裏面可以有多個哈希節點，每個哈希表節點就保存了字典中的一個鍵值對。

使用哈希表就難免遇到哈希碰撞，兩個 key 的哈希值和哈希桶計算對應關係時，正好落在了同一個哈希桶中。

Redis 解決哈希衝突的方式，就是鏈式哈希。鏈式哈希也很容易理解，就是指同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指針連接。

隨着寫入的消息越來越多，哈希衝突的幾率也隨之升高，這時候就需要對哈希表進行擴容，Redis 中的擴容使用的是漸進式 rehash。

其實，爲了使 rehash 操作更高效，Redis 默認使用了兩個全局哈希表：哈希表 1 和哈希表 2。一開始，當你剛插入數據時，默認使用哈希表 1，此時的哈希表 2 並沒有被分配空間。隨着數據逐步增多，Redis 開始執行 rehash，這個過程分爲三步：

1、給哈希表 2 分配更大的空間，例如是當前哈希表 1 大小的兩倍；

2、把哈希表 1 中的數據重新映射並拷貝到哈希表 2 中；

3、釋放哈希表 1 的空間。

當然數據很大的話，一次遷移所有的數據，顯然是不合理的，會造成 Redis 線程阻塞，無法服務其他請求。這裏 Redis 使用的是漸進式 rehash。

在 rehash 期間，每次執行添加，刪除，查找或者更新操作時，除了對命令本身的處理，還會順帶將哈希表 1 中的數據拷貝到哈希表 2 中。從索引 0 開始，每執行一次操作命令，拷貝一個索引位置的數據。

在進行 rehash 期間，刪除，查找或者更新操作都會在兩個哈希表中執行，添加操作就直接添加到哈希表 2 中了。查找會把兩個哈希表都找一遍，直到找到或者兩個都找不到。

4、跳錶

其中 Redis 中的有序集合就是使用跳錶來實現的

對於一個單鏈表來講，即便鏈表中存儲的數據是有序的，如果我們要想在其中查找某個數據，也只能從頭到尾遍歷鏈表。這樣查找效率就會很低，時間複雜度會很高，是 O(n)。

鏈表加多級索引的結構，就是跳錶, 跳錶查詢的時間複雜度是O(logn)。通過在每個節點中維持多個指向其他節點的指針，從而實現快速訪問的節點的目的。

5、整數數組

整數集合 (intset) 是集合鍵的底層實現之一，當一個集合只包含整數值元素，並且這個集合的元素數量不多時，Redis 就會使用整數集合作爲集合鍵的底層實現。是 Redis 用戶保存整數值的集合抽象數據結構，可以保存的類型是int16_t,int32_t,int64_t的整數值，並且保證集合中不會出現重複的元素。

typedef struct intset{
    // 編碼方法，指定當前存儲的是 16 位，32 位，還是 64 位的整數
    int32 encoding;
    // 集合中的元素數量
    int32 length;
    // 保存元素的數組
    int<T> contents;
}

這樣看，這個集合倒也沒有什麼特殊的點。這時候需要來看下整數集合的升級。

每當一個整數被添加到整數集合時，首先需要判斷下 新元素的類型和集合中現有元素類型的長短，如果新元素是一個 32 位的數字，現有集合類型是 16 位的，那麼就需要將整數集合進行升級，然後才能將新的元素加入進來。

這樣做的優點：

1、提升整數集合的靈活性，可以隨意的添加整數，而不用關心整數的類型；

2、可以儘可能的節約內存。

缺點：

不支持降級，一旦對數組進行了升級，就會一直保持升級後的狀態。

6、壓縮列表

壓縮列表 (ziplist) 是列表鍵和哈希鍵的底層實現之一。當一個元素只包含少量的列表項，並且每個列表項是小整數值或者是長度比較短的字符串, redis 就會使用壓縮列表來作爲列表鍵的底層實現。

壓縮列表 (ziplist) 的目的是爲了節約內存，通過一片連續的內存空間來存儲數據。這樣看起來好像和數組很像，數組中每個節點的內存大小是一樣的，對於壓縮列表，每個節點的內存大小是不同的，每個節點可以保存字節數組或一個整數值。通過可變的節點內存大小，來節約內存的使用。

ziplist 的結構：

1、zlbytes : 是壓縮列表所佔用的總內存字節數;

2、Zltail : 尾節點到起始位置的字節數，（目的是爲了直接定位到尾節點，方便反向查詢）;

3、Zllen : 總共包含的節點 / 內存塊數，也就是壓縮列表的節點數量;

4、Entry : 是 ziplist 保存的各個數據節點，這些數據點長度隨意;

5、Zlend : 是一個魔數 255，用來標記壓縮列表的結束。

由於 ziplist 是連續緊湊存儲，沒有冗餘空間，所以插入新的元素需要 realloc 擴展內存，所以如果 ziplist 佔用空間太大，realloc 重新分配內存和拷貝的開銷就會很大，所以 ziplist 不適合存儲過多元素，也不適合存儲過大的字符串。

因此只有在元素數和 value 數都不大的時候，ziplist 才作爲 hash 和 zset 的內部數據結構。其中 hash 使用 ziplist 作爲內部數據結構的限制時，元素數默認不超過 512 個，value 值默認不超過 64 字節。可以通過修改配置來調整 hash_max_ziplist_entries 、hash_max_ziplist_value 這兩個閥值的大小。

zset 有序集合，使用 ziplist 作爲內部數據結構的限制元素數默認不超過 128 個，value 值默認不超過 64 字節。可以通過修改配置來調整 zset_max_ziplist_entries 和 zset_max_ziplist_value 這兩個閥值的大小。

在壓縮列表中，如果我們要查找定位第一個元素和最後一個元素，可以通過表頭三個字段的長度直接定位，複雜度是 O(1)。而查找其他元素時，就沒有這麼高效了，只能逐個查找，此時的複雜度就是 O(N) 了。

連鎖更新

壓縮列表 ziplist 的存儲節點 Entry 數據節點的結構：

1、previous_entry_length : 記錄了前一個節點的長度

2、encoding : 記錄了節點的 content 屬性所保存數據的類型以及長度

3、content : 節點的 content 屬性負責保存節點的值， 節點值可以是一個字節數組或者整數， 值的類型和長度由節點的 encoding 屬性決定。

舉個栗子：

如果壓縮列表中每個節點的長度都是 250，因爲是小於 254，所以每個節點中的 previous_entry_length 長度 1 字節就能夠保存了。

這時候，在頭部節點插入了一個新的元素 entryNew，然後長度是大於 254，那麼後面的節點中 entry1 的 previous_entry_length 長度爲 1 字節，就不能保存了，需要擴容成 5 字節，然後 entry1 節點進行擴容了，變成了 254，所以後面的節點也就需要一次擴容，這就引發一連串的擴容。也就是連鎖更新。

爲什麼單線程還能很快

Redis 是單線程，主要是指 Redis 的網絡 IO 和鍵值對讀寫是由一個線程來完成的，這也是 Redis 對外提供鍵值存儲服務的主要流程。

多線程必然會面臨對於共享資源的訪問，這時候通常的做法就是加鎖，雖然是多線程，這時候就會變成串行的訪問。也就是多線程編程模式會面臨的共享資源的併發訪問控制問題。

同時多線程也會引入同步原語來保護共享資源的併發訪問，代碼的可維護性和易讀性將會下降。

基於多路複用的高性能 I/O 模型

首先，Redis 是跑在單線程中的，所有的操作都是按照順序線性執行的，但是由於讀寫操作等待用戶輸入或輸出都是阻塞的，所以 I/O 操作在一般情況下往往不能直接返回，這會導致某一文件的 I/O 阻塞導致整個進程無法對其它客戶提供服務，而 I/O 多路複用 就是爲了解決這個問題而出現的。

Linux 中的 IO 多路複用機制是指一個線程處理多個 IO 流。多路是指網絡連接，複用指的是同一個線程。簡單來說，在 Redis 只運行單線程的情況下，該機制允許內核中，同時存在多個監聽套接字和已連接套接字。內核會一直監聽這些套接字上的連接請求或數據請求。一旦有請求到達，就會交給 Redis 線程處理，這就實現了一個 Redis 線程處理多個 IO 流的效果。

文件事件是對連接 socket 操作的一個抽象。當端口監聽 socket 準備 accept 新連接，或者連接 socket 準備好讀取請求、寫入響應、關閉時，就會產生一個文件事件。IO 多路複用程序負責同時監聽多個 socket，當這些 socket 產生文件事件時，就會觸發事件通知，文件分派器就會感知並獲取到這些事件。

雖然多個文件事件可能會併發出現，但 IO 多路複用程序總會將所有產生事件的 socket 放入一個隊列中，通過這個隊列，有序的把這些文件事件通知給文件分派器。

文件事件分派器接收 I/O 多路複用程序傳來的套接字，並根據套接字產生的事件類型，調用相應的事件處理器。

服務器會爲執行不同任務的套接字關聯不同的事件處理器，這些處理器是一個個的函數，他們定義了這個事件發生時，服務器應該執行的動作。

Redis 封裝了 4 種多路複用程序，每種封裝實現都提供了相同的 API 實現。編譯時，會按照性能和系統平臺，選擇最佳的 IO 多路複用函數作爲底層實現，選擇順序是，首先嚐試選擇 Solaries 中的 evport，如果沒有，就嘗試選擇 Linux 中的 epoll，否則就選擇大多 UNIX 系統都支持的 kqueue，這 3 個多路複用函數都直接使用系統內核內部的結構，可以服務數十萬的文件描述符。

如果當前編譯環境沒有上述函數，就會選擇 select 作爲底層實現方案。select 方案的性能較差，事件發生時，會掃描全部監聽的描述符，事件複雜度是 O(n)，並且只能同時服務有限個文件描述符，32 位機默認是 1024 個，64 位機默認是 2048 個，所以一般情況下，並不會選擇 select 作爲線上運行方案。

單線程處理 IO 請求性能瓶頸

1、後臺 Redis 通過監聽處理事件隊列中的消息，來單線程的處理命令，如果一個命令的執行時間很久，就會影響整個 server 的性能；

耗時的操作命令有下面幾種：

上面的這幾種問題，我們在寫業務的時候需要去避免，對於 bigkey，Redis 在 4.0 推出了 lazy-free 機制，把 bigkey 釋放內存的耗時操作放在了異步線程中執行，降低對主線程的影響。

2、併發量非常大時，單線程讀寫客戶端 IO 數據存在性能瓶頸

使用 Redis 時，幾乎不存在 CPU 成爲瓶頸的情況， Redis 主要受限於內存和網絡。隨着硬件水平的提升，Redis 中的性能慢慢主要出現在網絡 IO 的讀寫上。雖然採用 IO 多路複用機制，但是讀寫客戶端數據依舊是同步 IO，只能單線程依次讀取客戶端的數據，無法利用到 CPU 多核。

爲了提升網絡 IO 的讀寫性能，Redis 在 6.0 推出了多線程，同過多線程的 IO 來處理網絡請求。不過需要注意的是這裏的多線程僅僅是針對客戶端的讀寫是並行的，Redis 處理事件隊列中的命令，還是單線程處理的。

總結

Redis 使用單線程，來避免共享資源的競爭，使用多路複用實現高性能的 I/O，它是內存數據庫，所有操作都在內存上完成，使用哈希表，跳錶等一系列高效的數據結構，這些特性保證了 Redis 的高性能。

參考

【Redis 核心技術與實戰】https://time.geekbang.org/column/intro/100056701
【Redis6.0 爲什麼引入多線程？】https://juejin.cn/post/7004683161695158309
【Redis 設計與實現】https://book.douban.com/subject/25900156/
【redis---sds（簡單動態字符串）詳解】https://blog.csdn.net/u010765526/article/details/89065607
【爲什麼 Redis 的查詢很快】https://boilingfrog.github.io/2022/01/07 / 爲什麼 redis 的查詢比較快 /
【redis 知識點】https://github.com/boilingfrog/Go-POINT/tree/master/redis

作者：ZhanLi

來源：www.cnblogs.com/ricklz/p/15839710.html

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/uCK-1fS4DzpKxQX67-CmWw

猜你喜歡