Method of creating hierarchical indices for a distributed object system

• US 8,200,706 B1
• Filed: 07/11/2011
• Issued: 06/12/2012
• Est. Priority Date: 07/20/2005
• Status: Expired due to Fees

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Sim-Tang, Siew Yong
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US13/179,904
• Time in Patent Office: 337 Days
• Field of Search: 707/797, 707/796
• 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 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:

organizing a data management system into a plurality of physically-dispersed regions, each physically-dispersed region of the plurality of physically-dispersed regions including at least one cluster, a given cluster of the at least one cluster including at least one node and a shared storage, the data management system including a plurality of data management servers, each data management server including at least one computer hardware processer;

continuously receiving at the at least one node at least one data stream;

storing the at least one data stream in an object-oriented data store;

maintaining an index tree for use in determining where a given object in the data management system is located, the index tree including a root, at least one level of joins, and a plurality of leaves, each leaf of the plurality of leaves associated with a sorted structure, the sorted structure including 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;

re-computing the key associated with a given sorted structure and the key of at least one join in the index tree, the key of the at least one join is a cluster membership key, a region membership key, or a universe membership key;

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

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

2. The data structuring method of claim 1, wherein the sorted structure is a BTree, a B+Tree, or 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, further comprising receiving notification that a key value associated with a given data source in another index tree has been modified.

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

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

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

8. The data structuring method of claim 7, wherein the algorithm is a Bloom Filter.

9. The data structuring method of claim 1, further comprising:

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 and re-computing at least one key value.

10. A system for managing data, the 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;

each application server associated with at least one first data storage device;

each data management server comprising at least one computer hardware processor and associated with at least one second data storage device, the at least one second data storage device organized into an object-oriented data store and an index tree; and

each physically-dispersed region including at least one cluster, a given cluster including 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 stored in the object-oriented data store, the index tree for use in determining where a given object is located, the index tree including a root, at least one level of joins, and a plurality of leaves, each leaf of the plurality of leaves associated with a sorted structure, the sorted structure including a property value and an object global unique identifier, each sorted structure in each leaf and with each join in the index tree associated with a key and a key value, the key of the at least one join is a cluster membership key, a region membership key, or a universe membership key;

wherein in response to a given occurrence, the data management server re-computes the key associated with the given sorted structure and the key of at least one join in the index tree, and performs a membership test on at least one key in the index tree to identify which of the clusters may have the given object so as to locate the given object within the given cluster using the sorted structure.

11. The system of claim 10, wherein the sorted structure comprises a temporal value and the data management server uses the index tree to locate a given point-in-time version of the given object.

12. The system of claim 10, 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.

13. The system of claim 10, wherein, responsive to the given occurrence the data management server updates the index tree.

14. The system of claim 13, wherein updating the index tree comprises adding new leaf to the index tree or modifying an existing leaf of the index tree.

15. The system of claim 10, wherein the key is a hash key that is generated by applying an algorithm to at least a current key of the given sorted structure.

16. The system of claim 15, wherein the algorithm is a Bloom Filter.

17. The system of claim 10, wherein responsive to the given occurrence, the data management server propagates a given cluster key value from a first cluster to a second cluster;

and at the second cluster, updates 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.

18. A data structuring system, comprising:

a plurality of data management servers, each data management server including one or more computer hardware processors in communication with associated disk storage and memory, the memory storing computer instructions, which, when executed cause the one or more processors to perform the following;

organize a data management system into a plurality of physically-dispersed regions, each physically-dispersed region of the plurality of physically-dispersed regions including at least one cluster, a given cluster of the at least one cluster including at least one node and a shared storage;

continuously receive at the at least one node at least one data stream;

store the at least one data stream in an object-oriented data store;

maintain an index tree for use in determining where a given object in the data management system is located, the index tree including a root, at least one level of joins, and a plurality of leaves, each leaf of the plurality of leaves associated with a sorted structure, the sorted structure including a property value and an object global unique identifier;

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

re-compute the key associated with the given sorted structure and the key of at least one join in the index tree, the key of the at least one join is a cluster membership key, a region membership key, or a universe membership key;

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

use the sorted structure to locate the given object within the given cluster.

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

20. The data structuring system of claim 19 wherein if the membership test determines that the given object is not associated with the given portion of the index tree, the given portion of the index tree is eliminated from further traversal and search.