METHOD AND SYSTEM FOR STORAGE OF DATA IN NON-VOLATILE MEDIA

• US 20090150599A1
• Filed: 11/18/2008
• Published: 06/11/2009
• Est. Priority Date: 04/21/2005
• Status: Active Grant

• Current Assignee: Innovations In Memory LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: Bennett, Jon C. R.
• Granted Patent: US 8,452,929 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A system and method for managing the storage of data in non-volatile memory is described. In an aspect, the data may be described by metadata and a transaction log file that are checkpointed from a volatile memory into the non-volatile memory. Actions that take place between the last checkpointing of a metadata segment and log file segment are discovered by scanning the non-volatile memory blocks, taking account of a record of the highest sector in each block that is known to have been recorded. Any later transactions are discovered and used to update the recovered metadata so that the metadata correctly represents the stored data.

Claims

1. A method of operating a memory system, the method comprising;

maintaining a checkpointed copy of a dynamic table in non-volatile storage (NVS);

maintaining a transaction log for the dynamic table;

discovering changes to the dynamic table that are not contained in the transaction log;

updating the dynamic table by applying the transactions in the transaction log and the discovered changes.

2. The method of claim 1, wherein the checkpointed copy of the dynamic table is read from the NVS to volatile storage.

3. The method of claim 2, wherein the dynamic table includes an index value for a block of a flash memory, the index value being the highest incremental value of a sector number of the block written with data.

4. The method of claim 3, wherein discovering changes includes the step of inspecting the block to determine if data has been written to a sector having an index value greater than the index value of the block.

5. The method of claim 4, wherein an indication that data has been written to the sector is that the data bits are other than all “

1”

.

6. The method of claim 4, wherein an indication that data has been written to the sector is that the data bits of the spare data area of the sector are other than all “

1”

.

7. The method of claim 4, wherein discovering changes includes the step of inspecting at least a lowest numbered sector of each block to determine if the block has been erased since a checkpoint of the transaction log.

8. The method of claim 4, wherein the discovered changes include spare data.

9. The method of claim 8, wherein the spare data includes the logical block address of the data, and a transaction sequence number.

10. The method of claim 8, wherein the spare data includes a previous sector address of the data.

11. The method of claim 3, wherein the sector is a plurality of sectors.

12. The method of claim 10, where four (4) sectors are a page, and the discovered changes are with respect to the page of data.

13. The method of claim 1, wherein a sequence number is assigned sequentially to each change of the dynamic table.

14. The method of claim 1, wherein the dynamic table is metadata representing at least a base memory address of data written to each of a minimum writable memory circuit address range.

15. The method of claim 1, wherein the metadata relates a logical block address to a physical sector address and the dynamic table is maintained in non-volatile storage by checkpointing in portions.

16. The method of claim 1, wherein the dynamic table contains metadata data for a plurality of blocks, each block comprised of sectors.

17. The method of claim 1, wherein the dynamic table and the transaction log are check pointed to non-volatile storage in segments.

18. The method of claim 17, wherein each segment of the dynamic table is checkpointed before the same segment is checkpointed again.

19. The method of claim 17, wherein each segment of the dynamic table is checkpointed when a predetermined number of changes have been made to the contents of the segment.

20. The method of claim 17, wherein each segment of the dynamic table is checkpointed after a predetermined elapsed time since the last checkpoint.

21. The method of claim 1, wherein the checkpointed transaction log in NVS is maintained by writing the contents of the most recent segment of a volatile transaction log to the transaction NVS.

22. The method of claim 1, wherein the size of the transaction log in NVS is sufficient to maintain a record of the transactions affecting the dynamic table since the last time that each of the segments of the dynamic table has been checkpointed.

23. The method of claim 1, wherein spare data for discovered changes is written to a recovery log.

24. The method of claim 23, wherein the spare data are ordered in the recovery log by a transaction sequence number extracted from the spare data.

26. The method of claim 3, wherein the sector corresponding to the index value for the block is inspected.

27. The method of claim 9, wherein when the sector contains an indication that the block has been erased by an erase transaction, a free sector table is updated.

28. The method of claim 1, wherein user data written in NVS is written using a RAID algorithm.

29. The method of claim 28, wherein dynamic table data contains a sequence number of the RAID data.

31. The system of claim 15, wherein dynamic table contains the metadata including a mapping of logical address to physical address and an index value for a writable data area of the NVS index the value representing the highest writable data area of a block of the NVS to which data has been written.

40. The computer program product of claim 24, wherein the block cannot be erased until the data of all sectors in the block having live data has been relocated to free sectors of another block.

25. The method of claim 25, wherein the ordered spare data are used to update the dynamic table by applying the transaction information contained in the spare data.

41. The computer program product of claim 25, wherein when data of a sector location is modified, a sector location of the modified data is changed that of a free page to which the modified data is written and the sector location from which the modified data has been moved is marked as a dead page.

30. A system for storage of data, the system comprising:

a volatile memory device (VS);

a non-volatile memory device (NVS); and

a processor in communication with the volatile memory device and the non-volatile memory device,

wherein the processor is configured to maintain a dynamic table in volatile storage representing data stored in the NVS, a checkpointed version of the dynamic table in NVS, and a log representing transactions affecting the stored, and to repair the dynamic table by discovering data written to the NVS between the last update of the log and a time of repair.

32. A computer program product, stored or distributed in or on a computer readable medium, comprising instructions for:

configuring a processor and memory system to maintain metadata in a volatile storage device representing data stored in a non-volatile storage device (NVS);

maintaining a checkpointed version of the metadata in NVS and a transaction log; and

repairing the metadata by;

applying the transactions of the transaction log to the metadata to update the metadata;

discovering a transaction written to NVS where the transaction log in NVS had not been updated to include the transaction; and

applying the discovered transactions to update the metadata.

33. The computer program product of claim 32, where the discovered transactions are arranged in an ordered sequence prior to applying.

34. The computer program product of claim 33, wherein the discovered transaction includes determining whether a block of data of the NVS has been erased and the transaction has not been recorded in the checkpointed metadata or the transaction log, and updating the metadata.

35. The computer program product of claim 32, wherein the metadata includes an index value representing a highest sector location that has data written thereto in a block of the NVS.

36. The computer program product of claim 32, wherein the metadata includes a listing of free blocks.

37. The computer program product of claim 36, wherein a free block is comprised of all free sectors.

38. The computer program product of claim 37, wherein data is written to free sectors of a block in order of increasing index value.

39. The computer program product of claim 38, wherein when data is written to the free sector, the sector is considered to have valid data and the sector cannot be written to again until the block has been erased.

42. A method of operating a memory system, the method comprising;

assigning a sequence number to each data element for determining the latest version of the data element;

setting a flag to indicate when the sequence number is not valid for use.

43. A method of operating a memory system, the method comprising:

creating metadata representing information relating a data element stored in a memory, the metadata having a field having an address where the data element is stored;

replacing the address data with a flag when the data element is a known data pattern, the flag indicating the data pattern.