METHOD TO EFFICIENTLY LOCATE META-DATA STRUCTURES ON A FLASH-BASED STORAGE DEVICE

• US 20110131231A1
• Filed: 11/30/2009
• Published: 06/02/2011
• Est. Priority Date: 11/30/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haas, Robert, Hu, Xiao-Yu, Pletka, Roman A.
• Granted Patent: US 8,250,324 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

Flash memory systems and methods for efficiently locating meta-data structures on solid-state devices, such as, flash-based memory devices, which allows for fast reconstruction of metadata structures are provided. These systems and methods place checkpoints, which identify the location of metadata structures, intelligently on the device so as to permit a more efficient method of locating such checkpoints. These techniques ensure best wear-leveling as all blocks on the device undergo the same wear-leveling strategy. These systems and methods further provide a free block maintenance strategy that provides blocks freed by garbage collection for future checkpoint writes.

Claims

1. A method for facilitating fast reconstruction of metadata structures on a memory storage device, comprising:

writing a plurality of checkpoints holding a root of metadata structures in an increasing order of timestamps to a plurality of blocks respectively on the memory storage device utilizing a memory controller, each checkpoint is associated with a timestamp, wherein the last-written checkpoint contains a root to the latest metadata information from where metadata structures are reconstructed.

2. The method of claim 1, wherein timestamps of the plurality of checkpoints increase in time over a physical block address space of the memory storage device, the physical block address space includes the plurality of blocks.

3. The method of claim 2, wherein the plurality of checkpoints are written about equidistant from one another over the physical block address space of the memory storage device or written unevenly from one another over the physical block address space of the memory storage device.

4. The method of claim 3, wherein the plurality of checkpoints are written equidistant from one another by maintaining blocks on the memory storage device freed by a garbage collection process in a free block queue.

5. The method of claim 4, wherein blocks freed by the garbage collection process are maintained by placing freed blocks with any page outside an interval in a first queue and placing freed blocks with a page on the interval in a second queue.

6. The method of claim 5, wherein the first queue is a normal free queue consumed by future normal writes while the second queue is a checkpoint free queue consumed by future checkpoint writes.

7. The method of claim 5, wherein the interval is based on the position of a page reserved for the last future checkpoint to be written.

8. The method of claim 7, wherein the interval is [X+N−

k, X+N+k], where k is a constant in the interval 1≦

k≦

N/2, X is the position of the page reserved for the last future checkpoint to be written, and N is an average space in the number of pages between two checkpoints.

9. The method of claim 1, wherein metadata information includes logic block address to physical block address mapping tables, error correction codes, a bad block list, or a combination thereof.

10. The method of claim 1, wherein the memory storage device is a flash-based memory storage device.

11. A method for locating metadata structures in a memory storage device, comprising:

writing a plurality of checkpoints holding a root of metadata structures in an increasing order of timestamps to a page on each of a plurality of blocks respectively within a physical block address of the memory storage device, each checkpoint is associated with a timestamp; and

performing a search on a limited number of pages on the memory storage device for the last-written checkpoint holding a root to the latest metadata information from where metadata structures are reconstructed.

12. The method of claim 11, wherein performing a search for the last-written checkpoint comprises:

selecting a first and a second starting page in the physical block address space of the memory storage device;

searching for a checkpoint closest to the first and second starting page;

reading the timestamp associated with the checkpoint closest to the first starting page and the second starting page;

calculating whether the distance between the checkpoint closest to the first starting page and the second starting page is less than a calculated interval; and

determining whether the last-written checkpoint has been located based on the calculation, the last-written checkpoint having the greatest timestamp among the plurality of checkpoints written in the memory device.

13. The method of claim 12, wherein the last-written checkpoint is located when the distance between the checkpoint closest to the first starting page and the second starting page is less than the calculated interval.

14. The method of claim 12, wherein new starting pages are selected until the distance between the checkpoints found closest to the new starting pages is less than the calculated interval.

15. The method of claim 12, wherein the calculated interval is found by equation N−

k, where N is the average space in the number of pages between two checkpoints, k is an arbitrary integer in the interval 1≦

k≦

N/2, and C denotes the capacity in terms of page of the memory storage device.

16. The method of claim 11, wherein timestamps of the plurality of checkpoints increase in time over the physical block address space of the memory storage device.

17. The method of claim 11, wherein the plurality of checkpoints are written equidistant from one another over the physical block address space of the memory storage device or written unevenly from one another over the physical block address space of the memory storage device.

18. The method of claim 17, wherein the plurality of checkpoints are written equidistant from one another by maintaining blocks on the memory storage device freed by a garbage collection process in a free block queue.

19. The method of claim 18, wherein blocks freed by the garbage collection process are maintained by placing freed blocks with any page outside an interval in a first queue and placing freed blocks with a page on the interval in a second queue, the first queue is a normal free queue consumed by future normal writes while the second queue is a checkpoint free queue consumed by future checkpoint writes.

20. The method of claim 19, wherein garbage collection of a new block having a page in the target interval is triggered if the length of the checkpoint free queue falls below a certain threshold.

21. A system, comprising:

a memory storage device having a plurality of blocks with pages for writing data; and

a controller in signal communication with the memory storage device, the controller configured to write a plurality of checkpoints holding a root to metadata structures in an increasing order of timestamps to a page on each of a plurality of blocks respectively within a physical block address of the memory storage device and perform a search on a limited number of pages on the memory storage device for the last-written checkpoint holding a root to the latest metadata information from where metadata structures are reconstructed.

22. The system of claim 21, wherein the plurality of checkpoints are written about equidistant from one another over the physical block address space of the memory storage device or written unevenly from one another over the physical block address space of the memory storage device.

23. The system of claim 22, wherein the plurality of checkpoints are written equidistant from one another by maintaining blocks on the memory storage device freed by a garbage collection process in a free block queue.

24. The system of claim 23, wherein blocks freed by the garbage collection process are maintained by placing freed blocks with any page outside an interval in a first queue and placing freed blocks with a page on the interval in a second queue.

25. The system of claim 24, wherein the interval is based on the position of a page reserved for the last future checkpoint to be written, the interval is [X+N−

k, X+N+k], where k is a constant in the interval 1≦

k≦

N/2, X is the position of the page reserved for the last future checkpoint to be written, and N is an average space in the number of pages between two checkpoints.