把大象關(guān)冰箱的步驟 --- NAND FLASH控制器磨損管理算法芯片化硬實(shí)現(xiàn)

目前，存儲領(lǐng)域包括eMMC，SATA SSD ,PCIe SSD等控制器是一個非常熱門的領(lǐng)域。通常，由于NAND FLASH易于損壞的特性，因此需要控制器做額外的工作，才能滿足商用可靠存儲的需要。

存儲控制器的所做的額外工作就是均衡磨損、壞塊管理、以及邏輯地址到物理地址映射的管理。通常在存儲控制器中需要集成CPU運(yùn)行并運(yùn)行相應(yīng)的軟件才能完成上述的功能，而隨著存儲性能的增加，則需要更高性能的CPU或者多核處理器以及高速的處理算法。

本文目的提出一種可以硬實(shí)現(xiàn)的均衡磨損，壞塊管理，以及邏輯地址映射的算法，(可芯片化)。用于替代處理器的軟件(FTL)實(shí)現(xiàn)，從總體上較CPU固件實(shí)現(xiàn)有較好的功耗比和高速性能的目標(biāo)。

首先說明: NAND FLASH的管理說明：

1：NAND FLASH 只能按頁寫，且只能寫干凈的頁。(一個頁一旦寫過就不能寫第二次，除非被擦除)

2：NAND FLASH 能按頁讀，這個可以讀多次。

3：NAND FLASH 只能按塊擦。(一個塊包含多個頁)。

4：NAND FLASH的出錯一般出現(xiàn)在寫，和擦除時，如果NAND FLSAH的塊在寫或者擦除時，出錯，則就不能再使用，內(nèi)部內(nèi)容需讀出寫入其他的位置。

5：如果NAND FLASH的管理中，如果重新改寫同一地址，則原地址內(nèi)容作廢，邏輯映射一個新地址寫入(原因見規(guī)則1)。

1：基本操作：讀，寫;

那么如何設(shè)計相應(yīng)的硬實(shí)現(xiàn)算法：首先是考慮寫操作，每次寫都要寫一個干凈的地址。因此我們假設(shè)有一個模塊，每次吐出一個新的干凈頁地址，那么每次寫操作時，都申請從此模塊申請一個新地址。

寫NAND FLASH的步驟：(把大象關(guān)冰箱里的步驟)。

0：主機(jī)寫入一個邏輯地址(LA logic address)中一個page的數(shù)據(jù)(PD pagedata)。

1：從地址分配器(FIFO)中申請一個干凈頁地址(PA physical address)，然后寫到新的頁地址中。(這個步驟前少一步，)

2：記錄邏輯地址和物理地址的對應(yīng)關(guān)系。(LA->PA)到映射表。這樣完成寫的流程。

下次讀的時候，

0：主機(jī)讀取一個邏輯地址(LA logic address)。

1：查找映射表，對應(yīng)的映射表LA->PA，則讀取PA的頁數(shù)據(jù)(PD)。返回主機(jī)。這樣就完成了讀的流程。

這樣考慮就是想法簡單了，上圖是正常的寫流程。

由于寫FLASH的步驟，首先要確定原有邏輯地址在映射表里是否存在，映射表相應(yīng)的表項刪除(刪除的表項會重新擦除使用，否則很快就會寫完)。

寫NAND FLASH的步驟：

0：主機(jī)寫入一個邏輯地址(LA logic address)中一個page的數(shù)據(jù)(PD pagedata)。

1：查看頁地址中是否有相關(guān)的邏輯地址表項，如果有，則刪除表項，否則直接到下一步。

2：從地址分配器(FIFO)中申請一個干凈頁地址(PA physical address)，

3：記錄邏輯地址和物理地址的對應(yīng)關(guān)系。(LA->PA)到映射表。

4：然后寫到新的頁地址中。

讀NAND FLASH的步驟：

0：主機(jī)從一個邏輯地址(LA logic address)中一個page的數(shù)據(jù)(PD pagedata)。

1：在映射標(biāo)的表項中，查找LAn的表項。

2：查找對應(yīng)的物理地址(PAm)。

3：從PAm讀出PD并返回主機(jī)。

2：擦除：擦除

從上述的機(jī)制來看，每次寫操作時，都會占用一個PAGE，而假設(shè)原有的邏輯地址內(nèi)部存儲數(shù)據(jù)，則原有的邏輯地址對應(yīng)的物理地址則被廢棄，因此需要將這些物理地址重新擦除后重新使用。(否則FLASH寫完一遍后，再也不能再寫)。

另一問題，page按頁來寫，而擦除按照塊來擦除，假設(shè)每個塊有512個page。

按照上述機(jī)制，每個塊都有512個page放入申請單元中，而這些page寫操作時，被依次申請，也就是說，BLOCK中每個page都會被寫滿，當(dāng)這些物理page被重新寫時，則原有的page變成臟頁，可以被擦除。但是前提是512個page的都湊齊。那擦除的情況分為兩種，

情況1：一個塊(block)中，所有的page都被寫變成dirty后，可以擦除，放入地址分配器中。

情況2：地址分配器中剩余地址少于一定數(shù)量，則就考慮將那些仍然還有數(shù)據(jù)頁部分有效的塊(block)擦除，再進(jìn)行分配。前提是，將數(shù)據(jù)頁先讀出換個地方存儲。

對于情況1，可以類似數(shù)通領(lǐng)域的組片，每個被重復(fù)寫的邏輯地址，就釋放一個物理地址，收齊一個塊中所有的物理地址(都被寫過后，釋放掉)，就可以重新擦除后，重新放置在地址分配器中。

對應(yīng)情況1來說：其觸發(fā)條件新的寫入page，原有page被回收后，放入地址回收器中：

因此擦除的步驟可以分為：

1：獲取被回收的物理地址PAn;

2：回收器檢查PAn所在的BLOCK n，所有的page是否收齊(每個塊用1bit標(biāo)示，所有bit收齊為1時，可被回收)，如果收齊轉(zhuǎn)入步驟3，否則置PAn已回收的標(biāo)示。

3：通過NFC(NAND FLASH)擦除相應(yīng)塊。

4：釋放地址(PAn … PAn+511)到地址分配器，供新的寫請求申請。

對于情況2，其觸發(fā)條件為，地址分配器中的可分配地址低于水位線(可用的地址少于一定數(shù)量)。

erase2.jpg

對于情況2來說：

1：地址分配器FIFO低于閾值，用于觸發(fā)地址回收器。

2：地址回收器，查找還剩最少page沒有收齊的BLOCK及相應(yīng)的page(PAx，PAy，PAz)。

3：在映射表中，查找相應(yīng)的物理地址所對應(yīng)的邏輯地址;

4：通過地址分配器申請新的物理地址，并填寫在原來的映射表中。

5：讀取原物理位置的數(shù)據(jù)PD(X，Y，Z)。

6：將數(shù)據(jù)寫入新的申請的物理地址中。(4，5，6可以串行執(zhí)行，循環(huán)多次，將未收齊的地址讀出)。

7：轉(zhuǎn)移完畢后，擦除原來的塊(BLOCK)。

8：將擦除后的塊地址，寫入地址分配器中。

完成后(就多出了接近一個BLOCK的地址空間，供上層應(yīng)用寫入)[!--empirenews.page--]

3：壞塊管理;

NAND FLASH在寫或者擦除時，會出錯，出錯時，需要將此塊標(biāo)記成壞塊，以后將不能使用。

因此壞塊管理模塊，需要記錄所需要不能使用的壞塊。因此我們討論壞塊出現(xiàn)的兩種情況：

1：在擦除時，出錯，則此block為壞塊，壞塊管理單元記錄壞塊。

2：在寫某page出錯，首先所在塊(block)讀出剩余的page，分配新的物理地址，更新映射表，同時對該塊進(jìn)行擦除，如果出錯標(biāo)記為壞塊，如果有幸不出錯，則可以重新將地址放入地址分配器。

對于情況1來說：操作相對簡單;

對于情況2來說：壞塊管理單元的操作較為復(fù)雜：

1：寫操作，觸發(fā)壞塊管理單元工作。

2：寫出錯。壞塊管理單元受到觸發(fā)，記錄當(dāng)前的物理壞塊的位置(M)。

3：同時將地址分配器中M壞塊中的剩余地址讀出，(禁止再向這些page中寫入數(shù)據(jù))。讀出后，申請新的塊中的page，將當(dāng)前數(shù)據(jù)寫入flash。

一種積極的處理方式如上圖所示：

4：查找該block對應(yīng)剩余物理地址所對應(yīng)的邏輯地址。

5：申請新的物理地址并記錄新的映射表。

6：讀出物理塊地址所對應(yīng)的數(shù)據(jù)。

7：將數(shù)據(jù)寫入新申請的物理地址。

注釋：步驟4，5，6，7可以順序執(zhí)行，循環(huán)多次，取決于該block的已用的page的個數(shù);

8：等搬完畢后，重新擦除該塊(M);

9：如果擦除成功，則將地址重新放入分配池，否則該塊丟棄。

另一種消極的方法：

在步驟3后，只需要記錄當(dāng)前塊位置，將M壞塊中的剩余地址讀出后，放入地址回收器，等待該塊剩余位置被重新寫時，則該page被廢棄，由地址分配器收齊所有地址后再進(jìn)行擦除。

剩余步驟從8開始，直接擦除該塊，擦除錯誤，直接廢棄該塊，擦除成功可重新放入地址分配器。

4：均衡磨損;

均衡磨損是NAND FLASH的基本功能，通過將可用的地址放入先入先出的地址分配器中，能夠保證均衡磨損的效果。

如何將磨損程度最小的可用塊，放入地址分配器(FIFO)，是本節(jié)討論的要點(diǎn)?

這個問題轉(zhuǎn)化為:設(shè)計均衡磨損管理模塊，其功能將磨損程度最小的塊，首先放入地址分分配器。

均衡管理模塊需要將統(tǒng)計所有塊的磨損次數(shù)，然后找到最小磨損的塊。對于需要分配地址時，如果涉及到查找最小磨損塊，則可能會影響寫的效率。因此，涉及一個鏈表，將塊的磨損次數(shù)按照次數(shù)的多少進(jìn)行排序，如果磨損次數(shù)相同，則按照地址的大小排序。如此一來，則可以保證，則需要快速申請有效地址時，則可以按照鏈表的順序，迅速將可用塊地址放入地址分配器。

因此：對于均衡磨損來所，涉及到鏈表的生成和鏈表的讀取;

對于初始化時，由于此時所有塊都是可用的，因此其擦除次數(shù)可以都設(shè)置為1，此時課可以按照的地址的大小進(jìn)行鏈表的鏈接。

對于地址回收器，來說如果已回收某塊，(如上圖中，地址回收器標(biāo)示第4塊已被回收)。觸發(fā)均衡磨損管理模塊，標(biāo)示其收到已擦除的塊。

將已擦除的塊(第四塊)擦除次數(shù)自加，標(biāo)示為有效(可以將此塊放入地址分配器)，

排序，建立新的鏈表。建立的過程一種方式是，查找到比其磨損次數(shù)多的塊n0，比其磨損次數(shù)少的塊n5,同時修改其上一塊(pre block)和下一塊(post block)。這樣就建立了一條按照磨損次數(shù)由小到大的鏈表。(建鏈的過程可以通過設(shè)計最新擦除的次數(shù)塊的cache，加大能夠碰撞的幾率，因為如果大塊數(shù)據(jù)的寫操作，其回收的塊的磨損次數(shù)應(yīng)該近似，寫時申請page所在的塊磨損次數(shù)就接近(我們按照由小到大的順序放入的)，因此回收時，磨損次數(shù)也接近，因此cache對處理此種空間相關(guān)性大的算法，效率較高)。

那什么時候均衡管理模塊將數(shù)據(jù)放入地址分配器中?

觸發(fā)條件：當(dāng)?shù)刂贩峙淦髦械腇IFO低于設(shè)定的閾值，觸發(fā)均衡管理模塊開始工作。

將入口地址n3塊放入地址分配器。(將塊號轉(zhuǎn)換為塊中所有的512個page號(假設(shè)為每個塊中有512個page)。

根據(jù)鏈表，將n5變?yōu)槿肟诘刂?，等待下次觸發(fā)條件，然后將 n5放入地址分配器。

這樣，根據(jù)上述的算法，就可以使所有的塊，均衡的磨損，保證所有塊被擦除的次數(shù)一致。

5：總結(jié)一下;

回應(yīng)開頭，本文的目標(biāo)是設(shè)計一種可以硬件(硬件描述語言)實(shí)現(xiàn)的NAND FLASH的均衡磨損的算法。替代CPU+軟件的方式實(shí)現(xiàn)在當(dāng)前較熱門的存儲控制器中。

(1)，所有的操作，都需要觸發(fā)條件(讀，寫，擦除，壞塊管理，均衡磨損)，其他時間可以模塊可以休眠，因此功耗容易控制;預(yù)計比CPU有更好的能耗比(也跟實(shí)現(xiàn)相關(guān))。

(2)硬件實(shí)現(xiàn)不取決于CPU的能力，特別是對于PCIe的NAND FLASH控制器來說，可以達(dá)到非常高的處理能力，瓶頸在NAND的讀寫擦除速率。

(3)缺點(diǎn)：設(shè)計中需要多個表項的管理。

分別是1：映射表，管理邏輯page地址和物理page地址的對應(yīng)關(guān)系。

2：地址回收器中，block內(nèi)page的回收表;(每個page需要1bit表示)。

3：均衡管理模塊中的鏈表，存儲所有塊的磨損次數(shù)以及鏈表信息。

這些表項與NAND的大小有關(guān)系(是8G/16G/32G?),這些表項是按比例增加的，因此NAND，這些表項需要大塊的RAM存儲。

其次映射表的查找，同時需要設(shè)計CAM模塊及操作，來加速表的查找。

如果在PCIe的控制器中，可以放在外部DRAM中，掉電檢測時，存儲在NAND中，加電時再將數(shù)據(jù)讀出。如果沒有外部DRAM，則就需要將映射表一部分放入NAND中，另一部分放入片內(nèi)SRAM中，同時也會占用較多的SRAM。 同時需要不斷的取出及存入NAND中(這個設(shè)計同時保證可靠性就是一個挑戰(zhàn))。

(4)：總結(jié)，此種算法應(yīng)該適合應(yīng)用于高速的NAND控制器中，替代高性能多核CPU來實(shí)現(xiàn)FTL。具有較高的能耗比與可行性。