面試：Redis為什么快呢？查詢為何會變慢呢？

越努力，越幸運，
本文已收藏在GitHub中JavaCommunity, 里面有面試分享、原始碼分析系列文章，歡迎收藏，點贊
https://github.com/Ccww-lx/JavaCommunity

在實際開發，Redis使用會頻繁，那么在使用程序中我們該如何正確抉擇資料型別呢？哪些場景下適用哪些資料型別，而且在面試中也很常會被面試官問到Redis資料結構方面的問題：

• Redis為什么快呢？
• 為什么查詢操作會變慢了？
• Redis Hash rehash程序
• 為什么使用哈希表作為Redis的索引

當我們分析理解了Redis資料結構，可以為了我們在使用Redis的時候，正確抉擇資料型別使用，提升系統性能，

Redis底層資料結構

Redis 是一個記憶體鍵值key-value 資料庫，且鍵值對資料保存在記憶體中，因此Redis基于記憶體的資料操作，其效率高，速度快；

其中，Key是String型別，Redis 支持的 value 型別包括了 String、List 、 Hash 、 Set 、 Sorted Set 、BitMap等，Redis 能夠之所以能夠廣泛地適用眾多的業務場景，基于其多樣化型別的value，

而Redis的Value的資料型別是基于為Redis自定義的物件系統redisObject實作的，

typedef struct redisObject{
    //型別
    unsigned type:4;
    //編碼
    unsigned encoding:4;
    //指向底層實作資料結構的指標
    void *ptr;
    ….. 
} 

redisObject除了記錄實際資料，還需要額外的記憶體空間記錄資料長度、空間使用等元資料資訊，其中包含了 8 位元組的元資料和一個 8 位元組指標，指標指向具體資料型別的實際資料所在位置：

?

其中，指標指向的就是基于Redis的底層資料結構存盤資料的位置，Redis的底層資料結構：SDS，雙向鏈表、跳表，哈希表，壓縮串列、整數集合實作的，

那么Redis底層資料結構是怎么實作的呢？

Redis底層資料結構實作

我們先來看看Redis比較簡單的**SDS,雙向鏈表，整數集合**，

SDS、雙向鏈表和整數集合

SDS，使用len欄位記錄已使用的位元組數，將獲取字串長度復雜度降低為O(1)，而且SDS是惰性釋放空間的，你free了空間，系統把資料記錄下來下次想用時候可直接使用，不用新申請空間，

整數集合，在記憶體中分配一塊地址連續的空間，資料元素會挨著存放，不需要額外指標帶來空間開銷，其特點為記憶體緊湊節省記憶體空間，查詢復雜度為O(1)效率高，其他操作復雜度為O(N)；

雙向鏈表， 在記憶體上可以為非連續、非順序空間，通過額外的指標開銷前驅/后驅指標串聯元素之間的順序，

其特點為節插入/更新資料復雜度為O(1)效率高，查詢復雜度為O(N)；

Hash哈希表

哈希表，其實類似是一個陣列，陣列的每個元素稱為一個哈希桶，每個哈希桶中保存了鍵值對資料，且哈希桶中的元素使用dictEntry結構，

因此，哈希桶元素保存的并不是鍵值對值本身，而是指向具體值的指標，**所以在保存每個鍵值對的時候會額外空間開銷，至少有增加24個位元組，**特別是Value為String的鍵值對，每一個鍵值對就需要額外開銷24個位元組空間，當保存資料小，額外開銷比資料還大時，這時為了節省空間，考慮換資料結構，

那來看看全域哈希表全圖：

雖然哈希表操作很快，但Redis資料變大后，就會出現一個潛在的風險：哈希表的沖突問題和 rehash開銷問題，這可以解釋為什么哈希表操作變慢了？

當往哈希表中寫入更多資料時，哈希沖突是不可避免的問題 ， Redis 解決哈希沖突的方式，就是鏈式哈希，同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指標連接，如圖所示：

當哈希沖突也會越來越多，這就會導致某些哈希沖突鏈過長，進而導致這個鏈上的元素查找耗時長，效率降低，

為了解決哈希沖突帶了的鏈過長的問題，進行rehash操作，增加現有的哈希桶數量，分散單桶元素數量，那么rehash程序怎么樣執行的呢？

Rehash

為了使rehash 操作更高效，使用兩個全域哈希表：哈希表 1 和哈希表 2，具體如下：

• 將哈希表 2 分配更大的空間，
• 把哈希表 1 中的資料重新映射并拷貝到哈希表 2 中；
• 釋放哈希表 1 的空間

但由于表1和表2在重新映射復制時資料大，如果一次性把哈希表 1 中的資料都遷移完，會造成 Redis 執行緒阻塞，無法服務其他請求，

為了避免這個問題，保證Redis能正常處理客戶端請求，Redis采用了漸進式rehash，

每處理一個請求時，從哈希表 1 中依次將索引位置上的所有 entries 拷貝到哈希表 2 中，把一次性大量拷貝的開銷，分攤到了多次處理請求的程序中，避免了耗時操作，保證了資料的快速訪問，

在理解完Hash哈希表相關知識點后，看看不常見的壓縮串列和跳表，

壓縮串列與跳表

壓縮串列，在陣列基礎上，在壓縮串列在表頭有三個欄位 zlbytes、zltail 和 zllen，分別表示串列長度、串列尾的偏移量和串列中的 entry 個數；壓縮串列在表尾還有一個 zlend，表示串列結束，

優點：記憶體緊湊節省記憶體空間，記憶體中分配一塊地址連續的空間，資料元素會挨著存放，不需要額外指標帶來空間開銷；查找定位第一個元素和最后一個元素，可以通過表頭三個欄位的長度直接定位，復雜度是 O(1)，

跳表 ，在鏈表的基礎上，增加了多級索引，通過索引位置的幾個跳轉，實作資料的快速定位，如下圖所示：

比如查詢33

特點：當資料量很大時，跳表的查找復雜度為O(logN)，

綜上所述，可以得知底層資料結構的時間復雜度：

Redis自定義的物件系統型別即為Redis的Value的資料型別，Redis的資料型別是基于底層資料結構實作的，那資料型別有哪些呢？

Redis資料型別

String、List、Hash、Sorted Set、Set比較常見的型別，其與底層資料結構對應關系如下：

資料型別對應特點跟其實作的底層資料結構差不多，性質也是一樣的,且

String，基于SDS實作，適用于簡單key-value存盤、setnx key value實作分布式鎖、計數器(原子性)、分布式全域唯一ID，

List， 按照元素進入List的順序進行排序的，遵循FIFO(先進先出)規則，一般使用在 排序統計以及簡單的訊息佇列，

Hash， 是字串key和字串value之間的映射，十分適合用來表示一個物件資訊 ，特點添加和洗掉操作復雜度都是O(1)，

Set，是String 型別元素的無序集合，集合成員是唯一的，這就意味著集合中不能出現重復的資料， 基于哈希表實作的，所以添加，洗掉，查找的復雜度都是 O(1)，

Sorted Set， 是Set的型別的升級， 不同的是每個元素都會關聯一個 double 型別的分數，通過分數排序，可以范圍查詢，

那我們再來看看這些資料型別，Redis Geo、HyperLogLog、BitMap？

Redis Geo， 將地球看作為近似為球體，基于GeoHash 將二維的經緯度轉換成字串，來實作位置的劃分跟指定距離的查詢，特點一般使用在跟位置有關的應用，

HyperLogLog， 是一種概率資料結構，它使用概率演算法來統計集合的近似基數 ， 錯誤率大概在0.81%， 當集合元素數量非常多時，它計算基數所需的空間總是固定的，而且還很小，適合使用做 UV 統計，

BitMap ，用一個位元位來映射某個元素的狀態， 只有 0 和 1 兩種狀態，非常典型的二值狀態，且其本身是用 String 型別作為底層資料結構實作的一種統計二值狀態的資料型別 ，優勢大量節省記憶體空間，可是使用在二值統計場景，

在理解上述知識后，我們接下來討論一下根據哪些策略選擇相對應的應用場景下的Redis資料型別？

選擇合適的Redis資料型別策略

在實際開發應用中，Redis可以適用于眾多的業務場景，但我們需要怎么選擇資料型別存盤呢？

主要依據就是時間/空間復雜度，在實際的開發中可以考慮以下幾個點：

• 資料量，資料本身大小
• 集合型別統計模式
• 支持單點查詢/范圍查詢
• 特殊使用場景

資料量，資料本身大小

當資料量比較大，資料本身比較小，使用**String**就會使用額外的空間大大增加，因為使用哈希表保存鍵值對，使用dictEntry結構保存，會導致保存每個鍵值對時額外保存dictEntry的三個指標的開銷，這樣就會導致資料本身小于額外空間開銷，最侄訓導致存盤空間資料大小遠大于原本資料存盤大小，

可以使用基于整數陣列和壓縮串列實作了 List、Hash 和 Sorted Set ，因為整數陣列和壓縮串列在記憶體中都是分配一塊地址連續的空間，然后把集合中的元素一個接一個地放在這塊空間內，非常緊湊，不用再通過額外的指標把元素串接起來，這就避免了額外指標帶來的空間開銷，而且采用集合型別時，一個 key 就對應一個集合的資料，能保存的資料多了很多，但也只用了一個 dictEntry，這樣就節省了記憶體，

集合型別統計模式

Redis集合型別統計模式常見的有：

• 聚合統計（ 交集、差集、并集統計 ）： 對多個集合進行聚合計算時，可以選擇Set；
• 排序統計（要求集合型別能對元素保序）： Redis中List 和 Sorted Set是有序集合，List是按照元素進入 List 的順序進行排序的，Sorted Set 可以根據元素的權重來排序；
• 二值狀態統計（ 集合元素的取值就只有 0 和 1 兩種 ）：Bitmap 本身是用 String 型別作為底層資料結構實作的一種統計二值狀態的資料型別 ， Bitmap通過 BITOP 按位 與、或、異或的操作后使用 BITCOUNT 統計 1 的個數，
• 基數統計（ 統計一個集合中不重復的元素的個數 ）：HyperLogLog 是一種用于統計基數的資料集合型別 ，統計結果是有一定誤差的，標準誤算率是 0.81% ，需要精確統計結果的話，用 Set 或 Hash 型別，

Set型別，適用統計用戶/好友/關注/粉絲/感興趣的人集合聚合操作，比如

• 統計手機APP每天的新增用戶數
• 兩個用戶的共同好友

Redis中List 和 Sorted Set是有序集合，使用應對集合元素排序需求 ，比如

• 最新評論串列
• 排行榜

Bitmap二值狀態統計，適用資料量大，且可以使用二值狀態表示的統計，比如：

• 簽到打卡，當天用戶簽到數
• 用戶周活躍
• 用戶在線狀態

HyperLogLog 是一種用于統計基數的資料集合型別， 統計一個集合中不重復的元素個數 ，比如

• 統計網頁的 UV ， 一個用戶一天內的多次訪問只能算作一次

支持單點查詢/范圍查詢

Redis中List 和 Sorted Set是有序集合支持范圍查詢，但是Hash是不支持范圍查詢的

特殊使用場景

訊息佇列，使用Redis作為訊息佇列的實作，要訊息的基本要求訊息保序、處理重復的訊息和保證訊息可靠性，方案有如下：

• 基于 List 的訊息佇列解決方案
• 基于 Streams 的訊息佇列解決方案

基于位置 LBS 服務，使用Redis的特定GEO資料型別實作，GEO 可以記錄經緯度形式的地理位置資訊，被廣泛地應用在 LBS 服務中， 比如:打車軟體是怎么基于位置提供服務的，

總結

Redis之所以那么快，是因為其基于記憶體的資料操作和使用Hash哈希表作為索引，其效率高，速度快，而且得益于其底層資料多樣化使得其可以適用于眾多場景，不同場景中選擇合適的資料型別可以提升其查詢性能，

謝謝各位點贊，沒點贊的點個贊支持支持
最后，微信搜《Ccww技術博客》觀看更多文章，也歡迎關注一波，