Method and apparatus for recovering metadata lost during an unexpected power down event

Patent metadata

Field	Value
Publication number	US-9639423-B2
Application number	US-201414538179-A
Country	US
Kind code	B2
Filing date	Nov 11, 2014
Priority date	May 25, 2010
Publication date	May 2, 2017
Grant date	May 2, 2017

Abstract

A system including first and second memory and a control module. The first memory stores a first lookup table with first metadata that includes a first mapping between logical and physical addresses and is lost due to an unexpected power down event. The second memory stores a second lookup table with second metadata and an event log. The second metadata includes a second mapping between the logical and physical addresses. The event log includes entries indicating updated associations between respective ones of the logical addresses and one of the physical addresses as included in the first metadata prior to the power down event. The control module: prior to the power down event, performs segmented flushes each including updating a segment of the second metadata with a corresponding segment of the first metadata; and walks the event log to recover a full flush cycle of segments of the first metadata.

First claim

What is claimed is:

1. A system comprising:
a first memory configured to store a first lookup table with first metadata, wherein the first metadata includes a first mapping between logical addresses and physical addresses, and wherein the first metadata is susceptible to being lost due to an unexpected power down event;
a second memory configured to store (i) a second lookup table with second metadata, and (ii) an event log, wherein the second metadata includes a second mapping between the logical addresses and the physical addresses, wherein the event log comprises a plurality of entries, wherein the second memory is configured to store in the event log each of the plurality of entries, such that each of the plurality of entries indicates an updated association between a respective one of the logical addresses and a corresponding one of the physical addresses as included in the first metadata prior to the unexpected power down event; and
a control module configured to
prior to the unexpected power down event, perform segmented flushes, wherein each of the segmented flushes includes updating one or more entries of a segment of the second metadata with a corresponding one or more entries of a segment of the first metadata, and wherein each of the segmented flushes includes updating one or more entries that are different than the one or more entries of each of other segmented flushes, and
as a result of the unexpected power down event, process the event log entry-by-entry in a successive order beginning at a first entry and stopping at a second entry to recover, based on the second metadata and the entries in the event log from the first entry to the second entry, a single full flush cycle of segments of the first metadata in the first memory,
wherein
the control module is configured to, while processing the event log from the first entry to the second entry, (i) skip an entry in the event log between the first entry and the second entry, and (ii) refrain from updating a segment of the first metadata associated with the skipped entry,
the skipped entry of the event log corresponds to an entry of the first metadata last updated (i) during or subsequent to a first one of the segmented flushes, and (ii) prior to the unexpected power down event,
the first one of the segmented flushes occurred prior to the other ones of the segmented flushes,
the processing of the event log to recover the single full flush cycle of segments of the first metadata includes, based on the event log, updating each of the entries of the segment of the second metadata to recover one or more last modified entries of a corresponding one or more segments of the first metadata,
the control module is configured to update each of the one or more last modified entries of the first metadata subsequent to a corresponding one of the segmented flushes being performed and prior to the unexpected power down event,
the first entry is a predetermined number of entries prior to the second entry,
the unexpected power down event occurs during or after storing the second entry in the second memory, and
the predetermined number of entries corresponds to recovering the single full flush cycle of segments.

2. The system of claim 1 , wherein:
the skipped entry comprises a logical-to-physical address association and corresponds to a first time slot;
a third entry of the event log comprises the logical-to-physical address of the skipped entry and corresponds to a second time slot; and
the second time slot is subsequent to the first time slot.

3. The system of claim 1 , wherein each of the segmented flushes includes updating a first plurality of physical address associations of a plurality of logical addresses in the second lookup table with a second plurality of physical address associations of the plurality of logical addresses indicated in the first lookup table.

4. The system of claim 1 , wherein:
the second memory is configured to store third metadata;
the third metadata is (i) different than the first metadata and the second metadata, and (ii) determined based on values of the first metadata or the second metadata; and
the control module is configured to (i) as a result of the unexpected power down event, determine whether a segment of the third metadata is stored in the second memory, and (ii) if the segment of the third metadata is stored in the second memory and while processing the event log, recover the first metadata based on a time slot corresponding to the segment of the third metadata.

5. The system of claim 4 , wherein the control module is configured to:
if the segment of the third metadata is stored in the second memory,
increment an upload timer if a full flush cycle of segments since the unexpected power down event has not been uploaded, and
upload the segment of the third metadata based on the first lookup table if a full flush cycle of segments since the unexpected power down event has been uploaded; and

increment the upload timer if (i) the segment of the third metadata is not stored in the second memory, and (ii) an end of the event log has not been reached.

6. The system of claim 5 , wherein the control module is configured to, if the end of the event log has not been reached, recover (i) the third metadata, and (ii) some logical-to-physical address associations in the first lookup table based on corresponding entries in the event log.

7. The system of claim 4 , wherein:
the third metadata includes information regarding the first metadata or the second metadata; and
the information regarding the first metadata or the second metadata comprises pointers of user data, pointers of system data, amounts of data stored in blocks of the first memory or the second memory, and defect information.

8. The system of claim 1 , wherein the control module is configured to:
determine whether a proper power down of the system has occurred, wherein a proper power down occurs when the first lookup table is flushed to the second memory prior to a last power down event of the system;
in response to a proper power down of the system occurring, (i) transfer the second metadata from the second memory to the first memory, and (ii) refrain from processing the event log; and
in response to a proper power down of the system having not occurred, (i) transfer the second metadata from the second memory to the first memory, and (ii) process the event log.

9. The system of claim 1 , further comprising a solid-state drive comprising the first memory and the second memory, wherein:
the first memory includes volatile memory; and
the second memory includes non-volatile memory.

10. The system of claim 1 , wherein:
each of the one or more segments of the first metadata refers to a respective column of the first lookup table; and
the segment of the second metadata refers to a column of the second lookup table.

11. The system of claim 1 , wherein:
the entry of the first metadata, corresponding to the skipped entry of the event log, was last updated prior to a second one of the segmented flushes; and
the second one of the segmented flushes occurred subsequent to the first one of the segmented flushes.

12. The system of claim 1 , wherein the skipped entry of the event log corresponds to (i) a segment of the first metadata that was not updated for a period of the skipped entry, or (ii) an entry of the first metadata that was updated prior to a corresponding one of the segmented flushes.

13. A method comprising:
storing a first lookup table with first metadata in a first memory, wherein the first metadata includes a first mapping between logical addresses and physical addresses, and

Assignees

• Marvell World Trade Ltd

Inventors

• Adler Jason
• Neos Perry
• Ton-That Luan
• Hwu Gwoyuh

Classifications

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F12/02 Primary

  Addressing or allocation; Relocation (program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00) · CPC title

• G06F12/16

  Protection against loss of memory contents {(contains no material, see G06F11/00)} · CPC title

• G06F11/1435 Primary

  using file system or storage system metadata · CPC title

• G06F11/1451

  by selection of backup contents · CPC title