Metadata journaling with error correction redundancy

• US 9,411,717 B2
• Filed: 10/23/2012
• Issued: 08/09/2016
• Est. Priority Date: 10/23/2012
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Goss, Ryan James, Seekins, David Scott, Gaertner, Mark Allen
• Primary Examiner(s): Rigol, Yaima
• Assistant Examiner(s): Matin, Tasnima
• Application Number:
  US13/658,643
• Publication Number:
  US 20140115232A1
• Time in Patent Office: 1,386 Days
• Field of Search: 711/103, 711/160
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• 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

Abstract

Method and apparatus for managing a memory, such as but not limited to a flash memory. In accordance with some embodiments, user data and associated metadata are stored in a memory. The metadata are arranged as a first sequence of snapshots of the metadata at different points in time during the operation of the memory, and a second sequence of intervening journals which reflect updates to the metadata from one snapshot to the next. Requested portions of the metadata are recovered from the memory using a selected snapshot in the first sequence and first and second journals in the second sequence.

Claims

1. A method comprising:

storing user data in a memory;

maintaining metadata in the memory associated with the stored user data, the metadata arranged as a first sequence of snapshots of the metadata at different points in time during the operation of the memory and a second sequence of intervening journals which reflect updates to the metadata from one snapshot to the next, each of the intervening journals in the second sequence reflecting the updates to a different one of the snapshots in the first sequence, the first sequence comprising at least two copies of three most recent successive snapshots, the second sequence comprising at least two copies of three most recent successive journals and a virtual copy of the three most recent successive journals distributed and protected against an error condition using an error detection code (EDC); and

recovering requested metadata from the memory using a selected snapshot in the first sequence and first and second intervening journals in the second sequence responsive to an error condition associated with a more recent snapshot in the first sequence, the second intervening journal in the second sequence occurring at a point in time after generation of the more recent snapshot in the first sequence.

2. The method of claim 1, in which the first journal reflects the updates to the selected snapshot and the second journal reflects the updates to the more recent snapshot.

3. The method of claim 1, in which the first and second journals are both formed after the selected snapshot, the first journal is formed before the more recent snapshot, and the second journal reflects the most recent journal information for the memory.

4. The method of claim 1, in which the first journal comprises error detection and correction (EDC) codes generated in accordance with a first EDC scheme, and the second journal comprises EDC codes generated in accordance with a second EDC scheme.

5. The method of claim 4, in which a selected one of the first or second EDC schemes is a parity code scheme.

6. The method of claim 4, in which a selected one of the first or second EDC schemes is a Reed-Solomon ECC scheme.

7. The method of claim 1, further comprising using the recovered metadata to retrieve a selected block of the stored user data from the memory.

8. The method of claim 1, further comprising retrieving the first and second journals and the selected snapshot from the memory, using the retrieved first journal and the selected snapshot to reconstruct the more recent snapshot, combining the reconstructed more recent snapshot with the second journal to generate the recovered metadata, and using the recovered metadata to write a new block of user data to the memory.

9. The method of claim 1, further comprising using the recovered metadata to schedule a garbage collection operation on a garbage collection unit (GCU) of the memory, the GCU allocated and erased as a unit, the garbage collection operation erasing at least one of the snapshots in the first sequence.

10. The method of claim 1, in which data portions of the first and second journals are respectively retrieved from the memory and validated responsive to a comparison of said data portions.

11. The method of claim 10, further comprising retrieving data from a third journal associated with the first and second journals and applying error detection and correction (EDC) processing to the retrieved data from the third journal.

12. The method of claim 1, the selected snapshot comprising a relatively older snapshot in the first sequence indicative of a state of the metadata at a first time, the first sequence comprising at least one relatively newer snapshot indicative of a different state of the metadata at a different, second time.

13. An apparatus comprising:

a memory arranged into a plurality of garbage collection units (GCUs) each separately allocated and erased as a unit, the memory storing user data in the form of addressable blocks and metadata that provide a logical to physical address correspondence for the user data, the metadata arranged as a first sequence of snapshots of the metadata at different points in time during the operation of the memory and a second sequence of intervening journals of updates to the metadata from one snapshot to the next, each of the journals associated with a different one of the snapshots in the first sequence, the first sequence comprising at least two copies of three most recent successive snapshots, the second sequence comprising at least two copies of three most recent successive journals and a virtual copy of the three most recent successive journals distributed across multiple locations in the memory and protected against an error condition using error detection and correction (EDC) codes; and

a metadata recovery engine adapted to recover selected metadata from the memory using a selected snapshot in the first sequence and first and second intervening journals in the second sequence, the selected snapshot comprising an older snapshot in the first sequence indicative of a state of the metadata at an earlier first time, the first sequence further comprising a newer snapshot indicative of a different state of the metadata at a later second time.

14. The apparatus of claim 13, in which each of the journals in the second sequence is protected by a first type of EDC code, and at least one copy of the most recent journal in the second sequence is further protected by a different, second type of EDC code.

15. The apparatus of claim 13, in which the first journal reflects the changes in the metadata between the older snapshot and the newer snapshot, and the second journal reflects the changes in the metadata since the newer snapshot.

16. The apparatus of claim 13, further comprising a journal processing engine which generates first error detection and correction (EDC) codes for the first journal in accordance with a first EDC scheme and which generates different, second EDC codes for the second journal in accordance with a different, second EDC scheme.

17. The apparatus of claim 16, in which a selected one of the first or second EDC schemes is a parity code scheme.

18. The apparatus of claim 13, in which the metadata retrieval engine recovers the selected metadata using the older snapshot and the first and second journals responsive to a failure to retrieve the newer snapshot.

19. The apparatus of claim 18, in which the metadata retrieval engine further operates to concurrently apply error detection and correction (EDC) processing to a third journal formed after the selected snapshot and to compare a result of said EDC processing to at least a selected one of the first or second journals.

20. The apparatus of claim 13, in which the memory is a flash memory the GCUs are each formed from a plurality of erasure blocks, and the older and newer snapshots are each stored in a different GCU.