Flash memory system and designing method of flash translation layer thereof

• US 20100100667A1
• Filed: 10/07/2009
• Published: 04/22/2010
• Est. Priority Date: 10/16/2008
• Status: Active Grant

• Current Assignee: Korea Advanced Institute of Science and Technology, Samsung Electronics Co. Ltd.
• Original Assignee: Korea Advanced Institute of Science and Technology, Samsung Electronics Co. Ltd.
• Inventors: Lee, Yong-Goo, Kim, Jin Soo, Kang, Jeonguk, Park, Chanik
• Granted Patent: US 8,495,280 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

The method of designing a flash translation layer includes receiving a logical address according to an external request and mapping a physical address that corresponds to the logical address. The mapping manages continuous logical addresses and physical addresses corresponding to the logical addresses as one mapping unit.

Claims

1. A method of designing a flash translation layer, the method comprising:

receiving a logical address according to an external request; and

mapping a physical address that corresponds to the logical address,

wherein the mapping manages continuous logical addresses and physical addresses corresponding to the logical addresses as one mapping unit.

2. The method of claim 1, wherein the mapping maps using a μ

tree.

3. The method of claim 2, wherein the mapping defines a mapping entry of the mapping unit to include,

a tree key storing a first logical address among the continuous logical addresses, and

a tree record storing a first physical address among the physical addresses and the number of continuous pages.

4. The method of claim 3, wherein the mapping merges two continuous address mapping entries into one address mapping entry.

5. The method of claim 2, further comprising:

managing bit map information through the μ

tree, where the bit map information is used for used for garbage collection.

6. The method of claim 5, wherein the managing manages a bit map entry of the bit map information to include:

a tree key storing a physical block number; and

a tree record storing valid and invalid information of pages corresponding to the physical block number.

7. The method of claim 6, wherein,

the physical block number corresponds to a physical block, and

data of a logical address where a write is frequently made and data of a logical address where a write is infrequently made are mixed in the physical block.

8. The method of claim 6, wherein the managing manages the bit map entry of the bit map information to further include,

the tree key storing a sub-block number corresponding to at least one of a plurality of sub-blocks, wherein

the physical block number is divided into the plurality of sub-blocks, and

the tree record is allocated separately for each of the sub-blocks.

9. The method of claim 8, wherein the bit map entry is associated with at least one of the plurality of sub-blocks if the associated sub-block includes at least one invalid page.

10. The method of claim 5, wherein the mapping updates address mapping information and the managing updates bit map information in the μ

tree at each write request.

11. The method of claim 5, wherein the bit map information about a physical block having at least one valid page is stored in the μ

tree.

12. The method of claim 1, wherein the mapping manages address mapping information and bit map information using the μ

tree, the bit map information not being updated in the μ

tree each time a write request is made and the bit map information being collected in a bit map cache using a hash table.

13. The method of claim 12, wherein the mapping further comprises:

storing information about a plurality of continuously invalidated physical pages at an entry of the hash table; and

erasing all the entries of the hash table in the bit map cache when a size of the bit map cache is greater than a value and then updating the bit map information in the μ

tree.

14. The method of claim 13, wherein the mapping further comprises:

erasing entries of the hash table of the determined block and then updating the bit map information in the μ

tree when a block of a garbage collection target is determined.

15. The method of claim 1, wherein the mapping divides an entire logical address region into a plurality of partitions, and allocates at least one update block into at least one of the divided partitions, where the update block stores new data delivered at a write request, and includes at least one of a valid page, an invalid page, and a free page.

16. The method of claim 15, wherein the mapping allocates the update block for a corresponding partition of the divided partitions only when the write request is made, and does not allocate the update block for the corresponding partition when no write request is made.

17. The method of claim 16, wherein the mapping writes the write request to include:

writing data in the update block of the partition corresponding to the logical address of the write request;

at least one of modifying, erasing, and inserting the mapping unit corresponding to the update block;

inserting an invalid pair into the bit map cache to update the bit map information;

including the bit map update information in the μ

tree if the bit map cache is full or is selected as a garbage collection target block;

storing a μ

tree entry in a memory if a μ

tree cache is full; and

reading the μ

tree entry from the memory if the μ

tree entry is not found in the μ

tree cache.

18. A memory system comprising:

a non-volatile memory; and

a memory controller controlling the non-volatile memory, wherein

the memory controller has a file translation layer, the file translation layer receiving a logical address according to an external request and mapping a physical address that corresponds to the logical address, and

the mapping manages continuous logical addresses and physical addresses corresponding to the logical addresses in one mapping unit.