[[318583]]

阿里妹導(dǎo)讀：阿里云智能數(shù)據(jù)庫Tair團(tuán)隊主要負(fù)責(zé)自研分布式鍵值存儲(KVS)系統(tǒng)，幾乎涵蓋了淘寶、天貓、阿里媽媽、菜鳥、釘釘、優(yōu)酷、高德等阿里巴巴所有核心業(yè)務(wù)。十多年來，始終如一為阿里業(yè)務(wù)提供著高可靠、高性能、低成本的數(shù)據(jù)存儲與訪問服務(wù)。

01 概 述

近日，Tair團(tuán)隊的一篇論文——HotRing: A Hotspot-Aware In-Memory Key-Value Store 被FAST'20 Research Track接收 (USENIX Conference on File and Storage Techniques (FAST)，CCF A類會議，存儲領(lǐng)域頂會，2020年接受率16%)。

HotRing是Tair團(tuán)隊的創(chuàng)新性純內(nèi)存KV存儲引擎設(shè)計。其引擎吞吐性能可達(dá)600M ops/s，與目前最快的KVS系統(tǒng)相比，可實現(xiàn)2.58倍的性能提升。HotRing最重要的創(chuàng)新點是：極大的提升了KVS引擎對于熱點訪問的承載能力。這對于KVS系統(tǒng)的穩(wěn)定性以及成本控制尤為關(guān)鍵。

為了方便大家更通俗全面的理解這篇論文，本文將從阿里巴巴的雙十一零點峰值講起，介紹峰值下數(shù)據(jù)庫整體架構(gòu)所面臨的熱點問題，再介紹Tair團(tuán)隊在解決熱點方面一次次的優(yōu)化提升，最后介紹Tair的創(chuàng)新性引擎HotRing。

02 背 景

零點峰值

2019年天貓雙11再次刷新世界紀(jì)錄，零點的訂單峰值達(dá)到54.4萬筆/秒。有訂單就涉及到交易，有交易就需要數(shù)據(jù)庫的事務(wù)保證，因此阿里巴巴數(shù)據(jù)庫將在這時面臨巨大的沖擊。

現(xiàn)實往往更加嚴(yán)峻，在業(yè)務(wù)方面，一次訂單隨著業(yè)務(wù)邏輯在后端會放大為數(shù)十次的訪問;在客戶方面，大量的客戶只是瘋狂的訪問，并沒有生成訂單。因此，在雙11的零點峰值，業(yè)務(wù)實際的訪問量級是10億次/秒。

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

熱點問題

在業(yè)務(wù)層面，熱點問題很好理解，最典型的就是雙十一零點秒殺。這會導(dǎo)致數(shù)據(jù)訪問呈現(xiàn)嚴(yán)重傾斜的冪律分布。

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

直觀上可以用下圖來解釋。以蘋果新手機(jī)發(fā)售舉例。手機(jī)的庫存等信息只存在KVS的一個節(jié)點中。當(dāng)新手機(jī)發(fā)售后，大量的果粉瘋狂進(jìn)行搶購下單，業(yè)務(wù)的訪問量基本都聚集在這一個節(jié)點上。節(jié)點可能無法承載大量的熱點訪問，進(jìn)而引發(fā)系統(tǒng)崩潰，嚴(yán)重影響用戶體驗。

熱點優(yōu)化

為了保證雙十一絲般順滑的購物體驗，Tair針對熱點問題進(jìn)行了多層優(yōu)化：

• 客戶端緩存：通過預(yù)先標(biāo)記熱點，設(shè)置客戶端層面的緩存。以上圖來理解，就是將訪問在業(yè)務(wù)層面返回，直接減小了KVS系統(tǒng)的負(fù)載壓力。
• 熱點散列技術(shù)：通過將熱點數(shù)據(jù)備份到多個KVS節(jié)點上，分?jǐn)偀狳c訪問。以少量成本的資源與系統(tǒng)開銷，換取了成倍的系統(tǒng)承載力。
• RCU無鎖引擎：通過采用Read-Copy-Update的方式，實現(xiàn)內(nèi)存KV引擎的無鎖化(lock-free)訪問(參考論文[1,2])。成倍提升KVS引擎的性能，進(jìn)而提高熱點的承載力。
• HotRing：在RCU無鎖引擎基礎(chǔ)上，我們進(jìn)行索引結(jié)構(gòu)的熱點感知設(shè)計，提出了一種名為HotRing的新型熱點感知內(nèi)存KVS。HotRing可動態(tài)識別熱點，并實時的進(jìn)行索引結(jié)構(gòu)的無鎖調(diào)整，對于冪律分布場景實現(xiàn)成倍的引擎性能提升。

經(jīng)過十年的技術(shù)沉淀，我們已將集團(tuán)Tair數(shù)據(jù)庫的緩存技術(shù)釋放到云上，普惠大眾，即“阿里云Redis企業(yè)版”。

03 HotRing

現(xiàn)有技術(shù)

現(xiàn)有的內(nèi)存KVS引擎通常采用鏈?zhǔn)焦Ｗ鳛樗饕Y(jié)構(gòu)如下圖所示。首先，根據(jù)數(shù)據(jù)的鍵值(k)計算其哈希值h(k)，對應(yīng)到哈希表(Hash table)的某個頭指針(Headi)。根據(jù)頭指針遍歷相應(yīng)的沖突鏈(Collision Chain)的所有數(shù)據(jù)(Item)，通過鍵值比較，找到目標(biāo)數(shù)據(jù)。如果目標(biāo)數(shù)據(jù)不在沖突鏈中(read miss)，則可在沖突鏈頭部插入該數(shù)據(jù)。

在鏈?zhǔn)焦Ｋ饕Y(jié)構(gòu)中，訪問位于沖突鏈尾部的數(shù)據(jù)，需要經(jīng)過更多的索引跳數(shù)，即更多次的內(nèi)存訪問。很直觀的想法是，如果可以將熱點數(shù)據(jù)放置在沖突鏈頭部，那么系統(tǒng)對于熱點數(shù)據(jù)的訪問將會有更快的響應(yīng)速度。

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

設(shè)計挑戰(zhàn)

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

HotRing整體設(shè)計

HotRing在傳統(tǒng)鏈?zhǔn)焦Ｋ饕A(chǔ)上，實現(xiàn)了有序環(huán)式哈希索引設(shè)計。如下圖所示，將沖突鏈?zhǔn)孜策B接形式?jīng)_突環(huán)，保證頭指針指向任何一個item都可以遍歷環(huán)上所有數(shù)據(jù)。然后，HotRing通過lock-free移動頭指針，動態(tài)指向熱度較高的item(或根據(jù)算法計算出的最優(yōu)item位置)，使得訪問熱點數(shù)據(jù)可以更快的返回。

下面通過如下4方面進(jìn)行介紹：

• 設(shè)計1：為什么要實現(xiàn)為有序環(huán)?
• 設(shè)計2：如何動態(tài)識別熱點并調(diào)整頭指針?
• 設(shè)計3：如何保證無鎖的并發(fā)訪問?
• 設(shè)計4：如何根據(jù)熱點數(shù)據(jù)量的動態(tài)變化進(jìn)行無鎖rehash?

設(shè)計1——有序環(huán)

實現(xiàn)環(huán)式哈希索引后，第一個問題是要保證查詢的正確性。若為無序環(huán)，當(dāng)一個read miss操作遍歷沖突環(huán)時，它需要一個標(biāo)志來判斷遍歷何時終止，否則會形式死循環(huán)。但是在環(huán)上，所有數(shù)據(jù)都會動態(tài)變化(更新或刪除)，頭指針同樣也會動態(tài)移動，沒有標(biāo)志可以作為遍歷的終止判斷。

利用key排序可以解決這個問題，若目標(biāo)key介于連續(xù)兩個item的key之間，說明為read miss操作，即可終止返回。由于實際系統(tǒng)中，數(shù)據(jù)key的大小通常為10~100B，比較會帶來巨大的開銷。哈希結(jié)構(gòu)利用tag來減少key的比較開銷。

如下圖所示，tag是哈希值的一部分，每個key計算的哈希值，前k位用來哈希表的定位，后n-k位作為沖突鏈中進(jìn)一步區(qū)分key的標(biāo)志。為了減小排序開銷，我們構(gòu)建字典序：order = (tag, key)。先根據(jù)tag進(jìn)行排序，tag相同再根據(jù)key進(jìn)行排序。

下圖比較了HotRing與傳統(tǒng)鏈?zhǔn)焦！Ｒ詉temB舉例，鏈?zhǔn)焦Ｐ枰闅v所有數(shù)據(jù)才能返回read miss。而HotRing在訪問itemA與C后，即可確認(rèn)B read miss。因此針對read miss操作，鏈?zhǔn)焦Ｐ枰闅v整個沖突鏈;而HotRing利用字典序，不僅可以正確終止，且平均只需遍歷1/2沖突環(huán)。

設(shè)計2——動態(tài)識別與調(diào)整

HotRing實現(xiàn)了兩種策略來實現(xiàn)周期性的熱點識別與調(diào)整。每R次訪問為一個周期(R通常設(shè)置為5)，第R次訪問的線程將進(jìn)行頭指針的調(diào)整。兩種策略如下：

• 隨機(jī)移動策略：每R次訪問，移動頭指針指向第R次訪問的item。若已經(jīng)指向該item，則頭指針不移動。該策略的優(yōu)勢是， 不需要額外的元數(shù)據(jù)開銷，且不需要采樣過程，響應(yīng)速度極快。
• 采樣分析策略：每R次訪問，嘗試啟動對應(yīng)沖突環(huán)的采樣，統(tǒng)計item的訪問頻率。若第R次訪問的item已經(jīng)是頭指針指向的item，則不啟動采樣。

采樣所需的元數(shù)據(jù)結(jié)構(gòu)如下圖所示，分別在頭指針處設(shè)置Total Counter，記錄該環(huán)的訪問總次數(shù)，每個item設(shè)置Counter記錄該item的訪問次數(shù)。因為內(nèi)存指針需要分配64bits，但實際系統(tǒng)地址索引只使用其中的48bits。我們使用剩余16bits設(shè)置標(biāo)志位(例如Total Counter、Counter等)，保證不會增加額外的元數(shù)據(jù)開銷。該策略的優(yōu)勢是，通過采樣分析，可以計算選出最優(yōu)的頭指針位置，穩(wěn)態(tài)時性能表現(xiàn)更優(yōu)。

這一部分的細(xì)節(jié)設(shè)計有很多：

1. 采樣分析策略如何選出最優(yōu)位置;
2. 針對RCU更新操作的采樣優(yōu)化，
3. 熱點繼承防止冷啟動。

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

設(shè)計3——無鎖并發(fā)訪問

Tair的RCU無鎖引擎是HotRing的設(shè)計基礎(chǔ)。參考論文[1,2]對如何實現(xiàn)無鎖鏈表進(jìn)行了詳細(xì)講解，后續(xù)的所有無鎖設(shè)計基本都沿用了他們的策略。有興趣可以讀一下。這里我們舉一個典型的并發(fā)示例進(jìn)行介紹。

如下圖所示，在鏈A->B->D上，線程1進(jìn)行插入C的操作，同時線程2進(jìn)行RCU更新B的操作，嘗試更新為B'。線程1修改B的指針指向C，完成插入。而線程2修改A的指針指向B'完成更新。兩個線程并發(fā)修改不同的內(nèi)存，均可成功返回。但是這時遍歷整條鏈(A->B'->D)，將發(fā)現(xiàn)C無法被遍歷到，導(dǎo)致正確性問題。

解決措施是利用上圖(Item Format)中的Occupied標(biāo)志位。當(dāng)線程2更新B時，首先需要將B的Occupied標(biāo)志位置位。線程1插入C需要修改B的指針(Next Item Address)，若發(fā)現(xiàn)Occupied標(biāo)志位已置位，則需要重新遍歷鏈表，嘗試插入。通過使并發(fā)操作競爭修改同一內(nèi)存地址，保證并發(fā)操作的正確性。

利用相同原理，我們保證了頭指針移動操作，與CRUD操作的并發(fā)正確性。因此實現(xiàn)了HotRing的無鎖并發(fā)訪問。

設(shè)計4——適應(yīng)熱點數(shù)據(jù)量的無鎖rehash

如背景所述，對于極端的冪率分布場景，大量的數(shù)據(jù)訪問只集中在少部分的熱點數(shù)據(jù)中。因此只要保證熱點數(shù)據(jù)可以位于頭指針位置，沖突環(huán)即使很長，對于引擎的性能表現(xiàn)并不影響。引擎性能的降低，必然是因為沖突環(huán)上存在多個熱點。因此HotRing設(shè)計了適應(yīng)熱點數(shù)據(jù)量的無鎖rehash策略來解決這一問題。

HotRing利用訪問所需平均內(nèi)存訪問次數(shù)(access overhead)來替代傳統(tǒng)rehash策略的負(fù)載因子(load factor)。在冪率分布場景，若每個沖突環(huán)只有一個熱點，HotRing可以保證access overhead < 2，即平均每次訪問所需內(nèi)存訪問次數(shù)小于2。因此設(shè)定access overhead閾值為2，當(dāng)大于2時，觸發(fā)rehash。

rehash過程分為3步進(jìn)行，結(jié)合上面4圖進(jìn)行說明，圖一為哈希表，哈希值在rehash前后的變化。剩余三圖為rehash三個過程。

初始化(Initialization)：首先，HotRing創(chuàng)建一個后臺rehash線程。該線程創(chuàng)建2倍空間的新哈希表，通過復(fù)用tag的最高一位來進(jìn)行索引。因此，新表中將會有兩個頭指針與舊表中的一個頭指針對應(yīng)。HotRing根據(jù)tag范圍對數(shù)據(jù)進(jìn)行劃分。假設(shè)tag最大值為T，tag范圍為[0,T)，則兩個新的頭指針對應(yīng)tag范圍為[0,T/2)和[T/2,T)。同時，rahash線程創(chuàng)建一個rehash節(jié)點(包含兩個空數(shù)據(jù)的子item節(jié)點)，子item節(jié)點分別對應(yīng)兩個新頭指針。HotRing利用item中的Rehash標(biāo)志位識別rehash節(jié)點的子item節(jié)點。

分裂(Split)：在分裂階段，rehash線程通過將rehash節(jié)點的兩個子item節(jié)點插入環(huán)中完成環(huán)的分裂。如圖(Split)所示，因為itemB和E是tag的范圍邊界，所以子item節(jié)點分別插入到itemB和E之前。完成兩個插入操作后，新哈希表將激活，所有的訪問都將通過新哈希表進(jìn)行訪問。到目前為止，已經(jīng)在邏輯上將沖突環(huán)一分為二。當(dāng)我們查找數(shù)據(jù)時，最多只需要掃描一半的item。

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

04 總 結(jié)

內(nèi)存鍵值存儲系統(tǒng)由于高性能、易擴(kuò)展等特性在云存儲服務(wù)中廣泛使用。其通常作為必不可少的緩存組件，以解決持久化存儲系統(tǒng)或分布式存儲系統(tǒng)中的熱點問題。

但分析發(fā)現(xiàn)，內(nèi)存KVS內(nèi)部的熱點問題更加嚴(yán)重，其數(shù)據(jù)訪問分布同樣服從冪律分布，且訪問傾斜愈加嚴(yán)重。現(xiàn)有的內(nèi)存KVS缺乏熱點優(yōu)化意識，部分?jǐn)?shù)據(jù)節(jié)點可能無法承載大量的熱點訪問，進(jìn)而引發(fā)系統(tǒng)崩潰，嚴(yán)重影響用戶體驗。

在本論文中，我們進(jìn)行索引結(jié)構(gòu)的熱點感知設(shè)計，提出了一種名為HotRing的新型熱點感知內(nèi)存KVS，針對冪率分布的熱點場景進(jìn)行大量優(yōu)化。HotRing可動態(tài)識別熱點，并實時的進(jìn)行索引結(jié)構(gòu)的無鎖調(diào)整，進(jìn)而提供高并發(fā)高性能的無鎖化訪問。

與傳統(tǒng)的內(nèi)存KVS索引相比，HotRing采用輕量級的熱點識別策略，且沒有增加元數(shù)據(jù)存儲開銷。但在冪律分布的應(yīng)用場景中，HotRing的引擎吞吐性能可達(dá)600M ops/s，與目前最快KVS相比，可實現(xiàn)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)