System and method for distributing and accessing files in a distributed storage system

• US 8,290,919 B1
• Filed: 08/27/2010
• Issued: 10/16/2012
• Est. Priority Date: 08/27/2010
• Status: Active Grant

• Current Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Original Assignee: Disney Enterprises Incorporated (The Walt Disney Company)
• Inventors: Kelly, Sean A., Milne, Roger B.
• Primary Examiner(s): Fleurantin, Jean B
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US12/870,739
• Time in Patent Office: 781 Days
• Field of Search: 707/770, 707/966, 707/968, 707/E17.032, 707/E17.124, 707/E17.125, 707/698, 707/747, 707/E17.036, 707/E17.052, 709/203, 709/214, 709/215, 709/218, 714/6, 711/114, 711/118, 711/129, 711/152
• US Class Current: 707/698
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067

Abstract

A system and method for distributing and accessing files in a distributed storage system uses an ordered list of the storage nodes in the system to determine the storage node on which a file is stored. The distributed storage system includes a cluster of storage nodes and may also include one or more client nodes that participate in the system as storage resources. Each node (client and storage) stores an ordered list of the storage nodes in the system, allowing any of the nodes to access the file. The list is updated whenever a new storage node is added to the system, an existing storage node is removed from the system, or a new storage node is swapped with an existing storage node. Each one of the nodes may independently compute a new mapping of files to the storage nodes when the ordered list is changed.

Claims

1. A computer-implemented method for accessing files that are distributed across multiple storage nodes in a distributed storage system, the method comprising:

receiving an access request identifying a first distributed file having an associated filename;

determining, based on the filename, a bucket identifier corresponding to a first one of a plurality of buckets that contains the first distributed file, comprising;

upon determining that the filename is not associated with a predefined hash code;

computing a hash code using the filename; and

extracting the bucket identifier from a bit field of the computed hash code,

wherein each of the plurality of buckets maps to a respective one or more of a plurality of partitions containing the distributed files, and

wherein each of the plurality of partitions is stored across a respective one or more of the multiple storage nodes in the distributed storage system;

determining a first one or more partitions from the plurality of partitions that the first bucket maps to, wherein at least one of the first one or more partitions contains the first distributed file;

determining, based on a mapping of the first one or more partitions to the one or more storage nodes, a first storage node that stores the first distributed file; and

dispatching a request to the first storage node to access the first distributed file.

2. The method of claim 1, wherein the distributed files are read and written by a client node that is coupled to the multiple storage nodes and does not store any of the distributed files.

3. The method of claim 2, wherein each of the client node and the multiple storage nodes stores an ordered list of the storage nodes that is used to compute a mapping of the bucket and other buckets to the multiple storage nodes.

4. The method of claim 1, wherein the access request is received from a client node and the dispatching comprises:

determining that the access request is a write request; and

reading, by the first storage node, the first distributed file from the client node in response to the dispatched request.

5. The method of claim 4, further comprising the steps of:

determining, based on the mapping of the bucket to the multiple storage nodes, a second storage node that also stores the first distributed file;

dispatching the request to the second storage node; and

reading, by the second storage node, the first distributed file from the client node in response to the dispatched request.

6. The method of claim 5, wherein the dispatched request is multicast to the first storage node and the second storage node.

7. The method of claim 1, further comprising:

upon determining that the filename is associated with a second predefined hash code, extracting the bucket identifier from a bit field of the predefined hash code.

8. The method of claim 1, wherein the multiple storage nodes include one or more heterogeneous machines.

9. A system for accessing files that are distributed across multiple storage nodes in a distributed storage system, the system comprising:

a first storage node of the multiple storage nodes, the first storage node storing a first distributed file; and

a client node that is coupled to the multiple storage nodes and configured to;

receive an access request identifying a first distributed file having an associated filename;

determine, based on the filename, a bucket identifier corresponding to a first one of a plurality of buckets that contains the first distributed file, comprising;

upon determining that the filename is not associated with a predefined hash code;

compute a hash code using the filename; and

extract the bucket identifier from a bit field of the computed hash code,

wherein each of the plurality of buckets maps to a respective one or more of a plurality of partitions containing the distributed files, and

wherein each of the plurality of partitions is stored across a respective one or more of the multiple storage nodes in the distributed storage system;

determine a first one or more partitions from the plurality of partitions that the first bucket maps to, wherein at least one of the first one or more partitions contains the first distributed file;

determine, based on a mapping of the first one or more partitions to the one or more storage nodes, a first storage node that stores the first distributed file; and

dispatch a request to the first storage node to access the first distributed file.

10. The system of claim 9, wherein the client node is further configured to determine that the access request is a write request and the first storage node is configured to read the first distributed file from the client node in response to the dispatched request.

11. The system of claim 10, further comprising a second storage node that also stores the first distributed file, wherein the client node is further configured to:

determine, based on the mapping of the bucket to the multiple storage nodes, that the second storage node also stores the first distributed file; and

dispatch the request to the second storage node, and

the second storage node is configured to read the first distributed file from the client node in response to the dispatched request.

12. The system of claim 11, wherein the dispatched request is multicast to the first storage node and the second storage node.

13. The system of claim 9, further comprising:

upon determining that the filename is associated with a second predefined hash code, extracting the bucket identifier from a bit field of the predefined hash code.

14. The system of claim 9, wherein the multiple storage nodes include one or more heterogeneous machines.

15. The system of claim 9, wherein each of the client node and the multiple storage nodes stores an ordered list of the storage nodes that is used to compute the mapping of the bucket and other buckets to the multiple storage nodes.

16. A computer-readable storage medium storing instructions that, when executed by a processor, cause a computer system to access files that are distributed across multiple storage nodes in a distributed storage system, by performing the steps of:

receiving an access request identifying a first distributed file having an associated filename;

determining, based on the filename, a bucket identifier corresponding to a first one of a plurality of buckets that contains the first distributed file, comprising;

upon determining that the filename is not associated with a predefined hash code;

computing a hash code using the filename; and

extracting the bucket identifier from a bit field of the computed hash code,

wherein each of the plurality of buckets maps to a respective one or more of a plurality of partitions containing the distributed files, and

wherein each of the plurality of partitions is stored across a respective one or more of the multiple storage nodes in the distributed storage system;

determining a first one or more partitions from the plurality of partitions that the first bucket maps to, wherein at least one of the first one or more partitions contains the first distributed file;

determining, based on a mapping of the first one or more partitions to the one or more storage nodes, a first storage node that stores the first distributed file; and

dispatching a request to the first storage node to access the first distributed file.

17. The computer-readable storage medium of claim 16, wherein the access request is received from a client node and the dispatching comprises:

determining that the access request is a write request; and

reading, by the first storage node, the first distributed file from the client node in response to the dispatched request.

18. The computer-readable storage medium of claim 17, further comprising the steps of:

determining, based on the mapping of the bucket to the multiple storage nodes, a second storage node that also stores the first distributed file;

dispatching the request to the second storage node; and

reading, by the second storage node, the first distributed file from the client node in response to the dispatched request.