【導(dǎo)讀】目前，存儲(chǔ)領(lǐng)域包括eMMC，SATA SSD ,PCIe SSD等控制器是一個(gè)非常熱門(mén)的領(lǐng)域。通常，由于NAND FLASH易于損壞的特性，因此需要控制器做額外的工作，才能滿(mǎn)足商用可靠存儲(chǔ)的需要。本文目的提出一種可以硬實(shí)現(xiàn)的均衡磨損，壞塊管理，以及邏輯地址映射的算法，（可芯片化）。用于替代處理器的軟件（FTL）實(shí)現(xiàn)，從總體上較CPU固件實(shí)現(xiàn)有較好的功耗比和高速性能的目標(biāo)。
存儲(chǔ)控制器的所做的額外工作就是均衡磨損、壞塊管理、以及邏輯地址到物理地址映射的管理。通常在存儲(chǔ)控制器中需要集成CPU運(yùn)行并運(yùn)行相應(yīng)的軟件才能完成上述的功能，而隨著存儲(chǔ)性能的增加，則需要更高性能的CPU或者多核處理器以及高速的處理算法。
NAND FLASH的管理說(shuō)明：
1：NAND FLASH 只能按頁(yè)寫(xiě)，且只能寫(xiě)干凈的頁(yè)。（一個(gè)頁(yè)一旦寫(xiě)過(guò)就不能寫(xiě)第二次，除非被擦除）
2：NAND FLASH 能按頁(yè)讀，這個(gè)可以讀多次。
3：NAND FLASH 只能按塊擦。（一個(gè)塊包含多個(gè)頁(yè)）
4：NAND FLASH的出錯(cuò)一般出現(xiàn)在寫(xiě)，和擦除時(shí)，如果NAND FLSAH的塊在寫(xiě)或者擦除時(shí)，出錯(cuò)，則就不能再使用，內(nèi)部?jī)?nèi)容需讀出寫(xiě)入其他的位置。
5：如果NAND FLASH的管理中，如果重新改寫(xiě)同一地址，則原地址內(nèi)容作廢，邏輯映射一個(gè)新地址寫(xiě)入（原因見(jiàn)規(guī)則1）。
1 基本操作：讀、寫(xiě)
那么如何設(shè)計(jì)相應(yīng)的硬實(shí)現(xiàn)算法：首先是考慮寫(xiě)操作，每次寫(xiě)都要寫(xiě)一個(gè)干凈的地址。因此我們假設(shè)有一個(gè)模塊，每次吐出一個(gè)新的干凈頁(yè)地址，那么每次寫(xiě)操作時(shí)，都申請(qǐng)從此模塊申請(qǐng)一個(gè)新地址。
寫(xiě)NAND FLASH的步驟：（把大象關(guān)冰箱里的步驟）。
0：主機(jī)寫(xiě)入一個(gè)邏輯地址（LA logic address）中一個(gè)page的數(shù)據(jù)（PD pagedata）。
1：從地址分配器（FIFO）中申請(qǐng)一個(gè)干凈頁(yè)地址（PA physical address），然后寫(xiě)到新的頁(yè)地址中。（這個(gè)步驟前少一步，）
2：記錄邏輯地址和物理地址的對(duì)應(yīng)關(guān)系。（LA->PA）到映射表。這樣完成寫(xiě)的流程。
下次讀的時(shí)候：
0：主機(jī)讀取一個(gè)邏輯地址（LA logic address）。
1：查找映射表，對(duì)應(yīng)的映射表LA->PA，則讀取PA的頁(yè)數(shù)據(jù)（PD）。返回主機(jī)。這樣就完成了讀的流程。
這樣考慮就是想法簡(jiǎn)單了，上圖是正常的寫(xiě)流程。由于寫(xiě)FLASH的步驟，首先要確定原有邏輯地址在映射表里是否存在，映射表相應(yīng)的表項(xiàng)刪除（刪除的表項(xiàng)會(huì)重新擦除使用，否則很快就會(huì)寫(xiě)完）。
寫(xiě)NAND FLASH的步驟：
0：主機(jī)寫(xiě)入一個(gè)邏輯地址（LA logic address）中一個(gè)page的數(shù)據(jù)（PD pagedata）。
1：查看頁(yè)地址中是否有相關(guān)的邏輯地址表項(xiàng)，如果有，則刪除表項(xiàng)，否則直接到下一步。
2：從地址分配器（FIFO）中申請(qǐng)一個(gè)干凈頁(yè)地址（PA physical address），
3：記錄邏輯地址和物理地址的對(duì)應(yīng)關(guān)系。（LA->PA）到映射表。
4：然后寫(xiě)到新的頁(yè)地址中。
讀NAND FLASH的步驟：
0：主機(jī)從一個(gè)邏輯地址（LA logic address）中一個(gè)page的數(shù)據(jù)（PD pagedata）。
1：在映射標(biāo)的表項(xiàng)中，查找LAn的表項(xiàng)。
2：查找對(duì)應(yīng)的物理地址（PAm）。
3：從PAm讀出PD并返回主機(jī)。
2 擦除
從上述的機(jī)制來(lái)看，每次寫(xiě)操作時(shí)，都會(huì)占用一個(gè)PAGE，而假設(shè)原有的邏輯地址內(nèi)部存儲(chǔ)數(shù)據(jù)，則原有的邏輯地址對(duì)應(yīng)的物理地址則被廢棄，因此需要將這些物理地址重新擦除后重新使用。（否則FLASH寫(xiě)完一遍后，再也不能再寫(xiě)）。
另一問(wèn)題，page按頁(yè)來(lái)寫(xiě)，而擦除按照塊來(lái)擦除，假設(shè)每個(gè)塊有512個(gè)page。
按照上述機(jī)制，每個(gè)塊都有512個(gè)page放入申請(qǐng)單元中，而這些page寫(xiě)操作時(shí)，被依次申請(qǐng)，也就是說(shuō)，BLOCK中每個(gè)page都會(huì)被寫(xiě)滿(mǎn)，當(dāng)這些物理page被重新寫(xiě)時(shí)，則原有的page變成臟頁(yè)，可以被擦除。但是前提是512個(gè)page的都湊齊。那擦除的情況分為兩種，
情況1：一個(gè)塊（block）中，所有的page都被寫(xiě)變成dirty后，可以擦除，放入地址分配器中。
情況2：地址分配器中剩余地址少于一定數(shù)量，則就考慮將那些仍然還有數(shù)據(jù)頁(yè)部分有效的塊（block）擦除，再進(jìn)行分配。前提是，將數(shù)據(jù)頁(yè)先讀出換個(gè)地方存儲(chǔ)。
對(duì)于情況1，可以類(lèi)似數(shù)通領(lǐng)域的組片，每個(gè)被重復(fù)寫(xiě)的邏輯地址，就釋放一個(gè)物理地址，收齊一個(gè)塊中所有的物理地址（都被寫(xiě)過(guò)后，釋放掉），就可以重新擦除后，重新放置在地址分配器中。
對(duì)應(yīng)情況1來(lái)說(shuō)：其觸發(fā)條件新的寫(xiě)入page，原有page被回收后，放入地址回收器中：
因此擦除的步驟可以分為：
1：獲取被回收的物理地址PAn；
2：回收器檢查PAn所在的BLOCK n，所有的page是否收齊（每個(gè)塊用1bit標(biāo)示，所有bit收齊為1時(shí)，可被回收），如果收齊轉(zhuǎn)入步驟3，否則置PAn已回收的標(biāo)示。
3：通過(guò)NFC（NAND FLASH）擦除相應(yīng)塊。
4：釋放地址（PAn … PAn+511）到地址分配器，供新的寫(xiě)請(qǐng)求申請(qǐng)。
對(duì)于情況2，其觸發(fā)條件為，地址分配器中的可分配地址低于水位線(xiàn)（可用的地址少于一定數(shù)量）。
對(duì)于情況2來(lái)說(shuō)：
1：地址分配器FIFO低于閾值，用于觸發(fā)地址回收器。
2：地址回收器，查找還剩最少page沒(méi)有收齊的BLOCK及相應(yīng)的page（PAx，PAy，PAz）。
3：在映射表中，查找相應(yīng)的物理地址所對(duì)應(yīng)的邏輯地址；
4：通過(guò)地址分配器申請(qǐng)新的物理地址，并填寫(xiě)在原來(lái)的映射表中。
5：讀取原物理位置的數(shù)據(jù)PD（X，Y，Z）。
6：將數(shù)據(jù)寫(xiě)入新的申請(qǐng)的物理地址中。（4，5，6可以串行執(zhí)行，循環(huán)多次，將未收齊的地址讀出）。
7：轉(zhuǎn)移完畢后，擦除原來(lái)的塊（BLOCK）。
8：將擦除后的塊地址，寫(xiě)入地址分配器中。
完成后（就多出了接近一個(gè)BLOCK的地址空間，供上層應(yīng)用寫(xiě)入）
3 壞塊管理
NAND FLASH在寫(xiě)或者擦除時(shí)，會(huì)出錯(cuò)，出錯(cuò)時(shí)，需要將此塊標(biāo)記成壞塊，以后將不能使用。因此壞塊管理模塊，需要記錄所需要不能使用的壞塊。因此我們討論壞塊出現(xiàn)的兩種情況：
1：在擦除時(shí)，出錯(cuò)，則此block為壞塊，壞塊管理單元記錄壞塊。
2：在寫(xiě)某page出錯(cuò)，首先所在塊（block）讀出剩余的page，分配新的物理地址，更新映射表，同時(shí)對(duì)該塊進(jìn)行擦除，如果出錯(cuò)標(biāo)記為壞塊，如果有幸不出錯(cuò)，則可以重新將地址放入地址分配器。
對(duì)于情況1來(lái)說(shuō)：操作相對(duì)簡(jiǎn)單；
對(duì)于情況2來(lái)說(shuō)：壞塊管理單元的操作較為復(fù)雜：
1：寫(xiě)操作，觸發(fā)壞塊管理單元工作。
2：寫(xiě)出錯(cuò)。壞塊管理單元受到觸發(fā)，記錄當(dāng)前的物理壞塊的位置（M）。
3：同時(shí)將地址分配器中M壞塊中的剩余地址讀出，（禁止再向這些page中寫(xiě)入數(shù)據(jù)）。讀出后，申請(qǐng)新的塊中的page，將當(dāng)前數(shù)據(jù)寫(xiě)入flash。
一種積極的處理方式如上圖所示：
4：查找該block對(duì)應(yīng)剩余物理地址所對(duì)應(yīng)的邏輯地址。
5：申請(qǐng)新的物理地址并記錄新的映射表。
6：讀出物理塊地址所對(duì)應(yīng)的數(shù)據(jù)。
7：將數(shù)據(jù)寫(xiě)入新申請(qǐng)的物理地址。
注釋?zhuān)翰襟E4，5，6，7可以順序執(zhí)行，循環(huán)多次，取決于該block的已用的page的個(gè)數(shù)；
8：等搬完畢后，重新擦除該塊（M）；
9：如果擦除成功，則將地址重新放入分配池，否則該塊丟棄。
另一種消極的方法：
在步驟3后，只需要記錄當(dāng)前塊位置，將M壞塊中的剩余地址讀出后，放入地址回收器，等待該塊剩余位置被重新寫(xiě)時(shí)，則該page被廢棄，由地址分配器收齊所有地址后再進(jìn)行擦除。
剩余步驟從8開(kāi)始，直接擦除該塊，擦除錯(cuò)誤，直接廢棄該塊，擦除成功可重新放入地址分配器。
4 均衡磨損
均衡磨損是NAND FLASH的基本功能，通過(guò)將可用的地址放入先入先出的地址分配器中，能夠保證均衡磨損的效果。如何將磨損程度最小的可用塊，放入地址分配器（FIFO），是本節(jié)討論的要點(diǎn)?這個(gè)問(wèn)題轉(zhuǎn)化為:設(shè)計(jì)均衡磨損管理模塊，其功能將磨損程度最小的塊，首先放入地址分分配器。
均衡管理模塊需要將統(tǒng)計(jì)所有塊的磨損次數(shù)，然后找到最小磨損的塊。對(duì)于需要分配地址時(shí)，如果涉及到查找最小磨損塊，則可能會(huì)影響寫(xiě)的效率。因此，涉及一個(gè)鏈表，將塊的磨損次數(shù)按照次數(shù)的多少進(jìn)行排序，如果磨損次數(shù)相同，則按照地址的大小排序。如此一來(lái)，則可以保證，則需要快速申請(qǐng)有效地址時(shí)，則可以按照鏈表的順序，迅速將可用塊地址放入地址分配器。
因此：對(duì)于均衡磨損來(lái)所，涉及到鏈表的生成和鏈表的讀??；
1.對(duì)于初始化時(shí)，由于此時(shí)所有塊都是可用的，因此其擦除次數(shù)可以都設(shè)置為1，此時(shí)課可以按照的地址的大小進(jìn)行鏈表的鏈接。
2.對(duì)于地址回收器，來(lái)說(shuō)如果已回收某塊，（如上圖中，地址回收器標(biāo)示第4塊已被回收）。觸發(fā)均衡磨損管理模塊，標(biāo)示其收到已擦除的塊。
3.將已擦除的塊（第四塊）擦除次數(shù)自加，標(biāo)示為有效（可以將此塊放入地址分配器），
4.排序，建立新的鏈表。建立的過(guò)程一種方式是，查找到比其磨損次數(shù)多的塊n0，比其磨損次數(shù)少的塊n5,同時(shí)修改其上一塊（pre block）和下一塊（post block）。這樣就建立了一條按照磨損次數(shù)由小到大的鏈表。（建鏈的過(guò)程可以通過(guò)設(shè)計(jì)最新擦除的次數(shù)塊的cache，加大能夠碰撞的幾率，因?yàn)槿绻髩K數(shù)據(jù)的寫(xiě)操作，其回收的塊的磨損次數(shù)應(yīng)該近似，寫(xiě)時(shí)申請(qǐng)page所在的塊磨損次數(shù)就接近（我們按照由小到大的順序放入的），因此回收時(shí)，磨損次數(shù)也接近，因此cache對(duì)處理此種空間相關(guān)性大的算法，效率較高）。
那什么時(shí)候均衡管理模塊將數(shù)據(jù)放入地址分配器中？
1.觸發(fā)條件：當(dāng)?shù)刂贩峙淦髦械腇IFO低于設(shè)定的閾值，觸發(fā)均衡管理模塊開(kāi)始工作。
2.將入口地址n3塊放入地址分配器。（將塊號(hào)轉(zhuǎn)換為塊中所有的512個(gè)page號(hào)（假設(shè)為每個(gè)塊中有512個(gè)page）。
3.根據(jù)鏈表，將n5變?yōu)槿肟诘刂罚却麓斡|發(fā)條件，然后將 n5放入地址分配器。
這樣，根據(jù)上述的算法，就可以使所有的塊，均衡的磨損，保證所有塊被擦除的次數(shù)一致。
5 總結(jié)
回應(yīng)開(kāi)頭，本文的目標(biāo)是設(shè)計(jì)一種可以硬件（硬件描述語(yǔ)言）實(shí)現(xiàn)的NAND FLASH的均衡磨損的算法。替代CPU+軟件的方式實(shí)現(xiàn)在當(dāng)前較熱門(mén)的存儲(chǔ)控制器中。
（1），所有的操作，都需要觸發(fā)條件（讀，寫(xiě)，擦除，壞塊管理，均衡磨損），其他時(shí)間可以模塊可以休眠，因此功耗容易控制；預(yù)計(jì)比CPU有更好的能耗比（也跟實(shí)現(xiàn)相關(guān)）。
（2）硬件實(shí)現(xiàn)不取決于CPU的能力，特別是對(duì)于PCIe的NAND FLASH控制器來(lái)說(shuō)，可以達(dá)到非常高的處理能力，瓶頸在NAND的讀寫(xiě)擦除速率。
（3）缺點(diǎn)：設(shè)計(jì)中需要多個(gè)表項(xiàng)的管理。
1：映射表，管理邏輯page地址和物理page地址的對(duì)應(yīng)關(guān)系。
2：地址回收器中，block內(nèi)page的回收表；（每個(gè)page需要1bit表示）。
3：均衡管理模塊中的鏈表，存儲(chǔ)所有塊的磨損次數(shù)以及鏈表信息。
這些表項(xiàng)與NAND的大小有關(guān)系（是8G/16G/32G？）,這些表項(xiàng)是按比例增加的，因此NAND，這些表項(xiàng)需要大塊的RAM存儲(chǔ)。
其次映射表的查找，同時(shí)需要設(shè)計(jì)CAM模塊及操作，來(lái)加速表的查找。
如果在PCIe的控制器中，可以放在外部DRAM中，掉電檢測(cè)時(shí)，存儲(chǔ)在NAND中，加電時(shí)再將數(shù)據(jù)讀出。如果沒(méi)有外部DRAM，則就需要將映射表一部分放入NAND中，另一部分放入片內(nèi)SRAM中，同時(shí)也會(huì)占用較多的SRAM。 同時(shí)需要不斷的取出及存入NAND中（這個(gè)設(shè)計(jì)同時(shí)保證可靠性就是一個(gè)挑戰(zhàn)）。
（4）：總結(jié)，此種算法應(yīng)該適合應(yīng)用于高速的NAND控制器中，替代高性能多核CPU來(lái)實(shí)現(xiàn)FTL。具有較高的能耗比與可行性。
