郭云格，陳明宇 ，蔣德鈞

1.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190

2.中國(guó)科學(xué)院大學(xué)，北京 100049

1 引言

固態(tài)硬盤（solid state drives，SSD），具有讀寫速度快、防震抗摔、低功耗、無(wú)噪音、工作溫度范圍大、輕便等機(jī)械硬盤不具有的優(yōu)點(diǎn)。SSD在接口規(guī)范和定義、讀寫功能及使用方法上與普通硬盤完全相同。因此，最近幾年SSD被越來(lái)越多地應(yīng)用于數(shù)據(jù)中心服務(wù)器、存儲(chǔ)系統(tǒng)等多種領(lǐng)域。

類似于一次寫入型存儲(chǔ)器，SSD在進(jìn)行寫之前必須進(jìn)行擦除操作。頻繁的擦除操作會(huì)嚴(yán)重影響SSD壽命和性能：首先，擦除操作會(huì)損耗存儲(chǔ)單元，導(dǎo)致SSD無(wú)法可靠地保存數(shù)據(jù)。當(dāng)擦除次數(shù)達(dá)到上限時(shí)，SSD將無(wú)法繼續(xù)使用。此外，擦除操作可能導(dǎo)致的寫入放大會(huì)增加寫和讀請(qǐng)求的響應(yīng)時(shí)間，嚴(yán)重影響SSD的性能[1-2]。

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

為了在減少SSD擦除次數(shù)同時(shí)提升空間利用率，本文針對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)更新場(chǎng)景設(shè)計(jì)了一種對(duì)SSD進(jìn)行二次寫（對(duì)寫過(guò)的SSD物理頁(yè)進(jìn)行二次寫入）的方法，即基于差值和壓縮的二次寫（second write based on difference and compression，SWBOCAD）。最后本文使用tpcc基準(zhǔn)測(cè)試程序?qū)λ岬木幋a方式進(jìn)行了評(píng)測(cè)。評(píng)測(cè)結(jié)果表明，和Reusable SSD[4]相比，在數(shù)據(jù)更新量較小的應(yīng)用場(chǎng)景中，SWBOCAD能夠減少SSD 50%的擦除次數(shù)。

本文的主要貢獻(xiàn)如下：

（1）提出利用物理頁(yè)中的可寫位和WOM編碼實(shí)現(xiàn)對(duì)一個(gè)SSD物理頁(yè)的二次寫；

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

本文的組織結(jié)構(gòu)：第2章介紹本文的工作背景；第3章介紹SWBOCAD的設(shè)計(jì)與實(shí)現(xiàn)；第4章對(duì)本文提出的方法進(jìn)行評(píng)測(cè)；第5章介紹與本文相關(guān)的工作；第6章為總結(jié)。

2 工作背景

2.1 基于NAND Flash的SSD

SSD一般采用NAND Flash作為內(nèi)部的存儲(chǔ)介質(zhì)。根據(jù)存儲(chǔ)元件的不同，可以將SSD分為SLC（single-level cell）、MLC（multi-level cell）、TLC（triplelevel cell）三種。三種存儲(chǔ)元件的每個(gè)存儲(chǔ)單元（cell）分別可以存儲(chǔ)1 bit、2 bit、3 bit的信息。存儲(chǔ)單元通過(guò)電壓的高低來(lái)表示不同的數(shù)據(jù)。存儲(chǔ)元件的基本結(jié)構(gòu)如圖1所示。

Fig.1 Storage cell structure圖1 存儲(chǔ)單元結(jié)構(gòu)圖

在對(duì)一個(gè)閃存單元編程的時(shí)候，電壓加到控制柵極（control gate）上，形成一個(gè)電場(chǎng)，讓電子穿過(guò)硅氧化物柵欄，達(dá)到浮動(dòng)?xùn)艠O（floating gate）。穿越過(guò)程完成后，控制柵極上的電壓會(huì)立刻降回零，硅氧化物就扮演了一個(gè)絕緣層的角色。單元的擦除過(guò)程類似，只不過(guò)電壓加在硅基底（P-well）上。

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

每個(gè)頁(yè)都配有額外區(qū)域，主要用來(lái)保存ECC編碼（error correction codes）[2,5]，其大小通常為頁(yè)面大小的5%～12.5%[6,8]。隨著SSD使用時(shí)間的增長(zhǎng)，需要保存ECC的空間也會(huì)增加[2,9-10]。

由于SSD在寫之前必須擦除，如果在不改變數(shù)據(jù)存儲(chǔ)位置的條件下對(duì)數(shù)據(jù)進(jìn)行原地更新（in-place update），會(huì)造成巨大的開(kāi)銷。因此，SSD的數(shù)據(jù)更新操作通常采用異地更新的方式（out-of-place update）：在收到一個(gè)邏輯頁(yè)的更新請(qǐng)求時(shí)，之前其對(duì)應(yīng)的物理頁(yè)會(huì)被標(biāo)記為無(wú)效頁(yè)，新的數(shù)據(jù)會(huì)被寫到一個(gè)新分配的未寫過(guò)的物理頁(yè)中。這就需要建立一個(gè)映射表來(lái)保存邏輯頁(yè)和物理頁(yè)的映射關(guān)系，這是閃存轉(zhuǎn)換層（flash transfer layer，F(xiàn)TL）的主要工作。

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

2.2 WOM編碼

WOM編碼在1982年第一次被Rivest和Shamir提出[3]，表1是WOM編碼的一種。假設(shè)每一位只能從0變?yōu)?，無(wú)法從1變?yōu)?。

Table 1 WOM codes表1 WOM編碼

這種方式用3位編碼來(lái)表示2位的數(shù)據(jù)。以數(shù)據(jù)01為例，第一次寫的時(shí)候用010來(lái)表示；當(dāng)進(jìn)行第二次寫的時(shí)候，如果數(shù)據(jù)還是01，則保持編碼不變，即010；如果數(shù)據(jù)變?yōu)?0，則用編碼111；如果數(shù)據(jù)變?yōu)?0，則用編碼011；如果數(shù)據(jù)變?yōu)?1，則用編碼110?？梢钥吹?，第一次寫的編碼010總能夠被第二次寫的編碼111、011、110完全覆蓋。通過(guò)這種編碼，原來(lái)只能寫一次的存儲(chǔ)介質(zhì)就能進(jìn)行二次寫。

當(dāng)然，表1只是WOM編碼中的一種，有很多其他的編碼方式。但是無(wú)論采用哪種編碼方式，編碼的長(zhǎng)度總是長(zhǎng)于數(shù)據(jù)的長(zhǎng)度。如果在SSD中采用WOM，以表1的編碼為例，只有2/3的實(shí)際空間被用來(lái)存儲(chǔ)數(shù)據(jù)；每次數(shù)據(jù)傳輸也都需要額外傳輸更多的數(shù)據(jù)。

Fig.2 Micron NAND flash chip internal structure圖2 鎂光NAND閃存芯片內(nèi)部結(jié)構(gòu)圖

3 設(shè)計(jì)與實(shí)現(xiàn)

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

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

為了進(jìn)一步減少所需的可寫位，充分利用寫過(guò)的物理頁(yè)，本文將差值信息進(jìn)行壓縮，然后進(jìn)行編碼，再將編碼寫入到可重寫的頁(yè)中。之后，將可重寫頁(yè)的頁(yè)號(hào)等二次寫的信息保存到原來(lái)物理頁(yè)的額外空間中。

圖3所示為驅(qū)動(dòng)軟件與SSD控制器的交互示意圖。其中，SSD控制器接收驅(qū)動(dòng)發(fā)來(lái)的讀寫請(qǐng)求，再向Flash芯片發(fā)送相應(yīng)命令進(jìn)行讀寫操作。

Fig.3 System structure圖3 系統(tǒng)結(jié)構(gòu)圖

本文提出的方法可以實(shí)現(xiàn)在SSD控制器中，寫入操作的數(shù)據(jù)差值和壓縮過(guò)程都在SSD控制器中實(shí)現(xiàn)；讀取操作的數(shù)據(jù)解壓和還原操作也在SSD控制器中實(shí)現(xiàn)。

3.1 寫操作

寫操作的主要流程如圖4所示，當(dāng)控制器接收到驅(qū)動(dòng)的某個(gè)邏輯頁(yè)的寫請(qǐng)求時(shí)，首先根據(jù)映射表判斷該邏輯頁(yè)是否已經(jīng)有物理頁(yè)與之相對(duì)應(yīng)。

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

Table 2 Example data表2 示例數(shù)據(jù)

3.1.1 獲取差值

在接收到一個(gè)邏輯頁(yè)的更新請(qǐng)求時(shí)，先根據(jù)映射表從SSD中讀出與該邏輯頁(yè)對(duì)應(yīng)的物理頁(yè)的數(shù)據(jù)，然后將新的數(shù)據(jù)和原來(lái)的數(shù)據(jù)進(jìn)行比較，本文采用的是按位異或操作。如果異或的結(jié)果中只有少量的位是1，表明該邏輯頁(yè)的新數(shù)據(jù)和舊數(shù)據(jù)相比變化較小，即更新的數(shù)據(jù)量較小，可以采用保存差值的方法來(lái)保存更新的邏輯頁(yè)。

表2中原數(shù)據(jù)和新數(shù)據(jù)做異或后的結(jié)果轉(zhuǎn)化為十六進(jìn)制為1000000E000000000000C0000000000C。

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

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

3.1.2 差值編碼

差值壓縮后，為了在可重寫頁(yè)上寫入壓縮后的數(shù)據(jù)，需要對(duì)其進(jìn)行編碼。

為了利用頁(yè)面中已有的01或10，可以用01表示0，10表示1。對(duì)于可重寫頁(yè)中無(wú)法利用的01和10，將其填充為11，作為無(wú)效數(shù)據(jù)。

表2中數(shù)據(jù)進(jìn)行壓縮后用上述編碼結(jié)果為01011010 10101010 10010101 10101010 10101010 10101010 01101010 10101010 10101010 0110。

針對(duì)可重寫頁(yè)中可寫位的數(shù)量，可以根據(jù)可寫位的數(shù)量采用相應(yīng)的編碼長(zhǎng)度，例如用3 bit編碼表示2 bit數(shù)據(jù)，用4 bit編碼表示3 bit數(shù)據(jù)。

3.1.3 數(shù)據(jù)寫入

對(duì)于編碼后的數(shù)據(jù)，選取包含足夠數(shù)量的可寫位的可重寫頁(yè)?？砂凑湛芍貙戫?yè)中可寫位的數(shù)量大小對(duì)可重寫頁(yè)進(jìn)行排序，選擇可寫位的數(shù)量與編碼后的數(shù)據(jù)長(zhǎng)度相匹配的可重寫頁(yè)?？芍貙戫?yè)指該頁(yè)面已經(jīng)被無(wú)效掉，但發(fā)現(xiàn)其中還有大量的可寫位，沒(méi)有進(jìn)行擦除操作的頁(yè)。

首先驗(yàn)證可重寫頁(yè)中剩余可寫位的數(shù)量足夠?qū)懭胝?qǐng)求數(shù)據(jù)，然后按3.2節(jié)中編碼方法將數(shù)據(jù)寫入，并將可重寫頁(yè)的索引信息（頁(yè)號(hào)）、編碼方式（可用一個(gè)數(shù)字代表一種編碼）等二次寫信息存入原來(lái)物理頁(yè)的額外空間中。

選擇下述的可重寫頁(yè)來(lái)寫入編碼后的數(shù)據(jù)（不包括額外空間的內(nèi)容）：

寫入編碼后的數(shù)據(jù)后，該可重寫頁(yè)的內(nèi)容變?yōu)椋ɑ疑糠譃楦淖兊腷it）：

3.2 讀操作

數(shù)據(jù)讀取首先根據(jù)映射表從原來(lái)的物理頁(yè)中讀取數(shù)據(jù)（這個(gè)物理頁(yè)并不會(huì)作為廢棄頁(yè)進(jìn)行回收），并從其額外空間中讀取二次寫的信息（可重寫頁(yè)的索引信息和編碼方式），然后根據(jù)二次寫的頁(yè)號(hào)從可重寫頁(yè)中讀取壓縮后的差值數(shù)據(jù)，根據(jù)編碼方式解壓出差值數(shù)據(jù)，然后與舊數(shù)據(jù)進(jìn)行異或操作，恢復(fù)出新的數(shù)據(jù)。

讀操作的流程圖如圖5所示，其中，虛線框中是本文方法對(duì)傳統(tǒng)的SSD控制器所做的補(bǔ)充。

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

4 實(shí)驗(yàn)評(píng)測(cè)

下面對(duì)本文提出的二次寫的方法進(jìn)行評(píng)測(cè)。4.1節(jié)介紹測(cè)試平臺(tái)及評(píng)測(cè)系統(tǒng)；4.2節(jié)介紹差值數(shù)據(jù)和壓縮的測(cè)試；4.3節(jié)介紹可重寫頁(yè)的獲取；4.4節(jié)測(cè)試差值寫入的過(guò)程；4.5節(jié)是對(duì)測(cè)試結(jié)果的分析。

4.1 測(cè)試平臺(tái)及評(píng)測(cè)系統(tǒng)

為了獲取真實(shí)應(yīng)用的數(shù)據(jù)，實(shí)驗(yàn)采用MySQL-tpcc[14]工具加載一個(gè)數(shù)據(jù)庫(kù)，使用其中的一個(gè)大小為3 GB左右的表作為監(jiān)測(cè)對(duì)象，表中大約有3 000萬(wàn)條記錄。然后進(jìn)行數(shù)據(jù)庫(kù)的更新操作，記錄數(shù)據(jù)更新導(dǎo)致的數(shù)據(jù)變化，具體步驟如下：

（1）對(duì)數(shù)據(jù)表進(jìn)行300萬(wàn)（記錄總數(shù)的10%）次更新操作，更新操作每次隨機(jī)選擇一條記錄，然后隨機(jī)選擇6個(gè)非主鍵屬性中的一個(gè)進(jìn)行更新。

（2）對(duì)數(shù)據(jù)表做快照，保存其數(shù)據(jù)。

按照上述步驟循環(huán)幾次，即可得到數(shù)據(jù)表的多個(gè)快照文件。

將不同的快照文件進(jìn)行比較，獲取快照文件之間的差值數(shù)據(jù)。再對(duì)差值數(shù)據(jù)進(jìn)行壓縮，嘗試將壓縮后的差值數(shù)據(jù)寫入到原來(lái)的文件中，從而減少擦除次數(shù)。

4.2 差值數(shù)據(jù)及壓縮測(cè)試

獲取到數(shù)據(jù)表的多個(gè)快照文件后，首先按照頁(yè)面大小為8 KB對(duì)文件進(jìn)行切分；接著比較對(duì)應(yīng)的文件，即將文件進(jìn)行按位異或操作，得到頁(yè)面更新前后的差值數(shù)據(jù)；然后將差值數(shù)據(jù)進(jìn)行壓縮，統(tǒng)計(jì)差值數(shù)據(jù)的壓縮率。

實(shí)驗(yàn)共獲得5個(gè)快照文件，差值數(shù)據(jù)通過(guò)相鄰的快照文件進(jìn)行按位異或操作得到，接著采用zip工具對(duì)差值數(shù)據(jù)進(jìn)行壓縮，發(fā)現(xiàn)絕大部分的差值數(shù)據(jù)的壓縮率能夠達(dá)到90%以上，只有少數(shù)的差值數(shù)據(jù)壓縮率在90%以下。為了表述方便，下文的差值文件指的是包含差值數(shù)據(jù)的文件。

具體的統(tǒng)計(jì)結(jié)果即處于各個(gè)壓縮率的文件數(shù)量所占文件總數(shù)的具體比例，如圖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萬(wàn)次更新后不同壓縮率文件的占比（C代表壓縮率）

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

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

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

因此，壓縮后的差值文件大小低于文件自身大小的10%，可見(jiàn)數(shù)據(jù)庫(kù)類應(yīng)用的更新操作，產(chǎn)生的數(shù)據(jù)變化量非常小，通過(guò)保存更新前后數(shù)據(jù)的差值來(lái)保存更新后的數(shù)據(jù)可以大大減少所需的存儲(chǔ)空間，為本文提出的SSD二次寫的方法提供了可能。

4.3 可重寫頁(yè)的獲取

根據(jù)第一次寫過(guò)的頁(yè)中的可寫位的數(shù)量，判斷該頁(yè)能否用于二次寫，即是否是可重寫頁(yè)。如果可寫位的數(shù)量過(guò)低，則不滿足寫入壓縮文件的需要，無(wú)法用于二次寫。

在本實(shí)驗(yàn)中，切分快照文件產(chǎn)生的頁(yè)面文件都可以視為第一次寫的頁(yè)，本文假定在寫的過(guò)程中，存儲(chǔ)單元只能從1變?yōu)?，不能從0變?yōu)?，則其中為1的位的數(shù)量，即為可寫位的數(shù)量。

分析5個(gè)快照文件中為1的位，得到圖8所示的統(tǒng)計(jì)結(jié)果?？梢钥吹?，對(duì)于每個(gè)快照文件，可寫位的平均數(shù)量都處于27%～28%之間，能夠滿足寫入壓縮后的差值數(shù)據(jù)的要求。

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

事實(shí)上，如果在寫數(shù)據(jù)之前可以提前感知所寫的數(shù)據(jù)中0位的數(shù)量遠(yuǎn)大于1位的數(shù)量，則可以將所寫數(shù)據(jù)按位取反后再進(jìn)行寫入，從而使物理頁(yè)在第一次寫后仍有很大一部分處于可寫狀態(tài)。

在傳統(tǒng)的SSD設(shè)計(jì)中，垃圾回收操作會(huì)在物理頁(yè)無(wú)效以后直接將其擦除，并不會(huì)利用其中的可寫位，本文利用這些可寫位來(lái)實(shí)現(xiàn)SSD的二次寫。

4.4 差值寫入測(cè)試

基于4.2節(jié)和4.3節(jié)所得實(shí)驗(yàn)數(shù)據(jù)，進(jìn)行差值寫入測(cè)試。選取可重寫頁(yè)，嘗試進(jìn)行二次寫入的操作。實(shí)驗(yàn)步驟如下：

（1）任意選擇一個(gè)快照文件切分后產(chǎn)生的頁(yè)面文件作為可重寫頁(yè)；

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

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

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

每次實(shí)驗(yàn)都會(huì)對(duì)差值文件1～4壓縮后的3 GB/8 KB×4=1 570 816個(gè)文件進(jìn)行二次寫測(cè)試。對(duì)于4個(gè)可重寫頁(yè)，二次寫失敗的統(tǒng)計(jì)結(jié)果如圖9所示。

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

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

正如4.3節(jié)中所說(shuō)，如果所寫數(shù)據(jù)中1 bit（可寫位）的數(shù)量較少，可以將數(shù)據(jù)按位取反后寫入。因此，對(duì)于本文方法，可以認(rèn)為所有的寫過(guò)一次的頁(yè)面都可以作為進(jìn)行二次寫的可重寫頁(yè)，且寫入成功的概率為96%。

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

實(shí)驗(yàn)結(jié)果表明，有22.41%的可重寫頁(yè)能夠?qū)懭雰蓚€(gè)壓縮后的差值文件。

對(duì)于壓縮率在95%以上的差值文件，更詳細(xì)的統(tǒng)計(jì)如圖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 測(cè)試結(jié)果分析

4.2節(jié)中差值數(shù)據(jù)的壓縮結(jié)果表明數(shù)據(jù)庫(kù)的更新操作導(dǎo)致的相應(yīng)的文件內(nèi)容的變化十分微小，在這類應(yīng)用中，可以采用本文方法。

無(wú)論哪種應(yīng)用，在其對(duì)SSD進(jìn)行寫入操作后，依然存在大量的可寫位。本文提出的二次寫的方法可以利用傳統(tǒng)SSD設(shè)計(jì)無(wú)法利用的可寫位，在響應(yīng)相同的寫操作的情況下，大大減少SSD的擦除次數(shù)，延長(zhǎng)SSD的使用壽命。

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

表3對(duì)比了本文提出的方法與Reusable SSD[4]（表中簡(jiǎn)稱ReSSD）對(duì)SSD擦除次數(shù)的影響。

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

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

在收到一個(gè)寫邏輯頁(yè)的請(qǐng)求時(shí)，選擇兩個(gè)寫過(guò)一次且被無(wú)效掉的物理頁(yè)，通過(guò)編碼將邏輯頁(yè)的數(shù)據(jù)寫到這兩個(gè)物理頁(yè)和其額外空間（每頁(yè)的額外空間需要寫入5%的數(shù)據(jù)），實(shí)現(xiàn)物理頁(yè)的二次寫。讀取數(shù)據(jù)時(shí)，讀出相應(yīng)的兩個(gè)物理頁(yè)的內(nèi)容，根據(jù)編碼恢復(fù)出原來(lái)的數(shù)據(jù)。

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

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

與Reusable SSD相比，本文提出的方法能夠在一個(gè)可重寫頁(yè)中寫入兩個(gè)壓縮后的差值文件。4.2節(jié)和4.4節(jié)中統(tǒng)計(jì)結(jié)果表明有82%的差值文件壓縮率在95%以上，其中的65%壓縮率在97%以上，即有82%×65%=53.3%的差值文件可以作為要寫入的對(duì)象。而4.4節(jié)的實(shí)驗(yàn)結(jié)果表明對(duì)于壓縮率在97%以上的文件，有22.41%的概率能夠?qū)懭氲娇芍貙戫?yè)中。因此，本文方法有63.3%×22.41%=14.19%的概率可以在一個(gè)可重寫頁(yè)中寫入兩個(gè)差值文件。

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

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

在數(shù)據(jù)寫入的過(guò)程中，本文方法需要先將原來(lái)的數(shù)據(jù)讀出，和新數(shù)據(jù)進(jìn)行異或，然后壓縮，進(jìn)而判斷能否將其寫入無(wú)效頁(yè)中；如果可以，將壓縮后的數(shù)據(jù)進(jìn)行編碼，寫入到無(wú)效的頁(yè)中，保存無(wú)效頁(yè)的物理頁(yè)號(hào)到原來(lái)頁(yè)的額外空間，共需要兩次讀取操作，兩次寫入操作。如果不采用本文方法，只需進(jìn)行一次寫入操作。

因此，本文方法會(huì)對(duì)數(shù)據(jù)讀取和寫入的性能帶來(lái)一定的影響。但是，在實(shí)際應(yīng)用中，對(duì)于邏輯頁(yè)的操作一般是連續(xù)的，可以將本文方法中的讀取操作和寫入操作并行，從而減少本文方法對(duì)讀寫性能帶來(lái)的影響。

需要說(shuō)明的是，本文的測(cè)試集只有3 GB，而目前SSD的容量一般都在256 GB、512 GB，但SSD進(jìn)行讀寫的基本單位都是頁(yè)，本文方法主要對(duì)頁(yè)的讀取和寫入操作進(jìn)行改動(dòng)，實(shí)驗(yàn)數(shù)據(jù)處理也是以頁(yè)作為基本單位。雖然本文的數(shù)據(jù)集對(duì)于SSD的容量而言太小，但是并不會(huì)影響本文實(shí)驗(yàn)結(jié)果的說(shuō)服力。

5 相關(guān)工作

擦除操作會(huì)嚴(yán)重影響SSD的性能，近年來(lái)，有很多工作在研究如何減少擦除操作。

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

一類則是通過(guò)WOM編碼，對(duì)寫過(guò)的物理頁(yè)進(jìn)行重復(fù)利用，從而實(shí)現(xiàn)二次寫，減少擦除次數(shù)。但是，基于WOM編碼的大部分工作都需要多于邏輯頁(yè)的空間來(lái)存儲(chǔ)編碼信息[5,16]，而且編碼的復(fù)雜度較高，還有很高的幾率編碼失敗[17-18]。改進(jìn)的WOM編碼利用頁(yè)的額外空間來(lái)實(shí)現(xiàn)二次寫，編碼實(shí)現(xiàn)比較簡(jiǎn)單，但是仍然有一定的幾率失敗，而且隨著SSD使用時(shí)間的增長(zhǎng)無(wú)法繼續(xù)發(fā)揮作用[4]。

本文方法利用寫過(guò)物理頁(yè)的可寫位，通過(guò)簡(jiǎn)單的編碼實(shí)現(xiàn)二次寫。針對(duì)某些應(yīng)用中數(shù)據(jù)更新量較小的特點(diǎn)，采用保存差值的方法來(lái)保存新數(shù)據(jù)。可以作為FTL的一個(gè)軟件擴(kuò)展，具有良好的移植性。

6 結(jié)論

本文基于壓縮和編碼實(shí)現(xiàn)了一種對(duì)SSD進(jìn)行二次寫的方法，不需要占用大量的額外空間，減少了SSD的擦除次數(shù)，顯著延長(zhǎng)SSD的使用壽命，在實(shí)際應(yīng)用中能發(fā)揮重要的作用。