Consolidating data in storage host groupings

• US 9,858,325 B1
• Filed: 09/29/2014
• Issued: 01/02/2018
• Est. Priority Date: 09/29/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Suver, Claire E., Donlan, Bryan James, Franklin, Paul David, Kirschner, James Caleb, Sorenson, III, James Christopher
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US14/500,782
• Time in Patent Office: 1,191 Days
• Field of Search: 707812, 707609, 707693, 707699, 707999101
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A data storage service distributes a plurality of data fragments corresponding to a data object among one or more data storage host groupings in a manner that avoids a possibility of correlated loss of multiple data fragments by consolidation of data of a data storage host grouping onto a single data storage host. The data storage service selects a data storage host grouping and determines an amount of used capacity for the selected data storage host grouping. If the selected grouping satisfies an emptiness threshold, the data storage service selects a data storage host from the grouping and consolidates one or more data sets of the grouping onto the selected data storage host. Subsequently, the data storage service updates metadata for each data storage host of the selected data storage host grouping to specify a location of data stored therein.

Claims

1. A computer-implemented method comprising:

determining a plurality of data storage host pairs having a respective first and second storage host corresponding to a respective first and second physical storage location, the plurality of data storage host pairs determined based at least in part on physical characteristics of the respective first and second physical storage locations;

for each data object of a plurality of data objects, using a redundancy encoding scheme to generate a plurality of data fragments;

distributing the plurality of data fragments among at least a subset of the plurality of data storage host pairs according to one or more placement rules based at least in part on the physical characteristics of the respective first and second physical storage locations, wherein distribution of the plurality of data fragments is performed to avoid a possibility of correlated loss of multiple data fragments of the plurality of data fragments by consolidation of data of a data storage host pair onto a single data storage host;

selecting a data storage host pair from the plurality of data storage host pairs;

selecting a data storage host from the selected data storage host pair;

consolidating data from the selected data storage host pair onto the selected data storage host; and

updating metadata for each data storage host of the selected data storage host pair to specify a location of data stored therein.

2. The computer-implemented method of claim 1, further comprising:

determining an amount of used capacity for the selected data storage host pair; and

determining, based at least in part on the amount of used capacity, whether the selected data storage host pair satisfies an emptiness threshold, the emptiness threshold specifying a point wherein all data fragments from the selected data storage host pair can be stored onto a single data storage host of the data storage host pair.

3. The computer-implemented method of claim 2, further comprising selecting the data storage host from the selected data storage host pair based at least in part on an amount of capacity used by each data storage host of the data storage host pair.

4. The computer-implemented method of claim 1, further comprising removing one or more unselected data storage hosts from the data storage host pair upon updating the metadata for each data storage host of the selected data storage host pair.

5. The computer-implemented method of claim 1,

wherein the plurality of data storage host pairs comprise a respective first and second storage host;

wherein the first storage host is defined by a first physical storage location; and

wherein the second storage host is defined by a second physical storage location that is different from the first physical storage location.

6. The computer-implemented method of claim 5, wherein:

the distributing the plurality of data fragments among at least a subset of the plurality of data storage host pairs occurs such that no data storage host pair receives more than a maximum number of data fragments of the same data object, and

wherein distribution of the plurality of data fragments is further performed to avoid a loss of more than the maximum number of data fragments due to loss of a storage host in the plurality of host pairs.

7. A system, comprising at least one computing device configured to implement one or more services, wherein the one or more services are configured to:

for each data object of a plurality of data objects that has been redundancy encoded to generate a plurality of data fragments, distribute the plurality of data fragments among a plurality of data storage host groupings according to one or more placement rules based at least in part on the physical characteristics of a respective plurality of physical storage locations that define the plurality of data storage host groupings, such that consolidation of data of a data storage host grouping to fewer data storage hosts maintains compliance with one or more conditions for independent failure of the plurality of data fragments of the plurality of data objects;

select a data storage host grouping from a plurality of data storage host groupings, the plurality of data storage host groupings storing a plurality of data fragments, each data fragment of the plurality of data fragments;

determine to consolidate data of the data storage host grouping onto fewer data storage hosts;

consolidate the data of the data storage host grouping onto fewer data storage hosts; and

remove at least one data storage host from the selected data storage host grouping.

8. The system of claim 7, wherein the one or more conditions for independent failure of the plurality of data fragments of the plurality of data objects specify that the one or more conditions are not violated as a result of consolidation of the data of the data storage host grouping onto fewer data storage hosts.

9. The system of claim 7, wherein the data storage host groupings are data storage host pairs, each data storage host pair comprising two data storage hosts.

10. The system of claim 7, wherein the plurality of data objects are redundantly encoded using an erasure coding scheme.

11. The system of claim 7, wherein the one or more services are further configured to distribute the plurality of data fragments among the plurality of data storage host groupings in a manner such that one data fragment is stored within each data storage host grouping of the plurality of the data storage host groupings.

12. The system of claim 7, wherein the one or more services are further configured to add the removed at least one data storage host to another data storage host grouping.

13. The system of claim 7, wherein determination whether to consolidate the data of the data storage host grouping onto fewer data storage hosts is based at least in part on the data storage host grouping having satisfied an emptiness threshold.

14. The system of claim 7, wherein the fewer data storage hosts are selected based at least in part on an amount of capacity used by each data storage host of the data storage host grouping.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, if executed by one or more processors of a computer system, cause the computer system to at least:

for each data object of a plurality of data objects that has been redundancy encoded to generate a plurality of data fragments, distribute the plurality of data fragments among a plurality of data storage host groupings according to one or more placement rules based at least in part on the physical characteristics of a respective plurality of physical storage locations that define the plurality of data storage host groupings, such that consolidation of data of a data storage host grouping to fewer data storage hosts maintains compliance with one or more conditions for independent failure of the plurality of data fragments of the plurality of data objects;

select, from the plurality of data storage host groupings, a data storage host grouping;

select fewer data storage hosts than a number of data storage hosts comprising the selected data storage host grouping;

consolidate the data of the selected data storage host grouping onto the fewer data storage hosts; and

remove at least one data storage host from the selected data storage host grouping.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to update metadata for each data storage host of the selected data storage host grouping to specify a location of data stored therein.

17. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to add the removed at least one data storage host to another data storage host grouping.

18. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to:

determine an amount of capacity used by a plurality of data storage hosts of a data storage host grouping;

identify, for each data storage host of the plurality of data storage hosts of the selected data storage host grouping, an amount of used capacity; and

determine, based at least in part on a sum of the amount of used capacity for each data storage host, whether the sum satisfies an emptiness threshold for the selected data storage host grouping.

19. The non-transitory computer-readable storage medium of claim 15, wherein the fewer data storage hosts are selected based at least in part on an amount of capacity used by each data storage host of the selected data storage host grouping.

20. The non-transitory computer-readable storage medium of claim 15, wherein the one or more conditions for independent failure of the plurality of data fragments of the plurality of data objects specify that the one or more conditions are not violated as a result of consolidation of the data of the data storage host grouping onto the fewer data storage hosts.

21. The non-transitory computer-readable storage medium of claim 15, wherein the plurality of data objects are redundantly encoded using an erasure coding scheme.

22. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, when executed by the one or more processors, cause the computer system to distribute the plurality of data fragments among the plurality of data storage host groupings in a manner such that a limited number of data fragments are stored within each data storage host grouping of the plurality of the data storage host groupings.