Team SOD : SFS to FTL

From OpenSSDWiki
Jump to: navigation, search

Please copy this page to make your own final report...


Project Information

  • Project title: Adapt SFS to FTL to reduce erase counts
  • Team Name: SOD (Software On Demand)
  • Team members: Hyobong Son, Jonghan Lee


  • Adapt SFS policies to FTL
    • Establish efficient policies and reduce unneccessary erase counts : Expand Lifespan of SSDs
    • Check the calculation overhead and possiblity of overcoming it by hardware supports

Motivation, Introduction to SFS 

  • Random write is considered harmful to SSDs
    • Performance of random write is considerably low in SSD
    • It can shorten the limited lifespan of SSDs because they incur more NAND block erases per write.


  • New data grouping strategy on Writing 
    • Puts the data blocks with similar update liklihood into the same segment.
    • This minimize the segment cleaning overhead.

 Design and Implementation

Overall architecture

  • Adapt SFS to FTL
    • SFS terminology to FTL's
      • SFS is not a FTL. It has different internal implementation, therefore we change it into FTL like implementation.
      1. Block → Page
        • Basic write unit of SFS is Block. Best way to implement it to FTL is to change it into page
      2. File → Block
        • File is upper level of block in SFS. We implement it to Block. Most important reason is hotness calculation. FTL blocks should credit page hotness which it includes.
      3. Segment → Region
        • It is the highest level of SFS architecture. We suggest upper level of block. It is virtual level which contains number of blocks in it.
              SFS terminologies → FTL terminolgies 
       Block → Page         File → Block         Segment → Region 
  • Calculating Hotness
    • Page Hotness
      • SFS's implementation of page hotness(block hotness in SFS) is
        • hotness = wcount / age, if wcount = 0 get file hotness
      • but we don't have file level, and block hotness is also 0, if page hotness is 0.
      • also wcount = 0 just occur once. so we simply add some hotness to lpn when wcount is 0
    • Block, Segment Hotness
      • Block and Segment contain pages. So Block and Segment hotness is mean of page hotness in it

Main data structures

  • DRAM Metadata
    • DRAM buffers
      • RD_BUF
      • WR_BUF
      • COPY_BUF
      • FTL_BUF
      • HIL_BUF
      • TEMP_BUF
    • Basic meta data for page mapping & bad block list
      • BAD_BLK_MAP
      • PAGE_MAP
    • Additional data for FTL
      • VCOUNT  : valid count
      • PAGE_AGE  : age of the page
      • VBLK_AGE  : age of the vblock
      • VBLK_REGION  : region of the vblock
      • PAGE_WCOUNT  : wcount of the page
      • VBLK_WCOUNT  : wcount of the vblock
      • VBLK_HOTNESS  : hotness of ther vblock


  • SRAM Metadata
    • Meta data : per bank
      • free_blk_cnt
      • gc_vblock
      • global_age
      • Regional data
        • cur_write_vpn
        • lpn_list_of_cur_vblock : per page
        • vcount_of_active_vblock
        • region hotness
        • region wcount
    • FTL_Statiscics
      • gc_cnt
      • gc_live_copy
      • page_wcount

Handling writes

  • Write acts as follows
    • ftl_write() calls write_page()
    • In write_page()
      • Read current page's left & right hole to FTL_BUF
      • Get new vpn to write : assign_new_write_vpn()
      • Perform NAND write
    • In assign_new_write_vpn()
      • Get current lpn's hotness
        • Calculate the age of the lpn
        • Get wcount of the lpn
        • Hotness = wcount / age
      • Find the closest region
        • Recalculate the region hotness
        • Increase the wcount of the region
      • Write to region
        • If bank is full, collect the garbages : garbage_collection() → cost-hotness

Handling Reads

  • Read acts as follows
    • Get Vpn
    • Read from NAND

Garbage Collections

  • Mainly SFS uses Cost-Hotness which considers hotness into victim selection
    • SFS claims Hotness = (1 - Utilization) / (2 * Utilization * Segment Hotness) but We changed Segment into Block so,
    • Hotness = (1 - Utilization) / (2 * Utilization * Block Hotness) is the correct expression.
  • We also used other victim selection policies to check how efficient the Cost-hotness is
  • Follows are candidates for victim selection policy
    • Greedy : Select victim with least valid count
    • Cost-benefit : Select victim block with maximum Hotness
      • Hotness = (1 - Utilization) * Age / (2 * u)

Determining Group Criteria

  • Find natural hotness groups across segments in disk - K-means clustering algorithm


Other information

  • Difficulties in adapting SFS to FTL
    1. Defining SFS things to FTL like form.
      • SFS is not a FTL. It was very big problem. We designed and tested recursivly... and find adaption
      • We mensioned it before in very easy way. Block to page, File to block, Segment to region.. but we tested it case by case
        1. We deleted segment.. used only blocks, in this case we couldn't set the write region for lpn
        2. We tried to use segment only.. but we also encountered problems in garbage collection.. each segment containes to many pages to calculate particular hotness
    2. Calculating age
      • We want to caluate the age by real time. Using real time looks more fassionating! But we encountered many problems.
        1. Idle time is critical to calculating Hotness.
          • We set the time unit to ms.. If we just hold a second... hotness goes down to 1/1000...
          • If we set the time unit to s.. It is not efficient to calculate hotness..
        2. It is hard to control time overflow
          • Rollover time of PRESCALE2 is 14,455s.. It is quite small time for storage.
          • It needs to check rollover and calculate more!

  • Changes from orignal paper
    • There are changes quiet a lot, because SFS is not a FTL.
      1. Block to page, file to block, segment to region.
        • Region is group of blocks which are likely to have similar write frequency.
      2. Initial hotness calculation is changed a little bit.
        • Paper claim page to have file hotness when wcount of page is 0. but our FTL shows when wcount of page is 0, then wcount of block is also 0.
        • Instead we increased little hotness to first write.
        • Hotness of both block and region are mean of pages in it.

  • Not implemented from paper
    • Crash recovery is not implemented.
    • When sudden power off occurs... It looses all the SFS data.



Evaluation methodology

  • FTL is set to have 100 VBLKS_PER_BANK
  • Initial FTL state is formated state.
  • We measured number of garbage collections


Result SFS.png \

  • This Results are comparisons of each victim selection policy.
  • For different three policies and three traces, compared number of garbage collection operation.
  • Garbage collection occurs when insufficient number of free blocks.
Reduction of erase count is not sufficiently satisfiable.

Kmeans change.png Hotness 2.png

  • Separating Hot, Cold data is very good
  • First result saparates area into 3 visible parts.
  • Second Result saparates area into 2 Visible parts.
  • According to data trace it makes various pattern of data sparation
Regional sparation adpats to usage pattern of user. It provides flexible Hot/Cold Separation.

Good to general purpose computer.


  • This FTL is very good at grouping hot/cold data at write time.(conclusion)
    • Area of hot/cold is not static.(K-means algorithm)
    • Adpatable to any kinds of data traces.
  • But it need considerable amount of memory to maintain the additional metadata.(main datastructure)
    • Page - Age / Wcount (DRAM)
    • Block - Age / Wcount / Region (DRAM)
    • Segmnet - Wcount / Hotness (SRAM)


Whos here now:   Members 0   Guests 1   Bots & Crawlers 0
Personal tools