Distributed data synchronization in a distributed computing system

1. A system for implementing distributed data synchronization in a distributed computing system, the system comprising:

one or more processors; and

one or more computer storage media storing computer-useable instructions that, when used by the one or more processors, cause the one or more processors to execute:

accessing a first data record of a first data set;

encoding the first data record into a first distributed invertible bloom filter (DIBF) data structure, wherein encoding the first data record generates, for the first DIBF data structure, a first DIBF record based on the first data record, wherein the first DIBF record comprises a data field and a quantifier field, wherein the quantifier field includes a quantifier value that indicates a quantity of references that a plurality of server hosts use to access the first data record;

accessing the first DIBF data structure and an encoded second DIBF data structure, wherein the second DIBF data structure comprises a second DIBF record;

decoding the first DIBF data structure and the second DIBF data structure, wherein decoding the first DIBF data structure and the second DIBF data structure comprises computing a difference between at least the quantifier value of the first DIBF data structure and a quantifier value of the second DIBF data structure;

based on decoding the first DIBF data structure and the second DIBF data structure, determining that a match exists between the first data DIBF data structure and the second DIBF data structure; and

based on decoding the first DIBF data structure and the second DIBF data structure, determining that a match does not exist between the first data DIBF data structure and the second DIBF data structure.

2. The system of claim 1 , wherein encoding the first data record into the first DIBF data structure comprises:

generating a plurality of hash data units based on a plurality fixed data units of the first data record;

multiplying a plurality of fixed data units of the first data record by the quantifier value, to generate fixed data elements for the first DIBF record; and

multiplying the plurality of hash data units of the first data record by the quantifier value, to generate hash data elements for the first DIBF record.

3. The system of claim 1 , based at least in part on the decoding and the quantifier value, synchronizing the first data set across the plurality of server hosts.

4. The system of claim 2 , wherein encoding the first data record into the first DIBF data structure further comprises:

computing at least one insertion position; and

inserting the first DIBF record into the first DIBF data structure at the at least one insertion position of the first DIBF data structure.

5. The system of claim 4 , wherein inserting the first DIBF record comprises:

adding the fixed data elements to existing fixed data elements in the at least one insertion position;

adding the hash data elements to existing hash data elements in the at least one insertion position; and

summing, via an addition operation, the quantifier value to an another quantifier value in the at least one insertion position, wherein the another quantifier value exists before the adding of the fixed data elements and the adding of the hash data elements, and wherein the addition operation for adding is a substitute for an exclusive disjunction (XOR) operation.

6. The system of claim 1 , wherein computing a difference further comprises:

computing a difference between fixed data elements of the first DIBF data structure and fixed data elements of the second DIBF data structure; and

computing a difference between hash data elements of the first DIBF data structure and hash data elements of the second DIBF data structure.

7. The system of claim 1 , wherein the match between the first data DIBF data structure and the second DIBF data structure exists when each of the following occurs:

the difference between fixed data elements of the first DIBF data structure and fixed data elements of the second DIBF data structure,

the difference between hash data elements of the first DIBF data structure and hash data elements of the second DIBF data structure, and

the difference between the quantifier value of the first DIBF data structure and the quantifier value of the second DIBF data structure, result in a zero difference.

8. The system of claim 1 , wherein the match does not exist when any of the following occur:

the difference between fixed data elements of the first DIBF data structure and fixed data elements of the second DIBF data structure,

the difference between hash data elements of the first DIBF data structure and hash data elements of the second DIBF data structure, and

the difference between the quantifier value of the first DIBF data structure and the quantifier value of the second DIBF data structure, result in a non-zero difference.

9. The system of claim 8 , wherein decoding the first DIBF data structure and the second DIBF data structure further comprises:

upon determining that the match does not exist, decoding a data unit for the first data record and decoding a hash unit for the first data record based on division operations; and

determining whether the first DIBF record contains a single DIBF record entry based on the decoded data unit, the hash unit, and a hash function.

10. A computer-implemented method for implementing distributed data synchronization in a distributed computing system, the method comprising:

accessing a first data record;

encoding the first data record into a first distributed invertible bloom filter (DIBF) data structure, wherein encoding the first data record generates, for the first DIBF data structure, a first DIBF record based on the first data record, wherein the first DIBF record comprises a data field and a quantifier field, wherein the quantifier field includes a quantifier value that indicates a quantity of references that one or more server hosts use to access the first DIBF record;

wherein encoding the first data record further comprises:

generating, via a hashing function, a hash data unit based on a fixed data unit of the first data record;

multiplying the fixed data unit of the first data record by the quantifier value to generate a fixed data element for the first DIBF record; and

multiplying the hash data unit of the first data record by the quantifier value, to generate a hash data element for the first DIBF record.

11. The method of claim 10 , wherein the data field comprises a fixed data field and hash data field, wherein the fixed data field comprises the fixed data element and the hash data field comprises the hash data element.

12. The method of claim 10 , the method further comprising:

accessing a second DIBF record having a fixed data unit of a second data record, wherein the fixed data unit of the first data record matches the fixed data unit of the second data record;

computing at least one insertion position;

inserting the first DIBF record into the first DIBF data structure at the at least one insertion position of the first DIBF data structure; and

inserting the second DIBF record into the first DIBF data structure at the at least one insertion position of the first DIBF data structure.

13. The method of claim 10 , wherein inserting the first DIBF record comprises:

adding the fixed data element to an existing fixed data element in the at least one insertion position;

adding the hash data element to an existing hash data element in the at least one insertion position; and

summing, via an addition operation, the quantifier value to an existing quantifier value in the at least one insertion position, wherein the addition operation for adding is a substitute for an exclusive disjunction (XOR) operation.

14. One or more computer storage media having computer-executable instructions embodied thereon that, when executed, by one or more processors, cause the one or more processors to perform a method for providing distributed data synchronization in a distributed computing system, the method comprising:

accessing a first distributed invertible bloom filter (DIBF) data structure, wherein the first DIBF data structure comprises a first DIBF record based on a first data record, wherein the first DIBF record comprises a data field and a quantifier field, wherein the quantifier field includes a quantifier value that indicates a quantity of references that one or more server hosts use to access the first DIBF record;

accessing a second DIBF data structure, wherein the second DIBF data structure comprises a second DIBF record;

encoding the first DIBF data structure and the second DIBF data structure; and

decoding the first DIBF data structure and the second DIBF data structure, wherein decoding the first DIBF data structure and the second DIBF data structure comprises computing a difference between at least the quantifier value of the first DIBF data structure and a quantifier value of the second DIBF data structure.

15. The media of claim 14 , wherein computing a difference further comprises:

computing a difference between a fixed data element of the first DIBF data structure and a fixed data element of the second DIBF data structure; and

computing a difference between a hash data element of the first DIBF data structure and a hash data element of the second DIBF data structure.

16. The media of claim 14 , further comprising, based on decoding the first DIBF data structure and the second DIBF data structure, determining that a match exists between the first data DIBF data structure and the second DIBF data structure.

17. The media of claim 16 , wherein the match exists when each of the following:

the difference between the fixed data element of the first DIBF data structure and fixed data element of the second DIBF data structure,

the difference between the hash data element of the first DIBF data structure and the hash data element of the second DIBF data structure, and

the difference between the quantifier value of the first DIBF data structure and the quantifier value of the second DIBF data structure, result in a zero difference.

18. The media of claim 14 , further comprising, based on decoding the first DIBF data structure and the second DIBF data structure, determining that a match does not exist between the first data DIBF data structure and the second DIBF data structure.

19. The media of claim 18 , wherein the match does not exist when any of the following:

the difference between the fixed data element of the first DIBF data structure and the fixed data element of the second DIBF data structure,

the difference between the hash data element of the first DIBF data structure and the hash data element of the second DIBF data structure, and

the difference between the quantifier value of the first DIBF data structure and the quantifier value of the second DIBF data structure, result in a non-zero difference.

20. The media of claim 18 , wherein decoding the first DIBF data structure and the second DIBF data structure further comprises:

upon determining that the match does not exist, decoding a data unit for the first data record and decoding a hash unit for the first data record based on division operations; and

determining whether the first DIBF record contains a single DIBF record entry based on the decoded data unit, the hash unit, and a hash function.