Systems and methods for maintaining distributed data

• US 8,214,400 B2
• Filed: 08/24/2010
• Issued: 07/03/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: Fachan, Neal T., Passey, Aaron J., Schack, Darren P.
• Primary Examiner(s): Shmatov, Alexey
• Application Number:
  US12/862,060
• Publication Number:
  US 20110035412A1
• Time in Patent Office: 679 Days
• Field of Search: 707/999.103, 707/655, 707/787, 707/793, 707/797
• US Class Current: 707/793
• 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 accessing a data unit stored at a leaf node of a distributed index tree, the method comprising:

using a reference from a superblock to access an available copy of a root node, copies of the root node stored on different devices among a plurality of storage devices, each copy of the root node comprising a first reference to a first copy of a branch of the distributed index tree and a second reference to a second copy of the branch, wherein the branch leads to one or more copies of a parent node;

accessing, by a computer processor, an available copy of the parent node, copies of the parent node stored on different devices among the plurality of storage devices, each copy of the parent node comprising a first electronic reference to a first copy of a leaf node stored on a first storage device, a second electronic reference to a second copy of the leaf node stored on a second storage device, and a third electronic reference to a third copy of the leaf node stored on a third storage device, the first storage device different from the second storage device;

determining, by a computer processor, that the first storage device is unavailable;

based on the determination that the first storage device is unavailable, choosing to access the second copy of the child node instead of the third copy of the child node based on a technique including at least one of a round robin technique based on the last storage device used, selecting a most recently used storage device, and choosing based on a preference of local storage devices over remote storage devices; and

processing, by a computer processor, the second electronic reference to access the second copy of the leaf node stored on the second storage device.

2. The computer-implemented method of claim 1, further comprising:

maintaining at least as many copies of the parent node as the maximum number of copies of any of its one or more children, wherein the one or more children of the parent node include the leaf node.

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

creating a third copy of the leaf node;

storing the third copy of the leaf node on a third storage device which is different than the first storage device and the second storage device; and

modifying each available copy of the parent node to include a reference to the third copy of the leaf node stored on the third storage device.

4. The computer-implemented method of claim 1, further comprising determining that a first copy of the parent node is stored on an unavailable device, and wherein accessing the available copy of the parent node comprises using a reference to a second copy of the parent node, the reference stored in a parent of the parent node.

5. The computer-implemented method of claim 1, further comprising maintaining a copy of the superblock on each of the plurality of storage devices.

6. The computer-implemented method of claim 5, further comprising maintaining an indication of a version of the superblock on each of the plurality of storage devices.

7. The computer-implemented method of claim 1, wherein the parent node and the leaf node each comprise one or more keys, and the data unit is associated with an index which corresponds to one of the one or more keys of the leaf node.

8. The computer-implemented method of claim 1, wherein the parent node is the root node.

9. The computer-implemented method of claim 1, wherein the data unit comprises a physical address.

10. The computer-implemented method of claim 1, wherein the data unit comprises at least one of a database record, a physical address, content data, and metadata.

11. The computer-implemented method of claim 1, wherein the distributed indexed tree is implemented using at least one of a balanced tree, a hash table and a linked list.

12. A system for accessing a data unit stored in a distributed index tree comprising:

one or more computer processors;

at least one computer memory accessible by at least one of the one or more computer processors; and

a computing component comprising an executable software module executed by the one or more computer processors, wherein the computing component is operable to;

use a reference from a superblock to access an available copy of a root node, copies of the root node stored on different devices among a plurality of storage devices, each copy of the root node comprising a first reference to a first copy of a branch of the distributed index tree and a second reference to a second copy of the branch, wherein the branch leads to one or more copies of a parent node;

access an available copy of the parent node, copies of the parent node stored on different devices among the plurality of storage devices, each copy of the parent node comprising a first electronic reference to a first copy of a leaf node stored on a first storage device, a second electronic reference to a second copy of the leaf node stored on a second storage device, and a third electronic reference to a third copy of the leaf node stored on a third storage device, the first storage device different from the second storage device;

determine that the first storage device is unavailable;

based on the determination that the first storage device is unavailable, choose to access the second copy of the child node instead of the third copy of the child node based on a technique including at least one of a round robin technique based on the last storage device used, selecting a most recently used storage device, and choosing based on a preference of local storage devices over remote storage devices; and

process the second electronic reference to access the second copy of the leaf node stored on the second storage device.

13. The system of claim 12, wherein the computing component is further operable to maintain at least as many copies of the parent node as the maximum number of copies of any of its one or more children, wherein the one or more children of the parent node include the leaf node.

14. The system of claim 12, wherein the computing component is further operable to:

create a third copy of the leaf node;

store the third copy of the leaf node on a third storage device which is different than the first storage device and the second storage device; and

modify each available copy of the parent node to include a reference to the third copy of the leaf node stored on the third storage device.

15. The system of claim 12, wherein the computing component is further operable to determine that a first copy of the parent node is stored on an unavailable device, and wherein accessing the available copy of the parent node comprises using a reference to a second copy of the parent node, the reference stored in a parent of the parent node.

16. The system of claim 12, wherein the computing component is further operable to maintain a copy of the superblock on each of the plurality of storage devices.

17. The system of claim 16, wherein the computing component is further operable to maintain an indication of a version of the superblock on each of the plurality of storage devices.

18. The system of claim 12, wherein the parent node and the leaf node each comprise one or more keys, and the data unit is associated with an index which corresponds to one of the one or more keys of the leaf node.

19. The system of claim 12, wherein the parent node is the root node.

20. The system of claim 12, wherein the data unit comprises at least one of a database record, a physical address, content data, and metadata.