Systems and methods for accessing and updating distributed data

• US 7,917,474 B2
• Filed: 10/21/2005
• Issued: 03/29/2011
• Est. Priority Date: 10/21/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Schack, Darren P., Passey, Aaron J., Godman, Peter J., Anderson, Robert J., Fachan, Neal T.
• Primary Examiner(s): Robinson; Greta L
• Assistant Examiner(s): Chang; Jeffrey
• Application Number:
  US11/255,337
• Publication Number:
  US 20070094310A1
• Time in Patent Office: 1,985 Days
• Field of Search: 707/102, 707/655
• US Class Current: 707/655
• 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 computer-implemented method of maintaining protection levels for nodes of a distributed mirrored indexed tree while modifying data stored in the nodes, the method comprising:

receiving a request to modify a target node of a mirrored index data structure organized in a hierarchy and stored among a plurality of storage devices, the mirrored index data structure comprising;

a root node;

at least one copy of the root node, wherein the root node and the copy of the root node are stored on different storage devices;

a plurality of nodes beneath the root node in the hierarchy, each of the nodes referencing one or more index nodes or indexed data, the plurality of nodes including the target node; and

at least one copy of each node of the plurality of nodes stored on one of the plurality of storage devices, wherein each node of the plurality of nodes and its respective copy are stored on different storage devices;

accessing, by a computer processor, a first reference to the target node and a second reference to a copy of the target node, the first reference and the second reference stored on a parent node of the target node, wherein the parent node is the root node or one of the plurality of nodes and is above the target node in the hierarchy, wherein the target node is stored on a first storage device of a plurality of storage devices, the copy of the target node is stored on a second storage device of the plurality of storage devices, the second storage device different from the first storage device;

determining, by a computer processor, whether the second storage device storing the copy of the target node is unavailable;

accessing, by a computer processor, the target node;

modifying, by a computer processor, the target node based on the request;

if the second storage device is unavailable, storing, by a computer processor, a copy of the modified target node on a third storage device of the plurality of storage devices, wherein the third storage device is available and is different from the first storage device and the second storage device, and updating, by a computer processor, the second reference; and

if the second storage device is available, updating, by a computer processor, the copy of the target node.

2. The computer-implemented method of claim 1 wherein updating the second reference comprises recursively applying, by a computer processor, the method of claim 1 to modify one or more references in one or more ancestor nodes of the target node, the ancestor nodes among the plurality of nodes, above the target node in the hierarchy, and including at least the parent node, one or more copies of the parent node, any grandparent nodes of the target node, and any copies of any grandparent nodes.

3. The computer-implemented method of claim 1 wherein updating the second reference comprises:

updating, by a computer processor, the parent node to reference the copy of the modified target node stored on the third storage device and to not reference the copy of the target node stored on the second storage device; and

updating, by a computer processor, any copies of the parent node to reference the copy of the modified target node stored on the third storage device and to not reference the copy of the target node stored on the second storage device.

4. The computer-implemented method of claim 3, further comprising:

determining, by a computer processor, that the parent node is the root node;

determining that a copy of the parent node is stored on an unavailable device;

storing a copy of the updated parent node on one of the plurality of storage devices that is available and that is different from the device on which the parent node is stored;

determining, by a computer processor, whether there is a quorum of available storage devices among the plurality of storage devices that are available; and

if there is a quorum, updating, by a computer processor, data stored on each of the plurality of devices to reference the copy of the updated parent node stored on the available third device and to not reference the copy of the parent node stored on the unavailable storage device.

5. The computer-implemented method of claim 1 wherein updating the second reference comprises recursively applying, by a computer processor, the method of claim 1 to modify one or more references in one or more ancestor nodes of the target node, the ancestor nodes among the plurality of nodes, above the target node in the hierarchy, and including at least the parent node, one or more copies of the parent node, any grandparent nodes of the target node, and any copies of any grandparent nodes, wherein the method of claim 1 is recursively applied, by a computer processor, to the one or more ancestor nodes of the target node until it is determined, by a computer processor, that the one or more ancestor nodes and each copy of the one or more ancestor nodes are stored on available storage devices.

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

15. The computer-implemented method of claim 3 wherein updating the second reference further comprises:

determining that a copy of the parent node is stored on an unavailable device;

storing a copy of the modified parent node on one of the plurality of devices that is available and that is different from the device on which the parent node is stored;

accessing a grandparent node of the target node, the grandparent node including references to the parent node and to the copy of the parent node;

modifying the grandparent node to reference the copy of the modified parent node instead of the copy of the parent node;

accessing a copy of the grandparent node, the copy of the grandparent node stored on a device that is different from the device on which the grandparent node is stored; and

modifying the copy of the grandparent node to reference the copy of the modified parent node instead of the copy of the parent node.

16. The computer-implemented method of claim 3 wherein updating the second reference further comprises:

determining that a copy of the parent node is stored on an unavailable device;

storing a copy of the modified parent node on one of the plurality of devices that is available and that is different from the device on which the parent node is stored;

accessing a grandparent node of the target node, the grandparent node including references to the parent node and to the copy of the parent node;

modifying the grandparent node to reference the copy of the modified parent node instead of the copy of the parent node;

determining that a copy of the grandparent node is stored on an unavailable device;

storing a copy of the modified grandparent node on one of the plurality of devices that is available and that is different from the device on which the grandparent node is stored;

accessing a root node of the target node, the root node including references to the grandparent node and to the copy of the grandparent node,

modifying the root node to reference the copy of the modified grandparent node instead of the copy of the grandparent node;

accessing a copy of the root node, the copy of the root node stored on a device that is different from the device on which the root node is stored;

modifying the copy of the root node to reference the copy of the modified grandparent node instead of the copy of the grandparent node.

17. The computer-implemented method of claim 3 wherein updating the second reference further comprises:

determining that a copy of the parent node is stored on an unavailable device;

storing a copy of the modified parent node on one of the plurality of devices that is available and that is different from the device on which the parent node is stored;

accessing a grandparent node of the target node, the grandparent node including references to the parent node and to the copy of the parent node;

modifying the grandparent node to reference the copy of the modified parent node instead of the copy of the parent node;

determining that a copy of the grandparent node is stored on an unavailable device;

storing a copy of the modified grandparent node on one of the plurality of devices that is available and that is different from the device on which the grandparent node is stored;

accessing a root node of the target node, the root node including references to the grandparent node and to the copy of the grandparent node,

modifying the root node to reference the copy of the of the copy of the modified grandparent node instead of the copy of the grandparent node;

determining that a copy of the root node is stored on an unavailable device; and

storing a copy of the modified root node on one of the plurality of devices that is available and that is different from the device on which the root node is stored,

accessing a superblock node of the target node, the superblock node including references to the root node and to the copy of the root node,

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

if there is a quorum, updating the superblock to reference the copy of the modified root node instead of the copy of the root node and storing an updated superblock version of the distributed mirrored index tree.

18. The computer-implemented method of claim 17 wherein updating the superblock further comprises instructing other devices in the plurality of devices to reference the copy of the modified root node instead of the copy of the root node and to store the updated superblock version of the distributed mirrored index tree.

19. A computer-readable storage device including a set of instructions that causes a computer to perform the method of computer-implemented method of claim 1.

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

accessing, by a computer processor, a first reference to a child node of a mirrored index data structure organized in a hierarchy and stored among a plurality of drives, the mirrored index data structure comprising;

a root node;

at least one copy of the root node, wherein the root node and the copy of the root node are stored on different drives;

a plurality of nodes beneath the root node in the hierarchy, each of the plurality of nodes referencing one or more index nodes or indexed data, the plurality of nodes including the child node; and

at least one copy of each node of the plurality of nodes stored on one of the plurality of drives, wherein each node of the plurality of nodes and its respective copy are stored on different drives;

accessing, by a computer processor, a second reference to a copy of the child node, the child node stored on a first drive of a plurality of drives and the copy of the child node stored on a different second drive of the plurality of drives, the first reference and the second reference stored in a parent node of the child node, wherein the parent node is the root node or one of the plurality of nodes and is above the child node in the hierarchy;

determining, by a computer processor, whether the second drive on which the copy of the child node is stored is unavailable; and

if the second drive is unavailable, storing, by a computer processor, a new copy of the child node on an available third drive of the plurality of drives, the third drive different than the first drive and the second drive, and updating, by a computer processor, the second reference.

8. The computer-implemented method of claim 7 wherein updating the second reference comprises recursively applying, by a computer processor, the method of claim 7 to modify one or more references in one or more ancestor nodes of the child node and to restore ancestor nodes of the child node and copies of the ancestor nodes of the child node which are stored on unavailable drives, the ancestor nodes among the plurality of nodes, above the child node in the hierarchy, and including at least the parent node, one or more copies of the parent node, any grandparent nodes of the child node, and any copies of the grandparent nodes.

9. The computer-implemented method of claim 7 further comprising:

accessing a third reference to a grandchild node stored on the plurality of drives and a fourth reference to a copy of the grandchild node stored on the plurality of drives, the grandchild node beneath the child node in the hierarchy and the copy of the grandchild node stored on different drives, the third reference and the fourth reference stored in the child node;

determining whether the drive on which the copy of the grandchild node is stored is unavailable; and

if the drive on which the copy of the grandchild node is stored is unavailable, storing a new copy of the grandchild node on an available drive of the plurality of drives, the new copy of the grandchild node and the grandchild node stored on different drives, and updating the fourth reference to reference the new copy of the grandchild node stored on the available drive instead of the copy of the grandchild node stored on the unavailable drive.

10. The computer-implemented method of claim 7 wherein the child node is an indexed node in a distributed mirrored index tree, the distributed mirrored index tree implemented as at least one of a balanced tree, a hash table, and a linked list.

20. A computer-readable storage device including a set of instructions that causes a computer to perform the method of computer-implemented method of claim 7.

11. A distributed system comprising:

a plurality of storage units;

a balanced, mirrored index tree stored among the plurality of storage units, the balanced, mirrored index tree organized in a hierarchy and comprising;

a root node stored on one of the plurality of storage units;

a copy of the root node stored on one of the plurality of storage units, wherein the root node and the copy of the root node are stored on different storage units;

a plurality of nodes beneath the root node in the hierarchy, each of the nodes stored on one of the plurality of storage units; and

a copy of each node of the plurality of nodes stored on one of the plurality of storage units, wherein each node of the plurality of nodes and its respective copy are stored on different storage units;

wherein each of the plurality of storage units comprises one or more memory devices, at least one executable software module stored on the one or more memory devices, a processor configured to execute the at least one executable software module, a first index tree reference referencing the root node and a second index tree reference referencing the copy of the root node, the first index tree reference and the second index tree reference stored on the one or more memory devices of each of the plurality of storage units, and

wherein the at least one executable software module comprises a modify module configured to;

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

determine that a copy of the target node is stored on an unavailable storage unit;

modify the target node;

store a copy of the modified target node on one of the plurality of storage units that is available and that is different from the storage unit that stores the target node; and

update a parent node of the target node to reference the copy of the modified target node instead of the copy of the target node, wherein the parent node is the root node or one of the plurality of nodes and is above the target node in the hierarchy.

12. The distributed system of claim 11, wherein the at least one executable software module further comprises a restore module configured to:

for each child node of the parent node,

determine that one copy of the child node is located on an unavailable storage unit;

retrieve the child node from an available storage unit;

initiate the storage of a new copy of the child node on an available storage unit that is different from the storage unit on which the child node is stored;

initiate the updating of the parent node and copies of the parent node to reference the new copy of the child node instead of the copy of the child node.

13. The distributed system of claim 11, the plurality of storage units further comprising a version value stored on the one or more memory devices, wherein the at least one executable software module further comprises a merge module configured to:

receive a first request from a first storage unit to merge into the plurality of storage units, the first storage unit 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 and determine which storage unit stores the highest version value;

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

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

update the first version value to be the same as the highest version value;

update the first index tree reference of the first storage unit to reference the same root node that is referenced by the first index tree reference of the storage unit storing the highest version value; and

update the second index tree reference of the first storage unit to reference the same copy of the root node that is referenced by the second index tree reference of the storage unit storing the highest version value.

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

21. The distributed system of claim 11, wherein the modify module is further configured to apply the modify module using the parent of the target node as the target node.

22. The distributed system of claim 12, wherein the restore module is further configured to apply the restore module using the parent of the parent node as the parent node.

23. The computer-implemented method of claim 11, wherein the plurality of nodes comprises leaf nodes comprising address data and inner nodes comprising references to leaf nodes or other inner nodes.