# US 10,120,579 B1 · Data storage management for sequentially written media > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,120,579 B1 - Document ID: US10120579B1 - Status: Granted - Kind: B1 - Application number: 13/570,057 - Filed: 2012-08-08 - Granted: 2018-11-06 - Earliest claimed: 2012-08-08 - Assignees: Amazon Technologies, Inc. - Applicants: Kestutis Patiejunas; Colin L. Lazier; James Christopher Sorenson, III - Inventors: Kestutis Patiejunas; Colin L. Lazier; James Christopher Sorenson, III - Web page: https://patentgrep.com/patent/US10120579B1 ## CPC - G06F 3/061: {Improving I/O performance} - G06F 3/0613: {in relation to throughput} - G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors} - G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket} - G06F 3/0653: {Monitoring storage devices or systems} - G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling} - G06F 3/0676: {Magnetic disk device} - G11B 5/012: Recording on, or reproducing or erasing from, magnetic disks (G11B17/00, G11B19/00 take precedence) - G11B 5/86: Re-recording, i.e. transcribing information from one magnetisable record carrier on to one or more similar or dissimilar record carriers {(by varying the order of the information G11B27/029, G11B27/036)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R) ## Abstract Techniques for implementing a data management scheme for optimizing data storage are described herein. A deletion quantity or other metric relating to deletions of data within a first storage zone are tracked. Upon detection that the tracked deletion metric meets certain criteria, the data within the first storage zone are moved to a second storage zone. A verification of the data to be moved is also performed, and if such verification indicates that at least a portion of the data is corrupted, routines repairing and/or restoring at least the corrupted portion are initiated. ## Claims ### Claim 1 A computer-implemented method for optimizing data storage, comprising: under the control of one or more computer systems configured with executable instructions, tracking a level of deleted data locations on a first data storage device to which data are sequentially written, the data locations being deleted by updating location information related to the data locations in one or more indexes that are used to access data on the first data storage device; and at a time after the level of deleted data locations reaches a predetermined threshold: locating a second data storage device that is capable of storing the data on the first data storage device; reading the data stored on the first data storage device by at least processing the indexes and omitting data locations that the associated location information indicates have been deleted; verifying integrity of the read data by at least comparing verification values generated from the read data with expected values for the read data; when the comparison of the verification values and the expected values indicates that at least a subset of the read data is corrupted, generating information that relates to the corrupted subset of data; storing the read data upon the second data storage device such that the data locations that have been deleted are absent from one or more indexes that are used to access data on the second data storage device; and initializing the first data storage device so as to render it capable of storing additional data at least on the deleted data locations. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the second data storage device is optimized for sequential data writes. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein both the first data storage device and the second data storage device record data using shingled magnetic recording techniques. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein the data stored on the first data storage device is encoded with a redundancy code, and wherein the corrupted subset of data is restored by using at least the redundancy code to regenerate correct data for the corrupted subset. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein the generated information relating to the corrupted subset of data includes instructions that, when executed by the one or more computer systems, causes the one or more computer systems to restore the corrupted subset of data. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the generated information relating to the corrupted subset of data includes an indication that at least a subset of the corrupted subset of data is invalid. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, wherein the level of deleted data locations is tracked by the first data storage device. ### Claim 8 A computer-implemented method comprising: tracking deletion of sequentially written data in a first storage zone; and at a time after the tracked deletion satisfies one or more conditions: moving at least a portion of data stored on the first storage zone to a second storage zone, wherein the first storage zone and the second storage zone are respectively coincident with a first storage device and a second storage device; verifying the portion of data for integrity using verification values associated with the portion; and as a result of the verification values indicating that at least a subset of the portion is corrupted, at least generating information related to the corrupted subset. ### Claim 9 (depends on 8) The computer-implemented method of claim 8, further comprising initializing the first storage zone at a time after the portion of data has been moved. ### Claim 10 (depends on 8) The computer-implemented method of claim 8, wherein the first storage zone and the second storage zone are located on one physical device, and wherein the level of deletion is tracked by the physical device. ### Claim 11 (depends on 8) The computer-implemented method of claim 8, wherein the one or more conditions include a condition that that a quantity of data elements pending deletion exceeds a threshold. ### Claim 12 (depends on 8) The computer-implemented method of claim 8, wherein the portion of data is verified for integrity while being moved to the second storage zone. ### Claim 13 (depends on 8) The computer-implemented method of claim 8, wherein the verification values include digests generated by applying at least one hash function to the portion of data. ### Claim 14 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: monitor a quantity of deleted subsets of data stored on a first data storage media upon which data are written sequentially; and when the quantity of deleted subsets reaches a predetermined level, at least: transfer the data from the first data storage media to a second data storage media such that the deleted subsets of data are omitted during the transfer; confirm, by at least analyzing integrity information associated with the data, that the data are correctly transferred; and when the analysis of the integrity information indicates that at least a portion of the data was transferred incorrectly, at least generate information relating to the incorrectly transferred data. ### Claim 15 (depends on 14) The data storage system of claim 14, wherein the predetermined level is set by the data storage system so as to optimize for at least one of cost, performance, storage efficiency, or time necessary to transfer the data from the first data storage media to the second data storage media. ### Claim 16 (depends on 14) The data storage system of claim 14, wherein the first data storage media and the second data storage media record data using shingled magnetic recording techniques. ### Claim 17 (depends on 14) The data storage system of claim 14, wherein the quantity of deleted subsets of data is externally queriable through a programmatic interface exposed by the data storage system. ### Claim 18 (depends on 14) The data storage system of claim 14, wherein the data is stored on the first data storage media in one or more data pages, and the integrity information includes, for each data page, a digest value that is calculated based on the data within the data page. ### Claim 19 (depends on 14) The data storage system of claim 14, wherein the instructions further cause the data storage system to, when the analysis indicates that the portion of the data was transferred incorrectly, attempt to retry transferring the incorrectly transferred data. ### Claim 20 One or more non-transitory computer-readable storage media having collectively stored thereon executable instructions that, as a result of execution by one or more processors of a computing resource provider's computer system, cause the computer system to at least: determine if data deletion activity on a first append-optimized data storage zone marked as deleted has reached a defined threshold; at a time after determining that the data deletion activity has reached the defined threshold, initiate compaction of data located in data locations of the first append-optimized data storage zone by at least initiating propagation of the data located in the data locations that are not marked as deleted to a second append-optimized data storage zone; analyze at least integrity information associated with the data to determine whether any portion of the data is corrupted, wherein the integrity information is analyzed at least partially during the propagation of the data; and as a result of a determination that at least one portion of the data is corrupted, reconstitute the at least one portion. ### Claim 21 (depends on 20) The one or more non-transitory computer-readable storage media of claim 20, wherein the data propagated to the second append-optimized data storage zone is stored in a substantially contiguous fashion. ### Claim 22 (depends on 20) The one or more non-transitory computer-readable storage media of claim 20, wherein the first append-optimized data storage zone and the second append-optimized data storage zone are of a plurality of data storage zones on a hardware data storage device. ### Claim 23 (depends on 22) The one or more non-transitory computer-readable storage media of claim 22, wherein at least the compaction of the data is performed by the hardware data storage device. ### Claim 24 (depends on 20) The one or more non-transitory computer-readable storage media of claim 20, wherein the data locations are marked as deleted within one or more indexes associated with the data locations and stored in the first append-optimized data storage zone. ### Claim 25 (depends on 20) The one or more non-transitory computer-readable storage media of claim 20, wherein the executable instructions that cause the computer system to reconstitute the at least one portion include instructions that cause the computer system to: obtain uncorrupted data from another data storage zone; and reconstitute the at least one portion using the uncorrupted data.