Flash Translation Layer 是泛指實現於快閃記憶體 (Flash memory) 的韌體演算法，其中 Flash 又分為 NOR 和 NAND 兩種，本篇主要針對 NAND 的 FTL (或稱 NFTL) 來討論。NAND Flash (此處假設不討論 SLC 或 MLC) 具有下列物理特性：
1. Write once
寫 過的位址須要抹除 (erase) 後才能再次寫入。
2. Small w/r and large erase
讀寫單位很小 (page) 而抹除單位很大 (block)，通常 block 中有 64 或 128 個 page。
3. block wear
每個 block 有抹除次數限制，一般 SLC 為 100000 次，而 MLC 為 10000 次。
FTL 的實作上還蠻多變化的，但總合而言考慮的好像都是那幾點：
1. Address mapping table 的大小 (即表示耗費 RAM 的多少)
由於寫過的位址須要抹除才可以再次寫入，所以資料從 I/O 端進來後寫入到 Flash 通常會先找空的位址寫入，因此需要將這些 logical 對應到 physical 位址的資訊記錄下來，這就是 mapping table，而記錄的單位越小，需要記錄的資料量就越大，存放 tabe 所需的 RAM 也就越多。
2. Garbage collection (GC) 時需要的 live page copy 數量
當空間不夠時就必須透過抹除來釋放空間，而抹除一個 block 時，裡面可能還包含有效的資料，此時就必須將那些資料搬移到別的地方才能抹除這個 block，這種釋放空間的動作通稱 garbage collection，這是影響 Flash performance 的一個關鍵。
3. wear leveling
每個 block 都有抹除次數的限制，因此要讓每個 block 的抹除次數平均以免某些 block 提前壞掉。
4. recovery scheme (針對 power failure 的應對機制)
像第一點提到的，有關資料讀寫的位址資訊是存在 RAM 的 table 中，因此可能因為突然斷電的關係導致這些資訊遺失，所以要怎樣在斷電時將傷害減少到最小就是 recovery scheme 要討論的。
5. Error Correction Code
Flash memory 是電子式的儲存裝置，所以在資料傳輸的過程可能會發生電子遺失等現象導致資料錯誤，因此 ECC 是必備的，但越精準的 ECC 也會需要使用越多的空間去記錄。
其它還有 responce time 等等也蠻重要的，底下列出幾種常見的 FTL，它們的方法主要都是以第一點和第二點為考量：
Page Level Mapping
在 table 中替每一個 page 都建立對應的 entry，要 update 資料時直接找空的 page 作寫入，同時更改 table 中 logical page 對應到的 physical page 的位址即可。
但這種做法 table 會很大，耗費的 RAM 也就很多，所以也有一些節省 table size 的變型，像是一個 logical page 對應到多個 physical page，或是像後面提到的 superblock 將部分 table 存在 spare area 中等等。
優點：update 時很簡易迅速，也不用擔心空間利用度過低的問題。
缺點：需要較多的 RAM 來存放 mapping table。
要考慮將 hat-cold data 分開以降低 GC 的 copy page 成本。
Block Level Mapping
簡稱 BL，在 mapping table 中僅建立 logical block 對應到 physical block 位址的 entry，每次寫入資料時就必須要一塊新的 block，然後將要寫的 page 之前的所有 page 都由舊的 block 中循序搬移到新的 block 中。
而為了應付循序資料的寫入，大多會搭配 pending 方法，也就是記錄上次最後寫入的位址，則下次寫入若是延續前一次的寫入就可以直接由那個位址繼續寫。
優點：需要較少的 RAM 存放 mapping table。
缺點：每次寫入一個 page 就要更新一整個 block，所需 GC 負擔很大，不利小檔案存取。
BAST (Block Associative Sector Translation)
將 block 分為 data block 和 log block，data block 採用 BL mapping 存放原始位址資料，log block 則採用 page level mapping，存放 update 的資料，而一個 data block 會對應到一個 log block，而 log block 的數量有限，有 update 時才會去要，當可用的 log block 用完或者一個 data block 對應的 log block 寫滿時就會去做 GC，GC 時將 log block 和 data block 的資料合併寫進一個新的 block 用來取代本來的 data block，這種動作稱為 merge。
優點：在 page level mapping 和 block level mapping 間取得平衡。
缺點：當 log block 被不常存取的資料佔用時就會發生頻繁的 GC (這種現象為 block threshiing)。
N-FTL
和 BAST 幾乎一樣，唯一不同在於一個 data block 可以對應無限多個 log block (在可用的 log block 數量限制內都可以一直用)。
FAST (Fully Associative Sector Translation)
和 BAST 不同有兩點：
1. log block 是共用的，所有 update page 都會寫入同一區 log block。
2. 一個 request 存取位址在 block 開頭時表示很大機會是循序存取的檔案，所以它建立一個 sequential block 專門處理這種 request，以增進處理循序資料的效能。
優點：解決 BAST 的缺點，相較於 BAST 更適合用來處理 random access。
缺點：但是每次 GC 做 merge 時可能牽涉很多 data block，必須將那些 block 全部做 erase 和搬移的動作，因此每次 GC 的成本都很高，可能會使得 responce time 過長，且因為只有一個 sequential block 來處理循序資料，所以在循序存取的效能沒有 BAST 好。
N-K (N data block v.s. K log block)
方法與 BAST、FAST 和 NFTL 一樣都是 log block scheme，主要探討了 N 與 K 的關係，其中 N = 1、K = 1 時就是 BAST，N = 1、K = 無窮大時就是 NFTL，而 N = 無窮大、K = 無窮大時則接近 FAST。
此篇論文最後探討出來 data block 與 log block 的最佳解為 N = 4~8、K = 2~4，但這其實也會隨著存取資料的類型不同而改變。
Super-Block
概念是令 N 個 data block 為一個 group，對應 M 個 log block，並且建立三層式的 mapping table 達到 full page level mapping，因此其實已經沒有 data block 和 log block 的概念，也可以說是 N 個 log block 對應 M 個 log block，GC 時也不需要做 merge。
優點：根據 access data 的種類決定 N 和 M 可以達到最好的效率，但要怎樣動態決定 N 和 M 的值就是一個值得思考的地方。
缺點：實作較複雜，且會佔用 spare area 的空間。
LAST (Locality-Aware Sector Translation)
根據兩層 locality 將 request 分類
1. 超過 8-sectors 大小的 request 會採用 BAST 處理
2. 小於 8-sectors 大小的 request 會再根據 temporal locality (access frequency) 分類，依據這樣辨別 hot-cold data，判斷為 hot data 的 request 會集中放到某些特定 block 去處理。
優點：把重點放在辨別 hot-cold data，部分測試的結果效能甚至會比 superblock 還要好。
本文引用至:
http://anemospring.blogspot.tw/2010/06/ftl-scheme-flash-translation-layer.html
1. Write once
寫 過的位址須要抹除 (erase) 後才能再次寫入。
2. Small w/r and large erase
讀寫單位很小 (page) 而抹除單位很大 (block)，通常 block 中有 64 或 128 個 page。
3. block wear
每個 block 有抹除次數限制，一般 SLC 為 100000 次，而 MLC 為 10000 次。
FTL 的實作上還蠻多變化的，但總合而言考慮的好像都是那幾點：
1. Address mapping table 的大小 (即表示耗費 RAM 的多少)
由於寫過的位址須要抹除才可以再次寫入，所以資料從 I/O 端進來後寫入到 Flash 通常會先找空的位址寫入，因此需要將這些 logical 對應到 physical 位址的資訊記錄下來，這就是 mapping table，而記錄的單位越小，需要記錄的資料量就越大，存放 tabe 所需的 RAM 也就越多。
2. Garbage collection (GC) 時需要的 live page copy 數量
當空間不夠時就必須透過抹除來釋放空間，而抹除一個 block 時，裡面可能還包含有效的資料，此時就必須將那些資料搬移到別的地方才能抹除這個 block，這種釋放空間的動作通稱 garbage collection，這是影響 Flash performance 的一個關鍵。
3. wear leveling
每個 block 都有抹除次數的限制，因此要讓每個 block 的抹除次數平均以免某些 block 提前壞掉。
4. recovery scheme (針對 power failure 的應對機制)
像第一點提到的，有關資料讀寫的位址資訊是存在 RAM 的 table 中，因此可能因為突然斷電的關係導致這些資訊遺失，所以要怎樣在斷電時將傷害減少到最小就是 recovery scheme 要討論的。
5. Error Correction Code
Flash memory 是電子式的儲存裝置，所以在資料傳輸的過程可能會發生電子遺失等現象導致資料錯誤，因此 ECC 是必備的，但越精準的 ECC 也會需要使用越多的空間去記錄。
其它還有 responce time 等等也蠻重要的，底下列出幾種常見的 FTL，它們的方法主要都是以第一點和第二點為考量：
Page Level Mapping
在 table 中替每一個 page 都建立對應的 entry，要 update 資料時直接找空的 page 作寫入，同時更改 table 中 logical page 對應到的 physical page 的位址即可。
但這種做法 table 會很大，耗費的 RAM 也就很多，所以也有一些節省 table size 的變型，像是一個 logical page 對應到多個 physical page，或是像後面提到的 superblock 將部分 table 存在 spare area 中等等。
優點：update 時很簡易迅速，也不用擔心空間利用度過低的問題。
缺點：需要較多的 RAM 來存放 mapping table。
要考慮將 hat-cold data 分開以降低 GC 的 copy page 成本。
Block Level Mapping
簡稱 BL，在 mapping table 中僅建立 logical block 對應到 physical block 位址的 entry，每次寫入資料時就必須要一塊新的 block，然後將要寫的 page 之前的所有 page 都由舊的 block 中循序搬移到新的 block 中。
而為了應付循序資料的寫入，大多會搭配 pending 方法，也就是記錄上次最後寫入的位址，則下次寫入若是延續前一次的寫入就可以直接由那個位址繼續寫。
優點：需要較少的 RAM 存放 mapping table。
缺點：每次寫入一個 page 就要更新一整個 block，所需 GC 負擔很大，不利小檔案存取。
BAST (Block Associative Sector Translation)
將 block 分為 data block 和 log block，data block 採用 BL mapping 存放原始位址資料，log block 則採用 page level mapping，存放 update 的資料，而一個 data block 會對應到一個 log block，而 log block 的數量有限，有 update 時才會去要，當可用的 log block 用完或者一個 data block 對應的 log block 寫滿時就會去做 GC，GC 時將 log block 和 data block 的資料合併寫進一個新的 block 用來取代本來的 data block，這種動作稱為 merge。
優點：在 page level mapping 和 block level mapping 間取得平衡。
缺點：當 log block 被不常存取的資料佔用時就會發生頻繁的 GC (這種現象為 block threshiing)。
N-FTL
和 BAST 幾乎一樣，唯一不同在於一個 data block 可以對應無限多個 log block (在可用的 log block 數量限制內都可以一直用)。
FAST (Fully Associative Sector Translation)
和 BAST 不同有兩點：
1. log block 是共用的，所有 update page 都會寫入同一區 log block。
2. 一個 request 存取位址在 block 開頭時表示很大機會是循序存取的檔案，所以它建立一個 sequential block 專門處理這種 request，以增進處理循序資料的效能。
優點：解決 BAST 的缺點，相較於 BAST 更適合用來處理 random access。
缺點：但是每次 GC 做 merge 時可能牽涉很多 data block，必須將那些 block 全部做 erase 和搬移的動作，因此每次 GC 的成本都很高，可能會使得 responce time 過長，且因為只有一個 sequential block 來處理循序資料，所以在循序存取的效能沒有 BAST 好。
N-K (N data block v.s. K log block)
方法與 BAST、FAST 和 NFTL 一樣都是 log block scheme，主要探討了 N 與 K 的關係，其中 N = 1、K = 1 時就是 BAST，N = 1、K = 無窮大時就是 NFTL，而 N = 無窮大、K = 無窮大時則接近 FAST。
此篇論文最後探討出來 data block 與 log block 的最佳解為 N = 4~8、K = 2~4，但這其實也會隨著存取資料的類型不同而改變。
Super-Block
概念是令 N 個 data block 為一個 group，對應 M 個 log block，並且建立三層式的 mapping table 達到 full page level mapping，因此其實已經沒有 data block 和 log block 的概念，也可以說是 N 個 log block 對應 M 個 log block，GC 時也不需要做 merge。
優點：根據 access data 的種類決定 N 和 M 可以達到最好的效率，但要怎樣動態決定 N 和 M 的值就是一個值得思考的地方。
缺點：實作較複雜，且會佔用 spare area 的空間。
LAST (Locality-Aware Sector Translation)
根據兩層 locality 將 request 分類
1. 超過 8-sectors 大小的 request 會採用 BAST 處理
2. 小於 8-sectors 大小的 request 會再根據 temporal locality (access frequency) 分類，依據這樣辨別 hot-cold data，判斷為 hot data 的 request 會集中放到某些特定 block 去處理。
優點：把重點放在辨別 hot-cold data，部分測試的結果效能甚至會比 superblock 還要好。
本文引用至:
http://anemospring.blogspot.tw/2010/06/ftl-scheme-flash-translation-layer.html
全站熱搜
留言列表
