java開發十年技術變化（阿里最快KV存儲引擎揭秘）

2023-09-19 11:13:10 1

簡介：

阿里雲智能資料庫Tair團隊主要負責自研分布式鍵值存儲(KVS)系統，幾乎涵蓋了淘寶、天貓、阿里媽媽、菜鳥、釘釘、優酷、高德等阿里巴巴所有核心業務。十多年來，始終如一為阿里業務提供著高可靠、高性能、低成本的數據存儲與訪問服務。

近日，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。

2019年天貓雙11再次刷新世界紀錄，零點的訂單峰值達到54.4萬筆/秒。有訂單就涉及到交易，有交易就需要資料庫的事務保證，因此阿里巴巴資料庫將在這時面臨巨大的衝擊。

現實往往更加嚴峻，在業務方面，一次訂單隨著業務邏輯在後端會放大為數十次的訪問；在客戶方面，大量的客戶只是瘋狂的訪問，並沒有生成訂單。因此，在雙11的零點峰值，業務實際的訪問量級是10億次/秒。

Tair作為高並發分布式的KVS系統，在這時發揮了重要作用。如下面的邏輯圖所示，Tair作為資料庫的分布式緩存系統，緩存了大量的熱點數據(例如商品，庫存，風控信息等)，為資料庫抵擋了巨大的訪問量。2019年雙11，Tair的峰值訪問為9.92億次/秒。

在業務層面，熱點問題很好理解，最典型的就是雙十一零點秒殺。這會導致數據訪問呈現嚴重傾斜的冪律分布。

我們分析了多種業務的數據訪問分布，如下圖所示，大量的數據訪問只集中在少部分的熱點數據中，若用離散冪率分布(Zipfian)刻畫，其θ參數約為1.22。相似地，Facebook的一篇論文同樣也展示了近似的數據訪問分布(參考論文[3])。

直觀上可以用下圖來解釋。以蘋果新手機發售舉例。手機的庫存等信息只存在KVS的一個節點中。當新手機發售後，大量的果粉瘋狂進行搶購下單，業務的訪問量基本都聚集在這一個節點上。節點可能無法承載大量的熱點訪問，進而引發系統崩潰，嚴重影響用戶體驗。

為了保證雙十一絲般順滑的購物體驗，Tair針對熱點問題進行了多層優化：

經過十年的技術沉澱，我們已將集團Tair資料庫的緩存技術釋放到雲上，普惠大眾，即「阿里雲Redis企業版」。

現有的內存KVS引擎通常採用鏈式哈希作為索引，結構如下圖所示。首先，根據數據的鍵值(k)計算其哈希值h(k)，對應到哈希表(Hash table)的某個頭指針(Headi)。根據頭指針遍歷相應的衝突鏈(Collision Chain)的所有數據(Item)，通過鍵值比較，找到目標數據。如果目標數據不在衝突鏈中(read miss)，則可在衝突鏈頭部插入該數據。

在鏈式哈希索引結構中，訪問位於衝突鏈尾部的數據，需要經過更多的索引跳數，即更多次的內存訪問。很直觀的想法是，如果可以將熱點數據放置在衝突鏈頭部，那麼系統對於熱點數據的訪問將會有更快的響應速度。

但是，數據在衝突鏈中的位置由數據的插入順序決定，這和數據的冷熱程度是互相獨立的。因此，如圖所示，熱點數據(Hot Item)在衝突鏈中的位置是完全均勻分布。

理想的設計也很直觀，就是將所有熱點數據移動到衝突鏈的頭部。但有兩方面因素使得這個問題非常難解。一方面，數據的熱度是動態變化的，必須實現動態的熱點感知保證熱點時效性。另一方面，內存KVS的引擎性能是很敏感的(一次訪問的時延通常是100ns量級)，必須實現無鎖的熱點感知維持引擎的高並發與高吞吐特性。

HotRing在傳統鏈式哈希索引基礎上，實現了有序環式哈希索引設計。如下圖所示，將衝突鏈首尾連接形式衝突環，保證頭指針指向任何一個item都可以遍歷環上所有數據。然後，HotRing通過lock-free移動頭指針，動態指向熱度較高的item（或根據算法計算出的最優item位置），使得訪問熱點數據可以更快的返回。

下面通過如下4方面進行介紹：

實現環式哈希索引後，第一個問題是要保證查詢的正確性。若為無序環，當一個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衝突環。

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等)，保證不會增加額外的元數據開銷。該策略的優勢是，通過採樣分析，可以計算選出最優的頭指針位置，穩態時性能表現更優。

這一部分的細節設計有很多：

本文不再詳細描述，有興趣請參考HotRing論文。

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的無鎖並發訪問。

如背景所述，對於極端的冪率分布場景，大量的數據訪問只集中在少部分的熱點數據中。因此只要保證熱點數據可以位於頭指針位置，衝突環即使很長，對於引擎的性能表現並不影響。引擎性能的降低，必然是因為衝突環上存在多個熱點。因此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)。該靜默期保證所有從舊哈希表進入的訪問均已經返回。否則，直接回收舊哈希表可能導致並發錯誤。

內存鍵值存儲系統由於高性能、易擴展等特性在雲存儲服務中廣泛使用。其通常作為必不可少的緩存組件，以解決持久化存儲系統或分布式存儲系統中的熱點問題。

但分析發現，內存KVS內部的熱點問題更加嚴重，其數據訪問分布同樣服從冪律分布，且訪問傾斜愈加嚴重。現有的內存KVS缺乏熱點優化意識，部分數據節點可能無法承載大量的熱點訪問，進而引發系統崩潰，嚴重影響用戶體驗。

在本論文中，我們進行索引結構的熱點感知設計，提出了一種名為HotRing的新型熱點感知內存KVS，針對冪率分布的熱點場景進行大量優化。HotRing可動態識別熱點，並實時的進行索引結構的無鎖調整，進而提供高並發高性能的無鎖化訪問。

與傳統的內存KVS索引相比，HotRing採用輕量級的熱點識別策略，且沒有增加元數據存儲開銷。但在冪律分布的應用場景中，HotRing的引擎吞吐性能可達600M ops/s，與目前最快KVS相比，可實現2.58倍的性能提升。

來源：阿里雲開發者社區