CN111538865A - Multi-party set synchronization method and device and electronic equipment - Google Patents

Abstract

The present invention provides a multi-party set synchronization method, device and electronic device, which are characterized by comprising: constructing a marker cuckoo filter data structure and defining an operation of the marker cuckoo filter; using the local elements of each synchronization participant to use all The flag cuckoo filter is respectively represented to obtain a partial set of each of the synchronization participants; the partial set is sent to the central node for aggregation to obtain a global set; the global set is sent to each of the synchronization participants make the synchronization participant traverse the global set to determine the difference element; make the synchronization participant obtain the difference element from the global set to complete the multi-party set synchronization.

Description

Multi-party set synchronization method, apparatus and electronic device

technical field

The present invention relates to the technical field of distributed systems, and in particular, to a multi-party set synchronization method, device and electronic device.

Background technique

Basic functionality in distributed and networked systems when synchronizing multi-party collection content. The existing data structures cannot meet the requirements of space efficiency, fusion and information integrity required in multi-party synchronization scenarios, and cannot optimize the synchronization transmission overhead at the global level.

SUMMARY OF THE INVENTION

In view of this, the purpose of the present invention is to propose a multi-party set synchronization method and device that can optimize the synchronization transmission overhead from a global level and meet the requirements of space efficiency, fusion and information integrity required in a multi-party synchronization scenario. and electronic equipment.

Based on the above object, the invention provides a kind of multi-party set synchronization method, it is characterized in that, comprises:

constructing a flag cuckoo filter data structure and defining the operation of the flag cuckoo filter;

The local elements of each synchronization participant are respectively represented by using the flag cuckoo filter to obtain a local set of each synchronization participant;

sending the local set to the central node for aggregation to obtain a global set;

sending the global set to each of the synchronization participants;

Let the synchronization participants traverse the global set to determine the difference element;

The synchronization participant is made to obtain the difference element from the global set to complete the multi-party set synchronization.

In some embodiments, the flag cuckoo filter data structure specifically includes:

Isomorphic sign cuckoo filter: It consists of m cells, each cell contains b storage slots, and stores up to b element fingerprints, and the element fingerprints can be stored in any one of the candidate cells; the The storage slot has two fields, including a fingerprint field for storing the fingerprint information of the element and a flag field for recording the membership information of the stored element; the fingerprint field contains f bits, and the flag field contains n bits bit, where n is the number of sets participating in synchronization; two candidate cells are provided for any element x, and the indices of the element x in the two candidate cells are: h ₁ (x)=hash(x)% m and h ₂ (x)=hash(x)⊙(hash(n _x )%m), where n _x represents the element fingerprint of the element x, and hash represents the hash function;

Heterogeneous sign cuckoo filter: the relationship between the number of cells and the capacity of each cell is: m _i =α|S _i |/bi , where m _i and _{bi represent} the number of cells and the capacity of each cell, respectively capacity, α≥1 is a constant; the indices of the element x in the two candidate cells are: h ₁ (x)=hash(η _x )%m and

In some embodiments, the operation of the flag cuckoo filtering specifically includes:

Element insertion: calculate element fingerprint by hash function, then insert described element fingerprint into two described candidate cells; When all storage slots in two described candidate cells are all occupied, redistribute;

Element query: traverse two described candidate cells, and return the flag field of the storage slot of the queried element when finding the queried element; otherwise, return an error;

Element removal:

When deleting an element from a certain set: first determine the candidate cell position of the element fingerprint of the element to be deleted, if the element fingerprint of the element to be deleted does not exist or the storage slot of the element fingerprint of the element to be deleted is stored If the i-th bit of the flag field is 0, an error is returned; otherwise, the i-th bit of the flag field of the storage slot storing the element fingerprint of the element to be deleted is inverted to 0; If all bits of the flag field of the storage slot of the element fingerprint of the element are all 0, the element fingerprint of the element to be deleted is also deleted;

When deleting a certain element from all sets: the element fingerprint of the element to be deleted is deleted and all positions of the sign field of the storage slot where the element fingerprint of the element to be deleted is placed are set to 0;

Multiple sign cuckoo filter aggregation: Given two sign cuckoo filter vectors MCF _i and MCF _j , add the membership information of common elements in these two vectors to vector MCF _i , and insert the difference elements in MCF _j into MCF _i in.

In some embodiments, the reallocation specifically includes:

When all the storage slots in the two candidate cells are occupied, randomly kick out a stored element fingerprint to obtain an empty storage slot, and then store the element fingerprint to be stored and the membership information of the element fingerprint to be stored. In the empty storage slot; the kicked element fingerprints will be reallocated into another candidate cell; it ends when no additional element fingerprints are kicked out or the number of reallocations reaches a given upper limit.

In some embodiments, the sending the partial set to the central node for aggregation specifically includes:

Select the party with the largest node degree among the synchronization participants as the central node;

Described isomorphic sign cuckoo filter: select aggregation path by minimum spanning tree algorithm, and send described partial set to central node for aggregation through described aggregation path;

The heterogeneous sign cuckoo filter: constructs an empty sign cuckoo filter, and the capacity of the empty sign cuckoo filter is determined by the number of element fingerprints of the partial set to be aggregated; Fingerprints are inserted one by one into the empty flag cuckoo filter.

In some embodiments, the step of causing the synchronization participants to traverse the global set to determine the difference element specifically includes:

The difference elements include missing elements and unique elements;

The synchronization participant traverses the global set, adds the element fingerprint of the missing element and its membership information to the missing element set, and adds the element fingerprint of the unique element and its membership information to the unique element set.

In some embodiments, when the synchronization participants join and leave dynamically:

When the synchronization participant participating in the synchronization leaves, if the left synchronization participant is not a leaf node of the minimum spanning tree in the aggregation path, the minimum spanning tree is split into multiple subtrees, and the multiple subtrees are split into multiple subtrees. Use the minimum edge between subtrees to connect to obtain a new minimum spanning tree;

When a new synchronization participant joins, select the minimum edge between the new synchronization participant and the existing synchronization participant, and add the new synchronization participant to the existing minimum generation via the minimum edge in the tree.

Based on the same inventive concept, the present invention also provides a multi-party set synchronization device, characterized in that it includes:

a data structure building module configured to construct a flag cuckoo filter data structure and define the operation of the flag cuckoo filter;

a local element representation module, configured to represent the local elements of each synchronization participant using the sign cuckoo filter, respectively, to obtain a partial set of each of the synchronization participants;

a set aggregation module, configured to send the local set to the central node for aggregation to obtain a global set;

a set sending module configured to send the global set to each of the synchronization participants;

a difference element determination module, configured to make the synchronization participants traverse the global set to determine a difference element;

The synchronization module is configured to make the synchronization participant acquire the difference element from the global set to complete the synchronization of the multi-party set.

Based on the same inventive concept, the present invention also provides an electronic device, including a memory, a processor, and a computer program stored in the memory and running on the processor, characterized in that the processor implements the program when executing the program. A method as claimed in any one of claims 1 to 7.

Based on the same inventive concept, the present invention also provides a non-transitory computer-readable storage medium, characterized in that the non-transitory computer-readable storage medium stores computer instructions, and the computer instructions are used to cause the computer to execute The method of any one of claims 1 to 7.

It can be seen from the above that the multi-party set synchronization method, device and electronic device provided by the present invention construct and use the flag cuckoo filter as the data structure of the set summary for the multi-party set synchronization scene in the distributed scenario. The tree aggregates and distributes sets, shortening the transmission path, and the selection of the central node and the transmission method of aggregation while transmission further reduces the transmission overhead and meets the requirements of space efficiency, fusion and information integrity in multi-party synchronization scenarios. requirements, which greatly saves bandwidth.

Description of drawings

In order to explain the embodiments of the present invention or the technical solutions in the prior art more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

Fig. 1 is the structure diagram of the mark cuckoo filter of one embodiment of the present invention;

2 is a schematic diagram of an aggregation and distribution process according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of a hardware structure of an electronic device according to an embodiment of the present invention.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present invention more clearly understood, the present invention will be further described in detail below in conjunction with specific embodiments and with reference to the accompanying drawings.

It should be noted that, unless otherwise defined, the technical terms or scientific terms used in the embodiments of the present invention shall have the usual meanings understood by those with ordinary skill in the art to which this disclosure belongs. As used in this disclosure, "first," "second," and similar terms do not denote any order, quantity, or importance, but are merely used to distinguish the different components. "Comprising" or "comprising" and similar words mean that the elements or things appearing before the word encompass the elements or things recited after the word and their equivalents, but do not exclude other elements or things. Words like "connected" or "connected" are not limited to physical or mechanical connections, but may include electrical connections, whether direct or indirect. "Up", "Down", "Left", "Right", etc. are only used to indicate the relative positional relationship. When the absolute position of the described object changes, the relative positional relationship may also change accordingly.

As users move computing and data to the cloud, cloud services such as Dropbox, Google Drive, and OneDrive are emerging to help users access data from different devices and perform collaborative tasks on the same data. Since multiple data copies coexist on the user device, cloud server, and edge server, when users update data from different devices, these copies must be regularly synchronized to ensure their consistency and correctness. The multi-party set synchronization problem in this distributed scenario also commonly exists in wireless sensor networks, software-defined networks, content distribution networks, blockchain transaction processes, and other scenarios.

Multi-party set synchronization can be solved by being naturally decomposed into two dimensions: 1) set representation - how to represent set elements; 2) synchronization strategy - how to let synchronizing parties interact to determine and transmit difference elements. Existing set representation methods mainly rely on linear sketch data structures, such as hash tree, Bloom filter, reversible Bloom filter, Invertible Bloom lookup table (IBLT), etc. In particular, if the set elements can be represented by an integer, set characteristic polynomials based on these integer frameworks can also be used as set sketches. Synchronization strategies are built on top of these collection representations. Typically, these sketches need to be exchanged between the parties involved in the synchronization. After mastering the set sketches of other synchronization participants, the local synchronization participants can infer the difference elements that need to be transmitted according to the obtained sketches.

However, the current sketch data structure is not capable of meeting the new requirements of multi-party set synchronization scenarios. Specifically, in the case of multi-party participation, the sketch data structure used needs to have the following characteristics: 1) Space efficient, the space used is much smaller than the original data size of the set elements; 2) Fusion, multiple sketches It can be merged into a sketch without losing any information; 3) Information integrity, the content information (such as element fingerprint) and membership information (which set or sets the element belongs to) of the set elements can be recorded in the sketch. Space efficiency and merging guarantees the transmission overhead of exchanging sketches between synchronizing participants. Information integrity ensures synchronization accuracy. However, the existing sketch data structures do not have the above three characteristics at the same time. Bloom filters and their variants are space friendly, but most of them are not fusible. IBLT is both space-friendly and fusible, but does not achieve information integrity.

Furthermore, the existing synchronization strategies do not comprehensively consider the location of the synchronization participants in the network and the distribution of data in the synchronization participants, so global optimization of the transmission overhead cannot be achieved. Therefore, these synchronization strategies often lead to unnecessary sketch exchanges or data transfers. Currently, most cloud storage services deploy replica strategies to achieve collection synchronization. They usually use a cloud server as a central node for collecting data on other user devices, that is, various other synchronization participants. Other user devices upload their updated data modules to the cloud or download their missing data modules from the cloud, that is, multi-party synchronization. Unfortunately, the transmission overhead of this synchronization strategy is highly dependent on the physical location of the synchronization participants and the distance between the synchronization participants. This strategy also wastes a lot of network bandwidth, because the synchronizing party can only get data from the cloud server, although the neighbor nodes of the synchronizing party also have the data it needs. Other possible synchronization strategies, such as exchanging sketches and transferring diff elements via all-to-all or gossip protocols, would consume more network bandwidth resources.

For this reason, the present application firstly designs the Marked Cuckoo Filter, namely the Marked Cuckoo Filter (Marked CuckooFilter, MCF) data structure to represent the multi-party set, and subsequently uses the MCF to represent the Marked Cuckoo Filter. Based on this, the present application further proposes a multi-party set synchronization strategy MCFsyn. MCFsyn aggregates and distributes the MCF generated by each party based on the minimum spanning tree between participating parties. Each participating synchronizer traverses the global MCF that records the entire union information to identify its missing and unique set elements. For missing elements, MCFsyn enables synchronization participants to choose the best element content provider, thereby minimizing transmission overhead. Experiments show that MCFsyn can outperform other methods in terms of synchronization accuracy and transmission overhead.

The present application first proposes a new variant of Cuckoo filtering, the Cuckoo filtering MCF, ie, the Cuckoo filtering, which is used to represent a multi-party set. The MCF adds an additional flag field to each storage slot to indicate the membership information of the stored elements before the synchronization is completed. For example, given three sets S ₁ , S ₂ and S ₃ , the MCF will use a three-bit flag field to represent the membership information of the stored elements before synchronization is complete. If the element exists in the set Si, the _i -th bit in the flag field will be set to 1. MCF naturally inherits the functions of standard Cuckoo filtering, including element insertion, query and deletion. In addition, MCF also supports aggregation operations between MCFs, so that MCFs from different synchronization participants can be aggregated into a single MCF. Based on the above design ideas, MCF achieves space efficiency, fusion and information integrity at the same time.

Based on the MCF data structure, this application proposes a novel multi-party set synchronization strategy MCFsyn. MCFsyn has the following five main steps: 1) Each synchronization participant represents its set element as MCF; 2) Aggregates the MCF generated by each synchronization party into a global MCF; 3) Distributes the global MCF to each synchronization party; 4) The synchronization participants traverse the global MCF to determine their missing elements; 5) The synchronization participants try to obtain their missing elements with minimal transmission overhead. Each of the above steps requires a comprehensive consideration of synchronization latency, transmission overhead, and the underlying network topology.

The purpose of the present invention is to propose a multi-party set synchronization method, device and electronic device that can optimize the synchronization transmission overhead from the global level and meet the requirements of space efficiency, fusion and information integrity required in multi-party synchronization scenarios.

The present invention will be further described below in conjunction with Fig. 1, Fig. 2 and Fig. 3, which are the structure diagram, aggregation and distribution process schematic diagram, and hardware structure schematic diagram of electronic equipment of a sign cuckoo filter according to an embodiment of the present invention, respectively. The present invention provides a multi-party set synchronization method, comprising:

S1: constructing the flag cuckoo filtering data structure and defining the operation of the flag cuckoo filtering;

The sign cuckoo filter data structure specifically includes:

Isomorphic sign cuckoo filter: It consists of m cells, each cell contains b storage slots, and stores up to b element fingerprints, and the element fingerprints can be stored in any one of the candidate cells; the The storage slot has two fields, including a fingerprint field for storing the fingerprint information of the element and a flag field for recording the membership information of the stored element; the fingerprint field contains f bits, and the flag field contains n bits bit, where n is the number of sets participating in synchronization; two candidate cells are provided for any element x, and the indices of the element x in the two candidate cells are: h ₁ (x)=hash(x)% m and h ₂ (x)=hash(x)⊙(hash(n _x )%m), where n _x represents the element fingerprint of the element x, and hash represents the hash function;

As shown in Figure 1, the MCF consists of m cells. Each cell contains b storage slots, so each cell stores at most b element fingerprints. Each storage slot has two fields, including a fingerprint field for storing element fingerprint information and a flag field for recording membership information of stored elements. The fingerprint field contains f bits; while the flag field has n bits, where n is the number of sets participating in synchronization. If the element exists in the set Si, the _i -th bit in the flag field will be set to 1. The MCF provides two candidate cells for any element x whose indices are: _h1 (x)=hash(x)%m and h2 ₍ x)=hash(x)⊙(hash( _nx )%m). The element fingerprint _ηx can be stored in any of the cells. If all the storage slots in the two candidate cells are occupied, MCF will randomly kick out a stored element fingerprint, and store _nx and its membership information in this storage slot. The kicked element fingerprint will be reassigned to another of its candidate cells. The above reallocation process will end when no additional element fingerprints are kicked out (elements indicate success) or when the number of reallocations reaches a given upper limit max (elements indicate failure).

Heterogeneous sign cuckoo filter: the relationship between the number of cells and the capacity of each cell is: m _i =α|S _i |/bi , where m _i and _{bi represent} the number of cells and the capacity of each cell, respectively capacity, α≥1 is a constant; the indices of the element x in the two candidate cells are: h ₁ (x)=hash(η _x )%m and

In practice, the size of the set on the synchronization participants varies widely. For example, a participant that has been offline for a long time may have far fewer elements than other synchronizing parties, while a synchronizing party that is updated suddenly may contain more elements. In this case, representing different sets with isomorphic MCFs is not an economical choice. Therefore, this section considers the MCFsyn design when using heterogeneous MCFs. In this way, each synchronization participant can customize the MCF capacity it uses according to its local aggregate size.

如此一来，当将来自于两个不同MCF中的元素 指纹插入到其聚合结果的MCF中时，其候选单元格仅由元素指纹决定。对 于参与方P_i，其使用的MCF长度计算为：m_i＝α|S_i|/b_i，其中m_i和b_i分别表 示MCF_i的单元格数量以及每个单元格的容量，而α≥1是一个常数。Different from homogeneous MCF, heterogeneous MCF has different number of cells, so the candidate cells of elements in it are not the same. This feature invalidates the aggregation operation. To this end, the MCF data structure needs to be redesigned so that the candidate cells of an element are determined only by the element fingerprint. The specific improvement is that, given an element x and its fingerprint η _x , the corresponding two candidate cells are: h ₁ (x)=hash(η _x )%m and

In this way, when element fingerprints from two different MCFs are inserted into the MCF of its aggregated result, its candidate cells are determined only by the element fingerprints. For the participant P _i , the length of MCF used is calculated as: m _i =α|S _i |/bi , where m _i and _{bi represent the number of cells of MCF i and} the capacity of each cell, respectively, and α ≥1 is a constant.

In addition to element fingerprints, multi-party set representation also requires the recording of element membership information. To this end, the MCF introduces extra bits in each memory slot and is used to record this information. Based on the above design, MCF supports element-oriented collection representation operations, including element insertion, query and deletion. In addition, MCF also enables aggregation operations between MCF vectors. Under the design of fingerprint domain and logo domain, MCF naturally supports multi-party set representation. Therefore, MCF will be used in this application as the basic data structure supporting the multi-party synchronization strategy.

Element insertion: calculate the element fingerprint through a hash function, and then insert the element fingerprint into the two candidate cells; reassign when all the storage slots in the two candidate cells are occupied; specifically The process includes:

When inserting element x in set Si, _MCF first calculates its f-bit element fingerprint η _x through a hash function. Subsequently, the candidate cells corresponding to x are calculated by the functions h ₁ (x) and h ₂ (x). The reassignment specifically includes: when all the storage slots in the two candidate cells are occupied, randomly kicking out a stored element fingerprint to obtain an empty storage slot, and then combining the element fingerprint to be stored with the to-be-stored element fingerprint. Membership information storing element fingerprints is stored in the empty storage slot; kicked element fingerprints will be reassigned to another candidate cell; when no additional element fingerprints are kicked out or the number of reassignments reaches a given upper limit At the end, the specific process includes: if there is an unoccupied storage slot, _nx will be placed in the storage slot. The i-th bit in the flag field of the storage slot will be set to 1. Otherwise, the MCF must kick out the element fingerprint stored in one of these two candidate cells to make room for _nx . The kicked element fingerprint and its membership information will be reassigned to another of its candidate cells. The above reallocation process will end when no additional element fingerprints are kicked out or the number of reallocations reaches the given upper limit max. When the element fingerprint is kicked out of the storage slot, the 1 in the flag field of the slot will also be inverted to 0. Correspondingly, when the element fingerprint is reinserted, the corresponding bit of the flag field of the storage slot where it is located will be set to 1. In this way, the correctness of the element information in the whole re-insertion process is guaranteed.

Element query: traverse the two candidate cells, and return the flag field of the storage slot of the queried element when the queried element is found; otherwise, return an error; the specific process includes:

其中f和b分别为元素指纹长度和每个单元格中存储槽数量。When querying for element x, MCF only needs to check two candidate cells for element x. If the element fingerprint _nx can be found in either of these two cells, the MCF returns the flag field of its storage slot to explicitly give the membership information of element x. Otherwise, MCF returns False, meaning that element x is not an element in any set. The time complexity of element query is also constant, because only two cells will be traversed. The false positive and false positive probability of MCF membership query is

where f and b are the element fingerprint length and the number of storage slots in each cell, respectively.

Element deletion: When deleting an element from a certain set: first determine the candidate cell position of the element fingerprint of the element to be deleted, if the element fingerprint of the element to be deleted does not exist or the element fingerprint of the element to be deleted is stored. If the i-th bit of the flag field of the storage slot is 0, an error is returned; otherwise, the i-th bit of the flag field of the flag field of the storage slot of the element fingerprint of the element to be deleted is inverted to 0; All bits of the flag field of the storage slot of the element fingerprint of the element to be deleted are all 0, then the element fingerprint of the element to be deleted is also deleted; when deleting a certain element from all sets: the element of the element to be deleted is deleted. The fingerprint is deleted and all the bits of the flag field of the storage slot where the element fingerprint of the element to be deleted is located are set to 0; the specific process includes:

Delete operations are critical when representing dynamic collections. _MCF supports deleting element x from a certain set Si, and also supports deleting x from all sets at the same time. Specifically, in order to delete element x of Si in the set, MCF first determines the candidate cell positions of element fingerprint _nx . If _nx does not exist in its candidate cell or the _i -th bit of the flag field of the storage slot storing the fingerprint of the element is 0, the MCF returns False, indicating that the element does not exist in the set Si. Otherwise, the i-th bit of the flag field of the storage slot storing the fingerprint of this element will be inverted to 0. After this, if all bits in the flag field of the storage slot are 0, the element fingerprint is also deleted. It is simpler and more straightforward to remove element x from all sets. MCF only needs to try to delete _nx and set all bits in the flag field of the storage slot where it is located to 0. It can be seen that the time complexity of the element deletion operation is constant.

Table 1 Algorithm 1

Multiple sign cuckoo filter aggregation: Given two sign cuckoo filter vectors MCF _i and MCF _j , add the membership information of common elements in these two vectors to vector MCF _i , and insert the difference elements in MCF _j into MCF _i ; the specific process includes:

Aggregation operation means fusing element fingerprint information and its server membership information from multiple homogeneous MCFs into one MCF. This operation is of great significance for reducing the overhead of ensemble synchronization transmission. As shown in Algorithm 1, given two MCF vectors MCF _i and MCF _j , the basic idea of the aggregation operation is to add the membership information of the common elements in these two vectors to the vector MCF _i , while the difference elements in MCF _j are is inserted into MCF _i . Specifically, the algorithm traverses the entire MCF _j vector. For an arbitrarily stored element fingerprint MCF _j [k][r].fingerprint (0≤k≤m-1 and 0≤r≤b-1), MCF tries to find the element fingerprint in MCF _i . If the element fingerprint can be found in MCF _i , the mark field of its corresponding storage slot (referred to as slot) will be recalculated as the OR operation result of the mark field and MCF _j [k][r].mark (algorithm 1, lines 4 to 6). Otherwise, MCF _j [k][r].fingerprint will be inserted into MCF _i . Finally, the updated MCF _i will be returned as the aggregated result. The time complexity of this algorithm is O(mb).

Based on the above synchronization framework, there are still two challenges that need to be solved urgently. First, the paths for aggregating and distributing MCFs have a significant impact on the total transmission overhead. Gossiping or broadcasting these sketches can also do the trick, but incurs a lot of latency and transmission overhead. Therefore, it is necessary to comprehensively consider the underlying network and plan the transmission path reasonably. Second, missing elements may exist in multiple synchronization parties. How to choose the optimal missing element sender is also very challenging. In order to solve the above two problems, this application first gives the synchronization group abstraction before introducing the specific solution.

Consider n simultaneous participants, denoted as P ₁ ,...,P _n , with a local set on each participant. As shown in FIG. 2 , the present application abstracts the synchronization group into a complete graph. Each edge in the graph has a weight value, which is used to represent the number of physical network hops between the pair of nodes. For example, the weight w _i,j represents the number of hops between the parties P _i and P _j . In the aggregation step, the sketches obtained by all participants will be sent to the central node. Based on the above definitions, the specific design details of the multi-party set synchronization MCFsyn are as follows:

S2: The local elements of each synchronization participant are respectively represented by the sign cuckoo filter, and the local set of each synchronization participant is obtained:

Each synchronization participant represents its local element with an MCF as the sketch of its collection. MCFs used by different parties can choose homogeneous MCF or heterogeneous MCF according to specific needs. Homogeneous MCF has the same parameter configuration, including MCF length m, hash function for generating element fingerprints and calculating candidate cells, and each cell capacity b, which greatly simplifies subsequent aggregation and extraction steps; heterogeneous MCF reduces The storage overhead and aggregate distribution overhead are reduced, and bandwidth waste is reduced.

S3: Send the local set to the central node for aggregation to obtain a global set:

Sending the partial set to the central node for aggregation specifically includes: selecting the party with the largest node degree among the synchronization participants as the central node; the isomorphic sign cuckoo filtering: selecting an aggregation path through a minimum spanning tree algorithm, The local set is sent to the central node for aggregation through the aggregation path; the heterogeneous flag cuckoo filter: constructs an empty flag cuckoo filter, and the capacity of the empty flag cuckoo filter is determined by the elements of the local set to be aggregated. The number of fingerprints is determined; the element fingerprints in the partial set to be aggregated are inserted into the empty sign cuckoo filter one by one.

Specifically include:

All synchronization participants send their sketches to the central node for aggregation, resulting in a union global sketch. For the purpose of privacy protection, the data to be synchronized can only be transmitted between the parties participating in the synchronization. Therefore, the selected central node must also be one of the parties involved in the synchronization.

After constructing the synchronization group topology, MCFsyn calculates the Minimum Spanning Tree (MST) in the graph as the path of sketch aggregation. One of the synchronization participants is elected as the central node, which is responsible for collecting and aggregating MCFs from other synchronization parties. It is worth noting that the selection of the central node has no effect on the transmission overhead of the entire aggregation process. However, MCFsyn prefers to select the party with the largest node degree in MST as the central node. In this way, the participants from the leaf nodes of the minimum generation tree can transmit their MCFs to the central node in parallel. As in Figure 2, participant _P3 is selected as the central node. Thus, parties P2 and _P5 can simultaneously transmit their _MCFs to _P3 along the MST. The intermediate node between the leaf node and the central node aggregates the MCF from its child nodes with its local MCF, and sends the aggregated result to its parent node. For example, in FIG. 2 , after receiving the MCF ₅ from P ₅ , the participant P ₁ aggregates the received MCF ₅ with the local MCF ₁ , and sends the aggregation result to its parent node P ₃ . This transmission strategy of aggregation while transmission can significantly reduce the transmission overhead of aggregation.

In the heterogeneous sign cuckoo filter, given MCF _i and MCF _j , an empty MCF, denoted as MCF _o , will be enabled, and its capacity can be calculated as: m _o b _o =α|S _i ∪S _j |. The value of |S _i ∪S _j | can be determined by the number of element fingerprints stored in MCF _i and MCF _j . Then, the element fingerprints in MCF _i and MCF _j will be inserted into MCF _o one by one. Therefore, the time complexity of the aggregation operation increases from O(mb) for isomorphic MCF to O(m _i b _i +m _j b _j ).

When the sync participants join and leave dynamically:

When the synchronization participant participating in the synchronization leaves, if the left synchronization participant is not a leaf node of the minimum spanning tree in the aggregation path, the minimum spanning tree is split into multiple subtrees, and the multiple subtrees are split into multiple subtrees. Use the minimum edge between subtrees to connect to obtain a new minimum spanning tree;

When a new synchronization participant joins, select the minimum edge between the new synchronization participant and the existing synchronization participant, and add the new synchronization participant to the existing minimum generation via the minimum edge in the tree.

Specifically include:

In the synchronization group topology, if the constructed MST, that is, the leaf node of the minimum spanning tree, leaves the synchronization group, it will not affect the remaining part of the MST, and only need to ignore or delete the corresponding bits of the flag field in the MCF. However, when the non-leaf nodes in the MST leave the synchronization group, the MST will be split into multiple subtrees. In this case, MCFsyn needs to rebuild a new MST. This problem can be solved by the following cut-set properties and inferences.

Theorem 1 (cutset property of minimum spanning tree): Let G(V,E) denote a graph, (X,V-X) denote a cutset of graph G, and edge e is the least expensive among all edges connecting the cutset edge, then every minimum spanning tree of graph G contains edge e.

是图G的一个联通子图，其中

是T的一个子树，并且覆盖子图

中所有的节点，则

是图

的一棵最小生成树。Corollary 1: Let G(V,E) denote a graph, T denote a minimum spanning tree of graph G, and the graph

is a connected subgraph of graph G, where

is a subtree of T and covers the subgraph

all nodes in , then

is a picture

a minimum spanning tree of .

及最小生成树T，则根据定理1，可以得到：

其中

是T中覆盖子图

节点的子树，而e则是连接

和

的边中 的最小代价边。如果

不是子图

的最小生成树，则它可以被拥有更小代价的 最小生成树代替，从而使得图G拥有比T代价更小的生成树。这便与T是图 G的最小生成树矛盾，从而证明了推论1的正确性。Proof: Consider Cut Sets

and the minimum spanning tree T, then according to Theorem 1, we can get:

in

is the covering subgraph in T

subtree of nodes, and e is the connection

and

The least-cost edge among the edges. if

not a subgraph

, then it can be replaced by a minimum spanning tree with a smaller cost, so that the graph G has a spanning tree with a lower cost than T. This contradicts that T is the minimum spanning tree of graph G, thus proving the correctness of Inference 1.

Corollary 2: Let the complete graph G(V, E) represent the synchronization group topology, and its minimum spanning tree is T. When the synchronization participant _Pi leaves the synchronization group, T may be split into multiple subtrees. By connecting these subtrees one by one using the minimum edge connection among their subtrees without generating a cycle, the minimum spanning tree of the synchronization group without _Pi can be obtained.

Corollary 2 is a natural consequence of Theorem 1 and Corollary 1, and will not be proved here. Based on this inference, MCFsyn obtains a new minimum spanning tree by connecting these subtrees using the minimum edges between subtrees. Of course, when adding these edges, it is not allowed to introduce cycles into the minimum spanning tree.

When a new synchronization participant joins the synchronization group, the required operation is quite simple. When P _n+1 joins the synchronization group, in order to maintain the minimum spanning tree, MCFsyn only needs to select the minimum edge between P _n+1 and the existing synchronization party, and add it to the existing minimum spanning tree. In addition, an extra bit needs to be introduced into the MCF data structure to represent the element membership information of the set Sn ₊₁ on the synchronization party.

S4: Send the global set to each of the synchronization participants:

The central node distributes the aggregated global sketch to each synchronization party. In this way, each synchronization easily knows the information of the elements of the union.

The central node aggregates the MCF sent by its child nodes into a global MCF as a sketch of the union of sets. The global MCF, denoted as MCF _o , represents the fingerprint information and membership information of the elements in the entire union. As shown in Figure 2, MCFsyn distributes MCF _o from the central node to each synchronization participant through MST.

S5: Let the synchronization participants traverse the global set to determine the difference elements:

The difference elements include missing elements and unique elements; the synchronization participant traverses the global set, and adds the element fingerprint of the missing element and its membership information to the missing element set, and the element fingerprint of the unique element and their affiliation information are added to the set of unique elements.

Specifically include:

中(算法2中第6到第7行)。另外，如果只有第i个比特位的值为1，则该 元素只存在于集合S_i，并将被加入到集合

中(算法2中第8到第9行)。 抽取操作的时间复杂度为O(mb)，因为MCF_o中所有存储槽都需要被遍历。After receiving MCF _o , each participant attempts to determine its missing and unique elements by traversing MCF _o . For example, Algorithm 2 gives the process of extracting the participant _Pi . For the element fingerprint stored in any storage slot, if the value of the i-th bit in the flag field of the storage slot is 0, it means that the element does not belong to the set S _i . Therefore, the element fingerprint and its membership information will be added to the collection

in (lines 6 to 7 in Algorithm 2). Also, if only the _i -th bit has a value of 1, the element exists only in the set Si and will be added to the set

in (Lines 8 to 9 in Algorithm 2). The time complexity of the extraction operation is O(mb), because all the storage slots in the MCF _o need to be traversed.

Table 2 Algorithm 2

S6: Make the synchronization participant obtain the difference element from the global set to complete the synchronization of the multi-party set:

中的独有元素将会被其推送给其他参与方。采用 广播的方式推送这些元素能节约时间，而沿着MST进行传输则能节约传输 开销。对于

中的缺失元素，如果其对应标志域中仅有一个比特位为1，则 该元素为该比特位对应参与方的独有元素。此时，P_i只需要等着接收来自元 素宿主的元素内容即可。相反，如果标志域中存在多个比特位为1，P_i将选 择那个与其在同步组拓扑中构成最小边权值的参与方作为该元素的内容发 送方完成同步。此种策略可以通过在每个同步参与方上维持一个偏好列表实现。在该列表中，边权值越低的邻居节点将具有更高的优先级，这样就选择 出了最优元素内容发送方。For a party P _i , its

The unique elements in will be pushed to other parties by it. Pushing these elements by broadcasting saves time, and transmitting along the MST saves transmission overhead. for

For the missing element in , if only one bit in the corresponding flag field is 1, the element is the unique element of the party corresponding to the bit. At this point, _Pi just needs to wait to receive the element content from the element host. On the contrary, if there are multiple bits in the flag field that are 1, _Pi will select the party with the smallest edge weight in the synchronization group topology as the content sender of the element to complete the synchronization. Such a strategy can be implemented by maintaining a preference list on each synchronization participant. In this list, neighbor nodes with lower edge weights will have higher priority, thus selecting the optimal sender of element content.

Based on the same inventive concept, the present invention also provides a multi-party set synchronization device, including:

a data structure building module configured to construct a flag cuckoo filter data structure and define the operation of the flag cuckoo filter;

a local element representation module, configured to represent the local elements of each synchronization participant using the sign cuckoo filter, respectively, to obtain a partial set of each of the synchronization participants;

a set aggregation module, configured to send the local set to the central node for aggregation to obtain a global set;

a set sending module configured to send the global set to each of the synchronization participants;

a difference element determination module, configured to make the synchronization participants traverse the global set to determine a difference element;

The synchronization module is configured to make the synchronization participant acquire the difference element from the global set to complete the synchronization of the multi-party set.

The apparatuses in the foregoing embodiments are used to implement the corresponding methods in the foregoing embodiments, and have the beneficial effects of the corresponding method embodiments, which will not be repeated here.

Based on the same inventive concept, the present invention also provides an electronic device, including a memory, a processor, and a computer program stored in the memory and running on the processor, characterized in that the processor implements the program when executing the program. The method as described in the above embodiment.

Based on the same inventive concept, the present invention also provides a non-transitory computer-readable storage medium, characterized in that the non-transitory computer-readable storage medium stores computer instructions, and the computer instructions are used to cause the computer to execute The method as described in the above embodiment.

It should be noted that, the method in this embodiment of the present invention may be executed by a single device, such as a computer or a server. The method in this embodiment can also be applied to a distributed scenario, and is completed by the cooperation of multiple devices. In the case of such a distributed scenario, one device among the multiple devices may only perform one or more steps in the method of the embodiment of the present invention, and the multiple devices will interact with each other to complete all the steps. method described.

The foregoing describes specific embodiments of the present specification. Other embodiments are within the scope of the appended claims. In some cases, the actions or steps recited in the claims can be performed in a different order than in the embodiments and still achieve desirable results. Additionally, the processes depicted in the figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some embodiments, multitasking and parallel processing are also possible or may be advantageous.

FIG. 3 shows a more specific schematic diagram of the hardware structure of an electronic device provided in this embodiment. The device may include: a processor 1010 , a memory 1020 , an input/output interface 1030 , a communication interface 1040 and a bus 1050 . The processor 1010, the memory 1020, the input/output interface 1030 and the communication interface 1040 realize the communication connection between each other within the device through the bus 1050.

The processor 1010 may be implemented by a general-purpose CPU (Central Processing Unit, central processing unit), a microprocessor, an application specific integrated circuit (Application Specific Integrated Circuit, ASIC), or one or more integrated circuits, and is used to execute related program to implement the technical solutions provided by the embodiments of this specification.

The memory 1020 may be implemented in the form of a ROM (Read Only Memory, read only memory), a RAM (Random Access Memory, random access memory), a static storage device, a dynamic storage device, and the like. The memory 1020 can store the operating system and other application programs. When implementing the technical solutions provided by the embodiments of this specification through software or firmware, the relevant program codes are stored in the memory 1020 and invoked by the processor 1010 for execution.

The input/output interface 1030 is used to connect the input/output module to realize information input and output. The input/output/module can be configured in the device as a component (not shown in the figure), or can be externally connected to the device to provide corresponding functions. The input device may include a keyboard, a mouse, a touch screen, a microphone, various types of sensors, etc., and the output device may include a display, a speaker, a vibrator, an indicator light, and the like.

The communication interface 1040 is used to connect a communication module (not shown in the figure), so as to realize the communication interaction between the device and other devices. Wherein, the communication module can realize communication through wired means (such as USB, network cable, etc.), or can realize communication through wireless means (such as mobile network, WIFI, Bluetooth, etc.).

Bus 1050 includes a path to transfer information between the various components of the device (eg, processor 1010, memory 1020, input/output interface 1030, and communication interface 1040).

It should be noted that although the above-mentioned device only shows the processor 1010, the memory 1020, the input/output interface 1030, the communication interface 1040 and the bus 1050, in the specific implementation process, the device may also include necessary components for normal operation. other components. In addition, those skilled in the art can understand that, the above-mentioned device may also include only the components necessary to realize the solutions of the embodiments of the present specification, and need not include all the components shown in the figures.

The computer readable medium of this embodiment includes both persistent and non-permanent, removable and non-removable media, and information storage can be implemented by any method or technology. Information may be computer readable instructions, data structures, modules of programs, or other data. Examples of computer storage media include, but are not limited to, phase-change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read Only Memory (EEPROM), Flash Memory or other memory technology, Compact Disc Read Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, Magnetic tape cartridges, magnetic tape magnetic disk storage or other magnetic storage devices or any other non-transmission medium that can be used to store information that can be accessed by a computing device.

Those of ordinary skill in the art should understand that the discussion of any of the above embodiments is only exemplary, and is not intended to imply that the scope of the present disclosure (including the claims) is limited to these examples; under the spirit of the present invention, the above embodiments or There may also be combinations between technical features in different embodiments, steps may be carried out in any order, and there are many other variations of the different aspects of the invention as described above, which are not provided in detail for the sake of brevity.

Additionally, well known power/ground connections to integrated circuit (IC) chips and other components may or may not be shown in the figures provided in order to simplify illustration and discussion, and in order not to obscure the present invention. . Furthermore, devices may be shown in block diagram form in order to avoid obscuring the present invention, and this also takes into account the fact that the details regarding the implementation of these block diagram devices are highly dependent on the platform on which the invention will be implemented (i.e. , these details should be fully within the understanding of those skilled in the art). Where specific details (eg, circuits) are set forth to describe exemplary embodiments of the invention, it will be apparent to those skilled in the art that these specific details may be used without or with changes The present invention is carried out below. Accordingly, these descriptions are to be regarded in an illustrative rather than a restrictive sense.

Although the present invention has been described in conjunction with specific embodiments thereof, many alternatives, modifications and variations to these embodiments will be apparent to those of ordinary skill in the art from the foregoing description. For example, other memory architectures, such as dynamic RAM (DRAM), may use the discussed embodiments.

Embodiments of the present invention are intended to cover all such alternatives, modifications and variations that fall within the broad scope of the appended claims. Therefore, any omission, modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention should be included within the protection scope of the present invention.

Claims (10)

1. A multi-party aggregation synchronization method, comprising:

constructing a mark cuckoo filtering data structure and defining the operation of the mark cuckoo filtering;

respectively representing the local elements of each synchronous participant by using the mark cuckoo filtering to obtain a local set of each synchronous participant;

sending the local set to a central node for aggregation to obtain a global set;

sending the global set to each of the synchronization participants;

enabling the synchronous participants to traverse the global set to determine difference elements;

and enabling the synchronous participants to acquire the difference elements from the global set to complete multi-party set synchronization.

2. The multi-party aggregation synchronization method according to claim 1, wherein the flag cuckoo filtering data structure specifically comprises:

filtering the isomorphic marker cuckoo: the unit cell comprises m unit cells, each unit cell comprises b storage grooves, and at most b element fingerprints are stored, and the element fingerprints can be stored in any one candidate unit cell; the storage slot has two fields including a fingerprint field for storing the element fingerprint information and a field for recording the element fingerprint informationA flag domain storing membership information of the element; the fingerprint field comprises f bits, and the mark field comprises n bits, wherein n is the number of sets participating in synchronization; providing two candidate cells for any element x, wherein indexes of the element x in the two candidate cells are respectively as follows: h is₁(x) Hash (x)% m and h₂(x)＝hash(x)⊙(hash(η_x) % m), wherein η_xAn element fingerprint representing an element x, and a hash representing a hash function;

heterogeneous marker cuckoo filtering: the relationship between the number of cells and the capacity of each cell is specifically as follows: m is_i＝α|S_i|/b_iWherein m is_iAnd b_iRespectively representing the number of cells and the capacity of each cell, α is a constant, and the index of the element x in the two candidate cells is h₁(x)＝hash(η_x) % m and

3. the multi-party aggregation synchronization method according to claim 2, wherein the operation of flag cuckoo filtering specifically comprises:

element insertion: calculating an element fingerprint through a hash function, and then inserting the element fingerprint into the two candidate cells; reallocating when all slots in both of the candidate cells are occupied;

element query: traversing the two candidate cells, and returning the mark domain of the storage slot of the queried element when the queried element is found; otherwise, returning an error;

element deletion:

when an element is deleted from a collection: firstly, determining the candidate cell position of the element fingerprint of an element to be deleted, and returning an error if the element fingerprint of the element to be deleted does not exist or the ith bit of a mark field of a storage groove for storing the element fingerprint of the element to be deleted is 0; otherwise, the ith bit of the mark field of the storage slot for storing the element fingerprint of the element to be deleted is inverted to 0; if all bits of the flag field of the storage slot for storing the element fingerprint of the element to be deleted are 0, deleting the element fingerprint of the element to be deleted;

when an element is deleted from all sets: deleting the element fingerprints of the elements to be deleted and setting all the positions of the mark fields of the storage slots where the element fingerprints of the elements to be deleted are located as 0;

filtering and aggregating a plurality of mark cuckoos: given two flag cuckoo filter vectors MCF_iAnd MCF_jAdding membership information of common elements in the two vectors to the MCF vector_iIn, MCF_jThe difference element in (3) is inserted into the MCF_iIn (1).

4. The multi-party aggregation synchronization method according to claim 3, wherein the reallocating specifically comprises:

when all storage grooves in the two candidate cells are occupied, randomly kicking out a stored element fingerprint to obtain an empty storage groove, and then storing the element fingerprint to be stored and the membership information of the element fingerprint to be stored in the empty storage groove; the kicked-out element fingerprint will be reassigned to another candidate cell; ending when no additional element fingerprints are kicked out or the number of reassignments reaches a given upper limit.

5. The multi-party aggregation synchronization method according to claim 4, wherein the sending the local aggregation to a central node for aggregation specifically comprises:

selecting one of the synchronous participants with the maximum node degree as a central node;

filtering the isomorphic marker cuckoo: selecting an aggregation path through a minimum spanning tree algorithm, and sending the local set to a central node through the aggregation path for aggregation;

the heterogeneous marker cuckoo filtering: constructing an empty-mark cuckoo filter, wherein the capacity of the empty-mark cuckoo filter is determined by the number of element fingerprints of a local set to be aggregated; and inserting the element fingerprints in the local set to be aggregated into the empty marker cuckoo filtering one by one.

6. The multi-party collection synchronization method of claim 5, wherein the traversing the global collection by the synchronization participants to determine the difference element specifically comprises:

the difference elements comprise missing elements and unique elements;

and the synchronous participants traverse the global set, add the element fingerprints and the membership information of the missing elements into the missing element set, and add the element fingerprints and the membership information of the unique elements into the unique element set.

7. The multi-party aggregation synchronization method of claim 6, wherein, when the synchronization participants join and leave dynamically:

when a synchronous participant participating in synchronization leaves, if the synchronous participant leaves and is not a leaf node of the minimum spanning tree in an aggregation path, splitting the minimum spanning tree into a plurality of subtrees, and connecting the subtrees by using minimum edges among the subtrees to obtain a new minimum spanning tree;

when a new synchronous participant joins, selecting a minimum edge between the new synchronous participant and an existing synchronous participant, and joining the new synchronous participant into an existing minimum spanning tree through the minimum edge.

8. A multi-party aggregation synchronization apparatus, comprising:

a data structure construction module configured to construct a signature cuckoo filtering data structure and define operations of the signature cuckoo filtering;

a local element representation module configured to represent the local element of each synchronization participant by using the marker cuckoo filtering, so as to obtain a local set of each synchronization participant;

the set aggregation module is configured to send the local set to a central node for aggregation to obtain a global set;

a set sending module configured to send the global set to each of the synchronization participants;

a difference element determination module configured to cause the synchronization participant to traverse the global set, determining a difference element;

and the synchronization module is configured to enable the synchronization participants to acquire the difference elements from the global set so as to complete multi-party set synchronization.

9. An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, characterized in that the processor implements the method according to any of claims 1 to 7 when executing the program.

10. A non-transitory computer readable storage medium storing computer instructions for causing a computer to perform the method of any one of claims 1 to 7.

Images