Methods and apparatus for optimizing resource utilization in distributed storage systems

• US 8,452,819 B1
• Filed: 03/22/2011
• Issued: 05/28/2013
• Est. Priority Date: 03/22/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sorenson, James Christopher III, He, Gang, Goel, Saurabh
• Primary Examiner(s): BROWN, SHEREE N
• Application Number:
  US13/053,469
• Time in Patent Office: 798 Days
• Field of Search: 707/809
• US Class Current: 707/809
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Methods and apparatus for optimizing resource utilization in distributed storage systems. A data migration technique is described that may operate in the background in a distributed storage data center to migrate data among a fleet of storage units to achieve a substantially even and randomized data storage distribution among all storage units in the fleet. When new storage units are added to the fleet and coupled to the data center network, the new storage units are detected. Instead of processing and storing new data to the newly added storage units, as in conventional distributed storage systems, the new units are blocked from general client I/O to allow the data migration technique to migrate data from other, previously installed storage hardware in the data center onto the new storage hardware. Once the storage load on the new storage units is balanced with the rest of the fleet, the new storage units are released for general client I/O.

Claims

1. A distributed storage data center, comprising:

a data center network;

a plurality of storage units each coupled to the data center network that collectively store client data for a plurality of clients, wherein the data center network carries general client I/O traffic from the plurality of clients to the plurality of storage units, wherein the general client I/O traffic includes reads from and writes to the client data collectively stored on the plurality of storage units;

one or more devices coupled to the data center network, wherein the one or more devices implement a data migration module operable to;

initiate migration of data units among the plurality of storage units according to a storage load balancing technique to maintain a balanced distribution of the client data across the plurality of storage units;

detect addition of one or more new storage units to the data center network;

in response to said detecting the addition of the one or more new storage units to the data center network;

block general client I/O traffic to the one or more new storage units on the data center network;

initiate migration of data units from each of one or more of the plurality of storage units to the one or more new storage units according to the storage load balancing technique to balance storage load across the plurality of storage units and the one or more new storage units, wherein general client I/O traffic is allowed to go through to the one or more of the plurality of storage units during said migration of data units from the one or more of the plurality of storage units to the one or more new storage units, and wherein general client I/O traffic remains blocked to the one or more new storage units during said migration of data units from the one or more of the plurality of storage units to the one or more new storage units;

determine that storage load is balanced across the plurality of storage units and the one or more new storage units; and

in response to said determining that storage load is balanced across the plurality of storage units and the one or more new storage units, unblock general client I/O traffic to the one or more new storage units on the data center network.

2. The distributed storage data center as recited in claim 1, wherein, to initiate migration of data units from each of one or more of the plurality of storage units to the one or more new storage units according to the storage load balancing technique, the data migration module is operable to:

select one of the plurality of storage units as a source storage unit according to a selection technique and one or more resource constraints;

select one or more data units to be migrated from the source storage unit to one of the one or more new storage units as a destination storage unit according to one or more data selection criteria; and

direct migration of the selected one or more data units from the source storage unit to the destination storage unit.

3. The distributed storage data center as recited in claim 2, wherein the data migration module is operable to repeat said selecting one of the plurality of storage units as a source storage unit, said selecting one or more data units to be migrated from the source storage unit to the destination storage unit, and said directing migration of the selected one or more data units from the source storage unit to the destination storage unit until said determining that storage load is balanced across the plurality of storage units and the one or more new storage units.

4. The distributed storage data center as recited in claim 2, wherein the selection technique is an N-choices technique that randomly selects a subset of the plurality of storage units and selects one storage unit from the selected subset as the source storage unit according to one or more criteria for selecting a source storage unit.

5. The distributed storage data center as recited in claim 4, wherein the one or more criteria for selecting a source storage unit include one or more of relative amount of data stored on each storage unit in the subset, relative size of data elements within data units stored on each storage unit in the subset, type of data elements within data units stored on each storage unit in the subset, or a restriction that prohibits copies of a same data unit that are stored on different storage units from being migrated to one storage unit.

6. A distributed storage system, comprising:

a plurality of storage units each coupled to a network, wherein the plurality of storage units collectively store client data for a plurality of clients, wherein the network carries general client I/O traffic from the plurality of clients to the plurality of storage units, wherein the general client I/O traffic includes reads from and writes to the client data collectively stored on the plurality of storage units;

one or more devices coupled to the network operable to;

detect addition of one or more new storage units to the network;

in response to said detecting the addition of the one or more new storage units to the network;

block general client I/O traffic to the one or more new storage units on the network;

migrate data units from each of one or more of the plurality of storage units to the one or more new storage units, wherein general client I/O traffic is allowed to go through to the one or more of the plurality of storage units during said migration of data units from the one or more of the plurality of storage units to the one or more new storage units, and wherein general client I/O traffic remains blocked to the one or more new storage units during said migration of data units from the one or more of the plurality of storage units to the one or more new storage units; and

in response to determining that said migrating data units from the one or more of the plurality of storage units to the one or more new storage units is complete, unblock general client I/O traffic to the one or more new storage units on the network.

7. The distributed storage system as recited in claim 6, wherein, to migrate data units from each of one or more of the plurality of storage units to the one or more new storage units, the one or more devices are operable to select the data units for migration according to a storage load balancing technique that substantially balances storage load across the plurality of storage units and the one or more new storage units.

8. The distributed storage system as recited in claim 7, wherein the storage load balancing technique employs an N-choices technique that randomly selects a subset of the plurality of storage units and selects one storage unit from the selected subset as the source storage unit for migrating data units to the one or more new storage units according to one or more selection criteria.

9. The distributed storage system as recited in claim 6, wherein the client data are stored on the plurality of storage units as individually addressable data elements, wherein the data units each include a plurality of the individually addressable data elements, and wherein, in said migration, the one or more devices are operable to update mapping information at data unit level and not at data element level.

10. The distributed storage system as recited in claim 9, wherein the distributed storage system is operable to:

maintain mapping information for accessing the data elements that maps each addressable data element to one or more data units; and

maintain mapping information that maps each data unit to a storage unit; and

wherein, to update the mapping information at the data unit level, the one or more devices are operable to modify entries corresponding to the migrated data units in the mapping information that maps each data unit to a storage unit.

11. A method, comprising:

detecting one or more new storage units added to a plurality of storage units coupled to a network, wherein the plurality of storage units collectively store data, wherein the network carries general I/O traffic to the plurality of storage units, wherein the general client I/O traffic includes reads from and writes to the data collectively stored on the plurality of storage units;

in response to said detecting the one or more new storage units;

blocking general I/O traffic to the one or more new storage units on the network;

migrating, by one or more devices coupled to the network, data units from each of one or more of the plurality of storage units to the one or more new storage units, wherein general client I/O traffic is allowed to go through to the one or more of the plurality of storage units when migrating data units from the one or more of the plurality of storage units to the one or more new storage units, and wherein general client I/O traffic remains blocked to the one or more new storage units during said migration of data units from the one or more of the plurality of storage units to the one or more new storage units; and

in response to determining that said migrating data units from the one or more of the plurality of storage units to the one or more new storage units is complete, unblocking general I/O traffic to the one or more new storage units on the network.

12. The method as recited in claim 11, wherein said migrating data units from each of one or more of the plurality of storage units to the one or more new storage units substantially balances storage load across the plurality of storage units and the one or more new storage units.

13. The method as recited in claim 11, wherein said migrating data units from each of one or more of the plurality of storage units to the one or more new storage units comprises:

selecting one of the plurality of storage units as a source storage unit;

selecting one or more data units to be migrated from the source storage unit to one of the one or more new storage units as a destination storage unit; and

migrating the selected one or more data units from the source storage unit to the destination storage unit.

14. The method as recited in claim 13, further comprising repeating said selecting one of the plurality of storage units as a source storage unit according to a selection technique, said selecting one or more data units to be migrated from the source storage unit to one of the one or more new storage units as a destination storage unit, and said migrating the selected one or more data units from the source storage unit to the destination storage unit until storage load is substantially balanced across the plurality of storage units and the one or more new storage units.

15. The method as recited in claim 13, wherein said selecting one of the plurality of storage units as a source storage unit comprises selecting the source storage unit according to an N-choices technique that randomly selects a subset of the plurality of storage units and selects one storage unit from the selected subset as the source storage unit according to one or more criteria for selecting a source storage unit.

16. The method as recited in claim 15, wherein the one or more criteria for selecting a source storage unit include relative amount of data stored on each storage unit in the subset, and wherein the storage unit in the subset with a highest amount of data is selected from the subset as the source storage unit.

17. The method as recited in claim 13, wherein said selecting one or more data units to be migrated from the source storage unit to a destination storage unit comprises selecting the one or more units according to one or more data selection criteria.

18. The method as recited in claim 17, wherein the one or more data selection criteria include relative size of data elements within data units.

19. The method as recited in claim 17, wherein the one or more data selection criteria include type of data elements within data units.

20. The method as recited in claim 17, wherein the one or more data selection criteria include a restriction that prohibits copies of a same data unit that are stored on different storage units from being migrated to one storage unit.

21. The method as recited in claim 11, wherein the data are stored on the plurality of storage units as individually addressable data elements, wherein the data units each include a plurality of the individually addressable data elements, and wherein said migrating comprises updating mapping information at data unit level and not at data element level.

22. The method as recited in claim 21, further comprising:

maintaining mapping information for accessing the data elements that maps each addressable data element to one or more data units;

maintaining mapping information that maps each data unit to a storage unit; and

wherein said updating mapping information comprises updating entries corresponding to the migrated data units in the mapping information that maps each data unit to a storage unit.

23. The method as recited in claim 11, wherein said migrating data units from each of one or more of the plurality of storage units to the one or more new storage units comprises enforcing one or more specified resource constraints on said migrating, wherein each of the one or more resource constraints limits how much of a respective resource is used in performing said migrating.

24. The method as recited in claim 23, wherein the resources for which the resource constraints are enforced include one or more of network bandwidth or processing capacity of the storage units.

25. The method as recited in claim 11, further comprising:

detecting a storage unit to be removed from the plurality of storage units;

blocking general I/O traffic to the storage unit on the network;

migrating data units stored on the storage unit to be removed from the storage unit to one or more other storage units in the plurality of storage units; and

removing the storage unit from the plurality of storage units on the network.

26. A non-transitory computer-accessible storage medium storing program instructions computer-executable to implement:

detecting a new storage unit added to a fleet of storage units coupled to a network, wherein the fleet of storage units collectively store data, wherein the network carries general I/O traffic to the storage units in the fleet, and wherein the general client I/O traffic includes reads from and writes to the data collectively stored on the fleet of storage units;

in response to said detecting the new storage unit;

blocking general I/O traffic to the new storage unit on the network;

migrating data units from each of two or more of the storage units in the fleet to the new storage unit, wherein, in said migrating, the program instructions are computer-executable to implement iteratively performing;

selecting a storage unit from the fleet as a source storage unit;

selecting one or more units of the data to be migrated from the source storage unit to the new storage unit; and

initiating migration of the selected one or more units of the data from the source storage unit to the new storage unit, wherein general client I/O traffic is allowed to go through to the source storage unit during said migration of data units from the source storage unit to the new storage unit;

wherein general client I/O traffic remains blocked to the new storage unit during said migration of data units from the two or more storage units to the new storage unit; and

unblocking general I/O traffic to the new storage unit on the network subsequent to said migration of data units from the two or more storage units to the new storage unit.

27. The non-transitory computer-accessible storage medium as recited in claim 26, wherein the program instructions are computer-executable to implement iteratively performing said selecting a storage unit from the fleet as a source storage unit, said selecting one or more units of the data to be migrated from the source storage unit to the new storage unit, and said initiating migration of the selected one or more units of the data from the source storage unit to the new storage unit until storage load is substantially balanced across the plurality of storage units and the new storage unit.

28. The non-transitory computer-accessible storage medium as recited in claim 26, wherein, in said selecting a storage unit from the fleet as a source storage unit, the program instructions are computer-executable to implement:

randomly selecting a subset of the storage units from the fleet; and

selecting the source storage unit from among the subset of the storage units in the fleet according to one or more selection criteria.

29. The non-transitory computer-accessible storage medium as recited in claim 28, wherein the one or more selection criteria include relative amount of data stored on each storage unit in the subset, and wherein the storage unit with a highest amount of data is selected from the subset as the source storage unit.

30. The non-transitory computer-accessible storage medium as recited in claim 26, wherein, in said selecting one or more units of the data to be migrated from the source storage unit to the new storage unit, the program instructions are computer-executable to implement selecting the one or more units according to one or more data selection criteria.

31. The non-transitory computer-accessible storage medium as recited in claim 30, wherein the one or more data selection criteria include relative size of data elements within data units.

32. The non-transitory computer-accessible storage medium as recited in claim 30, wherein the one or more data selection criteria include type of data elements within data units.

33. The non-transitory computer-accessible storage medium as recited in claim 26, wherein, in said initiating migration of data units from each of two or more of the storage units in the fleet to the new storage unit, the program instructions are computer-executable to implement enforcing one or more specified resource constraints, wherein each of the one or more resource constraints limits how much of a respective resource is used in performing migration.