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

趙乾瑞 冉全

收稿日期：2023-05-20

基金項目：武漢工程大學研究生創新基金（CX2021290）

DOI：10.19850/j.cnki.2096-4706.2024.07.018

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

關鍵詞：NAND閃存；垃圾回收；讀干擾；FRT-GC

中圖分類號：TP333；TP312? 文獻標識碼：A? 文章編號：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? 引? 言

閃存讀干擾產生的原因是存儲單元之間電荷的相互干擾，這導致讀取到的數據發生錯誤，具體有兩個主要原因：一是存儲單元之間的距離非常相近，電荷可能會在相鄰的單元之間泄露，從而導致讀干擾；二是高速寫入和擦除操作可能會引起存儲單元之間的電荷遷移，產生讀干擾。這種讀干擾是不可避免的，詳細原因解釋如下。

如圖1所示，當讀取某個page時，需要對所有的WL的ControlGate上都施加一個Vpass電壓，Vpass電壓一般都大于其閾值電壓Vth，保證所有的單元都可以導通。而對于要讀取的page，需要在其ControlGate上施加一個讀取電壓Vread（或者叫參考電壓Vref），然后通過BL上的電流檢測來判斷單元內的狀態。為了保證所有的單元都導通，所以Vpass電壓是比較大的，通過圖1（b）可以看出，此時不被讀取的頁面狀態有點像寫數據時的狀態，有的單元中電子會被吸入浮柵中，久而久之，浮柵中的電子越來越多，數據被讀取時就會發生錯誤。

根據讀干擾產生的原因，各個學者研究出了以下優化方案。

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

Jung等人通過實驗分析得出，當相應的塊被物理擦除，讀干擾可以被糾正，因此他們提出將產生干擾的塊擦除并遷移來消除讀干擾產生的影響[2]。雖然通過實驗得知該方法在減少讀干擾產生的錯誤率方面有所提升，但是擦除遷移會導致長時間的延遲，進而影響性能。

Huang等人提出了感知讀干擾的寫調度和數據重新分配算法[3]，該算法通過參考塊的P/E周期和對塊的累計讀取計數的因素來估計由讀干擾引起的塊讀取錯誤率，再分析哪些數據的讀取頻繁，將頻繁的數據放入讀干擾錯誤率低的區域，不頻繁的數據放入讀干擾錯誤率較高的區域。該算法一定程度上優化了讀干擾問題，但是通過構建模型分析塊的錯誤率，具有一定的隨機性，不太穩定。

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

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

1.1? 設計思路

讀干擾產生的原因無非是閾值電壓的改變導致讀取錯誤，但是當重新對塊進行擦除操作后，這種錯誤就會消失，但是在擦除操作之前，塊中的有效頁需要進行遷移，因此想要減輕讀干擾有兩個步驟：

1）將目標塊中的有效頁面進行遷移。

2）對目標塊進行擦除操作，以消除累計的讀計數。

上面的兩步操作，等同于一次垃圾回收操作。換句話說，當目標塊的讀計數達到指定的閾值，那么就可以對該塊進行垃圾回收。

對于垃圾回收的啟動時機，由于閃存的擦除次數越多氧化層絕緣性就越差，讀干擾的現象就會越嚴重，因此FRT-GC（Frequency and Read Times-Garbage Collection）算法需要設定指定的閾值，當大于指定閾值時啟動垃圾回收，這樣可以很好地考慮到每個塊的磨損情況。

對于垃圾回收過程中回收塊的選擇，需要在FRT-GC算法中設計方法來獲取每個塊的訪問熱度，根據熱度判斷每個塊的讀取頻率，以此獲得受讀干擾的影響程度，據此進行回收塊的選擇。

1.2? 詳細設計

1.2.1? 算法啟動策略

總結前文算法的缺點，本章中的垃圾回收算法FRT-GC的啟動時機，也就是讀干擾產生的影響的臨界時間，根據讀取次數和讀取頻率兩個方面進行判別，從而決定何時啟動垃圾回收。

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

1.2.2? 算法回收塊的選擇

FRT-GC算法中回收塊的選擇主要考慮BRF和BRT兩個方面。如果一個塊的BRF高，則說明該塊之后被讀的次數會很多，那么之后產生的讀干擾也會非常嚴重，需要進行預防，所以可以選擇該塊進行回收，繼而消除讀干擾的影響；如果一個塊的BRT高，說明該塊之前被讀了很多次，所以之后如果再去讀，極有可能會發生數據錯誤，所以也可以選擇該塊進行回收。

該步驟通過在映射表中添加統計項來實現。在映射表中添加讀取次數和被讀取的時間，通過記錄最近5次被讀取的時間計算被讀取的頻率。由于擦除是以塊為單位，所以需要計算平均BRF，如式（1）所示：

（1）

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

通過算式再次計算閃存設備的平均讀取頻率，如式（2）所示：

（2）

其中TVC為總的有效頁的數量（Total Vaild Count），FRF為閃存讀頻率（Flash Read Frequence）。計算出各個塊的平均讀頻率和閃存的平均讀頻率，可以得出每個塊的平均讀取頻率在閃存中的占比。式（3）為回收塊的選擇方式：

（3）

其中CF為回收因子（Collection Factor），通過判斷每個塊的回收因子的值來決定是否進行回收，選擇CF值大的進行回收。FRT為閃存讀次數（Flash Read Times）。

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

1）如果是BRT大，代表其被讀次數多，說明其在之前已經被讀了很多次，這就代表如果再讀，讀出來的數據很有可能發生錯誤，此時就需要垃圾回收進行有效頁的遷移和無效頁的擦除，如圖3所示，如果在t時刻需要執行垃圾回收，此時塊A和塊B的讀次數相同，但是在之前塊A的讀次數明顯多余塊B，所以選擇塊A作為回收塊。

2）如果是AvgBRF大，則代表其最近的訪問頻率有所上升，根據數據訪問的時間局部性來看，其之后有極大的可能被頻繁訪問，因此之后該塊內的數據在被讀取時，也很有可能發生錯誤，如圖4所示，t時刻之前，雖然塊A的讀取次數多，但是最近幾次塊B的讀取更為頻繁，且之后還會被頻繁訪問，可能會對數據的讀取產生影響，因此選擇塊B做回收塊。

圖4? AvgBRF影響較大示意圖

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

2? 實驗結果分析

本實驗選用FlashSim [5]作為垃圾回收算法的測試平臺，由于FlashSim是裝在DiskSim下的，所以需要先安裝DiskSim。FlashSim的核心部分包括模擬器、文件系統驅動和用戶空間工具，模擬器是FlashSim的核心，它提供了對讀、寫、擦除等操作的模擬，并且文件系統驅動提供了對各種文件系統的支持，包括ext4 [6]、FAT32 [7]、YaFFS [8]等。

2.1? 實驗實現方式說明

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

在Disksim-3.0文件中的Parfile文件，用來設置仿真的閃存設備的參數：FTL算法、Block數量、SSD接口、總線、控制器參數，等等。

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

在執行文件runvalid中可以輸入多條命令，如圖7所示。運行命令./runvalid，運行結果如圖8所示。運行結果新增文件如圖9所示。

在測試結束后，會生成.outv文件，該文件是測試數據結果文件，通過在結果文件中尋找想要的數據，并通過Excel來進行所需圖表的生成。

2.2? 參數配置

NAND閃存參數配置如表1所示。

2.3? 性能比較

本實驗對比的算法為傳統讀干擾算法Refresh [9]，與RDD [10]算法，Referesh算法是通過固定閾值來進行數據遷移來以免有效數據受到讀干擾的影響。RDD算法在Refresh的基礎上，通過實時檢測來判斷數據的干擾情況，從而減輕讀干擾的影響。

本實驗通過以下幾個方面進行FRT-GC算法與其他算法的性能評測：

1）平均響應時間。平均響應時間是指從上層文件系統發送請求到返回結果的平均時間，該標準可以直觀判斷算法對閃存效率的影響。

2）數據錯誤率。數據錯誤率主要是通過判斷讀取出錯數據的比特占總數據的比例。該標準可以判斷出算法對減輕讀干擾的效果情況，可以直觀的反應算法的可靠性。

3）數據遷移量。在減輕讀干擾的過程中，需要對有效數據進行數據遷移，而對數據讀干擾的情況判斷極大的影響這數據遷移量，所以該標準可以反映算法的性能情況。

2.3.1? 平均響應時間

圖10為實驗結果，為了使數據便于觀察，此處將數據使用最大最小歸一化方式進行了處理，使所有數據都趨于區間0和1之間，從圖中可以看出，Refresh算法的響應時間較長，主要是因為其通過固定閾值去判斷干擾情況，判斷方式過于固定和單一，因此會導致很多不必要的數據遷移。通過實驗可知FRT-GC算法對比Refresh算法和RDD算法時，分別提升了6.1%和0.7%，所以可以看出FRT-GC算法在平均響應時間方面優于其余兩個算法。

2.3.2? 數據錯誤率

如圖11所示，該數據也進行了歸一化處理，FRT-GC算法在數據錯誤率方面優于其他算法。相比Refresh和RDD算法，錯誤率降低了7%和0.7%，主要是因為FRT-GC算法在進行垃圾回收的過程中，在回收塊的選擇方面，選擇之前受讀干擾影響較大或之后會受讀干擾影響的塊，所以在錯誤率方面低于其他兩個算法。

2.3.3? 數據遷移量

如圖12所示，通過實驗可以看出FRT-GC在數據遷移量方面優于Refresh算法和RDD算法。相比其他兩個算法，FRT-GC算法在數據遷移量方面減少了54.7%和17.7%，主要是因為兩個算法通過固定閾值和固定間隔去進行數據遷移，導致一些未受讀干擾影響的數據被遷移，產生不必要的遷移操作。

3? 結? 論

本文提出了一種減輕讀干擾的垃圾回收算法FRT-GC，該算法通過計算每個頁的讀頻率和讀次數，通過近幾次的讀頻率可以看出該頁最近將要被訪問的概率，通過讀次數可以判斷該頁之前被讀的次數，通過這兩項來判斷周圍頁的讀干擾情況來進行垃圾回收。該算法在減輕讀干擾影響以及提高閃存性能方面都有著不錯的性能。

參考文獻：

[1] 許毅，姚蘭，鄭春陽.一種緩解MLC閃存讀干擾問題的方法：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，FISHER T J，et al. Efficient reduction of Read Disturb Errors in NAND FLASH Memory：US12879966 [P].2010-09-10.

[10] 翁陽.固態盤內讀干擾感知的智能管理優化方法研究 [D].武漢：華中科技大學，2020.

作者簡介：趙乾瑞（1998—），男，漢族，山西運城人，碩士在讀，研究方向：嵌入式、存儲性能、閃存數據庫。