Journal

ACM TECS’07

Authors

Sang-won Lee, Dong-joo Park, Tae-sun Chung, Dong-ho Lee, Sangwon Park, Ha-joo Song

Summary

Motivation

BAST has the low space utilization because of its block-level associativity. Fully-associativity can overcome the low space utilization.

BAST

  • Scheme

    If the target sector in the data block is already written, FTL writes the given sector data at the same offset in a free-block allocated with the free-block list, and copies all the other written sectors in the data block to the free block. Then, FTL erases the data block and returns it th the free-block list.

    Whenever a collision between the current write and the previous writes occurs, merge operation is triggered. BAST reduces the number of merge operations by writing data to temporary storage, called log blocks.

  • Log block scheme: a cache for writes

    The log blocks in the log block scheme can also be viewed as “a cache for overwrites”. There is the associativity issue between memory and cache regarding how memory blocks are mapped to cache blocks. The log block scheme takes the block-associative approach.

  • Disadvantages

    BAST has low space utilization because of block-thrashing and block-level associativity. The space utilization in BAST gets worse as the write pattern becomes more random.

FAST

  • Key idea

    Fully associative approach: a logical sector can be placed in any log block. This alleviate log block thrashing and can avoid many merge operation.

  • The architecture

    The architecture of FAST is analogous to that of BAST.

    One important difference is the log blocks in FAST are divided into two areas: sequential writes and random writes. By seperating two types, FAST can get little chance for switch optimization.

    The other difference is that FAST maintains separate sector-level mapping tables for the above two types of log blocks.

    FAST maintains the sector-mapping table in SRAM. For consistency, the sector mapping table in SRAM is dynamically constructed during the booting time from the sector-mapping information stored in the spare area of the physical sector.

  • Handling write operations

    The log blocks in FAST are divided into two groups: the SW and the RW log blocks. FAST directs only the sectors that have the lsn at the first offset in the log block is divided by the number of sectors per block and is filled up with the sectors into the SW log block.

  • Handling merge operations

    • A switch operation in the SW log block

      similar to the switch operation in BAST.

    • A merge operation in the SW log block

      Two cases which require a merge operation in the SW log block:

      1. When the SW log block encounters a sector that has the lsn at the first offset is divided by the number of sectors per block.
      2. When the SW log block is filled up with the sectors.

      FAST can optimize the merge operations when the SW log block has a particular state.

    • A merge operation in the RW log block

      If no more empty sectors exist in the RW log blocks, FAST needs a merge operation in the RW log block. The victim selection is done in a round-robin fashion. In FAST, each merge operation per logical block proceeds as follows. First, FAST find all sectors for the logical block, copies the most up-to-date version from the RW log vlocks to a free-block, and marks all the found sectors as invalid state. Next, FAST selectively fills each empty sector in the free-block with its corresponding sector in the data block, and exchanges the free-block with the data block. The data block is erased and returned to the free-block list. Finally, the victim logical blocks are erased and returned to the free-block list.

  • An analytical comparison to BAST

    • When nhb(the number of hot data blocks) is equal to nlb(the number of the log blocks)

      BAST and FAST will require nearly the same number of erase operations.

    • When there exists only one hot data block

      All the sectors to be overwritten come from only one logical block.

      BAST writes all the sectors only in a dedicated log block and thus requires a merge operations frequently, even though other log blocks are empty. FAST utilizes every log block and thus accepts the sector writes until it all the log blocks are filled.

    • When nhb is greater than nlb

      BAST should replace a log block whenever a sector without its dedicated log block in the log buffer arrives, and only a small fraction of the victim block is used. FAST caches the sectors to be overwritten in a new log block until it is full.

    • When nhb is between one and nlb

      As the nhb increases from one to nlb, the performance of BAST is approaching that of FAST.

  • O-FAST

    O-FAST can delay the merge operation for a logical data block if more recent versions for all those sectors exist in the nonvictim log blocks.