Method Of Creating Hierarchical Indices For A Distributed Object System

• US 20100146004A1
• Filed: 01/21/2010
• Published: 06/10/2010
• Est. Priority Date: 07/20/2005
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Sim-Tang, Siew Yong
• Granted Patent: US 7,979,441 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• 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

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 or more 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 an index tree for use in locating a given object in the data management system, 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 with each sorted structure in each leaf, and with each join in the index tree;

in response to modification of a given sorted structure, re-computing the key associated with the given sorted structure; and

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

2. The data structuring method as described in 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.

3. The data structuring method as described in claim 2 wherein the given algorithm is a Bloom Filter.

4. The data structuring method as described in claim 1 wherein the sorted structure is one of:

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

5. The data structuring method as described in claim 1 wherein the sorted structure comprises a property value and an object global unique identifier.

6. The data structuring method as described in claim 1 wherein the sorted structure comprises a temporal value to enable the index tree to be used in locating a given point-in-time version of the given object in the data management system.

7. A data structuring method operative in a data management system organized into one or more 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, maintaining an index tree for use in locating a given object in the data management system, 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, wherein each sorted structure in each leaf and each join in the index tree has an associated key value;

upon a given occurrence, updating the index tree.

8. The method as described in claim 7 wherein the given occurrence is receipt of a notification that a key value associated with a given data source in another index tree has been modified.

9. The method as described in claim 7 wherein the index tree is updated by adding a new leaf to the index tree or modifying an existing leaf.

10. The method as described in claim 9 wherein the index tree is updated by re-computing a value of a cluster membership key.

11. The method as described in claim 10 wherein the index tree is updated by re-computing a value of a region membership key.

12. The method as described in claim 11 wherein the index tree is updated by re-computing a value of a universe membership key.

13. A method operative in a data management system organized into one or more 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:

at each cluster, for each of a set of one or more defined object properties, maintaining an index tree for use in locating a given object in the data management system, 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, wherein each sorted structure in each leaf and each join in the index tree has an associated key value;

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

at the second cluster, updating the index tree based on the given cluster key value propagated from the first cluster.