[發(fā)明專利]一種基于熱點(diǎn)數(shù)據(jù)上流的云平臺(tái)鍵值存儲(chǔ)數(shù)據(jù)編排方法

在審

• 申請?zhí)枺?/td>: 202210812128.2
• 申請日: 2022-07-11
• 公開（公告）號(hào): CN115203203A
• 公開（公告）日: 2022-10-18
• 發(fā)明（設(shè)計(jì)）人: 吳侗雨;顧榮;羅義力;李思勉;袁春風(fēng);黃宜華
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/245;G06F3/06
• 代理公司: 蘇州威世朋知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 32235
• 代理人: 沈曉敏

1.一種基于熱點(diǎn)數(shù)據(jù)上流的云平臺(tái)鍵值存儲(chǔ)數(shù)據(jù)編排方法，包括以下步驟：

(1)自動(dòng)跟蹤一段時(shí)間內(nèi)用戶對(duì)鍵值數(shù)據(jù)的訪問，并將所述鍵值數(shù)據(jù)記錄在哈希表M中；對(duì)每一次鍵值數(shù)據(jù)訪問，更新記錄在哈希表中的訪問時(shí)刻CLOCK信息與訪問頻次FREQ信息；將訪問時(shí)刻CLOCK能表示的最大值記為MAX_CLOCK，對(duì)于不在哈希表M中的數(shù)據(jù)的訪問時(shí)刻CLOCK值初始化為MAX_CLOCK，訪問頻次FREQ初始化為1；對(duì)于重復(fù)訪問已在哈希表M中的數(shù)據(jù)，記訪問時(shí)刻CLOCK值為MAX_CLOCK，訪問頻次FREQ增加1；

(2)每個(gè)鍵值數(shù)據(jù)訪問記錄在哈希表M中對(duì)應(yīng)兩個(gè)桶，在插入訪問記錄X時(shí)，若訪問記錄X對(duì)應(yīng)的桶已被占滿，則廣度優(yōu)先搜索出有空位的桶，形成從已被占滿的桶到所述有空位的桶的路徑，在所述路徑上后向移動(dòng)各個(gè)項(xiàng)，使得訪問記錄X對(duì)應(yīng)的兩個(gè)桶位置有空位，從而得以插入訪問記錄X；

(3)定義函數(shù)AGING維護(hù)哈希表M的動(dòng)態(tài)性與實(shí)時(shí)性，所述函數(shù)AGING對(duì)部分哈希表M_p內(nèi)的訪問時(shí)刻CLOCK進(jìn)行衰減；根據(jù)時(shí)間窗口大小W設(shè)定時(shí)間間隔T，周期性觸發(fā)AGING函數(shù)；此外，在用戶每次訪問鍵值數(shù)據(jù)時(shí)，使用投機(jī)方法觸發(fā)函數(shù)AGING，直到當(dāng)訪問時(shí)刻CLOCK值為0，將對(duì)應(yīng)鍵值數(shù)據(jù)從哈希表M中移除；

(4)在一個(gè)鍵值數(shù)據(jù)的訪問時(shí)刻CLOCK與訪問頻次FREQ發(fā)生變化時(shí)，依據(jù)熱度計(jì)算公式K計(jì)算鍵值數(shù)據(jù)新的熱度HEAT；得到鍵值數(shù)據(jù)的熱度之后，更新對(duì)應(yīng)熱度計(jì)數(shù)器，得到數(shù)據(jù)整體熱度分布；

(5)根據(jù)鍵值數(shù)據(jù)整體的熱度分布和當(dāng)前訪問數(shù)據(jù)的熱度信息，能夠判斷出當(dāng)前訪問數(shù)據(jù)是否為熱數(shù)據(jù)，若是，將當(dāng)前訪問數(shù)據(jù)放入熱數(shù)據(jù)表HT中，下次對(duì)相同數(shù)據(jù)的訪問將能直接從熱數(shù)據(jù)表HT中讀取，從而完成數(shù)據(jù)預(yù)熱；

(6)熱數(shù)據(jù)表HT中的數(shù)據(jù)在一段時(shí)間沒有訪問后將逐漸下沉到磁盤中，維護(hù)熱數(shù)據(jù)表HT的動(dòng)態(tài)性與實(shí)時(shí)性。

2.根據(jù)權(quán)利要求1所述的一種基于熱點(diǎn)數(shù)據(jù)上流的云平臺(tái)鍵值存儲(chǔ)數(shù)據(jù)編排方法，其特征在于，所述步驟(1)中，哈希表M的查詢與插入方式基于布谷鳥過濾器；哈希表M管理著插入項(xiàng)的訪問時(shí)刻，訪問頻次以及指紋信息；其中，訪問時(shí)刻與訪問頻次用于計(jì)算項(xiàng)的熱度，而指紋信息則用于項(xiàng)的查詢。

3.根據(jù)權(quán)利要求1所述的一種基于熱點(diǎn)數(shù)據(jù)上流的云平臺(tái)鍵值存儲(chǔ)數(shù)據(jù)編排方法，其特征在于，所述步驟(2)中，為支持多線程并發(fā)，在進(jìn)行后向移動(dòng)時(shí)，對(duì)需要移動(dòng)的原地址與目標(biāo)地址桶加分段鎖。

4.根據(jù)權(quán)利要求1所述的一種基于熱點(diǎn)數(shù)據(jù)上流的云平臺(tái)鍵值存儲(chǔ)數(shù)據(jù)編排方法，其特征在于，所述步驟(3)中，時(shí)間窗口大小W是基于時(shí)間的窗口大小或基于計(jì)數(shù)的窗口大??；若訪問時(shí)刻CLOCK所占比特?cái)?shù)目為s，則使得AGING函數(shù)的觸發(fā)間隔T滿足T＝W/2^s；在觸發(fā)間隔T內(nèi)對(duì)所有項(xiàng)的訪問時(shí)刻CLOCK進(jìn)行衰減，這段時(shí)間中用戶的操作也將觸發(fā)部分哈希表M_p內(nèi)的函數(shù)AGING，分?jǐn)傇跁r(shí)間間隔T時(shí)間后在哈希表M上執(zhí)行函數(shù)AGING的時(shí)間開銷。

5.根據(jù)權(quán)利要求1所述的一種基于熱點(diǎn)數(shù)據(jù)上流的云平臺(tái)鍵值存儲(chǔ)數(shù)據(jù)編排方法，其特征在于，所述步驟(4)中，熱度計(jì)算公式K表示為HEAT＝FREQ^a×CLOCK^b，其中a，b分別表示用戶設(shè)置的關(guān)于頻次和時(shí)間的權(quán)重。

6.根據(jù)權(quán)利要求1所述的一種基于熱點(diǎn)數(shù)據(jù)上流的云平臺(tái)鍵值存儲(chǔ)數(shù)據(jù)編排方法，其特征在于，所述步驟(5)中，判斷一個(gè)鍵值數(shù)據(jù)是否為熱數(shù)據(jù)的依據(jù)是所述鍵值數(shù)據(jù)的熱度排名是否大于80％的鍵值數(shù)據(jù)，若所述熱度排名大于80％的鍵值數(shù)據(jù)則判斷所述鍵值數(shù)據(jù)為熱數(shù)據(jù)。