APPARATUS, SYSTEM, AND METHOD FOR ATOMIC STORAGE OPERATIONS

• US 20120030408A1
• Filed: 07/28/2011
• Published: 02/02/2012
• Est. Priority Date: 07/28/2010
• Status: Active Grant

• Current Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Ouyang, Xiangyong, Nellans, David, Wipfel, Robert, Uphoff, Stephan
• Granted Patent: US 10,013,354 B2
• Time in Patent Office: Days
• US Class Current: 711/102
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 Management of files
• 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

Abstract

A virtual storage layer (VSL) for a non-volatile storage device presents a logical address space of a non-volatile storage device to storage clients. Storage metadata assigns logical identifiers in the logical address space to physical storage locations on the non-volatile storage device. Data is stored on the non-volatile storage device in a sequential log-based format. Data on the non-volatile storage device comprises an event log of the storage operations performed on the non-volatile storage device. The VSL presents an interface for requesting atomic storage operations. Previous versions of data overwritten by the atomic storage device are maintained until the atomic storage operation is successfully completed. Data pertaining to a failed atomic storage operation may be identified using a persistent metadata flag stored with the data on the non-volatile storage device. Data pertaining to failed or incomplete atomic storage requests may be invalidated and removed from the non-volatile storage device.

Claims

1. A method for providing an atomic storage request, comprising:

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

storing persistent metadata with the data of the atomic storage request that indicates that the data pertains to the atomic storage request; and

acknowledging completion of the atomic storage request upon completion of the one or more storage operations of the atomic storage request.

2. The method of claim 1, wherein the logical identifiers of the atomic storage request are noncontiguous within a logical address space.

3. The method of claim 1, wherein a storage operation is complete when data of the storage operation is received by one of a write buffer of the non-volatile storage device, a protection domain of the non-volatile storage device, a powercut safe domain of the non-volatile storage device, and a non-volatile storage media of the non-volatile storage device.

4. The method of claim 1, wherein the persistent metadata is stored with data of the atomic storage request in a single storage operation.

5. The method of claim 1, further comprising updating a forward index to assign logical identifiers of the atomic storage request with physical storage locations of the data of the atomic storage request responsive to completing the one or more storage operations of the atomic storage request.

6. The method of claim 1, further comprising invalidating data of the atomic storage request in response to the non-volatile storage device failing to include a second persistent indicator that indicates completion of the atomic storage request.

7. The method of claim 1, further comprising:

storing a first persistent metadata flag on the non-volatile storage device to identify data pertaining to the atomic storage request;

storing a second persistent metadata flag on the non-volatile storage device with a last packet of data of the atomic storage request that indicates completion of the atomic storage request; and

using persistent metadata flags to determine whether the atomic storage request was successfully completed.

8. The method of claim 7, further comprising:

storing data of the atomic storage request sequentially at an append point on the non-volatile storage media;

determining a location of the append point on the non-volatile storage device;

accessing the non-volatile storage media at the sequential append point; and

identifying a failed atomic storage request when data at the append point comprises a first persistent metadata flag and not a second persistent metadata flag.

9. The method of claim 8, further comprising storing data of the atomic storage request contiguously on physical storage locations of the non-volatile storage device.

10. The method of claim 8, further comprising disabling a garbage collection bypass while storing the data of the atomic storage request on the non-volatile storage media.

11. The method of claim 1, further comprising:

detecting a loss of a primary power source of the non-volatile storage device; and

completing the one or more storage operations of the atomic storage request using a secondary power source.

12. The method of claim 1, wherein a logical identifier of the atomic storage request corresponds to a logical identifier bound to existing data on the non-volatile storage device, the method further comprising:

preserving the binding between the logical identifier and the existing data until all of the storage operations of the atomic storage request are complete; and

preserving the existing data on the non-volatile storage device until all of the storage operations of the atomic storage request are complete.

13. The method of claim 1, further comprising:

maintaining an inflight data structure to track completion of storage operations of the atomic storage request, the inflight datastructure to assign physical storage locations of data of the atomic storage request with logical identifiers of the atomic storage request;

deferring updates to the forward index with the assignment of the inflight datastructure until all of the one or more storage operations of the atomic storage request are complete; and

removing the assignments from the inflight datastructure when the one or more storage operations of the atomic storage request are complete.

14. The method of claim 13, accessing the inflight data structure to prevent one of a read hazard and a write hazard.

15. A non-transitory computer-readable storage medium comprising machine-readable instructions configured to cause a machine to perform a method for servicing an atomic storage request, the method comprising:

maintaining a forward index comprising bindings between logical identifiers in a logical address space of the non-volatile storage device and physical storage locations on the non-volatile storage device;

storing data of an atomic storage request in a sequential log-based format in one or more storage operations on the non-volatile storage device, wherein data of the atomic storage request is stored on the non-volatile storage device together with persistent metadata indicating that the data pertains to an atomic storage request;

maintaining an inflight index to associate logical identifiers of the atomic storage request with physical storage locations on the non-volatile storage device; and

preserving the forward index while the one or more storage operations of the atomic storage request are performed.

16. The non-transitory computer-readable storage medium of claim 15, further comprising acknowledging completion of the atomic storage request after updating the forward index. and wherein data of the atomic storage request is stored together with persistent metadata on the non-volatile storage device in a single storage operation.

17. The non-transitory computer-readable storage medium of claim 15, the method further comprising:

storing a persistent metadata flag indicating completion of the atomic storage device with a last data packet of the atomic storage request; and

identifying a failed atomic storage request when the persistent metadata flag indicating completion is absent on the non-volatile storage device.

18. An apparatus for providing atomic storage operations, comprising:

a non-volatile storage device comprising a non-volatile storage media; and

a virtual storage layer to;

receive an atomic storage request from the storage client the atomic storage request comprising noncontiguous logical identifiers in a logical address space of the non-volatile storage device, and

store data of the atomic storage request on the non-volatile storage device in a log-based format in one or more storage operations, wherein the data of the atomic storage request is stored together with persistent metadata that identifies the data as pertaining to an atomic storage request, and

acknowledge completion of the atomic storage request to the storage client.

19. The apparatus of claim 18, wherein the virtual storage layer stores persistent metadata that indicates completion of the atomic storage request together with a last data packet of the atomic storage request on the non-volatile storage device and wherein persistent metadata is stored together with data of the atomic storage request on the non-volatile storage device in each of one or more respective storage operations.

20. The apparatus of claim 18, wherein the virtual storage layer maintains a forward index to assign logical identifiers of a logical address space of the non-volatile storage device to physical storage locations on the non-volatile storage device, and wherein the virtual storage layer maintains the assignments while the one or more storage operations of the atomic storage request are performed, and updates the forward index with assignments between logical identifiers of the atomic storage request and data of the atomic storage request after completion of the one or more storage operations.