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

• US 8,392,368 B1
• Filed: 08/27/2010
• Issued: 03/05/2013
• 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): SYED, FARHAN M
• Application Number:
  US12/870,743
• Time in Patent Office: 921 Days
• Field of Search: None
• US Class Current: 707/634
• CPC Class Codes: G06F 16/182 Distributed file systems

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 system configured for distributed storage, the system comprising:

a plurality of storage nodes configured to store a plurality of files, wherein each storage node is configured to store at least a portion of one of the files; and

one or more client machines, wherein each client machine is configured to access the plurality of files stored across the plurality of storage nodes,

wherein each storage node and each client machine executes a software application to independently compute a mapping of the plurality of files to the plurality of storage nodes,

wherein, based on the mapping, any storage node and any client machine is able to access any portion of any file stored on any storage node, and

wherein, in response to a change to the plurality of storage nodes, each storage node and each client machine re-executes the software application to independently compute a new mapping of the plurality of files to the plurality of storage nodes, the change comprising;

a new storage node being added to the plurality of storage nodes, in which case at least a portion of one of the files is transferred to the new storage node for storage;

a storage node being removed from the plurality of storage nodes, in which case all portions of all files stored on the storage node being removed are transferred to one or more remaining storage nodes for storage; and

a new storage node being swapped for one storage node in the plurality of storage nodes in which case all portions of all files stored on the one storage node are transferred to the new storage node for storage.

2. The system of claim 1, wherein each storage node and each client machine stores an ordered list that includes each storage node in the plurality of storage nodes.

3. The system of claim 2, wherein each storage node and each client machine independently computes the mapping based on the ordered list.

4. The system of claim 1, wherein at least two machines comprising the plurality of storage nodes and the one or more client machines have different hardware architectures.

5. The system of claim 1, wherein the mapping of the plurality of files to the plurality of storage nodes independently computed by each storage node and each client machine is deterministic.

6. A computer-implemented method for computing a mapping of plurality of files to a plurality of storage nodes in a distributed storage system, the method comprising:

placing a plurality of buckets in a first partition, wherein each bucket stores at least a portion of at least one file in the plurality of files;

creating at least one new partition;

for each new partition;

computing a number of buckets to place in the new partition;

for the first partition;

determining a number of buckets to remove from the first partition and add to the new partition,

removing the number of buckets from the first partition, and

adding the number of buckets removed from the first partition to the new partition, and

for each other existing partition;

determining a number of buckets to remove from the existing partition and add to the new partition,

removing the number of buckets from the existing partition, and

adding the number of buckets removed from the existing partition to the new partition,

wherein the number of buckets removed from the first partition and each of the other existing partitions equals the number of buckets being placed in the new partition, and

wherein each partition is associated with at least one storage node and the mapping of the plurality of files to the plurality of storage nodes comprises a first mapping of the first partition and the at least one new partition to the plurality of storage nodes and a second mapping of the plurality of buckets to the first partition and the at least one new partition.

7. The method of claim 6, wherein each new partition comprises a set of segments, and each segment is comprised of one or more consecutive buckets in the plurality of buckets.

8. The method of claim 7, wherein a first existing partition includes a first segment, and the step of removing, with respect to the first existing partition, comprises dividing the first segment into a first portion and a second portion, the first portion including at least one of the buckets being removed from the first existing partition and added to the to the new partition.

9. The method of claim 6, wherein the number of buckets to be removed from a first existing partition is increased by one if the other existing partitions have fewer buckets than the first existing partition and decreased by one if the other existing partitions have more buckets than the first existing partition.

10. The method of claim 6, wherein the distributed file system includes a total number of partitions equal to the sum of the first partition and a total number of new partitions created, and wherein the total number of partitions is optimized for the distributed file system such that a minimum number of files needs to be moved when adding a storage node to the distributed file system or removing a storage node to the distributed file system.

11. The method of claim 10, wherein the total number of partitions equals a total number of storage nodes in the distributed file system.

18. The method of claim 6, wherein each client machine in the distributed storage system executes a software application to independently compute the mapping of the plurality of files to the plurality of storage nodes.

12. A computer-readable storage medium storing instructions that, when executed by a processing unit, cause the processing unit to map of plurality of files to a plurality of storage nodes in a distributed storage system, by performing the steps of:

placing a plurality of buckets in a first partition, wherein each bucket stores at least a portion of at least one file in the plurality of files;

creating at least one new partition;

for each new partition;

computing a number of buckets to place in the new partition;

for the first partition;

determining a number of buckets to remove from the first partition and add to the new partition,

removing the number of buckets from the first partition, and

adding the number of buckets removed from the first partition to the new partition, and

for each other existing partition;

determining a number of buckets to remove from the existing partition and add to the new partition,

removing the number of buckets from the existing partition, and

adding the number of buckets removed from the existing partition to the new partition,

wherein the number of buckets removed from the first partition and each of the other existing partitions equals the number of buckets being placed in the new partition, and

wherein each partition is associated with at least one storage node and the mapping of the plurality of files to the plurality of storage nodes comprises a first mapping of the first partition and the at least one new partition to the plurality of storage nodes and a second mapping of the plurality of buckets to the first partition and the at least one new partition.

13. The computer-readable storage medium of claim 12, wherein each new partition comprises a set of segments, and each segment is comprised of one or more consecutive buckets in the plurality of buckets.

14. The computer-readable storage medium of claim 13, wherein a first existing partition includes a first segment, and the step of removing, with respect to the first existing partition, comprises dividing the first segment into a first portion and a second portion, the first portion including at least one of the buckets being removed from the first existing partition and added to the to the new partition.

15. The computer-readable storage medium of claim 12, wherein the number of buckets to be removed from a first existing partition is increased by one if the other existing partitions have fewer buckets than the first existing partition and decreased by one if the other existing partitions have more buckets than the first existing partition.

16. The computer-readable storage medium of claim 12, wherein the distributed file system includes a total number of partitions equal to the sum of the first partition and a total number of new partitions created, and wherein the total number of partitions is optimized for the distributed file system such that a minimum number of files needs to be moved when adding a storage node to the distributed file system or removing a storage node to the distributed file system.

17. The computer-readable storage medium of claim 16, wherein the total number of partitions equals a total number of storage nodes in the distributed file system.

19. The computer-readable storage medium of claim 12, wherein each client machine in the distributed storage system executes a software application to independently compute the mapping of the plurality of files to the plurality of storage nodes.