Stabilization of distributed systems

• US 20100082802A1
• Filed: 09/30/2008
• Published: 04/01/2010
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jackson, Ethan K., Schulte, Wolfram
• Granted Patent: US 7,822,853 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

One or more embodiments, described herein, are directed towards a technology for analyzing a distributed system in order to determine one or more inconsistencies placing the distributed system in an unstable state. Once the one or more inconsistencies are determined, one or more operations reconciling the inconsistencies are defined in order to stabilize the distributed system.

Claims

1. In a distributed system comprised of a plurality of nodes, a method for facilitating stabilization of the distributed system, the method comprising:

receiving an indication of a connection between a first node and a second node, each of the first node and second node storing one or more types of data;

creating a clique, the clique comprising the first node, the second node, and a plurality of other connected nodes;

monitoring the clique for consistency across the one or more types of data located in the plurality of nodes in the clique;

identifying one or more inconsistencies occurring in the clique by checking one or more conditions for data consistency over the clique;

specifying one or more reconciling operations, wherein the one or more reconciling operations reconcile the one or more identified inconsistencies; and

stabilizing the clique by initiating performance of the specified reconciling operations, wherein the stabilizing produces a stable clique, a stable clique being a plurality of nodes, wherein each node is connected to one another and wherein the one or more types of data contained over the clique satisfies the one or more conditions.

2. A method as recited by claim 1, further comprising determining an operation horizon, wherein the operation horizon defines a particular set of nodes performing the one or more operations reconciling the one or more identified inconsistencies.

3. A method as recited by claim 2, wherein the particular set of nodes must be connected to successfully perform the one or more operations.

4. A method as recited by claim 1, wherein the one or more types of data are consistent when one or more conditions defined for each type of data are satisfied.

5. A method as recited by claim 1, wherein the one or more types of data are consistent when one or more conditions defined for each type of data are satisfied, the one or more conditions being pre-set and customized in accordance with each particular type of data.

6. A method as recited by claim 1, wherein the one or more types of data are consistent when one or more conditions defined for each type of data are satisfied, the one or more conditions being defined by a system analyst.

7. A method as recited by claim 1, wherein the stabilizing comprises performing a plurality of reconciling operations in sequence over a set of cliques.

8. In a distributed system comprised of a plurality of nodes, one or more computer-readable media having embodied thereon computer-executable instructions that, when executed by a computer, direct performance of a method for facilitating stabilization of the distributed system, the method comprising:

receiving an indication of a connection between a first node and a second node, each of the first node and second node storing one or more types of data;

creating a clique, the clique comprising of a set of completely connected nodes;

monitoring the clique for consistency across the one or more types of data persisting over the clique; and

in response to the monitoring, stabilizing the clique by reconciling one or more identified inconsistencies found across the one or more types of data located in the clique.

9. One or more computer-readable media as recited by claim 8 wherein the stabilizing comprises performing one or more reconciling operations, wherein the one or more reconciling operations reconcile the one or more identified inconsistencies found across the one or more types of data located in the clique.

10. One or more computer-readable media as recited by claim 9, further comprising determining an operation horizon, wherein the operation horizon defines a particular set of nodes performing the one or more operations reconciling the one or more identified inconsistencies.

11. One or more computer-readable media as recited by claim 10, wherein the particular set of nodes must be connected to successfully perform the one or more operations.

12. One or more computer-readable media as recited by claim 8 further comprising:

identifying the one or more identified inconsistencies found across the one or more types of data located in the cliques; and

specifying one or more reconciling operations, wherein the one or more reconciling operations reconcile the one or more identified inconsistencies.

13. One or more computer-readable media as recited by claim 8, wherein the one or more types of data are consistent when one or more conditions defined for each type of data are satisfied.

14. One or more computer-readable media as recited by claim 8, wherein the one or more types of data are consistent when one or more conditions defined for each type of data are satisfied, the one or more conditions being pre-set and customized in accordance with each particular type of data.

15. One or more computer-readable media as recited by claim 14, wherein the clique further comprises a plurality of nodes, each node being completely connected to one another.

16. One or more computer-readable media as recited by claim 14, wherein the stabilizing produces a stable clique, a stable clique being a plurality of nodes, wherein each node is connected to one another and wherein one or more types of data located across the plurality of nodes are consistent.

17. One or more computer-readable media as recited by claim 14, wherein the stabilizing produces a stable clique, a stable clique being a plurality of nodes, wherein each node is connected to one another and wherein:

one or more types of data located across the plurality of nodes are consistent;

or

reconciling operations have been initiated which will reconcile one or more inconsistencies associated with the one or more types of data.

18. A distributed system comprising:

a plurality of nodes;

a processor;

one or more computer-readable media having embodied thereon computer-executable instructions that, when executed by the processor, configure the distributed system to perform acts comprising;

receiving an indication of a connection between a first node and a second node, each of the first node and second node storing one or more types of data;

creating a clique, the clique comprising the first node and the second node, and a plurality of other nodes so that all nodes are fully connected;

monitoring the clique for consistency across the one or more types of data located in the clique; and

in response to the monitoring, stabilizing the clique by reconciling one or more identified inconsistencies found across the one or more types of data located in the clique.

19. A distributed system as recited by claim 18, wherein the one or more types of data are consistent when one or more conditions defined for each type of data are satisfied, the one or more conditions being pre-set and customized by a user in accordance with each particular type of data.

20. A distributed system as recited by claim 18, further comprising determining an operation horizon, wherein the operation horizon defines a particular set of connected nodes performing the one or more operations reconciling the one or more identified inconsistencies