原文 http://codecapsule.com/2014/02/12/coding-for-ssds-part-3-pages-blocks-and-the-flash-translation-layer/
在這個部分，我會解釋寫操作在頁和塊級是如何處理的，以及寫入放大和損耗均衡計算的基本概念。此外，我描述了閃存轉換層（ftl）的概念，以及應用了閃存轉換層的兩個技術：邏輯塊位址映射和垃圾回收。更詳細的說，我解釋了在混合邏輯塊映射背景下的寫操作是怎麼實作的。
3. 基本操作
3.1 讀出、寫入、擦除
因為nand閃存單元的組織結構限制，單獨讀寫一個閃存單元是不可能的。存儲單元被組織起來并有着十分特别的屬性。要知道這些屬性對于為固态硬碟優化資料結構的過程和了解其行為來說是很重要的。我 在下方描述了關于讀寫擦除操作的ssd的基本屬性
讀是以頁大小對齊的
一次讀取少于一頁的内容是不可能的。作業系統當然可以隻請求一位元組，但是ssd會通路整個頁，強制讀取遠超所需的資料。
寫是以頁大小對齊的
将資料寫入ssd的時候，寫入的增量也是頁大小。是以即使一個寫入操作隻影響到一個位元組，無論如何整個頁都會寫入。寫入比所需更多的資料的行為被稱為寫入放大，其概念在3.3節。另外，向某頁寫入的行為有時候被稱為“編置（to program）”一頁，是以在大多數關于ssd的出版物和文章中“write 寫”和“program編置”是可以互相替換的
頁不能被複寫
nand閃存頁隻有在其“空閑”着的時候才能寫入。當資料改變後，這頁的内容被拷貝到一個内部寄存器，此時資料更新而新版本的資料存儲在一個“空閑”的頁中，這被稱為“讀-改-寫”操作。資料并非就地更新，因為“空閑”頁與原來存儲資料的頁不是同一個頁。一旦資料被硬碟儲存，原先的頁被标記為“stale（意為 腐敗的 不新鮮的）”，直到其被擦除。
擦除以塊對齊
頁不能被複寫，而一旦其成為stale，讓其重新空閑下來的唯一方法是擦除他們。但是對單個頁進行擦除是不可能的，隻能一次擦除整個塊。在使用者看來，通路資料的時候隻有讀和寫指令。擦除指令則是當ssd控制器需要回收stale頁來擷取空閑空間的時候，由其垃圾回收程序觸發。
3.2 寫入的例子
讓我們用個例子來理清3.1節的這些概念。下邊的圖4是向ssd寫入的一個例子。隻顯示了兩個塊，每個塊有4個頁。顯然這是一個為了簡化我在這使用的例子而精簡的nand閃存封裝示意。圖中的每一步裡，圖右側的圓點解釋了發生的事情
圖4：向固态硬碟中寫資料
3.3 寫入放大
因為寫入是按頁大小對齊的，任何沒有對齊一個或者多個頁大小的寫操作都會寫入大于所需的資料，這是寫入放大的概念。寫一個位元組最終導緻一整頁都要寫入，而一頁的大小在某些型号的ssd中可能達到16kb，這是相當沒有效率的。
而這不是唯一的問題。除了寫入過多的資料外，這些額外的寫入也會觸發更多不必要的内部操作。實際上，用未對齊的方法寫入資料會導緻在更改和寫回硬碟之前需要頁讀到緩存，這比直接寫入硬碟要慢。這個操作被稱為讀-改-寫，且應該盡可能的避免。
絕不進行少于一頁的寫入
避免寫入小于nand閃存頁大小的資料塊來最小化寫入放大和讀-改-寫操作。現在一頁的大小最大的是16kb，是以這個值應作為預設值使用。閃存頁大小的值基于ssd型号并且在未來ssd發展中可能會增加。
對齊寫入
以頁大小對齊寫入，并寫入大小為數個頁大小的資料塊。
緩存化小寫入
為了最大化吞吐量，盡可能的将小資料寫入ram緩存中，當緩存滿了之後執行一個大的寫入來合并所有的小寫入。
3.4 損耗均衡
如我們在1.1節讨論的那樣，nand閃存單元因其有p/e循環限制導緻其有生命限制。想象一下我們有一個ssd，資料總是在同一個塊上寫入。這個塊将很快達到其p/e循環限制、耗盡。而ssd控制器井标記其為不可用。這樣硬碟的容量将減小。想象一下買了一個500gb的硬碟，過了幾年還剩250g，這會非常惱火。
是以，ssd控制器的一個主要目标是實作損耗均衡，即是将p/e循環在塊間盡可能的平均配置設定。理想上，所有的塊會在同一時間達到p/e循環上限并耗盡。
為了達到最好的全局損耗均衡，ssd控制器需要明智的選擇要寫入的塊，且可能需要在數個塊之間移動，其内部的程序會導緻寫入放大的增加。是以，塊的管理是在最大化損耗均衡和最小話寫入放大之間的權衡。
制造商想出各種各樣的功能來實作損耗均衡，例如下一節要講的垃圾回收。
損耗均衡
因為nand閃存單元會耗盡，ftl的一個主要目标是盡可能平均的将工作配置設定給各個閃存單元，這樣使得各個塊将會在同一時間達到他們的p/e循環限制而耗盡。
4.閃存轉換層(ftl)
4.1 ftl存在的必要性
使用ssd如此容易的主要因素是其使用和hdd相同的主機接口。盡管一組邏輯塊位址（lba）的出現使其感覺像hdd的扇區一樣可被複寫，但其并非完全符合閃存的工作方式。是以需要一個額外的元件來隐藏nand閃存的内部特征，并隻向主機暴露一組lba。這個元件稱為閃存轉換層（ftl），位于ssd控制器中。ftl很關鍵，并有兩個主要的作用，邏輯塊尋址和垃圾回收。
4.2邏輯塊映射
邏輯塊映射将來自主機空間的邏輯塊位址（lba）轉換為實體nand閃存空間的實體塊位址（pba）。為了通路速度，這個映射表儲存在ssd的ram中，并儲存在閃存中以防電源故障。當ssd啟動後，這個表從閃存中讀出并在ssd的ram中重建。
一個比較簡單的方法是使用頁級映射來将主機的所有邏輯頁映射為實體頁。這個映射方法提供了很大的靈活性，然而主要的缺點是映射表需要大量的記憶體，這會顯著地增加生産成本。一個解決方案是使用塊級映射不再對頁，而是對塊進行映射。假設一個ssd硬碟每個塊有256個頁。這表示塊級映射需要的記憶體是頁級映射的256分之一，這是記憶體使用的巨大優化。然而這個映射仍然需要儲存在硬碟上以防掉電。同時，以防大量小更新的工作負載，無論頁是否是滿的，全部閃存塊都會寫入。這會增加寫入放大并使得塊級映射普遍低效。
頁級映射和塊級映射的折中其實是在性能和空間之間折中的一個表現。一些研究者試着在兩個方面都能夠最佳化，得到了稱為“hybrid（混合）”的方法。最普遍的是日志塊映射，其使用了一種比較像日志結構檔案系統的方法。輸入的寫操作按順序寫入日志塊中。當一個日志塊滿了之後，将其和與其在相同邏輯塊編号（lbn）的資料塊合并到空塊中。隻需要維護少量的日志塊，且允許以頁粒度維護。而塊級映射是以塊粒度維護的。
下邊的圖5是對混合日志塊ftl的一個簡單的陳述，每個塊有4個頁。ftl處理4個寫操作，都是頁大小尺寸的寫入。邏輯頁編号5和9都被映射到lbn（邏輯塊編号）=1，而lbn=1關聯到實體塊#1000。最初，在邏輯塊映射表中，lbn=1的所有實體頁offset都是null，而日志塊#1000同樣是完全空的。
第一個寫入将b’寫到lpn=5，這被日志塊映射表解釋到lbn=1，即為關聯到pbn=1000（日志塊#1000）。是以頁b’寫到塊#1000的0号頁中。映射用的中繼資料需要更新，為此，邏輯offset 1（随便舉的例子）對應的實體offset從null改為0。
寫入操作繼續而映射中繼資料随之更新，當日志塊#1000完全填滿，将其和對應為相同的邏輯塊的資料塊（本例中是#3000）合并。這個資料可以從資料塊映射表中讀取，此表将邏輯塊映射為實體塊。合并操作的結果資料被寫到新的空塊中，本例中為#9000。當這個工作做完了，塊#1000和#3000可以被擦除成為空塊，而塊#9000成為一個資料塊。資料塊映射表中lbn=1的中繼資料則從一開始的#3000改為新的資料塊#9000.
一個值得注意的很重要的事情是，四個寫操作隻集中在兩個lpn中。邏輯塊方法在合并的過程中隐藏了b’和d’操作，直接使用更加新的b”和d”版本，使其能夠更好的降低寫入放大。最後，如果讀指令請求一個最新更新但還沒合并到資料塊中的頁，這個頁将會在日志塊中讀取，否者将會在資料塊中找到。這就是如圖5中所示，讀操作即需要讀取日志塊映射表又需要讀取資料塊映射表的原因。
圖5：混合日志塊ftl
日志塊ftl可以進行優化，其最值得注意的是切換合并，有時候也叫做“交換合并”。假設邏輯塊中所有位址都立馬寫滿了，這表示這些位址的所有新資料都将寫到一個像樣的日志塊中。既然這個日志塊包含的資料是一整個邏輯塊的資料，那麼将其和資料塊合并到新的空塊中是沒有意義的，因為儲存合并結果的空塊中的資料就是日志塊中的資料。隻更新資料塊映射表中的中繼資料并将資料塊映射表中的資料塊切換為日志塊将會更快，這就是切換合并。
很多論文都讨論日志塊映射方案，這些論文導緻了一系列的改進，例如fast（fully associative sector translation 完全關聯扇區轉換）、superblock mapping（超塊映射）、以及flexible group mapping（靈活組映射）。同樣還有其他的映射方案，例如mitsubishi（三菱）算法和ssr。下面兩篇論文是學習更多關于ftl和映射方案的很好的開始點
“a survey of flash translation layer“, chung et al., 2009
“a reconfigurable ftl (flash translation layer) architecture for nand flash-based applications“, park et al., 2008
閃存轉換層
閃存轉換層是ssd控制器的一個元件，它将來自主機的邏輯塊位址（lba）映射為硬碟上的實體塊位址（pba）。大部分最新的硬碟使用了一種叫做“混合日志塊映射”的技術或者其衍生技術，其工作方式比較像日志結構檔案系統。這種技術可以将随機寫入當做序列寫入處理。
4.3 關于行業狀态的注記.
在2014年2月2日，wikipedia 上列出了70個ssd的生産商，有意義的是，隻有11個主要的生産商。在這11個主要生産商之中，隻有4個是“captive（自給自足的）”，即僅對它們自己的産品使用自己的主要（譬如intel和三星）；而其他的7個是“independent（獨立的）”，即他們把自己的主要賣給其他的硬碟生産商。這些數字表示，這7個公司生産固态硬碟市場上90%的主要。
我沒有這90%中，關于哪個主要生産商賣給哪個硬碟生産商的資料嗎，但是根據帕雷托法則（二八定律或80/20法則——譯注），我賭隻有兩三家主要制造商分享了大部分的蛋糕。直接結論是，來自非自給自足廠家的ssd，因其本質上使用相同的主要或至少其主要使用相同的全局設計和底層思想，其行為會及其相似。
映射方案作為主要的一部分是ssd十分重要的元件，因為其往往完全定義了硬碟的表現。這就解釋了為什麼在有如此多競争的産業中，ssd主要生産商不分享其ftl實作的細節。是以，即使有大量的公共可用的關于ftl算法的研究，但仍然不清楚主要生産商使用了多少研究，以及某個牌子和型号具體實作了什麼。
這篇文章的作者聲稱通過分析工作負載，他們可以對硬碟的映射政策進行反向工程。除非晶片中的二進制代碼本身被反向工程，我自己還是不太認同這種方法。因為沒有辦法完全确認某個硬碟中映射政策真正做了什麼。并且預測一個特定的工作負載下映射的行為更難。
因為有很大量的不同映射政策，而對市場上所有可用固件進行反向工程所花費的時間的量值得考慮。然後，即使獲得了所有可能的映射政策的源代碼，你能拿來幹啥？新産品的系統需求經常導緻全面改進，使用未标明和内部易變的硬體元件。是以，隻為一個映射政策進行優化是不值當的，因為這個優化的方案可能在其他所有映射政策表現很差。某人想隻對一種映射政策進行優化的唯一原因是他在為已經保證使用一緻硬體的嵌入式系統進行開發。
綜上所述，我得說知道某一個ssd具體使用的是哪一個映射政策并不重要。唯一重要的事情是知道映射政策是lba和pba之間的轉換層，而其很像混合日志塊或其衍生算法的實作。是以，寫入大小至少是nand閃存塊大小的資料片将會更加效率，因為對于ftl來說，更新映射及其中繼資料的開支是最小化的。
4.4 垃圾回收
如我在4.1和4.2節中所說，頁不能被複寫。如果頁中的資料必須更新，新版本必須寫到空頁中，而儲存之前版本資料的頁被标記為stale。當塊被stale頁充滿後，其需要在能夠再寫入之前進行擦除。
垃圾回收
ssd控制器中的垃圾回收程序確定“stale”的頁被擦除并變為“free”狀态，使得進來的寫入指令可以通路這個頁。
如第一節中所說，擦除指令需要1500-3500 μs，寫入指令需要250-1500 μs。因為擦除比寫入需要更高的延遲，額外的擦除步驟導緻一個延遲使得寫入更慢。是以，一些控制器實作了背景垃圾回收程序，或者被稱為閑置垃圾回收，其充分利用空閑時間并經常在背景運作以回收stale頁并確定将來的前台操作具有不足夠的空頁來實作最高性能。其他的實作使用并行垃圾回收方法，其在來自主機的寫入操作的同時，以并行方式進行垃圾回收操作。
遇到寫入工作負載重到垃圾回收需要在主機來了指令之後實時運作的情況并非罕見。在這種情況下，本應運作在背景的垃圾回收程序可能會幹預到前台指令。trim指令和預留白間是減少這種影響的很好的方法，具體細節将在6.1和6.2節介紹。
背景操作可能影響前台操作
諸如垃圾回收背景操作可能會對來自主機的前台操作造成負面影響，尤其是在持續的小随機寫入的工作負載下。
塊需要移動的一個不太重要的原因是read disturb（讀取擾亂）。讀取可能改變臨近單元的狀态，是以需要再一定數量的讀取之後移動塊資料。
資料改變率是一個很重要的影響因素。有些資料很少變化，稱為冷資料或者靜态資料，而其他一些資料更新的很頻繁，稱為熱資料或者動态資料。如果一個頁一部分儲存冷資料，另一部分儲存熱資料，這樣冷資料會随着熱資料一起在垃圾回收以損耗均衡的過程中拷貝，冷資料的存在增加了寫入放大。這可以通過将冷資料從熱資料之中分離出來，存儲到另外的頁中來避免。缺點是這樣會使儲存冷資料的頁更少擦除，是以必須将儲存冷資料和熱資料的塊經常交換以確定損耗均衡。
因為資料的熱度是在應用級确定的，ftl沒法知道一個頁中有多少冷資料和熱資料。改進ssd性能的一個辦法是盡可能将冷熱資料分到不同的頁中，使垃圾回收的工作更簡單。
分開冷熱資料
熱資料是經常改變的資料，而冷資料是不經常改變的資料。如果一些熱資料和冷資料一起儲存到同一個頁中，冷資料會随着熱資料的讀-改-寫操作一起複制很多次，并在為了損耗均衡進行垃圾回收過程中一起移動。盡可能的将冷熱資料分到不同的頁中是垃圾回收的工作更簡單
緩存熱資料
極其熱的資料應該盡可能多的緩存，并盡可能的少的寫入到硬碟中。
以較大的量廢除舊資料
當一些資料不再需要或者需要删除的時候，最好等其它的資料一起，在一個操作中廢除一大批資料。這會使垃圾回收程序一次處理更大的區域而最小化内部碎片。