OSTEP Chapter 44

ECE 3600, Fall 2022

Table of Contents

1. Flash-based SSDs

solid-state storage device

Basic Flash Operations: read page (fast), erase block (slow), write page

block must be erased before writing any pages

rewrite page: read block, erase block, update block

2. Flash Translation Layer (FTL)

map logical pages to physical blocks and pages

direct mapped - write logical 0(a),10(b),20(c) --> physical 0,10,20 

  FTL   0:0, 10:10, 20:20
  Block 0          1          2
  Page  0000000000 1111111111 2222222222
        0123456789 0123456789 0123456789
  State vEEEEEEEEE vEEEEEEEEE vEEEEEEEEE
  Data  a          b          c
  Live  +          +          +
To rewrite logical page 20: erase block 2, write page 20

log-structured - write logical 0(a),10(b),20(c) --> physical 0,1,2 

  FTL   0:0, 10:1, 20:2
  Block 0          1          2
  Page  0000000000 1111111111 2222222222
        0123456789 0123456789 0123456789
  State vvvEEEEEEE iiiiiiiiii iiiiiiiiii
  Data  abc
  Live  +++
To rewrite logical page 20(d): remap to free page: 
  FTL   0:0, 10:1, 20:3
  Block 0          1          2
  Page  0000000000 1111111111 2222222222
        0123456789 0123456789 0123456789
  State vvvvEEEEEE iiiiiiiiii iiiiiiiiii
  Data  abcd
  Live  ++ +

3. Garbage Collection

write logical 100(a1),101(a2),2000(b1),2001(b2) --> physical 0,1,2,3

write logical 100(c1),101(c2) --> physical 4,5

remap and erase:

4. Exercises

Exercises from the book using ssd.py: 

$ python ./ssd.py -s 1 -B 3 -l 30 -n 2 -q

FTL   (empty)
Block 0          1          2
Page  0000000000 1111111111 2222222222
      0123456789 0123456789 0123456789
State iiiiiiiiii iiiiiiiiii iiiiiiiiii
Data
Live

cmd   0:: command(??) -> ??

FTL     7:  7
Block 0          1          2
Page  0000000000 1111111111 2222222222
      0123456789 0123456789 0123456789
State EEEEEEEvEE iiiiiiiiii iiiiiiiiii
Data         u
Live         +

cmd   1:: command(??) -> ??

FTL     7:  7  19: 19
Block 0          1          2
Page  0000000000 1111111111 2222222222
      0123456789 0123456789 0123456789
State EEEEEEEvEE EEEEEEEEEv iiiiiiiiii
Data         u            M
Live         +            +

$ python ./ssd.py -s 1 -B 3 -l 30 -n 2 -C

FTL   (empty)
Block 0          1          2
Page  0000000000 1111111111 2222222222
      0123456789 0123456789 0123456789
State iiiiiiiiii iiiiiiiiii iiiiiiiiii
Data
Live

cmd   0:: write(7, u) -> success
cmd   1:: write(19, M) -> success
      
$ python ./ssd.py -s 1 -B 3 -l 30 -n 2 -C -T log

FTL   (empty)
Block 0          1          2
Page  0000000000 1111111111 2222222222
      0123456789 0123456789 0123456789
State iiiiiiiiii iiiiiiiiii iiiiiiiiii
Data
Live

cmd   0:: write(7, u) -> success

FTL     7:  0
Block 0          1          2
Page  0000000000 1111111111 2222222222
      0123456789 0123456789 0123456789
State vEEEEEEEEE iiiiiiiiii iiiiiiiiii
Data  u
Live  +

cmd   1:: write(19, M) -> success

FTL     7:  0  19:  1
Block 0          1          2
Page  0000000000 1111111111 2222222222
      0123456789 0123456789 0123456789
State vvEEEEEEEE iiiiiiiiii iiiiiiiiii
Data  uM
Live  ++

$