FAST'20
Jiqiang Chen, Liang Chen, Sheng Wang, Guoyun Zhu, Yuanyuan Sun, Huan Liu, and Feifei Li, Alibaba Group
背景
- 熱點問題是現(xiàn)實世界中的一個很普遍的問題
- 內(nèi)存KV Store的熱點問題沒有被重視，在阿里的生產(chǎn)環(huán)境中觀察到50%-90%的訪問，只涉及到了1%的數(shù)據(jù)，主要原因：
- 互聯(lián)網(wǎng)用戶數(shù)量增加约谈，一個熱點事件往往吸引大量用戶訪問
- 應(yīng)用底層變得更加復(fù)雜碗啄，一個小錯誤可能導(dǎo)致數(shù)據(jù)被重復(fù)訪問
- 傳統(tǒng)Hash表（最簡單的Chain Hash）的問題：沒有熱度感知
- 現(xiàn)有的對熱點數(shù)據(jù)訪問的優(yōu)化作用有限：
- CPU有cache质和，但是CPU cache大小與數(shù)據(jù)集相比實在太小
- rehash不太適合本身已經(jīng)很大的hash表
Hot-Ring
基本思想
使訪問item需要的次數(shù)與其熱度相關(guān)
主要設(shè)計
Hot-ring shift
Ordered-Ring Hash Index
HotRing將原來哈希表的沖突鏈表改成一個環(huán)狀鏈表，將最后一個元素指向第一個元素稚字，HashTable中有個head pointer指向環(huán)狀鏈表的一個元素饲宿。
這樣的結(jié)構(gòu)帶來一個問題：查找的時候怎么知道查找結(jié)束了？為了解決這個問題胆描，本文提出了Ordered-ring的方法褒傅，本質(zhì)就是對這個鏈表以tag-key(稱為一個Order)的方式進(jìn)行排序（對于一個key，計算其n位的hash值袄友，取前k位作為hash表的索引，后n-k位為tag）霹菊。排序之后的結(jié)構(gòu)如下圖：
進(jìn)行查找的時候根據(jù)tag和key的大小判斷是否結(jié)束：
以上圖作為例子剧蚣，查找B(4, 35)的時候，查到C(5, 65)不命中旋廷，而下一個元素一定比C大鸠按，所以這個時候就知道B不在表里，結(jié)束查找饶碘，其他同理目尖。
Hotspot Identification
HotRing通過head pointer指向hot元素以減少hot元素的查找開銷，接下來本文需要解決如何判斷熱點數(shù)據(jù)的問題扎运，判斷熱點需要考慮兩個因素瑟曲，分別是判斷精度以及反應(yīng)時間，針對這個問題提出了兩種熱點數(shù)據(jù)判斷的策略：1）Random Movement Strategy豪治；2）Statistical Sampling Strategy洞拨。
- Random Movement Strategy
主要思想：沒有歷史數(shù)據(jù)統(tǒng)計，每R個請求之后负拟，如果第R個請求訪問的不是當(dāng)前的熱數(shù)據(jù)（head pointer指向的元素）烦衣，則將head pointer指向當(dāng)前訪問的元素。
缺點：需要workload有很好的熱點掩浙，以及只能單一熱點花吟，不能都會造成head pointer的頻繁切換
- Statistical Sampling Strategy
主要思想：通過記錄歷史訪問信息來計算熱度
因為需要記錄歷史訪問信息，為了能夠不引入額外的空間厨姚，HotRing中利用了head pointer / next pointer的剩余空間衅澈，因為指示地址用48位就夠了，這樣還有16位剩下來谬墙，對于head pointer矾麻，HotRing將這16位分成1 bit的active位以及15位的total counter位纱耻，total counter用于記錄當(dāng)前這個bucket的訪問次數(shù)，對于next pointer险耀， HotRing將這16位分成了1 bit Rehash位弄喘，1bit Occupied位以及14 bit的counter位，Rehash和Counter分別用于并發(fā)的Rehash和update操作甩牺。
Statistical Sample：每個線程維護(hù)一個請求計數(shù)R蘑志，當(dāng)?shù)赗個請求結(jié)束的時候判斷是否觸發(fā)Sample，如果訪問的不是當(dāng)前的熱點數(shù)據(jù)則觸發(fā)贬派。然后設(shè)置Active位為1急但，這之后的每個請求都會在Total counter以及Counter中被計數(shù)。sample的次數(shù)等于bucket內(nèi)item個數(shù)搞乏。
熱點計算：最后一個訪問的線程負(fù)責(zé)根據(jù)統(tǒng)計的熱度信息波桩，計算income，這個income代表了當(dāng)某個item被選為head pointer之后訪問該ring的平均內(nèi)存訪問次數(shù)请敦，ni為第i個item的訪問次數(shù)镐躲，N為總的訪問次數(shù)，Wt為income值侍筛，計算公式如下：
RCU寫熱點的計算：RCU是指Read-Modify-Update操作萤皂，對于小于8B的value，可以通過CAS原子就地更新匣椰，但是對于超過8B的value裆熙，就需要先新建一個節(jié)點，然后替換舊的節(jié)點禽笑，這個時候就需要遍歷整個鏈表來獲取head pointer的前一個元素入录。為了減少內(nèi)存訪問，HotRing增加的是head pointer的上一個元素的counter佳镜，這樣head就是熱點數(shù)據(jù)的前一個元素纷跛，加速了熱點數(shù)據(jù)的修改。
- 熱點繼承
當(dāng)更新或者刪除head pointer的時候邀杏，需要將head pointer進(jìn)行移動贫奠。對于更新，將head point指向最新被更新的元素望蜡，因為本文認(rèn)為這樣的元素再被訪問的概率會更大唤崭；對于刪除，將head point移到下一個元素脖律。
Lock-Free concurrency
- Read：不需要額外的機(jī)制
- Insert：通過CAS修改next指針
- Update：
- 小于8B的update可以通過CAS原子修改
- Read-Modify-Update：
RCU需要創(chuàng)建新的節(jié)點谢肾，然后替換舊的節(jié)點，這種情況如果有別的線程也在進(jìn)行操作小泉，則可能出錯：
（a）中插入C同時更新B芦疏，因為C修改的是B冕杠，所以C將無法訪問；（b）中同時update B和D酸茴，D'將無法訪問分预；（c）中刪除B，D’將無法訪問薪捍。
為了解決上面的這些情況笼痹，本文通過前面指針中的Occupied位來進(jìn)行并發(fā)控制（有點像鎖），當(dāng)需要修改一個節(jié)點的時候酪穿，將這個節(jié)點的next指針中的Occupied位設(shè)置為1凳干，然后再更新這個節(jié)點，此時對需要修改當(dāng)前next指針的操作就會失敗被济，等這次操作完成之后再reset Occupied位另一個線程才能繼續(xù)操作救赐。例如（a）中更新B首先設(shè)置B的next中Occupied為1，然后原子更新A的next只磷，此時插入C的線程因為B的Occupied為1不能操作经磅，等A更新完，這個時候C的插入才能繼續(xù)喳瓣。
- Head pointer movement
對于head pointer的移動，這里分成兩種情況赞别，一是update畏陕，這就只需要Occupied新的節(jié)點；對于delete仿滔，需要Occupied當(dāng)前節(jié)點以及next節(jié)點惠毁，因為如果next節(jié)點被修改，那么head可能指向一個無效數(shù)據(jù)崎页。
Lock-Free Rehash
- 觸發(fā)條件
因為原來根據(jù)load factor觸發(fā)rehash的方式?jīng)]有考慮熱度鞠绰，所以HotRing采用的是access overhead（讀取一個item平均的內(nèi)存訪問次數(shù)）來觸發(fā)rehash
- 初始化：
創(chuàng)建一個rehash線程，并初始化一個二倍于舊空間的hash表飒焦，每一個舊表的head pointer對應(yīng)兩個新表的head pointer蜈膨。舊表采用hash值的k位作為hash地址，新表取k+1位牺荠，同時取T = 2^(n-k)作為鏈表的分界點翁巍。同時，創(chuàng)建兩個rehash item休雌，tag分別為0和2^(n-k)灶壶，設(shè)置rehash位為1，同時兩個新的head分別指向兩個rehash item
- 拆分
插入rehash item到鏈表杈曲，插入之后新表就可以active驰凛，并且不影響數(shù)據(jù)訪問
- 刪除
在確保舊表沒有訪問之后刪除舊表胸懈，然后刪除rehash node，完成rehash
唔恰响。趣钱。。因為這篇文章跟研究方向不太相關(guān)渔隶，測試部分就不詳細(xì)看了
