[NVMW 2016] Develop A Fast Flash Translation Layer by Exploiting Block-Level I/O Correlation

NAND Flash has a distinct erase-before-write feature com-

pared to traditional memory media. The Flash Translation

Layer (FTL) in Nand Flash based Solid State Disks (SSDs),

redirects the write to a free physical location and manages

a logical to physical translation table. To accelerate the address translation, the FTL leverages the built-in DRAM to

assist mapping table cache, prefetch technologies, and data

buffers, all of which take advantage of the temporal and

spatial locality in workloads. With the increasing capacity

of SSDs, the size of mapping tables and other metadata,

such as garbage collection and wear leveling information, are

also increased. This creates a demand to optimize the FTL

and cache algorithms for environments with limited DRAM

resources. What’s more, temporal and spatial locality based

cache or prefetch algorithms can not deliver high performance

for the FTL. First, because on the host side there is a large

data buffer governed by cache and prefetch algorithm, the

workloads inside a SSDs often exhibit very low locality

compared to the original application workloads and can be

dominanted by random read/writes in real world workloads

such as transaction workloads. Second, because current cache

replacement algorithms mainly exploit temporal locality, those

mapping entries having low access frequency might stay in

the cache and thus make entries having high access frequency

become replacement victims. To resolve this problem, in the

light of data correlation information, we propose Correlation-

Aware Page-level FTL, a.k.a CPFTL, which exploits semantic

patterns of workload directly in the SSD, and pertain to higher

level system software optimizations.