Patent ID: 8024545
Filing Date: 2011-09-20
Classification: G06F,G11C

Abstract:
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.