Storage apparatus using non-volatile memory as cache and method of managing the same

• US 7,774,541 B2
• Filed: 11/20/2006
• Issued: 08/10/2010
• Est. Priority Date: 12/27/2005
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: Lee, Shea-yun, Song, Dong-hyun, Kim, Jang-hwan, Shin, Dong-kun
• Primary Examiner(s): Thomas; Shane M
• Application Number:
  US11/601,819
• Publication Number:
  US 20070150654A1
• Time in Patent Office: 1,359 Days
• Field of Search: 711/103, 711/113, 711/3
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/282 Partitioned cache
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

A storage apparatus using a non-volatile memory, which retains data even after power interruption, as its cache and a method of managing the same are provided. The storage apparatus includes a main storage medium, a non-volatile memory used as a cache of the main storage medium, a region of the non-volatile memory being divided into a fixed region and a non-fixed region according to whether or not data is fixed, and a block management unit managing physical blocks by means of virtual addresses, the physical blocks being allocated to the non-volatile memory.

Claims

1. A storage apparatus comprising:

a main storage medium;

a non-volatile memory, which is used as a cache of the main storage medium, wherein a region of the non-volatile memory is divided into a fixed region and a non-fixed region according to whether or not data is fixed; and

a block management unit which manages physical blocks using virtual addresses, wherein the physical blocks are allocated to the non-volatile memory,

wherein the block management unit comprises;

a block allocation unit, which allocates physical blocks to the non-volatile memory;

a block collection unit, which collects the physical blocks allocated to the non-volatile memory;

a bad block management unit, which manages a bad block;

a power interruption recovery unit, which restores the storage apparatus using a logical block address, and fixed region and non-fixed region data indicators, stored in the non-volatile memory as a metadata in case of an unexpected power interruption;

a block mapping table management unit, which manages a block mapping table indicating a mapping relationship between physical block numbers and virtual block numbers that are allocated to the physical block numbers; and

a list storage unit, which stores an allocated block list enumerating allocated physical blocks and a free block list enumerating vacant physical blocks.

2. The storage apparatus of claim 1, wherein the block allocation unit is adapted to allocate a foremost physical block on the free block list to the fixed region or to the non-fixed region.

3. The storage apparatus of claim 2, wherein the free block list enumerates vacant physical blocks in order of increasing wear level.

4. The storage apparatus of claim 2, wherein the block allocation unit is adapted to position the physical block at an end of the allocated block list.

5. The storage apparatus of claim 4, wherein the block mapping table management unit is adapted to store a block mapping table having virtual block numbers, which are allocated to physical block numbers that are enumerated in the allocated block list and to physical block numbers that are enumerated in the free block list, and

wherein the block mapping table management unit allocates a virtual block number to a last physical block number on the allocated block list so that the block mapping table is updated.

6. The storage apparatus of claim 1, wherein the block collection unit is adapted to count effective pages of respective physical blocks on the allocated block list, and

wherein the block collection unit performs block collection beginning with a physical block having a smallest number of effective pages.

7. The storage apparatus of claim 6, wherein the block collection unit is adapted to position a physical block at an end of the allocated block list, and

wherein the block collection unit moves effective pages in a physical block due for block collection to the physical block at the end of the allocated block list.

8. The storage apparatus of claim 7, wherein the block collection unit is adapted to add a physical block to the free block list according to a wear level when the physical block due for block collection is vacant after effective pages are moved out.

9. The storage apparatus of claim 1, wherein the bad block management unit is adapted to move data out of a physical block on the allocated block list when the physical block comprises a bad block, to a physical block which is newly allocated from the free block list, and wherein the physical block comprising the bad block is exempted from allocation.

10. The storage apparatus of claim 9, wherein the bad block management unit is adapted to insert the physical block which is newly allocated from the free block list into a previous position of the physical block comprising the bad block, and

wherein the block mapping table management unit is adapted to allocate a virtual block number to a physical block number of the physical block which is inserted,

wherein the allocated virtual block number was previously allocated to the physical block comprising the bad block.

11. The storage apparatus of claim 1, wherein the power interruption recovery unit is adapted to extract the allocated block list and to restore the block mapping table in case of the unexpected power interruption.

12. The storage apparatus of claim 1, wherein the fixed region stores data that permanently resides in the non-volatile memory and is used as the cache of the main storage medium, and the non-fixed region stores data that frequently moves to or from the main storage medium.

13. The storage apparatus of claim 1, wherein the power interruption recovery unit restores the storage apparatus using the logical block address, the fixed region and non-fixed region data indicators, and a restoration mark, and

wherein the allocated block list and the free block list are stored together as a single list, and the restoration mark is at the beginning of the free block list and differentiates between the allocated block list and the free block list.

14. A method of managing a storage apparatus, the method comprising:

dividing a region of a non-volatile memory, which is used as a cache of a main storage medium, into a fixed region and a non-fixed region according to whether data is fixed or non-fixed; and

managing physical blocks allocated to the fixed region and allocated to the non-fixed region using virtual addresses which are allocated to the physical blocks, respectively,

wherein the managing the physical blocks comprises;

allocating physical blocks to the non-volatile memory;

collecting the physical blocks allocated to the non-volatile memory;

managing a bad block;

recovering from an unexpected power interruption using a logical block address, and fixed region and non-fixed region data indicators, stored in the non-volatile memory as a metadata;

managing a block mapping table which indicates a mapping relationship between physical block numbers and virtual block numbers allocated to the physical block numbers;

storing an allocated block list which enumerates allocated physical blocks; and

storing a free block list which enumerates vacant physical blocks.

15. The method of claim 14, wherein the allocating physical blocks comprises allocating a foremost physical block on the free block list to the fixed region or to the non-fixed region.

16. The method of claim 15, wherein the free block list enumerates vacant physical blocks in order of increasing wear level.

17. The method of claim 15, wherein the allocating physical blocks comprises positioning the physical block at an end of the allocated block list.

18. The method of claim 17, wherein the managing a block mapping table comprises:

storing a block mapping table having virtual block numbers, which are allocated to physical block numbers that are enumerated in the allocated block list and to physical block numbers that are enumerated in the free block list; and

allocating a virtual block number to a last physical block number on the allocated block list so that the block mapping table is updated.

19. The method of claim 14, wherein the collecting the physical blocks comprises:

counting effective pages of respective physical blocks on the allocated block list; and

performing block collection beginning with a physical block having a smallest number of effective pages.

20. The method of claim 19, wherein the collecting the physical blocks comprises:

positioning a physical block at an end of the allocated block list, and

moving effective pages in a physical block due for block collection to the physical block at the end of the allocated block list.

21. The method of claim 20, wherein the collecting the physical blocks comprises adding a physical block to the free block list according to a wear level when the physical block due for block collection is vacant after effective pages are moved out.

22. The method of claim 14, wherein the managing a bad block comprises:

moving data out of a physical block on the allocated block list when the physical block comprises a bad block, to a physical block which is newly allocated from the free block list; and

exempting the physical block comprising the bad block being from allocation.

23. The method of claim 22, wherein the managing a bad block comprises:

inserting the physical block which is newly allocated from the free block list into a position of the physical block comprising the bad block; and

allocating a virtual block number to a physical block number of the physical block which is inserted,

wherein the allocated virtual block number was previously allocated to the physical block comprising the bad block.

24. The method of claim 14, wherein the recovering from the unexpected power interruption comprises:

extracting the allocated block list; and

restoring the block mapping table in case of the unexpected power interruption.

25. The method of claim 14, wherein the fixed region stores data that permanently resides in the non-volatile memory and is used as the cache of the main storage medium, and the non-fixed region stores data that frequently moves to or from the main storage medium.

26. The method of claim 14, wherein the recovering is performed using the logical block address, the fixed region and non-fixed region data indicators, and a restoration mark stored in the non-volatile memory as a metadata, and

wherein the allocated block list and the free block list are stored together as a single list, and the restoration mark is at the beginning of the free block list and differentiates between the allocated block list and the free block list.