趙乾瑞 冉全

收稿日期：2023-05-20

基金項(xiàng)目：武漢工程大學(xué)研究生創(chuàng)新基金（CX2021290）

DOI：10.19850/j.cnki.2096-4706.2024.07.018

摘? 要：NAND閃存憑借許多特點(diǎn)讓其在各種應(yīng)用場(chǎng)景中得到廣泛的應(yīng)用，例如手機(jī)、平板電腦等，但是閃存也有兩個(gè)受關(guān)注的特性：使用壽命和數(shù)據(jù)的可靠性。在閃存的使用過(guò)程中，讀干擾對(duì)數(shù)據(jù)準(zhǔn)確性的影響會(huì)隨著時(shí)間的增長(zhǎng)變大，因此，通過(guò)對(duì)讀干擾造成的影響進(jìn)行研究，提出了一種減輕讀干擾的垃圾回收算法FRT-GC，該算法通過(guò)對(duì)每個(gè)閃存塊的使用次數(shù)和使用頻率進(jìn)行統(tǒng)計(jì)計(jì)算，在合適的時(shí)機(jī)啟動(dòng)垃圾回收，最大限度地減輕讀干擾造成的影響。實(shí)驗(yàn)驗(yàn)證該算法在減輕讀干擾方面有很好的效果。

關(guān)鍵詞：NAND閃存；垃圾回收；讀干擾；FRT-GC

中圖分類(lèi)號(hào)：TP333；TP312? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：2096-4706（2024）07-0081-05

A Garbage Collection Algorithm of Reducing Read Disturb

ZHAO Qianrui， RAN Quan

（Wuhan Institute of Technology， Wuhan? 430205， China）

Abstract： NAND flash memory is widely used in various application scenarios due to its many characteristics， such as mobile phones， tablet computers and so on， but flash memory also has two characteristics of concern： service life and data reliability. In the using process of flash memory， the influence of read disturb on data accuracy will increase with time. Therefore， by studying the influence caused by read disturb， a garbage collection algorithm FRT-GC （Frequency and Read Times-Garbage Collection） that can reduce the influence caused by read disturb is proposed. This algorithm starts garbage collection at the right time by counting the usage times and frequency of each flash memory block， and minimizes the influence caused by read disturb. The experiments show that the algorithm has a good effect in reducing read disturb.

Keywords： NAND flash memory; garbage collection; read disturb; FRT-GC

0? 引? 言

閃存讀干擾產(chǎn)生的原因是存儲(chǔ)單元之間電荷的相互干擾，這導(dǎo)致讀取到的數(shù)據(jù)發(fā)生錯(cuò)誤，具體有兩個(gè)主要原因：一是存儲(chǔ)單元之間的距離非常相近，電荷可能會(huì)在相鄰的單元之間泄露，從而導(dǎo)致讀干擾；二是高速寫(xiě)入和擦除操作可能會(huì)引起存儲(chǔ)單元之間的電荷遷移，產(chǎn)生讀干擾。這種讀干擾是不可避免的，詳細(xì)原因解釋如下。

如圖1所示，當(dāng)讀取某個(gè)page時(shí)，需要對(duì)所有的WL的ControlGate上都施加一個(gè)Vpass電壓，Vpass電壓一般都大于其閾值電壓Vth，保證所有的單元都可以導(dǎo)通。而對(duì)于要讀取的page，需要在其ControlGate上施加一個(gè)讀取電壓Vread（或者叫參考電壓Vref），然后通過(guò)BL上的電流檢測(cè)來(lái)判斷單元內(nèi)的狀態(tài)。為了保證所有的單元都導(dǎo)通，所以Vpass電壓是比較大的，通過(guò)圖1（b）可以看出，此時(shí)不被讀取的頁(yè)面狀態(tài)有點(diǎn)像寫(xiě)數(shù)據(jù)時(shí)的狀態(tài)，有的單元中電子會(huì)被吸入浮柵中，久而久之，浮柵中的電子越來(lái)越多，數(shù)據(jù)被讀取時(shí)就會(huì)發(fā)生錯(cuò)誤。

根據(jù)讀干擾產(chǎn)生的原因，各個(gè)學(xué)者研究出了以下優(yōu)化方案。

許毅等人提出了一種針對(duì)MLC存儲(chǔ)介質(zhì)的緩解讀干擾的方案[1]，該方法將每個(gè)存儲(chǔ)單元的字線(xiàn)Wordline分為最低有效位（LSB）和最高有效位（MSB），并根據(jù)每個(gè)Wordline的編程程度設(shè)置三種狀態(tài)，根據(jù)不同的狀態(tài)設(shè)置不同的旁路電壓。該方法有效地降低了讀干擾的影響，間接增加了閃存設(shè)備的壽命，但是適用場(chǎng)景過(guò)于單一。

Jung等人通過(guò)實(shí)驗(yàn)分析得出，當(dāng)相應(yīng)的塊被物理擦除，讀干擾可以被糾正，因此他們提出將產(chǎn)生干擾的塊擦除并遷移來(lái)消除讀干擾產(chǎn)生的影響[2]。雖然通過(guò)實(shí)驗(yàn)得知該方法在減少讀干擾產(chǎn)生的錯(cuò)誤率方面有所提升，但是擦除遷移會(huì)導(dǎo)致長(zhǎng)時(shí)間的延遲，進(jìn)而影響性能。

Huang等人提出了感知讀干擾的寫(xiě)調(diào)度和數(shù)據(jù)重新分配算法[3]，該算法通過(guò)參考?jí)K的P/E周期和對(duì)塊的累計(jì)讀取計(jì)數(shù)的因素來(lái)估計(jì)由讀干擾引起的塊讀取錯(cuò)誤率，再分析哪些數(shù)據(jù)的讀取頻繁，將頻繁的數(shù)據(jù)放入讀干擾錯(cuò)誤率低的區(qū)域，不頻繁的數(shù)據(jù)放入讀干擾錯(cuò)誤率較高的區(qū)域。該算法一定程度上優(yōu)化了讀干擾問(wèn)題，但是通過(guò)構(gòu)建模型分析塊的錯(cuò)誤率，具有一定的隨機(jī)性，不太穩(wěn)定。

Wu等人提出了具有原位重新編程的自適應(yīng)單元位密度的閃存讀干擾管理方案[4]，該方案通過(guò)識(shí)別熱數(shù)據(jù)，并將熱數(shù)據(jù)遷移到低密度塊中，從而減少讀取刷新的需要。為了減少用于讀取刷新的數(shù)據(jù)遷移量，設(shè)計(jì)了就地重新編程算法。該方案減少了讀干擾的影響，但是就地重新編程的算法會(huì)導(dǎo)致額外的磨損，間接影響了閃存的壽命。

1? 減輕讀干擾的垃圾回收算法

1.1? 設(shè)計(jì)思路

讀干擾產(chǎn)生的原因無(wú)非是閾值電壓的改變導(dǎo)致讀取錯(cuò)誤，但是當(dāng)重新對(duì)塊進(jìn)行擦除操作后，這種錯(cuò)誤就會(huì)消失，但是在擦除操作之前，塊中的有效頁(yè)需要進(jìn)行遷移，因此想要減輕讀干擾有兩個(gè)步驟：

1）將目標(biāo)塊中的有效頁(yè)面進(jìn)行遷移。

2）對(duì)目標(biāo)塊進(jìn)行擦除操作，以消除累計(jì)的讀計(jì)數(shù)。

上面的兩步操作，等同于一次垃圾回收操作。換句話(huà)說(shuō)，當(dāng)目標(biāo)塊的讀計(jì)數(shù)達(dá)到指定的閾值，那么就可以對(duì)該塊進(jìn)行垃圾回收。

對(duì)于垃圾回收的啟動(dòng)時(shí)機(jī)，由于閃存的擦除次數(shù)越多氧化層絕緣性就越差，讀干擾的現(xiàn)象就會(huì)越嚴(yán)重，因此FRT-GC（Frequency and Read Times-Garbage Collection）算法需要設(shè)定指定的閾值，當(dāng)大于指定閾值時(shí)啟動(dòng)垃圾回收，這樣可以很好地考慮到每個(gè)塊的磨損情況。

對(duì)于垃圾回收過(guò)程中回收塊的選擇，需要在FRT-GC算法中設(shè)計(jì)方法來(lái)獲取每個(gè)塊的訪(fǎng)問(wèn)熱度，根據(jù)熱度判斷每個(gè)塊的讀取頻率，以此獲得受讀干擾的影響程度，據(jù)此進(jìn)行回收塊的選擇。

1.2? 詳細(xì)設(shè)計(jì)

1.2.1? 算法啟動(dòng)策略

總結(jié)前文算法的缺點(diǎn)，本章中的垃圾回收算法FRT-GC的啟動(dòng)時(shí)機(jī)，也就是讀干擾產(chǎn)生的影響的臨界時(shí)間，根據(jù)讀取次數(shù)和讀取頻率兩個(gè)方面進(jìn)行判別，從而決定何時(shí)啟動(dòng)垃圾回收。

如圖2所示，F(xiàn)RT-GC算法在進(jìn)行一次讀取操作后就進(jìn)行判斷，判斷總讀取次數(shù)（Total Read Times， TRT）是否大于指定閾值，如果沒(méi)有，則將被讀取塊的讀取次數(shù)（Block Read Times， BRT）和頻率（Block Read Frequence， BRF）進(jìn)行自增。如果大于指定閾值，則根據(jù)下文的規(guī)則選取回收塊，進(jìn)行一次垃圾回收，并將回收塊的BRT和TRT進(jìn)行歸0操作。

1.2.2? 算法回收塊的選擇

FRT-GC算法中回收塊的選擇主要考慮BRF和BRT兩個(gè)方面。如果一個(gè)塊的BRF高，則說(shuō)明該塊之后被讀的次數(shù)會(huì)很多，那么之后產(chǎn)生的讀干擾也會(huì)非常嚴(yán)重，需要進(jìn)行預(yù)防，所以可以選擇該塊進(jìn)行回收，繼而消除讀干擾的影響；如果一個(gè)塊的BRT高，說(shuō)明該塊之前被讀了很多次，所以之后如果再去讀，極有可能會(huì)發(fā)生數(shù)據(jù)錯(cuò)誤，所以也可以選擇該塊進(jìn)行回收。

該步驟通過(guò)在映射表中添加統(tǒng)計(jì)項(xiàng)來(lái)實(shí)現(xiàn)。在映射表中添加讀取次數(shù)和被讀取的時(shí)間，通過(guò)記錄最近5次被讀取的時(shí)間計(jì)算被讀取的頻率。由于擦除是以塊為單位，所以需要計(jì)算平均BRF，如式（1）所示：

（1）

其中VC為有效頁(yè)的數(shù)量（Vaild Count），PRF為有效頁(yè)的讀取頻率（Page Read Frequence）。

通過(guò)算式再次計(jì)算閃存設(shè)備的平均讀取頻率，如式（2）所示：

（2）

其中TVC為總的有效頁(yè)的數(shù)量（Total Vaild Count），F(xiàn)RF為閃存讀頻率（Flash Read Frequence）。計(jì)算出各個(gè)塊的平均讀頻率和閃存的平均讀頻率，可以得出每個(gè)塊的平均讀取頻率在閃存中的占比。式（3）為回收塊的選擇方式：

（3）

其中CF為回收因子（Collection Factor），通過(guò)判斷每個(gè)塊的回收因子的值來(lái)決定是否進(jìn)行回收，選擇CF值大的進(jìn)行回收。FRT為閃存讀次數(shù)（Flash Read Times）。

通過(guò)算式可以得出，如果一個(gè)塊的CF大，那么可能是BRT大，也可能是AvgBRF大，還有可能為兩者都大，具體情況有：

1）如果是BRT大，代表其被讀次數(shù)多，說(shuō)明其在之前已經(jīng)被讀了很多次，這就代表如果再讀，讀出來(lái)的數(shù)據(jù)很有可能發(fā)生錯(cuò)誤，此時(shí)就需要垃圾回收進(jìn)行有效頁(yè)的遷移和無(wú)效頁(yè)的擦除，如圖3所示，如果在t時(shí)刻需要執(zhí)行垃圾回收，此時(shí)塊A和塊B的讀次數(shù)相同，但是在之前塊A的讀次數(shù)明顯多余塊B，所以選擇塊A作為回收塊。

2）如果是AvgBRF大，則代表其最近的訪(fǎng)問(wèn)頻率有所上升，根據(jù)數(shù)據(jù)訪(fǎng)問(wèn)的時(shí)間局部性來(lái)看，其之后有極大的可能被頻繁訪(fǎng)問(wèn)，因此之后該塊內(nèi)的數(shù)據(jù)在被讀取時(shí)，也很有可能發(fā)生錯(cuò)誤，如圖4所示，t時(shí)刻之前，雖然塊A的讀取次數(shù)多，但是最近幾次塊B的讀取更為頻繁，且之后還會(huì)被頻繁訪(fǎng)問(wèn)，可能會(huì)對(duì)數(shù)據(jù)的讀取產(chǎn)生影響，因此選擇塊B做回收塊。

圖4? AvgBRF影響較大示意圖

3）如果BRT和AvgBRF都比較大，那么說(shuō)明其之前被讀次數(shù)很高，之后也將會(huì)被頻繁讀取，這樣如果之后再被讀取，那么被讀干擾影響，讀取錯(cuò)誤數(shù)據(jù)的概率也非常高。

2? 實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)選用FlashSim [5]作為垃圾回收算法的測(cè)試平臺(tái)，由于FlashSim是裝在DiskSim下的，所以需要先安裝DiskSim。FlashSim的核心部分包括模擬器、文件系統(tǒng)驅(qū)動(dòng)和用戶(hù)空間工具，模擬器是FlashSim的核心，它提供了對(duì)讀、寫(xiě)、擦除等操作的模擬，并且文件系統(tǒng)驅(qū)動(dòng)提供了對(duì)各種文件系統(tǒng)的支持，包括ext4 [6]、FAT32 [7]、YaFFS [8]等。

2.1? 實(shí)驗(yàn)實(shí)現(xiàn)方式說(shuō)明

安裝DiskSim后，DiskSim中文件如圖5所示，其中，src文件夾中存放的是可執(zhí)行文件，如圖6所示，test.release文件為數(shù)據(jù)集文件，其余則為編譯和配置文件。將FlashSim下載好后，更名為src覆蓋原有的src文件。

在Disksim-3.0文件中的Parfile文件，用來(lái)設(shè)置仿真的閃存設(shè)備的參數(shù)：FTL算法、Block數(shù)量、SSD接口、總線(xiàn)、控制器參數(shù)，等等。

在FlashSim中實(shí)現(xiàn)自己的映射算法方式：DiskSim-3.0/src文件夾下的.c文件中為FTL算法的具體實(shí)現(xiàn)方式，.h文件為FTL算法所聲明的函數(shù)庫(kù)的頭文件，這些頭文件在disksim_iodriver.c，ssd_interface，c，disksim_main.c和disksim_simpleflash.c中以選擇的形式，供disksim執(zhí)行模擬仿真。

在執(zhí)行文件runvalid中可以輸入多條命令，如圖7所示。運(yùn)行命令./runvalid，運(yùn)行結(jié)果如圖8所示。運(yùn)行結(jié)果新增文件如圖9所示。

在測(cè)試結(jié)束后，會(huì)生成.outv文件，該文件是測(cè)試數(shù)據(jù)結(jié)果文件，通過(guò)在結(jié)果文件中尋找想要的數(shù)據(jù)，并通過(guò)Excel來(lái)進(jìn)行所需圖表的生成。

2.2? 參數(shù)配置

NAND閃存參數(shù)配置如表1所示。

2.3? 性能比較

本實(shí)驗(yàn)對(duì)比的算法為傳統(tǒng)讀干擾算法Refresh [9]，與RDD [10]算法，Referesh算法是通過(guò)固定閾值來(lái)進(jìn)行數(shù)據(jù)遷移來(lái)以免有效數(shù)據(jù)受到讀干擾的影響。RDD算法在Refresh的基礎(chǔ)上，通過(guò)實(shí)時(shí)檢測(cè)來(lái)判斷數(shù)據(jù)的干擾情況，從而減輕讀干擾的影響。

本實(shí)驗(yàn)通過(guò)以下幾個(gè)方面進(jìn)行FRT-GC算法與其他算法的性能評(píng)測(cè)：

1）平均響應(yīng)時(shí)間。平均響應(yīng)時(shí)間是指從上層文件系統(tǒng)發(fā)送請(qǐng)求到返回結(jié)果的平均時(shí)間，該標(biāo)準(zhǔn)可以直觀(guān)判斷算法對(duì)閃存效率的影響。

2）數(shù)據(jù)錯(cuò)誤率。數(shù)據(jù)錯(cuò)誤率主要是通過(guò)判斷讀取出錯(cuò)數(shù)據(jù)的比特占總數(shù)據(jù)的比例。該標(biāo)準(zhǔn)可以判斷出算法對(duì)減輕讀干擾的效果情況，可以直觀(guān)的反應(yīng)算法的可靠性。

3）數(shù)據(jù)遷移量。在減輕讀干擾的過(guò)程中，需要對(duì)有效數(shù)據(jù)進(jìn)行數(shù)據(jù)遷移，而對(duì)數(shù)據(jù)讀干擾的情況判斷極大的影響這數(shù)據(jù)遷移量，所以該標(biāo)準(zhǔn)可以反映算法的性能情況。

2.3.1? 平均響應(yīng)時(shí)間

圖10為實(shí)驗(yàn)結(jié)果，為了使數(shù)據(jù)便于觀(guān)察，此處將數(shù)據(jù)使用最大最小歸一化方式進(jìn)行了處理，使所有數(shù)據(jù)都趨于區(qū)間0和1之間，從圖中可以看出，Refresh算法的響應(yīng)時(shí)間較長(zhǎng)，主要是因?yàn)槠渫ㄟ^(guò)固定閾值去判斷干擾情況，判斷方式過(guò)于固定和單一，因此會(huì)導(dǎo)致很多不必要的數(shù)據(jù)遷移。通過(guò)實(shí)驗(yàn)可知FRT-GC算法對(duì)比Refresh算法和RDD算法時(shí)，分別提升了6.1%和0.7%，所以可以看出FRT-GC算法在平均響應(yīng)時(shí)間方面優(yōu)于其余兩個(gè)算法。

2.3.2? 數(shù)據(jù)錯(cuò)誤率

如圖11所示，該數(shù)據(jù)也進(jìn)行了歸一化處理，F(xiàn)RT-GC算法在數(shù)據(jù)錯(cuò)誤率方面優(yōu)于其他算法。相比Refresh和RDD算法，錯(cuò)誤率降低了7%和0.7%，主要是因?yàn)镕RT-GC算法在進(jìn)行垃圾回收的過(guò)程中，在回收塊的選擇方面，選擇之前受讀干擾影響較大或之后會(huì)受讀干擾影響的塊，所以在錯(cuò)誤率方面低于其他兩個(gè)算法。

2.3.3? 數(shù)據(jù)遷移量

如圖12所示，通過(guò)實(shí)驗(yàn)可以看出FRT-GC在數(shù)據(jù)遷移量方面優(yōu)于Refresh算法和RDD算法。相比其他兩個(gè)算法，F(xiàn)RT-GC算法在數(shù)據(jù)遷移量方面減少了54.7%和17.7%，主要是因?yàn)閮蓚€(gè)算法通過(guò)固定閾值和固定間隔去進(jìn)行數(shù)據(jù)遷移，導(dǎo)致一些未受讀干擾影響的數(shù)據(jù)被遷移，產(chǎn)生不必要的遷移操作。

3? 結(jié)? 論

本文提出了一種減輕讀干擾的垃圾回收算法FRT-GC，該算法通過(guò)計(jì)算每個(gè)頁(yè)的讀頻率和讀次數(shù)，通過(guò)近幾次的讀頻率可以看出該頁(yè)最近將要被訪(fǎng)問(wèn)的概率，通過(guò)讀次數(shù)可以判斷該頁(yè)之前被讀的次數(shù)，通過(guò)這兩項(xiàng)來(lái)判斷周?chē)?yè)的讀干擾情況來(lái)進(jìn)行垃圾回收。該算法在減輕讀干擾影響以及提高閃存性能方面都有著不錯(cuò)的性能。

參考文獻(xiàn)：

[1] 許毅，姚蘭，鄭春陽(yáng).一種緩解MLC閃存讀干擾問(wèn)題的方法：201711225482.0 [P].2017-11-29.

[2] JUNG M，KANDEMIR M. Revisiting Widely Held SSD Expectations and Rethinking System-level Implications [C]//Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems.Pittsburgh：ACM，2013：203-216.

[3] HUANG B W，LIAO J W，LI J，et al. Read Disturb-aware Write Scheduling and Data Reallocation in SSDs [J].IEICE Electronics Express，2020，17（8）：20200015.

[4] WU T C，MA Y P，CHANG L P. Flash Read Disturb Management Using Adaptive Cell Bit-density with In-place Reprogramming [C]//2018 Design， Automation & Test in Europe Conference & Exhibition（DATE）.Dresden：IEEE，2018：325-330.

[5] KIM Y，TAURAS B，GUPTA A，et al. Flashsim： A Simulator for NAND Flash-based Solid-state Drives [C]//2009 First International Conference on Advances in System Simulation.Porto：IEEE，2009：125-131.

[6] MATHUR A，CAO M M，BHATTACHARYA S，et al. The New Ext4 Filesystem： Current Status and Future Plans [C]//Proceedings of the Linux symposium.Ottawa：[S.I]，2007，2：21-33.

[7] BHAT W A，QUADRI S M K. Review of FAT Data Structure of FAT32 file system [J].Oriental Journal of Computer Science & Technology，2010，3（1）：161-164.

[8] MANNING C. How Yaffs Works [EB/OL].（2012-06-02）.https：//yaffs.net/documents/how-yaffs-works.

[9] FROST H H，CAMP C J，F(xiàn)ISHER T J，et al. Efficient reduction of Read Disturb Errors in NAND FLASH Memory：US12879966 [P].2010-09-10.

[10] 翁陽(yáng).固態(tài)盤(pán)內(nèi)讀干擾感知的智能管理優(yōu)化方法研究 [D].武漢：華中科技大學(xué)，2020.

作者簡(jiǎn)介：趙乾瑞（1998—），男，漢族，山西運(yùn)城人，碩士在讀，研究方向：嵌入式、存儲(chǔ)性能、閃存數(shù)據(jù)庫(kù)。