Method of creating hierarchical indices for a distributed object system

• US 7,979,441 B2
• Filed: 01/21/2010
• Issued: 07/12/2011
• Est. Priority Date: 07/20/2005
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Sim-Tang, Siew Yong
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Vo; Truong V
• Application Number:
  US12/691,616
• Publication Number:
  US 20100146004A1
• Time in Patent Office: 537 Days
• Field of Search: 707/673, 707/741
• US Class Current: 707/741
• 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 comprising:

wherein a data management system is organized into a plurality of physically-dispersed regions, wherein;

each physically-dispersed region of the plurality of physically-dispersed regions comprises at least one cluster;

a given cluster of the at least one cluster comprises at least one node and a shared storage, and

the at least one node receives at least one data stream continuously and stores the at least one data stream in an object-oriented data store;

for a defined object property, maintaining an index tree for use in determining where a given object in the data management system is located, the index tree comprising;

a root;

at least one level of joins;

a plurality of leaves; and

wherein;

each leaf of the plurality of leaves is associated with a sorted structure;

a join above at least one leaf 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;

wherein the sorted structure comprises a property value and an object global unique identifier;

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

responsive to a given occurrence;

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

re-computing the key of at least one join in the index tree;

wherein the key of the at least one join is at least one of a cluster membership key, a region membership key, or a universe membership key; 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 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.

4. The data structuring 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.

5. The data structuring method of claim 1, wherein, responsive to the given occurrence further comprises updating the index tree.

6. The data structuring method of claim 5, wherein updating the index tree comprises adding new leaf to the index tree or modifying an existing leaf of the index tree.

7. The data structuring 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.

8. The data structuring method of claim 1, 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.

9. The data structuring method of claim 1, wherein the key is a hash key that is generated by applying a given algorithm to at least a current key of the given sorted structure.

10. The data structuring method of claim 1, wherein the given algorithm is a Bloom Filter.

11. The data structuring method of claim 1, wherein responsive to the given occurrence further comprises:

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.

12. The data structuring method of claim 1, wherein the given occurrence is the modification of the given sorted structure.