首先需要說(shuō)明的是，HotRing是阿里核心緩存系統(tǒng)Tair的一個(gè)子組件。Tair是阿里一個(gè)NoSQL內(nèi)存數(shù)據(jù)庫(kù)(Tair在阿里云上稱為企業(yè)版Redis)。HotRing是Tair用來(lái)解決沖突鏈表長(zhǎng)度導(dǎo)致性能衰減問(wèn)題的一個(gè)子組件。

[[324882]]

為什么需要HotRing

HotRing不是要解決緩存集群服務(wù)中單節(jié)點(diǎn)的并發(fā)能力上限，這一點(diǎn)一定要注意。它要解決的問(wèn)題是緩存核心數(shù)據(jù)結(jié)構(gòu)Hash中鏈表沖突導(dǎo)致性能衰減的問(wèn)題。所以，阿里工程師測(cè)試出來(lái)的帶有HotRing的Tair，其性能相比目前其他最快的KV系統(tǒng)，是它們的2.58倍。根據(jù)壓力測(cè)試可知，HotRing對(duì)于緩存集群的每個(gè)節(jié)點(diǎn)處理熱點(diǎn)數(shù)據(jù)，是一個(gè)非常有用的數(shù)據(jù)結(jié)構(gòu)。

題外話：Tair也有解決單個(gè)節(jié)點(diǎn)性能瓶頸的能力。假設(shè)雙十一淘寶首頁(yè)上的一件商品，我們可知，這件商品信息的TPS起碼是幾百萬(wàn)甚至千萬(wàn)級(jí)別的。這樣的熱點(diǎn)KEY，無(wú)論你的集群有多大，這個(gè)KEY只會(huì)路由到其中的一臺(tái)服務(wù)器上，那么并發(fā)能力就受到單節(jié)點(diǎn)限制，原生的memcache和Redis是完全搞不定的(Redis單節(jié)點(diǎn)TPS大概是10w級(jí)別，memcache可以達(dá)到幾十萬(wàn))。有一種辦法就是自己處理本地緩存，這樣代價(jià)比較大。阿里Tair的做法是熱點(diǎn)散列，如下圖所示，在每一個(gè)DataServer上開(kāi)辟一個(gè)HotZone，統(tǒng)計(jì)到的熱點(diǎn)KEY就保存到集群每一個(gè)節(jié)點(diǎn)上的HotZone中，客戶端把熱點(diǎn)數(shù)據(jù)KEY的請(qǐng)求隨機(jī)打到任意一臺(tái)DataServer的HotZone區(qū)域(熱點(diǎn)KEY并不是Hash取模，這一點(diǎn)很重要)，這樣的話熱點(diǎn)KEY請(qǐng)求就會(huì)被散列到多個(gè)節(jié)點(diǎn)乃至整個(gè)集群。那么整個(gè)Tair集群就不會(huì)因?yàn)槟硞€(gè)熱點(diǎn)KEY而發(fā)生過(guò)載的情況。

背景和動(dòng)機(jī)

這一段落，我們首先介紹Hash索引和KV系統(tǒng)中存在的熱點(diǎn)問(wèn)題。然而，我們會(huì)給出熱點(diǎn)感應(yīng)理論的潛在好處。最后，我們討論感應(yīng)熱點(diǎn)的挑戰(zhàn)以及我們的設(shè)計(jì)原則。

Hash索引和熱點(diǎn)問(wèn)題

Hash索引是KV存儲(chǔ)中最流行的數(shù)據(jù)結(jié)構(gòu)，尤其當(dāng)上游系統(tǒng)不需要范圍查詢的時(shí)候。下圖是典型的hash索引結(jié)構(gòu)，其包含一張全局的Hash表，并且每個(gè)Entry都有一個(gè)沖突的鏈表。當(dāng)我們?cè)L問(wèn)一個(gè)元素時(shí)，首先計(jì)算它的hash值h，這樣就能定位到Entry，然后在沖突鏈表上尋找我們要找的KEY。我們假設(shè)hash值h有n位，我們將其分為兩部分，前面 k位用來(lái)作為hash表部分，后面n-k位用來(lái)作為tag部分，如下圖所示：

這樣的數(shù)據(jù)結(jié)構(gòu)有一個(gè)很明顯的問(wèn)題，如下圖所示。沖突的鏈表越長(zhǎng)，需要訪問(wèn)的內(nèi)存次數(shù)就越多。因?yàn)樵阪湵砩喜檎夷硞€(gè)KEY的時(shí)間復(fù)雜度是O(n)：

這樣的數(shù)據(jù)結(jié)構(gòu)還帶來(lái)一個(gè)問(wèn)題，我們?cè)倏瓷厦娴?Figure 2)，因?yàn)樗鼰o(wú)法感知熱點(diǎn)數(shù)據(jù)，那么熱點(diǎn)數(shù)據(jù)很可能在鏈表的頭部，也可能在鏈表的尾部，也可能均勻分散在鏈表上。熱點(diǎn)數(shù)據(jù)越接近尾部，訪問(wèn)內(nèi)存的次數(shù)就越高，性能就會(huì)越差，而且會(huì)隨著并發(fā)的提升，表現(xiàn)會(huì)更差。所以，這樣的數(shù)據(jù)結(jié)構(gòu)對(duì)熱點(diǎn)數(shù)據(jù)是非常不友好的。

也有一些方法減少熱點(diǎn)數(shù)據(jù)訪問(wèn)代價(jià)，但是，效果非常有限。首先，比如CPU緩存可以加速訪問(wèn)熱點(diǎn)數(shù)據(jù)塊。但是對(duì)大部分的服務(wù)器來(lái)說(shuō)，CPU緩存只有32M左右。對(duì)于一個(gè)256G的Redis緩存集群來(lái)說(shuō)，它只能緩存0.012%的數(shù)據(jù)。

0.012%的比例肯定是不夠用的。阿里團(tuán)隊(duì)分析了他們的業(yè)務(wù)數(shù)據(jù)分布，得到如下圖所示的結(jié)論。即對(duì)于一個(gè)Redis集群來(lái)說(shuō)，50%～90%的情況下會(huì)訪問(wèn)集群中1%的KEY。：

CPU緩存這種方案行不通。還有另一種辦法：Rehash。通過(guò)Rehash來(lái)減少?zèng)_突鏈表的長(zhǎng)度。沖突鏈表長(zhǎng)度越短，熱點(diǎn)數(shù)據(jù)訪問(wèn)的代價(jià)就越小，性能就會(huì)越高。但是。當(dāng)Hash表已經(jīng)非常大的時(shí)候，非常不建議Rehash。因?yàn)镽ehash可能僅帶來(lái)一半的功效(就減少鏈長(zhǎng)而言)。總而言之，所有現(xiàn)有方法都只能在較小程度上緩解熱點(diǎn)問(wèn)題。

當(dāng)我們論證HotRing的價(jià)值后，就剩下挑戰(zhàn)需要我們?nèi)ソ鉀Q了，我們的設(shè)計(jì)主要面對(duì)以下兩個(gè)問(wèn)題：

熱點(diǎn)轉(zhuǎn)移(Hotspot Shift)。真實(shí)系統(tǒng)的緩存中熱點(diǎn)數(shù)據(jù)是會(huì)隨著時(shí)間發(fā)生變化的，比如今天是IQOO3，明天是Mate30，后臺(tái)是iPhone。所以，我們需要一個(gè)輕量的方案來(lái)跟蹤這些熱點(diǎn)切換問(wèn)題。

并發(fā)訪問(wèn)(Concurrent Access)。每個(gè)熱點(diǎn)數(shù)據(jù)的并發(fā)都會(huì)非常高，所以支持高并發(fā)的讀寫，才能達(dá)到令人滿意的性能。

HotRing簡(jiǎn)介

讓我們看看阿里的HotRing是如何設(shè)計(jì)來(lái)優(yōu)化沖突鏈表訪問(wèn)性能問(wèn)題的。如下圖所示，由沖突環(huán)取代之前的沖突鏈表，并且有一個(gè)Head指針，它會(huì)指向或者接近最熱的KEY，并且這個(gè)環(huán)是有序的。Head指針?lè)浅Ｓ杏?，?dāng)熱點(diǎn)數(shù)據(jù)發(fā)生轉(zhuǎn)移時(shí)，只需要更改這個(gè)Head指針，讓其指向環(huán)上最熱的數(shù)據(jù)，或者一個(gè)更好的位置。熱點(diǎn)數(shù)據(jù)轉(zhuǎn)移策略有兩種，后面會(huì)細(xì)講：

至于并發(fā)問(wèn)題，無(wú)鎖(LOCK-FREE)設(shè)計(jì)是最權(quán)威的解決方案，而且很多研究表明無(wú)鎖設(shè)計(jì)能顯著提升性能(JDK8中JUC大量采用CAS盡可能的不加鎖解決并發(fā)，也是一樣的原理)!而在HotRing中引入無(wú)鎖設(shè)計(jì)，可以非常優(yōu)雅的解決并發(fā)寫入與刪除問(wèn)題，并且設(shè)計(jì)團(tuán)隊(duì)還將其應(yīng)用到所有需要的地方，比如：熱點(diǎn)轉(zhuǎn)移探測(cè)，Head指針移動(dòng)，rehash等。

HotRing設(shè)計(jì)

接下來(lái)，讓我們更深入的了解HotRing的設(shè)計(jì)細(xì)節(jié)，包括索引結(jié)構(gòu)，特點(diǎn)轉(zhuǎn)移探測(cè)策略，無(wú)鎖操作(包括讀寫，插入刪除，Head指針移動(dòng)，Rehash等)。

有序環(huán)索引結(jié)構(gòu)

如上面的(Figure 4)圖描述了HotRing的索引結(jié)構(gòu)，它主要改進(jìn)了傳統(tǒng)Hash索引沖突鏈表結(jié)構(gòu)。阿里HotRing的設(shè)計(jì)將最后一個(gè)KEY和第一個(gè)KEY連起來(lái)，并稱之為沖突環(huán)。這樣的話，Head指針可以指向任意一個(gè)元素，并不一定是固定在鏈表的第一個(gè)元素。這樣的設(shè)計(jì)，就可以將Head指向熱點(diǎn)數(shù)據(jù)。需要注意的是，當(dāng)沖突環(huán)上只有一個(gè)數(shù)據(jù)時(shí)，Head的next指向它本身。

但是環(huán)形設(shè)計(jì)有一個(gè)很嚴(yán)重的問(wèn)題，就是如果KEY不存在的話，就會(huì)導(dǎo)致死循環(huán)。因此，需要一個(gè)很好的方案解決這個(gè)問(wèn)題，這非常重要?？吹竭@里，你可能會(huì)有疑問(wèn)，為什么不把Head指針當(dāng)作起點(diǎn)，也當(dāng)作終點(diǎn)呢?不可以，因?yàn)橛捎诓l(fā)問(wèn)題，Head指針可能會(huì)被修改。因此，HotRing的設(shè)計(jì)是讓沖突環(huán)有序，并且根據(jù)KEY進(jìn)行排序。這樣的話，當(dāng)我們?cè)跊_突環(huán)上查找某個(gè)KEY時(shí)，如果連續(xù)碰到兩個(gè)KEY且一個(gè)比目標(biāo)KEY大，一個(gè)比目標(biāo)KEY小，就表示找不到目標(biāo)KEY，那么就可以安全的停止查找了。

下圖對(duì)比了沖突鏈表和HotRing兩種數(shù)據(jù)結(jié)構(gòu)訪問(wèn)方式。在HotRing中，Head指向A(3, 25)，假設(shè)我們要查詢B(4，35)，那么從Head開(kāi)始，訪問(wèn)到C(5，65)就可以結(jié)束了。而在沖突鏈表中，我們需要遍歷A，C，D，E，F(xiàn)，I后才能停止訪問(wèn)：

熱點(diǎn)轉(zhuǎn)移識(shí)別

如剛才講到，在HotRing中，無(wú)論是查找一個(gè)存在的KEY還是不存在的KEY，都非常容易。那么還有一個(gè)很棘手的問(wèn)題，就是當(dāng)熱點(diǎn)發(fā)生轉(zhuǎn)移的時(shí)候，如何識(shí)別并調(diào)整Head指針。比如熱點(diǎn)本來(lái)在A(3，25)上，隨著時(shí)間的推移，當(dāng)熱點(diǎn)轉(zhuǎn)移到D(5, 68)時(shí)，如何感知，并將Head移到D(5, 68)上。

由于Hash值分布非常均勻，所以熱點(diǎn)KEY均勻分布在所有桶中。因此，我們只需要關(guān)注每個(gè)Bucket中如何識(shí)別熱點(diǎn)問(wèn)題即可。實(shí)際上，每個(gè)桶中沖突的元素是很少的(可能只有5～10個(gè))，并且由于熱點(diǎn)數(shù)據(jù)比例一般只有10～20%，這就意味著每個(gè)桶上可能只有一個(gè)熱點(diǎn)KEY。因此，我們要做的就是，把這個(gè)Head指針指向這個(gè)熱點(diǎn)元素。為了獲得很好的性能，我們需要考慮兩個(gè)指標(biāo)：識(shí)別精準(zhǔn)度和反應(yīng)靈敏度(魚(yú)與熊掌不可兼得)。

1.隨機(jī)移動(dòng)策略

我們首先介紹的是隨機(jī)移動(dòng)策略，這種策略的特點(diǎn)是反應(yīng)靈敏，但是精準(zhǔn)度不及后面介紹的統(tǒng)計(jì)采樣策略。這個(gè)策略的基本思路就是周期性的將Head指針移到一個(gè)潛在的熱點(diǎn)KEY上，不需要記錄任何歷史數(shù)據(jù)。每個(gè)線程會(huì)有一個(gè)ThreadLocal變量記錄它執(zhí)行的請(qǐng)求數(shù)，每滿R次請(qǐng)求，線程決定是否需要移動(dòng)Head指針。假設(shè)第R次訪問(wèn)剛好是熱點(diǎn)訪問(wèn)，那么不需要移動(dòng)Head指針。反之，將指針移動(dòng)到訪問(wèn)的這個(gè)元素上，這個(gè)元素變?yōu)樾碌臒狳c(diǎn)數(shù)據(jù)。

這個(gè)參數(shù)R會(huì)影響反應(yīng)靈敏度和識(shí)別精確度，如果R的值比較小，反應(yīng)靈敏度會(huì)變高，但是就會(huì)帶來(lái)頻繁的，無(wú)效的Head指針移動(dòng)。在我們的使用場(chǎng)景中，訪問(wèn)的數(shù)據(jù)高度傾斜，因此Head指針移動(dòng)應(yīng)該不會(huì)頻繁。根據(jù)經(jīng)驗(yàn)，這個(gè)R值默認(rèn)設(shè)置為5。

需要注意的是，如果數(shù)據(jù)傾斜不明顯的話，這個(gè)隨機(jī)策略的效果就不是很理想。更重要的是，這個(gè)策略不能處理一個(gè)環(huán)上有多個(gè)熱點(diǎn)KEY的場(chǎng)景。因?yàn)樵谶@種場(chǎng)景下，Head指針會(huì)頻繁的在這些熱點(diǎn)KEY之間移動(dòng)。如此一來(lái)，不但不能加速熱點(diǎn)數(shù)據(jù)訪問(wèn)，可能還會(huì)影響常規(guī)操作。

2.統(tǒng)計(jì)采樣策略

為了訪問(wèn)熱點(diǎn)數(shù)據(jù)的性能最高，因?yàn)槲覀冊(cè)O(shè)計(jì)了統(tǒng)計(jì)采樣策略。它提供了更精準(zhǔn)的特點(diǎn)識(shí)別能力，但是相比隨機(jī)策略反應(yīng)會(huì)遲鈍一些。接下來(lái)首先介紹每個(gè)KEY的詳細(xì)格式，以及HotRing上的Head指針，講解如何利用這些數(shù)據(jù)格式在沒(méi)有額外空間消耗的前提下維護(hù)統(tǒng)計(jì)信息，然后我們?cè)敿?xì)闡述采樣策略預(yù)估訪問(wèn)頻率。最終，我們要找到一個(gè)方法，當(dāng)熱點(diǎn)數(shù)據(jù)轉(zhuǎn)移時(shí)，能讓Head指針移動(dòng)到最佳位置，并且支持多個(gè)熱點(diǎn)KEY存在一個(gè)HotRing上的情況。

并發(fā)操作

Head指針無(wú)鎖(lock-free)設(shè)計(jì)會(huì)比較復(fù)雜，主要反映在幾個(gè)方面：一方面，Head指針可能被多個(gè)線程并發(fā)執(zhí)行移動(dòng)操作。因?yàn)橐紤]Head指針的并發(fā)情況，防止Head指針移動(dòng)到無(wú)效的KEY上。另一方面，當(dāng)我們刪除或者更新KEY時(shí)，我們需要檢查Head指針是否在這些KEY上。如果是，那我我們要保證移動(dòng)Head的準(zhǔn)確性。接下來(lái)我們從增刪改查這4個(gè)維度詳細(xì)講述HotRing上的并發(fā)操作。

1.查詢

在HotRing上查找一個(gè)目標(biāo)KEY就是從Head開(kāi)始查找，前面已經(jīng)提到過(guò)，不需要任何額外的動(dòng)作，讀操作本身就是無(wú)鎖的。

2.新增

新增操作如下圖所示，假設(shè)創(chuàng)建一個(gè)C，同時(shí)并發(fā)修改B為B'。假如沒(méi)有并發(fā)保護(hù)，插入C后，鏈路就是B->C->D。同時(shí)將B修改為B'，鏈路就是A->B'->D。這樣的話，從A遍歷，就會(huì)發(fā)現(xiàn)C已經(jīng)丟失了。

3.修改

修改操作如下圖所示，假設(shè)有一個(gè)線程將B修改為B‘，同時(shí)另一個(gè)線程將D修改為D‘，如果沒(méi)有并發(fā)保護(hù)，就會(huì)導(dǎo)致最終的鏈路變成：A->B'->D->E，即D'會(huì)丟失：

4.刪除

刪除操作如下圖所示，假設(shè)有一個(gè)線程將D修改為D‘，同時(shí)另一個(gè)線程將B線程。如果沒(méi)有并發(fā)保護(hù)，可能導(dǎo)致最終的鏈路變成A->D->E，即D'會(huì)丟失：

為了解決上面這幾種并發(fā)導(dǎo)致的問(wèn)題，HotRing用了一個(gè)Occupied位來(lái)解決這個(gè)問(wèn)題。例如，在[2. 新增]即更新和被插入并發(fā)操作時(shí)，更新B時(shí)它的Next被更新，這時(shí)候它的Occupied就會(huì)設(shè)置為true。一旦Occupied設(shè)置為true，接下來(lái)的并發(fā)新增C就會(huì)失敗，因?yàn)锽的Occupied為true，所以必須重試，直到更新操作完成才行。原理非常類似于CAS，即你任何操作涉及的KEY的Occupied都不能是true，是true表示其他并發(fā)操作正在進(jìn)行中。

5.Head指針移動(dòng)

為了確保Head指針操作的準(zhǔn)確性，尤其在更新和刪除的時(shí)候。HotRing分不同情況解決這個(gè)問(wèn)題。如果是識(shí)別策略導(dǎo)致Head指針移動(dòng)時(shí)，也用Occupied這個(gè)占位符來(lái)解決并發(fā)問(wèn)題。比如識(shí)別策略達(dá)到滿足Head指針移動(dòng)的條件，首先將Head指針指向的元素的Occupied置為true。確保它不被更新和刪除(因?yàn)檫@時(shí)候如果有并發(fā)更新和刪除，發(fā)現(xiàn)它們要操作的KEY的Occupied為true，就會(huì)重試)。然后將Head指針移到新的KEY上，移動(dòng)之前，需要確保新的KEY沒(méi)有被其他線程更新或者刪除，因此移動(dòng)Head之前，還需要將新的KEY的Occupied置為true，當(dāng)Head指針移動(dòng)完成后，再將這兩個(gè)KEY的Occupied重置。然后其他線程就能操作這兩個(gè)KEY了。

無(wú)鎖Rehash

傳統(tǒng)的Rehash策略一般由負(fù)載因子觸發(fā)，例如沖突鏈表平均長(zhǎng)度等。然后這種策略沒(méi)有考慮熱點(diǎn)數(shù)據(jù)，所以對(duì)HotRing不適合。取而代之的是，HotRing用訪問(wèn)成本來(lái)觸發(fā)Rehash(獲取數(shù)據(jù)時(shí)平均內(nèi)存訪問(wèn)次數(shù))。如下圖所示，HotRing的無(wú)鎖Rehash分為如下3個(gè)主要步驟：

1.初始化

首先HotRing創(chuàng)建一個(gè)rehash的后臺(tái)線程，這個(gè)線程初始化一個(gè)size是舊hash表兩倍的新hash表。通過(guò)復(fù)用tag的最高一位來(lái)進(jìn)行索引。因此，新表中將會(huì)有兩個(gè)Head指針與舊表中的一個(gè)Head指針對(duì)應(yīng)。HotRing根據(jù)tag范圍對(duì)數(shù)據(jù)進(jìn)行劃分。假設(shè)tag最大值為T，tag范圍為[0,T)，則兩個(gè)新的Head指針對(duì)應(yīng)tag范圍為[0,T/2)和[T/2,T)。同時(shí)，rehash線程創(chuàng)建一個(gè)rehash節(jié)點(diǎn)(如下右圖中間節(jié)點(diǎn)所示，包含兩個(gè)空數(shù)據(jù)的子元素節(jié)點(diǎn))，子元素節(jié)點(diǎn)分別對(duì)應(yīng)兩個(gè)新Head指針(Head1和Head2)。HotRing利用元素中的Rehash標(biāo)志位識(shí)別rehash節(jié)點(diǎn)的子元素節(jié)點(diǎn)：

2.分裂

在分裂階段，rehash線程通過(guò)將rehash節(jié)點(diǎn)的兩個(gè)子元素節(jié)點(diǎn)插入沖突環(huán)中完成環(huán)的分裂。如圖(Split)所示，因?yàn)锽和E是tag的范圍邊界，所以子元素節(jié)點(diǎn)分別插入到B和E之前。完成兩個(gè)插入操作后，新hash表將激活，所有的訪問(wèn)都將通過(guò)新hash表進(jìn)行訪問(wèn)。到目前為止，已經(jīng)在邏輯上將沖突環(huán)一分為二。接下來(lái)當(dāng)我們查找數(shù)據(jù)時(shí)，最多需要掃描相比舊hash表一半的元素：

3.刪除

刪除階段需要做一些收尾性的工作，包括舊hash表的回收。以及rehash節(jié)點(diǎn)的刪除回收。這里需要強(qiáng)調(diào)，分裂階段和刪除階段間，必須有一個(gè)RCU靜默期(transition period)。該靜默期保證所有從舊哈希表進(jìn)入的訪問(wèn)均已經(jīng)返回。否則，直接回收舊哈希表可能導(dǎo)致并發(fā)錯(cuò)誤。

總結(jié)

接下來(lái)簡(jiǎn)單總結(jié)一下HotRing是如何rehash的。首先會(huì)有一個(gè)size為舊表2倍的新的hash表，并且會(huì)有兩個(gè)Head指針：Head1和Head2。分裂時(shí)，原沖突環(huán)中一半的元素跟著Head1，另一半的元素跟著Head2，從而組成兩個(gè)新的沖突環(huán)。最后是一些收尾性的工作，簡(jiǎn)單吧^^

總結(jié)

最后，我們通過(guò)YCSB對(duì)HotRing方案進(jìn)行了壓力測(cè)試，并對(duì)比了行業(yè)有名的Memcached等。壓測(cè)結(jié)果如下圖所示，我們可以看到HotRing方案的吞吐量遠(yuǎn)超其他方案：

此外，壓測(cè)了鏈表長(zhǎng)度對(duì)性能的影響，如下圖所示，我們可以發(fā)現(xiàn)當(dāng)鏈表長(zhǎng)度從2一直遞增到16的過(guò)程中。HotRing方案的性能幾乎是恒定的。而一致性Hash和FASTER方案的性能很明顯梯度遞減了：