Efficient prefetching and asynchronous writing for flash memory

• US 8,024,545 B2
• Filed: 10/20/2008
• Issued: 09/20/2011
• Est. Priority Date: 10/19/2007
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute, INHA Industry Partnership Institute
• Original Assignee: Electronics and Telecommunications Research Institute, INHA Industry Partnership Institute
• Inventors: Park, Kwang-Hee, Kim, Deok-Hwan
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): Verderamo, III; Ralph A
• Application Number:
  US12/254,410
• Publication Number:
  US 20090106486A1
• Time in Patent Office: 1,065 Days
• Field of Search: None
• US Class Current: 711/206
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles

Abstract

Disclosed herein are a flash file system and an address translation method. The flash file system includes a file system, a Flash Translation Layer (FTL), and flash memory. The FTL receives Local Block Addresses (LBAs) from the file system, and translates the LBAs into Physical Block Address (PBAs. The flash memory receives the resulting PBAs. The FTL includes a memory block in which a multi-stage clustered hash table for mapping the LBAs to the PBAs is stored, and performs the address translation using the clustered hash table.

Claims

1. A flash file system, comprising:

a file system;

a Flash Translation Layer (FTL) for receiving Local Block Addresses (LBAs) from the file system, and translating the LBAs into Physical Block Address (PBAs); and

flash memory for receiving the resulting PBAs;

wherein the FTL includes a memory block in which a multi-stage clustered hash table for mapping the LBAs to the PBAs is stored, and performs the address translation using the multi-stage clustered hash table,

wherein the multi-stage clustered hash table stored in the memory block comprises a first clustered hash table and a second clustered hash table of a page translation type and a third clustered hash table of a block translation type, each of the clustered hash tables including buckets into each of which a predetermined number of pieces of consecutive address data is grouped,

wherein each of the LBAs recorded in each of the first clustered hash table and the second clustered hash table includes a bit vector that includes a reference bit and a modification bit respectively indicative of reference and modification of the LBA, and

wherein address data recorded in each of the clustered hash tables is migrated from the first clustered hash table to the second clustered hash table and from the second clustered hash table to the third clustered hash table on a basis of the bit vectors.

2. The flash file system as set forth in claim 1, wherein:

each of the page translation-type clustered hash tables includes buckets into each of which a predetermined number of consecutive LBAs is grouped; and

the block translation-type clustered hash table includes buckets into each of which a predetermined number of consecutive sub-blocks is grouped.

3. The flash file system as set forth in claim 1, wherein the block translation-type clustered hash table includes continuity counters, each indicative of a number of consecutive sub-blocks, along with PBAs of the sub-blocks.

4. The flash file system as set forth in claim 1, wherein if the entered LBA exists in the multi-stage clustered hash table, the FTL prefetches an entire bucket including the LBA to the memory block and then performs the address translation.

5. The flash file system as set forth in claim 1, wherein:

each memory block includes a buffer; and

if 2 bit write prediction at an address is updated by requested a write operation and 2 bit write prediction is 11 or 10, data stored in the flash memory at the address is temporarily stored in a buffer;

if the buffer becomes full or the reference bit is changed to 00 or 01, data stored in the buffer is collectively written to the flash memory.

6. The flash file system as set forth in claim 1, wherein:

each of the LBAs recorded in the multi-stage clustered hash table includes data of a hit count in which a number of uses of the LBA is recorded; and

a hit count of address data stored in each of the clustered hash tables is compared with a preset threshold value, and the address data is migrated based on a result of the comparison.

7. An address translation method using a Clustered Flash Translation Layer (CFTL), comprising the steps of:

(a) searching a page translation-type first clustered hash table for an LBA, translation of which has been requested;

(b) determining whether data corresponding to the LBA exists in the first clustered hash table, and, if the data exists, translating the LBA into a PBA;

(c) If, as a result of the determination at step (b), the data of the LBA does not exist, determination whether the data of the LBA exists in a page translation-type second clustered hash table, and, if the data exists, translating the LBA into a PBA; and

(d) if, as a result of the determination at step (c), the data of the LBA does not exist, translating the LBA into a PBA using a block translation-type third clustered hash table.

8. The address translation method as set forth in claim 7, wherein data of each address recorded in the third clustered hash table includes a hit count in which a number of uses of the address is recorded;

further comprising, after step (d), step (e) of, if the hit count exceeds a first preset threshold value, migrating the data of the address from the third clustered hash table to the second clustered hash table.

9. The address translation method as set forth in claim 7, wherein data of each address recorded in the second clustered hash table includes a hit count in which a number of uses of the address is recorded;

further comprising, after step (d), step (f) of, if the hit count exceeds a second preset threshold value, migrating the data of the address from the second clustered hash table to the first clustered hash table.

10. The address translation method as set forth in claim 7, further comprising, after step (d), step (g) of migrating data of each address recorded in the first clustered hash table or the second clustered hash table, from the first clustered hash table or the second clustered hash table to the third clustered hash table using a bit vector including a reference bit indicative of reference of the address and a modification bit indicative of modification of the address.

11. The address translation method as set forth in claim 7, wherein each of the clustered hash tables includes buckets into each of which a predetermined number of consecutive sub-blocks, including data of the LBAs, is grouped.

12. The address translation method as set forth in claim 11, wherein the third clustered hash table includes continuity counters, each indicative of a number of consecutive sub-blocks, along with PBAs of the sub-blocks.

13. The address translation method as set forth in claim 11, wherein if the LBA, the translation of which has been requested, exists in the clustered hash table, the address translation is performed after an entire bucket including the LBA has been prefetched to a memory block.