[發明專利]一種集合同步方法及裝置

有效

• 申請號: 202010212860.7
• 申請日: 2020-03-24
• 公開（公告）號: CN111339058B
• 公開（公告）日: 2023-05-16
• 發明（設計）人: 郭得科;羅來龍;李尚森;袁昊;高軍軍;閆晶晶
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/182
• 分類號: G06F16/182;G06F16/178;G06F16/14;G06N3/006
• 代理公司: 北京風雅頌專利代理有限公司 11403
• 代理人: 曾志鵬

本說明書一個或多個實施例提供一種集合同步方法及裝置，通過計數布谷鳥過濾器存儲元素的指紋信息和數量信息來表示集合，在計數布谷鳥過濾器中，對比兩個集合，得到僅在一個集合中存在的元素，以及在兩個集合中均存在，但是存在的數量不相同的元素。交換僅在一個集合中存在的元素，復制在兩個集合中均存在，但是存在的數量不相同的元素，從而實現集合同步。

技術領域

本說明書一個或多個實施例涉及數據處理技術領域，尤其涉及一種集合同步方法及裝置。

背景技術

集合同步是分布式系統和應用中的基礎任務，指的是找出兩個數據集合的差異元素，通過相互交換差異元素，最終實現數據同步。

現有的集合同步方法是基于緊湊型數據結構，比如bloom?filter(BF，布隆過濾器)及其變種實現的，利用bloom?filter(BF，布隆過濾器)生成集合的內容總結，在交換集合數據之后識別差異元素，再交換差異元素實現集合同步。

然而上述方法只能適用于簡單集合，簡單集合即不允許出現重復的元素的集合。如果集合中允許出現重復的元素，我們稱這種集合為多重集合。緊湊型數據結構如bloomfilter(BF，布隆過濾器)的比特向量不能記錄數量超過一的元素，因而不能有效表示多重集合中元素的數量，因此不適用于實現多重集合的同步。

發明內容

有鑒于此，本說明書一個或多個實施例的目的在于提出一種集合同步方法及裝置，以解決不能同步多重集合的問題。

基于上述目的，本說明書一個或多個實施例提供了一種集合同步方法，包括：

將本地集合插入到本地計數布谷鳥過濾器中；

接收異地終端設備發送的異地計數布谷鳥過濾器，異地計數布谷鳥過濾器中插入了異地集合；

在本地計數布谷鳥過濾器和異地計數布谷鳥過濾器中，對比本地集合和異地集合中的元素；

將僅在本地集合中存在的元素，添加到差異元素集合，添加的數量為元素在本地集合中的數量；

將在本地集合和異地集合中均存在，但是在本地集合中的數量小于在異地集合中的數量的元素，添加到相同元素集合，添加的數量為兩者數量之差；

發送差異元素集合至異地終端設備；

將相同元素集合添加到本地集合中。

優選地，將本地集合插入到本地計數布谷鳥過濾器中，包括：

利用哈希函數，生成本地集合中的元素的指紋和元素的數量信息；

將本地計數布谷鳥過濾器的槽位分為指紋區和計數區；

將指紋插入到指紋區；

將數量信息插入到計數區。

優選地，在本地計數布谷鳥過濾器和異地計數布谷鳥過濾器中，對比本地集合和異地集合中的元素；將僅在本地集合中存在的元素，添加到差異元素集合，添加的數量為元素在本地集合中的數量；將在本地集合和異地集合中均存在，但是在本地集合中的數量小于在異地集合中的數量的元素，添加到相同元素集合，添加的數量為兩者數量之差，包括：

獲取本地集合的根集；根集包括本地集合中出現的元素，但不包含重復元素；根集中的每個元素，均為被查詢元素；

在異地計數布谷鳥過濾器中，分別查詢被查詢元素所對應的指紋，以及所對應的數量信息，得到被查詢元素在異地集合中的數量；

如果被查詢元素在異地集合中的數量為零，則被查詢元素為僅在本地集合中存在的元素；