Systems and methods for maintaining distributed data

• US 7,797,283 B2
• Filed: 10/21/2005
• Issued: 09/14/2010
• 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., Fachan, Neal T.
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Shmatov; Alexey
• Application Number:
  US11/255,818
• Publication Number:
  US 20070094277A1
• Time in Patent Office: 1,789 Days
• Field of Search: 707/103.R, 707/8, 707/999.103, 707/999.008, 707/655
• US Class Current: 707/655
• 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 distributed storage system storing a distributed tree structure, comprising:

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

a tree structure stored as nodes across two or more of the plurality of storage devices, the tree structure comprising;

a first leaf node comprising a first record identified by a first key, the first leaf node stored on one of the plurality of storage devices, the first record stored on one of the plurality of storage devices;

at least one copy of the first leaf node comprising a copy of the first record identified by the first key, the at least one copy of the first leaf node stored on one of the plurality of storage devices that is different from the storage device storing the first leaf node;

a second leaf node comprising a second record identified by a second key, the second leaf node stored on one of the plurality of storage devices, the second record stored on one of the plurality of storage devices;

one or more copies of the second leaf node, the one or more copies of the second leaf node comprising a different number of copies than the at least one copy of the first leaf node, each of the one or more copies of the second leaf node comprising a copy of the second record identified by the second key, each of the one or more copies of the second leaf node stored on one of the plurality of storage devices that is different from the storage device storing the second leaf node;

a parent node referencing the first leaf node, the at least one copy of the first leaf node, the second leaf node, and the one or more copies of the second leaf node, the parent node stored on one of the plurality of storage devices;

at least one copy of the parent node referencing the first leaf node, the at least one copy of the first leaf node, the second leaf node, and the one or more copies of the second leaf node, the at least one copy of the parent node stored on one of the plurality of storage devices that is different from the storage device storing the parent node;

a grandparent node referencing the parent node and the at least one copy of the parent node, the grandparent node stored on one of the plurality of storage devices;

at least one copy of the grandparent node referencing the parent node and the at least one copy of the parent node, the at least one copy of the grandparent node stored on one of the plurality of storage devices that is different from the storage device storing the grandparent node; and

the grandparent node, the at least one copy of the grandparent node, the parent node, and the at least one copy of the parent node configured to index the first leaf node and the at least one copy of the first leaf node based on the first key and the second leaf node and the one or more copies of the second leaf node based on the second key; and

an index management module in communication with the plurality of storage devices, the index management module configured to run on a processor and to;

maintain at least as many copies of the parent node as the maximum number of copies of any of its children nodes, its children nodes including the first leaf node and the second leaf node;

maintain at least as many copies of the grandparent node as the maximum number of copies of any of its children nodes, its children nodes including the parent node; and

traverse the tree structure, using a copy of the first leaf node if the first leaf node is unavailable, using a copy of the parent node if the parent node is unavailable, and using a copy of the grandparent node if the grandparent node is unavailable.

2. The distributed storage system of claim 1, the index management module further configured to store a superblock on each storage device in the plurality of storage devices, each superblock referencing the tree structure.

3. The distributed storage system of claim 1, the tree structure further comprising a root node and at least as many copies of the root node as the maximum number of copies of any of the root node'"'"'s descendants, the root node stored on a different storage device than the storage devices storing the copies of the root node.

4. The distributed storage system of claim 1, the tree structure further comprising a version value.

5. The distributed storage system of claim 1, the tree structure further comprising:

a root node referencing the grandparent node and the copy of the grandparent node, the root node stored on one of the plurality of storage devices;

a copy of the root node referencing the grandparent node and the copy of the grandparent node, the copy of the root node stored on one of the plurality of storage devices that is different from the storage device storing the root node; and

the root node and the copy of the root node configured to index the first leaf node and the at least one copy of the first leaf node based on the first key, and the second leaf node and the one or more copies of the second leaf node based on the second key.

6. A computer-implemented method for storing a distributed tree structure, comprising:

providing, by a processor, a tree structure stored as nodes across two or more of a plurality of storage devices, the tree structure comprising;

a first leaf node comprising a first record identified by a first key, the first leaf node stored on one of the plurality of storage devices, the first record stored on one of the plurality of storage devices;

at least one copy of the first leaf node comprising a copy of the first record identified by the first key, the at least one copy of the first leaf node stored on one of the plurality of storage devices that is different from the storage device storing the first leaf node;

a second leaf node comprising a second record identified by a second key, the second leaf node stored on one of the plurality of storage devices, the second record stored on one of the plurality of storage devices;

one or more copies of the second leaf node, the one or more copies of the second leaf node comprising a different number of copies than the at least one copy of the first leaf node, each of the one or more copies of the second leaf node comprising a copy of the second record identified by the second key, each of the one or more copies of the second leaf node stored on one of the plurality of storage devices that is different from the storage device storing the second leaf node;

a parent node referencing the first leaf node, the at least one copy of the first leaf node, the second leaf node, and the one or more copies of the second leaf node, the parent node stored on one of the plurality of storage devices;

at least one copy of the parent node referencing the first leaf node, the at least one copy of the first leaf node, the second leaf node, and the one or more copies of the second leaf node, the at least one copy of the parent node stored on one of the plurality of storage devices that is different from the storage device storing the parent node;

a grandparent node referencing the parent node and the at least one copy of the parent node, the grandparent node stored on one of the plurality of storage devices;

at least one copy of the grandparent node referencing the parent node and the at least one copy of the parent node, the at least one copy of the grandparent node stored on one of the plurality of storage devices that is different from the storage device storing the grandparent node; and

the grandparent node, the at least one copy of the grandparent node, the parent node, and the at least one copy of the parent node configured to index the first leaf node and the at least one copy of the first leaf node based on the first key and the second leaf node and the one or more copies of the second leaf node based on the second key; and

maintaining, by a processor, at least as many copies of the parent node as the maximum number of copies of any of its children nodes, its children nodes including the first leaf node and the second leaf node;

maintaining, by a processor, at least as many copies of the grandparent node as the maximum number of copies of any of its children nodes, its children nodes including the parent node; and

traversing, by a processor, the tree structure, using a copy of the first leaf node if the first leaf node is unavailable, using a copy of the parent node if the parent node is unavailable, and using a copy of the grandparent node if the grandparent node is unavailable.

7. The computer-implemented method of claim 6, further comprising storing a superblock on each storage device in the plurality of storage devices, each superblock referencing the tree structure.

8. The computer-implemented method of claim 6, wherein the tree structure further comprises a root node and at least as many copies of the root node as the maximum number of copies of any of the root node'"'"'s descendants, the root node stored on a different storage device than the storage devices storing the copies of the root node.

9. The computer-implemented method of claim 6, wherein the tree structure further comprises a version value.

10. The computer-implemented method of claim 6, wherein the tree structure further comprises:

a root node referencing the grandparent node and the copy of the grandparent node, the root node stored on one of the plurality of storage devices;

a copy of the root node referencing the grandparent node and the copy of the grandparent node, the copy of the root node stored on one of the plurality of storage devices that is different from the storage device storing the root node; and

the root node and the copy of the root node configured to index the first leaf node and the at least one copy of the first leaf node based on the first key, and the second leaf node and the one or more copies of the second leaf node based on the second key.

11. A computer-readable storage medium having instructions stored thereon for implementing, when the instructions are executed, a distributed tree structure, the instructions comprising:

providing a tree structure stored as nodes across two or more of a plurality of storage devices, the tree structure comprising;

a first leaf node comprising a first record identified by a first key, the first leaf node stored on one of the plurality of storage devices, the first record stored on one of the plurality of storage devices;

at least one copy of the first leaf node comprising a copy of the first record identified by the first key, the at least one copy of the first leaf node stored on one of the plurality of storage devices that is different from the storage device storing the first leaf node;

a second leaf node comprising a second record identified by a second key, the second leaf node stored on one of the plurality of storage devices, the second record stored on one of the plurality of storage devices;

one or more copies of the second leaf node, the one or more copies of the second leaf node comprising a different number of copies than the at least one copy of the first leaf node, each of the one or more copies of the second leaf node comprising a copy of the second record identified by the second key, each of the one or more copies of the second leaf node stored on one of the plurality of storage devices that is different from the storage device storing the second leaf node;

a parent node referencing the first leaf node, the at least one copy of the first leaf node, the second leaf node, and the one or more copies of the second leaf node, the parent node stored on one of the plurality of storage devices;

at least one copy of the parent node referencing the first leaf node, the at least one copy of the first leaf node, the second leaf node, and the one or more copies of the second leaf node, the at least one copy of the parent node stored on one of the plurality of storage devices that is different from the storage device storing the parent node;

a grandparent node referencing the parent node and the at least one copy of the parent node, the grandparent node stored on one of the plurality of storage devices;

at least one copy of the grandparent node referencing the parent node and the at least one copy of the parent node, the at least one copy of the grandparent node stored on one of the plurality of storage devices that is different from the storage device storing the grandparent node; and

the grandparent node, the at least one copy of the grandparent node, the parent node, and the at least one copy of the parent node configured to index the first leaf node and the at least one copy of the first leaf node based on the first key and the second leaf node and the one or more copies of the second leaf node based on the second key; and

maintaining at least as many copies of the parent node as the maximum number of copies of any of its children nodes, its children nodes including the first leaf node and the second leaf node;

maintaining at least as many copies of the grandparent node as the maximum number of copies of any of its children nodes, its children nodes including the parent node; and

traversing the tree structure, using a copy of the first leaf node if the first leaf node is unavailable, using a copy of the parent node if the parent node is unavailable, and using a copy of the grandparent node if the grandparent node is unavailable.

12. The computer-readable storage medium of claim 11, the instructions further comprising storing a superblock on each storage device in the plurality of storage devices, each superblock referencing the tree structure.

13. The computer-readable storage medium of claim 11, wherein the tree structure further comprises a root node and at least as many copies of the root node as the maximum number of copies of any of the root node'"'"'s descendants, the root node stored on a different storage device than the storage devices storing the copies of the root node.

14. The computer-readable storage medium of claim 11, wherein the tree structure further comprises a version value.

15. The computer-readable storage medium of claim 11, wherein the tree structure further comprises:

a root node referencing the grandparent node and the copy of the grandparent node, the root node stored on one of the plurality of storage devices;

a copy of the root node referencing the grandparent node and the copy of the grandparent node, the copy of the root node stored on one of the plurality of storage devices that is different from the storage device storing the root node; and

the root node and the copy of the root node configured to index the first leaf node and the at least one copy of the first leaf node based on the first key, and the second leaf node and the one or more copies of the second leaf node based on the second key.