Interval vector based knowledge synchronization for resource versioning

• US 7,506,007 B2
• Filed: 03/01/2004
• Issued: 03/17/2009
• Est. Priority Date: 03/03/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bjorner, Nikolaj S.
• Primary Examiner(s): PANNALA, SATHYANARAYA R
• Application Number:
  US10/791,041
• Publication Number:
  US 20040186916A1
• Time in Patent Office: 1,842 Days
• Field of Search: 703/203, 703/204
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A method and system for synchronizing objects among members of a replica set. An interval vector is maintained on each member. The interval vector includes one or more intervals each of which has an upper and lower bound. During synchronization, the member sends the interval vector to the member with which it is synchronizing. The other member examines the interval vector and finds resources with versions that are not included in any of the intervals of the interval vector. The other member then transmits these resources to the first member which uses them to update its store. The first member also updates its interval vector to account for the received resources.

Claims

1. A computer storage medium having computer-executable instructions, comprising:

maintaining first interval vector, the first interval vector comprising at least two-intervals of versions, each interval having an upper bound and a lower bound, and the first interval vector comprising at least one gap in versions between two intervals;

evaluating the first interval vector to identify the gap;

using the gap in the first interval vector to determine that a resources is out-of-sync between a first member and a second member of a replica set, wherein the resource has a version contained within the gap of the first interval vector;

synchronizing the resources; and

updating the first interval vector to indicate that the resource is synchronized.

2. The computer storage medium of claim 1, wherein each version is a number.

3. The computer storage medium of claim 1, wherein the intervals of the first interval vector are represented as nodes of a binary search tree.

4. The computer storage medium of claim 3, wherein the binary search tree is selected from the group consisting of an AVL tree, a red-black tree, and a splay tree.

5. The computer storage medium of claim 3, wherein each non-terminal node of the binary search tree has at least one child, the child having an interval with an upper bound less than the lower bound of the interval in the child'"'"'s parent node or having an interval with a lower bound greater than the upper bound of the child'"'"'s parent node.

6. The computer storage medium of claim 3, wherein updating the first interval vector to indicate that the at least one resource is synchronized comprises reducing the number of nodes in the binary search tree.

7. The computer storage medium of claim 1, further comprising transmitting a second interval vector from the second member of the replica set to the first member of the replica set, the second interval vector serving to distinguish updates from conflicts.

8. The compute storage medium of claim 1, wherein the out-of-sync resource is organized in a sequence determined by its corresponding version number and wherein synchronizing the at least one resources comprises transmitting the resources in an order other than the sequence.

9. The computer storage medium of claim 1, wherein the first interval vector is represented by an interval decision diagram having internal and leaf nodes, wherein internal nodes represent binary digits in a binary expansion of a version sequence number and have two outgoing edges.

10. The computer storage medium of claim 9, wherein the interval decision diagram remains the same size regardless of the number of intervals in the interval vector.

11. A computer implemented method, comprising:

maintaining a interval vector, the interval vector comprising at least two-intervals of versions, each interval having an upper bound and a lower bound, and the interval vector comprising at least one gap in versions between two intervals;

evaluating the interval vector to identify the gap;

using the gap in the interval vector to determine that a resource is out-of-sync between a first member and a second member of a replica set, wherein the resource has a version contained within the gap of the interval vector;

synchronizing the resource; and

updating the interval vector to indicate that the resources is synchronized.

12. The method of claim 11, wherein each version is a number.

13. The method of claim 11, wherein the intervals of the interval vector are represented as nodes of a binary search tree.

14. The method of claim 13, wherein the binary search tree is selected from the group consisting of an AVL tree, a red-black tree, and a splay tree.

15. The method of claim 13, wherein each non-terminal node of the binary search tree has at least one child, the child having an interval with an upper bound less than the lower bound of the interval in the child'"'"'s parent node or having an interval with a lower bound greater than the upper bound of the child'"'"'s parent node.

16. The computer implemented method of claim 11, wherein the binary search tree is selected from the group consisting of an AVL tree, a red-black tree, and a splay tree.