持續原創輸出,點擊上方藍字關注我

目錄

• 前言
• 為什麼 Redis 這麼火？
• 鍵和值的保存形式？
• 為什麼哈希表操作變慢了？
• 集合的操作效率？

  • 有哪些數據結構？
  • 不同操作的複雜度？
• 總結

前言

現在一提到Redis的第一反應就是快、單線程，但是Redis真的快嗎？真的是單線程嗎？

你有沒有深入了解一下Redis，看看它的底層有哪些”慢動作”呢？

為什麼 Redis 這麼火？

Redis作為一個內存數據庫，它接收一個key到讀取數據幾乎是微妙級別，一個字快詮釋了它火的原因。另一方面就歸功於它的數據結構了，你知道Redis有哪些數據結構嗎？

很多人可能會說不就是String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）這五種嗎？我想大家可能有一種誤區，我說的是底層數據結構，而你說僅僅是數據的保存形式而已。

那麼Redis底層有哪幾種數據結構呢？和幾種數據保存形式的關係又是什麼呢？別著急，先通過一張圖了解下，如下圖：

通過上圖可以知道只有String對應的是一種數據結構，其他的數據類型對應的都是兩種數據結構，我們通常將這四種數據類型稱為集合類型，它們的特點是「一個鍵對應了一個集合的數據」。

既然數據本身是通過數據結構保存的，那麼鍵和值是什麼保存形式呢？

鍵和值的保存形式？

為了實現鍵和值的快速訪問，Redis使用的是哈希表來存放鍵，使用哈希桶存放值。

一個哈希表其實就是一個數組，數組的每個元素稱之為哈希桶。

所以，一個哈希表是由多個哈希桶組成，每個哈希桶中保存了鍵值對數據。

哈希桶中保存的並不是值，而是指向值的指針。

這也解釋了為什麼哈希桶能夠保存集合類型的數據了，也就是說不管是String還是集合類型，哈希桶保存的都是指向具體的值的指針，具體的結構如下圖：

從上圖可以看出，每個entry中保存的是*key和*value分別指向了鍵和值，這樣即使保存的值是集合類型也能通過指針 *value找到。

鍵是保存在哈希表中，哈希表的時間複雜度是O(1)，也就是無論多少個鍵，總能通過一次計算就找到對應的鍵。

但是問題來了，當你往Redis中寫入大量的數據就有可能發現操作變「慢」了，這就是一個典型的問題：「哈希衝突」。

為什麼哈希表操作變慢了？

既然底層用了哈希表，則哈希衝突是不可避免的，那什麼是哈希衝突呢？

Redis中的哈希衝突則是兩個或者多個key通過計算對應關係，正好落在了同一個哈希桶中。

這樣則導致了不同的key查找到的值是相同的，但是這種問題在Redis中顯然是不存在的，那麼Redis用了什麼方法解決了哈希衝突呢？

Redis底層使用了鏈式哈希的方式解決了哈希衝突，即是同一個哈希桶中的多個元素用一個鏈表保存，他們之間用指針*next相連。

此時的哈希表和鏈式哈希的結構如下圖：

從上圖可以看到，entry1、entry3、entry3都保存在哈希桶 1 中，導致了哈希衝突。但是此時的entry1中的*next指針指向了entry2，同樣entry2中的*next指針指向了entry3。這樣下來即使哈希桶中有很多個元素，也能通過這樣的方式連接起來，稱作哈希衝突鏈。

這裡存在一個問題：鏈表的查詢效率很低，如果哈希桶中元素很多，查找起來會很「慢」，顯然這個對於Redis來說是不能接受的。

Redis使用了一個很巧妙的方式：「漸進式 rehash」。那麼什麼是漸進是rehash呢？

想要理解漸進式rehash，首先需要理解下的rehash的過程。

rehash 也就是增加現有的哈希桶數量，讓逐漸增多的entry元素能在更多的桶之間分散保存，減少單個桶中的元素數量，從而減少單個桶中的衝突。

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

1. 給哈希表2分配更大的空間，例如是當前哈希表1大小的兩倍
2. 把哈希表1中的數據重新映射並拷貝到哈希表2 中
3. 釋放哈希表1 的空間。

以上這個過程結束，就可以釋放掉哈希表1的數據而使用哈希表2了，此時的哈希表1可以留作下次的rehash備用。

此時這裡存在一個問題：rehash整個過程的第 2 步涉及到大量的拷貝，一次性的拷貝數據肯定會造成線程阻塞，無法服務其他的請求。此時的Redis就無法快速訪問數據了。

為了避免一次性拷貝數據導致線程阻塞，Redis使用了漸進式rehash。

漸進式rehash則是rehash的第 2 步拷貝數據分攤到每個請求中，Redis 仍然正常服務，只不過在處理每次請求的時候，從哈希表1中索引1的位置將所有的entry拷貝到哈希表2中，下一個請求則從索引1的下一個的位置開始。

通過漸進式 rehash 巧妙的將一次性開銷分攤到各個請求處理的過程中，避免了一次性的耗時操作。

此時可能有人提出疑問了：「如果沒有請求，那麼Redis就不會rehash了嗎？」

Redis底層其實還會開啟一個定時任務，會定時的拷貝數據，即使沒有請求，rehash也會定時的在執行。

集合的操作效率？

如果是string，找到哈希桶中的entry則能正常的進行增刪改查了，但是如果是集合呢？即使通過指針找到了entry中的value,但是此時是一個集合，又是一個不同的數據結構，肯定會有不同的複雜度了。

集合的操作效率肯定是和集合底層的數據結構相關，比如使用哈希表實現的集合肯定要比使用鏈表實現的結合訪問效率要高。

接下來就來說說集合的底層數據結構和操作複雜度。

有哪些數據結構？

本文的第一張圖已經列出了集合的底層數據結構，主要有五種：整數數組、雙向鏈表、哈希表、壓縮列表和跳錶。

以上這五種數據結構都是比較常見的，如果讀者不是很了解具體的結構請閱讀相關的書籍，我就不再贅述了。

五種數據結構按照查找時間的複雜度分類如下：

不同操作的複雜度？

集合類型的操作類型很多，有讀寫單個集合元素的，例如 HGET、HSET，也有操作多個元素的，例如SADD，還有對整個集合進行遍歷操作的，例如 SMEMBERS。這麼多操作，它們的複雜度也各不相同。而複雜度的高低又是我們選擇集合類型的重要依據。

下文列舉了一些集合操作的複雜度，總共三點，僅供參考。

1. 單元素操作由底層數據結構決定

每一種集合類型對單元素的增刪改查操作這些操作的複雜度由集合採用的數據結構決定。例如，HGET、HSET 和HDEL 是對哈希表做操作，所以它們的複雜度都是O(1)；Set類型用哈希表作為底層數據結構時，它的SADD、SREM、SRANDMEMBER 複雜度也是 O(1)。

有些集合類型還支持一條命令同時對多個元素的操作，比如Hash類型的HMGET和HMSET。此時的操作複雜度則是O(N)。

2. 範圍操作非常耗時，應該避免

範圍操作是指集合類型中的遍歷操作，可以返回集合中的所有數據或者部分數據。比如List類型的HGETALL 和Set 類型的SMEMBERS，這類操作的複雜度為O(N)，比較耗時，應該避免。

不過Redis提供了Scan系列操作，比如HSCAN、SSCSCAN和ZSCAN,這類操作實現了漸進式遍歷，每次只返回有限數量的數據。這樣一來，相比於HGETALL、SMEMBERS 這類操作來說，就避免了一次性返回所有元素而導致的 Redis 阻塞。

3. 統計操作通常比較高效

統計操作是指對集合中的所有元素個數的記錄，例如LLEN 和SCARD。這類操作複雜度只有O(1)，這是因為當集合類型採用壓縮列表、雙向鏈表、整數數組這些數據結構時，這些結構中專門記錄了元素的個數統計，因此可以高效地完成相關操作。

總結

Redis之所以這麼快，不僅僅因為全部操作都在內存中，還有底層數據結構的支持，但是數據結構雖好，每種數據結構也有各種「慢」的情況，Redis結合各種數據結構的利弊，完善了整個運行機制。