Self-describing data blocks stored with atomic write

• US 9,817,710 B2
• Filed: 10/10/2016
• Issued: 11/14/2017
• Est. Priority Date: 05/28/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gupta, Anurag Windlass, Corey, James McClellan, Leshinsky, Yan Valerie, Madhavarapu, Pradeep Jnana, McKelvie, Samuel James
• Primary Examiner(s): Chase, Shelly A
• Application Number:
  US15/289,907
• Publication Number:
  US 20170031749A1
• Time in Patent Office: 400 Days
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/0787 Storage of error reports, e.g. persistent data storage, storage using memory protection
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• 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/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• 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/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Self-describing data blocks of a minimum atomic write size may be stored for a data store. Data may be received for storage in a data block at a persistent storage device. Metadata may be generated for the data that includes an error detection code which is generated for the data and the metadata together. An individual atomic write operation may write together the data and the metadata in the data block. When accessed, the error detection code is applicable to detect errors and the metadata may also be applicable to determine whether the data is stored for a currently assigned purpose or a previously assigned purpose of the data block.

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;

a storage manager implementing a data store, configured to;

access a data block of the plurality of data blocks as part of an operation utilizing data blocks assigned to a particular purpose, and wherein the access comprises;

read metadata stored in the data block, wherein the metadata was stored along with other contents of the data block within an individual atomic write operation to the data block by the at least one persistent storage device;

evaluate the metadata to determine that the data block is not erroneous and that an assigned purpose for the data block indicated by the metadata matches the particular purpose; and

in response to the determination that the data block is not erroneous and that the assigned purpose for the data block matches the particular purpose, include the data block as part of the operation.

2. The system of claim 1, wherein the operation is performed to service an access request for data stored in one of a plurality of zones in the data store, wherein data blocks assigned to the particular purpose are data blocks assigned to the one zone, wherein the metadata in the data block comprises a zone identifier indicating a zone assigned to the data block, and wherein to evaluate the metadata to determine that the assigned purpose for the data block included in the metadata matches the particular purpose, the storage manager is further configured to evaluate the zone identifier to determine that the assigned zone matches the one zone.

3. The system of claim 1, wherein the storage manager is further configured to:

access another data block of the plurality of data blocks as part of the operation utilizing data blocks assigned to the particular purpose, and wherein the accessing comprises;

read metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluate the metadata to determine that an assigned purpose for the other data block indicated by the metadata does not match the particular purpose; and

in response to the determination that the assigned purpose for the other data block does not match the particular purpose, exclude the other data block from the operation.

4. The system of claim 1, wherein the operation is performed upon recovery of a system failure to detect an end of a log stored in the data store, wherein data blocks assigned to the particular purpose are data blocks assigned to store respective log records for the log, wherein the metadata in the data block comprises a block identifier indicating that the data block stores a portion of the log and a location of the data block in a logical sequence of at least some of the plurality of data blocks, wherein to evaluate the metadata to determine that the assigned purpose for the data block included in the metadata matches the particular purpose, the storage manager is configured to evaluate the identifier to determine that the data block stores the log record, and wherein the storage manager is further configured to:

perform the access for other ones of the plurality of data blocks as part of the operation;

evaluate block identifiers of those data blocks included in the operation, including the block identifier of the data block, to identify a data block with a highest block identifier that is contiguous with a previous block identifier as the end of the log.

5. The system of claim 1, wherein the storage manager is further configured to:

access another data block of the plurality of data blocks as part of the operation utilizing data blocks assigned to the particular purpose, and wherein the access comprises;

read metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluate the metadata to determine that the other data block is erroneous; and

in response to the determination that that the other data block is erroneous, exclude the other data block from the operation.

6. The system of claim 1, wherein the storage manager is further configured to:

access another data block of the plurality of data blocks as part of the operation utilizing data blocks assigned to the particular purpose, and wherein the accessing comprises;

read metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluate the metadata to determine that the other data block is erroneous; and

in response to the determination that that the other data block is erroneous, initiate a recovery operation to obtain data stored in the other data block.

7. A method, comprising:

performing, by one or more computing devices;

accessing a data block of the plurality of data blocks as part of an operation dependent on respective indicators for the data blocks stored in respective metadata for the data blocks, and wherein the access comprises;

reading the metadata stored in the data block, wherein the metadata was stored along with other contents of the data block within an individual atomic write operation to the data block by the at least one persistent storage device;

evaluating the metadata to determine that the data block and the indicator in the metadata is not erroneous for performing the operation; and

in response to determining that the data block and the indicator in the metadata is not erroneous for performing the operation, including the data block as part of the operation.

8. The method of claim 7, wherein the operation is performed to access data blocks assigned to a particular purpose, wherein the respective indicators identify an assigned purpose for the data blocks, and wherein evaluating the metadata to determine that the data block and the indicator in the metadata is not erroneous for performing the operation comprises determining that the assigned purpose for the data block matches the particular purpose.

9. The method of claim 7, further comprising:

accessing another data block of the plurality of data blocks as part of the operation, and wherein the accessing comprises;

reading metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluating the metadata to determine that the indicator in the metadata is erroneous for performing the operation; and

in response to determining that the indicator in the metadata is erroneous for performing the operation, excluding the other data block from the operation.

10. The method of claim 9, wherein the respective indicators are an assigned purpose for the data blocks, wherein the operation is performed to access data blocks assigned to a particular purpose, and wherein the method further comprises:

maintaining purpose assignments for the plurality of data blocks, wherein the purpose assignments indicate that the data block is assigned to the particular purpose and the other data block is assigned to a different purpose;

prior to performing the operation, modifying the purpose assignments to indicate that the other data block is assigned to the particular purpose;

wherein the operation identifies the data block and the other data block for accessing based on the purpose assignments;

wherein the indicator stored in the other data block indicates that the other data block is assigned to the different purpose.

11. The method of claim 7,

wherein the operation is performed upon recovery of a system failure to detect an end of a log stored in the data store, wherein the data blocks store respective log records for the log, wherein the respective indicators in the data blocks are block identifiers indicating that the data blocks store respective portions of the log and respective locations of the data blocks in a logical sequence of at least some of the plurality of data blocks;

wherein the method further comprises;

performing said accessing for other ones of the plurality of data blocks as part of the operation; and

evaluating block identifiers of those data blocks included in the operation, including the block identifier of the data block, to identify a data block with a highest block identifier that is contiguous with a previous block identifier as the end of the log.

12. The method of claim 7, further comprising:

accessing another data block of the plurality of data blocks as part of the operation, and wherein the accessing comprises;

reading metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluating the metadata to determine that data stored in the data block is erroneous for performing the operation; and

in response to determining that the data stored in the data block is erroneous for performing the operation, excluding the other data block from the operation.

13. The method of claim 7, further comprising:

accessing another data block of the plurality of data blocks as part of the operation, and wherein the accessing comprises;

reading metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluating the metadata to determine that data stored in the data block is erroneous for performing the operation; and

in response to determining that the data stored in the data block is erroneous for performing the operation, initiating a recovery operation to obtain a valid version of the data stored in the other data block.

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

accessing a data block of the plurality of data blocks as part of an operation dependent on respective indicators for the data blocks stored in respective metadata for the data blocks, and wherein the access comprises;

reading the metadata stored in the data block, wherein the metadata was stored along with other contents of the data block within an individual atomic write operation to the data block by the at least one persistent storage device;

evaluating the metadata to determine that the data block and the indicator in the metadata is not erroneous for performing the operation; and

in response to determining that the data block and the indicator in the metadata is not erroneous for performing the operation, including the data block as part of the operation.

15. The non-transitory, computer-readable storage medium of claim 14, wherein the operation is performed to access data blocks assigned to a particular purpose, wherein the respective indicators identify an assigned purpose for the data blocks, and wherein, in evaluating the metadata to determine that the data block and the indicator in the metadata is not erroneous for performing the operation, the program instructions cause the one or more computing devices to implement determining that the assigned purpose for the data block matches the particular purpose.

16. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

accessing another data block of the plurality of data blocks as part of the operation, and wherein the accessing comprises;

reading metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluating the metadata to determine that the indicator in the metadata is erroneous for performing the operation; and

in response to determining that the indicator in the metadata is erroneous for performing the operation, excluding the other data block from the operation.

17. The non-transitory, computer-readable storage medium of claim 16, wherein the respective indicators are an assigned purpose for the data blocks, wherein the operation is performed to access data blocks assigned to a particular purpose, and wherein the program instructions cause the one or more computing devices to further implement:

maintaining purpose assignments for the plurality of data blocks, wherein the purpose assignments indicate that the data block is assigned to the particular purpose and the other data block is assigned to a different purpose;

prior to performing the operation, modifying the purpose assignments to indicate that the other data block is assigned to the particular purpose;

wherein the operation identifies the data block and the other data block for accessing based on the purpose assignments;

wherein the indicator stored in the other data block indicates that the other data block is assigned to the different purpose.

18. The non-transitory, computer-readable storage medium of claim 14,

wherein the operation is performed upon recovery of a system failure to detect an end of a log stored in the data store, wherein the data blocks store respective log records for the log, wherein the respective indicators in the data blocks are block identifiers indicating that the data blocks store respective portions of the log and respective locations of the data blocks in a logical sequence of at least some of the plurality of data blocks;

wherein the program instructions cause the one or more computing devices to further implement;

performing said accessing for other ones of the plurality of data blocks as part of the operation; and

evaluating block identifiers of those data blocks included in the operation, including the block identifier of the data block, to identify a data block with a highest block identifier that is contiguous with a previous block identifier as the end of the log.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

accessing another data block of the plurality of data blocks as part of the operation, and wherein the accessing comprises;

reading metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluating the metadata to determine that data stored in the data block is erroneous for performing the operation; and

in response to determining that the data stored in the data block is erroneous for performing the operation, excluding the other data block from the operation.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

accessing another data block of the plurality of data blocks as part of the operation, and wherein the accessing comprises;

reading metadata stored in the other data block, wherein the metadata is stored within an individual atomic write operation to the other data block by the at least one persistent storage device;

evaluating the metadata to determine that data stored in the data block is erroneous for performing the operation; and

in response to determining that the data stored in the data block is erroneous for performing the operation, initiating a recovery operation to obtain a valid version of the data stored in the other data block.