首先需要說明的是，HotRing是阿里核心緩存系統Tair的一個子組件。Tair是阿里一個NoSQL內存數據庫(Tair在阿里云上稱為企業版Redis)。HotRing是Tair用來解決沖突鏈表長度導致性能衰減問題的一個子組件。

[[324882]]

為什么需要HotRing

HotRing不是要解決緩存集群服務中單節點的并發能力上限，這一點一定要注意。它要解決的問題是緩存核心數據結構Hash中鏈表沖突導致性能衰減的問題。所以，阿里工程師測試出來的帶有HotRing的Tair，其性能相比目前其他最快的KV系統，是它們的2.58倍。根據壓力測試可知，HotRing對于緩存集群的每個節點處理熱點數據，是一個非常有用的數據結構。

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

背景和動機

這一段落，我們首先介紹Hash索引和KV系統中存在的熱點問題。然而，我們會給出熱點感應理論的潛在好處。最后，我們討論感應熱點的挑戰以及我們的設計原則。

Hash索引和熱點問題

Hash索引是KV存儲中最流行的數據結構，尤其當上游系統不需要范圍查詢的時候。下圖是典型的hash索引結構，其包含一張全局的Hash表，并且每個Entry都有一個沖突的鏈表。當我們訪問一個元素時，首先計算它的hash值h，這樣就能定位到Entry，然后在沖突鏈表上尋找我們要找的KEY。我們假設hash值h有n位，我們將其分為兩部分，前面 k位用來作為hash表部分，后面n-k位用來作為tag部分，如下圖所示：

這樣的數據結構有一個很明顯的問題，如下圖所示。沖突的鏈表越長，需要訪問的內存次數就越多。因為在鏈表上查找某個KEY的時間復雜度是O(n)：

這樣的數據結構還帶來一個問題，我們再看上面的(Figure 2)，因為它無法感知熱點數據，那么熱點數據很可能在鏈表的頭部，也可能在鏈表的尾部，也可能均勻分散在鏈表上。熱點數據越接近尾部，訪問內存的次數就越高，性能就會越差，而且會隨著并發的提升，表現會更差。所以，這樣的數據結構對熱點數據是非常不友好的。

也有一些方法減少熱點數據訪問代價，但是，效果非常有限。首先，比如CPU緩存可以加速訪問熱點數據塊。但是對大部分的服務器來說，CPU緩存只有32M左右。對于一個256G的Redis緩存集群來說，它只能緩存0.012%的數據。

0.012%的比例肯定是不夠用的。阿里團隊分析了他們的業務數據分布，得到如下圖所示的結論。即對于一個Redis集群來說，50%～90%的情況下會訪問集群中1%的KEY。：

CPU緩存這種方案行不通。還有另一種辦法：Rehash。通過Rehash來減少沖突鏈表的長度。沖突鏈表長度越短，熱點數據訪問的代價就越小，性能就會越高。但是。當Hash表已經非常大的時候，非常不建議Rehash。因為Rehash可能僅帶來一半的功效(就減少鏈長而言)。總而言之，所有現有方法都只能在較小程度上緩解熱點問題。

當我們論證HotRing的價值后，就剩下挑戰需要我們去解決了，我們的設計主要面對以下兩個問題：

熱點轉移(Hotspot Shift)。真實系統的緩存中熱點數據是會隨著時間發生變化的，比如今天是IQOO3，明天是Mate30，后臺是iPhone。所以，我們需要一個輕量的方案來跟蹤這些熱點切換問題。

并發訪問(Concurrent Access)。每個熱點數據的并發都會非常高，所以支持高并發的讀寫，才能達到令人滿意的性能。

HotRing簡介

讓我們看看阿里的HotRing是如何設計來優化沖突鏈表訪問性能問題的。如下圖所示，由沖突環取代之前的沖突鏈表，并且有一個Head指針，它會指向或者接近最熱的KEY，并且這個環是有序的。Head指針非常有用，當熱點數據發生轉移時，只需要更改這個Head指針，讓其指向環上最熱的數據，或者一個更好的位置。熱點數據轉移策略有兩種，后面會細講：

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

HotRing設計

接下來，讓我們更深入的了解HotRing的設計細節，包括索引結構，特點轉移探測策略，無鎖操作(包括讀寫，插入刪除，Head指針移動，Rehash等)。

有序環索引結構

如上面的(Figure 4)圖描述了HotRing的索引結構，它主要改進了傳統Hash索引沖突鏈表結構。阿里HotRing的設計將最后一個KEY和第一個KEY連起來，并稱之為沖突環。這樣的話，Head指針可以指向任意一個元素，并不一定是固定在鏈表的第一個元素。這樣的設計，就可以將Head指向熱點數據。需要注意的是，當沖突環上只有一個數據時，Head的next指向它本身。

但是環形設計有一個很嚴重的問題，就是如果KEY不存在的話，就會導致死循環。因此，需要一個很好的方案解決這個問題，這非常重要。看到這里，你可能會有疑問，為什么不把Head指針當作起點，也當作終點呢?不可以，因為由于并發問題，Head指針可能會被修改。因此，HotRing的設計是讓沖突環有序，并且根據KEY進行排序。這樣的話，當我們在沖突環上查找某個KEY時，如果連續碰到兩個KEY且一個比目標KEY大，一個比目標KEY小，就表示找不到目標KEY，那么就可以安全的停止查找了。

下圖對比了沖突鏈表和HotRing兩種數據結構訪問方式。在HotRing中，Head指向A(3, 25)，假設我們要查詢B(4，35)，那么從Head開始，訪問到C(5，65)就可以結束了。而在沖突鏈表中，我們需要遍歷A，C，D，E，F，I后才能停止訪問：

熱點轉移識別

如剛才講到，在HotRing中，無論是查找一個存在的KEY還是不存在的KEY，都非常容易。那么還有一個很棘手的問題，就是當熱點發生轉移的時候，如何識別并調整Head指針。比如熱點本來在A(3，25)上，隨著時間的推移，當熱點轉移到D(5, 68)時，如何感知，并將Head移到D(5, 68)上。

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

1.隨機移動策略

我們首先介紹的是隨機移動策略，這種策略的特點是反應靈敏，但是精準度不及后面介紹的統計采樣策略。這個策略的基本思路就是周期性的將Head指針移到一個潛在的熱點KEY上，不需要記錄任何歷史數據。每個線程會有一個ThreadLocal變量記錄它執行的請求數，每滿R次請求，線程決定是否需要移動Head指針。假設第R次訪問剛好是熱點訪問，那么不需要移動Head指針。反之，將指針移動到訪問的這個元素上，這個元素變為新的熱點數據。

這個參數R會影響反應靈敏度和識別精確度，如果R的值比較小，反應靈敏度會變高，但是就會帶來頻繁的，無效的Head指針移動。在我們的使用場景中，訪問的數據高度傾斜，因此Head指針移動應該不會頻繁。根據經驗，這個R值默認設置為5。

需要注意的是，如果數據傾斜不明顯的話，這個隨機策略的效果就不是很理想。更重要的是，這個策略不能處理一個環上有多個熱點KEY的場景。因為在這種場景下，Head指針會頻繁的在這些熱點KEY之間移動。如此一來，不但不能加速熱點數據訪問，可能還會影響常規操作。

2.統計采樣策略

為了訪問熱點數據的性能最高，因為我們設計了統計采樣策略。它提供了更精準的特點識別能力，但是相比隨機策略反應會遲鈍一些。接下來首先介紹每個KEY的詳細格式，以及HotRing上的Head指針，講解如何利用這些數據格式在沒有額外空間消耗的前提下維護統計信息，然后我們詳細闡述采樣策略預估訪問頻率。最終，我們要找到一個方法，當熱點數據轉移時，能讓Head指針移動到最佳位置，并且支持多個熱點KEY存在一個HotRing上的情況。

并發操作

Head指針無鎖(lock-free)設計會比較復雜，主要反映在幾個方面：一方面，Head指針可能被多個線程并發執行移動操作。因為要考慮Head指針的并發情況，防止Head指針移動到無效的KEY上。另一方面，當我們刪除或者更新KEY時，我們需要檢查Head指針是否在這些KEY上。如果是，那我我們要保證移動Head的準確性。接下來我們從增刪改查這4個維度詳細講述HotRing上的并發操作。

1.查詢

在HotRing上查找一個目標KEY就是從Head開始查找，前面已經提到過，不需要任何額外的動作，讀操作本身就是無鎖的。

2.新增

新增操作如下圖所示，假設創建一個C，同時并發修改B為B'。假如沒有并發保護，插入C后，鏈路就是B->C->D。同時將B修改為B'，鏈路就是A->B'->D。這樣的話，從A遍歷，就會發現C已經丟失了。

3.修改

修改操作如下圖所示，假設有一個線程將B修改為B‘，同時另一個線程將D修改為D‘，如果沒有并發保護，就會導致最終的鏈路變成：A->B'->D->E，即D'會丟失：

4.刪除

刪除操作如下圖所示，假設有一個線程將D修改為D‘，同時另一個線程將B線程。如果沒有并發保護，可能導致最終的鏈路變成A->D->E，即D'會丟失：

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

5.Head指針移動

為了確保Head指針操作的準確性，尤其在更新和刪除的時候。HotRing分不同情況解決這個問題。如果是識別策略導致Head指針移動時，也用Occupied這個占位符來解決并發問題。比如識別策略達到滿足Head指針移動的條件，首先將Head指針指向的元素的Occupied置為true。確保它不被更新和刪除(因為這時候如果有并發更新和刪除，發現它們要操作的KEY的Occupied為true，就會重試)。然后將Head指針移到新的KEY上，移動之前，需要確保新的KEY沒有被其他線程更新或者刪除，因此移動Head之前，還需要將新的KEY的Occupied置為true，當Head指針移動完成后，再將這兩個KEY的Occupied重置。然后其他線程就能操作這兩個KEY了。

無鎖Rehash

傳統的Rehash策略一般由負載因子觸發，例如沖突鏈表平均長度等。然后這種策略沒有考慮熱點數據，所以對HotRing不適合。取而代之的是，HotRing用訪問成本來觸發Rehash(獲取數據時平均內存訪問次數)。如下圖所示，HotRing的無鎖Rehash分為如下3個主要步驟：

1.初始化

首先HotRing創建一個rehash的后臺線程，這個線程初始化一個size是舊hash表兩倍的新hash表。通過復用tag的最高一位來進行索引。因此，新表中將會有兩個Head指針與舊表中的一個Head指針對應。HotRing根據tag范圍對數據進行劃分。假設tag最大值為T，tag范圍為[0,T)，則兩個新的Head指針對應tag范圍為[0,T/2)和[T/2,T)。同時，rehash線程創建一個rehash節點(如下右圖中間節點所示，包含兩個空數據的子元素節點)，子元素節點分別對應兩個新Head指針(Head1和Head2)。HotRing利用元素中的Rehash標志位識別rehash節點的子元素節點：

2.分裂

在分裂階段，rehash線程通過將rehash節點的兩個子元素節點插入沖突環中完成環的分裂。如圖(Split)所示，因為B和E是tag的范圍邊界，所以子元素節點分別插入到B和E之前。完成兩個插入操作后，新hash表將激活，所有的訪問都將通過新hash表進行訪問。到目前為止，已經在邏輯上將沖突環一分為二。接下來當我們查找數據時，最多需要掃描相比舊hash表一半的元素：

3.刪除

刪除階段需要做一些收尾性的工作，包括舊hash表的回收。以及rehash節點的刪除回收。這里需要強調，分裂階段和刪除階段間，必須有一個RCU靜默期(transition period)。該靜默期保證所有從舊哈希表進入的訪問均已經返回。否則，直接回收舊哈希表可能導致并發錯誤。

總結

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

總結

最后，我們通過YCSB對HotRing方案進行了壓力測試，并對比了行業有名的Memcached等。壓測結果如下圖所示，我們可以看到HotRing方案的吞吐量遠超其他方案：

此外，壓測了鏈表長度對性能的影響，如下圖所示，我們可以發現當鏈表長度從2一直遞增到16的過程中。HotRing方案的性能幾乎是恒定的。而一致性Hash和FASTER方案的性能很明顯梯度遞減了：