Systems and methods for atomic storage operations

• US 9,842,128 B2
• Filed: 06/24/2014
• Issued: 12/12/2017
• Est. Priority Date: 08/01/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Talagala, Nisha, Flynn, David, Sundararaman, Swaminathan, Subramanian, Sriram, Nellans, David, Wipfel, Robert, Strasser, John
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US14/313,933
• Publication Number:
  US 20150039577A1
• Time in Patent Office: 1,267 Days
• Field of Search: 707703
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

An atomic storage module may be configured to implement atomic storage operation directed to a first set of identifiers in reference to a second, different set of identifiers. In response to completing the atomic storage operation, the atomic storage module may move the corresponding data to the first, target set of identifiers. The move operation may comprise modifying a logical interface of the data. The move operation may further include storing persistent metadata configured to bind the data to the first set of identifiers.

Claims

1. A method, comprising:

implementing an atomic storage request, the atomic storage request corresponding to an address space, wherein a translation layer maps identifiers of the address space to data stored on a non-volatile storage medium, and wherein implementing the atomic storage request comprises;

executing a plurality of storage operations corresponding to the atomic storage request, the plurality of storage operations comprising a write to a specified target identifier of the atomic storage request, wherein executing the write comprises storing a data segment on the non-volatile storage medium with a transactional identifier, the transactional identifier different from the specified target identifier of the atomic storage request; and

committing the atomic storage request in response to completing execution of the plurality of storage operations corresponding to the atomic storage request, wherein committing the atomic storage request comprises recording persistent metadata that associates the specified target identifier of the atomic storage request with the stored data segment, such that the translation layer maps the specified target identifier to the data segment stored with the transactional identifier on the non-volatile storage medium.

2. The method of claim 1, wherein storing the data segment comprises appending the data segment to a log on the non-volatile storage medium, the data segment comprising first mapping metadata that associates the appended data segment with the transactional identifier.

3. The method of claim 2, wherein recording the persistent metadata comprises appending second mapping metadata to the log on the non-volatile storage medium, the second mapping metadata associating the appended data segment with the specified target identifier and following the first mapping metadata in the log, the method further comprising:

determining that the second mapping metadata replaces the first mapping metadata based on the second mapping metadata following the first mapping metadata in the log, such that the translation layer associates the appended data segment with the specified target identifier of the second mapping metadata rather than the transactional identifier of the first mapping metadata.

4. The method of claim 1, wherein storing the data segment further comprises associating a storage address of the data segment stored on the non-volatile storage medium with the transactional identifier in the translation layer.

5. The method of claim 4, wherein committing the atomic storage request further comprises replacing, in the translation layer, an association between the transactional identifier and the storage address with an association between the specified target identifier and the storage address.

6. The method of claim 1, wherein committing the atomic storage request further comprises writing the persistent metadata on the non-volatile storage medium in a single operation, the method further comprising acknowledging completion of the atomic storage request in response to determining that the single operation will result in storing the persistent metadata on the non-volatile storage medium.

7. An apparatus, comprising:

a storage layer configured to perform storage operations on a storage device and to manage storage metadata that maps identifiers of a logical address space to data stored on the storage device; and

a storage interface configured to receive a storage request, the storage request comprising a plurality of storage operations and pertaining to a first set of identifiers of the logical address space;

wherein the storage layer is configured to service the storage request, and wherein to service the storage request the storage layer is configured to;

perform the plurality of storage operations of the storage request on the storage device within a second set of identifiers, different from the first set of identifiers, wherein performing the plurality of storage operations comprises storing data segments on the storage device with identifiers of the second set of identifiers, and

move the storage operations of the storage request to the first set of identifiers in response to performing the plurality of storage operations of the storage request,

wherein moving the storage operations comprises writing a persistent note that associates identifiers of the first set of identifiers with the data segments stored on the storage device with the identifiers of the second set of identifiers, such that the storage metadata maps the identifiers of the first set of identifiers to the stored data segments.

8. The apparatus of claim 7, wherein:

storing the data segments with the identifiers of the second set of identifiers comprises mapping the identifiers of the second set of identifiers to the stored data segments in the storage metadata; and

moving the storage operations comprises unmapping the identifiers of the second set of identifiers from the stored data segments in the storage metadata.

9. The apparatus of claim 7, wherein the storage layer is configured to acknowledge completion of the storage request in response to determining that the persistent note will be stored on the storage device.

10. The apparatus of claim 7, wherein:

the first set of identifiers comprises a plurality of disjoint sets of identifiers; and

the persistent note is configured to bind the data segments written on the storage device with the identifiers of the second set of identifiers to respective identifiers within the plurality of disjoint sets of identifiers.

11. The apparatus of claim 7, wherein the storage layer is configured to allocate the second set of identifiers within one of:

a different address space from the logical address space, and a designated region of the logical address space.

12. The apparatus of claim 7, wherein:

writing the data segments with the identifiers of the second set of identifiers comprises appending first mapping metadata to an ordered log maintained on the storage device, the first mapping metadata associating the data segments stored on the storage device with the identifiers of the second set of identifiers,

storing the persistent note comprises appending second mapping metadata to the ordered log, the second mapping metadata associating the stored data segments with the identifiers of the first set of identifiers and being ordered after the first mapping metadata in the ordered log, and

the second mapping metadata overrides the first mapping metadata based on being ordered after the first mapping metadata in the ordered log.

13. The apparatus of claim 7, wherein:

the storage layer is configured to write translation metadata on the storage device, the translation metadata configured to record associations between the storage operations performed on the storage device and respective identifiers, the second set of identifiers comprises identifiers of a transactional address space,

the storage layer is configured to rebuild the storage metadata by use of the translation metadata written on the storage device, and rebuilding the storage metadata comprises invalidating data stored on the storage device associated with the identifiers of the transactional address space by the translation metadata.

14. The apparatus of claim 7, wherein the storage layer is configured to invalidate one of the identifiers within the first set of identifiers in response to moving a storage operation configured to invalidate data of one of the identifiers in the second set of identifiers.

15. The apparatus of claim 7, wherein the storage layer is further configured to append the data segments pertaining to the storage request to an ordered log on the storage device, and wherein a data segment that does not pertain to the storage request is appended between two or more data segments that pertain to the storage request within the ordered log.

16. A system, comprising:

means for executing an atomic storage request pertaining to identifiers of a set of destination identifiers, comprising;

translation means for mapping identifiers to data stored on a storage device;

means for appending a plurality of data packets pertaining to the atomic storage request to a sequential storage log on the storage device, wherein the data packets comprise persistent metadata configured to associate the data packets with respective transactional identifiers, different from the identifiers of the set of destination identifiers; and

means for appending a persistent note to the sequential storage log responsive to appending the plurality of data packets pertaining to the atomic storage request to the sequential storage log, wherein;

the persistent note is configured to associate the plurality of data packets appended to the sequential storage log with respective identifiers of the set of destination identifiers, such that the translation means maps the plurality of data packets appended to the sequential storage log to respective identifiers of the set of destination identifiers, and

the means for executing the atomic storage request comprises one or more of instructions stored on a non-transitory storage medium, a circuit, a configurable circuit, and firmware.

17. The system of claim 16, further comprising means for linking identifiers of the set of destination identifiers to respective transactional identifiers.

18. The system of claim 16, further comprising means for binding one or more of the transactional identifiers to a storage location associated with an identifier of the set of destination identifiers.

19. The system of claim 16, further comprising means for providing access to the data packets comprising the persistent metadata configured to associate the data packets with respective transactional identifiers using respective identifiers of the set of destination identifiers.

20. The system of claim 16, wherein the identifiers of the set of destination identifiers correspond to a first address space, and wherein the transactional identifiers correspond to a second address space, different from the first address space, the system further comprising:

means for reconstructing mappings between identifiers of the first address space and the data packets stored on the storage device by use of the persistent metadata of the data packets; and

means for invalidating data packets associated with transactional identifiers corresponding to the second address space.