Systems and methods for maintaining distributed data

• US 20070094277A1
• Filed: 10/21/2005
• Published: 04/26/2007
• Est. Priority Date: 10/21/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Schack, Darren, Fachan, Neal, Passey, Aaron
• Granted Patent: US 7,797,283 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

Systems and methods are disclosed that provide an indexing data structure. In one embodiment, the indexing data structure is mirrored index tree where the copies of the nodes of the tree are stored across devices in a distributed system. In one embodiment, nodes that are stored on an offline device are restored, and an offline device that comes back online is merged into the distributed system and given access to the current indexing data structure. In one embodiment, the indexing data structure is traversed to locate and restore nodes that are stored on offline devices of the distributed system.

Claims

1. An indexing system, comprising:

a plurality of storage devices configured to communicate with each other;

a set of database records each record with a distinct index; and

a balanced index tree structure comprising;

a first and second copy of a set of leaf nodes stored among the plurality of storage devices configured to store the set of database records based on the indexes; and

a first and second copy of a set of parent nodes of the leaf nodes stored among the plurality of storage devices and configured to store references to the first and second copy of the set of leaf nodes;

a first and second copy of a set of grandparent nodes of the leaf nodes stored among the plurality of storage devices, configured to store references to the first and second copy of the parent nodes;

a first and second copy of a root node configured to store references to the first and second copy of the grandparent nodes;

the set of parent nodes, set of grandparent nodes, and the root node configured to index the first and second copy of the set of leaf nodes based on the indexes in the form of a balanced tree.

2. An indexing system, comprising:

a plurality of storage devices configured to communicate with each other;

a set of data units wherein the set of data units includes an index value for each data unit; and

an index data structure comprising;

a first and second copy of a set of first nodes stored among the plurality of storage devices; and

a first and second copy of a set of second nodes stored among the plurality of storage devices;

the first and second copy of the set of second nodes configured to store the set of data units based on the index values of each data unit; and

the first and second copy of the set of first nodes configured to index the first and second copy of the set of second nodes based on the index values of the data units stored in the second nodes.

3. The indexing system of claim 2 further comprising a plurality of superblocks stored on each of the plurality of storage devices, the plurality of superblocks referencing the index data structure.

4. The indexing system of claim 2, wherein the index data structure is a balanced tree, the set of first nodes are inner nodes, and the set of second nodes are leaf nodes.

5. The indexing system of claim 3 further comprising a first and second copy of a root node selected from the first and second copy of the set of inner nodes.

6. The indexing system of claim 5 further comprising a plurality of superblocks stored on each of the plurality of storage devices, the plurality of superblocks referencing the first and second copy of the root node.

7. The indexing system of claim 2, wherein the set of data units include at least one of database records, physical addresses, and metadata.

8. The indexing system of claim 2, wherein the index data structure is at least one of a tree, a hash table, and a linked list.

9. The indexing system of claim 2, the index data structure further comprising a version value.

10. The indexing system of claim 2 further comprising a third copy of a set of second nodes.

11. The indexing system of claim 2 further comprising a third copy of at least one of the set of second nodes.

12. A method for indexing data in an index tree, comprising:

providing an index tree with inner nodes, leaf nodes, redundant copies of the inner nodes, and redundant copies of the leaf nodes;

receiving a first data with a first index;

traversing the index tree to select one of the leaf nodes on which to store first data based at least on the first index;

storing the first data on the selected leaf node;

storing the first data on the redundant copy of the selected leaf node; and

traversing the inner nodes and redundant copies of the inner nodes that are parents of the selected leaf node to update metadata related to the inner nodes and the redundant copies of the inner nodes to reflect the stored first data.

13. The method of claim 12 further comprising storing the inner nodes, leaf nodes, redundant copies of the inner nodes, and redundant copies of the leaf nodes among a plurality of networked storage units.

14. The method of claim 13 further comprising selecting one of the inner nodes as a root node of the index tree.

15. The method of claim 14 further comprising storing on each of the plurality of networked storage units a first reference to the inner node selected as the root node and a second reference to the redundant copy of the selected inner node.

16. The method of claim 15 further comprising storing on each of the plurality of networked storage units a version value related to the index tree.

17. The method of claim 12, wherein the index tree is implemented using at least one of a balanced tree, a hash table, and a linked list.

18. The method of claim 12, wherein the redundant copies of the inner nodes includes at least one or more copies of the inner nodes, wherein the inner nodes may have a different number of redundant copies.

19. The method of claim 12, wherein the redundant copies of the leaf nodes includes at least one or more copies of the leaf nodes, wherein the leaf nodes may have a different number of redundant copies.

20. The method of claim 12, wherein the first data includes at least one of database records, physical addresses, and metadata.