Method of creating hierarchical indices for a distributed object system

• US 8,429,198 B1
• Filed: 06/06/2012
• Issued: 04/23/2013
• 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): VO, TRUONG V
• Application Number:
  US13/489,751
• Time in Patent Office: 321 Days
• Field of Search: 707/796, 707/797
• 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 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 DMS 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 active object storage to provide the necessary real-time data management services. The distributed object store can be built above raw storage devices, a traditional file system, a special purpose file system, a clustered file system, and a database. 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.

Claims

1. A method of searching a data management system for a data object, the method comprising:

receiving a search request for a data object in a data management system, the data object comprising a lookup value, the data management system comprising a plurality of data management servers organized into a plurality of physically-dispersed regions and at least one computer hardware processor associated with at least one data storage device, the at least one data storage device organized into an object oriented data store and an index tree, each physically-dispersed region comprising at least one cluster, the at least one cluster comprising at least one node and a shared storage, the at least one node continuously receiving at least one data stream, the at least one data stream being stored in the object oriented data store, the index tree comprising a root, at least one level of joins, and a plurality of leaves, each leaf associated with a sorted structure, each sorted structure associated with a key, the key being a sorted structure membership key, a cluster membership key, a region membership key or a universe membership key;

performing a universe membership test against the universe membership key using the lookup value to determine whether the data management system stores the data object;

for the physically-dispersed regions of the data management system storing the data object, iteratively performing a region membership test against the region membership key using the lookup value to determine the physically-dispersed region storing the data object;

for the clusters in the physically-dispersed region storing the data object, iteratively performing a cluster membership test against the cluster membership key using the lookup value to determine the cluster storing the data object;

for the sorted structures in the cluster storing the data object, iteratively performing a sorted structure membership test against the sorted structure membership key using the lookup value to determine the sorted structure storing the data object; and

iteratively searching entries in the sorted structure storing the data object for the lookup value to locate and return the data object.

2. The method of claim 1 wherein the universe membership key is associated with the data management system.

3. The method of claim 1 wherein the region membership key is associated with the physically-dispersed region.

4. The method of claim 1 wherein the cluster membership key is associated with the cluster.

5. The method of claim 1 further comprising updating the key when at least one entry in the sorted structure is modified, removed, or added to the sorted structure.

6. The method of claim 5 further comprising updating the index tree with the updated key.

7. The method of claim 6 wherein updating the index tree comprises adding a new leaf to the index tree or modifying an existing leaf of the index tree.

8. The method of claim 1 wherein the sorted structure comprises a property value and object global identifier.

9. The method of claim 1 wherein the data management system further comprises a network connecting a plurality of application servers to the plurality of data management servers.

10. A data searching system comprising

a data management system comprising a network connecting a plurality of application servers to a plurality of data management servers, the plurality of data management servers organized into a plurality of physically-dispersed regions and comprising one or more computer hardware processors associated with at least one data storage device, the at least one data storage device organized into an object oriented data store and an index tree, each physically-dispersed region comprising at least one cluster, the at least one cluster comprising at least one node and a shared storage, the at least one node continuously receiving at least one data stream, the at least one data stream being stored in the object oriented data store, the index tree comprising a root, at least one level of joins, and a plurality of leaves, each leaf associated with a sorted structure, each sorted structure associated with a key, the key being a sorted structure membership key, a cluster membership key, a region membership key or a universe membership key;

and

computer-readable storage comprising computer-readable instructions that, when executed by the one or more computer hardware processors cause the data management servers to perform operations defined by the computer-executable instructions, the computer-readable instructions comprising;

receiving a search request for a data object in the data management system, the data object comprising a lookup value;

performing a universe membership test against the universe membership key using the lookup value to determine whether the data management system stores the data object;

for the physically-dispersed regions of the data management system storing the data object, iteratively performing a region membership test against the region membership key using the lookup value to determine the physically-dispersed region storing the data object;

for the clusters in the physically-dispersed region storing the data object, iteratively performing a cluster membership test against the cluster membership key using the lookup value to determine the cluster storing the data object;

for the sorted structures in the cluster storing the data object, iteratively performing a sorted structure membership test against the sorted structure membership key using the lookup value to determine the sorted structure storing the data object; and

iteratively searching entries in the sorted structure storing the data object for the lookup value to locate and return the data object.

11. The system of claim 10 wherein the universe membership key is associated with the data management system.

12. The system of claim 10 wherein the region membership key is associated with the physically-dispersed region.

13. The system of claim 10 wherein the cluster membership key is associated with the cluster.

14. The system of claim 10 wherein the computer-executable instructions further comprise updating the key when at least one entry in the sorted structure is modified, removed, or added to the sorted structure.

15. The system of claim 14 wherein the computer-executable instructions further comprise updating the index tree with the updated key.

16. The system of claim 15 wherein updating the index tree comprises adding a new leaf to the index tree or modifying an existing leaf of the index tree.

17. The system of claim 10 wherein the sorted structure comprises a property value and object global identifier.

18. The system of claim 10 wherein the data management system further comprises a network connecting a plurality of application servers to the plurality of data management servers.