Methods and apparatus for optimizing resource utilization in distributed storage systems

• US 9,020,984 B1
• Filed: 05/28/2013
• Issued: 04/28/2015
• Est. Priority Date: 03/22/2011
• Status: Expired due to Fees

• 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/903,670
• Time in Patent Office: 700 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 system, comprising:

a plurality of storage units each coupled to a network, wherein the plurality of storage units collectively store data for a plurality of clients, wherein the plurality of clients each read previously stored data from and store new data to the plurality of storage units via the network;

one or more devices coupled to the network configured 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 new data from being stored to the one or more new storage units;

in response to said detecting the addition of the one or more new storage units to the network, migrate previously stored data units from the data collectively stored on the plurality of storage units to the one or more new storage units until determining that a storage load on each of the one or more new storage units is at a target level; and

in response to said determining that the storage load on each of the one or more new storage units is at the target level and after said blocking new data from being stored to the one or more new storage units, allow new data to be stored to the one or more new storage units.

2. The distributed storage system as recited in claim 1, wherein the one or more devices are further configured to, in response to said determining that the storage load on each of the one or more new storage units is at the target level, allow reads of data from the one or more new storage units.

3. The distributed storage system as recited in claim 1, wherein, to determine that the storage load on each of the one or more new storage units is at a target level, the one or more devices are configured to determine that a storage load of the collectively stored data is substantially balanced across the plurality of storage units and the one or more new storage units.

4. The distributed storage system as recited in claim 1, wherein the network transmits 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 data collectively stored on the plurality of storage units, and wherein the one or more devices are further configured to block at least a portion of the general client I/O traffic to the one or more new storage units on the network until determining that the storage load on each of the one or more new storage units is at the target level.

5. The distributed storage system as recited in claim 1, wherein, to migrate previously stored data units from the data collectively stored on the plurality of storage units to the one or more new storage units until determining that the storage load on each of the one or more new storage units is at a target level, the one or more devices are configured to select the data units for migration according to a storage load balancing technique that substantially balances a storage load across the plurality of storage units and the one or more new storage units.

6. The distributed storage system as recited in claim 5, 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 a source storage unit for migrating data units to the one or more new storage units according to one or more selection criteria.

7. The distributed storage system as recited in claim 1, wherein the data is 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, during said migration, the one or more devices are further configured to update mapping information maintained by the distributed storage system at a data unit level and not at a data element level.

8. A method, comprising:

detecting, by one or more computing devices coupled to a network, one or more new storage units added to a plurality of storage units coupled to the network, wherein the plurality of storage units collectively store data, wherein a plurality of clients each read previously stored data from and store new data to the plurality of storage units via the network;

in response to said detecting the one or more new storage units, blocking new data from being stored to the one or more new storage units;

in response to said detecting the one or more new storage units, migrating previously stored data units from the data collectively stored on the plurality of storage units to the one or more new storage units until determining that a storage load on each of the one or more new storage units is at a target level; and

in response to said determining that the storage load on each of the one or more new storage units is at the target level and after said blocking new data from being stored to the one or more new storage units, allowing new data to be stored to the one or more new storage units.

9. The method as recited in claim 8, further comprising, in response to said determining that the storage load on each of the one or more new storage units is at the target level, allowing reads of data from the one or more new storage units.

10. The method as recited in claim 8, wherein said determining that a storage load on each of the one or more new storage units is at a target level comprises determining that a storage load of the collectively stored data is substantially balanced across the plurality of storage units and the one or more new storage units.

11. The method as recited in claim 8, wherein the network transmits 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 data collectively stored on the plurality of storage units, the method further comprising blocking at least a portion of the general client I/O traffic to the one or more new storage units on the network until determining that the storage load on each of the one or more new storage units is at the target level.

12. The method as recited in claim 8, wherein said migrating previously stored data units from the data collectively stored on the plurality of storage units to the one or more new storage units until determining that the storage load on each of the one or more new storage units is at a target level comprises iteratively performing:

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.

13. The method as recited in claim 12, 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.

14. The method as recited in claim 12, 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 data units according to one or more data selection criteria, wherein the one or more data selection criteria include at least one of relative size of data elements within data units, type of data elements within data units, 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.

15. The method as recited in claim 8, wherein, in said migrating previously stored data units from the data collectively stored on the plurality of storage units to the one or more new storage units until determining that the storage load on each of the one or more new storage units is at a target level, one or more specified resource constraints are enforced 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, wherein the resources for which the resource constraints are enforced include one or more of network bandwidth or processing capacity of the storage units.

16. A non-transitory computer-accessible storage medium storing program instructions that, when executed on one or more processors, cause the one or more processors to implement:

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 a plurality of clients each read previously stored data from and store new data to the plurality of storage units via the network;

in response to said detecting the one or more new storage units, blocking new data from being stored to the one or more new storage units;

in response to said detecting the one or more new storage units, migrating previously stored data units from the data collectively stored on the plurality of storage units to the one or more new storage units until determining that a storage load on each of the one or more new storage units is at a target level; and

allowing new data to be stored to the one or more new storage units subsequent to said determining that the storage load on each of the one or more new storage units is at the target level and after said preventing new data from being stored to the one or more new storage units.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the program instructions, when executed on the one or more processors, further cause the one or more processors to implement allowing reads of data from the one or more new storage units subsequent to said determining that the storage load on each of the one or more new storage units is at the target level.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein in said determining that the storage load on each of the one or more new storage units is at a target level comprises determining that a storage load of the collectively stored data is substantially balanced across the plurality of storage units and the one or more new storage units.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the network transmits 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 data collectively stored on the plurality of storage units, and wherein the program instructions, when executed on the one or more processors, further cause the one or more processors to implement blocking at least a portion of the general client I/O traffic to the one or more new storage units on the network until determining that the storage load on each of the one or more new storage units is at the target level.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein said migrating previously stored data units from the data collectively stored on the plurality of storage units to the one or more new storage units until determining that storage load on each of the one or more new storage units is at a target level comprises iteratively performing:

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.