Log-based data storage on sequentially written media

• US 9,779,035 B1
• Filed: 08/08/2012
• Issued: 10/03/2017
• Est. Priority Date: 08/08/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Patiejunas, Kestutis
• Primary Examiner(s): Yi, David X
• Assistant Examiner(s): Puche, Tahilba
• Application Number:
  US13/569,984
• Time in Patent Office: 1,882 Days
• CPC Class Codes: G06F 13/00 Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units interface circuits for specific input/output devices G06F3/00 ; multiprogram control therefor G06F9/46; multiprocessor systems G06F15/16
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Techniques for implementing a log-based storage scheme upon data storage devices are described herein. A data storage device is initialized by writing an identifying record. For each portion of data to be written to the drive, a first record including information regarding the anticipated nature of the portion of data is written prior to the data. The data is then written as a second record that includes at least the raw data as well as integrity verification information. A third record is stored following the second record, and includes an accounting and/or index of the data successfully written in the second record. On sequentially written devices, the information in the first stored record may be used to locate the third record, which in turn may be used to record data in the second record as well as the location of a first record of another portion of data.

Claims

1. A computer-implemented method for storing data, comprising:

under the control of one or more computer systems configured with executable instructions,

provisioning a hardware storage device by at least storing an initialization record, the initialization record that at least identifies at least a time at which data are first stored upon the hardware storage device, the hardware storage device having a media surface upon which data are to be sequentially stored;

at a time after receiving a data write request, at least;

storing, upon the media surface, a first record that includes at least;

a data write identifier that identifies a position of the data write request within a sequence;

information that includes an intended size, as stored upon the media surface, of data associated with the data write request; and

information that indicates a location of a third record upon the media surface;

storing, sequentially adjacent to and sequentially after the first record, upon the media surface, a second record that includes at least one or more data pages that each include at least;

one or more subsets of the data associated with the write request;

information that enables verification of integrity of the one or more subsets of the associated data; and

information identifying at least an association between the first record and the second record; and

storing, sequentially adjacent to and sequentially after the second record, upon the media surface, the third record, the third record including at least;

information about which of the data pages were successfully stored in the second record; and

information that enables location of at least the successfully stored subsets of data within the second record;

in response to a read request for a subset of the data, at least;

locating the third record by at least analyzing the first record;

processing the third record to determine the location of at least an associated subset of the stored data subsets in the second record; and

retrieving the associated subset from the determined location.

2. The computer-implemented method of claim 1, wherein the one or more computer systems and the hardware storage device are connected via one or more network connections.

3. The computer-implemented method of claim 1, wherein the first record, the second record, and the third record are collectively included in a data set among a plurality of data sets that are sequentially stored upon the media surface.

4. The computer-implemented method of claim 3, wherein:

a first data set among the plurality of data sets is sequentially located immediately after the initialization record; and

the first record of each of the remaining data sets among the plurality of data sets is sequentially located immediately after the third record of the sequentially preceding data set.

5. The computer-implemented method of claim 3, further comprising storing, at predetermined locations upon the media surface, at least one checkpoint record that includes at least aggregated information that enables location of the stored subsets of data that sequentially precede the checkpoint record upon the media surface.

6. The computer-implemented method of claim 3, wherein the location of the third record and the processing of the third record are sequentially performed for each stored data set.

7. The computer-implemented method of claim 1, wherein the location of the third record and the processing of the third record is performed in response to receiving a data read request.

8. A computer-implemented method for storing data, comprising:

under the control of one or more computer systems configured with executable instructions,

initializing, by at least storing an initial identification record, a data storage device upon which data are sequentially stored;

storing, upon the data storage device, a first record that includes information about data that are intended to be written to the data storage device, information that indicates a location of a third record upon the data storage device, and at least a portion of the initial identification record;

storing, sequentially adjacent to and sequentially after the first record upon the data storage device, a second record that includes at least the data intended to be written;

storing, sequentially adjacent to and sequentially after the second record upon the data storage device, the third record that includes at least information that enables location of at least a subset of the written data that was successfully written; and

determining a location of the third record by at least analyzing the first record.

9. The computer-implemented method of claim 8, wherein at least the storing of the first record, the storing of the second record, and the storing of the third record are in response to a data write request associated with the data intended to be written.

10. The computer-implemented method of claim 8, further comprising storing, at predetermined locations upon the data storage device, at least one checkpoint record that enables location of stored data that sequentially precede the checkpoint record on the data storage device.

11. The computer-implemented method of claim 10, wherein the first record, the second record, and the third record are collectively included in a data set among a plurality of data sets stored upon the data storage device, and further comprising generating a state of the data storage device by at least:

analyzing, at the sequentially last predetermined location, the checkpoint record to determine the location of the successfully written data sequentially preceding the checkpoint record;

for each data set sequentially after the checkpoint record and sequentially preceding a pointer that indicates a final sequential write location of the data storage device, at least;

analyzing the first record of each data set to determine the location of the third record; and

analyzing the located third record of each data set to determine the location of the subset of successfully written data associated with the data set.

12. The computer-implemented method of claim 8, wherein the data storage device is capable of random read access to stored data.

13. A data storage system, comprising:

one or more processors; and

memory, including instructions executable by the one or more processors to cause the data storage system to at least;

requisition a data storage medium upon which data are sequentially stored by at least identifying the data storage medium as containing data written after a given generation of the data;

record, in a first record, at least information about data intended to be written to the data storage medium and a location of a third record;

record, in a second record, and sequentially adjacent to and sequentially after the first record upon the data storage media, at least the data intended to be written to the data storage medium and integrity information associated with the recorded data;

record, in the third record, sequentially adjacent to and sequentially after the second record upon the data storage media, at least a catalog that enables location of at least a subset of the data intended to be written that was successfully recorded in the second record; and

determine a location of the third record by processing the information in the first record.

14. The data storage system of claim 13, wherein the first record and the third record are recorded upon different write zones of the data storage medium.

15. The data storage system of claim 13, wherein the data storage medium utilizes shingled magnetic recording techniques.

16. The data storage system of claim 13, wherein the data storage medium includes tape media.

17. The data storage system of claim 13, wherein the instructions further cause the data storage system to, at a time after receiving a request to delete at least a subset of the successfully recorded data, enable a fourth record, stored sequentially after the third record, to disable location of the successfully recorded data associated with the request.

18. The data storage system of claim 14, wherein the first record, the second record, and the third record are collectively included in a data set among a plurality of data sets stored on the data storage medium, and wherein the instructions further cause the data storage system to generate a state of the data storage medium by at least:

for each stored data set sequentially preceding a pointer that indicates a final sequential write location of the data storage medium, at least;

analyzing the first record of each data set to determine the location of the third record; and

analyzing metadata within the catalog of the located third record to determine which subset of successfully recorded data is associated with the data set.

19. One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, when executed by one or more processors of a computing resource provider'"'"'s computer system, cause the computer system to at least:

initialize a second storage medium operatively connected to the computer system by at least storing, upon the second storage medium, an identity record that includes at least information relating to a write state of the second storage medium, the second storage medium, at least in part, written sequentially;

recording, upon the second storage medium, a first record that contains at least information relating to a write request received by the computer system, at least a portion of the identity record, and a location of a third record on the second storage medium;

recording, sequentially adjacent to and sequentially after the first record upon the second storage medium, a second record that contains at least;

data associated with the write request; and

verification values associated with the data and generated by the computer system; and

recording, sequentially adjacent to and sequentially after the second record upon the data storage media upon the second storage medium, an index that enables location of the data recorded in the second record and, if a subset of the data was written unsuccessfully in the second record, includes information identifying unsuccessfully written data within the first record.

20. The non-transitory computer-readable storage media of claim 19, wherein the instructions cause the computer system to further:

collectively record the first record, the second record and the index as a data set in response to the write request; and

in response to further write requests, sequentially append upon the second storage medium additional data sets in response to the further write requests.

21. The non-transitory computer-readable storage media of claim 19, wherein the data associated with the write request is recorded as one or more data pages of predetermined size within the second record.

22. The non-transitory computer-readable storage media of claim 19, wherein the write request is received through a programmatic interface enabled by the computer system.

23. The non-transitory computer-readable storage media of claim 19, wherein the storage media and the second storage medium are co-located within a common physical chassis.

24. The non-transitory computer-readable storage media of claim 19, wherein the second storage medium is configured to write data using shingled magnetic recording techniques.