redis 為什么要這莫快?一個(gè)就是他是基于內(nèi)存的,另外一個(gè)就是他是他的數(shù)據(jù)結(jié)構(gòu)
說(shuō)到這兒,你肯定會(huì)說(shuō):“這個(gè)我知道,不就是 String(字符串)、List(列表)、
Hash(哈希)、Set(集合)和 Sorted Set(有序集合)嗎?”其實(shí),這些只是 Redis 鍵
值對(duì)中值的數(shù)據(jù)類(lèi)型,也就是數(shù)據(jù)的保存形式。而這里,我們說(shuō)的數(shù)據(jù)結(jié)構(gòu),是要去看看
它們的底層實(shí)現(xiàn)。
簡(jiǎn)單來(lái)說(shuō),底層數(shù)據(jù)結(jié)構(gòu)一共有 6 種,分別是簡(jiǎn)單動(dòng)態(tài)字符串、雙向鏈表、壓縮列表、哈
希表、跳表和整數(shù)數(shù)組。它們和數(shù)據(jù)類(lèi)型的對(duì)應(yīng)關(guān)系如下圖所示
?可以看到,String 類(lèi)型的底層實(shí)現(xiàn)只有一種數(shù)據(jù)結(jié)構(gòu),也就是簡(jiǎn)單動(dòng)態(tài)字符串。而 List、
Hash、Set 和 Sorted Set 這四種數(shù)據(jù)類(lèi)型,都有兩種底層實(shí)現(xiàn)結(jié)構(gòu)。通常情況下,我們會(huì)
把這四種類(lèi)型稱(chēng)為集合類(lèi)型,它們的特點(diǎn)是一個(gè)鍵對(duì)應(yīng)了一個(gè)集合的數(shù)據(jù)
以上 底層的數(shù)據(jù)結(jié)構(gòu)我單寫(xiě)一篇文章
看到這里,其實(shí)有些問(wèn)題已經(jīng)值得我們?nèi)タ紤]了:
????????這些數(shù)據(jù)結(jié)構(gòu)都是值的底層實(shí)現(xiàn),鍵和值本身之間用什么結(jié)構(gòu)組織?
????????為什么集合類(lèi)型有那么多的底層結(jié)構(gòu),它們都是怎么組織數(shù)據(jù)的,都很快嗎?
????????什么是簡(jiǎn)單動(dòng)態(tài)字符串,和常用的字符串是一回事嗎?
接下來(lái),我就和你聊聊前兩個(gè)問(wèn)題。這樣,你不僅可以知道 Redis“快”的基本原理,還
可以借此理解 Redis 中有哪些潛在的“慢操作”,最大化 Redis 的性能優(yōu)勢(shì)。
鍵和值用什么結(jié)構(gòu)組織?
了實(shí)現(xiàn)從鍵到值的快速訪問(wèn),Redis 使用了一個(gè)哈希表來(lái)保存所有鍵值對(duì)。
一個(gè)哈希表,其實(shí)就是一個(gè)數(shù)組,數(shù)組的每個(gè)元素稱(chēng)為一個(gè)哈希桶。所以,我們常說(shuō),一
個(gè)哈希表是由多個(gè)哈希桶組成的,每個(gè)哈希桶中保存了鍵值對(duì)數(shù)據(jù)。
看到這里,你可能會(huì)問(wèn)了:“如果值是集合類(lèi)型的話,作為數(shù)組元素的哈希桶怎么來(lái)保存
呢?”其實(shí),哈希桶中的元素保存的并不是值本身,而是指向具體值的指針。這也就是
說(shuō),不管值是 String,還是集合類(lèi)型,哈希桶中的元素都是指向它們的指針。
在下圖中,可以看到,哈希桶中的 entry 元素中保存了*key和*value指針,分別指向了
實(shí)際的鍵和值,這樣一來(lái),即使值是一個(gè)集合,也可以通過(guò)*value指針被查找到。
?因?yàn)檫@個(gè)哈希表保存了所有的鍵值對(duì),所以,我也把它稱(chēng)為全局哈希表。哈希表的最大好
處很明顯,就是讓我們可以用 O(1) 的時(shí)間復(fù)雜度來(lái)快速查找到鍵值對(duì)——我們只需要計(jì)算
鍵的哈希值,就可以知道它所對(duì)應(yīng)的哈希桶位置,然后就可以訪問(wèn)相應(yīng)的 entry 元素。
你看,這個(gè)查找過(guò)程主要依賴于哈希計(jì)算,和數(shù)據(jù)量的多少并沒(méi)有直接關(guān)系。也就是說(shuō),
不管哈希表里有 10 萬(wàn)個(gè)鍵還是 100 萬(wàn)個(gè)鍵,我們只需要一次計(jì)算就能找到相應(yīng)的鍵
但是,如果你只是了解了哈希表的 O(1) 復(fù)雜度和快速查找特性,那么,當(dāng)你往 Redis 中
寫(xiě)入大量數(shù)據(jù)后,就可能發(fā)現(xiàn)操作有時(shí)候會(huì)突然變慢了。這其實(shí)是因?yàn)槟愫雎粤艘粋€(gè)潛在
的風(fēng)險(xiǎn)點(diǎn),那就是哈希表的沖突問(wèn)題和 rehash 可能帶來(lái)的操作阻塞。
為什么哈希表操作變慢了?
當(dāng)你往哈希表中寫(xiě)入更多數(shù)據(jù)時(shí),哈希沖突是不可避免的問(wèn)題。這里的哈希沖突,也就是
指,兩個(gè) key 的哈希值和哈希桶計(jì)算對(duì)應(yīng)關(guān)系時(shí),正好落在了同一個(gè)哈希桶中。
畢竟,哈希桶的個(gè)數(shù)通常要少于 key 的數(shù)量,這也就是說(shuō),難免會(huì)有一些 key 的哈希值對(duì)
應(yīng)到了同一個(gè)哈希桶中
Redis 解決哈希沖突的方式,就是鏈?zhǔn)焦?。鏈?zhǔn)焦R埠苋菀桌斫猓褪侵竿粋€(gè)哈希
桶中的多個(gè)元素用一個(gè)鏈表來(lái)保存,它們之間依次用指針連接。
如下圖所示:entry1、entry2 和 entry3 都需要保存在哈希桶 3 中,導(dǎo)致了哈希沖突。此
時(shí),entry1 元素會(huì)通過(guò)一個(gè)*next指針指向 entry2,同樣,entry2 也會(huì)通過(guò)*next指針
指向 entry3。這樣一來(lái),即使哈希桶 3 中的元素有 100 個(gè),我們也可以通過(guò) entry 元素
中的指針,把它們連起來(lái)。這就形成了一個(gè)鏈表,也叫作哈希沖突鏈。
?但是,這里依然存在一個(gè)問(wèn)題,哈希沖突鏈上的元素只能通過(guò)指針逐一查找再操作。如果
哈希表里寫(xiě)入的數(shù)據(jù)越來(lái)越多,哈希沖突可能也會(huì)越來(lái)越多,這就會(huì)導(dǎo)致某些哈希沖突鏈
過(guò)長(zhǎng),進(jìn)而導(dǎo)致這個(gè)鏈上的元素查找耗時(shí)長(zhǎng),效率降低。對(duì)于追求“快”的 Redis 來(lái)說(shuō),
這是不太能接受的。
所以,Redis 會(huì)對(duì)哈希表做 rehash 操作。rehash 也就是增加現(xiàn)有的哈希桶數(shù)量,讓逐漸
增多的 entry 元素能在更多的桶之間分散保存,減少單個(gè)桶中的元素?cái)?shù)量,從而減少單個(gè)
桶中的沖突。那具體怎么做呢?
其實(shí),為了使 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 的空間
到此,我們就可以從哈希表 1 切換到哈希表 2,用增大的哈希表 2 保存更多數(shù)據(jù),而原來(lái)
的哈希表 1 留作下一次 rehash 擴(kuò)容備用.
這個(gè)過(guò)程看似簡(jiǎn)單,但是第二步涉及大量的數(shù)據(jù)拷貝,如果一次性把哈希表 1 中的數(shù)據(jù)都
遷移完,會(huì)造成 Redis 線程阻塞,無(wú)法服務(wù)其他請(qǐng)求。此時(shí),Redis 就無(wú)法快速訪問(wèn)數(shù)據(jù)
了.
為了避免這個(gè)問(wèn)題,Redis 采用了漸進(jìn)式 rehash
簡(jiǎn)單來(lái)說(shuō)就是在第二步拷貝數(shù)據(jù)時(shí),Redis 仍然正常處理客戶端請(qǐng)求,每處理一個(gè)請(qǐng)求
時(shí),從哈希表 1 中的第一個(gè)索引位置開(kāi)始,順帶著將這個(gè)索引位置上的所有 entries 拷貝
到哈希表 2 中;等處理下一個(gè)請(qǐng)求時(shí),再順帶拷貝哈希表 1 中的下一個(gè)索引位置的
entries。如下圖所示:
?這樣就巧妙地把一次性大量拷貝的開(kāi)銷(xiāo),分?jǐn)偟搅硕啻翁幚碚?qǐng)求的過(guò)程中,避免了耗時(shí)操
作,保證了數(shù)據(jù)的快速訪問(wèn)。
好了,到這里,你應(yīng)該就能理解,Redis 的鍵和值是怎么通過(guò)哈希表組織的了。對(duì)于
String 類(lèi)型來(lái)說(shuō),找到哈希桶就能直接增刪改查了,所以,哈希表的 O(1) 操作復(fù)雜度也就
是它的復(fù)雜度了。
但是,對(duì)于集合類(lèi)型來(lái)說(shuō),即使找到哈希桶了,還要在集合中再進(jìn)一步操作。接下來(lái),我
們來(lái)看集合類(lèi)型的操作效率又是怎樣的
有哪些底層數(shù)據(jù)結(jié)構(gòu)?
集合類(lèi)型的底層數(shù)據(jù)結(jié)構(gòu)主要有 5 種:整數(shù)數(shù)組、雙向鏈表、哈
希表、壓縮列表和跳表
其中,哈希表的操作特點(diǎn)我們剛剛已經(jīng)學(xué)過(guò)了;整數(shù)數(shù)組和雙向鏈表也很常見(jiàn),它們的操
作特征都是順序讀寫(xiě),也就是通過(guò)數(shù)組下標(biāo)或者鏈表的指針逐個(gè)元素訪問(wèn),操作復(fù)雜度基
本是 O(N),操作效率比較低;壓縮列表和跳表我們平時(shí)接觸得可能不多,但它們也是
Redis 重要的數(shù)據(jù)結(jié)構(gòu),所以我來(lái)重點(diǎn)解釋一下。
壓縮列表實(shí)際上類(lèi)似于一個(gè)數(shù)組,數(shù)組中的每一個(gè)元素都對(duì)應(yīng)保存一個(gè)數(shù)據(jù)。和數(shù)組不同
的是,壓縮列表在表頭有三個(gè)字段 zlbytes、zltail 和 zllen,分別表示列表長(zhǎng)度、列表尾的
偏移量和列表中的 entry 個(gè)數(shù);壓縮列表在表尾還有一個(gè) zlend,表示列表結(jié)束。
?
在壓縮列表中,如果我們要查找定位第一個(gè)元素和最后一個(gè)元素,可以通過(guò)表頭三個(gè)字段
的長(zhǎng)度直接定位,復(fù)雜度是 O(1)。而查找其他元素時(shí),就沒(méi)有這么高效了,只能逐個(gè)查
找,此時(shí)的復(fù)雜度就是 O(N) 了。
我們?cè)賮?lái)看下跳表。
有序鏈表只能逐一查找元素,導(dǎo)致操作起來(lái)非常緩慢,于是就出現(xiàn)了跳表。具體來(lái)說(shuō),跳
表在鏈表的基礎(chǔ)上,增加了多級(jí)索引,通過(guò)索引位置的幾個(gè)跳轉(zhuǎn),實(shí)現(xiàn)數(shù)據(jù)的快速定位,
如下圖所示
?可以看到,這個(gè)查找過(guò)程就是在多級(jí)索引上跳來(lái)跳去,最后定位到元素。這也正好符
合“跳”表的叫法。當(dāng)數(shù)據(jù)量很大時(shí),跳表的查找復(fù)雜度就是 O(logN)。
?
不同操作的復(fù)雜度
集合類(lèi)型的操作類(lèi)型很多,有讀寫(xiě)單個(gè)集合元素的,例如 HGET、HSET,也有操作多個(gè)元
素的,例如 SADD,還有對(duì)整個(gè)集合進(jìn)行遍歷操作的,例如 SMEMBERS。這么多操作,
它們的復(fù)雜度也各不相同。而復(fù)雜度的高低又是我們選擇集合類(lèi)型的重要依據(jù)。我總結(jié)了一個(gè)“四句口訣”,希望能幫助你快速記住集合常見(jiàn)操作的復(fù)雜度。這樣你在使用過(guò)程中,就可以提前規(guī)避高復(fù)雜度操作了
單元素操作是基礎(chǔ);
范圍操作非常耗時(shí);
統(tǒng)計(jì)操作通常高效;
例外情況只有幾個(gè)。
第一,單元素操作,是指每一種集合類(lèi)型對(duì)單個(gè)數(shù)據(jù)實(shí)現(xiàn)的增刪改查操作。例如,Hash 類(lèi)
型的 HGET、HSET 和 HDEL,Set 類(lèi)型的 SADD、SREM、SRANDMEMBER 等。這些操
作的復(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)。
這里,有個(gè)地方你需要注意一下,集合類(lèi)型支持同時(shí)對(duì)多個(gè)元素進(jìn)行增刪改查,例如 Hash
類(lèi)型的 HMGET 和 HMSET,Set 類(lèi)型的 SADD 也支持同時(shí)增加多個(gè)元素。此時(shí),這些操
作的復(fù)雜度,就是由單個(gè)元素操作復(fù)雜度和元素個(gè)數(shù)決定的。例如,HMSET 增加 M 個(gè)元
素時(shí),復(fù)雜度就從 O(1) 變成 O(M) 了。
第二,范圍操作,是指集合類(lèi)型中的遍歷操作,可以返回集合中的所有數(shù)據(jù),比如 Hash
類(lèi)型的 HGETALL 和 Set 類(lèi)型的 SMEMBERS,或者返回一個(gè)范圍內(nèi)的部分?jǐn)?shù)據(jù),比如 List
類(lèi)型的 LRANGE 和 ZSet 類(lèi)型的 ZRANGE。這類(lèi)操作的復(fù)雜度一般是 O(N),比較耗時(shí),
我們應(yīng)該盡量避免。
不過(guò),Redis 從 2.8 版本開(kāi)始提供了 SCAN 系列操作(包括 HSCAN,SSCAN 和
ZSCAN),這類(lèi)操作實(shí)現(xiàn)了漸進(jìn)式遍歷,每次只返回有限數(shù)量的數(shù)據(jù)。這樣一來(lái),相比于
HGETALL、SMEMBERS 這類(lèi)操作來(lái)說(shuō),就避免了一次性返回所有元素而導(dǎo)致的 Redis 阻
塞。
第三,統(tǒng)計(jì)操作,是指集合類(lèi)型對(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)操作。
第四,例外情況,是指某些數(shù)據(jù)結(jié)構(gòu)的特殊記錄,例如壓縮列表和雙向鏈表都會(huì)記錄表頭
和表尾的偏移量。這樣一來(lái),對(duì)于 List 類(lèi)型的 LPOP、RPOP、LPUSH、RPUSH 這四個(gè)操
作來(lái)說(shuō),它們是在列表的頭尾增刪元素,這就可以通過(guò)偏移量直接定位,所以它們的復(fù)雜
度也只有 O(1),可以實(shí)現(xiàn)快速操作。
edis 之所以能快速操作鍵值對(duì),一方面是因?yàn)?O(1) 復(fù)雜度的哈希表被廣泛使用,包括
String、Hash 和 Set,它們的操作復(fù)雜度基本由哈希表決定,另一方面,Sorted Set 也采
用了 O(logN) 復(fù)雜度的跳表。不過(guò),集合類(lèi)型的范圍操作,因?yàn)橐闅v底層數(shù)據(jù)結(jié)構(gòu),復(fù)
雜度通常是 O(N)。這里,我的建議是:用其他命令來(lái)替代,例如可以用 SCAN 來(lái)代替,
避免在 Redis 內(nèi)部產(chǎn)生費(fèi)時(shí)的全集合遍歷操作。文章來(lái)源:http://www.zghlxwxcb.cn/news/detail-615881.html當(dāng)然,我們不能忘了復(fù)雜度較高的 List 類(lèi)型,它的兩種底層實(shí)現(xiàn)結(jié)構(gòu):雙向鏈表和壓縮列
表的操作復(fù)雜度都是 O(N)。因此,我的建議是:因地制宜地使用 List 類(lèi)型。例如,既然
它的 POP/PUSH 效率很高,那么就將它主要用于 FIFO 隊(duì)列場(chǎng)景,而不是作為一個(gè)可以隨
機(jī)讀寫(xiě)的集合文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-615881.html
到了這里,關(guān)于數(shù)據(jù)結(jié)構(gòu):快速的Redis有哪些慢操作?的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!