本文主要解決的是基于記憶體的K-V存儲引擎在實際應用中出現的熱點問題，設計了一個熱點可感覺的KV存儲引擎，極大的提升了KV存儲引擎對于熱點資料通路的承載能力。
Introduction
熱點問題，可以了解為在一個嚴重傾斜的工作負載下，頻繁的通路和操作某一小部分資料。
如圖，是阿裡的不同業務中資料通路分布情況，大量的資料通路隻集中在少部分的熱點資料中。在平常的情況下，百分之五十的使用者通路請求隻是針對其中百分之一的資料，在一些極端的情況下，當新産品發售後，大量的粉絲瘋狂進行搶購下單，業務的通路量基本都聚集在某一小部分資料上，會出現百分之九十的使用者請求針對其中百分之一的資料。
目前有一些方法來解決熱點資料問題：
- 使用一緻性雜湊演算法将資料分片，分布到多個節點上，分攤熱點通路。（Scale out using consistent hashing）
- 将熱點資料備份到多個節點上，分攤熱點通路。 （Replication in multi-node）
- 用戶端緩存：通過預先标記熱點，設定用戶端層面的緩存。減小鍵值存儲系統的負載壓力。（Front-end cache）
第一種和第二種方法中因為節點的添加，會使得系統的成本會大大增加。第三種方法，如果使用者請求中涉及到很多資料更新的請求，對用戶端層面的緩存的資料需要維護，這個過程實作會變得很複雜。
本篇論文則是從提升單個點對熱點資料的處理能力出發（Improve Single node’s ability to handle hotspots），設計了一種熱點可感覺的鍵值資料結構，實作在嚴重傾斜的工作負載下，快速的完成使用者的通路請求。
Prior work
現有很多基于記憶體的鍵值存儲引擎通常采用鍊式哈希作為索引，這種索引結構對熱資料是無法感應到，資料項被随機的分布在連結清單上。如果圖中item3是一個熱資料項，他處在某一連結清單的尾部，需要經過多次記憶體通路才可以将item3的資料取出來。如果高度傾斜的工作負載下，要通過多次記憶體通路才可以的得到item3，會使得系統的性能就會很低下。如果可以将熱點資料放置在沖突鍊頭部，那麼系統對于熱點資料的通路将會有更快的響應速度。
Challenges
設計一個熱點可感覺的索引結構需要解決兩個問題：
- 資料的熱度是動态變化的，必須實作動态的熱點感覺，保證熱點時效性。
- 無鎖化處理，基于記憶體的鍵值存儲引擎性能是很敏感的，要保證高性能就必須支援無鎖的并發讀/寫操作
Design of HotRing
論文提出的索引結構被稱作hotring，與傳統的哈希結構不同的是，将哈希表中的鍊式結構改成了環，哈希表中存儲的頭指針可以指向環中的任意資料項。當連結清單變成環的時候，以頭指針所指的資料項為起點，查找要通路的元素，如果元素不存在，就會一直循環查找下去，是以，作者将該還設計成一個有序環。
在變成有序環的時候，因為表示key大小所用的位元組數一般不會少（通常為10-100位元組大小），隻是簡單的對key進行排序，比較會帶來巨大的開銷。我們建構字典序：order = (tag, key)。先根據tag進行排序，tag相同再根據key進行排序：以itemB舉例，鍊式哈希需要周遊所有資料才能傳回read miss。而HotRing在通路itemA與C後，即可确認B read miss。
Hotspot Shift Identification
每段時間使用者的通路需求在不斷變化，資料的熱度是動态變化的，HotRing實作了兩種政策來實作周期性的動态識别熱點并調整頭指針指向。
- 随機移動政策
- 采樣分析政策
随機移動政策
每個線程維護一個變量，記錄執行了多少次請求，每R次通路，移動頭指針指向第R次通路的資料項。若指針已經指向該資料項，則頭指針不移動。該政策的優勢是， 不需要額外的中繼資料開銷，實作簡單，響應速度快。
缺點：
- 若R小，找到熱點的時間會很短，但是可能造成頻繁的頭指針移動。
- 若使用者的通路負載傾斜程度小，頭指針移動的頻率會變高，效率就會降低。
- 難以處理環中多個熱點資料。
采樣分析政策
使用該政策時，同樣的，在R次通路後，若第R次通路的item已經是頭指針指向的item，則不啟動采樣，否則，嘗試啟動對應沖突環的進行采樣。
在介紹采樣政策之前，先介紹一下頭指針和資料項對應的資料結構。頭指針head包括：
- active：1 bit，作為控制采樣分析的辨別。
- total_counter：15 bits，目前環總共的通路次數。
- address：48 bits，環的頭位址（x86-64上目前隻使用了48位）。
而環上每一項的next包括（因為現代作業系統所使用的記憶體位址空間使用64bit，而環中下一項的位址實際隻需要48bit即可表示，其餘的16bit來控制并發，通路次數等資訊）：
- rehash：1 bit，作為控制rehash的辨別。
- occupied：1 bit，用于并發控制，保證并發通路的正确性。
- counter：14 bits，該項的通路次數。
- address：48 bits，下一項的位址。
現在開始介紹采樣分析政策，如果第R次通路資料項并不是頭指針指向的資料項，說明熱點資料已經發生了變化，這個時候會對沖突環進行采樣。采樣的過程如下：
- 打開head.active（CAS）
- 後續的請求的通路記錄會被記錄到頭指針的total_count和對應item的的next.count（CAS)采樣個數也是R
- 采樣結束後，将頭指針的采樣标記恢複過來。
CAS（Compare And Swap）:當要操作記憶體中某一個變量的時候，會記錄下變量中的舊值，通過對舊值進行一系列的操作後得到新值，然後将舊值會與記憶體中的變量做比較，如果不相同，則說明記憶體中的值在這期間内被修改過，這時CAS操作将會失敗，新值将不會被寫入記憶體。如果相同，使記憶體中的變量變為新值。
對資料采樣結束後，利用已有的資訊可以進行判斷将哪一個資料項作為頭節點。具體過程如下：
- 周遊環，計算每一項的通路頻率。（第k項的通路次數nk，環中所有項的通路次數為N，則第k項的通路頻率為nk/N）。
- 計算每個節點的收益W，取最小的收益的資料項作為新的熱資料項。每一項的受益值的計算公式如下，假設現在求第k項的收益，即計算所有項到該項的距離乘以該項的通路頻率，求得每一項的期望值，選擇最小的期望值作為新的頭節點：
- 使用CAS原子操作将新的頭指針指向資料項。
- 重置頭指針和資料項的計數器。
Write-Intensive Hotspot with RCU
在一般情況下，對于更新操作，HotRing可以對不超過8位元組的資料進行update-in-place原子更新操作，這種情況下，讀取和更新被視作一樣的操作。但對于超過8個位元組的大資料進行更新，hotring則會使用read-copy-update協定，RCU——更新資料的時候，首先拷貝一個副本，然後對副本進行修改，最後使用一個回調（callback）機制在适當的時機把指向原來資料的指針重新指向新的被修改的資料，這個期間資料都是可以随意讀的。
當更新的資料項是頭指針指向的熱資料項時，因為要修改前一個資料項的next指針，需要周遊整個環來擷取頭節點的前一項。如圖，周遊得到熱資料的前一項需要花費大量的記憶體通路開銷。論文在這種情況下，更新的隻是前一項的計數器，其他項的計數器不變，這樣可以使得頭指針可以在後面的政策調整中直接指向熱資料的前一項，使得對熱資料的更新需要的記憶體通路操作就會減少。
Concurrent Operations
1.Read操作
Hotringd的讀取不需要任何的操作，操作完全無鎖。
2.Insert操作
當兩個線程都在B、D之間插入時，對原來結構的修改，隻涉及到B項的next項，修改B項的next項的競争沖突可以通過CAS保證線程安全。若前一項next字段發生競争，CAS會失敗，此時操作需要重試。
3.Update操作
當更新的資料不超過8位元組：使用in-place update方法去更新即可，不需要其它操作，線程安全可以通過CAS保證。當更新的資料超過8位元組：使用RCU更新，因為采用RCU方法，這時候需要分3種情況：
①RCU-update & Insert
2個線程分别更新B和插入C，兩個線程對原來結構的影響分别是修改A的next指針和修改B的next指針，即便存在CAS操作，但兩者之間不存在沖突，是以兩個操作都會成功，但結果肯定不是我們所希望的。
解決辦法：RCU-update前，嘗試CAS修改B.next值，置B.next.occupy = 1。另外一個線程的在完成插入操作時，使用CAS原子操作通路前一個節點B的next字段，發現該字段的occupy位為1，操作會失敗，重試。操作完成後，新版本項的occupy為0。
②RCU-update & RCU-update
2個線程分别更新B和更新D，兩個線程對原來結構的影響分别是修改A的next指針和修改B的next指針，即便存在CAS操作，但兩者之間不存在沖突，是以兩個操作都會成功，但結果肯定不是我們所希望的。
解決辦法：更新B的時候，建立一個新的資料項B’，使用CAS操作修改B的，置B.next.occupy = 1，當另一個線程修改D節點後，使用CAS連接配接前一個節點B的時候，發現B.next.occupy = 1，操作會失敗，重試。
③RCU-update & Delete
2個線程分别删除B和更新D，會出現和上述一樣的問題。此處不再贅述。
4.頭指針在并發下的移動操作
- 當要移動頭指針時，為了避免新的頭節點在這個過程中出現更新或者删除的情況，導緻頭指針可能指向無效的資料項，我們會通過CAS設定新的頭節點的occupy為1，保證不被被其他操作更新/删除。
- 當頭節點被更新時：更新時會設定新版本的頭節點occupy為1，使得其他操作無法對新節點造成影響。将頭指針指向新的頭節點，将新版本的occupy标記為0
- 當頭節點被删除時：除了設定目前被删除的頭節點occupy為1，還得設定下一項的occupy為1，因為下一項是新的頭節點，需要保證其不被更新/删除
Lock-free Rehash
當沖突環上存在多個熱點資料時，鍵值對存儲引擎的性能就會大大降低。是以HotRing設計了無鎖rehash政策來解決這一問題。和普通的哈希表不同的是使用負載因子來觸發rehash不同，HotRing使用通路開銷（即操作平均記憶體通路次數）來觸發rehash，文中設定平均記憶體通路次數超過2的時候，就會自動觸發。HotRing rehash分為3步：
1. 初始化 ——首先建立線程來專門處理rehash操作，初始化一個2倍大小的散清單，複用tag的最高一位來進行索引，将原先的一個環拆分成了兩個環。根據tag範圍對資料項進行劃分。假設tag最大值為T，tag範圍為[0,T)，則兩個新的頭指針對應tag範圍為[0,T/2)和[T/2,T)。然後該線程建立一個rehash node，裡面包含2個rehash child item，作為2個新環的頭，它的格式和data item一樣，但是tag值分别是0和T/2。
2. 分割——接下來需要分割原有的環到2個新的環。如圖，因為itemB和E是tag的範圍邊界，是以線程會将兩個rehash item節點分别插入到itemB和E之前。到目前為止，已經在邏輯上将沖突環一分為二。
3. 删除——最後一步，将每一個環中首尾兩部分連接配接在一起。此外，還有一些收尾工作，包括舊哈希表的回收、以及rehash節點的删除回收等。需要注意的是，在完成删除操作之前，要確定所有對舊哈希表的通路已經結束。隻有rehash線程會阻塞一段時間。
Evaluation
Experimental Setting
在一台記憶體容量為32GB的伺服器上測試的，測試的時候使用YCSB提供5種工作負載，預設情況下，使用64個線程在兩億五千萬個鍵值對測試負載B，在測試負載中，有百分之97.8的操作是針對其中百分隻1的資料，百分之99.8的操作是針對10%的資料，
Deployment
- HotRing-r (random movement strategy)
- HotRing-s (sampling statistics strategy)
Baselines
- Chaining Hash(a lock-free chain-based hash index that is modified from the hash structure in Memcached.)
- FASTER(SIGMOD 2019)
- Masstree
- Memcached
在單線程和多線程情況下，對這幾種資料結構的性能進行了測試。Hotring在大量讀操作的情況下，可以實作一個很高的性能。
下圖中，左圖表明，鍊或者環中資料項的個數即便很多，hotring也可以保持一個很好的性能。右圖表明hotring在資料通路呈現嚴重傾斜的情況下，也能保持非常好的性能。（θ是齊夫分布的參數，YCSB生成工作負載時， θ的值越高，表明測試的所使用負載的傾斜程度就越嚴重。）
在下圖中，左圖表明hotring在read miss的情況下的性能比chaining hash的性能要好。這是因為hotring中每一個桶的環是有序的，判斷元素不存在不需要周遊桶中的所有元素。右圖熱點切換時，不同的熱點選擇政策穩定下來需要的時間，hotring-r在兩秒内就可以達到一種穩定的狀态了。
在分裂前，為了保證從舊哈希表進入的通路均已經傳回，rehash的過程被阻塞一段時間，随着資料容量的不斷增長，rehash操作可以維持這個穩定的性能。如下圖所示：
參考資料：
1.Jiqiang Chen, Liang Chen, Sheng Wang, Guoyun Zhu, Yuanyuan Sun, Huan Liu, Feifei Li:HotRing: A Hotspot-Aware In-Memory Key-Value Store. FAST 2020: 239-252
2. 最快KV引擎！存儲頂會FAST’20論文揭秘Tair創新性引擎
3.Presentation Video