Methods and appratuses for atomic storage operations

• US 8,725,934 B2
• Filed: 12/22/2011
• Issued: 05/13/2014
• Est. Priority Date: 12/22/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Batwara, Ashish, Peterson, James G., Talagala, Nisha, Zappe, Michael
• Primary Examiner(s): Gu, Shawn X
• Application Number:
  US13/335,922
• Publication Number:
  US 20130166820A1
• Time in Patent Office: 873 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

A method and apparatus for storing data packets in two different logical erase blocks pursuant to an atomic storage request is disclosed. Each data packet stored in response to the atomic storage request comprises persistent metadata indicating that the data packet pertains to an atomic storage request. In addition, a method and apparatus for restart recovery is disclosed. A data packet preceding an append point is identified as satisfying a failed atomic write criteria, indicating that the data packet pertains to a failed atomic storage request. One or more data packets associated with the failed atomic storage request are identified and excluded from an index of a non-volatile storage media.

Claims

1. A method for servicing an atomic storage request to store data on a non-volatile solid-state storage device, the non-volatile solid-state storage device comprising one or more solid-state storage elements, each solid-state storage element partitioned into a plurality of physical erase blocks, the method comprising:

storing data of an atomic storage request comprising a first data packet and a second data packet on a non-volatile solid-state storage device in a log-based sequential format, wherein the first data packet and the second data packet are stored on different logical erase blocks, wherein each logical erase block comprises two or more physical erase blocks;

storing persistent metadata within each data packet of the atomic storage request that indicates that the data of the atomic storage request pertains to the atomic storage request; and

acknowledging completion of the atomic storage request upon completion of storing the data of the atomic storage request.

2. The method of claim 1, wherein the persistent metadata and data corresponding to the persistent metadata for each data packet are stored in a single write operation to the nonvolatile solid-state storage device.

3. The method of claim 1, wherein the persistent metadata for the data of each data packet indicates that the data of the atomic storage request pertains to the atomic storage request comprises a single bit within each data packet.

4. The method of claim 1, further comprising queuing atomic and non-atomic storage requests for the non-volatile solid-state storage device in an ordered queue, wherein the atomic and the non-atomic storage requests are processed in an order of arrival at the ordered queue.

5. The method of claim 1, wherein data stored on the non-volatile solid-state storage device pursuant to the atomic storage request comprises an endpoint, and further comprising prohibiting grooming operations within an erase block of the non-volatile solid-state storage device associated with the endpoint.

6. The method of claim 1, further comprising receiving the atomic storage request by way of a single application programming interface call, the single application programming interface call identified as the atomic storage request by a flag parameter, the single application programming interface call comprising a vector that identifies storage locations related to each of one or more storage operations associated with the atomic storage request.

7. An apparatus for servicing an atomic storage request, the apparatus comprising:

a non-volatile solid-state storage device comprising one or more solid-state storage elements, each solid-state storage element partitioned into a plurality of physical erase blocks; and

a storage layer configured to;

store data of an atomic storage request comprising a first data packet and a second data packet in a log-based sequential format, wherein the first data packet and the second data packet are stored on separate logical erase blocks, wherein each logical erase block comprises two or more physical erase blocks;

include persistent metadata within each of the first and second data packets, the persistent metadata configured to indicate that the data is associated with the atomic storage request; and

report completion of the atomic storage request when the first and second data packets are stored.

8. The apparatus of claim 7, wherein the storage layer is further configured to store the persistent metadata and data corresponding to the persistent metadata for each data packet in a single write operation to the non-volatile solid-state storage device.

9. The apparatus of claim 7, wherein the persistent metadata comprises a single bit within each data packet.

10. The apparatus of claim 7, wherein the storage layer further comprises an ordered queue for queuing both atomic and non-atomic storage requests for the non-volatile solid-state storage device, wherein the ordered queue processes the atomic and the non-atomic storage requests in an order of arrival at the ordered queue.

11. A method for restart recovery for a non-volatile storage device configured to accept atomic and non-atomic storage requests, the method comprising:

accessing a non-volatile storage device at an append point, the non-volatile storage device configured to store a plurality of data packets to solid-state storage media by sequentially appending the data packets at the append point to a log-based structure of the solid-state storage media, the data packets associated with different logical identifiers belonging to a logical address space that is independent of physical storage locations on the solid-state storage media;

identifying a failed atomic storage request in response to a data packet preceding the append point comprising a persistent indicator that satisfies a failed atomic write criteria;

identifying one or more data packets associated with the failed atomic storage request; and

excluding from an index each data packet associated with the failed atomic storage request, the index mapping the logical identifiers to physical locations of the plurality of data packets on the solid-state storage media.

12. The method of claim 11, further comprising reading from the solid-state storage media during a power-on operation to construct the index, and wherein exclusion of the one or more packets associated with the failed atomic storage request from the index occurs during the power-on operation and before normal input-output operations commence for the non-volatile storage device.

13. The method of claim 11, wherein the persistent indicator comprises a single bit within each data packet.

14. The method of claim 11, wherein the one or more data packets associated with the failed atomic storage request are positioned sequentially within the log-based structure.

15. The method of claim 11, wherein excluding from the index further comprises bypassing each data packet associated with the failed atomic storage request during a scan of the log-based structure used to create the index.

16. The method of claim 11, wherein excluding from the index further comprises removing each logical identifier that maps to each data packet associated with the failed atomic storage request from the index created by way of a scan of the log-based structure.

17. The method of claim 11, wherein excluding from the index further comprises erasing each data packet associated with the failed atomic storage request from the solid-state storage media by way of a storage space recovery operation.

18. The method of claim 11, wherein excluding from the index further comprises erasing each erase block of the solid-state storage media comprising one or more data packets associated with the failed atomic storage request and transferring valid data packets from each erase block to a different location on the solid-state storage media.

19. The method of claim 18, wherein erasing each erase block comprises assigning a subsequence number to a destination erase block configured to store the transferred data packets, the subsequence number configured to maintain an ordered sequence among erase blocks of the log-based structure such that an ordered sequence of storage operations completed on the solid-state storage media is preserved on the solid-state storage media.

20. The method of claim 19, further wherein erasing each erase block further comprises in response to identifying a first erase block having a sequence number and second erase block having subsequence number derived from the sequence number of the first erase block, grooming the first erase block and excluding each data packet associated with the failed atomic storage request from the index.

21. An apparatus for restart recovery for a non-volatile storage device configured to accept atomic and non-atomic storage requests, the apparatus comprising:

a non-volatile storage device configured to store a plurality of data packets to solid-state storage media by sequentially appending the data packets at an append point to a log-based structure of the solid-state storage media, the data packets associated with different logical identifiers belonging to a logical address space that is independent of physical storage locations on the solid-state storage media; and

a storage layer configured to;

access the non-volatile storage device at the append point;

identify a failed atomic storage request in response to a data packet preceding the append point comprising a persistent indicator that satisfies a failed atomic write criteria;

identify one or more data packets associated with the failed atomic storage request; and

exclude from an index each data packet associated with the failed atomic storage request, the index mapping the logical identifiers to physical locations of the plurality of data packets on the solid-state storage media.

22. The apparatus of claim 21, wherein the storage layer is configured to read from the solid-state storage media during a power-on operation to construct the index, and wherein exclusion of the one or more packets associated with the failed atomic storage request from the index occurs during the power-on operation and before normal input-output operations commence for the non-volatile storage device.

23. The apparatus of claim 21, wherein the persistent indicator comprises a single bit within each data packet.

24. The apparatus of claim 21, wherein the one or more data packets associated with the failed atomic storage request are positioned sequentially within the log-based structure.

25. The apparatus of claim 21, wherein excluding from the index further comprises bypassing each data packet associated with the failed atomic storage request during a scan of the log-based structure used to create the index.

26. The apparatus of claim 21, wherein excluding from the index further comprises removing each logical identifier that maps to each data packet associated with the failed atomic storage request from the index created by way of a scan of the log-based structure.

27. An atomic storage request method to store data on a non-volatile solid-state storage device comprising a solid-state storage element partitioned into a plurality of physical erase blocks, the method comprising:

storing data of an atomic storage request on a non-volatile solid-state storage device in a log-based sequential format including storing a first data packet and a second data packet on different logical erase blocks in the storage device, wherein each logical erase block comprises two or more physical erase blocks;

storing metadata on the different logical erase blocks, the metadata indicating that the data relates to the atomic storage request; and

reporting that the atomic storage request is complete when the data is stored.

28. The method of claim 27, further comprising storing the first and second data packets on the different logical erase blocks at the same time.

29. An apparatus, comprising:

a non-volatile solid-state storage device comprising a solid-state storage element partitioned into a plurality of physical erase blocks, the non-volatile solid-state storage device configured to service an atomic storage request; and

a storage layer configured to;

package data of the atomic storage request into a first data packet and a second data packet;

generate persistent metadata for each data packet, the persistent metadata configured to indicate that the data is associated with the atomic storage request;

store the first data packet and the second data packet on separate logical erase blocks, wherein each logical erase block comprises two or more physical erase blocks; and

store persistent metadata for each data packet on media of the non-volatile solid-state storage device.

30. The apparatus of claim 29, wherein the storage layer is configured to store the first and second data packets on the separate logical erase blocks at the same time.