星載大容量固態存儲器快速可靠啟動算法設計

李 姍，宋 琪，朱 巖，安軍社（.中國科學院空間科學與應用研究中心，0090北京；2.中國科學院大學，00049北京）

星載大容量固態存儲器快速可靠啟動算法設計

李 姍1，2，宋 琪1，2，朱 巖1，安軍社1
（1.中國科學院空間科學與應用研究中心，100190北京；2.中國科學院大學，100049北京）

本文研究星載大容量固態存儲器（SSR）的索引建立機制，分析傳統方案的優缺點并結合在軌運控需求、工作模式等特點，提出一種適合基于NAND FLASH的星載大容量固態存儲器的快速啟動算法.原有文件系統存儲索引表來自于NAND FLASH空余區，算法增加新的保留區設計及相應的啟動過程，避免重啟時掃描空余區重新建立索引.針對空間環境單粒子效應帶來的存儲錯誤，NAND FLASH保留區的索引信息采取ECC編碼、冗余備份、分區存儲等可靠性措施，提高索引表的可靠性.本文介紹了應用保留區的啟動工作機理以及不同模式下的更新方式，闡述了系統在功能性重啟和故障性重啟下的掃描方式，并建立數學模型分析算法的有效性，最后在使用歐比特NAND FLASH搭建的測試平臺上進行驗證.本文算法功能性重啟索引建立耗時5.643 ms，故障重啟索引建立73.985 ms，而傳統算法重啟索引建立50.37 s.實驗結果表明，本算法顯著減少了系統啟動耗時.

快速啟動；NAND FLASH；固態存儲器；存儲系統

星載大容量固態存儲器（SSR）是航天器的關鍵設備之一，由于地面接收站數量、接收范圍有限，航天器在軌運行時，產生的大量珍貴數據需先在星上暫存，待入境后進行數據傳輸.航天器工作環境惡劣，空間中充斥著大量帶電粒子可導致設備內管理邏輯混亂，部分單元失效甚至引起設備起火燒毀整個航天器［1－5］.異常發生時，需通過地面在過境時發送指令以備份單元切換的方式降低或消除帶電粒子帶來的效應的影響.另外，對繞月、繞火星等非地球恒星的飛行器而言，其測控和數傳接收還受到各星球間位置關系變化的影響，因此星載SSR管理算法對可靠性和啟動時間都提出了較高的要求.

NAND FLASH的存儲密度高，低功耗，抗震能力強等［6－8］.目前，常見的NAND FLASH管理方法有JFFS［9］，YAFFS［10］等.其中YAFFS是針對NAND FLASH設計的管理方法，啟動較JFFS更快［11］，應用范圍更廣.YAFFS算法中索引表使用多級映射方式，系統重建耗時長，風險大.Yim［12］提出的快照技術（Snapshot）將系統內數據索引記錄下來并保存在NAND FLASH中，系統再次啟動時只需讀取快照內數據即可重建索引，但該算法的快照機制只在系統正常關機時才啟動，異常關機時快照內容無法重建系統，必須對所有NAND FLASH空余區進行掃描，依舊存在啟動時間過長的問題.星載SSR的啟動時間由索引表建立時間、CPU讀取索引表時間以及存儲系統初始狀態設置時間3部分構成.256 Gb容量（32 K條索引表項）情況下，CPU讀取索引表時間在1 s以內，初始狀態設置過程在幾個CPU周期之內即可完成，而索引表的建立時間占啟動時間的95%以上.因此，本文重點討論如何對索引表建立時間的優化設計.

1 NAND FLASH

NAND FLASH是一種層次結構的掉電非易失存儲器，頁作為基本單元構成塊，多個塊組成芯片.每頁包含數據區和空余區，空余區用于存儲一些管理信息.NAND FLASH由FN tunnel構成，它是芯片中的最小存儲單元，可以通過放電的方式使其為零，但無法單獨使其置‘1'，只能整塊充電置‘1'.因此，NAND FLASH不能直接更新，需要先擦除后更新. NAND FLASH的基本操作包括：讀取，擦除，寫入.其中讀取和寫入的基本單元為頁，而擦除的基本單元為塊［13］.NAND FLASH采用數據地址分時復用的形式，通過IO分時傳輸數據、地址及控制信息.壞塊是一些無法被徹底擦除或者其中有些位無法翻轉塊的統稱.由于成本和工藝限制，出廠時NAND FLASH中會存在一些壞塊，稱為初始壞塊.為區分這些出廠壞塊，廠家通常在NAND FLASH空余區的第一個字節標記非“0XFF”.NAND FLASH的塊擦除極限為5 000～100 000次，因此會有壞塊在使用過程中產生，稱作使用壞塊.

為滿足空間應用需要，原始NAND FLASH芯片不僅經過抗輻照加固而且使用3?D封裝技術進行疊裝，以實現更高的存儲密度［14］.3?D技術將8片NAND FLASH基片（DIE）封裝為成一個鍍金立方體，將芯片的控制信號，電源線連接在一起，而數據線、片選信號分別引出.以珠海歐比特公司的VDNF64G08為例［15］，每個芯片包含8個die，每個die包含4 096個塊，每塊包含64頁，每頁包含4 KBytes數據區和128 Kbytes空余區.

2 快速啟動算法設計

星載SSR在軌運行時有3種工作模式：存儲模式、回放模式以及混合模式.索引表隨星載SSR內數據存儲狀態變化持續更新，索引表更新策略需靈活適應各工作模式的需求.傳統應用中采用頁作為索引最小單元，不僅占用大量存儲空間且啟動緩慢［15］.現在越來越多的研究者把眼光集中在以塊為單元甚至更大的單元索引策略上［16］.NAND FLASH讀操作的最小單元是頁，擦除操作的最小單元是塊.因此，本文采用以塊為主以頁為輔的索引方式，有效提高啟動速率.

2.1 星載SSR的啟動基本流程

傳統星載SSR在對NAND FLASH進行數據存儲、讀取等操作的同時，將管理信息存儲在NAND FLASH空余區.由于NAND FLASH單頁加載時間較長，約為200～700μs，而一頁數據加載時間通常不超過130μs，為了提高SSR的吞吐量，多采用多級流水操作［17］.空余區采用頁為單元標記，當頁操作完畢后根據操作結果在頁空余區中寫入頁信息，包括頁使用情況、頁屬性、流水級信息等.空間中存在多種高能粒子，易誘發NAND FLASH發生單粒子效應，產生邏輯錯誤或引起功能異常，嚴重影響航天器在軌效能的發揮.為提高索引條目的可靠性，加入ECC校驗碼，可實現自動糾正1位錯誤，檢測2位錯誤.具體頁信息存儲情況如表1所示.

星載SSR啟動時遍歷所有頁的空余區，并將頁信息整合為按照塊為單位的新條目.塊條目包含塊信息、使用信息等.塊條目結構組成如表2所示.

索引表建立完成之后，由CPU讀取并存入緩存SDRAM中，供CPU對存儲區進行管理.因此，對于傳統算法管理的星載SSR而言，索引表一份存儲在CPU緩存SDRAM中，另一份存儲在NAND FLASH的空余區.第一份掉電丟失，啟動時必須遍歷所有塊空余區，致使啟動時間隨容量增加大幅增長［12］，無法滿足星載SSR的應用需求.

表1 NAND FLASH空余區頁記錄信息表

表2 塊條目信息表

2.2 保留區索引表設計

為提高系統啟動速度，本文提出保留區概念，在星載SSR存儲區中劃分一塊區域專門保存索引信息，定義為保留區索引表.啟動時，優先搜索保留區索引表，集中搜索區域降低搜索用時.

保留區索引表基于CPU中原始索引表架構，精簡組織信息，減少組織用時，減小索引表，提高啟動速度.根據保留區索引條目類型將其劃分為壞塊信息區與數據信息區，由于二者更新頻率、方式不同，因此將兩者獨立存儲、管理.壞塊區更新頻率低，可靠性要求更高，對壞塊信息區進行雙份冗余存儲.數據信息區保存索引條目，壞塊區保存壞塊塊號.索引表條目可用數組表示為：｛塊號，塊類型，文件號，文件占用頁數，ECC編碼｝，索引條目使用固定的位數存儲，替代條目標示符，提高檢索效率.保留區中，塊的數據區存儲索引信息，空余區存儲維護信息.空余區第一個字節代表塊屬性，第二個字節代表頁狀態，塊屬性分為正常塊（0x“03”）、未使用塊（0x“FF”），頁狀態分為有效（0x”55”）、無效（0x”00”）.

隨著星載SSR的運行，索引表中將產生大量失效條目，需定期整理.如將整個索引表讀出，剔除失效條目，再寫入，需占用NAND FLASH總線較長時間，降低系統存儲效率.為此本文提出分die管理的方式，將保留區分die劃分，每個die的保留區中僅存儲該die的索引表，使用時只需維護當前die，充分利用空間，降低各die間的耦合度，提高可靠性同時增強算法適用性.

首次上電，對所有NAND FLASH芯片進行掃描得到出廠壞塊地址，并分別將其全部寫入每個die保留區的第一個block壞塊區中，然后使用Page Cope－Back將其中內容拷貝至第二個block的壞塊區中，并在第一塊空余區寫入0x“55”，標示該頁為有效的索引表存儲頁.正常工作時，CPU按一定更新周期對保留區索引表進行更新，將新增的數據信息寫入數據信息區.根據NAND FLASH的特性，無法對寫入塊直接更新但分析可知再次寫入，對應位為兩次寫入量相與的結果，因此可以通過再次寫入零的方式將對應位寫為零，此操作定義為覆寫.新增信息如為文件寫入，順序添加條目；如為文件擦除，將對應條目的文件大小覆寫為0；如為擦除壞塊則將其塊號寫入壞塊信息存儲頁；如為出錯塊則先將其寫入數據信息存儲頁中，待失效處理后將地址寫入壞塊區.

每個Die的保留區采用固定定位的方式，提高系統故障后重啟的可靠性.每個Die的前5個好塊定為保留區，隨著系統信息的更新保留區內也可能出現壞塊，如出現壞塊順序向后擴展保留區，保證保留區中至少有3個好塊可供使用.更新策略也采用順序更新方式，即第i塊是兩個區都更新，第i+1塊是獨立更新壞塊區.

索引更新策略需配合各工作模式以保證性能最優.存儲模式下數據流量低，NAND FLASH I／O總線空閑時間充裕，保留區正常更新.回放模式和混合模式下數據流量高，NAND FLASH I／O總線忙碌，停止更新保留區，僅實時更新原始索引表和備份索引表.在境內時，地面會根據需求，發送指令標記不再需要的文件為失效數據.索引條目對應文件失效時，將該條目對應文件占用頁數改寫為零，該操作定義為失效處理，失效處理通過覆寫即可快速實現.出境模式后，需根據地面指令更新索引表.通常，過境后會有大量數據被標記無效.為提高更新效率，將保留區中入境前有效的block標記無效，根據原始索引表中失效信息對保留區組織新索引表寫入保留區中空白塊.采用流水線方式更新索引表，提高整體更新效率，具體流程如圖1所示.其中Nc1＝更新總級數；Nc＝單級更新總數；Ne1＝擦除總級數；Ne＝單級擦除總數；一個die內有B個塊.

3 星載SSR的快速啟動模式

星載SSR在首次啟動或者徹底復位后的首次啟動需要遍歷Flash空余區，無法實現快速啟動.而在一般工作過程中重啟時能夠使用快速啟動模式.實際應用中，快速啟動擁有兩種模式，一種為功能性重啟，一種為故障性重啟.功能性重啟為恢復功能或消除某些粒子效應時進行的軟件重啟.故障性重啟多為系統在運行中遇到的不可抗力使得其突然掉電或者復位.兩者間最大的區別為功能性重啟時過程可控，系統有足夠的時間將緩存區的索引表寫入保留區并將保留區索引表所在位置保存，而故障性重啟時過程不可控.

功能性重啟：由計算機中主控計算機板發送重啟指令，星載SSR系統中計算機板接到指令后優先將緩存中索引信息存入保留區.保存保留區索引表后，星載SSR系統中CPU將保留區索引表所在位置發送給主控計算機板然后重啟.再次上電，CPU只掃描保留區有效塊的數據區即可重建索引.

故障性重啟：系統突然掉電丟失CPU緩存內信息，包括原始索引表，保留區索引表更新信息，最后更新位置以及整體分布位置.再次啟動后，重建步驟如下：

1）定位保留區.CPU按順序讀取每個die內前兩塊空余區前兩個字節，搜索到0x”0155”即停止，如無則從該die末尾開始倒序搜索，搜索到0x”0155”即止；

圖1 索引表更新流程

2）讀取保留區.FPGA順序讀取每個die保留區有效塊的空余區，掃描0x”0155”.根據0x”0155”的位置定位有效頁，讀取有效頁的數據區；

3）定位最后更新位置.讀取每個die索引表記錄中最后一塊的下一非壞塊空余區，如非0x”FF”，則表明此塊已使用.塊內實際使用情況與索引表記錄不符，此die為最后更新位置；

4）恢復更新信息.假設最后更新die的索引表最后一條地址是第m塊，更新周期為N塊.將從m塊開始掃描每頁空余區的前6字節，直至m+N塊或者掃描到某頁空余區第一個字節為“FF”表明此塊未寫入過數據為止.

4 系統性能分析

4.1 基本假設

本算法的啟動時間與NAND FLASH大小、保留區內壞塊的數量、索引表的大小、更新方式、故障發生時緩存區內容大小、索引表更新周期都相關.為計算方便，做出如下假設：

1）系統壽命內每個die內壞塊的數量不超過總量的一半；

2）目標NAND FLASH滿足：

1page＝（D+S）Byte，1block＝Ppages，1die＝Bblocks.

測試系統包括Qd個die；

3）保留區內有效塊為第i塊的概率為ni%；

4）讀取時鐘周期為tclk，NAND FLASH內部加載時間為tbusy，讀取比特數為qread，因此，讀NAND FLASH的時間可以表示為

5）最后更新位置為第Nl塊，0≤Nl≤Qd；

6）算法更新周期為Nup；

7）第i個die的索引表大小為Vi，0≤Vi≤P（D +S）.

4.2 快速啟動、傳統索引建立時間分析及對比

根據以上假設建立NAND FLASH數學模型，重點對本文提出的快速啟動算法的故障性啟動時間Tstartn和傳統算法的啟動時間Tstarto進行計算.

Tstartn的計算根據啟動流程可分為如下4步：

1）定位保留區Torient.掃描i次找到保留區使用時間為：Qdni%i（Tc+2 tclk）.廠商允許NAND FLASH存在一定數量的壞塊，一般在2%至5%之間，同時，FLASH設備的使用有擦寫次數的限制，NAND FLASH是100萬次，在空間環境中出現輻射時，新增長使用壞塊的概率pub1＜10－4，連續出現兩塊使用壞塊的概率為pub2＝p2ub1＜10－8［19］.因此，系統壽命內連續出現兩塊以上使用壞塊的概率極低，假設保留區最多會出現兩個壞塊，最多需掃描三次即可得到索引表位置.

傳統星載SSR管理算法在每頁空余區寫入塊屬性、塊計數、時間碼、校驗碼等，每次啟動時都需要掃描所有空余區，用Tstarto表示啟動時間.

Tstarto＝QdB P（Tc+S tclk）＝

Qd（B P Tc+B P Stclk）.目前市場上常用的NAND FLASH中各參數的范圍如下：

5 實驗結果

本文使用國產化器件搭建星載SSR硬件平臺驗證算法性能.存儲芯片使用國產珠海歐比特生產的VDNF64G08芯片，CPU使用計算所研制的龍芯. FPGA尚未國產化，使用Actel A3PE3000L芯片，工作在64 M晶振下.主要存儲芯片為4片VDNF64G08芯片共256 G.測試軟件為基于LINUX5.8自主開發的星載SSR控制軟件.在該平臺下使用本文提出算法與傳統管理算法進行啟動時間的比較試驗，并且針對相關參數進行實驗、討論.星載相機拍攝圖片通常較大，為貼合使用需求，測試數據選用大小為100 K～10 M的圖像數據.

5.1 啟動時間

使用測試數據在以上測試平臺上分別進行功能重啟和故障重啟，記錄上電到索引表識別完畢的時間，并與傳統算法進行比較.首先，設定更新周期為100塊，使用測試數據將星載SSR存儲區寫滿，待到數據開始循環擦除、寫入到第550塊時，由上位機軟件發送重啟指令，得到功能重啟的時間是5.643 ms.在同樣測試條件下，待存儲區循環擦除、寫入到第550塊時，人為掉電模擬故障，得到的故障重啟時間是73.985 ms.

相同條件下使用傳統的管理算法得到的故障重啟與軟件重啟時間相同，都為50.37 s.可見，本文算法的啟動時間顯著縮短了啟動時間.

5.2 更新周期

由于系統故障后啟動時間與更新周期關系密切，使用原測試數據在上述平臺上進行以更新周期為變量的一組關于啟動時間的測試實驗.設定更新周期分別為10，100，500塊.在寫第495塊時，人為掉電模擬故障重啟，啟動時間如表3.

表3 不同更新周期下的啟動時間表

故障后存留在緩存中的索引表信息丟失，緩存區中的索引表信息量與故障發生的時間以及更新周期有關.隨著更新周期增大，緩存區的信息量增多，故障發生時可能丟失信息量增多.再次啟動時需要掃描的空余區數量增多，所以系統故障啟動時間變長.雖然更新周期增加對應啟動時間增長，但較長的更新周期CPU緩存內保存的索引信息量增多，索引信息發生改動時，更改索引表消耗的系統資源減少，索引表維護更便捷.尤其時當系統內信息小范圍頻繁改動時，較長的更新周期更利于簡化索引表從而提高啟動時間.因此，需要結合工程具體需求選擇更新周期.

6 結 語

對星載SSR工作特點進行分析，提出一種可靠的快速啟動算法.該算法在原始星載SSR啟動機制的基礎上提出保留區概念，單獨存儲索引表，減少啟動掃描用時；流水更新的更新策略，提高更新效率；雙份冗余的壞塊表存儲方案，增加算法可靠性；依據不同模式使用不同更新策略，充分保證其性能.筆者在邏輯模型下對該算法進行分析并與傳統算法進行比較，又在國產器件搭建的星載SSR測試平臺上對其進行試驗驗證.分析結果和試驗結果均表明，該算法在功能性重啟和故障重啟條件下都能顯著減少啟動時間，在功能性重啟條件下性能更優.在今后的研究中，筆者將就更新周期，文件修改概率，文件大小等多種影響因素進行更多的探討以求更優良的管理方案.

［1］WANG J，KATZ R，SUN J，etal.SRAM based reprogrammable FPGA for space application［J］.IEEE Trans Nuclear Science，1999，46（6）：1728－1735.

［2］ALIA R G，BISKUP B，BRUGGER M，et al.SEU measurements and simulations in a mixed field environment［J］.IEEE Trans Nuclear Science，2013，60（4）：2469－2476.［3］MCMICKELL M B，TANZILLO P，KREIDER T，et al. Rapid development of space applications with responsive digital electronics board and LabVIEW FPGA［C］／／NASA／ESA Conference on Adaptive Hardware and Systems（AHS）.Anaheim：［s.n.］，2010：79－81.

［4］THOMPSON S，MYCROFT A，BRAT G，et al.Automatic in?flight repair of FPGA cosmic ray damage［C］／／1st Disruption in Space Symposium.Washington：［s.n.］，2005：287－296.

［5］KOZA J R，BENNETT F H.Genetic programming 3：darwinian invention and problem solving［M］.Berlin：Springer Netherlands，2000：379－381.

［6］BU K，WANG M，NIE H，et al.The optimization of the hierarchical storage system based on the hybrid SSD technology［C］／／the 2nd International Conference on ISDEA.Piscataway：IEEE，2012：1323－1326.

［7］FABIANO M，FURANO G.NAND flash storage technology for mission?critical space applications［J］.Aerospace and Electronic Systems Magazine，IEEE，2013，28（9）：30－36.

［8］MARINELLA M.The future of memory［C］／／2013 IEEE Aerospace Conference.Piscataway：IEEE，2013：1－11.

［9］WOODHOUSE D.JFFS：The journalling flash file system. https：／／www.sourceware.org／jffs2／jffs2?html／.2001－10－10.

［10］Aleph One Ltd，Embedded Debian.Yaffs：A NAND?Flash Filesystem.http：／／www.aleph1.co.uk／yaffs／.［214－5－23］.

［11］LU Cao，SHI Shao.A fast mounting method for NAND flash file system 2011［C］／／3rd International Conference on Computer Research and Development（ICCRD）. Shanghai：［s.n.］，2011：416－420.

［12］YIM K S.A fast start?up technique for flash memory based computing systems［C］／／Proceedings of the ACM Symposium on Applied Computing（SAC）.New York：ACM，2005：843－849.

［13］ho CHIEN?CHUNG，HUANG PO?CHUN，KUO TEI?WEI，et al.A dram?flash index for native flash file systems［C］／／International Conference on Hardware／Software Co?design and System Synthesis（CODES+ISSS）.Montreal：［s.n.］，2013：1－10.

［14］AL?SARAWI SAID F，ABBOTT DEREK，FRANZON PAUL D.A review of 3－D packaging technology［J］.IEEE Transactions on Components，Packaging and Manufacturing Technology，1998，21：2－14.

［15］Orbit Electronics.VDNF64G08?F 64G bit?8 bit NAND Flash memory Data Sheet，2013.

［16］RIZVI S S，CHUNG Tae?Sun.An advanced and reliable initialization technique using virtual clustering for flash memory based embedded and real time systems［C］／／2011 6th International Conference on Computer Sciences and Convergence Information Technology（ICCIT）.Piscataway：IEEE，2011：509－513.

［17］RIZVI S S，CHUNG T S，AMI：an advanced endurance management technique for flash memory storage systems［J］.The International Arab Journal of Information Technology，2011.8（1）：1－9.

［18］朱巖.基于閃存的星載高速大容量存儲技術的研究［D］.北京：空間科學與應用研究中心，2006.

［19］NGUYEN E N，GUERTIN S M，SWIFTG M，et al. Radiation effects on advanced flash memories［J］.IEEE Transactions on Nuclear Science，1999，46（6）：1744－1750.

（編輯 張 宏）

Design of quick initialization algorithm for space?borne solid state recorder

LI Shan1，2，SONG Qi1，2，ZHU Yan1，AN Junshe1
（1.Center for Space Science and Application Research，Chinese Academy of Sciences，100190 Beijing，China；2.University of Chinese Academy of Sciences，100049 Beijing，China）

This paper focuses on the index establishing mechanism for onboard Solid State Recorder（SSR），a quick initialization method for onboard massive capacity SSR based on NAND FLASH is proposed by analyzing the advantages and disadvantages of traditional scheme，the requirement of on?orbit operation and control，and working mode，etc.The proposed method uses the design ofreserved area and corresponding booting process on the basis of the original NAND FLASH indexing mechanism by space area，which largely reduced the organization time for index table.By considering the memory error caused by single particle effect，the index information in the reserved area of NAND FLASH uses reliability methods including ECC coding，redundancies and partition storage to improve the reliability of the index table.The restart working mechanism and the update of different mode for the reserved area of application is firstly introduced.Followed by the description of the scanning mode in both functional restart and fault restart，and a mathematical model is built to prove the effectiveness，and is verified in a platform established using Orbita NAND FLASH.Finally，in the designed platform the functional restart of the algorithm takes 3.643 ms and the fault restart takes 73.985 ms while the traditional algorithm takes 50.37 s，which demonstrate that the proposed algorithm significantly reduces the mounting up time.

quick initialization；NAND FLASH；solid state recorder；storage system

文獻標志碼：A文章編號：0367－6234（2015）10－0116－06

10.11918／j.issn.0367?6234.2015.10.022

2014－05－23.

中國科學院戰略性先導科技專項資助（XDA04060300）.

李 姍（1989—），女，博士研究生；朱 巖（1973—），男，研究員，博士生導師；安軍社（1969—），男，教授，博士生導師.

李 姍，lishanmg＠gmail.com.