Efficient storage of variably-sized data objects in a data store

• US 9,317,213 B1
• Filed: 05/10/2013
• Issued: 04/19/2016
• Est. Priority Date: 05/10/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gupta, Anurag Windlass, Tobler, Benjamin, McKelvie, Samuel James, Corey, James McClellan
• Primary Examiner(s): Fan, Shiow-Jy
• Application Number:
  US13/892,027
• Time in Patent Office: 1,075 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Variably-sized data objects may be received for storage at a data store. The data store may have a minimum write size. In various embodiments, received data objects may be divided into one or more equally-sized portions that equal the minimum write size of the data store and a remainder of the data object. The one or more equally-sized portions of the data object may be stored in data blocks that are equivalent to the minimum write size of the data store in a fixed-size data storage area of the data store. The remainder of the data object may be stored in a variably-sized data storage area of the data store along with one or more other data portions in a same data block. The remainder of the data object may, in some embodiments, be linked to the one or more equally-sized portions of the data object.

Claims

1. A system, comprising:

a storage node of a distributed storage service, comprising;

at least one persistent data storage device, comprising a plurality of data blocks equivalent to a minimum write size of the at least one persistent storage device;

a storage node management module, configured to;

receive a data object for storage at the storage node;

divide the data object into one or more equally-sized portions and a remainder, wherein each of the one or more equally-sized portions equal the minimum write size of the at least one persistent data storage device;

store each of the one or more equally-sized portions of the data object in a respective data block of the plurality of data blocks in a fixed-size data storage area on the persistent data storage device; and

store the remainder of the data object in a variably-sized data storage area on the persistent data storage device, wherein the remainder is linked to the one or more data blocks storing the one or more equally-sized portions of the data object, wherein the variably-sized data storage area stores a plurality of other data portions, wherein at least some of the other data portions are stored together with the remainder in a same data block of the plurality of data blocks in the variably-sized data storage area.

2. The system of claim 1, wherein the storage node management module is further configured to:

receive data for the data object; and

compress the received data for the data object according to one or more compression techniques to generate a compressed data object;

wherein the compressed data object is the received data object.

3. The system of claim 1, wherein, to divide the data object into the one or more equal-sized portions that equal the minimum write size of the at least one persistent data storage device and the remainder of the data object, the storage management module is configured to:

divide the data object into one or more equally-sized initial portions of the data object such that for each of the one or more equally-sized initial portions of the data object a sum of a size of the equally-sized initial portion and a metadata portion is equivalent to the minimum write size of the at least one persistent data storage device; and

for each of the one or more equally-sized initial portions, obtain the metadata to include with the equally-sized initial portion in order to generate the one or more equally-sized portions of the data object.

4. The system of claim 1, wherein the remainder is stored as a log record, and wherein the plurality of other data portions stored in the variably-sized storage area are a plurality of other log records.

5. A method, comprising:

performing, by one or more computing devices;

receiving a data object for storage in a data store, wherein said data store comprises a plurality of data blocks equivalent to a minimum write size for the data store;

dividing the data object into one or more equally-sized portions and a remainder, wherein each of the one or more equally-sized data portions equal the minimum write size of the data store;

storing each of the one or more equally-sized portions of the data object in a respective data block of the plurality of data blocks in a fixed-size data storage area in the data store; and

storing the remainder of the data object in a variably-sized data storage area in the data store, wherein the remainder is linked to the one or more equally-sized portions of the data object stored in the fixed-size data storage area, wherein the variably-sized data storage area stores a plurality of other data portions, wherein at least some of the other data portions are stored together with the remainder in a same data block of the plurality of data blocks.

6. The method of claim 5, further comprising:

receiving data for the data object; and

encrypting the received data for the data object according to an encryption technique to generate an encrypted data object;

wherein the encrypted data object is the received data object.

7. The method of claim 5, wherein said dividing the data object into one or more equally-sized portions and a remainder of the data object comprises:

determining that a size of the remainder of the data object is less than a remainder efficiency threshold.

8. The method of claim 7, wherein said dividing the data object into one or more equally-sized portions and a remainder of the data object further comprises:

determining the remainder efficiency threshold based, at least in part, on available storage in the fixed-size data storage area or available storage in the variably-sized data storage area.

9. The method of claim 5, further comprising:

receiving data for the data object; and

compressing the received data for the data object according to one or more compression techniques to generate a compressed data object;

wherein the compressed data object is the received data object.

10. The method of claim 5, wherein said dividing the data object into one or more equally-sized portions and a remainder of the data object comprises:

dividing the data object into one or more equally-sized initial portions of the data object such that for each of the one or more equally-sized initial portions of the data object a sum of a size of the equally-sized initial portion and a size of a metadata portion is equivalent to the minimum write size of the data store; and

for each of the one or more equally-sized initial portions, obtaining the metadata to include with the equally-sized initial portion in order to generate the one or more equally-sized portions of the data object.

11. The method of claim 5, further comprising:

upon detecting that the data object is to no longer be persisted;

indicating that the respective data blocks storing the one or more equally-sized portions of the data object in the fixed-size data storage area are available for storing new data; and

indicating that a portion of the data block storing the remainder in the variably-sized data storage area is available for reclamation.

12. The method of claim 11, wherein different ones of the plurality of other data portions are indicated as available for reclamation, wherein the method further comprises:

performing a reclamation process to arrange contiguously those data portions of the plurality of other data portions in the variably-sized data storage area that are not indicated as available for reclamation such that the data block storing the indicated remainder of the data object is available for storing new data.

13. The method of claim 12, wherein the reclamation process is performed as a background process.

14. The method of claim 5, wherein the one or more computing devices together implement a storage node of a distributed storage service, and wherein the data object is received from a client of the distributed storage service for storage at the storage node.

15. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices implement:

receiving a data object for storage in a data store, wherein said data store comprises a plurality of data blocks equivalent to a minimum write size for the data store;

dividing the data object into one or more equally-sized portions and a remainder, wherein each of the one or more equally-sized portions equal the minimum write size of the data store;

storing each of the one or more equally-sized portions of the data object in a respective data block of the plurality of data blocks in a fixed-size data storage area in the data store; and

storing the remainder of the data object in a variably-sized data storage area in the data store, wherein the remainder is linked to the one or more equally-sized portions of the data object stored in the fixed-size data storage area, wherein the variably-sized data storage area stores a plurality of other data portions, wherein at least some of the other data portions are stored together with the remainder in a same data block of the plurality of data blocks.

16. The non-transitory, computer-readable storage medium of claim 15, wherein the program instructions when executed by the one or more computing devices further implement:

receiving data for the data object; and

compressing the received data for the data object according to one or more compression techniques to generate a compressed data object;

wherein the compressed data object is the received data object.

17. The non-transitory, computer-readable storage medium of claim 15, wherein, in said dividing the data object into the one or more equally-sized portions and the remainder, the program instructions when executed by the one or more computing devices further implement:

dividing the data object into one or more equally-sized initial portions of the data object such that for each of the one or more equally-sized initial portions of the data object a sum of a size of the equally-sized initial portion and a size of a metadata portion is equivalent to the minimum write size of the data store; and

for each of the one or more equally-sized initial portions, generating the metadata to include with the equally-sized initial portion in order to generate the one or more equally-sized portions of the data object.

18. The non-transitory, computer-readable storage medium of claim 15, wherein the program instructions when executed by the one or more computing devices further implement:

receiving another data object for storage;

dividing the other data object into one or more other equally-sized portions and another remainder, wherein each of the one or more other equally-sized portions equal the minimum write size of the data store;

determining that a size of the other remainder of the other data object exceeds a remainder efficiency threshold; and

storing each of the other one or more equally-sized portions of the other data object and the other remainder of the other data object in a respective data block of the plurality of data blocks in the fixed-size data storage area in the data store.

19. The non-transitory, computer-readable storage medium of claim 15, wherein the link between the remainder and the one or more the one or more equally-sized portions of the data object is stored along with the remainder in the variably-sized data storage area.

20. The non-transitory, computer-readable storage medium of claim 15, wherein the fixed-size data storage and the variably-sized data storage are implemented together as part of a single persistent storage device.