Systems, methods, and interfaces for managing persistent data of atomic storage operations

• US 10,133,662 B2
• Filed: 06/29/2012
• Issued: 11/20/2018
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Peterson, James G., Batwara, Ashish, Talagala, Nisha, Zappe, Michael
• Primary Examiner(s): Sain, Gautam
• Application Number:
  US13/539,235
• Publication Number:
  US 20140006685A1
• Time in Patent Office: 2,335 Days
• Field of Search: 711150
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A storage controller is configured to implement an atomic storage operation comprising a plurality of separate storage operations on a non-volatile storage medium. The storage controller may store persistent indicators to identify data that pertains to the atomic storage operation. An invalid shutdown may occur before the atomic storage operation is complete. A restart and recovery operation comprises a first scan of the non-volatile storage medium to identify data of the failed atomic storage operation. A physical trim note is stored on the non-volatile storage medium to identify the data of the failed atomic storage operation. The data may be identified by media address. Storage metadata is reconstructed in a second scan, which excludes the data and/or operations of the failed atomic storage operation.

Claims

1. An apparatus, comprising:

a non-volatile storage medium; and

a processor configured to execute atomic storage operations on the non-volatile storage medium, wherein executing an atomic operation comprises storing first persistent metadata indicating that the atomic storage operation is incomplete and, in response to completing execution of the atomic storage operation on the non-volatile storage medium, storing second persistent metadata indicating that the atomic storage operation is complete;

wherein the processor is further configured to perform a first scan of the non-volatile storage medium, the first scan comprising;

locking access to all of the non-volatile storage medium during the first scan,

identifying data of a failed atomic storage operation stored on one or more storage locations of the non-volatile storage medium in response to accessing first persistent metadata pertaining to the failed atomic storage operation, and

writing third persistent metadata on the non-volatile storage medium, the third persistent metadata configured to invalidate the identified data stored on the one or more storage locations independent of the first persistent metadata, wherein the third persistent metadata is appended to the identified data such that the third persistent metadata is written to a first storage location immediately following the one or more storage locations of the identified data, wherein the first storage location is different from a second storage location comprising the first persistent metadata; and

wherein the processor is further configured to perform a second scan of the non-volatile storage medium, the second scan comprising;

rebuilding an index comprising associations between data stored on the non-volatile storage medium and logical identifiers of a logical address space based on one or more of the first, second, and third persistent metadata, and

unlocking access to the non-volatile storage medium in response to rebuilding the index.

2. The apparatus of claim 1, wherein the first scan comprises accessing data stored on the non-volatile storage medium according to a log order defined, at least in part, by sequence indicators stored on the non-volatile storage medium.

3. The apparatus of claim 1, wherein the processor is further configured to invalidate the identified data stored on the one or more storage locations of the non-volatile storage medium in an index, the index comprising associations between logical identifiers and corresponding data stored on the non-volatile storage medium.

4. The apparatus of claim 3, wherein the processor is further configured to record that the identified data stored on the one or more storage locations of the non-volatile storage medium is invalid in one or more of a reverse index and a validity bitmap.

5. The apparatus of claim 1, wherein the third persistent metadata comprises a media address of the one or more storage locations.

6. The apparatus of claim 1, wherein the processor is configured to lock access to the non-volatile storage medium during the first scan by one or more of:

locking storage request execution until completion of the first scan, deferring storage request execution until completion of the first scan, queueing storage requests until completion of the first scan, and rejecting storage requests until completion of the first scan.

7. The apparatus of claim 1, wherein the processor is configured to identify the data of the failed atomic storage operation in response to determining that second metadata pertaining to the failed atomic storage operation is not stored on the non-volatile storage medium.

8. The apparatus of claim 7, wherein the processor is configured to identify the data of the failed atomic storage operation during the first scan in response to detecting a data packet stored on the non-volatile storage medium comprising the first persistent metadata pertaining to the failed atomic storage operation and failing to detect that the data packet comprises the second persistent metadata pertaining to the failed atomic storage operation stored on the non-volatile storage medium.

9. The apparatus of claim 1, wherein the first scan comprises accessing data from a head of an ordered log maintained on the non-volatile storage medium towards a tail of the log.

10. The apparatus of claim 1, wherein the second scan further comprises:

recording associations between valid data stored on the non-volatile storage medium and corresponding logical addresses in a forward map in response to accessing the valid data during the first scan; and

excluding the identified data of the failed atomic storage request from the forward map based on the third persistent metadata stored on the non-volatile storage medium irrespective of whether or not the first persistent metadata or the second persistent metadata pertaining to the failed atomic storage operation is present on the non-volatile storage medium.

11. The apparatus of claim 1, wherein the second scan further comprises:

reconstructing associations between logical identifiers of data accessed during the second scan and storage locations of the accessed data based upon one or more of the first, second, and third persistent metadata stored with the accessed data on the non-volatile storage medium; and

recording the reconstructed associations in the index.

12. The apparatus of claim 11, wherein the second scan further comprises:

excluding the identified data of the failed atomic storage request based on the third persistent metadata stored on the non-volatile storage medium.

13. The apparatus of claim 1, wherein the third persistent metadata comprises logical identifiers corresponding to the failed atomic storage operation.

14. The apparatus of claim 1, wherein the processor is configured to perform the first scan of the non-volatile storage medium in response to detecting an invalid shutdown.

15. The apparatus of claim 14, wherein the processor is configured to detect the invalid shutdown by accessing the non-volatile storage medium.

16. The apparatus of claim 1, wherein the processor is further configured to erase the third persistent metadata from the non-volatile storage medium in response to determining that the data of the failed atomic storage operation is no longer stored on the one or more storage locations of the non-volatile storage medium.

17. A method, comprising:

using a processor of a computing device to implement atomic operations on a non-volatile storage medium, wherein implementing an atomic operation comprises writing a first note indicating that the atomic operation is incomplete and, in response to completing the atomic operation, writing a second note indicating that the atomic operation is complete;

using the processor of the computing device to perform a first scan of the non-volatile storage medium, comprising;

blocking execution of storage requests on all of the non-volatile storage medium during the first scan,

detecting data of a failed atomic storage operation stored on one or more storage locations of the non-volatile storage medium in response to accessing a first note indicating that the failed atomic storage operation is incomplete and determining that a second note indicating that the failed atomic operation is complete was not written on the non-volatile storage medium, and

writing a third note on the non-volatile storage medium in response to the detecting, wherein the third note is written separately from the first note and is configured to invalidate the detected data of the failed atomic storage operation independent of the first note, the third note comprising a media address of the detected data, wherein the third note is appended to the detected data such that the third note is written to a first storage location immediately following the one or more storage locations of the detected data, wherein the first storage location is different from a second storage location comprising the first note, and

using the processor of the computing device to perform a second scan of the non-volatile storage medium, the second scan comprising;

accessing persistent metadata stored on the non-volatile storage device,

recording translation entries in a memory of the computing device, the translation entries configured to associate media addresses of data stored on the non-volatile storage medium with respective logical identifiers of the data,

excluding a translation entry corresponding to the detected data of the failed atomic storage operation based on the third note written on the non-volatile storage medium during the first scan, and

unlocking access to the non-volatile storage medium in response to completing the second scan.

18. The method of claim 17, wherein the second scan of the non-volatile storage medium comprises accessing the persistent metadata stored on the non-volatile storage medium in a log order, the log order determined by sequence indicators stored on storage divisions of the non-volatile storage medium.

19. The method of claim 17, wherein detecting the data of the failed atomic storage operation further comprises:

accessing the first note pertaining to the failed atomic operation stored on the non-volatile storage medium; and

determining that the second note pertaining to the failed atomic operation is not stored on the non-volatile storage medium.

20. The method of claim 17, wherein detecting data of the failed atomic storage operation further comprises:

determining that one or more data packets comprising the detected data of the failed atomic storage operation stored on the non-volatile storage medium include the first note; and

completing the first scan of the non-volatile storage medium without accessing a data packet that includes the second note pertaining to the failed atomic operation.

21. A system, comprising:

means for performing atomic storage operations on a non-volatile storage medium, wherein performing an atomic storage operation comprises storing first persistent metadata indicating that the atomic storage operation is incomplete and second persistent metadata indicating that the atomic storage operation is complete in response to completing the atomic storage operation on the non-volatile storage medium;

means for performing a scan of the non-volatile storage medium, comprising;

means for locking access to all of the non-volatile storage medium during the scan;

means for accessing first persistent metadata pertaining to a particular atomic storage operation stored at one or more storage addresses of the non-volatile storage medium during the scan;

means for determining that the particular atomic storage operation is incomplete in response to failing to access second persistent metadata pertaining to the particular atomic storage operation during the scan; and

means for storing third persistent metadata on the non-volatile storage medium in response to the determining, the third persistent metadata configured to invalidate data corresponding to the particular atomic storage operation independent of the first persistent metadata, wherein the third persistent metadata is appended to the data corresponding to the particular atomic storage operation such that the third persistent metadata is stored at a first storage address immediately following the one or more storage addresses of the data corresponding to the particular atomic storage operation, wherein the first storage address is different from a second storage address of the first persistent metadata; and

means for performing a second scan of the non-volatile storage medium, comprising;

means for rebuilding an index comprising associations between data stored on the non-volatile storage medium and logical identifiers of a logical address space based on one or more of the first, second, and third persistent metadata; and

means for unlocking access to the non-volatile storage medium in response to rebuilding the index.