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

• US 8,768,981 B1
• Filed: 08/27/2010
• Issued: 07/01/2014
• 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: Milne, Roger B., Kelly, Sean A.
• Primary Examiner(s): LE, THU NGUYET T
• Application Number:
  US12/870,734
• Time in Patent Office: 1,404 Days
• Field of Search: 707822-831, 707/966, 707/999.101, 707/999.102
• US Class Current: 707/822
• 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 computer-implemented method to distribute files across multiple heterogeneous storage nodes without using a centralized server in a distributed storage system, the method comprising:

computing a first mapping of buckets to partitions using a first deterministic function applied to an ordered list of the storage nodes, wherein each bucket stores at least a portion of the files, and at least one of the partitions is fragmented in bucket space, wherein a number of buckets mapped to each partition is based on a ratio of a number of existing buckets to a number of existing partitions in the distributed storage system;

computing, using a second deterministic function applied to the ordered list of the storage nodes, a second mapping of the partitions to the multiple storage nodes, wherein each partition is mapped to two or more of the multiple storage nodes based on a predefined redundancy value;

combining the first mapping with the second mapping to produce a third mapping of the buckets to the multiple storage nodes; and

storing the files across the multiple storage nodes in the distributed storage system according to the third mapping, wherein the ordered list of storage nodes is stored by each of;

(i) a plurality of client nodes, and (ii) each of the multiple storage nodes.

2. The method of claim 1, wherein each of the plurality of client nodes and the multiple storage nodes uses the ordered list of the storage nodes to determine which of the multiple storage nodes a requested file resides on, wherein the distributed storage system employs a pull architecture, and not a push architecture, to satisfy local file system operations.

3. The method of claim 2, further comprising:

adding a new storage node to the distributed storage system;

adding the new storage node to the end of the ordered list of the storage nodes; and

transferring a portion of the distributed files stored on each one of the multiple storage nodes to the new storage node.

4. The method of claim 3, further comprising:

recomputing the first mapping of the buckets to the partitions;

recomputing the second mapping of the partitions to the multiple storage nodes; and

combining the recomputed first mapping with the recomputed second mapping to produce a recomputed third mapping of the buckets to the multiple storage nodes, wherein the transferring of the portion of the distributed files stored on each one of the multiple storage nodes is performed according to the recomputed third mapping, wherein a number of buckets extracted from each of the multiple storage nodes is based on the number of existing buckets divided by the number of existing partitions.

5. The method of claim 2, further comprising:

removing an existing storage node from the distributed storage system;

removing the existing storage node from the end of the ordered list of the storage nodes; and

transferring different portions of the distributed files stored on the existing storage node to each one of the multiple storage nodes.

6. The method of claim 5, further comprising:

recomputing the first mapping of the buckets to the partitions;

recomputing the second mapping of the partitions to the multiple storage nodes; and

combining the recomputed first mapping with the recomputed second mapping to produce a recomputed third mapping of the buckets to the multiple storage nodes, wherein the transferring of the different portions of the distributed files stored on the existing storage node is performed according to the recomputed third mapping.

7. The method of claim 2, further comprising:

swapping an existing storage node in the distributed storage system with a new storage node;

replacing the existing storage node in the ordered list of the storage nodes with the new storage node; and

transferring a portion of the distributed files that are stored on the existing storage node to the new storage node.

8. The method of claim 2, wherein the buckets are indirectly mapped to the storage nodes through the partitions, wherein the buckets are mapped to contiguous partitions when a single partition and when two partitions are used, wherein the buckets are mapped to a greater number of fragmented partitions as a number of partitions increases.

9. The method of claim 8, wherein the first deterministic function iteratively distributes the buckets substantially evenly between the partitions, wherein an amount of redistribution of files in the event of a configuration update is reduced by mapping the buckets to the partitions, thereby facilitating scaling of the distributed storage system up and down in size in respective instances and in a manner more efficient than a second distributed storage system in which the buckets are mapped to the nodes and not mapped to the partitions, wherein approximately a number of buckets equaling one divided by the number of partitions are mapped to each of the partitions.

10. A system method to distribute files across multiple heterogeneous storage nodes without using a centralized server in a distributed storage system, the system comprising:

one or more computer processors; and

a memory containing a program, which, when executed by the one or more computer processors performs an operation, the operation comprising;

computing a first mapping of buckets to partitions using a first deterministic function applied to an ordered list of the storage nodes, wherein each bucket stores at least a portion of the files, and at least one of the partitions is fragmented in bucket space, wherein a number of buckets mapped to each partition is based on a ratio of a number of existing buckets to a number of existing partitions in the distributed storage system;

computing, using a second deterministic function applied to the ordered list of storage nodes, a second mapping of the partitions to the multiple storage nodes, wherein each partition is mapped to two or more of the multiple storage nodes based on a predefined redundancy value;

combining the first mapping with the second mapping to produce a third mapping of the buckets to the multiple storage nodes; and

storing the files across the multiple storage nodes in the distributed storage system according to the third mapping, wherein the ordered list of storage nodes is stored by each of;

(i) a plurality of client nodes, and (ii) each of the multiple storage nodes.

11. The system of claim 10, wherein each of the plurality of client nodes and the multiple storage nodes uses the ordered list of the storage nodes to determine which of the multiple storage nodes a requested file resides on, wherein the buckets are indirectly mapped to the storage nodes through the partitions, wherein the buckets are mapped to contiguous partitions when a single partition and when two partitions are used, wherein the buckets are mapped to a greater number of fragmented partitions as a number of partitions increases, wherein the distributed storage system employs a pull architecture, and not a push architecture, to satisfy local file system operations.

12. The system of claim 11, wherein an amount of redistribution of files in the event of a configuration update is reduced by mapping the buckets to the partitions, thereby facilitating scaling of the distributed storage system up and down in size in respective instances and in a manner more efficient than a second distributed storage system in which the buckets are mapped to the nodes and not mapped to the partitions, wherein approximately a number of buckets equaling one divided by the number of partitions are mapped to each of the partitions, the system further comprising a new storage node that is added to the distributed storage system, wherein the operation further comprises:

adding the new storage node to the end of the ordered list of the storage nodes; and

transferring a portion of the distributed files stored on each one of the multiple storage nodes to the new storage node.

13. The system of claim 12, wherein the operation further comprises:

recomputing the first mapping of the buckets to the partitions;

recomputing the second mapping of the partitions to the multiple storage nodes; and

combining the recomputed first mapping with the recomputed second mapping to produce a recomputed third mapping of the buckets to the multiple storage nodes, wherein the transferring of the portion of the distributed files stored on each one of the multiple storage nodes is performed according to the recomputed third mapping, wherein a number of buckets extracted from each of the multiple storage nodes is based on the number of existing buckets divided by the number of existing partitions.

14. The system of claim 11, further comprising an existing storage node that is removed from the distributed storage system, wherein the operation further comprises:

removing the existing storage node from the end of the ordered list of the storage nodes; and

transferring different portions of the distributed files stored on the existing storage node to each one of the multiple storage nodes.

15. The system of claim 14, wherein the operation further comprises:

recomputing the first mapping of the buckets to the partitions;

recomputing the second mapping of the partitions to the multiple storage nodes; and

combining the recomputed first mapping with the recomputed second mapping to produce a recomputed third mapping of the buckets to the multiple storage nodes, wherein the transferring of the different portions of the distributed files stored on the existing storage node is performed according to the recomputed third mapping.

16. The system of claim 11, further comprising an existing storage node that is replaced with a new storage node in the distributed storage system, wherein the operation further comprises:

replacing the existing storage node in the ordered list of the storage nodes with the new storage node; and

transferring a portion of the distributed files that are stored on the existing storage node to the new storage node.

17. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause a computer system to distribute-files across multiple heterogeneous storage nodes without using a centralized server in a distributed storage system, by:

computing a first mapping of buckets to partitions using a first deterministic function applied to an ordered list of the storage nodes, wherein each bucket stores at least a portion of the files, and at least one of the partitions is fragmented in bucket space, wherein a number of buckets mapped to each partition is based on a ratio of a number of existing buckets to a number of existing partitions in the distributed storage system;

computing, using a second deterministic function applied to the ordered list of the storage nodes, a second mapping of the partitions to the multiple storage nodes, wherein each partition is mapped to two or more of the multiple storage nodes based on a predefined redundancy value;

combining the first mapping with the second mapping to produce a third mapping of the buckets to the multiple storage nodes; and

storing the files across the multiple storage nodes in the distributed storage system according to the third mapping, wherein the ordered list of storage nodes is stored by each of;

(i) a plurality of client nodes, and (ii) each of the multiple storage nodes.

18. The non-transitory computer-readable storage medium of claim 17, wherein the first mapping iteratively distributes the buckets substantially evenly between the partitions, wherein each of the plurality of client nodes and the multiple storage nodes uses the ordered list of storage nodes to determine which of the multiple storage nodes a requested file resides on, wherein the distributed storage system employs a pull architecture, and not a push architecture, to satisfy local file system operations.

19. The non-transitory computer-readable storage medium of claim 18, wherein the buckets are indirectly mapped to the storage nodes through the partitions, wherein the buckets are mapped to contiguous partitions when a single partition and when two partitions are used, wherein the buckets are mapped to a greater number of fragmented partitions as a number of partitions increases.

20. The non-transitory computer-readable storage medium of claim 19, wherein an amount of redistribution of files in the event of a configuration update is reduced by mapping the buckets to the partitions, thereby facilitating scaling of the distributed storage system up and down in size in respective instances and in a manner more efficient than a second distributed storage system in which the buckets are mapped to the nodes and not mapped to the partitions, wherein approximately a number of buckets equaling one divided by the number of partitions are mapped to each of the partitions.