Atomic write command support in a solid state drive

• US 10,254,983 B2
• Filed: 03/14/2017
• Issued: 04/09/2019
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Tomlin, Andrew J., Jones, Justin, Mullendore, Rodney N.
• Primary Examiner(s): Patel, Kaushikkumar M
• Application Number:
  US15/458,901
• Publication Number:
  US 20170344287A1
• Time in Patent Office: 756 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0638 Combination of memories, e.g. ROM and RAM such as to permit replacement or supplementing of words in one module by words in another module address formation of the next microinstruction G06F9/26; masking faults in memories by using spares or by reconfiguring G11C29/70
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G11C 16/10 Programming or data input circuits

Abstract

A method of performing an atomic write command in a data storage device comprising a volatile memory and a plurality of non-volatile memory devices configured to store a plurality of physical pages. The method may comprise storing data in a plurality of logical pages (L-Pages), each associated with a logical address. A logical-to-physical address translation map may be maintained in the volatile memory, and may be configured to enable determination of a physical location, within one or more of the physical pages, of the data referenced by each logical address. The data specified by a received atomic write command may be stored one or more L-Pages. Updates to the entry or entries in the translation map associated with the L-Page(s) storing the data specified by the atomic write command may be deferred until all L-Pages storing data specified by the atomic write command have been written in a power-safe manner.

Claims

1. A method comprising:

receiving an atomic write command;

storing, based on the atomic write command, data in one or more logical pages (L-Pages), wherein each L-Page among the one or more L-Pages is associated with a logical address;

generating a system journal (S-Journal) entry for each of the one or more L-Pages wherein each S-Journal entry comprises a first sequence number associated with the atomic write command;

determining, based on the S-Journal entries, whether all L-Pages are stored in a non-volatile memory; and

after a power loss event, in response to determining that all L-Pages are not stored in the non-volatile memory;

determining, based on the first sequence number, a minimum L-Page number, and a maximum L-Page number, a range of L-Page numbers;

for each L-Page number in the range of L-Page numbers, determining data in the L-Page associated with the L-Page prior to receiving the atomic write command; and

generating a copy command to store the data, for the L-Pages associated with the range of L-Page numbers, in the non-volatile memory.

2. The method of claim 1, further comprising:

in response to determining that all L-Pages are stored in the non-volatile memory;

updating an entry in a logical-to-physical address translation map.

3. The method of claim 1, further comprising:

for each of the one or more L-Pages, storing, in a data structure in a volatile memory, an entry that specifies a physical address in the non-volatile memory that is associated with the logical address of the L-Page.

4. The method of claim 1, wherein each S-Journal entry associates one or more physical pages to the L-Page.

5. The method of claim 1, further comprising:

storing a second sequence number in a power-safe memory.

6. The method of claim 5, further comprising:

determining whether the first sequence number comprised in the S-Journal entry matches the second sequence number; and

in response to determining that the first sequence number matches the second sequence number;

determining that all L-Pages are not stored in the non-volatile memory.

7. The method of claim 5, further comprising:

in response to determining that the first sequence number does not match the second sequence number;

determining that all L-Pages are stored in the non-volatile memory.

8. The method of claim 1, further comprising:

for each L-Page stored in the non-volatile memory;

determining whether an L-Page number associated with the L-Page is less than a minimum L-Page number comprised in an entry in a data structure;

in response to determining that the L-Page number associated with the L-Page is less than the minimum L-Page number;

updating the minimum L-Page number comprised in the entry with the L-Page number associated with the L-Page, wherein the entry is associated with the first sequence number associated with the atomic write command;

determining whether the L-Page number associated with the L-Page is greater than a maximum L-Page number comprised in the entry; and

in response to determining that the L-Page number associated with the L-Page is greater than the maximum L-Page number;

updating the maximum L-Page number comprised in the entry with the L-Page number associated with the L-Page.

9. The method of claim 1, further comprising:

in response to determining that all L-Pages are not stored in the non-volatile memory;

deferring an update to an entry in a logical-to-physical address translation map until all L-Pages are stored in the non-volatile memory, wherein the entry is associated with at least one L-Page among the one or more L-Pages.

10. A storage system comprising:

a non-volatile memory; and

a controller;

wherein the controller is configured to;

receive an atomic write command;

store, based on the atomic write command, data in one or more logical pages (L-Pages), wherein each L-Page among the one or more L-Pages is associated with a logical address;

generate a system journal (S-Journal) entry for each of the one or more L-Pages, wherein each S-Journal entry comprises a first sequence number associated with the atomic write command;

determine, based on the S-Journal entries, whether all L-Pages are stored in a non-volatile memory;

after a power loss event, when all L-Pages are not determined to be stored in the non-volatile memory,

determine, based on the first sequence number, the minimum L-Page number and the maximum L-Page number, a range of L-Page numbers;

for each L-Page number in the range of L-Page numbers, determine data in the L-Page associated with the L-Page prior to receiving the atomic write command; and

generate a copy command to store the data, for the L-Pages associated with the range of L-Page numbers, in the non-volatile memory.

11. The storage system of claim 10, comprising:

a volatile memory; and

wherein the controller is configured to;

for each of the one or more L-Pages;

store, in the volatile memory, an entry that specifies a physical address in the non-volatile memory that is associated with the logical address of the L-Page.

12. The storage system of claim 10, wherein each S-Journal entry associates one or more physical pages to the L-Page.

13. The storage system of claim 10, comprising:

a power-safe memory; and

wherein the controller is configured to;

store a second sequence number in the power-safe memory.

14. The storage system of claim of claim 13, wherein the controller is configured to:

determine whether the first sequence number comprised in the S-Journal entry matches the second sequence number; and

when the first sequence number is determined to match the second sequence number,

determine that all L-Pages are not stored in the non-volatile memory.

15. The storage system of claim 13, wherein the controller is configured to:

when the first sequence number is determined to match the second sequence number,

determine that all L-Pages are stored in the non-volatile memory.

16. The storage system of claim 10, wherein the controller is configured to:

for each L-Page stored in the non-volatile memory;

determine whether an L-Page number associated with the L-Page is less than a minimum L-Page number comprised in an entry in a data structure;

when the L-Page number associated with the L-Page is determined to be less than the minimum L-Page number,

update the minimum L-Page number comprised in the entry with the L-Page number associated with the L-Page, wherein the entry is associated with the first sequence number associated with the atomic write command;

determine whether the L-Page number associated with the L-Page is greater than a maximum L-Page number comprised in the entry; and

when the L-Page number associated with the L-Page is determined to be greater than the maximum L-Page number,

update the maximum L-Page number comprised in the entry with the L-Page number associated with the L-Page.

17. The storage system of claim 10, wherein the controller is configured to:

when all L-Pages are not determined to be stored in the non-volatile memory, defer an update to an entry in a logical-to-physical address translation map until all L-Pages are stored in the non-volatile memory, wherein the entry is associated with at least one L-Page among the one or more L-Pages.

18. The storage system of claim 10, wherein the controller is configured to:

when all L-Pages are determined to be stored in the non-volatile memory, update an entry in a logical-to-physical address translation map.

19. A system comprising:

means for receiving an atomic write command;

means for storing, based on the atomic write command, data in one or more logical pages (L-Pages), wherein each L-Page among the one or more L-Pages is associated with a logical address;

means for generating a system journal (S-Journal) entry for each of the one or more L-Pages, wherein each S-Journal entry comprises a first sequence number associated with the atomic write command;

means for determining, based on the S-Journal entries, whether all L-Pages are stored in a non-volatile memory; and

after a power loss event, in response to determining that all L-Pages are not stored in the non-volatile memory;

means for determining, based on the first sequence number, a minimum L-Page number, and a maximum L-Page number, a range of L-Page numbers;

for each L-Page number in the range of L-Page numbers, means for determining data in the L-Page associated with the L-Page prior to receiving the atomic write command; and

means for generating a copy command to store the data, for the L-Pages associated with the range of L-Page numbers, in the non-volatile memory.

20. The system of claim 19, comprising:

in response to determining that all L-Pages are not stored in the non-volatile memory;

means for deferring an update to an entry in a logical-to-physical address translation map until all L-Pages are stored in the non-volatile memory, wherein the entry is associated with at least one L-Page among the one or more L-Pages.