當談到 redis 時，我們通常會聯(lián)想到一個關(guān)鍵詞：“速度”。然而，你是否曾思考過 Redis 之所以如此迅猛，到底在哪里呢？實際上，這其中有一個關(guān)鍵特性：Redis 能夠在微秒級別內(nèi)找到數(shù)據(jù)并快速執(zhí)行操作。
那么，Redis 為何在眾多數(shù)據(jù)庫中脫穎而出呢？這其中有幾個關(guān)鍵因素。首先，Redis 是一種內(nèi)存數(shù)據(jù)庫，它的所有操作都在內(nèi)存中進行，而內(nèi)存的訪問速度本身就非常快。此外，Redis 還依賴于高效的數(shù)據(jù)結(jié)構(gòu)。這是因為 Redis 的鍵值對實際上是按照特定的數(shù)據(jù)結(jié)構(gòu)組織的，因此鍵值對的操作實際上是對數(shù)據(jù)結(jié)構(gòu)進行增刪改查操作，高效的數(shù)據(jù)結(jié)構(gòu)是 Redis 處理數(shù)據(jù)的基礎(chǔ)。在這節(jié)課中，我們將深入探討這些數(shù)據(jù)結(jié)構(gòu)。
也許你會說：“這些我都知道，這不就是 Redis 的數(shù)據(jù)類型嗎？包括字符串、列表、哈希、集合和有序集合？”不過，這些只是 Redis 鍵值對中值的數(shù)據(jù)類型，也就是數(shù)據(jù)的存儲方式。而在這里，我們所說的數(shù)據(jù)結(jié)構(gòu)，指的是要深入了解它們的底層實現(xiàn)原理。
以簡單明了的方式來描述，總共有 6 種底層數(shù)據(jù)結(jié)構(gòu)，它們與數(shù)據(jù)類型之間存在如下對應(yīng)關(guān)系，具體如下圖所示：
可以看到，String 類型的底層實現(xiàn)只有一種數(shù)據(jù)結(jié)構(gòu)，也就是簡單動態(tài)字符串。而 List、Hash、Set 和 Sorted Set 這四種數(shù)據(jù)類型，都有兩種底層實現(xiàn)結(jié)構(gòu)。通常情況下，我們會把這四種類型稱為集合類型，它們的特點是一個鍵對應(yīng)了一個集合的數(shù)據(jù)。
看到這里，其實有些問題已經(jīng)值得我們?nèi)タ紤]了：
- 這些數(shù)據(jù)結(jié)構(gòu)都是值的底層實現(xiàn)，鍵和值本身之間用什么結(jié)構(gòu)組織？
- 為什么集合類型有那么多的底層結(jié)構(gòu)，它們都是怎么組織數(shù)據(jù)的，都很快嗎？
- 什么是簡單動態(tài)字符串，和常用的字符串是一回事嗎？
接下來，我就和你聊聊前兩個問題。這樣，你不僅可以知道 Redis“快”的基本原理，還可以借此理解 Redis 中有哪些潛在的“慢操作”，最大化 Redis 的性能優(yōu)勢。而關(guān)于簡單動態(tài)字符串，我會在后面的課程中再和你討論。
我們先來看看鍵和值之間是用什么結(jié)構(gòu)組織的。
鍵和值用什么結(jié)構(gòu)組織？
為了實現(xiàn)從鍵到值的快速訪問，Redis 使用了一個哈希表來保存所有鍵值對。
一個哈希表，其實就是一個數(shù)組，數(shù)組的每個元素稱為一個哈希桶。所以，我們常說，一個哈希表是由多個哈希桶組成的，每個哈希桶中保存了鍵值對數(shù)據(jù)。
看到這里，你可能會問了：“如果值是集合類型的話，作為數(shù)組元素的哈希桶怎么來保存呢？”其實，哈希桶中的元素保存的并不是值本身，而是指向具體值的指針。這也就是說，不管值是 String，還是集合類型，哈希桶中的元素都是指向它們的指針。
在下圖中，可以看到，哈希桶中的 entry 元素中保存了*key和*value指針，分別指向了實際的鍵和值，這樣一來，即使值是一個集合，也可以通過*value指針被查找到。
因為這個哈希表保存了所有的鍵值對，所以，我也把它稱為全局哈希表。哈希表的最大好處很明顯，就是讓我們可以用 O(1) 的時間復(fù)雜度來快速查找到鍵值對——我們只需要計算鍵的哈希值，就可以知道它所對應(yīng)的哈希桶位置，然后就可以訪問相應(yīng)的 entry 元素。
你看，這個查找過程主要依賴于哈希計算，和數(shù)據(jù)量的多少并沒有直接關(guān)系。也就是說，不管哈希表里有 10 萬個鍵還是 100 萬個鍵，我們只需要一次計算就能找到相應(yīng)的鍵。
但是，如果你只是了解了哈希表的 O(1) 復(fù)雜度和快速查找特性，那么，當你往 Redis 中寫入大量數(shù)據(jù)后，就可能發(fā)現(xiàn)操作有時候會突然變慢了。這其實是因為你忽略了一個潛在的風(fēng)險點，那就是哈希表的沖突問題和 rehash 可能帶來的操作阻塞。
為什么哈希表操作變慢了？
當你往哈希表中寫入更多數(shù)據(jù)時，哈希沖突是不可避免的問題。這里的哈希沖突，也就是指，兩個 key 的哈希值和哈希桶計算對應(yīng)關(guān)系時，正好落在了同一個哈希桶中。
畢竟，哈希桶的個數(shù)通常要少于 key 的數(shù)量，這也就是說，難免會有一些 key 的哈希值對應(yīng)到了同一個哈希桶中。
Redis 解決哈希沖突的方式，就是鏈式哈希。鏈式哈希也很容易理解，就是指同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指針連接。
如下圖所示：entry1、entry2 和 entry3 都需要保存在哈希桶 3 中，導(dǎo)致了哈希沖突。此時，entry1 元素會通過一個*next指針指向 entry2，同樣，entry2 也會通過*next指針指向 entry3。這樣一來，即使哈希桶 3 中的元素有 100 個，我們也可以通過 entry 元素中的指針，把它們連起來。這就形成了一個鏈表，也叫作哈希沖突鏈。
但是，這里依然存在一個問題，哈希沖突鏈上的元素只能通過指針逐一查找再操作。如果哈希表里寫入的數(shù)據(jù)越來越多，哈希沖突可能也會越來越多，這就會導(dǎo)致某些哈希沖突鏈過長，進而導(dǎo)致這個鏈上的元素查找耗時長，效率降低。對于追求“快”的 Redis 來說，這是不太能接受的。
所以，Redis 會對哈希表做 rehash 操作。rehash 也就是增加現(xiàn)有的哈希桶數(shù)量，讓逐漸增多的 entry 元素能在更多的桶之間分散保存，減少單個桶中的元素數(shù)量，從而減少單個桶中的沖突。那具體怎么做呢？
其實，為了使 rehash 操作更高效，Redis 默認使用了兩個全局哈希表：哈希表 1 和哈希表 2。一開始，當你剛插入數(shù)據(jù)時，默認使用哈希表 1，此時的哈希表 2 并沒有被分配空間。隨著數(shù)據(jù)逐步增多，Redis 開始執(zhí)行 rehash，這個過程分為三步：
- 給哈希表 2 分配更大的空間，例如是當前哈希表 1 大小的兩倍；
- 把哈希表 1 中的數(shù)據(jù)重新映射并拷貝到哈希表 2 中；
- 釋放哈希表 1 的空間。
到此，我們就可以從哈希表 1 切換到哈希表 2，用增大的哈希表 2 保存更多數(shù)據(jù)，而原來的哈希表 1 留作下一次 rehash 擴容備用。
這個過程看似簡單，但是第二步涉及大量的數(shù)據(jù)拷貝，如果一次性把哈希表 1 中的數(shù)據(jù)都遷移完，會造成 Redis 線程阻塞，無法服務(wù)其他請求。此時，Redis 就無法快速訪問數(shù)據(jù)了。
為了避免這個問題，Redis 采用了漸進式 rehash。
簡單來說就是在第二步拷貝數(shù)據(jù)時，Redis 仍然正常處理客戶端請求，每處理一個請求時，從哈希表 1 中的第一個索引位置開始，順帶著將這個索引位置上的所有 entries 拷貝到哈希表 2 中；等處理下一個請求時，再順帶拷貝哈希表 1 中的下一個索引位置的 entries。如下圖所示：
漸進式rehash
這樣就巧妙地把一次性大量拷貝的開銷，分攤到了多次處理請求的過程中，避免了耗時操作，保證了數(shù)據(jù)的快速訪問。
好了，到這里，你應(yīng)該就能理解，Redis 的鍵和值是怎么通過哈希表組織的了。對于 String 類型來說，找到哈希桶就能直接增刪改查了，所以，哈希表的 O(1) 操作復(fù)雜度也就是它的復(fù)雜度了。
但是，對于集合類型來說，即使找到哈希桶了，還要在集合中再進一步操作。接下來，我們來看集合類型的操作效率又是怎樣的。
集合數(shù)據(jù)操作效率
和 String 類型不同，一個集合類型的值，第一步是通過全局哈希表找到對應(yīng)的哈希桶位置，第二步是在集合中再增刪改查。那么，集合的操作效率和哪些因素相關(guān)呢？
首先，與集合的底層數(shù)據(jù)結(jié)構(gòu)有關(guān)。例如，使用哈希表實現(xiàn)的集合，要比使用鏈表實現(xiàn)的集合訪問效率更高。其次，操作效率和這些操作本身的執(zhí)行特點有關(guān)，比如讀寫一個元素的操作要比讀寫所有元素的效率高。
接下來，我們就分別聊聊集合類型的底層數(shù)據(jù)結(jié)構(gòu)和操作復(fù)雜度。
有哪些底層數(shù)據(jù)結(jié)構(gòu)？
剛才，我也和你介紹過，集合類型的底層數(shù)據(jù)結(jié)構(gòu)主要有 5 種：整數(shù)數(shù)組、雙向鏈表、哈希表、壓縮列表和跳表。
其中，哈希表的操作特點我們剛剛已經(jīng)學(xué)過了；整數(shù)數(shù)組和雙向鏈表也很常見，它們的操作特征都是順序讀寫，也就是通過數(shù)組下標或者鏈表的指針逐個元素訪問，操作復(fù)雜度基本是 O(N)，操作效率比較低；壓縮列表和跳表我們平時接觸得可能不多，但它們也是 Redis 重要的數(shù)據(jù)結(jié)構(gòu)，所以我來重點解釋一下。
壓縮列表實際上類似于一個數(shù)組，數(shù)組中的每一個元素都對應(yīng)保存一個數(shù)據(jù)。和數(shù)組不同的是，壓縮列表在表頭有三個字段 zlbytes、zltAIl 和 zllen，分別表示列表長度、列表尾的偏移量和列表中的 entry 個數(shù)；壓縮列表在表尾還有一個 zlend，表示列表結(jié)束。
在壓縮列表中，如果我們要查找定位第一個元素和最后一個元素，可以通過表頭三個字段的長度直接定位，復(fù)雜度是 O(1)。而查找其他元素時，就沒有這么高效了，只能逐個查找，此時的復(fù)雜度就是 O(N) 了。
我們再來看下跳表。
有序鏈表只能逐一查找元素，導(dǎo)致操作起來非常緩慢，于是就出現(xiàn)了跳表。具體來說，跳表在鏈表的基礎(chǔ)上，增加了多級索引，通過索引位置的幾個跳轉(zhuǎn)，實現(xiàn)數(shù)據(jù)的快速定位，如下圖所示：
跳表的快速查找過程
如果我們要在鏈表中查找 33 這個元素，只能從頭開始遍歷鏈表，查找 6 次，直到找到 33 為止。此時，復(fù)雜度是 O(N)，查找效率很低。
為了提高查找速度，我們來增加一級索引：從第一個元素開始，每兩個元素選一個出來作為索引。這些索引再通過指針指向原始的鏈表。例如，從前兩個元素中抽取元素 1 作為一級索引，從第三、四個元素中抽取元素 11 作為一級索引。此時，我們只需要 4 次查找就能定位到元素 33 了。
如果我們還想再快，可以再增加二級索引：從一級索引中，再抽取部分元素作為二級索引。例如，從一級索引中抽取 1、27、100 作為二級索引，二級索引指向一級索引。這樣，我們只需要 3 次查找，就能定位到元素 33 了。
可以看到，這個查找過程就是在多級索引上跳來跳去，最后定位到元素。這也正好符合“跳”表的叫法。當數(shù)據(jù)量很大時，跳表的查找復(fù)雜度就是 O(logN)。
好了，我們現(xiàn)在可以按照查找的時間復(fù)雜度給這些數(shù)據(jù)結(jié)構(gòu)分下類了：
不同操作的復(fù)雜度
集合類型的操作類型很多，有讀寫單個集合元素的，例如 HGET、HSET，也有操作多個元素的，例如 SADD，還有對整個集合進行遍歷操作的，例如 SMEMBERS。這么多操作，它們的復(fù)雜度也各不相同。而復(fù)雜度的高低又是我們選擇集合類型的重要依據(jù)。
我總結(jié)了一個“四句口訣”，希望能幫助你快速記住集合常見操作的復(fù)雜度。這樣你在使用過程中，就可以提前規(guī)避高復(fù)雜度操作了。
- 單元素操作是基礎(chǔ)；
- 范圍操作非常耗時；
- 統(tǒng)計操作通常高效；
例外情況只有幾個：
第一，單元素操作，是指每一種集合類型對單個數(shù)據(jù)實現(xiàn)的增刪改查操作。例如，Hash 類型的 HGET、HSET 和 HDEL，Set 類型的 SADD、SREM、SRANDMEMBER 等。這些操作的復(fù)雜度由集合采用的數(shù)據(jù)結(jié)構(gòu)決定，例如，HGET、HSET 和 HDEL 是對哈希表做操作，所以它們的復(fù)雜度都是 O(1)；Set 類型用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)時，它的 SADD、SREM、SRANDMEMBER 復(fù)雜度也是 O(1)。
這里，有個地方你需要注意一下，集合類型支持同時對多個元素進行增刪改查，例如 Hash 類型的 HMGET 和 HMSET，Set 類型的 SADD 也支持同時增加多個元素。此時，這些操作的復(fù)雜度，就是由單個元素操作復(fù)雜度和元素個數(shù)決定的。例如，HMSET 增加 M 個元素時，復(fù)雜度就從 O(1) 變成 O(M) 了。
第二，范圍操作，是指集合類型中的遍歷操作，可以返回集合中的所有數(shù)據(jù)，比如 Hash 類型的 HGETALL 和 Set 類型的 SMEMBERS，或者返回一個范圍內(nèi)的部分數(shù)據(jù)，比如 List 類型的 LRANGE 和 ZSet 類型的 ZRANGE。這類操作的復(fù)雜度一般是 O(N)，比較耗時，我們應(yīng)該盡量避免。
不過，Redis 從 2.8 版本開始提供了 SCAN 系列操作（包括 HSCAN，SSCAN 和 ZSCAN），這類操作實現(xiàn)了漸進式遍歷，每次只返回有限數(shù)量的數(shù)據(jù)。這樣一來，相比于 HGETALL、SMEMBERS 這類操作來說，就避免了一次性返回所有元素而導(dǎo)致的 Redis 阻塞。
第三，統(tǒng)計操作，是指集合類型對集合中所有元素個數(shù)的記錄，例如 LLEN 和 SCARD。這類操作復(fù)雜度只有 O(1)，這是因為當集合類型采用壓縮列表、雙向鏈表、整數(shù)數(shù)組這些數(shù)據(jù)結(jié)構(gòu)時，這些結(jié)構(gòu)中專門記錄了元素的個數(shù)統(tǒng)計，因此可以高效地完成相關(guān)操作。
第四，例外情況，是指某些數(shù)據(jù)結(jié)構(gòu)的特殊記錄，例如壓縮列表和雙向鏈表都會記錄表頭和表尾的偏移量。這樣一來，對于 List 類型的 LPOP、RPOP、LPUSH、RPUSH 這四個操作來說，它們是在列表的頭尾增刪元素，這就可以通過偏移量直接定位，所以它們的復(fù)雜度也只有 O(1)，可以實現(xiàn)快速操作。
小結(jié)
我們學(xué)習(xí)了 Redis 的底層數(shù)據(jù)結(jié)構(gòu)，這既包括了 Redis 中用來保存每個鍵和值的全局哈希表結(jié)構(gòu)，也包括了支持集合類型實現(xiàn)的雙向鏈表、壓縮列表、整數(shù)數(shù)組、哈希表和跳表這五大底層結(jié)構(gòu)。
Redis 之所以能快速操作鍵值對，一方面是因為 O(1) 復(fù)雜度的哈希表被廣泛使用，包括 String、Hash 和 Set，它們的操作復(fù)雜度基本由哈希表決定，另一方面，Sorted Set 也采用了 O(logN) 復(fù)雜度的跳表。不過，集合類型的范圍操作，因為要遍歷底層數(shù)據(jù)結(jié)構(gòu)，復(fù)雜度通常是 O(N)。這里，我的建議是：用其他命令來替代，例如可以用 SCAN 來代替，避免在 Redis 內(nèi)部產(chǎn)生費時的全集合遍歷操作。
當然，我們不能忘了復(fù)雜度較高的 List 類型，它的兩種底層實現(xiàn)結(jié)構(gòu)：雙向鏈表和壓縮列表的操作復(fù)雜度都是 O(N)。因此，我的建議是：因地制宜地使用 List 類型。例如，既然它的 POP/PUSH 效率很高，那么就將它主要用于 FIFO 隊列場景，而不是作為一個可以隨機讀寫的集合。
Redis 數(shù)據(jù)類型豐富，每個類型的操作繁多，我們通常無法一下子記住所有操作的復(fù)雜度。所以，最好的辦法就是掌握原理，以不變應(yīng)萬變。這里，你可以看到，一旦掌握了數(shù)據(jù)結(jié)構(gòu)基本原理，你可以從原理上推斷不同操作的復(fù)雜度，即使這個操作你不一定熟悉。這樣一來，你不用死記硬背，也能快速合理地做出選擇了。
