RECONSTRUCTING AN INDIRECTION TABLE FROM LOGGED MEDIA ADDRESSES

• US 20150178164A1
• Filed: 12/19/2013
• Published: 06/25/2015
• Est. Priority Date: 12/19/2013
• Status: Abandoned Application

• Current Assignee: Violin Memory Incorporated
• Original Assignee: Violin Memory Incorporated
• Inventors: Zhang, Silei
• Application Number:
  US14/135,105
• Publication Number:
  US 20150178164A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery

Abstract

The storage system uses a combination of checkpoint data and journal data to reconstruct an indirection table. The checkpoint data comprises compacted media addresses from the indirection table that are then stored in a relatively few number of media blocks. This allows the media controller to quickly read the compacted checkpoint data from the solid state media. The media controller generates the journal data from logical addresses and associated media addresses for additional write operations received while creating the checkpoint data. The media controller uses metadata when errors are identified in the checkpoint data or journal data.

Claims

1. An apparatus, comprising:

checkpoint data for an indirection table, wherein the checkpoint data is stored in a solid state media and comprises media addresses for sequential logical addresses of the indirection table;

journal data stored in the solid state media, wherein the journal data identifies changes in the indirection table after creation of the checkpoint data;

metadata summaries stored in the solid state media, wherein the metadata summaries contain error correction data for the checkpoint data and journal data; and

logic circuitry configured to;

read the checkpoint data from the solid state media;

read the journal data from the solid state media;

reconstruct the indirection table by overwriting at least some of the media addresses from the checkpoint data with media addresses from the journal data;

check for errors in the checkpoint data or the journal data; and

use the metadata summaries to recover from the errors in the checkpoint data and/or the errors in the journal data.

2. The apparatus of claim 1, wherein the indirection table comprises a linear association of the logical addresses of the indirection table with the media addresses of the solid state media.

3. The apparatus of claim 1, wherein the journal data comprises the logical addresses and associated media addresses for write operations performed after creation of the checkpoint data.

4. The apparatus of claim 1, wherein the metadata summaries contain the error correction data for blocks of sequential media address locations in the solid state memory.

5. The apparatus of claim 1, wherein the logic circuitry is further configured to:

identify locations in the solid state media associated with the errors in the checkpoint data or the errors in the journal data;

identify locations in the metadata summaries associated with the locations in the solid state media associated with the errors; and

use the error correction data at the identified locations in the metadata summaries to reconstruct the indirection table.

6. The apparatus of claim 1, wherein the checkpoint data is stored in sequential address locations in the solid state media and the error correction data is stored in locations of the metadata summaries corresponding to the sequential address locations of the checkpoint data.

7. The apparatus of claim 1, wherein the journal data is stored in sequential address locations in the solid state memory corresponding to sequential changes to the indirection table and the error correction data for the journal data is stored in locations of the metadata summaries corresponding to the sequential address locations of the journal data.

8. The apparatus of claim 1, wherein the logic circuitry is configured to overwrite the media addresses from the checkpoint data with the media addresses from the journal data in an order based on time stamps associated with the journal data.

9. The apparatus of claim 1, wherein:

the indirection table is stored in volatile memory;

the checkpoint data is stored in non-volatile solid state memory; and

the logic circuitry is configured to reconstruct in the indirection table in the volatile memory from the checkpoint data and the journal stored in the non-volatile memory in response to a power-up or reset condition.

10. A method, comprising:

identifying a reconstruction condition for an indirection table;

reading checkpoint data for the indirection table from a memory, wherein the checkpoint data comprises media addresses for sequential logical addresses of the indirection table;

reading journal data from the memory, wherein the journal data identifies changes between different stored versions of the checkpoint data;

reconstructing the indirection table by overwriting at least some of the media addresses from the checkpoint data with media addresses from the journal data;

checking for errors in the checkpoint data or the journal data;

identifying metadata summaries in the memory containing error correction data for the checkpoint data and/or journal data; and

using the error correction data in the metadata summaries to recover from the errors in the checkpoint data and/or the errors in the journal data.

11. The method of claim 10, wherein the different versions of the checkpoint data are periodically generated from different states of the indirection table and the journal data comprises the logical addresses and associated media addresses for write operations received between the different versions of the checkpoint data.

12. The method of claim 10, wherein the metadata summaries contain the error correction data for blocks of data stored in sequential address locations of the memory.

13. The method of claim 10, further comprising:

identifying address locations in the memory associated with the errors in the checkpoint data and/or the errors in the journal data;

identifying locations in the metadata summaries associated with the address locations in the memory associated with the errors; and

using the error correction data at the identified locations in the metadata summaries to reconstruct the indirection table.

14. The method of claim 10, wherein the checkpoint data is stored in sequential address locations in the memory and some of the error correction data is stored in locations of the metadata summaries corresponding to the sequential address locations of the checkpoint data.

15. The method of claim 10, wherein the journal data is stored in sequential address locations in the memory corresponding to sequential changes to the media addresses in the indirection table and the error correction data for the journal data are stored in locations of the metadata summaries corresponding to the sequential address locations of the of the journal data.

16. The method of claim 10, further comprising reconstructing the indirection table by overwriting the media addresses from the checkpoint data with the media addresses from the journal data in an order based on time stamps associated with the journal data.

17. The method of claim 10, wherein the checkpoint data and journal data are stored in non-volatile memory, and further comprising reconstructing the indirection table in volatile memory from the checkpoint data and the journal stored in the non-volatile memory in response to a power-up or reset condition.

18. An apparatus, comprising:

non-volatile memory configured to store checkpoint data for an indirection table, journal data containing changes in the checkpoint data, and metadata summaries containing error correction data for the checkpoint data and journal data; and

a media controller configured to;

read the checkpoint data and the journal data from the non-volatile memory into a volatile memory;

reconstruct the indirection table by updating at least some of the checkpoint data with the journal data; and

use the metadata summaries to recover from errors in the checkpoint data and/or errors in the journal data.

19. The apparatus of claim 18, wherein the indirection table comprises a linear association of logical addresses with media addresses in the non-volatile memory.

20. The apparatus of claim 18, wherein the metadata summaries contain error correction data for blocks of data stored in sequential address locations of the non-volatile memory.

21. The apparatus of claim 18, wherein the media controller is further configured to:

identify locations in the non-volatile memory associated with the errors in the checkpoint data and/or the errors in the journal data;

identify locations of the error correction data in the metadata summaries associated with the locations in the non-volatile memory associated with the errors; and

use the error correction data at the identified positions in the metadata summaries to reconstruct the indirection table.

22. The apparatus of claim 18, wherein the checkpoint data is stored in sequential address locations of the non-volatile memory and some of the error correction data is stored in locations of the metadata summaries corresponding to the sequential address locations of the checkpoint data.

23. The apparatus of claim 18, wherein the journal data is stored in sequential address locations of the non-volatile memory corresponding to sequential changes to the media addresses in the indirection table and the error correction data is stored in positions of the metadata summaries corresponding to the sequential address locations of the journal data.