Method of creating hierarchical indices for a distributed object system
View Patent ↗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.
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.