Figure 1: Three Types of Merge Operations
DBA which occupies most of the flash memory while each
valid page in the LBA is traced by another page-level map-
ping. The LBA is very small and generally takes less than 5
percent of th e entire flash memory. In hybrid FTLs (except
HFTL [17]), the LBA is used to store overwriting data and
different schemes adopt different strategies to merge data in
the LBA to the DBA to generate new space for the LBA.
There are three types of merge operations as illustrated in
Figure 1. A full merge is a general but expensive operation
in w h ich a ll up-to-date pages need to be copied to a new
allocated block and then old blocks are erased and put back
into the free block pool. The partial and sw itch merges are
efficient but can only be done in special cases s in c e they can
only be done when pages in th e log block or the repla c ement
block are all free or valid and each valid page is written in
their own place. Although many hybrid FTL schemes t r y to
do partial or switch merges whenever possible, full merges
are difficult to avoid with different a c c es s patterns. This
makes an insuperable bottleneck for all hybrid FTL schemes.
It is also possible to map variab le-len g th continuous logical
pages to continuou s physical pages in flas h memory. In this
case, granular ity can be adjusted dynamically when access
pattern changes. However, since sizes of different mapping
units are not identical and are changing, mapping entries can
only be stored in some type of search tree, and as a result,
the table look-up overhead of variable-length mappings is
higher than other schemes of which the mapping table is
nothing more than a simple address array.
2.3 Page-level FTL Schemes
The fir s t FTL scheme was patented by Ban in 1995 [3]
and was adopted by the PCMCIA as a standard for NOR-
based flash memories several years later [12]. There is one
issue that NOR-based FTLs should handle in the first place.
When a page is overwr itten , the relevant entr y in flash mem-
ory needs to be updated to keep the operation atomic and
reliable. (Remember that p a g e-level FTL schemes keep an
entire mir r o r of the mapping table in flash memory to re-
duce the SRAM overhead.) This presents no difficulty to
the NOR-based FTL since NOR-type flash memories can be
programmed in bytes. By assigning a replacement page list
for the relevant mapping page when necessary, this mapping
page can be updated (written in the first free entry of the
same offset in the replacement page list) several times as
long as the length of the list without rewritin g the entire
mapping page [12, 9].
DFTL (Demand-based FTL) [10], ano th er page-level FTL
scheme, makes the first attempt to transfer the former NOR-
based FTL to NAND-type flas h memories, omitting the re-
placement page part. This scheme, though efficient, faces a
serious reliability problem since a ll modified information in
the SRAM will be lost if a system failure occurs. In this case,
spare areas of all data pages need to be scanned until the sys-
tem r ec overs t o a consistent state. Therefore, DFTL is not
suitable, we believe, for circumstances where flash memory
is regarded as a permanent and reliable storage device.
2.4 Block-level FTL Schemes
Ban patented two other FTL schemes in 1999 [4, 8, 9].
These schemes are designed for NAND-type flash memories
and also known as the NF T Ls . In this paper, they will be
cited as NFTL-1 and NFTL-N. NFTL-1 is design ed for flash
memories that have a spare area for each page and NFTL-N
is for devices without such storage.
When a page is overwritten, NFTL-1 first allocates a re-
placement block for th e relevant logical b lock if there is none
and writes overwriting pages one after a n o th er from the be-
ginning of the replacement block. Since pag es are wr itten
in an out-of-place manner in replacement blocks, NFTL-1
needs to scan all the spare areas in the replacement block
in reversed order to find the most up-to-date version of a
requested page. Fortunately, the spare areas in NAND-type
flash memory are usin g a different addressing algorithm th a t
is optimized for fast reference and the overhead of this search
process is relatively low.
On the other hand, since some models of NAND flash
memories have no spare areas to support fast search, NFTL-N
keeps a replacement block list for some of the logical blocks
when necessary and write requests for each log ic a l p a g e are
first han d led by the first block in the list and th en the next
one, keeping the in-block offset identical with that of the
logical address. If all pages in the list with the request off-
set have been programmed , a n ew block is allocated and
appended to the back of the list.
2.5 Hybrid FTL Schemes
BAST (Block-Associative Sector Translat io n ) is the first
hybrid FTL scheme proposed in 2002 [15], which is essen-
tially an altered version of NFTL-1. As mentioned ear-
lier, hybrid FTL schemes build a page-level mapping for the
LBA. To keep this table small enough to reside in the SRAM,
BAST limits the tota l number of replacement blocks (also
known as log blocks). Obviously, the read performance of
BAST is better than N F T L-1 bec a u s e the SRAM is several
orders of magnitude faster tha n flash memories. However,
BAST does not work well with random overwrite patterns
which may result in a block thrashing p r o b lem [20]. Since
each replacement block can accommodate p a g es from only
one logical block, BAST can eas ily run out of free replace-
ment blocks and be forced to reclaim replacement blocks
that have not been filled. Therefore, the utilization ratio of
replacement blocks in BAST is low both theoretically and
experimentally.
To solve the block thrashing p r o b lem, another hybrid FTL
scheme named FAST (Fully Associative Sector Translation)
was put forward [20]. FAST goes to the other extreme by
allowing a log block to hold updates from any data block.
Although FAST successfully delays garbage collections as
much as possible, the system-wide latency for r ec la imin g
a single log block may turn out to be longer than BAST,
since the assoc ia tivity of log blocks is only limited by the
number o f pages in a block. The associativity of a log block
is defined as the number of different data blo cks whose most
up-to-date pages are located in the log block. The higher
the associativity of a log block is, the more expensive it is to