01 概 述
近日，Tair團隊的一篇論文——HotRing: A Hotspot-Aware In-Memory Key-Value Store 被FAST'20 Research Track接收 (USENIX Conference on File and Storage Techniques (FAST)，CCF A類會議，存儲領域頂會，2020年接受率16%)。
HotRing是Tair團隊的創新性純記憶體KV存儲引擎設計。其引擎吞吐性能可達600M ops/s，與目前最快的KVS系統相比，可實作2.58倍的性能提升。HotRing最重要的創新點是：極大的提升了KVS引擎對于熱點通路的承載能力。這對于KVS系統的穩定性以及成本控制尤為關鍵。
為了友善大家更通俗全面的了解這篇論文，本文将從阿裡巴巴的雙十一零點峰值講起，介紹峰值下資料庫整體架構所面臨的熱點問題，再介紹Tair團隊在解決熱點方面一次次的優化提升，最後介紹Tair的創新性引擎HotRing。
02 背 景
零點峰值
2019年天貓雙11再次重新整理世界紀錄，零點的訂單峰值達到54.4萬筆/秒。有訂單就涉及到交易，有交易就需要資料庫的事務保證，是以阿裡巴巴資料庫将在這時面臨巨大的沖擊。
現實往往更加嚴峻，在業務方面，一次訂單随着業務邏輯在後端會放大為數十次的通路；在客戶方面，大量的客戶隻是瘋狂的通路，并沒有生成訂單。是以，在雙11的零點峰值，業務實際的通路量級是10億次/秒。
Tair作為高并發分布式的KVS系統，在這時發揮了重要作用。如下面的邏輯圖所示，Tair作為資料庫的分布式緩存系統，緩存了大量的熱點資料(例如商品，庫存，風控資訊等)，為資料庫抵擋了巨大的通路量。2019年雙11，Tair的峰值通路為9.92億次/秒。
熱點問題
在業務層面，熱點問題很好了解，最典型的就是雙十一零點秒殺。這會導緻資料通路呈現嚴重傾斜的幂律分布。
我們分析了多種業務的資料通路分布，如下圖所示，大量的資料通路隻集中在少部分的熱點資料中，若用離散幂率分布(Zipfian)刻畫，其θ參數約為1.22。相似地，Facebook的一篇論文同樣也展示了近似的資料通路分布(參考論文[3])。
直覺上可以用下圖來解釋。以蘋果新手機發售舉例。手機的庫存等資訊隻存在KVS的一個節點中。當新手機發售後，大量的果粉瘋狂進行搶購下單，業務的通路量基本都聚集在這一個節點上。節點可能無法承載大量的熱點通路，進而引發系統崩潰，嚴重影響使用者體驗。
熱點優化
為了保證雙十一絲般順滑的購物體驗，Tair針對熱點問題進行了多層優化：
- 用戶端緩存：通過預先标記熱點，設定用戶端層面的緩存。以上圖來了解，就是将通路在業務層面傳回，直接減小了KVS系統的負載壓力。
- 熱點散列技術：通過将熱點資料備份到多個KVS節點上，分攤熱點通路。以少量成本的資源與系統開銷，換取了成倍的系統承載力。
- RCU無鎖引擎：通過采用Read-Copy-Update的方式，實作記憶體KV引擎的無鎖化(lock-free)通路(參考論文[1,2])。成倍提升KVS引擎的性能，進而提高熱點的承載力。
- HotRing：在RCU無鎖引擎基礎上，我們進行索引結構的熱點感覺設計，提出了一種名為HotRing的新型熱點感覺記憶體KVS。HotRing可動态識别熱點，并實時的進行索引結構的無鎖調整，對于幂律分布場景實作成倍的引擎性能提升。
經過十年的技術沉澱，我們已将集團Tair資料庫的緩存技術釋放到雲上，普惠大衆，即“阿裡雲Redis企業版”。
03 HotRing
現有技術
現有的記憶體KVS引擎通常采用鍊式哈希作為索引，結構如下圖所示。首先，根據資料的鍵值(k)計算其哈希值h(k)，對應到哈希表(Hash table)的某個頭指針(Headi)。根據頭指針周遊相應的沖突鍊(Collision Chain)的所有資料(Item)，通過鍵值比較，找到目标資料。如果目标資料不在沖突鍊中(read miss)，則可在沖突鍊頭部插入該資料。
在鍊式哈希索引結構中，通路位于沖突鍊尾部的資料，需要經過更多的索引跳數，即更多次的記憶體通路。很直覺的想法是，如果可以将熱點資料放置在沖突鍊頭部，那麼系統對于熱點資料的通路将會有更快的響應速度。
但是，資料在沖突鍊中的位置由資料的插入順序決定，這和資料的冷熱程度是互相獨立的。是以，如圖所示，熱點資料(Hot Item)在沖突鍊中的位置是完全均勻分布。
設計挑戰
理想的設計也很直覺，就是将所有熱點資料移動到沖突鍊的頭部。但有兩方面因素使得這個問題非常難解。一方面，資料的熱度是動态變化的，必須實作動态的熱點感覺保證熱點時效性。另一方面，記憶體KVS的引擎性能是很敏感的(一次通路的時延通常是100ns量級)，必須實作無鎖的熱點感覺維持引擎的高并發與高吞吐特性。
HotRing整體設計
HotRing在傳統鍊式哈希索引基礎上，實作了有序環式哈希索引設計。如下圖所示，将沖突鍊首尾連接配接形式沖突環，保證頭指針指向任何一個item都可以周遊環上所有資料。然後，HotRing通過lock-free移動頭指針，動态指向熱度較高的item（或根據算法計算出的最優item位置），使得通路熱點資料可以更快的傳回。
下面通過如下4方面進行介紹：
- 設計1：為什麼要實作為有序環？
- 設計2：如何動态識别熱點并調整頭指針？
- 設計3：如何保證無鎖的并發通路？
- 設計4：如何根據熱點資料量的動态變化進行無鎖rehash？
設計1——有序環
實作環式哈希索引後，第一個問題是要保證查詢的正确性。若為無序環，當一個read miss操作周遊沖突環時，它需要一個标志來判斷周遊何時終止，否則會形式死循環。但是在環上，所有資料都會動态變化(更新或删除)，頭指針同樣也會動态移動，沒有标志可以作為周遊的終止判斷。
利用key排序可以解決這個問題，若目标key介于連續兩個item的key之間，說明為read miss操作，即可終止傳回。由于實際系統中，資料key的大小通常為10~100B，比較會帶來巨大的開銷。哈希結構利用tag來減少key的比較開銷。
如下圖所示，tag是哈希值的一部分，每個key計算的哈希值，前k位用來哈希表的定位，後n-k位作為沖突鍊中進一步區分key的标志。為了減小排序開銷，我們建構字典序：order = (tag, key)。先根據tag進行排序，tag相同再根據key進行排序。
下圖比較了HotRing與傳統鍊式哈希。以itemB舉例，鍊式哈希需要周遊所有資料才能傳回read miss。而HotRing在通路itemA與C後，即可确認B read miss。是以針對read miss操作，鍊式哈希需要周遊整個沖突鍊；而HotRing利用字典序，不僅可以正确終止，且平均隻需周遊1/2沖突環。
設計2——動态識别與調整
HotRing實作了兩種政策來實作周期性的熱點識别與調整。每R次通路為一個周期(R通常設定為5)，第R次通路的線程将進行頭指針的調整。兩種政策如下：
随機移動政策：每R次通路，移動頭指針指向第R次通路的item。若已經指向該item，則頭指針不移動。該政策的優勢是， 不需要額外的中繼資料開銷，且不需要采樣過程，響應速度極快。
采樣分析政策：每R次通路，嘗試啟動對應沖突環的采樣，統計item的通路頻率。若第R次通路的item已經是頭指針指向的item，則不啟動采樣。
采樣所需的中繼資料結構如下圖所示，分别在頭指針處設定Total Counter，記錄該環的通路總次數，每個item設定Counter記錄該item的通路次數。因為記憶體指針需要配置設定64bits，但實際系統位址索引隻使用其中的48bits。我們使用剩餘16bits設定标志位(例如Total Counter、Counter等)，保證不會增加額外的中繼資料開銷。該政策的優勢是，通過采樣分析，可以計算選出最優的頭指針位置，穩态時性能表現更優。
這一部分的細節設計有很多：
- 采樣分析政策如何選出最優位置；
- 針對RCU更新操作的采樣優化，
- 熱點繼承防止冷啟動。
本文不再較長的描述，有興趣請參考HotRing論文。
設計3——無鎖并發通路
Tair的RCU無鎖引擎是HotRing的設計基礎。參考論文[1,2]對如何實作無鎖連結清單進行了詳細講解，後續的所有無鎖設計基本都沿用了他們的政策。有興趣可以讀一下。這裡我們舉一個典型的并發示例進行介紹。
如下圖所示，在鍊A->B->D上，線程1進行插入C的操作，同時線程2進行RCU更新B的操作，嘗試更新為B'。線程1修改B的指針指向C，完成插入。而線程2修改A的指針指向B'完成更新。兩個線程并發修改不同的記憶體，均可成功傳回。但是這時周遊整條鍊(A->B'->D)，将發現C無法被周遊到，導緻正确性問題。
解決措施是利用上圖(Item Format)中的Occupied标志位。當線程2更新B時，首先需要将B的Occupied标志位置位。線程1插入C需要修改B的指針(Next Item Address)，若發現Occupied标志位已置位，則需要重新周遊連結清單，嘗試插入。通過使并發操作競争修改同一記憶體位址，保證并發操作的正确性。
利用相同原理，我們保證了頭指針移動操作，與CRUD操作的并發正确性。是以實作了HotRing的無鎖并發通路。
設計4——适應熱點資料量的無鎖rehash
如背景所述，對于極端的幂率分布場景，大量的資料通路隻集中在少部分的熱點資料中。是以隻要保證熱點資料可以位于頭指針位置，沖突環即使很長，對于引擎的性能表現并不影響。引擎性能的降低，必然是因為沖突環上存在多個熱點。是以HotRing設計了适應熱點資料量的無鎖rehash政策來解決這一問題。
HotRing利用通路所需平均記憶體通路次數(access overhead)來替代傳統rehash政策的負載因子(load factor)。在幂率分布場景，若每個沖突環隻有一個熱點，HotRing可以保證access overhead < 2，即平均每次通路所需記憶體通路次數小于2。是以設定access overhead門檻值為2，當大于2時，觸發rehash。
rehash過程分為3步進行，結合上面4圖進行說明，圖一為哈希表，哈希值在rehash前後的變化。剩餘三圖為rehash三個過程。
初始化(Initialization)：首先，HotRing建立一個背景rehash線程。該線程建立2倍空間的新哈希表，通過複用tag的最高一位來進行索引。是以，新表中将會有兩個頭指針與舊表中的一個頭指針對應。HotRing根據tag範圍對資料進行劃分。假設tag最大值為T，tag範圍為[0,T)，則兩個新的頭指針對應tag範圍為[0,T/2)和[T/2,T)。同時，rahash線程建立一個rehash節點(包含兩個空資料的子item節點)，子item節點分别對應兩個新頭指針。HotRing利用item中的Rehash标志位識别rehash節點的子item節點。
分裂(Split)：在分裂階段，rehash線程通過将rehash節點的兩個子item節點插入環中完成環的分裂。如圖(Split)所示，因為itemB和E是tag的範圍邊界，是以子item節點分别插入到itemB和E之前。完成兩個插入操作後，新哈希表将激活，所有的通路都将通過新哈希表進行通路。到目前為止，已經在邏輯上将沖突環一分為二。當我們查找資料時，最多隻需要掃描一半的item。
删除(Deletion)：删除階段需要做一些首尾工作，包括舊哈希表的回收。以及rehash節點的删除回收。這裡需要強調，分裂階段和删除階段間，必須有一個RCU靜默期(transition period)。該靜默期保證所有從舊哈希表進入的通路均已經傳回。否則，直接回收舊哈希表可能導緻并發錯誤。
04 總 結
記憶體鍵值存儲系統由于高性能、易擴充等特性在雲存儲服務中廣泛使用。其通常作為必不可少的緩存元件，以解決持久化存儲系統或分布式存儲系統中的熱點問題。
但分析發現，記憶體KVS内部的熱點問題更加嚴重，其資料通路分布同樣服從幂律分布，且通路傾斜愈加嚴重。現有的記憶體KVS缺乏熱點優化意識，部分資料節點可能無法承載大量的熱點通路，進而引發系統崩潰，嚴重影響使用者體驗。
在本論文中，我們進行索引結構的熱點感覺設計，提出了一種名為HotRing的新型熱點感覺記憶體KVS，針對幂率分布的熱點場景進行大量優化。HotRing可動态識别熱點，并實時的進行索引結構的無鎖調整，進而提供高并發高性能的無鎖化通路。
與傳統的記憶體KVS索引相比，HotRing采用輕量級的熱點識别政策，且沒有增加中繼資料存儲開銷。但在幂律分布的應用場景中，HotRing的引擎吞吐性能可達600M ops/s，與目前最快KVS相比，可實作2.58倍的性能提升。
參考
[1] John D Valois. Lock-free linked lists using compare-and-swap. (PODC 1995)
[2] Timothy L Harris. A Pragmatic Implementation of Non-blocking Linked-lists. (DISC 2001)
[3] Berk Atikoglu. Workload Analysis of a Large- Scale Key-Value Store. (SIGMETRICS 2012)