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

• US 8,601,222 B2
• Filed: 05/13/2011
• Issued: 12/03/2013
• Est. Priority Date: 05/13/2010
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Nellans, David, Ouyang, Xiangyong
• Primary Examiner(s): SCHNEE, HAL W
• Application Number:
  US13/107,820
• Publication Number:
  US 20110296133A1
• Time in Patent Office: 935 Days
• Field of Search: 711/103, 711/152, 711/154, 711/162, 711/202, 711/E12.008, 711/E12.022
• US Class Current: 711/152
• 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 for providing a conditional storage request, comprising:

presenting a logical address space of a non-volatile storage device to a storage client, the logical address space comprising a plurality of logical identifiers;

receiving a conditional storage request comprising a condition, the request configured to conditionally store data at a storage location on the non-volatile storage device, wherein the condition is unrelated to modification of another storage location associated with the conditional storage request;

rejecting the conditional storage request if the condition of the conditional storage request is not satisfied; and

servicing the conditional storage request by storing data referenced in the conditional storage request on the non-volatile storage device if the condition of the conditional storage request is satisfied.

2. The method of claim 1, wherein determining that the condition is satisfied comprises determining that a specified logical identifier of the conditional storage request can be allocated in the logical address space of the non-volatile storage device.

3. The method of claim 2, wherein servicing the conditional storage request comprises:

allocating the specified logical identifier in the logical address space of the non-volatile storage device;

providing for storing data of the conditional storage request on storage locations of the non-volatile storage device; and

assigning the allocated logical identifier to the storage locations on the non-volatile storage device.

4. The method of claim 1, wherein determining that the condition is satisfied comprises determining that a logical capacity of the conditional storage request is available for allocation in the logical address space.

5. The method of claim 4, wherein servicing the conditional storage request comprises:

selecting and allocating one or more logical identifiers in the logical address space having sufficient logical capacity to satisfy the conditional storage request;

providing for storing data of the conditional storage request on one or more storage locations of the non-volatile storage device;

assigning the selected and allocated one or more logical identifiers to the one or more storage locations on the non-volatile storage device; and

providing an indicator of the selected and allocated logical identifier to the storage client.

6. The method of claim 5, wherein the selected and allocated logical identifiers comprise a contiguous range of logical identifiers in the logical address space, or two or more noncontiguous ranges of logical identifiers in the logical address space.

7. The method of claim 1, wherein the condition specifies a preferred set of logical identifiers to allocate in the address space, and wherein determining that the condition is satisfied comprises determining that a logical capacity of the conditional storage request comprising at least one of the preferred logical identifiers is available for allocation in the logical address space.

8. The method of claim 7, wherein servicing the conditional storage request comprises:

selecting and allocating logical identifiers in the logical address space having sufficient logical capacity to satisfy the conditional storage request, wherein selecting comprises selecting at least one of the preferred logical identifiers available for allocation in the logical address space;

providing for storing data of the conditional storage request on storage locations of the non-volatile storage device;

assigning the selected and allocated logical identifiers to the storage locations on the non-volatile storage device; and

providing indicators of the selected and allocated logical identifiers to the storage client.

9. The method of claim 1, wherein determining that the condition is satisfied comprises determining that a logical identifier specified by the condition is allocated in the logical address space.

10. The method of claim 1, further comprising maintaining metadata to track allocations of the logical address space, wherein determining whether the condition is satisfied comprises referencing the metadata.

11. The method of claim 10, wherein the condition specifies a logical identifier in the logical address space of the non-volatile storage device, and wherein the condition is satisfied by one of the metadata indicating that the specified logical identifier is available to be allocated and the metadata indicating that the specified logical identifier is allocated.

12. The method of claim 1, further comprising

maintaining metadata pertaining to the non-volatile storage device, the metadata comprising,

an index to track allocations of the logical address space and to assign allocated logical identifiers to storage locations on the non-volatile storage device, and

an inflight datastructure to track in-process storage operations pertaining to logical identifiers in the logical address space, wherein servicing the conditional storage request comprises:

allocating one or more logical identifiers in the metadata to satisfy the conditional storage request;

updating the inflight datastructure to indicate that a storage operation pertaining to the allocated logical identifiers is incomplete; and

providing for storing data of the conditional storage request on the non-volatile storage device in one or more storage operations.

13. The method of claim 12, wherein the condition specifies a logical identifier to allocate in the logical address space, and wherein the condition is satisfied when the specified logical identifier is available for allocation in the index and the inflight datastructure does not reference the specified logical identifier.

14. The method of claim 12, further comprising updating the metadata in response to an indication that the one or more storage operations are complete, wherein updating the metadata comprises one of:

updating the index to assign the allocated logical identifiers to storage locations comprising data of the conditional storage request; and

updating the inflight datastructure to indicate that the storage operation pertaining to the allocated logical identifiers is complete.

15. The method of claim 12, further comprising updating the metadata in response to an indication that one of the one or more storage operations failed, wherein updating the metadata comprises one of:

deallocating one or more allocated logical identifiers in the index; and

updating the inflight datastructure to indicate that the storage operation pertaining to the set of logical identifiers is complete.

16. The method of claim 1, wherein servicing the conditional storage request comprises:

providing for storing data of the conditional storage request on the non-volatile storage device in one or more storage operations; and

invalidating data of the conditional storage request stored on the non-volatile storage device in response to failure of one or more of the storage operations.

17. The method of claim 1, wherein servicing the conditional storage request further comprises:

providing for storing a persistent indicator on the non-volatile storage device that indicates the conditional storage request is incomplete; and

providing for storing a persistent indicator on the non-volatile storage device that indicates the conditional storage request is complete in response to completing each of one or more storage operations pertaining to the conditional storage operation.

18. The method of claim 1, wherein servicing the conditional storage request further comprises:

providing for storing a persistent indicator on the non-volatile storage device that indicates the conditional storage request is incomplete; and

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

19. The method of claim 1, wherein the logical identifiers of the logical address space are one of logical block addresses, block addresses, and sector addresses, and wherein the condition relates to logical identifiers defined within the logical address space of the non-volatile storage device.

20. A non-transitory computer-readable storage medium comprising machine-readable instructions configured to cause a machine to perform a method for providing a conditional storage request, the method comprising:

presenting a logical address space of a non-volatile storage device to a storage client, the logical address space comprising a plurality of logical identifiers;

receiving a conditional storage request comprising a condition, the request configured to conditionally store data on the non-volatile storage device, wherein the condition relates to logical identifiers of the presented logical address space, wherein the condition is unrelated to modification of another storage location associated with the conditional storage request;

rejecting the conditional storage request if the condition of the conditional storage request is not satisfied; and

servicing the conditional storage request by storing data referenced in the conditional storage request on the non-volatile storage device if the condition of the conditional storage request is satisfied.

21. The non-transitory machine-readable medium of claim 20, the method further comprising:

maintaining storage metadata to track allocations of the logical address space, the metadata comprising an index of allocated logical identifiers, and an inflight datastructure to track storage operations that are in process;

wherein determining that the condition is satisfied comprises referencing the storage metadata to determine one of a specified logical identifier in the logical address space can be allocated, a logical capacity of the conditional storage request can be allocated, and a specified logical identifier within the logical address space is allocated.

22. The non-transitory machine-readable medium of claim 20, wherein servicing the conditional storage request further comprises:

allocating logical capacity in the logical address space sufficient to satisfy the conditional storage request;

providing for storing data of the conditional storage request on storage locations of the non-volatile storage device; and

assigning the allocated logical identifiers to the storage locations on the non-volatile storage device.

23. The non-transitory machine-readable medium of claim 20, wherein servicing the conditional storage request comprises providing for storing data of the conditional storage request in a plurality of storage operations, the method further comprising:

maintaining storage metadata to track allocations of the logical address space, the metadata comprising an index of allocated logical identifiers, and an inflight data structure to track storage operations that are in process;

updating the inflight data structure in response to completing a storage operation of the conditional storage request with a physical storage location assignment; and

updating physical storage location assignments of the index in a single update based on the inflight data structure upon completion of the plurality of storage operations.