[發(fā)明專利]針對(duì)分布式存儲(chǔ)系統(tǒng)中的變化檢測(cè)的動(dòng)態(tài)散列函數(shù)組合

在審

• 申請(qǐng)?zhí)枺?/td>: 202080030703.2
• 申請(qǐng)日: 2020-03-30
• 公開（公告）號(hào): CN113767377A
• 公開（公告）日: 2021-12-07
• 發(fā)明（設(shè)計(jì)）人: T·克勒策;A·A·克瓦爾內(nèi)斯;O·托爾比約恩森;J-O·卡爾伯格
• 申請(qǐng)（專利權(quán)）人: 微軟技術(shù)許可有限責(zé)任公司
• 主分類號(hào): G06F16/172
• 分類號(hào): G06F16/172;G06F16/182
• 代理公司: 永新專利商標(biāo)代理有限公司 72002
• 代理人: 賈麗萍

1.一種用于針對(duì)文檔的變化檢測(cè)的動(dòng)態(tài)散列函數(shù)組合的方法，所述文檔存儲(chǔ)在具有經(jīng)由計(jì)算機(jī)網(wǎng)絡(luò)彼此互連的多個(gè)服務(wù)器的分布式存儲(chǔ)系統(tǒng)中，所述方法包括：

在所述服務(wù)器中的一個(gè)服務(wù)器處接收表示存儲(chǔ)在所述分布式存儲(chǔ)系統(tǒng)中的文檔的新版本的數(shù)據(jù)，所接收的所述文檔的新版本具有多個(gè)屬性，所述多個(gè)屬性分別具有描述或標(biāo)識(shí)所述文檔的值；以及

響應(yīng)于接收到表示所述文檔的所述新版本的所述數(shù)據(jù)，對(duì)于所述屬性中的每個(gè)屬性，

基于所述文檔的所述新版本中的所述屬性的值的數(shù)據(jù)大小或數(shù)據(jù)類型中的一項(xiàng)或多項(xiàng)來識(shí)別所述文檔的所述新版本的所述屬性的散列函數(shù)；

使用所識(shí)別的散列函數(shù)來生成所述屬性的所述值的散列值；

將所接收的新版本中的、所述文檔的所述屬性的所生成的散列值與所述分布式存儲(chǔ)系統(tǒng)中的所述文檔的先前版本中的相應(yīng)屬性的散列值進(jìn)行比較；以及

當(dāng)檢測(cè)到所生成的散列值與所述文檔的所述先前版本中的所述相應(yīng)屬性的散列值不同時(shí)，經(jīng)由所述計(jì)算機(jī)網(wǎng)絡(luò)，僅向先前注冊(cè)為接收關(guān)于所述屬性的變化的通知的一個(gè)或多個(gè)計(jì)算服務(wù)發(fā)送通知，而不向未注冊(cè)為接收所述通知的其他計(jì)算服務(wù)發(fā)送所述通知。

2.根據(jù)權(quán)利要求1所述的方法，其中，識(shí)別所述散列函數(shù)包括：

當(dāng)所述屬性的所述值是整數(shù)或者是具有比閾值字符數(shù)少的字符串時(shí)，選擇恒等函數(shù)作為所述散列函數(shù)，其中，所述恒等函數(shù)被配置為返回輸入值作為輸出。

3.根據(jù)權(quán)利要求1所述的方法，其中，識(shí)別所述散列函數(shù)包括：

當(dāng)所述屬性的所述值是整數(shù)或者是具有比閾值字符數(shù)少的字符串時(shí)，選擇恒等函數(shù)作為所述散列函數(shù)，其中，所述恒等函數(shù)被配置為返回輸入值作為輸出；并且

當(dāng)所述屬性的所述值不是整數(shù)或者不是具有比閾值字符數(shù)少的字符串時(shí)，選擇被配置為將所述數(shù)據(jù)大小的所述值的數(shù)據(jù)映射到與所述值的所述數(shù)據(jù)大小不同的固定大小的散列值的散列函數(shù)。

4.根據(jù)權(quán)利要求1所述的方法，其中，識(shí)別所述散列函數(shù)包括：

確定用于執(zhí)行所述比較的所述屬性的數(shù)量是否高于閾值；以及

響應(yīng)于確定用于執(zhí)行所述比較的所述屬性的所述數(shù)量高于所述閾值，選擇被配置為生成具有不少于閾值比特?cái)?shù)的比特?cái)?shù)的所述散列值的散列函數(shù)。

5.根據(jù)權(quán)利要求1所述的方法，其中，識(shí)別所述散列函數(shù)包括：

識(shí)別所述文檔的所述新版本的所述屬性的所述數(shù)據(jù)大小；以及

基于所述屬性的所識(shí)別的數(shù)據(jù)大小，根據(jù)包含數(shù)據(jù)大小的范圍的記錄和相應(yīng)散列函數(shù)的配置文件來確定所述散列函數(shù)。

6.根據(jù)權(quán)利要求1所述的方法，其中，識(shí)別所述散列函數(shù)包括：

通過基于所述散列值的大小、計(jì)算所述散列值的計(jì)算成本、所述散列值的沖突率中的一項(xiàng)或多項(xiàng)使成本函數(shù)最小化來選擇所述散列函數(shù)。

7.根據(jù)權(quán)利要求1所述的方法，其中，識(shí)別所述散列函數(shù)包括：

使用成本函數(shù)來選擇使處理器周期和所述散列值的存儲(chǔ)大小最小化、同時(shí)將沖突數(shù)量保持在閾值以下并使針對(duì)所執(zhí)行的比較而讀取的所述屬性的數(shù)據(jù)量最小化的散列函數(shù)。

8.根據(jù)權(quán)利要求1所述的方法，其中，識(shí)別所述散列函數(shù)包括：

使用成本函數(shù)來選擇使處理器周期和所述散列值的存儲(chǔ)大小最小化、同時(shí)將沖突數(shù)量保持在閾值以下并使針對(duì)所執(zhí)行的比較而讀取的所述屬性的數(shù)據(jù)量最小化的散列函數(shù)，如下所示：

J(_Hi)＝W_Collision*CR_Hi+W_CPU*CPU_Hi+W_Storage*Storage_Hi+W_Data*Data_Hi,

其中，CR_Hi是沖突率，CPU_Hi是處理器周期，Storage_Hi是所述散列值的存儲(chǔ)大小，Data_Hi∈{屬性大小,Storage_Hi}，并且W是與各種相應(yīng)參數(shù)相關(guān)聯(lián)的權(quán)重。