曹丹丹 陳 勇 林寶軍

1(中國科學(xué)院光電研究院 北京 100094)

2(中國科學(xué)院大學(xué) 北京 100190)

基于FTL層的高可靠星載數(shù)據(jù)編碼保護(hù)設(shè)計

曹丹丹1,2陳 勇1林寶軍1

1(中國科學(xué)院光電研究院 北京 100094)

2(中國科學(xué)院大學(xué) 北京 100190)

空間單子效應(yīng)對長期在軌航天器存儲數(shù)據(jù)可靠性具有重大影響。針對此問題，提出在閃存轉(zhuǎn)換層FLT(Flash Translation Layer)上添加編碼轉(zhuǎn)換層，以動態(tài)滿足數(shù)據(jù)存儲可靠性的設(shè)計。在編碼轉(zhuǎn)換層提出一種選取編碼的方法，依據(jù)用戶對可靠度，使用壽命的要求，使所選取的編碼的編碼復(fù)雜度最低，空間利用率最高。本設(shè)計能夠為用戶在屏蔽底層接口的情況下，依照用戶的可靠性需求，為數(shù)據(jù)提供糾錯，為空間數(shù)據(jù)存儲的可靠性設(shè)計提供了重要依據(jù)。

星載存儲器 閃存轉(zhuǎn)換層 編碼轉(zhuǎn)換層 糾錯碼

0 引 言

在空間環(huán)境中，由于單粒子效應(yīng)，會影響存儲器進(jìn)行位翻轉(zhuǎn)，從而影響存儲的數(shù)據(jù)可靠性。針對星載嵌入式系統(tǒng)數(shù)據(jù)的容錯，很多人提出了不同的方法。文獻(xiàn)[1]提出了在VFS(Virtual File System)層利用三模冗余的思想對數(shù)據(jù)進(jìn)行保護(hù)。三模冗余只能容錯不能糾錯，空間利用率只有三分之一，而在VFS層的容錯也不利于文件系統(tǒng)的可移植性。文獻(xiàn)[2]在文件系統(tǒng)層面對存儲器的使用壽命進(jìn)行了提升，卻并未有效量化壽命的提升時間，無法估算其使用壽命是否滿足星載需求。文獻(xiàn)[3]采取了漢明碼對星載存儲器進(jìn)行了容錯處理，但在漢明碼編碼長度選擇上只考慮了空間利用率，并未考慮使用壽命的因素。文獻(xiàn)[4]針對集群故障提出了一種增加存儲器使用壽命的方法，但是針對的是整個存儲器，因為有些臨時文件不需要容錯處理，造成存儲空間的浪費。

本文提出在FTL層之上添加編碼轉(zhuǎn)換層。按照用戶對不同重要性的數(shù)據(jù)可靠度、壽命的需求，通過選取編碼復(fù)雜度最小，且空間利用率最大的編碼方法，編碼長度與糾錯位數(shù)對用戶的數(shù)據(jù)進(jìn)行容錯、糾錯，以滿足存儲數(shù)據(jù)可靠性的需求。

1 設(shè)計流程

長期在軌航天器所存儲的數(shù)據(jù)共分為三類：1) 核心數(shù)據(jù)：決定飛行器生死的數(shù)據(jù)，如果缺失將會導(dǎo)致該飛行器所有任務(wù)失敗，例如，文件系統(tǒng)索引結(jié)構(gòu)、目錄、啟動代碼、系統(tǒng)鏡像文件、進(jìn)程文件、初始化參數(shù)；2) 重要數(shù)據(jù)：決定飛行器的某些重要功能能否工作的數(shù)據(jù)，如果缺失將會造成飛行器重要功能受損，例如子功能進(jìn)程文件、子功能參數(shù)配置數(shù)據(jù)等；3) 一般數(shù)據(jù)文件，如果缺失對飛行器的運行、功能略有影響，但不影響任務(wù)的成敗，例如，中間結(jié)果數(shù)據(jù)。

設(shè)長期在軌航天器的最低使用壽命為t0,則核心數(shù)據(jù)的生存壽命應(yīng)為t=t0，重要數(shù)據(jù)使用壽命應(yīng)為t0/2

閃存存儲器因為防振、非易失、高并發(fā)、低功耗等特點，現(xiàn)已廣泛應(yīng)用于空間環(huán)境[5-6]。典型的閃存存儲結(jié)構(gòu)如圖1所示。存儲接口MTD(Memory Technology Device)層用于訪問底層存儲設(shè)備，為存儲器和上層之間提供抽象接口。閃存轉(zhuǎn)換層FTL(Flash Translation Layer)將上層文件系統(tǒng)與底層存儲設(shè)備銜接起來，提供物理地址到邏輯地址的映射[7，10]。文件系統(tǒng)負(fù)責(zé)為用戶建立文件、讀寫文件、修改文件、復(fù)制文件等功能[4]。

圖1 典型的閃存存儲結(jié)構(gòu)圖

對用戶存入的數(shù)據(jù)進(jìn)行冗余糾錯可以在三個層面進(jìn)行。在閃存陣列中加硬件ECC校驗，但這種算法是在硬件出廠時就已經(jīng)規(guī)定好的，糾錯位數(shù)固定，一般為1 bit,具有局限性[8]，而且星載存儲數(shù)據(jù)可靠性要求高，僅僅在底層加了ECC校驗無法完全阻止數(shù)據(jù)出錯。基于文件系統(tǒng)的讀寫函數(shù)對數(shù)據(jù)進(jìn)行糾錯使文件系統(tǒng)被底層硬件存儲結(jié)構(gòu)限制住，不具備可移植性，所以一般很少用這種方案。在閃存轉(zhuǎn)換層上對數(shù)據(jù)進(jìn)行冗余糾錯既根據(jù)數(shù)據(jù)特性動態(tài)分配合適的糾錯算法，又能在底層閃存改變或上層文件系統(tǒng)改變時僅僅通過改變映射機(jī)制就可以適應(yīng)。

在FTL層之上添加的編碼轉(zhuǎn)換層，用戶提供不同重要性的數(shù)據(jù)可靠度和壽命的參數(shù)，據(jù)此提出一種設(shè)計，選取相應(yīng)的編碼。以編碼復(fù)雜度最小，且空間利用率最大為原則，選取的編碼方法，編碼長度與糾錯位數(shù)確定編碼，以此保證對數(shù)據(jù)進(jìn)行容錯、糾錯，以滿足存儲數(shù)據(jù)可靠性的需求。改進(jìn)后的閃存存儲結(jié)構(gòu)如圖2所示。

圖2 改進(jìn)后的閃存存儲結(jié)構(gòu)圖

其中根據(jù)壽命可靠度求得其需要糾錯位數(shù)與分組數(shù)據(jù)的長度范圍，若糾錯位為1 bit，則用漢明碼，多位則用BCH碼。若為BCH碼，則需要據(jù)其空間利用率確定分組長度。

2 編碼的確定方法

編碼的確定方法示意圖3所示。

圖3 編碼的確定方法示意圖

系統(tǒng)在規(guī)定的條件下和規(guī)定的時間內(nèi)，完成規(guī)定功能的概率為系統(tǒng)的可靠度函數(shù)。在此場景中，可靠度函數(shù)即為數(shù)據(jù)不失效的概率。在空間環(huán)境中，由于單粒子效應(yīng)，會引起單粒子翻轉(zhuǎn)。而單粒子翻轉(zhuǎn)為影響星載存儲器數(shù)據(jù)可靠性的最主要因素，同一個字節(jié)出現(xiàn)兩次以上單粒子翻轉(zhuǎn)的概率非常低。根據(jù)國內(nèi)外人士在空間環(huán)境高能粒子輻射研究監(jiān)測表明，單粒子出現(xiàn)單粒子翻轉(zhuǎn)各bit出現(xiàn)錯誤在時間上和存儲單元上都是離散的, 出現(xiàn)錯誤的空間分布隨機(jī)，且互不影響。每一位并未出現(xiàn)反轉(zhuǎn)的概率如下：

p(t)=e-λt

(1)

其中λ為失效率，t為使用時間。

由于各位出現(xiàn)位翻轉(zhuǎn)的情況互不影響，且只有0和1兩種情況。設(shè)編碼分組長度為n，編碼糾錯位數(shù)為j，則n位中未出錯的位數(shù)k=n-j。則此系統(tǒng)的可靠性滿足n中取k表決系統(tǒng)模型，記為k/n(G)。其中k/n(G)邏輯示意圖如圖4所示。

圖4 k/n(G)邏輯示意圖

圖4中，xn是每一位發(fā)生為翻轉(zhuǎn)的概率事件表示，則可計算發(fā)生j位錯誤的概率推導(dǎo)如下：

P(X=j)=1-R(t)=

(2)

其中，R(t)為系統(tǒng)可靠度。

算得可靠度R(t)應(yīng)該大于或等于用戶提供的可靠度，因為需要糾錯的位數(shù)不會很大，一般不會超過5。j的值可以從1開始進(jìn)行計算，由此，可以確定滿足條件R(t)的需要編碼糾錯的位數(shù)j與分組長度n的范圍。其中，j的選取原則為盡量選擇滿足條件值最小的，這樣可以降低編碼復(fù)雜度，n的選取遵循空間利用率r最大原則。

根據(jù)糾錯位數(shù)可以選擇編碼方法，當(dāng)出現(xiàn)單個錯誤時，應(yīng)選取漢明碼。因為其編譯碼結(jié)構(gòu)簡單，很容易實現(xiàn)，糾正一個錯誤的[n,k,d]分組碼，其中n為分組長度，k為信息長度，d為漢明距離。漢明碼為糾正單個錯誤的[n,k,3]碼，漢明碼滿足：

(3)

其中，m為某一素數(shù)，r為碼率。

BCH碼和RS碼都是糾正多個隨機(jī)錯誤的循環(huán)碼，但在糾正相同錯誤時，BCH碼所需冗余空間更小，即編碼后的碼長最短，出于對空間利用率的考慮，當(dāng)出現(xiàn)多個錯誤時，選取BCH碼進(jìn)行分編碼[9]。對于任意整數(shù)m(m>3)和j<2m-1，存在具有如下參數(shù)的二進(jìn)制BCH碼，信息包括長度為k,分組長度為n,能夠糾正j或小于j位的錯誤的任意組合。通常情況下，這種類型的碼標(biāo)記為[n,k,j]BCH碼。則其滿足以下條件：

(4)

其中，dmin為糾錯碼距，r為碼率。

在對編碼的選擇方式上，遵循編碼復(fù)雜度最低，空間利用率最大的原則。在選取糾錯位數(shù)時，以編碼復(fù)雜度最低為原則，選取滿足用戶可靠度的最小的糾錯位數(shù)，并確定編碼長度。由于漢明碼比BCH碼編碼復(fù)雜度更低，空間利用率更高，所以糾正1 bit錯誤滿足可靠度要求時，選用漢明碼。多位錯誤出現(xiàn)時選取BCH碼，而在選取BCH碼時，盡量滿足空間利用率最高的原則。根據(jù)空間利用率公式:

r=k/n

(5)

可計算漢明碼編碼長度越大空間利用率越高，而BCH碼，由式(2)可以計算:

r=1-21-m·m

(6)

由此可以確定分組長度。

3 實例分析

在某應(yīng)用場景中，空間環(huán)境中單粒子效應(yīng)對器件影響失效率λi=1×10-5/天，ECC校驗?zāi)苁故式档鸵粋€數(shù)量級，此時失效率λ=1×10-6/天。假設(shè)用戶所要存儲的數(shù)據(jù)為長期保存的數(shù)據(jù)，其VFS層輸入?yún)?shù)工作壽命為t=10年，可靠度R(t)≥0.99。由式(2)可知，十年每一位出現(xiàn)位翻轉(zhuǎn)的概率，由式(4)可得不同糾錯位數(shù)下，編碼長度與可靠度的關(guān)系如圖5所示。由圖5可知，編碼糾錯位數(shù)若為1 bit，則無法滿足可靠度0.99的要求，2 bit與3 bit都滿足可靠度要求，糾錯位數(shù)過大會增加編解碼的負(fù)擔(dān)，則選擇糾錯位數(shù)j=2 bit，確定此時編碼長度范圍為3

圖5 編碼長度與可靠度的關(guān)系圖

圖6 編碼長度參數(shù)與空間利用率的關(guān)系圖

由此可見，當(dāng)m=5時，空間利用率r最大，為68.75%，此時，n=31。由此可知在這種情況下，選取[31,21,2]BCH碼進(jìn)行編碼。

4 結(jié) 語

本文針對空間環(huán)境，在閃存轉(zhuǎn)換層之上增加了一個編碼轉(zhuǎn)換層，為用戶提供了一種屏蔽底層接口的基于編碼的數(shù)據(jù)可靠性提升方法。在FTL層上加編碼轉(zhuǎn)換層，可以在為用戶屏蔽底層接口的條件下，不影響文件系統(tǒng)的可移植性。而通過用戶對不同重要性的數(shù)據(jù)壽命、可靠度的需求，選取空間利用率最大，編碼復(fù)雜度最小的編碼方法。通過實例仿真分析，結(jié)果表明，本方法不僅滿足了可靠度和長壽命的需求，并在此基礎(chǔ)上最大限度地增加了空間利用率。

[1] 賈露娟, 李文新, 夏加高, 等. 星載嵌入式容錯文件系統(tǒng)的設(shè)計與實現(xiàn)[J]. 計算機(jī)技術(shù)與發(fā)展, 2015, 25(10): 49-53.

[2] 許浩, 李向陽, 劉泳. 星載嵌入式文件系統(tǒng)技術(shù)研究及實現(xiàn)[J]. 航天器工程, 2008 (5): 41-46.

[3] 張鈺, 鄭陽明, 黃正亮, 等. 皮衛(wèi)星星載計算機(jī)存儲模塊的容錯結(jié)構(gòu)設(shè)計[J]. 宇航學(xué)報, 2008, 29(6): 2057-2061.

[4] Choi M, Park N, Piuri V, et al. Reliability measurement of mass storage system for onboard instrumentation[J]. IEEE transactions on instrumentation and measurement, 2005, 54(6): 2297-2304.

[5] 李華, 賈振國. 基于 NAND FLASH 的大容量視頻存儲系統(tǒng)的設(shè)計[J]. 物聯(lián)網(wǎng)技術(shù), 2012, 2(2): 33-35.

[6] 陸游游, 舒繼武. 閃存存儲系統(tǒng)綜述[J]. 計算機(jī)研究與發(fā)展, 2013, 50(1):49-59.

[7] 張琦, 王林章, 張?zhí)?等. 一種優(yōu)化的閃存地址映射方法[J]. 軟件學(xué)報, 2014, 25(2):314-325.

[8] Li X, Chen J, Qin D, et al. Research and Realization based on hybrid encryption algorithm of improved AES and ECC[C]//Audio Language and Image Processing (ICALIP), 2010 International Conference on. IEEE, 2010: 396-400.

[9] 韓可, 鄧中亮, 黃建明. 高速層進(jìn)式 Nand Flash 差錯控制編碼[J]. 北京郵電大學(xué)學(xué)報, 2010, 33(3): 71-74.

[10] Chang Y H, Hsieh J W, Kuo T W. Endurance enhancement of flash-memory storage systems: an efficient static wear leveling design[C]// Proceedings of the 44th annual Design Automation Conference. ACM, 2007: 212-217.

THEDESIGNOFHIGHLYRELIABLESPACE-BORNEDATAENCODINGPROTECTIONBASEDONFTL

Cao Dandan1,2Chen Yong1Lin Baojun1

1(AcademyofOpto-Electronics,ChineseAcademyofSciences,Beijing100094,China)2(UniversityofChineseAcademyofSciences,Beijing100190,China)

Single event effects(SEE) has a significant impact on the reliability of stored data in long-term in-orbit spacecraft. To solve this problem, a design of adding an error correction code translation layer(ECCTL) was presented. It was on the flash translation layer(FTL), and could dynamically meet the data storage reliability. An encoding selecting method in ECCTL is proposed to minimum the complexity of the selected encoding according to the requirements of reliability and service life from users, which maximum the space utilization. The design could shield low-level interface to the user, and it could correct data errors, to meet the reliability needs of user, providing an important basis for the reliability design of spatial data storage.

Space-borne memory Flash translation layer Code conversion layer Error correction code

TP302.8

A

10.3969/j.issn.1000-386x.2017.10.025

2016-09-08。曹丹丹，碩士，主研領(lǐng)域：嵌入式系統(tǒng)可靠性設(shè)計，可靠數(shù)據(jù)存儲。陳勇，副研究員。林寶軍，研究員。