前言

• 相信你一定使用過新華字典吧！小時(shí)候不會讀的字都是通過字典去查找的。在Redis中也存在相同功能叫做字典又稱為符號表！是一種保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)

• 本篇仍然定位在【redis前傳】系列中，因?yàn)楸酒匀皇窃诮馕鰎edis數(shù)據(jù)結(jié)構(gòu)！當(dāng)你嘗試去了解redis時(shí)才能明白其中原理！才能明白為什么redis被大家吹捧速度快，而不是被告知redis很快！

應(yīng)用場景

• 在Redis中有很多場景都是用了字典作為底層數(shù)據(jù)結(jié)構(gòu)！我們使用最多的應(yīng)該是redis的庫的設(shè)置和五種基本數(shù)據(jù)類型的Hash結(jié)構(gòu)數(shù)據(jù)！

• 在上一篇【redis前傳】中我們學(xué)習(xí)了list數(shù)據(jù)結(jié)構(gòu)。今天我們繼續(xù)學(xué)習(xí)主流數(shù)據(jù)結(jié)構(gòu)Hash。

• 在redis內(nèi)部有字典結(jié)構(gòu)、hash結(jié)構(gòu)但是這里的hash和我們平時(shí)熟知的redis基礎(chǔ)數(shù)據(jù)的hash并不是一個(gè)意思！我們簡單的將字典結(jié)構(gòu)、hash結(jié)構(gòu)理解成redis更加底層的一種抽象結(jié)構(gòu)。平時(shí)我們使用的hash基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)理解成hash工具

• 而今天我們的主角就是五種數(shù)據(jù)結(jié)構(gòu)的Hash分析。他的底層使用了字典這個(gè)結(jié)構(gòu)。字典結(jié)構(gòu)內(nèi)部使用的是底層的hash結(jié)構(gòu)。有點(diǎn)繞！好好理解你行的

哈希表

• 上面這張圖詮釋了作為redis底層結(jié)構(gòu)的Hash。在內(nèi)部redis稱之為dictht  。后面我們?yōu)槭裁春椭暗膆ash結(jié)構(gòu)沖突我們都已類名為準(zhǔn)叫做dictht類。

• 在hictht類中有四個(gè)屬性分別是table 、 size 、 sizemask 、 used  ; 其中table就是一個(gè)數(shù)組；數(shù)組中元素是另外一個(gè)類叫做dictEntry類。

• dictEntry就是真正存儲數(shù)據(jù)的。內(nèi)部是key、value存儲結(jié)構(gòu)。一個(gè)簡單的哈希表就如圖所示。數(shù)據(jù)最終會存儲在table中的dictEntry對象中。

• 至于為什么sizemask = size -1 ; 這個(gè)是為了在計(jì)算hash索引時(shí)需要用到的。那為什么不直接使用size-1而是通過一個(gè)變量來承接呢？這個(gè)吧?。。∥乙膊恢?。容我去百度百度。

數(shù)組節(jié)點(diǎn)

• 上面的哈希表是不是很熟悉，這不和我們Java中的Map數(shù)據(jù)結(jié)構(gòu)如出一轍嗎?？梢哉f是也可以說不是，兩者很相似但也有區(qū)別的。

• 在上面中我們提到數(shù)據(jù)最終是存儲在哈希表里table數(shù)組里的元素。該元素叫dictEntry 。下面我們看看dictEntry結(jié)構(gòu)如何吧！

• 通過左側(cè)對dictEntry的定義我們可以看出。dictEntry存儲的值可以是指針、正數(shù)、浮點(diǎn)數(shù)各種數(shù)據(jù)類型！類似于Java中的Object屬性。 對于上述的key沒有啥真意的就是一個(gè)鍵。

• 既然是數(shù)組那么索引就是固定長度的，那么在有限的長度中肯定會出現(xiàn)經(jīng)典問題就是【hash沖突】。在Java中我們是通過鏈表和紅黑樹來解決沖突的問題！在redis中是通過鏈表解決的。在dictEntry中通過next指針將沖突元素連接。

• 這里我們就可以和Java中的Map結(jié)構(gòu)進(jìn)行理解。他們內(nèi)部很是相似!!!

• 這里需要注意下在hash沖突時(shí)redis的確是通過鏈表進(jìn)行存儲的，但是由于哈希表(dictht)中沒有記錄每個(gè)索引未中鏈表的尾部節(jié)點(diǎn)只有頭結(jié)點(diǎn)信息所以。而且我們也知道鏈表在查詢上效率不佳，所以當(dāng)發(fā)生哈希沖突時(shí)redis是將新加入的節(jié)點(diǎn)加入在鏈表的頭部！

字典

多態(tài)字典

• 字典是本文開頭提出的結(jié)構(gòu)！也是redis中大量使用的一種底層數(shù)據(jù)結(jié)構(gòu)。在redis中名叫做dict類。

• 通過圖示我們明確的看出內(nèi)部是包含哈希表的。其實(shí)從名字上我們也可以看出哈希表為什么叫dictht 。筆者這里認(rèn)為是dicthashcodetable 。意思就是字典表內(nèi)部的一個(gè)hash相關(guān)的數(shù)組(僅個(gè)人理解)

• 之前也提到過redis內(nèi)部很多地方會使用到字典！就好比我們上學(xué)是用到【新華字典】、【成語詞典】、【歇后語詞典】等等。雖然名字叫法不一樣但是內(nèi)部結(jié)構(gòu)都是一部字典供我們快速定位。而redis中dict內(nèi)部就是通過type字段進(jìn)行區(qū)分每個(gè)字典的。而privdata是每部字典需要的特定參數(shù)。通過type和privdata就可以輕松實(shí)現(xiàn)各種功能不同的字典，他有個(gè)專有名詞叫~~多態(tài)字典~~

rehash

• 除了type 、 privdata以外剩下的就是ht 、 rehashidx了。其中ht是一個(gè)長度為2的數(shù)組。數(shù)組里元素就是我們之前提到了哈希表(dictht) 。ht為什么長度為2 這就需要我們了解下redis的rehash過程了。而rehashidx就是記錄rehash的進(jìn)度！在沒有發(fā)生rehash的時(shí)候rehashidx=-1;

• 在實(shí)際使用過程中在字典中我們所有的數(shù)據(jù)都會存儲在ht[0]對應(yīng)的哈希表中。ht[1]永遠(yuǎn)都是一個(gè)空數(shù)組。這些都是為什么rehash做準(zhǔn)備，在正式開始之前我們先來了解下redis為什么需要rehash這個(gè)動作

• 首先我們在哈希表中是一個(gè)定長數(shù)組發(fā)生沖突時(shí)內(nèi)部是通過鏈表解決的。理論上一個(gè)哈希表可以存儲足夠的數(shù)據(jù)，這里的足夠就是指空間允許的范圍有多少存多少。但是我們知道鏈表的特點(diǎn)就是新增、刪除很快但是查詢很慢，尤其是當(dāng)鏈表很長的時(shí)候就會出現(xiàn)查詢效率低下的問題！為了避免鏈表過長redis就會在一定條件下對哈希表中數(shù)組長度的擴(kuò)展從而解決局部鏈表過長的問題！

• 每次數(shù)組發(fā)生長度變化時(shí)，那么之前的hash值就需要重新經(jīng)歷一遍hash然后尋址index的過程。這個(gè)過程就叫做rehash 。

• 關(guān)于rehash和Java中Map的resize是一樣的功能！Java中resize是直接new 出一片內(nèi)存進(jìn)行復(fù)制的而且他是每次進(jìn)行2倍擴(kuò)展。而redis的rehash稍微不同基本上我們也可以理解成2倍擴(kuò)展！關(guān)于兩塊內(nèi)存復(fù)制有點(diǎn)類似于JVM中垃圾回收有點(diǎn)類似。有時(shí)間我們可以一起研究下JVM章節(jié)。

• 那么啥時(shí)候需要進(jìn)行rehash呢？這里和Java的負(fù)載因子一樣；但是除了負(fù)載因子這個(gè)空間考核以外redis還考慮一個(gè)性能的問題。因?yàn)樵趩尉€程的前提下我們還要考慮客戶端使用的感知性！單線程的意思就是執(zhí)行命令是順序執(zhí)行的。總不能在我們r(jià)ehash的過程中全部阻塞客戶端的使用這對于操作體驗(yàn)上穩(wěn)定性來說是不友好的。

• 涉及到上述兩個(gè)命令的我們稱之為后臺命令結(jié)合負(fù)載因子產(chǎn)生如下條件

漸進(jìn)式rehash

• 一直強(qiáng)調(diào)redis是單線程。那么什么叫單線程模型？就是對于redis服務(wù)來說執(zhí)行命令是線性操作！但是每個(gè)客戶端的命令是無序的，先到的就先進(jìn)入隊(duì)列redis服務(wù)從隊(duì)列一次取出命令進(jìn)行執(zhí)行。除了客戶端的命令還有一些系統(tǒng)生成的命令比如說我們上面提到的rehash操作！

• ①、首先為了避免阻塞客戶端或者說盡量控制阻塞的時(shí)間在客戶端感知范圍內(nèi)，redis內(nèi)部的rehash并不是一次性操作而是一個(gè)循序漸進(jìn)的過程。一次僅復(fù)制一部分

• ②、還記得之前我們提到dict中rehashidx這個(gè)屬性嗎，他是記錄rehash的進(jìn)度。因?yàn)楣１韮?nèi)部是一個(gè)數(shù)組而rehashidx就是記錄這個(gè)數(shù)組的索引。從而我們也可以知道每次rehash復(fù)制的時(shí)候是已一個(gè)索引完整鏈表為單元進(jìn)行復(fù)制的。

• ③、除了新增以外的其他操作都會同時(shí)影響到ht[0]、ht[1] 因?yàn)樵趓ehash過程中兩個(gè)數(shù)組都是在使用狀態(tài)的

• ④、新增值的時(shí)候就只需要新增到ht[1]中。因?yàn)樽罱K的目的就是將所有值同步到ht[1]中。而ht[0]的值會慢慢的變少；沒必要新增到ht[0]

• ⑤、在rehash過程中查找元素時(shí)會查找兩個(gè)數(shù)組中的并集元素。這也就也是了為什么再rehash過程新增元素只需要新增到ht[1]的原因

總結(jié)

①、字典表在redis被廣泛使用，基于字典表優(yōu)秀的設(shè)計(jì)解決redis單線程問題

②、字典里包含哈希表，哈希表內(nèi)部使用節(jié)點(diǎn)負(fù)責(zé)存儲key、value

③、字典type實(shí)現(xiàn)多態(tài)字典用于多場景！

④、漸進(jìn)式rehash解決服務(wù)卡頓問題

作者：zxhtom
鏈接：https://juejin.cn/post/6981201729651998756
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。