[發(fā)明專(zhuān)利]基于CEPH的元素選擇方法、裝置、服務(wù)器及存儲(chǔ)介質(zhì)

有效

• 申請(qǐng)?zhí)枺?/td>: 202010992416.1
• 申請(qǐng)日: 2020-09-21
• 公開(kāi)（公告）號(hào): CN111930685B
• 公開(kāi)（公告）日: 2021-02-26
• 發(fā)明（設(shè)計(jì)）人: 胡玉晟;龔立義
• 申請(qǐng)（專(zhuān)利權(quán)）人: 柏科數(shù)據(jù)技術(shù)（深圳）股份有限公司
• 主分類(lèi)號(hào): G06F16/11
• 分類(lèi)號(hào): G06F16/11;G06F16/13;G06F16/172;G06F16/182;G06F7/58
• 代理公司: 深圳峰誠(chéng)志合知識(shí)產(chǎn)權(quán)代理有限公司 44525
• 代理人: 李明香

1.一種基于CEPH的元素選擇方法，其特征在于，包括：

計(jì)算CRUSH_HASH輸入?yún)?shù)的乘積結(jié)果，所述CRUSH_HASH輸入?yún)?shù)，包括：bucket的x、bucket的id和選擇的次數(shù)r；

將所述乘積結(jié)果作為隨機(jī)數(shù)種子，利用MT19937算法生成與所述bucket包括的item數(shù)量相對(duì)應(yīng)的32位的偽隨機(jī)數(shù)rand；

計(jì)算所述偽隨機(jī)數(shù)與其所對(duì)應(yīng)的item的權(quán)重比值的乘積，根據(jù)所述乘積結(jié)果確定選中的item；

所述計(jì)算所述偽隨機(jī)數(shù)與其所對(duì)應(yīng)的item的權(quán)重比值的乘積，采用如下方式計(jì)算：

其中，i表示item的編號(hào)，weight表示對(duì)應(yīng)item在CRUSH map中的權(quán)重，weight_sum表示所述bucket下item的總權(quán)重。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

緩存所述CRUSH_HASH輸入?yún)?shù)和與所述CRUSH_HASH輸入?yún)?shù)對(duì)應(yīng)的乘積結(jié)果。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述方法還包括：

接收CRUSH_HASH輸入?yún)?shù)，查找是否存在與所述CRUSH_HASH輸入?yún)?shù)一致的緩存條目；

在存在一致的緩存條目時(shí)，直接讀取與所述CRUSH_HASH輸入?yún)?shù)對(duì)應(yīng)的選中結(jié)果作為本次的選中結(jié)果。

4.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述方法還包括：

在所述bucket中的item被刪除時(shí)，對(duì)所述item的編號(hào)進(jìn)行保留，并對(duì)所述編號(hào)標(biāo)記為空出。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述方法還包括：

在所述bucket加入新的item時(shí)，將所述編號(hào)分配給新的item。

6.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述緩存所述CRUSH_HASH輸入?yún)?shù)和與所述CRUSH_HASH輸入?yún)?shù)對(duì)應(yīng)的乘積結(jié)果，包括：

確定所述CRUSH_HASH輸入?yún)?shù)的成績(jī)結(jié)果對(duì)應(yīng)的選中item的編號(hào)；

將所述CRUSH_HASH輸入?yún)?shù)和與所述選中item的編號(hào)，以二維數(shù)組的形式保存在連續(xù)的內(nèi)存中，所述x和r分別作為所述二維數(shù)組的下標(biāo)，所述選中的item的編號(hào)保存在下標(biāo)對(duì)應(yīng)的地址中。

7.根據(jù)權(quán)利要求6所述的方法，其特征在于，所述方法還包括：

在清空bucket的計(jì)算緩存時(shí)，將所述bucket對(duì)應(yīng)的二維數(shù)組的所有元素全部重新賦值為0xffffffff。

8.一種基于CEPH的元素選擇裝置，其特征在于，包括：

計(jì)算模塊，用于計(jì)算CRUSH_HASH輸入?yún)?shù)的乘積結(jié)果，所述CRUSH_HASH輸入?yún)?shù)，包括：bucket的x、bucket的id和選擇的次數(shù)r；

偽隨機(jī)數(shù)生成模塊，用于將所述乘積結(jié)果作為隨機(jī)數(shù)種子，利用MT19937算法生成與所述bucket包括的item數(shù)量相對(duì)應(yīng)的32位的偽隨機(jī)數(shù)rand；

選擇模塊，用于計(jì)算所述偽隨機(jī)數(shù)與其所對(duì)應(yīng)的item的權(quán)重比值的乘積，根據(jù)所述乘積結(jié)果確定選中的item；

所述選擇模塊，包括：

計(jì)算單元，所述計(jì)算單元用于計(jì)算所述偽隨機(jī)數(shù)與其所對(duì)應(yīng)的item的權(quán)重比值的乘積，采用如下方式計(jì)算：

其中，i表示item的編號(hào)，weight表示對(duì)應(yīng)item在CRUSH map中的權(quán)重，weight_sum表示所述bucket下item的總權(quán)重。

9.一種服務(wù)器，其特征在于，所述服務(wù)器包括：

一個(gè)或多個(gè)處理器；

存儲(chǔ)裝置，用于存儲(chǔ)一個(gè)或多個(gè)程序，

當(dāng)所述一個(gè)或多個(gè)程序被所述一個(gè)或多個(gè)處理器執(zhí)行，使得所述一個(gè)或多個(gè)處理器實(shí)現(xiàn)如權(quán)利要求1-7中任一所述的基于CEPH的元素選擇方法。

10.一種包含計(jì)算機(jī)可執(zhí)行指令的存儲(chǔ)介質(zhì)，所述計(jì)算機(jī)可執(zhí)行指令在由計(jì)算機(jī)處理器執(zhí)行時(shí)用于執(zhí)行如權(quán)利要求1-7任一所述的基于CEPH的元素選擇方法。