Demand-based flash translation layer considering spatial locality

A flash translation layer (FTL) is a firmware inside a SSD to support traditional file systems with NAND flash memory. One such FTL, the page mapping scheme shows high performance but requires a large mapping table to be stored in random access memory (RAM). Demand-based FTL (DFTL), which only stores frequently used mapping entries in RAM, overcomes this drawback. However, it has a weakness that the cached mapping table (CMT) that contains frequently used mapping entries must be sequentially searched; moreover, if the CMT is kept too small, frequent replacement of mapping entries may impair performance. Here, we propose a scheme in which the spatial locality of typical disk patterns is employed and clustered mapping entries are loaded into RAM. The scanning overhead of the CMT is also eliminated by using two-level mapping tables. We experimentally show that the presented scheme significantly reduces RAM usage while retaining comparable performance.