Systems and methods for accessing and updating distributed data

• US 8,176,013 B2
• Filed: 12/10/2010
• Issued: 05/08/2012
• 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: Passey, Aaron J., Schack, Darren P., Godman, Peter J., Anderson, Robert J., Fachan, Neal T.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Chang, Jeffrey
• Application Number:
  US12/965,748
• Publication Number:
  US 20110145195A1
• Time in Patent Office: 515 Days
• Field of Search: 707/656
• US Class Current: 707/656
• 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 merging a first storage device into a plurality of storage devices, the method comprising:

querying, by a processor of a first storage device of a plurality of storage devices, the other storage devices for an indication as to the current version of one or more portions of a mirrored index data structure, the mirrored index data structure stored across the storage devices and comprising;

a plurality of nodes 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 of the plurality of distributed storage devices;

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

at least one copy of each child node of the plurality of child nodes, wherein each child node of the plurality of child nodes and its respective copy are stored on different storage devices of the plurality of storage devices, wherein the root node and the plurality of child nodes form a first index tree and the at least one copy of the root node and the at least one copy of each child node form at least one mirror copy of the first index tree;

determining, by a processor of the first storage device and based on the indication as to the current version, whether the first storage device is storing the current version of the one or more portions;

if the first storage device is not storing the current version of the one or more portions, updating the first storage device to store the current version of the one or more portions; and

removing from the first storage device one or more nodes of the plurality of nodes which are not referenced by the current version of the one or more portions but are stored on the first storage device.

2. The method of claim 1, further comprising, before the querying, determining that the first storage device has become available, wherein the first storage device was previously unavailable.

3. The method of claim 1, wherein the one or more portions comprise references to one or more of the root node and the at least one copy of the root node.

4. The method of claim 1, wherein the indication as to the current version comprises version values for each of the plurality of queried storage devices, the version values representing versions of the one or more portions of the mirrored index data structure stored on the respective queried storage devices.

5. The method of claim 4, wherein the determining further comprises determining a highest version value of the version values of the queried storage devices and determining whether the version value of the first storage device is lower than the highest version value.

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

7. The method of claim 5, further comprising, if the first storage device is not storing the current version of the one or more portions of the mirrored index data structure, updating the version value of the first storage device to the highest version value.

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

9. The method of claim 1, further comprising, by a processor of at least one of the other storage devices:

receiving a request to modify a target node of the plurality of nodes;

determining that a copy of the target node is stored on the first storage device and that the first storage device is currently unavailable;

modifying the target node;

creating a new copy of the target node; and

storing the new copy of the target node on at least one of the plurality of storage devices that is available.

10. The method of claim 1, wherein the mirrored index data structure stores addresses of metadata data structures of files and directories in a distributed file system and maps identifiers for the files and directories to their respective addresses.

11. A storage system comprising:

a plurality of storage devices each comprising storage and at least one processor;

a mirrored index data structure stored across the storage devices and comprising;

a plurality of nodes 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 of the plurality of storage devices;

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

at least one copy of each child node of the plurality of child nodes, wherein each child node of the plurality of nodes and its respective copy are stored on different storage devices of the plurality of storage devices, wherein the root node and the plurality of child nodes form a first index tree and the at least one copy of the root node and the at least one copy of each child node form at least one mirror copy of the first index tree;

wherein at least a first storage device of the storage devices comprises a merge module executable by the at least one processor of the respective storage device and configured to;

query the other storage devices for an indication as to the current version of one or more portions of a mirrored index data structure;

determine, based on the indication as to the current version, whether the first storage device is storing the current version of the one or more portions;

if the first storage device is not storing the current version of the one or more portions, update the first storage device to store the current version of the one or more portions; and

remove from the first storage device one or more nodes of the plurality of nodes which are not referenced by the current version of the one or more portions but are stored on the first storage device.

12. The storage system of claim 11, wherein the merge module is further configured to, before querying the other storage devices, determine that the first storage device has become available, wherein the first storage device was previously unavailable.

13. The storage system of claim 11, wherein the one or more portions comprise references to one or more of the root node and the at least one copy of the root node.

14. The storage system of claim 11, wherein the indication as to the current version comprises version values for each of the plurality of queried storage devices, the version values representing versions of the one or more portions of the mirrored index data structure stored on the respective queried storage devices.

15. The storage system of claim 14, wherein the merge module determines whether the first storage device is storing the current version at least in part by determining a highest version value of the version values of the queried storage devices and determining whether the version value of the first storage device is lower than the highest version value.

16. The storage system of claim 15, wherein the merge module determines the highest version value at least in part by calculating the highest version value for which there is a quorum of the plurality of storage devices with that version value.

17. The storage system of claim 15, wherein, if the first storage device is not storing the current version of the one or more portions, the merge module is further configured to update the version value of the first storage device to the highest version value.

18. The storage system of claim 11, wherein the mirrored index data structure is implemented as at least one of a balanced tree, a hash table, and a linked list.

19. The storage system of claim 11, wherein each of the storage devices is further configured to:

receive a request to modify a target node of the plurality of nodes;

determine that a copy of the target node is stored on the first storage device and that the first storage device is currently unavailable;

modify the target node;

create a new copy of the target node; and

store the new copy of the target node on at least one of the plurality of storage devices that is available.

20. The method of claim 11, wherein the mirrored index data structure stores addresses of metadata data structures of files and directories in a distributed file system and maps identifiers for the files and directories to their respective addresses.