通過差值和壓縮減少SSD的擦除次數*

郭云格，陳明宇 ，蔣德鈞

1.中國科學院 計算技術研究所，北京 100190

2.中國科學院大學，北京 100049

1 引言

固態硬盤（solid state drives，SSD），具有讀寫速度快、防震抗摔、低功耗、無噪音、工作溫度范圍大、輕便等機械硬盤不具有的優點。SSD在接口規范和定義、讀寫功能及使用方法上與普通硬盤完全相同。因此，最近幾年SSD被越來越多地應用于數據中心服務器、存儲系統等多種領域。

類似于一次寫入型存儲器，SSD在進行寫之前必須進行擦除操作。頻繁的擦除操作會嚴重影響SSD壽命和性能：首先，擦除操作會損耗存儲單元，導致SSD無法可靠地保存數據。當擦除次數達到上限時，SSD將無法繼續使用。此外，擦除操作可能導致的寫入放大會增加寫和讀請求的響應時間，嚴重影響SSD的性能[1-2]。

為了減少SSD的擦除次數，可以采用一次寫入型存儲器編碼WOM（write-once memory codes）[3]，但是由于編碼的長度大于數據本身的長度，需要占用額外的存儲空間，在SSD的設計中并沒有被廣泛采用。近年來提出的Reusable SSD[4]利用SSD每個物理頁的額外空間實現二次寫，但是需要占用大量的額外空間。隨著SSD使用時間的增長，需要保存校驗位的額外空間越來越多，這種方法將不再適用。

為了在減少SSD擦除次數同時提升空間利用率，本文針對數據庫中的數據更新場景設計了一種對SSD進行二次寫（對寫過的SSD物理頁進行二次寫入）的方法，即基于差值和壓縮的二次寫（second write based on difference and compression，SWBOCAD）。最后本文使用tpcc基準測試程序對所提的編碼方式進行了評測。評測結果表明，和Reusable SSD[4]相比，在數據更新量較小的應用場景中，SWBOCAD能夠減少SSD 50%的擦除次數。

本文的主要貢獻如下：

（1）提出利用物理頁中的可寫位和WOM編碼實現對一個SSD物理頁的二次寫；

（2）提出利用壓縮進一步提升二次寫的可能性。

本文的組織結構：第2章介紹本文的工作背景；第3章介紹SWBOCAD的設計與實現；第4章對本文提出的方法進行評測；第5章介紹與本文相關的工作；第6章為總結。

2 工作背景

2.1 基于NAND Flash的SSD

SSD一般采用NAND Flash作為內部的存儲介質。根據存儲元件的不同，可以將SSD分為SLC（single-level cell）、MLC（multi-level cell）、TLC（triplelevel cell）三種。三種存儲元件的每個存儲單元（cell）分別可以存儲1 bit、2 bit、3 bit的信息。存儲單元通過電壓的高低來表示不同的數據。存儲元件的基本結構如圖1所示。

Fig.1 Storage cell structure圖1 存儲單元結構圖

在對一個閃存單元編程的時候，電壓加到控制柵極（control gate）上，形成一個電場，讓電子穿過硅氧化物柵欄，達到浮動柵極（floating gate）。穿越過程完成后，控制柵極上的電壓會立刻降回零，硅氧化物就扮演了一個絕緣層的角色。單元的擦除過程類似，只不過電壓加在硅基底（P-well）上。

在SSD內部，存儲單元被組織成塊（block），即擦除的基本單位。一個塊通常包括256～2 048個頁（page），頁大小通常為2～16 KB，頁是讀寫的基本單位。在芯片內部，塊又被分成若干個平面（plane），每個平面分開管理，可以獨立地進行各種操作[5-6]。圖2是Micron的芯片內部結構圖[7]。

每個頁都配有額外區域，主要用來保存ECC編碼（error correction codes）[2,5]，其大小通常為頁面大小的5%～12.5%[6,8]。隨著SSD使用時間的增長，需要保存ECC的空間也會增加[2,9-10]。

由于SSD在寫之前必須擦除，如果在不改變數據存儲位置的條件下對數據進行原地更新（in-place update），會造成巨大的開銷。因此，SSD的數據更新操作通常采用異地更新的方式（out-of-place update）：在收到一個邏輯頁的更新請求時，之前其對應的物理頁會被標記為無效頁，新的數據會被寫到一個新分配的未寫過的物理頁中。這就需要建立一個映射表來保存邏輯頁和物理頁的映射關系，這是閃存轉換層（flash transfer layer，FTL）的主要工作。

雖然有很多工作嘗試改進垃圾回收的時機和策略[11]，利用緩存來盡量減小寫入放大的倍數[12]，平衡各個塊的擦除次數來延長SSD的壽命[13]，但是垃圾回收仍然是影響SSD性能和使用壽命的一個重要因素。

2.2 WOM編碼

WOM編碼在1982年第一次被Rivest和Shamir提出[3]，表1是WOM編碼的一種。假設每一位只能從0變為1，無法從1變為0。

Table 1 WOM codes表1 WOM編碼

這種方式用3位編碼來表示2位的數據。以數據01為例，第一次寫的時候用010來表示；當進行第二次寫的時候，如果數據還是01，則保持編碼不變，即010；如果數據變為00，則用編碼111；如果數據變為10，則用編碼011；如果數據變為11，則用編碼110。可以看到，第一次寫的編碼010總能夠被第二次寫的編碼111、011、110完全覆蓋。通過這種編碼，原來只能寫一次的存儲介質就能進行二次寫。

當然，表1只是WOM編碼中的一種，有很多其他的編碼方式。但是無論采用哪種編碼方式，編碼的長度總是長于數據的長度。如果在SSD中采用WOM，以表1的編碼為例，只有2/3的實際空間被用來存儲數據；每次數據傳輸也都需要額外傳輸更多的數據。

Fig.2 Micron NAND flash chip internal structure圖2 鎂光NAND閃存芯片內部結構圖

3 設計與實現

通常情況下，新寫一個SSD頁時，寫入數據有1有0。根據SSD擦除機制，SSD擦除一個數據塊時將塊內所有位置為1。因此，SSD在寫入數據時只將bit值為1的位置為0，即實際只寫入0，并不寫入1。由于實際寫入數據時有0有1，因此，一個物理頁寫過一次后，通常有些位仍然處于可寫的狀態（programable），本文將這種物理頁稱為可二次寫頁，對這些物理頁仍然可寫的位再次執行寫操作，稱之為二次寫。本文利用上述可二次寫入的物理頁中仍然可以寫入的位保存新數據，從而提高這些可二次寫頁的利用率，進而減少物理頁的擦除次數。

因此，為了實現基于物理頁的二次寫操作，對于邏輯頁的更新操作，本文不像傳統的SSD設計，為邏輯頁分配一個新的物理頁進行寫入，而是將待寫入的數據和該邏輯頁對應的原來物理頁的數據進行對比（按位異或），得到一個差值信息。對于一個已寫入一次的物理頁而言，其中可寫位的數量可能并沒有太多，因此，本文利用上述差值信息判斷待寫入數據是否可以以二次寫入的方式進行保存。如果差值并不大，則保存差值這個信息到寫過的物理頁中；如果差值很大，則延用傳統的SSD異地更新機制，分配一個新的物理頁保存新數據。

為了進一步減少所需的可寫位，充分利用寫過的物理頁，本文將差值信息進行壓縮，然后進行編碼，再將編碼寫入到可重寫的頁中。之后，將可重寫頁的頁號等二次寫的信息保存到原來物理頁的額外空間中。

圖3所示為驅動軟件與SSD控制器的交互示意圖。其中，SSD控制器接收驅動發來的讀寫請求，再向Flash芯片發送相應命令進行讀寫操作。

Fig.3 System structure圖3 系統結構圖

本文提出的方法可以實現在SSD控制器中，寫入操作的數據差值和壓縮過程都在SSD控制器中實現；讀取操作的數據解壓和還原操作也在SSD控制器中實現。

3.1 寫操作

寫操作的主要流程如圖4所示，當控制器接收到驅動的某個邏輯頁的寫請求時，首先根據映射表判斷該邏輯頁是否已經有物理頁與之相對應。

本文提出的方法只對有物理頁對應的情況所做的操作進行了修改（圖4中虛線框部分），下面對其中的幾個主要步驟進行詳細說明，以一個大小為128 bit的頁面數據為例，原數據和新數據如表2所示。

Table 2 Example data表2 示例數據

3.1.1 獲取差值

在接收到一個邏輯頁的更新請求時，先根據映射表從SSD中讀出與該邏輯頁對應的物理頁的數據，然后將新的數據和原來的數據進行比較，本文采用的是按位異或操作。如果異或的結果中只有少量的位是1，表明該邏輯頁的新數據和舊數據相比變化較小，即更新的數據量較小，可以采用保存差值的方法來保存更新的邏輯頁。

表2中原數據和新數據做異或后的結果轉化為十六進制為1000000E000000000000C0000000000C。

為了減少保存差值信息所需的可寫位的數量，在獲取到差值信息后，由于新寫入的數據和原來的數據相差較小，差值信息中絕大部分位都是0，只有少量的位是1，因此對差值進行壓縮。壓縮可以使用任何已有的壓縮方法，本文直接采用Linux下的zip工具。由于表2中數據較少，直接采用哈夫曼編碼來進行壓縮，結果為0011 1111 1000 1111 1111 1111 0111 1111 1111 01，共38 bit。

Fig.4 Write process flowchart圖4 寫操作流程圖

3.1.2 差值編碼

差值壓縮后，為了在可重寫頁上寫入壓縮后的數據，需要對其進行編碼。

為了利用頁面中已有的01或10，可以用01表示0，10表示1。對于可重寫頁中無法利用的01和10，將其填充為11，作為無效數據。

表2中數據進行壓縮后用上述編碼結果為01011010 10101010 10010101 10101010 10101010 10101010 01101010 10101010 10101010 0110。

針對可重寫頁中可寫位的數量，可以根據可寫位的數量采用相應的編碼長度，例如用3 bit編碼表示2 bit數據，用4 bit編碼表示3 bit數據。

3.1.3 數據寫入

對于編碼后的數據，選取包含足夠數量的可寫位的可重寫頁。可按照可重寫頁中可寫位的數量大小對可重寫頁進行排序，選擇可寫位的數量與編碼后的數據長度相匹配的可重寫頁。可重寫頁指該頁面已經被無效掉，但發現其中還有大量的可寫位，沒有進行擦除操作的頁。

首先驗證可重寫頁中剩余可寫位的數量足夠寫入請求數據，然后按3.2節中編碼方法將數據寫入，并將可重寫頁的索引信息（頁號）、編碼方式（可用一個數字代表一種編碼）等二次寫信息存入原來物理頁的額外空間中。

選擇下述的可重寫頁來寫入編碼后的數據（不包括額外空間的內容）：

寫入編碼后的數據后，該可重寫頁的內容變為（灰色部分為改變的bit）：

3.2 讀操作

數據讀取首先根據映射表從原來的物理頁中讀取數據（這個物理頁并不會作為廢棄頁進行回收），并從其額外空間中讀取二次寫的信息（可重寫頁的索引信息和編碼方式），然后根據二次寫的頁號從可重寫頁中讀取壓縮后的差值數據，根據編碼方式解壓出差值數據，然后與舊數據進行異或操作，恢復出新的數據。

讀操作的流程圖如圖5所示，其中，虛線框中是本文方法對傳統的SSD控制器所做的補充。

Fig.5 Read process flowchart圖5 讀操作流程圖

4 實驗評測

下面對本文提出的二次寫的方法進行評測。4.1節介紹測試平臺及評測系統；4.2節介紹差值數據和壓縮的測試；4.3節介紹可重寫頁的獲取；4.4節測試差值寫入的過程；4.5節是對測試結果的分析。

4.1 測試平臺及評測系統

為了獲取真實應用的數據，實驗采用MySQL-tpcc[14]工具加載一個數據庫，使用其中的一個大小為3 GB左右的表作為監測對象，表中大約有3 000萬條記錄。然后進行數據庫的更新操作，記錄數據更新導致的數據變化，具體步驟如下：

（1）對數據表進行300萬（記錄總數的10%）次更新操作，更新操作每次隨機選擇一條記錄，然后隨機選擇6個非主鍵屬性中的一個進行更新。

（2）對數據表做快照，保存其數據。

按照上述步驟循環幾次，即可得到數據表的多個快照文件。

將不同的快照文件進行比較，獲取快照文件之間的差值數據。再對差值數據進行壓縮，嘗試將壓縮后的差值數據寫入到原來的文件中，從而減少擦除次數。

4.2 差值數據及壓縮測試

獲取到數據表的多個快照文件后，首先按照頁面大小為8 KB對文件進行切分；接著比較對應的文件，即將文件進行按位異或操作，得到頁面更新前后的差值數據；然后將差值數據進行壓縮，統計差值數據的壓縮率。

實驗共獲得5個快照文件，差值數據通過相鄰的快照文件進行按位異或操作得到，接著采用zip工具對差值數據進行壓縮，發現絕大部分的差值數據的壓縮率能夠達到90%以上，只有少數的差值數據壓縮率在90%以下。為了表述方便，下文的差值文件指的是包含差值數據的文件。

具體的統計結果即處于各個壓縮率的文件數量所占文件總數的具體比例，如圖6所示。圖中（1）代表壓縮率小于等于80%以下，（2）代表壓縮率在81%～85%之間，（3）代表壓縮率在86%～90%之間，（4）代表壓縮率在91%～95%之間，（5）代表壓縮率在96%～100%之間。從圖6中可以看出90%的差值文件壓縮率都在90%以上。

Fig.6 Percentages of files with different compression rates after 3 million times update(Cfor compression rate)圖6 300萬次更新后不同壓縮率文件的占比（C代表壓縮率）

對于間隔的快照文件進行異或操作，即第1個快照文件與第3個快照文件做差值，第2個快照文件與第4個快照文件做差值，第3個快照文件與第5個快照文件做差值，得到的為進行600萬次更新操作后得到的文件的差值。各種壓縮率文件所占的比例如圖6所示。

圖7中（1）～（5）的含義和圖6相同，從圖中可以看出，進行600萬次更新操作后86%的差值文件的壓縮率仍大于90%。

Fig.7 Percentages of files with different compression rates after 6 million times update(Cfor compression rate)圖7 600萬次更新后不同壓縮率文件的占比（C代表壓縮率）

因此，壓縮后的差值文件大小低于文件自身大小的10%，可見數據庫類應用的更新操作，產生的數據變化量非常小，通過保存更新前后數據的差值來保存更新后的數據可以大大減少所需的存儲空間，為本文提出的SSD二次寫的方法提供了可能。

4.3 可重寫頁的獲取

根據第一次寫過的頁中的可寫位的數量，判斷該頁能否用于二次寫，即是否是可重寫頁。如果可寫位的數量過低，則不滿足寫入壓縮文件的需要，無法用于二次寫。

在本實驗中，切分快照文件產生的頁面文件都可以視為第一次寫的頁，本文假定在寫的過程中，存儲單元只能從1變為0，不能從0變為1，則其中為1的位的數量，即為可寫位的數量。

分析5個快照文件中為1的位，得到圖8所示的統計結果。可以看到，對于每個快照文件，可寫位的平均數量都處于27%～28%之間，能夠滿足寫入壓縮后的差值數據的要求。

Fig.8 Percentage of writable bits in snapshot file圖8 快照文件中可寫位的比例

事實上，如果在寫數據之前可以提前感知所寫的數據中0位的數量遠大于1位的數量，則可以將所寫數據按位取反后再進行寫入，從而使物理頁在第一次寫后仍有很大一部分處于可寫狀態。

在傳統的SSD設計中，垃圾回收操作會在物理頁無效以后直接將其擦除，并不會利用其中的可寫位，本文利用這些可寫位來實現SSD的二次寫。

4.4 差值寫入測試

基于4.2節和4.3節所得實驗數據，進行差值寫入測試。選取可重寫頁，嘗試進行二次寫入的操作。實驗步驟如下：

（1）任意選擇一個快照文件切分后產生的頁面文件作為可重寫頁；

（2）任意選擇壓縮后的文件，按照3.2節中所述方式進行編碼；

（3）判斷編碼后的文件能否寫入可重寫頁中。

本文共進行了4次實驗，由于實驗中的可重寫頁面數量較多（1 570 816×4），為了證明本文方法確實可行，每次從切分快照文件所得的頁面文件中任意選擇一個作為可重寫頁，對于每一個壓縮后的差值文件，嘗試將其寫入可重寫頁中。

每次實驗都會對差值文件1～4壓縮后的3 GB/8 KB×4=1 570 816個文件進行二次寫測試。對于4個可重寫頁，二次寫失敗的統計結果如圖9所示。

Fig.9 Failure times of write twice圖9 二次寫的失敗次數

其中，可重寫頁1的失敗次數最小，所占比例為36 743/1 570 816=2.34%；可重寫頁2二次寫全部失敗；可重寫頁3失敗次數和4接近，分別為58 529和59 958，所占比例分別為3.73%和3.82%。相應地，可重寫頁1中1 bit即可寫位的比例最高，為28.78%；可重寫頁2中可寫位的比例為5.98%，不滿足二次寫的要求，因此全部失敗；可重寫頁3和4中可寫位的比例較為接近，分別為23.99%和22.65%。

正如4.3節中所說，如果所寫數據中1 bit（可寫位）的數量較少，可以將數據按位取反后寫入。因此，對于本文方法，可以認為所有的寫過一次的頁面都可以作為進行二次寫的可重寫頁，且寫入成功的概率為96%。

對于壓縮率大于97%的差值文件，本文進行了進一步的實驗：對每個快照文件切分后所得的頁面文件（可重寫頁）進行兩次寫入操作，寫入的內容為兩個壓縮率大于97%的差值文件；如果第一個差值文件成功寫入可重寫頁，則記錄下寫入第一個差值文件后可重寫頁的相關信息，再嘗試寫入第二個差值文件。

實驗結果表明，有22.41%的可重寫頁能夠寫入兩個壓縮后的差值文件。

對于壓縮率在95%以上的差值文件，更詳細的統計如圖10所示。

Fig.10 Percentages of files with above 95%compression rate(Cfor compression rate)圖10 壓縮率在95%以上的文件所占比例（C代表壓縮率）

圖10中（1）～（4）分別代表壓縮率在96%、97%、98%、99%的差值文件所占的比例。從圖中可以看出，壓縮率在97%以上的比例為65%。

4.5 測試結果分析

4.2節中差值數據的壓縮結果表明數據庫的更新操作導致的相應的文件內容的變化十分微小，在這類應用中，可以采用本文方法。

無論哪種應用，在其對SSD進行寫入操作后，依然存在大量的可寫位。本文提出的二次寫的方法可以利用傳統SSD設計無法利用的可寫位，在響應相同的寫操作的情況下，大大減少SSD的擦除次數，延長SSD的使用壽命。

4.4節的測試結果則表明，對于一個8 KB大小的頁面，如果壓縮率能夠達到90%以上，即壓縮后的文件小于其自身大小的10%，并且頁面中所含的可寫位的數量在30%左右，則壓縮后的文件能夠成功寫入到頁面中的概率為96%。

表3對比了本文提出的方法與Reusable SSD[4]（表中簡稱ReSSD）對SSD擦除次數的影響。

Table 3 Comparison between this paper and Reusable SSD表3 本文方法與Reusable SSD的比較

Reusable SSD主要思想是利用兩個寫過一次的物理頁和其額外空間來編碼一個新的邏輯頁，實現物理頁的二次寫。具體實現為將一個邏輯頁通過2.1個物理頁來表示，表示成功的概率為95%；如果第一次表示嘗試沒有成功，進行第二次嘗試。成功的概率為1-(1-0.95)×(1-0.95)=99.75%。

在收到一個寫邏輯頁的請求時，選擇兩個寫過一次且被無效掉的物理頁，通過編碼將邏輯頁的數據寫到這兩個物理頁和其額外空間（每頁的額外空間需要寫入5%的數據），實現物理頁的二次寫。讀取數據時，讀出相應的兩個物理頁的內容，根據編碼恢復出原來的數據。

Reusable SSD需要占用大量的頁面的額外空間，因此隨著SSD的使用，用于保證其穩定性的校驗碼越來越多，需要的額外空間越來越大，Reusable SSD將無法繼續應用。因此只適用于SSD壽命的前30%；本文方法只占用十分少的額外空間來保存二次寫的信息。以8 KB的頁面為例，假設SSD的容量為512 GB，則包含226個頁面，本文方法需要4×8 bit的空間來保存可重寫頁的索引。而對于8 KB大小的頁面，通常含有448 Byte[7]的額外空間，本文方法只需占用其中的4 Byte。

對于一個可重寫頁寫入兩個文件的情況，除了需要保存可重寫頁的索引信息，還要保存寫入文件的起始位置和長度信息。以8 KB的頁面為例，包含8×8×1 024=216bit，需要2×8 bit的空間來保存起始位置，長度信息也一樣。因此，除了可重寫頁的索引信息所需的4 Byte空間，還需要4 Byte空間來保存起始位置和長度，共8 Byte空間。

與Reusable SSD相比，本文提出的方法能夠在一個可重寫頁中寫入兩個壓縮后的差值文件。4.2節和4.4節中統計結果表明有82%的差值文件壓縮率在95%以上，其中的65%壓縮率在97%以上，即有82%×65%=53.3%的差值文件可以作為要寫入的對象。而4.4節的實驗結果表明對于壓縮率在97%以上的文件，有22.41%的概率能夠寫入到可重寫頁中。因此，本文方法有63.3%×22.41%=14.19%的概率可以在一個可重寫頁中寫入兩個差值文件。

Reusable SSD總計減少擦除次數的百分比為：0.997 5×0.33×0.3=9.88%。本文提出的方法總計減少擦除次數的百分比為：0.96×0.5×(2×0.141 9+1-0.141 9)×1=54.81%。

由于本文方法能夠有效減少SSD的擦除次數，在響應相同次數的寫操作時，能夠減少寫入放大。但是，在讀取數據的過程中，本文方法需要先將數據讀出，根據額外空間的內容來判斷是否有差值信息與其對應；如果有差值信息存在，還需要讀取差值信息所在的物理頁，然后再將差值信息解壓，從而恢復出新的數據。整個過程中，進行了兩次讀取操作，一次解壓操作；如果不采用本文方法，只需要進行一次讀取操作。

在數據寫入的過程中，本文方法需要先將原來的數據讀出，和新數據進行異或，然后壓縮，進而判斷能否將其寫入無效頁中；如果可以，將壓縮后的數據進行編碼，寫入到無效的頁中，保存無效頁的物理頁號到原來頁的額外空間，共需要兩次讀取操作，兩次寫入操作。如果不采用本文方法，只需進行一次寫入操作。

因此，本文方法會對數據讀取和寫入的性能帶來一定的影響。但是，在實際應用中，對于邏輯頁的操作一般是連續的，可以將本文方法中的讀取操作和寫入操作并行，從而減少本文方法對讀寫性能帶來的影響。

需要說明的是，本文的測試集只有3 GB，而目前SSD的容量一般都在256 GB、512 GB，但SSD進行讀寫的基本單位都是頁，本文方法主要對頁的讀取和寫入操作進行改動，實驗數據處理也是以頁作為基本單位。雖然本文的數據集對于SSD的容量而言太小，但是并不會影響本文實驗結果的說服力。

5 相關工作

擦除操作會嚴重影響SSD的性能，近年來，有很多工作在研究如何減少擦除操作。

這些工作主要分為兩大類，一類是通過優化垃圾回收操作，平衡存儲單元的損耗，從而延長SSD的使用壽命。例如，Stable Greedy[15]通過邏輯頁的更新頻率來將邏輯頁分為經常更新的熱頁和不經常更新的冷頁，然后將其分別存放到擦除次數較少的塊和擦除次數較多的塊中，一方面可以減少垃圾回收中的擦除操作，另一方面也能平衡各個存儲單元的擦除次數。

一類則是通過WOM編碼，對寫過的物理頁進行重復利用，從而實現二次寫，減少擦除次數。但是，基于WOM編碼的大部分工作都需要多于邏輯頁的空間來存儲編碼信息[5,16]，而且編碼的復雜度較高，還有很高的幾率編碼失敗[17-18]。改進的WOM編碼利用頁的額外空間來實現二次寫，編碼實現比較簡單，但是仍然有一定的幾率失敗，而且隨著SSD使用時間的增長無法繼續發揮作用[4]。

本文方法利用寫過物理頁的可寫位，通過簡單的編碼實現二次寫。針對某些應用中數據更新量較小的特點，采用保存差值的方法來保存新數據。可以作為FTL的一個軟件擴展，具有良好的移植性。

6 結論

本文基于壓縮和編碼實現了一種對SSD進行二次寫的方法，不需要占用大量的額外空間，減少了SSD的擦除次數，顯著延長SSD的使用壽命，在實際應用中能發揮重要的作用。