Stabilization of distributed systems

• US 7,822,853 B2
• Filed: 09/30/2008
• Issued: 10/26/2010
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Schulte, Wolfram, Jackson, Ethan K.
• Primary Examiner(s): Jean; Frantz B
• Application Number:
  US12/242,742
• Publication Number:
  US 20100082802A1
• Time in Patent Office: 756 Days
• Field of Search: 709/217, 709/219, 709/214, 709/224, 707/10, 707/101, 707/1, 707/201
• 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. A method for facilitating stabilization of a 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, 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;

identifying one or more inconsistencies occurring in the clique by checking the 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;

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; and

stabilizing the clique by initiating performance of the one or more 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, wherein the particular set of nodes must be connected to successfully perform the one or more reconciling operations.

3. A method as recited by claim 1, wherein the one or more conditions are defined by a system analyst.

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

5. In a distributed system comprised of a plurality of nodes, one or more computer-readable media having stored 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 including the first node and the second node;

monitoring the clique for consistency across the one or more types of data persisting over the clique, 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;

identifying one or more inconsistencies found across the one or more types of data located in the clique;

stabilizing the clique by reconciling the one or more inconsistencies found across the one or more types of data located in the clique, wherein the stabilizing comprises;

determining an operation horizon that defines a particular set of nodes for performing one or more operations reconciling the one or more identified inconsistencies; and

performing the one or more operations that reconcile the one or more inconsistencies found across the one or more types of data located in the clique.

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

7. One or more computer-readable media as recited by claim 5, wherein the one or more conditions are defined by a system analyst.

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

9. One or more computer-readable media as recited by claim 7, 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 located across the plurality of nodes are consistent.

10. One or more computer-readable media as recited by claim 5, wherein the stabilizing comprises performing a plurality of reconciling operations in sequence over a set of cliques.

11. A distributed system comprising:

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, 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;

identifying one or more inconsistencies found across the one or more types of data located in the clique;

determining an operation horizon, wherein the operation horizon defines a particular set of connected nodes for performing one or more operations reconciling the one or more inconsistencies; and

stabilizing the clique by performing the one or more operations reconciling the one or more inconsistencies found across the one or more types of data located in the clique.

12. A distributed system as recited by claim 11, wherein the one or more conditions are defined by a system analyst.

13. A distributed system as recited by claim 11, wherein the stabilizing comprises performing a plurality of reconciling operations in sequence over a set of cliques.