Apparatus, system, and method for conditional and atomic storage operations

• US 9,251,062 B2
• Filed: 11/22/2013
• Issued: 02/02/2016
• Est. Priority Date: 09/09/2009
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Flynn, David, Nellans, David, Ouyang, Xiangyong
• Primary Examiner(s): SCHNEE, HAL W
• Application Number:
  US14/087,297
• Publication Number:
  US 20140189216A1
• Time in Patent Office: 802 Days
• Field of Search: 711/103, 711/152, 711/154, 711/162, 711/E12.022
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards

Abstract

An apparatus, system, and method are disclosed for implementing conditional storage operations. Storage clients access and allocate portions of an address space of a non-volatile storage device. A conditional storage request is provided, which causes data to be stored to the non-volatile storage device on the condition that the address space of the device can satisfy the entire request. If only a portion of the request can be satisfied, the conditional storage request may be deferred or fail. An atomic storage request is provided, which may comprise one or more storage operations. The atomic storage request succeeds if all of the one or more storage operations are complete successfully. If one or more of the storage operations fails, the atomic storage request is invalidated, which may comprise deallocating logical identifiers of the request and/or invalidating data on the non-volatile storage device pertaining to the request.

Claims

1. A method, comprising:

storing data of an atomic storage request in one or more storage operations on a non-volatile storage medium of a non-volatile storage device;

allocating one or more logical identifiers to satisfy the atomic storage request in a logical address space of the non-volatile storage device;

in response to completion of the one or more storage operations,

updating storage metadata on the non-volatile storage medium to assign the allocated logical identifiers to storage locations comprising data of the atomic storage request, and

updating the storage metadata to indicate that the atomic storage request is complete; and

in response to failure of one or more of the storage operations, rolling back the atomic storage request by deallocating the allocated logical identifiers in response to failure of one or more of the storage operations.

2. The method of claim 1, further comprising:

storing a persistent indicator on the non-volatile storage medium that indicates the atomic storage request is incomplete; and

storing a persistent indicator on the non-volatile storage medium that indicates the atomic storage request is complete in response to completion of the one or more storage operations.

3. The method of claim 1, further comprising:

storing a persistent indicator on the non-volatile storage medium that indicates the atomic storage request is incomplete; and

invalidating data of the atomic storage request on the non-volatile storage medium when the non-volatile storage medium does not include a persistent indicator that indicates the atomic storage request is complete.

4. The method of claim 1, further comprising rolling back the atomic storage request if one of the updating operations fails.

5. A method, comprising:

receiving an atomic storage request to store data on a non-volatile storage medium of a non-volatile storage device;

allocating, in a logical address space of the non-volatile storage device, a logical identifier for each data packet corresponding to the atomic storage request;

storing a first indicator on the non-volatile storage medium of the non-volatile storage device which indicates that the atomic storage request is in progress;

storing the data in a log based format on the non-volatile storage medium of the non-volatile storage device;

in response to storing the data of the atomic storage request,

updating storage metadata on the non-volatile storage medium to assign the allocated logical identifiers to storage locations comprising the data of the atomic storage request, and

invalidating the first indicator stored on the non-volatile storage medium; and

deallocating the allocated logical identifiers, in response to a failure during storage of the data of the atomic storage request.

6. The method of claim 5, wherein invalidating the first indicator comprises a second indicator on the non-volatile storage medium of the non-volatile storage device to indicate that the atomic storage request is complete.

7. The method of claim 5, further comprising storing the data of the atomic storage request sequentially on the non-volatile storage medium of the non-volatile storage device.

8. The method of claim 5, wherein the atomic storage request includes multiple storage operations.

9. The method of claim 8, further comprising rolling back the atomic storage request in response to determining that the atomic storage request is not complete.

10. The method of claim 5, wherein the storage metadata stored on the non-volatile storage medium of the non-volatile storage device comprises an index to track allocation of the logical address space and to associate logical identifiers with storage locations on the non-volatile storage medium of the non-volatile storage device.

11. The method of claim 10, wherein invalidating the first indicator comprises a second indicator on the non-volatile storage medium of the non-volatile storage device to indicate that the atomic storage request is complete, wherein the first and second indicators distinguish between data of complete atomic storage requests stored on the non-volatile storage medium and data of failed atomic storage requests stored on the non-volatile storage medium.

12. A method, comprising:

receiving an atomic storage request to store data comprising multiple data packets on a solid state storage device, wherein each data packet contains a logical identifier associated with the data packet;

allocating, in a logical address space of the solid state storage device, logical identifiers for a plurality of data packets corresponding to the atomic storage request;

storing the data packets on the solid state storage device, wherein the data packets stored on the solid state storage device comprise an indicator of the progress of the atomic storage request;

in response to storing one or more data packets of the atomic storage request,

updating storage metadata on the solid state storage device to assign the allocated logical identifiers to storage locations comprising the data of the atomic storage request, and

updating the storage metadata to indicate that the atomic storage request is complete; and

deallocating the allocated logical identifiers, in response to a failure during storage of the one or more data packets of the atomic storage request.

13. The method of claim 12, wherein a first data packet contains a first indicator configured to indicate that the atomic storage request is in progress.

14. The method of claim 13, wherein updating the storage metadata to indicate that the atomic storage request is complete comprises storing a second data packet of the atomic storage request with a second indicator configured to indicate that the atomic storage request is complete.

15. The method of claim 12, further comprising storing the data packets on the non-volatile storage device in a log based format.

16. The method of claim 12, further comprising determining if the atomic storage request is complete based on indicators of the stored data packets.

17. The method of claim 16, further comprising rolling back the atomic storage request in response to determining that the atomic storage request is not complete.

18. The method of claim 12, wherein the storage metadata stored on the solid state storage device comprises an index to track allocation of the logical address space and to allocate logical identifiers to storage locations on the non-volatile storage device.

19. The method of claim 14, wherein the first and second indicators of the stored data packets distinguish data packets of complete atomic storage requests from data packets of atomic storage requests that are not complete.