Generating probalistic data structures in gossip protocols

• US 10,362,105 B1
• Filed: 07/31/2017
• Issued: 07/23/2019
• Est. Priority Date: 07/31/2017
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: DeMarco, Paul Derek
• Primary Examiner(s): Whipple, Brian
• Application Number:
  US15/665,169
• Time in Patent Office: 722 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Systems and methods are disclosed to implement a gossip protocol to synchronize data in among nodes of a distributed computing system. During a round of the gossip protocol, a first node generates a space-efficient probabilistic data structure (SEPDS) from its data set. The SEPDS is generated using a set of hash functions that changes from round to round. The set of hash functions may be derived using two base hash functions without reliance on the use of any randomizing operations, and the result of each hash function may be assigned to modify a different portion of the SEPDS. The generated SEPDS is sent to a second node, which performs probabilistic queries on the SEPDS to compare the contents of its own data set with the SEPDS. Any data items that are missing from the SEPDS are sent back to the first node, which updates its data set accordingly.

Claims

1. A system, comprising:

a distributed computing system comprising a plurality of nodes, each implemented by one or more processors and associated memory, wherein;

each node stores a data set of data items and uses a gossip protocol to synchronize its data set with data sets of other nodes of the plurality of nodes; and

during each round of the gossip protocol, each node is configured to;

select another node of the plurality of nodes to gossip with;

determine a set of hash functions to be used in the round to generate a space-efficient probabilistic data structure (SEPDS) that reflects a content of its data set, wherein the set of hash functions changes from round to round;

generate the SEPDS from its data set using the set of hash functions; and

perform a synchronization operation with the other node using the SEPDS.

2. The system of claim 1, wherein:

to determine the set of hash functions, each node is configured to;

determine a set of independent base hash functions; and

derive the set of hash functions based on the independent hash functions.

3. The system of claim 1, wherein:

the SEPDS comprises a bloom filter; and

to generate the bloom filter, each node is configured to;

hash a data item in its data set using each hash function in the set to determine different locations in the bloom filter, wherein the result of each hash function in the set is assigned to modify locations in different portion of the bloom filter; and

modify the bloom filter at the determined locations to reflect the data item.

4. The system of claim 1, wherein:

to perform the synchronization operation, each node is configured to;

send the SEPDS to the other node;

receive data items from the other node that are not present in the SEPDS and

update its data set with the received data items.

5. The system of claim 1, wherein the other node is configured to:

responsive to receiving the SEPDS from the node;

determine the set of hash functions;

perform one or more probabilistic queries on the SEPDS using the set of hash functions to determine data items in the its data set that are not present in the SEPDS; and

send the data items to the node.

6. A method comprising:

performing a synchronization of data sets in a distributed computing system using a gossip protocol, wherein the distributed computing system comprises a plurality of nodes implemented by one or more processors and associated memory, and each node performs, during each round of the gossip protocol;

selecting another node in the plurality of nodes to gossip with;

determining a set of hash functions to be used for the round to generate a space-efficient probabilistic data structure (SEPDS) that reflects a content of its data set, wherein the set of hash functions changes from round to round;

generating the SEPDS from its data set using the set of hash functions; and

performing a synchronization operation with the other node using the SEPDS.

7. The method of claim 6, wherein the SEPDS comprises a bloom filter, and generating the bloom filter comprises:

hashing a data item in the first node'"'"'s data set using each hash function in the set to determine locations in the bloom filter; and

modifying the bloom filter at the determined locations to reflect the data item.

8. The method of claim 7, wherein each hash function is assigned to modify a different portion of the bloom filter.

9. The method of claim 6, wherein performing the synchronization operation comprises:

sending the SEPDS to the other node, wherein the SEPDS includes a plurality of data items, each data item including a record identifier of a record from the node'"'"'s data set and a latest version identifier of the record;

receiving a discrepancy list from the other node including record identifiers and corresponding latest version identifiers in a data set of the other node that are not present in the SEPDS;

determining, from the discrepancy list, a first set of records for which the node has a later version, or a second set of records for which the other node has a later version; and

sending to the other node record data for records in the first set, or a request to obtain record data for records in the second set.

10. The method of claim 6, wherein performing the synchronization operation comprises receiving two independent base hash functions from a different node of the distributed computing system, wherein the two independent base hash functions are used to derive the set of hash functions used to generate the SEPDS.

11. The method of claim 6, wherein performing the synchronization operation comprises:

sending the SEPDS to the other node;

receiving data items from the other node that are not present in the SEPDS and

updating its data set with the received data items.

12. The method of claim 6, further comprising:

performing, by the other node;

performing one or more probabilistic queries on the SEPDS using the set of hash functions to determine data items in the other node'"'"'s data set that are missing from the SEPDS;

generating a second SEPDS from the other node'"'"'s data set using the set of hash functions; and

sending the missing data items and the second SEPDS to the node.

13. The method of claim 6, wherein selecting another node in the plurality of nodes to gossip with comprises selecting a different node at least partly in a pseudo-random fashion.

14. The method of claim 6, wherein performing the synchronization of data sets comprises:

prior to the generation of the SEPDS by each node;

determining a schedule of different hash functions to use for different rounds of the gossip protocol; and

providing the schedule to the plurality of nodes.

15. The method of claim 6, wherein:

the data set includes a set of node events; and

generating the SEPDS comprises generating the SEPDS from a subset of node events in the data set that occurred since a last time cutoff.

16. The method of claim 6, wherein generating the SEPDS comprises generating the SEPDS from a subset of data items in the data set that were learned during a number of most recent rounds.

17. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors of a first node in a distributed computing system implemented by a plurality of nodes, cause the first node to:

exchange communications via a gossip protocol with other nodes in the plurality of nodes to synchronize a data set stored by the first node with data sets stored by the other nodes, wherein, during a given round of the gossip protocol, the program instructions when executed cause the first node to;

determine a set of hash functions for the round, wherein the set of hash functions changes from round to round;

generate a space-efficient probabilistic data structure (SEPDS) that reflects a content of the data set using the set of hash functions;

send the SEPDS to a second node of the plurality of nodes;

receive from the second node one or more data items that are missing from the SEPDS; and

update the data set with the received data items.

18. The non-transitory computer-accessible storage medium of claim 17, wherein the program instructions when executed on the one or more processors of the first node cause the first node to:

during the given round of the gossip protocol;

receive another SEPDS from a third node of the plurality of nodes;

perform one or more probabilistic queries on the other SEPDS using the set of hash functions to determine data items in the data set that are missing from the other SEPDS; and

send the missing data items to the third node.

19. The non-transitory computer-accessible storage medium of claim 17, wherein to determine a set of hash functions for the round, the program instructions when executed on the one or more processors of the first node cause the first node to:

determine two independent base hash functions including a first base function and a second base function; and

derive the set of hash functions based on the two base functions, wherein the derivation comprises, for each hash function in the set, adding the first base function to a product of the second base function and a different coefficient.

20. The non-transitory computer-accessible storage medium of claim 17, wherein:

the SEPDS comprises a bloom filter; and

to generate the bloom filter, the program instructions when executed on the one or more processors of the first node cause the first node to;

hash a data item in its data set using each hash function in the set to determine different locations in the bloom filter, wherein the result of each hash function in the set is assigned to modify locations in a different portion of the bloom filter; and

modify the bloom filter at the determined locations to reflect the data item.