Method of creating hierarchical indices for a distributed object system

• US 7,689,602 B1
• Filed: 07/20/2005
• Issued: 03/30/2010
• Est. Priority Date: 07/20/2005
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: BakBone Software, Inc. (Quest Software, Inc.)
• Inventors: Sim-Tang, Siew Yong
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Vo; Truong V
• Application Number:
  US11/185,168
• Time in Patent Office: 1,714 Days
• Field of Search: 707/7, 707/204, 709/202, 395/612
• US Class Current: 707/673
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

Abstract

A data management system or “DMS” provides data services to data sources associated with a set of application host servers. The data management system typically comprises one or more regions, with each region having one or more clusters. A given cluster has one or more nodes that share storage. When providing continuous data protection and data distribution, the DMS nodes create distributed object storage to provide the necessary real-time data management services. The objects created by the DMS nodes are so-called active objects. The distributed object store can be built above raw storage devices, a traditional file system, a special purpose file system, a clustered file system, a database, and so on. According to the present invention, the DMS active object store provides an indexing service to the active objects. In an illustrative embodiment, any object property that has a given attribute is indexed and, as a result, the attribute becomes searchable. The DMS provides hierarchical distributed indexing using index trees to facilitate searching in a highly efficient manner.

Claims

1. A data structuring method operative in a data management system organized into one two or more physically-dispersed regions, with each region comprising one or more clusters, and wherein a given cluster includes one or more nodes and a shared storage, and wherein the nodes receive data streams continuously and store such data streams in an object-oriented data store, comprising:

for a defined object property, generating maintaining an index tree for use in locating determining where a given object in the data management system is located, the index tree comprising a root, one or more levels of joins, and a plurality of leaves, wherein each leaf is associated with a sorted structure, a join above one or more leaves aggregates leaves that are in a given cluster, a join on a next level up in the index tree aggregates the joins of multiple clusters that belong to a given region, and a join on a next level up in the index tree aggregates the joins of multiple regions that belong to a given universe at the root of the index tree;

associating a key and a key value with each sorted structure in each leaf and with each join in the index tree;

wherein the key is a hash key that is generated by applying a Bloom Filter to at least a current key of a given sorted structure;

responsive to the modification of the given sorted structure;

re-computing the key associated with the given sorted structure;

re-computing the keys of one or more joins in the index tree;

propagating a given cluster key value from a first cluster to a second cluster; and

at the second cluster, updating the index tree based on the given cluster key value propagated from the first cluster, wherein the updating includes re-computing at least one key value;

responsive to a given occurrence, updating the index tree by re-computing at least one key value; and

responsive to a search request for the given object;

performing a membership test on at least one key in the index tree to identify which of the multiple clusters may have the given object; and

using a sorted structure to locate the given object within a given cluster.

2. The data structuring method of claim 1 wherein the sorted structure is one of:

a BTree, A B+Tree, and a sorted list of entries.

3. The data structuring method of claim 1 wherein the sorted structure comprises a property value and an object global unique identifier.

4. The data structuring method of claim 1 wherein the sorted structure comprises a temporal value and the method further includes using the index tree to locate a given point-in-time version of the given object in the data management system.

5. The method of claim 1 wherein the given occurrence is receipt of a notification that a key value associate with a given data source in another index tree has been modified.

6. The method of claim 1 wherein the index tree is updated by adding a new leaf to the index tree or modifying an existing leaf.

7. The method of claim 6 wherein the index tree is updated by re-computing a value of a cluster membership key.

8. The method of claim 7 wherein the index tree is updated by re-computing a value of a region membership key.

9. The method of claim 8 wherein the index tree is updated by re-computing a value of a universe membership key.

10. The method of claim 1 wherein at each level of the index tree a membership test is performed to determine whether the search request is associated with a given object in a given portion of the index tree as indicated by the associated key value.

11. The method of claim 10 wherein if the membership test determines that the given object is not associated with a given portion of the index tree, the given portion of the index tree is eliminated from further traversal and search.