SSD數據結構與算法綜述

史高峰，李小勇

0 引言

SSD是一種基于閃存的電可擦除可編程的新型存儲器件，本文主要介紹SSD閃存的數據結構和算法以及SSD閃存在分層存儲中的應用。

閃存的讀、寫或擦除操作與易失的 RAM 和磁盤有很大的不同。閃存的每個單元只能擦寫有限次（10，000到1，000，000次），超過這個最大次數后，閃存就變得不可靠了。

閃存種類主要有兩種，NOR和NAND，這兩種有很大的區別。寫操作都是把“1”置為“0”，而擦除操作需要把一整個擦除單元的所有位都置為“1”。一個固定設備的擦除大小是固定的，從幾KB到上百KB。NOR閃存的每個位（bit）都能被處理機直接訪問并擦除，但是NOR的擦除時間比較長，而NAND閃存，擦除時間比較短，但是處理機不能訪問到每個位（bit），訪問的最小單位是頁（page），一個擦除單元由很多頁構成，典型的頁大小為 512字節（byte）。一個擦除周期中的一個頁只能被修改幾次，因為修改幾次后，頁中的數據就不再可靠了。

因為這些特殊性，基于磁盤的一些存儲技術就不太適合閃存了。隨著閃存的廣泛應用，在20世紀90年代后，基于閃存的存儲技術不斷發展。這些技術中，有一小部分是針對閃存的發明設計，而大部分發明是源自其他的存儲技術。本文就是分析比較了閃存的各種數據結構和算法。

1 塊映射技術

將閃存塊當做磁盤塊使用，會產生兩個問題：

第一，一些塊的修改次數遠遠大于其他塊，對于磁盤塊不會有任何問題，但是閃存中的這種塊就會由于擦除太多而達到擦除上限，這種問題可以通過損耗均衡技術解決。

第二，不合理的映射會將一個很小的塊映射到閃存的一個擦除單元，例如，文件系統將一個4KB的數據塊映射到閃存中一個128KB的擦除單元中，那么修改這個數據塊就需要將這128KB復制到內存，在內存中修改這4KB數據，擦除閃存中相應的128KB的擦出單元，然后，將這4KB數據寫回閃存，如果中間掉電，可能會損失128KB數據，而磁盤中只會損失4KB數據。這個問題也可以通過損耗平衡技術解決。

1.1 塊映射的思想

所有損耗平衡思想都是基于一個映射關系，即一個虛擬塊號映射到閃存中的一個物理塊號。閃存中，當一個虛擬塊需要被重寫，新數據不會寫到之前映射到的那個物理塊，而是寫入一個新的物理塊中，并修改邏輯塊號和物理塊號的映射表。

閃存中的一個物理塊一般是一個擦除單元中的固定大小的一部分，在NAND閃存中，一般是一個頁，而在NOR閃存中，有可能還會是變長大小。

這種映射有幾個目標：

首先，頻繁修改的塊會保存到不同的物理塊中，便于損耗平衡。

再次，這種映射允許寫擦除單元中的一個頁，而不是立即擦除掉整個擦除單元再進行寫。

第三，寫操作保持原子性，如果寫的過程中斷電，可以回滾到之前的狀態。

寫操作的原子性主要通過以下技術實現，每個物理塊有一個小的頭部，這個頭部可以在物理塊中，也可以保存在其他擦除單元中。當寫一個塊時，首先找到一個可用的物理塊，這種塊和它的頭部中的所有位都為“1”，然后頭部中的“空閑/占用”位被置為“0”，表明這個塊已經被占用，邏輯塊號寫入這個物理塊的頭部的相應位置，并且數據寫入相應的物理塊中，然后，頭部中的“無效/有效”位被置“0”，表明這個塊可以讀，最后，之前舊的版本的物理塊的頭部中的“有效/過時”位被置“0”，表明這個塊不再是虛擬塊的最新版本。

如果在寫操作中電源丟失，可能會出現兩種狀況，如果斷電發生在新寫的物理塊被標記為有效之前，則新寫的塊被置為無效，并且“有效/過時”位被置“0”，標記新塊可以被回收；如果斷電發生在新寫的物理塊被標記為有效之后但是舊的物理塊標記為過時之前，這兩個物理塊都是合法的，系統將隨意選擇一個標記為過時，如果最近更新的版本更重要，通過一個兩位的版本號標示出哪個是最新的，具體是1比0新，2比1新，3比2新，0比3新【Aleph One 2002】。

1.2 塊映射的數據結構

系統如何通過邏輯塊找到相應的物理塊呢？一般情況下，通過兩種數據結構，一種是正向映射，另一種是反向映射。正向映射是將邏輯塊號和物理塊號填入一張表中，系統可以通過邏輯塊號查詢到相應的物理塊號，反向映射是將每個物理塊的塊頭中保存邏輯塊號，如果系統需要通過邏輯塊找到相應的物理塊，就需要遍歷物理塊直到找到相應的邏輯塊為止。正向映射可能不是簡單的隊列實現而是一些更復雜的數據結構，以便于更高的查詢效率。而反向映射必須是隊列，隊列中的物理位置上可以不是連續的。

反向映射保存在閃存中，當一個邏輯塊寫入物理塊時，邏輯塊號記錄到相應的物理塊的頭部中，并且邏輯塊號伴隨物理塊的擦除而擦除。反向映射的主要作用是在設備初始化時重構正向映射。

正向映射保存在閃存控制器的內存中，是易失的，正向映射的作用是支持快速查詢邏輯塊的相應物理塊，當邏輯塊和相應的物理塊的映射關系更新時，正向映射也應該相應的更新，但是閃存不支持這種就地更新正向映射，其過程，如圖1所示：

正向映射并不是必須的，系統可以通過線性查詢反向映射找到邏輯塊號對應的物理塊，這樣的查詢速度慢，但是節省閃存控制器中的內存空間。如果把一個邏輯塊僅僅映射到一個集合的物理塊中，這樣可以提高查詢速度【Assar et al.1995a; 1995b】。這種技術類似于緩存中的組相聯映射，減少了內存占用，提高了查詢速度，但是減少了映射的靈活度，可能會導致損耗平衡問題。

閃存轉換層是一種將正向映射保存在閃存內存中，減少閃存中的映射更新。這個技術是Ban發明的【Ban 1995】，并且在后來被PCMCIA標準采用。

Ban后來發明了基于NAND閃存的閃存轉換層NFTL【Ban 1999】，主要思想是，將一個邏輯塊號映射成一個邏輯擦除單元和擦除單元中的塊號，每個邏輯擦除單元對應一個物理擦除單元鏈，比如，查找邏輯擦除單元7的第5塊，系統就順著這個鏈，找到相應的物理塊，將其返回，這個有效塊的之前的擦除單元中的第五塊都無效，之后的擦除單元中的塊仍舊可用（所有位全是“1”）。如果修改這個第5塊，則找出鏈中的下一個擦除單元的第5塊，將數據更新到新塊中，如果鏈中沒有可用的第5塊，則尋找新的物理擦除單元加入鏈中。當回收空間時，系統會將所有有效數據塊寫入鏈的最后一個擦除單元中，最后一個擦除單元作為新的鏈頭，所有舊鏈中的其它擦除單元都被擦除，鏈的長度一般是 1或更長。

邏輯擦除單元與物理擦除單元鏈的映射關系，保存在一個物理擦除單元頭部，在閃存設備初始化時，在閃存控制器的內存中構造相應的正向映射，因為是擦除單元之間的映射，而不是塊之間的映射，所以這個映射占用的空間很少。

也可以將變長的邏輯塊映射到閃存中，Wells at al.發明了這項技術【Wells at al.】，并且微軟閃存文件系統【Torelli 1995】也采用了相似的技術，主要思想是，在一個擦除單元內，將變長的數據塊從低地址存放，定長的頭部信息從高地址存放。每個頭指向相應的變長的塊，微軟閃存文件系統就是這樣的系統。

Smith和Garvin發明了一個類似的系統，但是粒度更粗，他們將每個擦除單元分為3部分：頭部、分配映射表和多個固定大小的塊。系統將一個邏輯塊分配到多個連續的物理塊中，這些連續分配的物理塊稱作extent，并在分配映射表中有一個表項，這個表項中的信息包括 extent的地址信息、長度和邏輯塊號等。當extent中的塊需要修改時，一個extent就被分裂成兩個或3個extent，將原來的映射表中的extent表項標記無效，并添加新的extent表項。

2 擦除單元回收

隨著時間的推移，閃存設備上的過時塊越來越多而空閑塊越來越少，為了空間利用，過時塊必須被回收，回收塊的唯一方式就是擦除整個擦除單元。回收總是針對整個擦除單元來說的。

回收發生在系統空閑時或當空閑塊數量低于一個預先設定的閾值時。

系統回收空間有幾個階段：

首先，一個或多個擦除單元被選為將要回收的單元。

然后，將這些擦除單元中的有效數據塊復制到設備中別的空閑塊中。

再次，修改遷移數據的邏輯塊和物理塊的映射關系。

最后，回收的擦除單元被擦除，并將這些回收的塊加入到空閑塊池中。

回收時需要將回收單元中的有效數據塊復制出來，所以系統中一般都會預留一部分空閑擦除單元來滿足擦除時的這種要求。

回收機制有兩個主要策略：選擇哪些單元回收？將這些單元中的有效數據塊遷移到哪里？這兩個策略又依賴于一個策略，就是在塊更新時，如何分配物理塊給新的數據塊？這3個相關的策略以3種方式影響系統。它們影響回收進程的效率（以過時塊占回收單元的比例為衡量），它們影響損耗平衡，它們影響映射關系的數據結構的相應更新。

損耗平衡的目標和回收效率往往是相悖的，例如一個擦除單元中僅僅包含靜態數據（很長時間不被更新的數據），從回收效率的角度來說，不會選擇回收這樣的單元，因為這樣的單元不能釋放更多有效的多余空間，但是，這樣的回收有利于整個設備的損耗平衡。假設我們知道一些數據屬于靜態數據，即一段時間內不會修改的數據，則我們將這些數據遷移到已經擦除次數較多的塊上，這樣我們就可以減少這些單元的勞損。

很顯然，回收時機往往發生在設備中沒有足夠空閑空間的時候，這種策略稱作及時回收，但是，有些系統的回收時機發生在系統空閑時，這種策略稱作后臺回收。后臺自動回收需要整個系統的支持，有的系統可以識別空閑時期，有的系統則不能。閃存的特性也很重要，當擦除速度很慢時，就應該避免及時回收否則影響數據塊更新的時間，當擦除速度很快時，這種影響就不是那么明顯。同樣，當擦除允許被中斷并能從中斷中恢復，那么后臺回收就不太影響數據塊的更新，而當擦除不允許中斷時，后臺回收就會很影響數據塊的更新。但是，所有這些問題都與算法和數據結構有互相交錯的影響。

2.1 損耗平衡為中心的回收和測量損耗的技術

這里描述的回收技術的主要設計是以減少損耗為中心的，這些技術在系統中用獨立的有效回收機制和損耗平衡策略。系統中在大部分時間使用效率為中心的回收策略，但在一些時候轉換為損耗平衡為中心的回收策略。有些時候不均衡的損耗引發轉換，有些時候周期性的發生轉換。很多技術用于測量損耗情況，接下來，介紹損耗測量技術。

Lofgren et al.發明了一種由回收擦除單元觸發的損耗平衡技術【Lofgren et al.2000; 2003】。在這個技術中，每個擦除單元頭部保存一個擦除計數。首先，系統中預留一個備用的擦除單元，當最勞損的擦除單元被回收時，計算最勞損的擦除單元與最不勞損的擦除單元的擦出計數的差，如果這個差超過一個閾值，比如15,000，則負載平衡回收策略被采用，將最不勞損的單元中的有效塊數據遷移到備用擦除單元中，擦除這個最不勞損單元，然后將最勞損單元中的有效數據塊遷移的剛剛擦除的那個最不勞損單元中，再擦除那個最勞損單元，并將其置為備用單元。這個技術試圖去識別最勞損單元和靜態數據塊，將靜態數據塊遷移到最勞損單元。而在下一個周期的損耗平衡中，最勞損塊將保存最不勞損塊中的數據。據推測，最不勞損單元中的數據相對靜態，將這些數據塊保存到最勞損單元中來平衡勞損單元的損耗，同時，將靜態數據從最不勞損單元中遷移，提高了整個設備中的每個單元的損耗更加均勻。

很顯然，這種技術依賴于擦除單元頭部的擦除計數，如果一個擦除操作正在進行，新的擦除計數沒有寫入擦除單元頭部時掉電，這個單元的擦除計數就會丟失，這種危險相當嚴重，尤其是當擦除速度比較慢時。

一種解決這個問題的方法是將擦除單元的計數保存到別的擦除單元中，比如單元i的計數保存到單元j中（ ）。Marshall和Manning就發明了這樣一種技術【Marshall and Manning 1998】。系統中每個擦除單元保存頭部保存一個擦除計數，在回收單元i之前，將i的計數復制到一個任意塊j的一個特殊區域中（ ），那么在回收中丟失單元i的計數，就直接可以從單元j中恢復。

Assar et al.發明了一種更簡單但是稍微低效的方法【Assar et al.1996】，將一個擦除單元的邊界為8的8位二進制數，保存在別的擦除單元中，比如單元i的擦除計數保存在單元j中（ ），當單元i被擦除時，就將單元j中的一位二進制位擦除（“1”置為“0”），這樣，單元i可以被擦除多次，擦除計數會相應地更新。但是，因為計數的邊界是8位，當擦除次數多于8次后，這個擦除計數就不準確了。這種系統中，需要周期性的損耗平衡機制來會回滾所有的擦除計數。

Jou和Jeppesen也發明了一種的擦除計數技術【Jou and Jeppesen 1996】。他們系統中使用了稱為“寫前擦除”策略：將回收的擦除單元的有效內容復制到別的單元中，但是這個單元不會被立即擦除，而是將其標記為候選擦除單元，并加入到閃存內存中的候選擦除單元的優先級隊列中，以損耗計數來排序，損耗計數最小的單元先被擦除為可用單元。這種技術在一定程度上平衡了損耗，因為延遲了一些損耗嚴重的單元被擦除，損耗的均衡與否取決于優先級隊列中候選擦除單元的多少：如果候選擦除隊列比較短，損耗嚴重的塊就可能不會被延遲很久被擦除。

Han發明了這個問題的另外一種解決方法【Han 2000】。依賴擦除延遲來預估損耗情況，一些閃存設備中，隨著損耗的增加擦除延遲也相應增加，Han的技術通過擦除所用時間來判斷損耗情況，并將這些損耗情況排序，這避免了保存擦除計數。損耗情況排序可用于分配策略等，但是系統僅僅預估一段時間的擦除單元的損耗狀況，對于那些一段時間內僅有少數單元被擦除的情況，就沒有辦法很好地使整個設備的損耗平衡。

另一種損耗平衡的方法依賴于隨機性而不是預估塊的損耗情況。Woodhouse提出了一個簡單的隨機的損耗平衡技術【Woodhouse 2001】。每100次回收，系統會隨機選擇一個僅有有效數據的單元回收，這樣就會將靜態數據從所在的損耗小的單元遷移到損耗大的單元中，如果這個技術應用在一個傾向于回收效率而不是損耗平衡的系統中的話，極端的損耗不平衡仍舊存在，如果回收單元時僅僅根據其中的無效塊的數量，那么一些僅有少量無效塊的單元可能永遠得不到回收。

大約在同一時間，Ban發明了一個更加健壯的技術【Ban 2004】。他的這個技術依賴于一個備用單元。每一個確定的回收次數中，一個擦除單元被隨機選中，將選中的擦除單元中的有效數據塊復制到備用單元中，選中的擦除單元擦除后就標記為新的備用單元，這種損耗平衡事件的觸發可以是確定的，比如每1000次擦除引發一次，或者隨機的。隨機的觸發損耗平衡可能會僅僅幾次擦除就產生一次。這個技術的目的是使閃存中的生命周期中的每個擦除單元有公平的互換，大量的互換可以減少一個擦除單元長時間地存儲靜態數據。另外，這個技術中的損耗平衡開銷是可預見的并均勻的。

這個技術的思想在更早的軟件中已經使用，M-Sytems公司的TrueFFS，使用了結合擦除次數和隨機性的損耗平衡技術，M-Sytems公司的描述中說，隨機性的使用消除了保護每個擦除單元的確切擦除計數的必要。

2.2 結合有效回收和損耗平衡技術

Kawaguchi，Nishioka和Motoda發明了一個這樣的技術【Kawaguchi et al.1995】。他們實現了一個閃存設備的塊設備驅動程序，這個驅動程序被用于日志結構文件系統。這個文件系統操作更像一個塊映射機制：它負責分配塊并回收擦除單元。Kawaguchi et al.描述了兩種回收策略。第一個策略是選擇下一個回收單元的原則是計算回收好處與回收代價的比率，一個單元的回收好處是這個單元中無效塊的個數，回收代價是將這個單元中有效塊復制到別的單元中的代價。一個單元距上次修改的時間也是其中的參數，即時間越長單元中的有效數據就越像靜態數據，這個時間越長就越容易被回收。而這個技術避免了回收好處與回收代價比率增長時回收，因為這時擦除單元距上次修改的時間比較短。這個技術沒有專門為損耗平衡設計，但是也達到了損耗平衡的結果，因為即使少量無效塊的擦除單元，隨著時間的推移，終將被回收。

Kawaguchi et al.發現這個策略在某些情況下仍舊低效率，于是提出了另外一個策略，他們提出將數據分成兩種單元，一種單元中存放“冷”數據，即在回收擦除單元中的不經常修改的數據，另一種單元存放“熱”數據，通常不在回收過程中動態寫入的數據。這種方式可以提高回收效率，因為動態的數據存放在一起，回收的時候可以將這個單元回收，而只遷移少量有效數據。存放靜態數據的單元不需要回收，因為它上面沒有無效數據塊。顯然，這樣的靜態數據單元很長時間不會得到回收，這會導致損耗平衡問題，除非采用別的損耗平衡策略。

Wu和Zwaenepoel描述了一個更縝密的策略【Wu and Zwaenepoel】。系統將擦除單元分為固定大小的區域，假設小號的區域存儲“熱”邏輯塊，大號的區域存儲“冷”邏輯塊，每個區域都有一個活躍的擦除單元存放最近更新的數據塊，當一個虛擬塊被更新，新的數據就寫入當前區域的活躍單元的一個相應的物理塊中，當一個區域中的那個活躍單元被寫滿，系統選擇這個區域中有效塊最少的單元回收，假如擦除單元分為前部和后部，在回收時，這個單元中的有效數據被復制到一個空單元的前部，這樣，不經常更新的塊就被保存到擦除單元的前部，即“冷”塊，而新更新的塊就保存到擦除單元的后部，也就是相對“熱”塊，Wu和Zwaenepoel就是這樣區分冷熱塊的，其冷熱區如圖2所示：

對于每個區域，系統試圖去獲得均衡的回收頻率，然而，熱區域應該比冷區域有更少的塊，因為熱數據無效的速度更快。在每次回收時，系統會將當前區域的回收頻率與區域的平均頻率作比較。如果，當前區域的回收頻率比平均頻率高，就將區域中的一些塊遷移到臨近的區域中，擦除單元中的前部，即冷塊遷移到冷區域中，擦除單元的后部，即熱塊被遷移到熱區域中。

Wu和Zwaenepoel實現了簡單形式的損耗平衡，當最勞損的單元比最不勞損的單元擦除計數高100時，交換這兩個單元的數據。當最不勞損的擦除單元保存的是靜態數據時，這是很有效的，這種交換會使勞損的單元休息下來。

Wells發明了一種依賴于有效回收和損耗平衡的回收策略【Well 1994】。系統選擇下一個回收單元是基于一個分數，單元j的分數的定義如下：

其中，無效塊(j)是指擦除單元 j中的無效數據塊的總數，擦除數(j)是指擦除單元j的擦除次數，最大分數的塊將是下一個回收的塊，無效塊(j)和擦除數(j)可以從每個擦除單元中獲得，0.8和0.2是發明中的數據，可以根據具體情況調整。總的原則是，回收有效性權重，而損耗平衡權輕。在足夠多的單元回收后，系統會檢查是否需要更激進的損耗平衡策略。如果最勞損和最不勞損的擦除次數相差超過 500或更多，系統將用另外一個分數公式來計算回收策略。

這種策略，先是考慮到回收效率，如果導致損耗不均衡，則進入損耗平衡階段，在這個階段回收效率不是那么重要。再者，沒有必要過早進入損耗平衡階段，因為那樣反而會增加系統整體的損耗。

Chiang，Lee和Chang提出了一個稱作CAT的塊集群技術【Chiang et al.1999】，Chiang和Chang后來改進這個技術為DAC【Chiang and Chang 1999】。這些思想的中心概念是“溫度”，一個塊的溫度表明這個塊是否將要被更新。系統基于兩個簡單規則來為每個塊維護溫度：一個是當一個塊被更新時，溫度升高，另一個是，隨著時間的增長塊的溫度降低。CAT將塊分為三類：只讀、冷和熱。這種分類沒必要必須與溫度一致，因為在CAT中，塊僅僅在回收的時候重新分類，每個擦除單元存儲一類塊，當擦除單元要回收時，擦除單元上的有效塊被重新分類，CAT選擇一下公式計算分數最高的回收單元。

其中，有效塊(j)是擦除單元j中的有效數據塊的個數，年齡(j)是從上次更新為止的時間，從這個分數公式可以看出，系統會優先選擇無效塊多而有效數據塊少的單元、不是最近更新的單元和擦除次數少的單元。這一定程度上結合了有效性和損耗平衡。CAT策略還包括額外的損耗平衡機制：當一個擦除單元將要達到它的擦除上限時，會將其與擦除次數最少的擦除單元交換數據。

DAC策略則更加復雜。首先，塊被分為3個以上的分類，更重要的是，塊在每次更新時重新分類，所以冷塊升溫后將被重新分配到一個更熱的擦除單元中，即使這個冷塊所在的單元沒有回收時。

TrueFFS選擇回收單元是基于無效數據個數、擦除次數和靜態數據的識別【Dan and Williams 1997】。TrueFFS還試圖將相關的塊放在一起，這樣一個擦除單元中的塊就可能同時無效，做法是將連續編號的邏輯塊存放在一個擦除單元中，這種做法基于的假設是，上層軟件將相關的塊是有連續的邏輯編號。

Kim和Lee提出一個自適應的結合損耗平衡和回收有效性的技術【Kim and Lee 2002】。他們的方法是設計一個文件系統，而不是一個塊映射機制，但是因為它也適應于塊映射機制。這個方法稱作CICL，選擇一個擦除單元（事實上是一個稱為段的一組擦除單元）回收，回收依據為一下公式的最小分數。

在這個表達式中，λ不是一個常量，而是依賴于更加最勞損和最不勞損擦除單元的差值。

當λ小的時候，單元回收主要考慮擦除效率，而λ大的時候則以損耗平衡為主。當λ增加時，損耗平衡問題越來越嚴重，這時候這個公式就會將重點轉向損耗平衡，而損耗均衡時則以擦除效率為主。

3 SSD在分層存儲中的應用

SSD閃存具有較高的IO性能并且耗電量小等優點，但是SSD盤的單位價格仍舊太高，純的SSD盤性價比比較低，而利用SSD的高性能和SATA盤的低價格組合的分層存儲已經成為業內的更好的選擇，很多大型數據中心已經開始研究如何使用SSD與SATA結合來提供更高的性價比，比如IBM數據中心等，SSD做為分層存儲有兩種方案，一種是將SSD與磁盤并行，另一種是將SSD作為磁盤的緩存，如圖3所示：

圖3 SSD分層存儲結構圖

3.1 FlashCache

FlashCache是一個為innoDB設計的塊cache應用，也可以用于一般的應用。FlashCache是基于 linux設備映射（Device Mapper）框架，將SSD和SATA盤虛擬成一個獨立的塊設備的軟件，利用SSD的高性能和SATA盤的高容量來提升整體的性價比。

FlashCache是將cache部分（SSD）分成邏輯的集合，然后將數據塊通過 hash運算到相應的集合中，其中，塊大小、集合大小以及cache大小是在創建時配置的參數，默認的集合大小為512塊，這樣，集合個數就時cache大小除以集合大小。其中，dbn（disk block number）即磁盤塊號，也就是磁盤的邏輯塊號，FlashCache使用以下的hash公式，將相應的磁盤塊映射到相應的集合中。

所以，每個塊一定會映射到相應的集合上，根據塊號就能從相應的目標集合中就能線性探相應的塊。設備映射層會將 IO組合成固定塊大小，然后將塊存放在 cache上，FlashCache緩存所有的塊級別的 IO，在每個集合中替換算法選擇是FIFO或者LRU，可以通過sysctl進行算法切換。

對于每個邏輯塊來說，都有一個邏輯塊頭，邏輯塊頭中包括邏輯塊號（dbn）、閃存狀態（Dirty/Valid/Invalid）、用于LRU算法的靜態指針和校驗和信息。校驗和信息主要保證塊信息的正確性，也可以不設置校驗和。

所有的邏輯頭，即邏輯塊的元數據，可以拼接成物理塊，存放在SSD中。

邏輯頭所占用的空間開銷，例如300GB 的SSD cache用16KB固定塊大小，大約2千萬個cache塊，元數據占用480MB，如果是300GB SSD用4KB的塊大小，元數據就占用1.8GB空間，如圖4所示：

圖4 SSD寫回架構

讀過程，首先，通過hash計算找出dbn所在的SSD中的目標集合，然后從相應的目標集合中線性找到dbn，如果命中則返回數據，否則從磁盤中讀數據返回，然后將數據塊替換到相應的集合中。

寫過程，FlashCache的寫過程使用寫回策略，即所有的寫操作都將數據寫入flash中，并將寫入的數據標記成臟塊。（如果寫入的數據已經是臟塊，則不需要重新標記。）每個集合中的臟塊百分比有個閾值，當臟塊的比例超過這個閾值時，就被設置成將要寫回磁盤，對于臟塊的選擇，使用一個類似時鐘算法選擇空閑的臟塊寫回。

讀寫過程中，盡量少寫回元數據，避免不必要的損耗，比如讀數據時，就不需要寫回。

替換策略選擇FIFO先進先出算法或LRU最近最久未使用算法，具體LRU算法的實現是使用靜態雙向鏈表，鏈表表頭表示最近被訪問的塊，而鏈表表尾則表示最久未訪問塊，當一個塊被訪問時，被訪問塊就被更新為新表頭。

4 結束語

SSD已經廣泛應用于計算機、手機、攝像機以及工作站等，SSD為這些設備提供了高速可靠的存儲，隨著 SSD技術的不斷提高、大規模的生產，SSD的價格也越來越低，性價比逐年攀升。

這篇文章的目的就是總結已發明的SSD閃存技術，希望能對新的SSD閃存技術的研究和開發提供更好的參考。

[1]Assar,M.,Nemazie,S.,and Estakhri,P.1995a.Flash memory mass storage architecture.US patent 5,388,083.Filed March 26,1993; Issued February 7,1995; Assigned to Cirrus Logic.

[2]Assar,M.,Nemazie,S.,and Estakhri,P.1995b.Flash memory mass storage architecture incorporation wear leveling technique.US patent 5,479,638.Filed March 26,1993; IssuedDecember 26,1995; Assigned to Cirrus Logic.

[3]Assar,M.,Nemazie,S.,and Estakhri,P.1996.Flash memory mass storage architecture incorporation wear leveling technique without using CAM cells.US patent 5,485,595.Filed October 4,1993; Issued January 16,1996; Assigned to Cirrus Logic.

[4]Ban,A.1995.Flash file system.US patent 5,404,485.Filed March 8,1993; Issued April 4,1995; Assigned to M-Systems.

[5]Ban,A.1999.Flash file system optimized for page-mode flash technologies.US patent 5,937,425.Filed October 16,1997; Issued August 10,1999; Assigned toM-Systems.

[6]Ban,A.2004.Wear leveling of static areas in flash memory.US patent 6,732,221.Filed June 1,2001; Issued May 4,2004; Assigned to M-Systems.

[7]Barrett,P.L.,Quinn,S.D.,and Lipe,R.A.1995.System for updating data stored on a flash-erasable,programmable,read-only memory (FEPROM)based upon predetermined bit value of indicating pointers.US patent 5,392,427.Filed May 18,1993; Issued February 21,1995;Assigned to Microsoft.

[8]Chang,L.-P.,Kuo,T.-W.,and Lo,S.-W.2004.Real-time garbage collection for flash-memory storage systems of real-time embedded systems.ACM Transactions on Embedded Computing Systems 3,4,837–863.