APPARATUS, SYSTEM, AND METHOD FOR CONDITIONAL AND ATOMIC STORAGE OPERATIONS

• US 20140189216A1
• Filed: 11/22/2013
• Published: 07/03/2014
• Est. Priority Date: 09/09/2009
• 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
• Granted Patent: US 9,251,062 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• 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
• 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-19. -19. (canceled)

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

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

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

updating storage metadata on the non-volatile storage device to assign 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.

21. The method of claim 20, further comprising:

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

deallocating the allocated logical identifiers in response to failure of one or more of the storage operations.

22. The method of claim 20, further comprising:

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

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

23. The method of claim 20, further comprising:

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

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

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

24. (canceled)

25. (canceled)

26. (canceled)

27. (canceled)

28. (canceled)

30. A method for servicing part of an atomic storage request, comprising:

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

storing a first indicator on 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 device; and

determining that the atomic request is not complete based on the presence of the first indicator.

31. The method of claim 30, further comprising storing a second indicator on the non-volatile storage device to indicate that the atomic storage request is complete.

32. The method of claim 30, further comprising storing the data sequentially on the non-volatile storage device.

33. The method of claim 30, wherein the atomic storage request includes multiple storage operations.

34. The method of claim 33, further comprising rolling back the atomic storage request if one of the storage operations is not complete.

35. The method of claim 30, wherein the data comprises a data packet containing a logical identifier associated with that data packet.

36. The method of claim 35, further comprising allocating a logical identifier for each data packet in a logical address space of the non-volatile storage device.

37. The method of claim 36, further comprising deallocating the allocated logical identifier in response to failure of the atomic storage request.

38. The method of claim 30, wherein the data contains storage metadata with an index to track allocation of the logical address space and to allocate logical identifiers to storage locations on the non-volatile storage device.

39. The method of claim 38, wherein the first and second indicators distinguish between complete and failed atomic storage requests without using the storage metadata.

40. A method for servicing an atomic storage request, comprising:

receiving an atomic storage request to store data comprising multiple data packets on a solid state storage device;

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

determining if the atomic request is not complete based on the indicator; and

rolling back the atomic storage request if storing of one of the data packets fails.

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

42. The method of claim 41, wherein a second data packet contains a second indicator configured to indicate that the atomic storage request is complete.

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

44. The method of claim 40, further comprising updating storage metadata on the non-volatile storage device to assign 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.

45. The method of claim 44, further comprising rolling back the atomic storage request if either or both of the updating operations fails.

46. The method of claim 40, wherein each data packet contains a logical identifier associated with that data packet.

47. The method of claim 46, further comprising allocating a logical identifier for each data packet in a logical address space of the non-volatile storage device.

48. The method of claim 47, further comprising deallocating the allocated logical identifier in response to failure of the atomic storage request.

49. The method of claim 40, wherein the data contains storage metadata with an index to track allocation of the logical address space and to allocate logical identifiers to storage locations on the non-volatile storage device.

50. The method of claim 49, wherein the first and second indicators can distinguish between complete and failed atomic storage requests without reference to the storage metadata.