Systems and methods for persistent atomic storage operations

• US 9,323,465 B2
• Filed: 02/20/2015
• Issued: 04/26/2016
• Est. Priority Date: 03/18/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Wipfel, Robert, Nellans, David, Strasser, John
• Primary Examiner(s): Chery, Mardochee
• Application Number:
  US14/627,869
• Publication Number:
  US 20150160879A1
• Time in Patent Office: 431 Days
• Field of Search: 711/103
• US Class Current: 1/1
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0634 by changing the state or mode of one or more devices
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 16/06 Auxiliary circuits, e.g. for writing into memory

Abstract

A storage layer presents logical address space of a non-volatile storage device. The storage layer maintains logical interfaces to the non-volatile storage device, which may include arbitrary, any-to-any mappings between logical identifiers and storage resources. Data may be stored on the non-volatile storage device in a contextual format, which includes persistent metadata that defines the logical interface of the data. The storage layer may modify the logical interface of data that is stored in the contextual format. The modified logical interface may be inconsistent with the existing contextual format of the data on the non-volatile storage media. The storage layer may provide access to the data in the inconsistent contextual format through the modified logical interface. The contextual format of the data may be updated to be consistent with the modified logical interface in a write out-of-place storage operation.

Claims

1. An apparatus, comprising:

a storage controller configured to perform an atomic transaction on a storage medium, wherein performing the atomic transaction comprises storing a plurality of data blocks for the atomic transaction on the storage medium, each data block corresponding to a respective logical identifier of a logical address space, wherein storing a data block for the atomic transaction comprises designating the stored data block for invalidation by associating the stored data block with a logical identifier of a designated set of logical identifiers that differs from the logical identifier corresponding to the data block; and

a reconstruction module configured to invalidate stored data blocks that are associated with logical identifiers of the designated set of logical identifiers.

2. The apparatus of claim 1, wherein the storage controller is further configured to associate the stored data block with the logical identifier corresponding to the data block in response to storing the plurality of data blocks for the atomic storage transaction on the storage medium.

3. The apparatus of claim 1, wherein the reconstruction module is configured to identify stored data blocks that are associated with the logical identifiers of the designated set of logical identifiers in response to an invalid shutdown.

4. The apparatus of claim 1, wherein the storage controller is configured to associate the stored data block with the logical identifier of the designated set of logical identifiers by writing persistent data to the storage medium, and wherein the reconstruction module is configured to identify the stored data blocks of the atomic transaction that is associated with the logical identifier of the designated set of logical identifiers by use of the persistent data written to the storage medium.

5. The apparatus of claim 1, wherein storing the data block comprises storing the data block with persistent metadata that comprises the logical identifier of the designated set of logical identifiers on the storage medium, and wherein the storage controller is further configured to store persistent metadata on the storage medium to associate the stored data block with the logical identifier corresponding to the data block in response to storing the plurality of data blocks for the atomic storage transaction on the storage medium.

6. The apparatus of claim 5, wherein the reconstruction module is configured to invalidate the stored data block in response to determining that the stored data block is associated with the logical identifier of the designated set of logical identifiers.

7. The apparatus of claim 5, wherein the storage controller is configured to determine that the stored data block comprises valid data in response to determining that the stored data block is associated with the logical identifier corresponding to the data block.

8. The apparatus of claim 1, wherein the designated set of logical identifiers comprise one or more of a range of logical identifiers of the logical address space, an extent of the logical address space, a subset of the logical address space, and logical identifiers of an address space that is separate from the logical address space of the logical identifiers corresponding to the data blocks.

9. The apparatus of claim 1, wherein the storage controller is configured to cancel the invalidation designation of the stored data block by associating the stored data block with the logical identifier corresponding to the data block in response to storing the plurality of data blocks for the atomic transaction on the storage medium.

10. The apparatus of claim 1, wherein the storage controller comprises a log storage module configured to append data blocks as packets in a storage log on the storage medium, to designate the stored data block for invalidation by associating the stored data block with the logical identifier of the designated set by use of a header of a packet comprising the stored data block, and to remove the invalidation designation from the stored data block by appending a persistent note to the storage log configured to associate the stored data block with the logical identifier corresponding to the data block.

11. A system, comprising:

a storage interface configured to receive an atomic storage request;

a log storage module configured to complete the atomic storage request, wherein completing the atomic storage request comprises writing a plurality of data segments of the atomic storage request to a storage log on a non-volatile storage medium, each data segment being associated with a respective one of a first set of logical addresses;

wherein the log storage module is configured to write the plurality of data segments to the storage log with persistent metadata that maps the data segments to respective logical addresses of a second set of logical addresses that differ from the logical addresses of the first set of logical addresses,

wherein the log storage module is configured to invalidate the persistent metadata that maps the data segment to the logical address of the second set of logical addresses in response to completing the atomic storage request; and

a translation layer configured to maintain logical address mappings between logical addresses and data segments of the storage log, wherein the translation layer is configured to invalidate data segments of the storage log that are mapped to logical addresses in the second set of logical addresses.

12. The system of claim 11, wherein the log storage module is configured to write a persistent note to the storage log that invalidates mappings between the data segments of the atomic storage request and logical addresses in the second set of logical addresses in response to completing the atomic storage request.

13. The system of claim 12, wherein the persistent note is configured to map the data segments of the atomic storage request to logical addresses in the first set of logical addresses.

14. The system of claim 11, wherein the translation layer is configured to reconstruct logical address mappings of data segments in the storage log by use of the persistent metadata of the data segments stored within the storage log, and wherein the translation layer is configured to ignore logical address mappings pertaining to data segments that are associated with logical addresses in the second set of logical addresses.

15. The system of claim 11, wherein completing the atomic storage request further comprises associating a particular data segment stored in the storage log that maps to a particular logical identifier with a logical identifier in the second set of logical identifiers such that the particular data segment is mapped to both the particular logical identifier and the logical identifier in the second set of logical identifiers.

16. A method, comprising:

servicing an atomic storage request comprising a plurality of storage operations, each storage operation comprising storage of a respective data segment corresponding to a respective logical address on a non-volatile storage medium, wherein servicing the atomic storage request comprises;

storing data segments of the atomic storage request on the non-volatile storage medium, wherein storing the data segments comprises assigning the stored data segments to respective logical addresses of a designated extent of logical addresses, wherein the assigned logical addresses differ from the logical addresses corresponding to the respective data segments, and

writing persistent metadata on the non-volatile storage medium to assign the stored data segments to the logical address corresponding to the respective data segments in response to servicing the plurality of storage operations of the atomic storage request; and

reconstructing assignments between the logical address space and data segments stored on the non-volatile storage medium in response to an invalid shutdown, wherein reconstructing the assignments comprises omitting assignments pertaining to the designated extent of logical addresses.

17. The method of claim 16, wherein assigning a data segment to a logical address of the designated extent of logical addresses comprises one or more of:

writing the logical address of the designated extent within a header of the data segment, and

appending data to a storage log on the non-volatile storage medium indicating that the data segment is assigned to the logical address of the designated extent, and

appending a data packet to the storage log on the non-volatile storage medium, the data packet comprising the data segment and the logical address of the designated extent.

18. The method of claim 16, wherein the persistent metadata written to the non-volatile storage medium indicates that assignments between the stored data segment and the logical addresses of the designated extent are invalid.

19. The method of claim 16, wherein storing the data segments of the atomic storage request comprises appending the data segments to a storage log on the non-volatile storage medium, and wherein writing the persistent metadata on the non-volatile storage medium comprises appending a persistent note to the storage log wherein the persistent note establishes assignments between the stored data segments of the atomic storage request and the logical addresses corresponding to the respective data segments.

20. The method of claim 16, wherein reconstructing the assignments between the logical address space and data segments stored on the non-volatile storage medium in response to an invalid shutdown further comprises invalidating data segments stored on the non-volatile storage medium that are assigned to logical addresses of the designated extent.

21. The method of claim 16, wherein servicing the atomic storage request further comprises assigning a particular stored data segment that is assigned to a particular logical address to a logical address of the designated extent, such that the particular stored data segment is assigned to the particular logical address and to the logical address of the designated extent of logical addresses.