  Storage devices based on flash memory have replaced hard disk drives (HDDs)
due to their superior performance, increasing density, and lower power
consumption. Unfortunately, flash memory is subject to challenging
idiosyncrasies like erase-before-write and limited block lifetime. These
constraints are handled by a flash translation layer (FTL), which performs
out-of-place updates, wear-leveling and garbage-collection behind the scene,
while offering the application a virtualization of the physical address space.
  A class of relevant FTLs employ a flash-resident page-associative mapping
table from logical to physical addresses, with a smaller RAM-resident cache for
frequently mapped entries. In this paper, we address the problem of performing
garbage-collection under such FTLs. We observe two problems. Firstly,
maintaining the metadata needed to perform garbage-collection under these
schemes is problematic, because at write-time we do not necessarily know the
physical address of the before-image. Secondly, the size of this metadata must
remain small, because it makes RAM unavailable for caching frequently accessed
entries. We propose two complementary techniques, called Lazy Gecko and
Logarithmic Gecko, which address these issues. Lazy Gecko works well when RAM
is plentiful enough to store the GC metadata. Logarithmic Gecko works well when
RAM isn't plentiful and efficiently stores the GC metadata in flash. Thus,
these techniques are applicable to a wide range of flash devices with varying
amounts of embedded RAM.
