單線(xiàn)程的Redis有哪些 "慢" 動(dòng)作？
持續(xù)原創(chuàng)輸出,點(diǎn)擊上方藍(lán)字關(guān)注我
目錄
前言 為什么 Redis 這么火？ 鍵和值的保存形式？ 為什么哈希表操作變慢了？ 集合的操作效率？ 有哪些數(shù)據(jù)結(jié)構(gòu)？ 不同操作的復(fù)雜度？ 總結(jié)
前言
現(xiàn)在一提到Redis的第一反應(yīng)就是快、單線(xiàn)程，但是Redis真的快嗎？真的是單線(xiàn)程嗎？
你有沒(méi)有深入了解一下Redis，看看它的底層有哪些"慢動(dòng)作"呢？
為什么 Redis 這么火？
Redis作為一個(gè)內(nèi)存數(shù)據(jù)庫(kù)，它接收一個(gè)key到讀取數(shù)據(jù)幾乎是微秒級(jí)別，一個(gè)字快詮釋了它火的原因。另一方面就歸功于它的數(shù)據(jù)結(jié)構(gòu)了，你知道Redis有哪些數(shù)據(jù)結(jié)構(gòu)嗎？
很多人可能會(huì)說(shuō)不就是String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）這五種嗎？我想大家可能有一種誤區(qū)，我說(shuō)的是底層數(shù)據(jù)結(jié)構(gòu)，而你說(shuō)僅僅是數(shù)據(jù)的保存形式而已。
那么Redis底層有哪幾種數(shù)據(jù)結(jié)構(gòu)呢？和幾種數(shù)據(jù)保存形式的關(guān)系又是什么呢？別著急，先通過(guò)一張圖了解下，如下圖：
通過(guò)上圖可以知道只有String對(duì)應(yīng)的是一種數(shù)據(jù)結(jié)構(gòu)，其他的數(shù)據(jù)類(lèi)型對(duì)應(yīng)的都是兩種數(shù)據(jù)結(jié)構(gòu)，我們通常將這四種數(shù)據(jù)類(lèi)型稱(chēng)為集合類(lèi)型，它們的特點(diǎn)是「一個(gè)鍵對(duì)應(yīng)了一個(gè)集合的數(shù)據(jù)」。
既然數(shù)據(jù)本身是通過(guò)數(shù)據(jù)結(jié)構(gòu)保存的，那么鍵和值是什么保存形式呢？
鍵和值的保存形式？
為了實(shí)現(xiàn)鍵和值的快速訪(fǎng)問(wèn)，Redis使用的是哈希表來(lái)存放鍵，使用哈希桶存放值。
一個(gè)
哈希表其實(shí)就是一個(gè)數(shù)組，數(shù)組的每個(gè)元素稱(chēng)之為哈希桶。
所以，一個(gè)哈希表是由多個(gè)哈希桶組成，每個(gè)哈希桶中保存了鍵值對(duì)數(shù)據(jù)。
哈希桶中保存的并不是值，而是指向值的指針。
這也解釋了為什么哈希桶能夠保存集合類(lèi)型的數(shù)據(jù)了，也就是說(shuō)不管是String還是集合類(lèi)型，哈希桶保存的都是指向具體的值的指針，具體的結(jié)構(gòu)如下圖：
從上圖可以看出，每個(gè)entry中保存的是*key和*value分別指向了鍵和值，這樣即使保存的值是集合類(lèi)型也能通過(guò)指針 *value找到。
鍵是保存在哈希表中，哈希表的時(shí)間復(fù)雜度是
O(1)，也就是無(wú)論多少個(gè)鍵，總能通過(guò)一次計(jì)算就找到對(duì)應(yīng)的鍵。
但是問(wèn)題來(lái)了，當(dāng)你往Redis中寫(xiě)入大量的數(shù)據(jù)就有可能發(fā)現(xiàn)操作變「慢」了，這就是一個(gè)典型的問(wèn)題：「哈希沖突」。
為什么哈希表操作變慢了？
既然底層用了哈希表，則哈希沖突是不可避免的，那什么是哈希沖突呢？
Redis中的哈希沖突則是兩個(gè)或者多個(gè)key通過(guò)計(jì)算對(duì)應(yīng)關(guān)系，正好落在了同一個(gè)哈希桶中。
這樣則導(dǎo)致了不同的key查找到的值是相同的，但是這種問(wèn)題在Redis中顯然是不存在的，那么Redis用了什么方法解決了哈希沖突呢？
Redis底層使用了鏈?zhǔn)焦?/code>的方式解決了哈希沖突，即是同一個(gè)哈希桶中的多個(gè)元素用一個(gè)鏈表保存，他們之間用指針*next相連。
此時(shí)的哈希表和鏈?zhǔn)焦５慕Y(jié)構(gòu)如下圖：
從上圖可以看到，entry1、entry3、entry3都保存在哈希桶 1 中，導(dǎo)致了哈希沖突。但是此時(shí)的entry1中的*next指針指向了entry2，同樣entry2中的*next指針指向了entry3。這樣下來(lái)即使哈希桶中有很多個(gè)元素，也能通過(guò)這樣的方式連接起來(lái)，稱(chēng)作哈希沖突鏈。
這里存在一個(gè)問(wèn)題：鏈表的查詢(xún)效率很低，如果哈希桶中元素很多，查找起來(lái)會(huì)很「慢」，顯然這個(gè)對(duì)于
Redis來(lái)說(shuō)是不能接受的。
Redis使用了一個(gè)很巧妙的方式：「漸進(jìn)式 rehash」。那么什么是漸進(jìn)是rehash呢？
想要理解漸進(jìn)式rehash，首先需要理解下的rehash的過(guò)程。
rehash也就是增加現(xiàn)有的哈希桶數(shù)量，讓逐漸增多的entry元素能在更多的桶之間分散保存，減少單個(gè)桶中的元素?cái)?shù)量，從而減少單個(gè)桶中的沖突。
為了使rehash操作更高效，Redis 默認(rèn)使用了兩個(gè)全局哈希表：哈希表1和哈希表2。一開(kāi)始，當(dāng)你剛插入數(shù)據(jù)時(shí)，默認(rèn)使用哈希表1，此時(shí)的哈希表2并沒(méi)有被分配空間。隨著數(shù)據(jù)逐步增多，Redis 開(kāi)始執(zhí)行rehash，這個(gè)過(guò)程分為三步：
給 哈希表2分配更大的空間，例如是當(dāng)前哈希表1大小的兩倍把 哈希表1中的數(shù)據(jù)重新映射并拷貝到哈希表2中釋放 哈希表1的空間。
以上這個(gè)過(guò)程結(jié)束，就可以釋放掉哈希表1的數(shù)據(jù)而使用哈希表2了，此時(shí)的哈希表1可以留作下次的rehash備用。
此時(shí)這里存在一個(gè)問(wèn)題：
rehash整個(gè)過(guò)程的第 2 步涉及到大量的拷貝，一次性的拷貝數(shù)據(jù)肯定會(huì)造成線(xiàn)程阻塞，無(wú)法服務(wù)其他的請(qǐng)求。此時(shí)的Redis就無(wú)法快速訪(fǎng)問(wèn)數(shù)據(jù)了。
為了避免一次性拷貝數(shù)據(jù)導(dǎo)致線(xiàn)程阻塞，Redis使用了漸進(jìn)式rehash。
漸進(jìn)式rehash則是rehash的第 2 步拷貝數(shù)據(jù)分?jǐn)偟矫總€(gè)請(qǐng)求中，Redis 仍然正常服務(wù)，只不過(guò)在處理每次請(qǐng)求的時(shí)候，從哈希表1中索引1的位置將所有的entry拷貝到哈希表2中，下一個(gè)請(qǐng)求則從索引1的下一個(gè)的位置開(kāi)始。
通過(guò)漸進(jìn)式 rehash 巧妙的將一次性開(kāi)銷(xiāo)分?jǐn)偟礁鱾€(gè)請(qǐng)求處理的過(guò)程中，避免了一次性的耗時(shí)操作。
此時(shí)可能有人提出疑問(wèn)了：「如果沒(méi)有請(qǐng)求，那么Redis就不會(huì)rehash了嗎？」
Redis底層其實(shí)還會(huì)開(kāi)啟一個(gè)定時(shí)任務(wù)，會(huì)定時(shí)的拷貝數(shù)據(jù)，即使沒(méi)有請(qǐng)求，rehash也會(huì)定時(shí)的在執(zhí)行。
集合的操作效率？
如果是string，找到哈希桶中的entry則能正常的進(jìn)行增刪改查了，但是如果是集合呢？即使通過(guò)指針找到了entry中的value,但是此時(shí)是一個(gè)集合，又是一個(gè)不同的數(shù)據(jù)結(jié)構(gòu)，肯定會(huì)有不同的復(fù)雜度了。
集合的操作效率肯定是和集合底層的數(shù)據(jù)結(jié)構(gòu)相關(guān)，比如使用哈希表實(shí)現(xiàn)的集合肯定要比使用鏈表實(shí)現(xiàn)的結(jié)合訪(fǎng)問(wèn)效率要高。
接下來(lái)就來(lái)說(shuō)說(shuō)集合的底層數(shù)據(jù)結(jié)構(gòu)和操作復(fù)雜度。
有哪些數(shù)據(jù)結(jié)構(gòu)？
本文的第一張圖已經(jīng)列出了集合的底層數(shù)據(jù)結(jié)構(gòu)，主要有五種：整數(shù)數(shù)組、雙向鏈表、哈希表、壓縮列表和跳表。
以上這五種數(shù)據(jù)結(jié)構(gòu)都是比較常見(jiàn)的，如果讀者不是很了解具體的結(jié)構(gòu)請(qǐng)閱讀相關(guān)的書(shū)籍，我就不再贅述了。
五種數(shù)據(jù)結(jié)構(gòu)按照查找時(shí)間的復(fù)雜度分類(lèi)如下：
| 數(shù)據(jù)結(jié)構(gòu) | 時(shí)間復(fù)雜度 |
|---|---|
| 哈希表 | O(1) |
| 跳表 | O(logN) |
| 雙向鏈表 | O(N) |
| 壓縮鏈表 | O(N) |
| 整數(shù)數(shù)組 | O(N) |
不同操作的復(fù)雜度？
集合類(lèi)型的操作類(lèi)型很多，有讀寫(xiě)單個(gè)集合元素的，例如 HGET、HSET，也有操作多個(gè)元素的，例如SADD，還有對(duì)整個(gè)集合進(jìn)行遍歷操作的，例如 SMEMBERS。這么多操作，它們的復(fù)雜度也各不相同。而復(fù)雜度的高低又是我們選擇集合類(lèi)型的重要依據(jù)。
下文列舉了一些集合操作的復(fù)雜度，總共三點(diǎn)，僅供參考。
1. 單元素操作由底層數(shù)據(jù)結(jié)構(gòu)決定
每一種集合類(lèi)型對(duì)單元素的增刪改查操作這些操作的復(fù)雜度由集合采用的數(shù)據(jù)結(jié)構(gòu)決定。例如，HGET、HSET 和HDEL 是對(duì)哈希表做操作，所以它們的復(fù)雜度都是O(1)；Set類(lèi)型用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)時(shí)，它的SADD、SREM、SRANDMEMBER 復(fù)雜度也是 O(1)。
有些集合類(lèi)型還支持一條命令同時(shí)對(duì)多個(gè)元素的操作，比如Hash類(lèi)型的HMGET和HMSET。此時(shí)的操作復(fù)雜度則是O(N)。
2. 范圍操作非常耗時(shí)，應(yīng)該避免
范圍操作是指集合類(lèi)型中的遍歷操作，可以返回集合中的所有數(shù)據(jù)或者部分?jǐn)?shù)據(jù)。比如List類(lèi)型的HGETALL 和Set 類(lèi)型的SMEMBERS，這類(lèi)操作的復(fù)雜度為O(N)，比較耗時(shí)，應(yīng)該避免。
不過(guò)Redis提供了Scan系列操作，比如HSCAN、SSCSCAN和ZSCAN,這類(lèi)操作實(shí)現(xiàn)了漸進(jìn)式遍歷，每次只返回有限數(shù)量的數(shù)據(jù)。這樣一來(lái)，相比于HGETALL、SMEMBERS 這類(lèi)操作來(lái)說(shuō)，就避免了一次性返回所有元素而導(dǎo)致的 Redis 阻塞。
3. 統(tǒng)計(jì)操作通常比較高效
統(tǒng)計(jì)操作是指對(duì)集合中的所有元素個(gè)數(shù)的記錄，例如LLEN 和SCARD。這類(lèi)操作復(fù)雜度只有O(1)，這是因?yàn)楫?dāng)集合類(lèi)型采用壓縮列表、雙向鏈表、整數(shù)數(shù)組這些數(shù)據(jù)結(jié)構(gòu)時(shí)，這些結(jié)構(gòu)中專(zhuān)門(mén)記錄了元素的個(gè)數(shù)統(tǒng)計(jì)，因此可以高效地完成相關(guān)操作。
總結(jié)
Redis之所以這么快，不僅僅因?yàn)槿坎僮鞫荚趦?nèi)存中，還有底層數(shù)據(jù)結(jié)構(gòu)的支持，但是數(shù)據(jù)結(jié)構(gòu)雖好，每種數(shù)據(jù)結(jié)構(gòu)也有各種「慢」的情況，Redis結(jié)合各種數(shù)據(jù)結(jié)構(gòu)的利弊，完善了整個(gè)運(yùn)行機(jī)制。