Method and system for detecting object inconsistency in a loosely consistent replicated directory service

• US 7,324,999 B2
• Filed: 06/14/2004
• Issued: 01/29/2008
• Est. Priority Date: 08/26/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Judd, Steven G.
• Primary Examiner(s): Lu; Kuen S.
• Application Number:
  US10/867,452
• Publication Number:
  US 20040243571A1
• Time in Patent Office: 1,324 Days
• Field of Search: 707/101, 707/204
• US Class Current: 707/690
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The invention describes a system for detecting partial changes to data-structures of interest. If an inter-related set of data items are to be used then it is of value to know that the data items are undergoing changes, and thus may not be self consistent, and/or have been tampered with and/or are not the most recent update. The invention uses GUIDS to track updates by assigning a GUID to a selected set of nodes or items belonging to an identified set, preferably arranged in a tree structure. A new GUID is generated whenever an update takes place. Methods are defined to test that the interrelated data items are valid, i.e., replicated into, by testing for changes in the GUID by traversing the interrelated data items and comparing GUIDs at each node. Similarly, methods are provided for generating a new GUID in course of inititiating an update, or in order to invalidate an intererlated data item set, and additional methods are envisaged for catering to particular applications such as assuring integrity of the data by using encryption and certificates.

Claims

1. A computer-implemented method, comprising:

accessing an object-set in a database, the object-set corresponding to a tree with a root node and each node of the tree corresponding to one of a plurality of objects in the object-set, each of said plurality of objects including a consistency-identifier representing information identifying a set of nodes updated collectively as part of a prior update and a consistency-count representing a single valued function of the number of child nodes present at the completion of the prior update; and

traversing the tree to visit every node in the tree to;

determine a number of children of the root node having the same consistency-identifier as the consistency-identifier of the root node, and

determine that partial-updates of the object-set are present if the consistency-count of a node of the tree is not equal to the single valued function of the number of children of the root-node.

2. The computer-implemented method of claim 1, wherein a depth-first strategy is used in traversing the tree.

3. A computer-readable storage medium storing computer-executable instructions for performing the method recited in claim 1.