※智慧手機時代的來臨，RWD網頁設計為架站首選
網動結合了許多網際網路業界的菁英共同研發簡單易操作的架站工具，及時性的更新，為客戶創造出更多的網路商機。
本文主要解決的是基於內存的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項的收益，即計算所有項到該項的距離乘以該項的訪問頻率，求得每一項的期望值，選擇最小的期望值作為新的頭節點：
3. 使用CAS原子操作將新的頭指針指向數據項。
4. 重置頭指針和數據項的計數器。
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
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
※回頭車貨運收費標準
宇安交通關係企業，自成立迄今，即秉持著「以誠待人」、「以實處事」的企業信念
