Systems and methods for accessing and updating distributed data

• US 20070094310A1
• 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: Anderson, Robert, Schack, Darren, Godman, Peter, Fachan, Neal, Passey, Aaron
• Granted Patent: US 7,917,474 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• 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. A method of modifying nodes stored on distributed indexed tree, the method comprising:

receiving a target node, wherein the target node and a copy of the target node are stored among a plurality of devices;

accessing a parent node of the target node;

determining that the copy of the target node is stored on a failed device of the plurality of devices;

modifying the target node;

creating a new copy of the target node;

storing the new copy of the target node on at least one of the plurality of devices that is not a failed device; and

recursively updating the parent node.

2. The method of claim 1 wherein recursively updating the parent node comprises:

modifying reference data of the parent node using the method of claim 1.

3. The method of claim 1 wherein recursively updating the parent node comprises:

updating the parent node to reference the new copy of the target node instead of the copy of the target node; and

updating copies of the parent node to reference the new copy of the target node instead of the copy of the target node.

4. The method of claim 1, wherein updating the parent node comprises:

determining whether the target node is a root node; and

if the target node is a root node,

determining whether there is a quorum among the plurality of devices that are not failed devices;

if there is a quorum, updating data stored on each of the plurality of devices to reference the new copy of the root node.

5. The method of claim 1 wherein the parent node and the target node are part of a distributed index tree.

6. The method of claim 5 wherein the distributed index tree is implemented as at least one of a balanced tree, a hash table, and a linked list.

7. A method of restoring mirrored nodes of a distributed indexed tree, the method comprising:

receiving a parent node;

for each child of the parent node,

determining that at least one copy of the child is located on a failed drive;

retrieving a copy of the child from a non-failed drive;

creating a new copy of the child;

storing the new copy of the child on a non-failed drive;

updating the parent and copies of the parent to reference the new copy of the child; and

recursively restoring the child.

8. The method of claim 7 wherein recursively restoring the child comprises:

restoring the child node using the method of claim 7.

9. The method of claim 7 wherein updating the parent and the copies of the parent to reference the new copy of the child comprises:

determining that the new copy of the child is a copy of the root node;

determining that there is a quorum of non-failed drives within a plurality of drives;

updating data on each of the non-failed drives to reference the new copy of the root node and to reflect a new version number.

10. The method of claim 7 wherein the parent node and the target node are part of a distributed index tree.

11. The method of claim 10 wherein the distributed index tree is implemented as at least one of a balanced tree, a hash table, and a linked list.

12. A method of merging a first device into a plurality of devices, the method comprising:

providing a first device configured to store a version value;

providing a plurality of devices, each of the plurality of devices configured to reference at least two copies of a mirrored index data structure and to store a version value

receiving the first version value;

querying the plurality of devices for their corresponding version values;

determining a highest version value from the version values;

determining whether the first version value is lower than the highest version value;

if the first version value is lower than the highest version value,

updating the version value of the first device to the highest version value; and

updating the first device to reference the at least two copies of the mirrored index data structure.

13. The method of claim 12, wherein determining a highest version includes calculating the highest version value for which there is a quorum of the plurality of devices with that version value.

14. The method of claim 12 wherein the mirrored index data structure is implemented as at least one of a balanced tree, a hash table, and a linked list.

15. The method of claim 12 wherein the version values are represented as a number.

16. A distributed system comprising:

a plurality of storage units;

a balanced index tree configured to be organized by index values comprising a root node, a copy of the root node, a plurality of nodes, and a copy of the plurality of nodes;

a storage module configured to store the root node, the copy of the root node, the plurality of nodes, and the copy of the plurality of nodes stored among the plurality of storage units; and

index tree data stored on each of the plurality of storage units referencing the root node and the copy of the root node.

17. The distributed system of claim 16 further comprising:

a modify module configured to;

receive a target node of the plurality of nodes to be modified;

accessing a parent node of the target node;

determine that a copy of the target node is stored on a disconnected storage of the plurality of storage units;

modify the target node;

create a new copy of the target node;

store the new copy of the target node on at least one of the plurality of storage units that is not a disconnected storage unit; and

recursively update the parent node to reference the new copy of the target node.

18. The distributed system of claim 16 further comprising:

a restore module configured to;

receive a parent node;

for each child of the parent node,

determine that at least one copy of the child is located on a failed drive;

retrieve a copy of the child from a non-failed drive;

create a new copy of the child;

store the new copy of the child on a non-failed drive;

update the parent and copies of the parent to reference the new copy of the child; and

recursively restore the child.

19. The distributed system of claim 16 wherein each of the plurality of storage units is configured to store a version value, further comprising:

a merge module configured to;

receive a first request from a first storage unit to merge into the plurality of storage units, the first device configured to store a first version value;

query the plurality of storage units for their corresponding version values;

determine a highest version value from the version values;

determine whether the first version value is lower than the highest version value;

if the first version value is lower than the highest version value,

updating the first version value to the highest version value; and

updating the first device to reference the root node and the copy of the root node referenced by the plurality of storage units.

20. The method of claim 16 wherein the balanced index tree is implemented as at least one of a balanced tree, a hash table, and a linked list.