Systems and methods for efficiently synchronizing configuration data within distributed computing systems
View Patent ↗A method for efficiently synchronizing configuration data within distributed computing systems may include: 1) maintaining a hash tree that is based on the hierarchical relationship of each object within a distributed computing system that is relevant to the computing device, 2) determining, during a reconciliation process with an additional computing device, that a hash of a top-level node of the hash tree differs from a hash of a corresponding node of the additional computing device's hash tree, 3) identifying, by iterating through the hash levels of the computing device's hash tree, at least one leaf node within the computing device's hash tree whose hash differs from a hash of a corresponding leaf node within the additional computing device's hash tree, 4) receiving the changed leaf node's value from the additional computing device, and then 5) updating the identified leaf node's value to match the changed leaf node's value.
1. A computer-implemented method for efficiently synchronizing configuration data within distributed computing systems, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:
maintaining a hash tree that identifies the hierarchical structure of at least a portion of a distributed computing system, wherein the hash tree comprises:
for each leaf node within the hash tree, a hash of the leaf node's value;
for each non-leaf node within the hash tree, a hash of the concatenated hashes of all of the non-leaf node's children;
identifying, during a reconciliation process with an additional computing device within the distributed computing system, at least one change to the hierarchical structure of the distributed computing system by:
determining that a hash of a top-level node of the hash tree differs from a hash of a corresponding node of a hash tree maintained by the additional computing device;
identifying, by iterating through the hash levels of the computing device's hash tree, at least one leaf node within the computing device's hash tree whose hash differs from a hash of a corresponding leaf node within the additional computing device's hash tree that has changed subsequent to a prior reconciliation process;
receiving the changed leaf node's value from the additional computing device;
updating the identified leaf node's value to match the changed leaf node's value.
2. The method of claim 1 , wherein maintaining the computing device's hash tree comprises:
determining that the value of at least one leaf node within the computing device's hash tree has changed;
recalculating the changed leaf node's hash;
iteratively recalculating the hash of each ancestor of the changed leaf node until the hash of the top-level node has been recalculated.
3. The method of claim 1 , wherein maintaining the computing device's hash tree comprises calculating hashes using the same hash function that is used by all other devices within the distributed computing system.
4. The method of claim 1 , wherein maintaining the computing device's hash tree comprises flagging nodes that have been deleted from the computing device's hash tree.
5. The method of claim 4 , wherein maintaining the computing device's hash tree further comprises purging the flagged nodes from the computing device's hash tree.
6. The method of claim 1 , wherein maintaining the computing device's hash tree comprises attempting to reduce the probability of hash collisions by:
using a hash-collision-detection function to identify potential hash collisions;
modifying the hash of a problematic node implicated in a potential hash collision by:
creating a null child node for the problematic node;
recalculating the problematic node's hash.
7. The method of claim 1 , wherein maintaining the computing device's hash tree comprises using differing hash functions when calculating leaf-node hashes and non-leaf-node hashes in an attempt to reduce the probability of hash collisions.
8. The method of claim 1 , wherein each node within the hash tree represents an object within the distributed computing system.
9. The method of claim 8 , wherein the object comprises:
a system;
a group;
a resource;
an attribute.
10. The method of claim 1 , wherein determining that the hash of the top-level node differs from the hash of the corresponding node comprises:
sending a request for the hash of the corresponding node to the additional computing device;
receiving the hash of the corresponding node from the additional computing device;
determining, by comparing the hash of the top-level node with the hash of the corresponding node, that the hash of the top-level node differs from the hash of the corresponding node.
11. The method of claim 1 , wherein determining that the hash of the top-level node differs from the hash of the corresponding node comprises:
sending the hash of the top-level node to the additional computing device;
receiving a communication from the additional computing device that indicates that the hash of the top-level node differs from the hash of the corresponding node.
12. The method of claim 1 , wherein receiving the changed leaf node's value from the additional computing device comprises receiving a subset of the additional computing device's configuration data that contains the changed leaf node's value.
13. The method of claim 12 , wherein receiving the subset of the additional computing device's configuration data that contains the changed leaf node's value comprises receiving a snapshot of the subset of the additional computing device's configuration data that contains the changed leaf node's value.
14. The method of claim 1 , wherein the computing device's hash tree comprises a subset of the additional computing device's hash tree.
15. The method of claim 1 , wherein:
the computing device comprises a client and the additional computing device comprises a server;
the computing device and the additional computing device comprise peers within a peer-to-peer computing system.
16. A system for efficiently synchronizing configuration data within distributed computing systems, the system comprising:
a maintenance module programmed to maintain a hash tree for a computing device that identifies the hierarchical structure of at least a portion of a distributed computing system, wherein the hash tree comprises:
for each leaf node within the hash tree, a hash of the leaf node's value;
for each non-leaf node within the hash tree, a hash of the concatenated hashes of all of the non-leaf node's children;
a reconciliation module programmed to identify, during a reconciliation process with an additional computing device within the distributed computing system, at least one change to the hierarchical structure of the distributed computing system by:
determining that a hash of a top-level node of the hash tree differs from a hash of a corresponding node of a hash tree maintained by the additional computing device;
identifying, by iterating through the hash levels of the computing device's hash tree, at least one leaf node within the computing device's hash tree whose hash differs from a hash of a corresponding leaf node within the additional computing device's hash tree that has changed subsequent to a prior reconciliation process;
wherein the reconciliation module is further programmed to:
receive the changed leaf node's value from the additional computing device;
update the identified leaf node's value to match the changed leaf node's value;
at least one processor configured to execute the maintenance module and the reconciliation module.
17. The system of claim 16 , wherein the maintenance module maintains the computing device's hash tree by:
determining that the value of at least one leaf node within the computing device's hash tree has changed;
recalculating the changed leaf node's hash;
iteratively recalculating the hash of each ancestor of the changed leaf node until the hash of the top-level node has been recalculated.
18. The system of claim 16 , wherein the reconciliation module receives the changed leaf node's value from the additional computing device by receiving a subset of the additional computing device's configuration data that contains the changed leaf node's value.
19. The system of claim 16 , wherein:
the computing device comprises a client and the additional computing device comprises a server;
the computing device and the additional computing device comprise peers within a peer-to-peer computing system.
20. A non-transitory computer-readable-storage medium comprising computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:
maintain a hash tree that identifies the hierarchical structure of at least a portion of a distributed computing system, wherein the hash tree comprises:
for each leaf node within the hash tree, a hash of the leaf node's value;
for each non-leaf node within the hash tree, a hash of the concatenated hashes of all of the non-leaf node's children;
identify, during a reconciliation process with an additional computing device within the distributed computing system, at least one change to the hierarchical structure of the distributed computing system by:
determining that a hash of a top-level node of the hash tree differs from a hash of a corresponding node of a hash tree maintained by the additional computing device;
identifying, by iterating through the hash levels of the computing device's hash tree, at least one leaf node within the computing device's hash tree whose hash differs from a hash of a corresponding leaf node within the additional computing device's hash tree that has changed subsequent to a prior reconciliation process;
receive the changed leaf node's value from the additional computing device;
update the identified leaf node's value to match the changed leaf node's value.