Apparatus, system, and method for atomic storage operations

• US 10,013,354 B2
• Filed: 07/28/2011
• Issued: 07/03/2018
• Est. Priority Date: 07/28/2010
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Flynn, David, Uphoff, Stephan, Ouyang, Xiangyong, Nellans, David, Wipfel, Robert
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Li, Hewy H
• Application Number:
  US13/193,559
• Publication Number:
  US 20120030408A1
• Time in Patent Office: 2,532 Days
• Field of Search: None
• 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 storage layer (SL) 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 SL 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, comprising:

storing a plurality of data units pertaining to an atomic storage request sequentially at an append point of a log within a physical address space of a non-volatile storage device in a plurality of storage operations, each storage operation to write a respective data unit at the append point of the log with respective persistent metadata and to advance the append point sequentially in the physical address space, such that physical storage addresses of data units stored within the log correspond to a sequence order of the data units, wherein;

the persistent metadata of data units to be written in storage operations other than a last storage operation of the atomic storage request comprises a first value configured to indicate that the data units correspond to an incomplete atomic storage request, and

the persistent metadata of a data unit to be written in the last storage operation of the atomic storage request comprises a second value configured to indicate that the plurality of data units correspond to a completed atomic storage request; and

determining whether the atomic storage request completed, the determining comprising;

traversing data units stored within the log in a reverse sequence order of the data units, the reverse sequence order corresponding to physical storage addresses of the data units stored within the log; and

accessing the persistent metadata of a first data unit in the reverse sequence order.

2. The method of claim 1, further comprising:

updating translation metadata of the non-volatile storage device in response to writing the last data unit on the non-volatile storage device, wherein;

the translation metadata is updated such that client requests pertaining to logical identifiers of the atomic storage request are associated with respective physical storage addresses of the data units written to the non-volatile storage device, and

logical identifiers of the atomic storage request are noncontiguous within a logical address space.

3. The method of claim 1, further comprising acknowledging completion of the atomic storage request in response to one or more of transferring the data units to a write buffer of the non-volatile storage device, transferring the data units to a protection domain of the non-volatile storage device, transferring the data units to a powercut safe domain of the non-volatile storage device, and storing the data units on a non-volatile storage medium of the non-volatile storage device.

4. The method of claim 1, further comprising updating a forward index to assign logical identifiers of the atomic storage request to the respective physical storage locations of the data units pertaining to the atomic storage request stored on the non-volatile storage device.

5. The method of claim 1, further comprising invalidating one or more data units stored on the non-volatile storage device in response to determining that the one or more data units do not correspond to a data unit written with persistent metadata comprising the second value.

6. The method of claim 1, wherein traversing the data units stored within the log in the reverse sequencer order comprises determining a physical storage address of a data unit stored at a head of the log based on physical storage addresses of the data units stored within the log;

and

determining whether the plurality of write operations of the atomic storage request completed successfully based on the persistent metadata included in the first data unit accessed at the head of the log.

7. The method of claim 1, wherein the data units are stored at contiguous physical storage addresses of the non-volatile storage device.

8. The method of claim 1, further comprising disabling a garbage collection bypass while storing the plurality of data units on the non-volatile storage device.

9. The method of claim 1, further comprising:

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

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

10. The method of claim 1, wherein a logical identifier of the atomic storage request is associated with existing data stored on the non-volatile storage device, the method further comprising:

preserving an association between the logical identifier and the existing data in logical-to-physical translation metadata pertaining to the non-volatile storage device until the last data unit is written to the non-volatile storage device; and

preserving the existing data on the non-volatile storage device until the last data unit is stored on the non-volatile storage device.

11. The method of claim 1, further comprising:

maintaining translation metadata for the non-volatile storage device, the translation metadata comprising logical-to-physical assignments between logical identifiers and data stored on the non-volatile storage device;

tracking completion of the atomic storage request in inflight metadata, independent of the translation metadata, the tracking comprising recording logical-to-physical assignments between logical identifiers of the atomic storage request and the data units pertaining to the atomic storage request stored on the non-volatile storage device in the inflight metadata, such that the logical-to-physical assignments recorded in the inflight metadata differ from corresponding logical-to-physical assignments of the translation metadata; and

updating the translation metadata with the logical-to-physical assignments of the inflight metadata in response to writing the last data unit on the non-volatile storage device.

12. The method of claim 11, further comprising accessing the inflight metadata structure to prevent one or more of a read hazard and a write hazard.

13. A non-transitory computer-readable storage medium comprising machine-readable instructions configured to cause a machine to perform operations, comprising:

storing data of an atomic storage request on the non-volatile storage device within a plurality of data packets, each data packet stored in a respective storage operation comprising, writing the data packet at an append point for a log maintained on a non-volatile storage medium and advancing the append point sequentially within a physical address space of the non-volatile storage medium, such that physical addresses of the data packets appended to the log correspond to a sequencer order of the data units, wherein;

data packets to be appended to the log in storage operations other than a last storage operation of the atomic storage request comprise a first persistent flag configured to indicate that the data packets correspond to an incomplete atomic storage operation, and

a data packet to be appended to the log in the last storage operation of the atomic storage request comprises a second persistent value configured to indicate that the plurality of data packets correspond to a complete atomic storage operation; and

determining whether the atomic storage request was successful, the determining comprising;

accessing data packets stored within the log on the non-volatile storage medium in a reverse sequence order, the reverse sequencer order corresponding to physical addresses of the data packets on the non-volatile storage medium; and

evaluating a persistent flag of a first data packet accessed in the reverse sequence order.

14. The non-transitory computer-readable storage medium of claim 13, the operations further comprising:

maintaining a forward index comprising associations between logical identifiers of a logical address space and physical storage locations storing data corresponding to the logical identifiers on a non-volatile storage medium;

recording associations between logical identifiers of the atomic storage request and physical addresses of respective data packets stored within the log in an inflight index separate from the forward index;

updating the forward index with the associations recorded in the inflight index in response to completing the last storage operation of the atomic storage request; and

acknowledging completion of the atomic storage request in response to the updating.

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

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

a storage layer configured to;

receive an atomic storage request from a storage client, and

store a plurality of data segments of the atomic storage request within a log on the non-volatile storage device, each data segment being written to the log in a respective storage operation, comprising writing the data segment at an append point for the log together with persistent metadata, and advancing the append point sequentially within a storage address space of the non-volatile storage device, such that storage addresses of the data segments stored on the non-volatile storage device correspond to a sequence order of the data segments in the log, wherein;

the persistent metadata stored with data segments to be written in storage operations other than a last storage operation of the atomic storage request comprises a first value configured to indicate that the data segments correspond to an incomplete atomic storage request, and

the persistent metadata stored with a data segment to be written in the last storage operation of the atomic storage request comprises a second value configured to indicate that the plurality of data segments correspond to a completed atomic storage request; and

to determine whether the atomic storage request was successfully completed, the storage layer is further configured to;

identify a current append point of the log within the storage address space of the non-volatile storage device, and

read persistent metadata of a data segment stored at the current append point of the log.

16. The apparatus of claim 15, wherein the storage layer is further configured to:

maintain a forward index comprising assignments between logical identifiers of the logical address space and corresponding data stored on the non-volatile storage device, the forward index comprising an assignment between a particular logical identifier of the atomic storage request and existing data stored on the non-volatile storage device;

maintain the assignments of the translation metadata, including the assignment between the particular logical identifier and the existing data, while the plurality of data segments of the atomic storage request are stored on the non-volatile storage device; and

update the forward index to assign the particular logical identifier to a stored data segment of the atomic storage request in response to completing storing the last storage operation of the atomic storage request on the non-volatile storage medium.

17. The apparatus of claim 15, wherein the storage layer is further configured to:

determine that the atomic storage request failed in response to the persistent metadata of the first data segment comprising the first value; and

invalidate the first data segment in response to determining that the atomic storage request failed.

18. The apparatus of claim 17, wherein the storage layer is further configured to:

invalidate one or more data segments that precede the first data segment in the sequence order in the log in response to persistent metadata of the one more data segments comprising the first value.

19. The apparatus of claim 17, wherein, in response to determining that the atomic storage request failed, the storage layer is further configured to:

traverse data segments appended to the log in a reverse sequence order, the reverse sequence order corresponding to storage addresses of the data segments stored on the non-volatile storage device; and

to invalidate data segments accessed while traversing the log in the reverse sequence order until accessing a data segment stored with persistent metadata comprising the second value.