基于嵌入式文件系統的記錄數據快速存儲與檢索的研究

摘要：文章探討了基于嵌入式文件系統的記錄數據存儲和檢索的設計方法，首先簡單介紹了嵌入式文件系統的基本知識和實現原理，接著簡要概述Nor Flash和Nand Flash區別，針對嵌入式系統中對文件系統的可靠性以及訪問存儲速度的特殊要求，重點介紹本研究課題的整體設計方案、映射表原理和鏈表原理，以及利用映射表和鏈表來實現記錄數據快速存儲和檢索的設計原理。

關鍵詞：快速存儲；快速檢索；文件系統；嵌入式系統；映射表

中圖分類號：TP317 文獻標識碼：A文章編號：1009-2374（2012）04-0109-03

隨著嵌入式技術的發展以及在各種電子產品中的廣泛應用，數據存儲管理已經成為嵌入式系統中一個重

要而深遠的研究課題，由此誕生了嵌入式文件系統。

嵌入式文件系統是嵌入式系統中重要組成部分，它構成了嵌入式系統上所有數據基礎，是系統中龐大復雜且又是最為基本和重要的資源。那么如何在文件系統上實現用戶記錄數據的快速可靠存儲與檢索是本文的研究重點。

一、文件系統定義

文件系統（File System）是系統的一個重要組成部分，通過對所管理的存儲空間的抽象，向用戶提供統一的、對象化的訪問接口，屏蔽對物理設備的直接操作和資源管理。從系統角度來看，文件系統是對文件存儲器空間進行組織和分配，負責文件的存儲并對存入的文件進行保護和檢索的系統。具體地說，它負責

為用戶建立文件，存入、讀出、修改、轉儲文件，控制文件的存取，當用戶不再使用時刪除文件等。

二、嵌入式文件系統

嵌入式文件系統中，Flash作為一種流行的存儲設備，Flash存儲器具有速度快、容量大、成本低等很多優點，因此大部分嵌入式系統都是把文件系統建立在Flash存儲器之上。

Flash存儲器主要有Nor Flash和Nand Flash兩種類型。目前，針對Nor Flash設計的文件系統JFFS/JFFS2在嵌入式系統中已得到廣泛的應用；隨著Nand作為大容量存儲介質的普及，基于Nand閃存的文件系統YAFFS(Yet Another Flash File System)正逐漸被應用到嵌入式系統中。

Nor屬于芯片內執行(XIP, eXecute In Place)的讀取，和我們常見的SDRAM的讀取是一樣，用戶可以直接運行裝載在Nor Flash里面的代碼，Nand Flash沒有采取內存的隨機讀取技術，它的讀取是以一次讀取一塊的形式來進行的，通常是一次讀取512個字節，采用這種技術的Flash比較廉價，用戶不能直接運行Nand Flash上的代碼。

針對Flash的特點，文件系統設計時還需要重點考慮Flash的損耗平衡、糾錯和壞塊處理問題。通常Nand中每個塊的最大擦寫次數是一百萬次，而Nor的擦寫次數是十萬次。如果某塊擦除次數超過壽命次數，容易導致壞塊。所謂壞塊并不是整個塊都壞了，可能只是塊中一位或某幾位損壞。Nand器件中的壞塊在出廠就有，且是隨機分布的。Nor正常不存在該問題。Nand器件需要對介質進行初始化掃描以發現壞塊，并將壞塊標記為不可用。所有Flash器件都受位交換現象的困擾，一位的變化可能不很明顯，但是如果發生在一個關鍵文件上，這個小小的故障可能導致系統停機。理論上Nand比Nor更容易受到影響。

由于這些特殊性，所以在Flash這樣的設備上建立文件系統以及在文件系統上實現記錄數據存儲和檢索的方法將直接影響嵌入式系統的運行性能和客戶體驗，具有深遠的研究意義。

三、設計方案

（一）設計說明

文件系統操作是以文件為單位，從系統角度來看，文件系統是對文件存儲器空間進行組織和分配，負責文件存儲并對存入的文件進行保護和檢索的系統。具體地說，它負責為用戶建立文件，存入、讀出、修改、轉儲文件，控制文件的存取，當用戶不再使用時刪除文件等操作。

根據文件系統的以上原理，本設計以文件為存儲體對象，同時分配有一個與文件長度相等的映射內存，在映射內存上構建記錄的存儲結構，所有存儲、檢索、刪除等操作首要都是在映射內存中完成，只有在需要更新時候才需要將部分數據更新到文件，避免頻繁且大數據量讀寫文件，實現記錄數據的快速存儲與檢索。

（二）結構圖

（三）存儲結構

記錄的存儲是以文件為存儲體對象，因此需要在文件的映射內存中構建存儲結構，如圖1所示，存儲結構包括：頭信息、映射表和記錄區組成。頭信息主要用來存儲記錄相關信息，如總記錄容量、已存記錄數，剩余記錄容量，鏈表信息等信息；映射表主要是描述記錄與位置編號之間的關系；記錄區就是用來存儲真正的記錄數據。

（四）頭信息

頭信息主要用來存儲記錄相關信息，如文件大小、總記錄容量、已存記錄數、剩余記錄容量、記錄域信息、記錄鏈表信息、空閑鏈表信息等信息，如圖2所示。通過頭信息可以快速獲取當前記錄文件的信息，以便快速統計和存儲操作。

（五）映射表和鏈表

映射表主要是描述記錄與位置編號之間的關系，以及通過鏈表的方式構建記錄與記錄編號之間的關系，如圖3所示，映射表是以鏈表節點為單位組成的，鏈表節點通過鏈表的方式串接起來。

鏈表主要用于管理記錄數據，每一個記錄就是一個小數據塊單元，用鏈表將這些單元串接起來。鏈表有鏈表節點，節點編號對應一個記錄位置編號，每個節點信息分為2部分，包含前向指針和后向指針，前向指針填充當前節點的前一個記錄位置編號，后向指針填充當前節點的后一個記錄位置編號（這里所指的前一個和后一個是邏輯上意義，非物理上排列）。

記錄位置編號：是指記錄區各個記錄的位置編號，如有N個記錄，從編號從1-N。

鏈表節點編號：鏈表節點編號與記錄位置編號一樣，是一一對應的。

記錄編號：是指一個記錄在鏈表中的邏輯位置，也就是該記錄屬于記錄鏈表的從鏈表頭開始的第幾個節點。

從頭信息可以看出，有2個鏈表信息（即2條鏈表）：記錄鏈表信息和空閑鏈表信息，記錄鏈表是將已存儲的記錄串接起來，空閑鏈表是將空閑的記錄串接起來；記錄鏈表信息的前向指針指向0，后項指針指向第1個記錄編號的記錄位置編號（鏈表節點編號），該鏈表節點編號所對應鏈表節點信息的后項指針又指向下一個記錄位置編號（鏈表節點編號），直到結束；空閑鏈表信息的前向指針指向0，后項指針指向第1個空閑記錄編號的記錄位置編號（鏈表節點編號），該鏈表節點編號所對應鏈表節點信息的后項指針又指向下一個記錄位置編號（鏈表節點編號），直到結束；。

計算記錄在映射內存中的地址：根據記錄編號去推算記錄鏈表信息后項指針，得到記錄位置編號，根據（（記錄位置編號-1）×記錄長度）得到記錄地址偏移量，（記錄地址偏移量+映射內存地址）得到記錄在映射內存中的地址。

（六）記錄區和域信息

記錄區就是用來存儲真正的記錄數據，因此記錄區將劃分成等分的記錄單元，每個記錄單元存儲一個記錄數據，每個記錄數據可由多個數據域組成，如排序域等，通過排序域，可以將記錄按照指定的規則進行排序，具體由頭信息字段中域信息決定，如圖4

所示。

域信息包括：域個數和各域描述：

域個數：用于表示記錄所組成的域個數；

域描述：用于描述記錄的各域組成，以及每個域的屬性和最大長度；域屬性可參考圖5所示位圖表示。

（七）記錄操作

通過以上原理介紹,可以快速進行記錄數據的存儲、刪除、查找等操作，因為記錄數據是通過映射表和鏈表來管理，通過映射表和鏈表檢索就可以快速定位記錄數據，無需去讀取實際記錄數據，考慮到數據存取的效率，每一個記錄文件都對應有一個與之大小相等映射內存，文件中的數據與內存中的數據是同

步的。

當讀取一個記錄數據時，可以直接訪問內存中的內容，而無需去訪問文件，提高數據讀取效率。

當存儲一個記錄數據時，只需要通過空閑鏈表獲取一個空閑記錄位置編號，根據記錄位置編號計算記錄所在映射內存中地址，將數據存儲到所在地址，接著將該鏈表節點掛接到記錄鏈表中，并支持按指定的域排序，更新記錄數，最后將內存中的數據更新到文件中，當然無需將整個內存數據更新到文件中，只需要更新頭信息、映射表和該記錄數據，大大提高文件更新速度，同時降低Flash存儲器的擦寫次數，延長產品的壽命。

當刪除一個記錄數據時，只需要通過記錄鏈表查找到鏈表節點，刪除記錄鏈表中該記錄節點，接著掛接到空閑鏈表中，更新記錄數，最后將內存中的數據更新到文件中，當然無需將整個內存數據更新到文件中，只需要更新頭信息、映射表，大大提高文件更新速度，同時降低Flash存儲器的擦寫次數，延長產品的壽命。

當檢索一個記錄數據時，只需要通過記錄鏈表查找到鏈表節點，獲取記錄位置編號，根據記錄位置編號計算記錄所在地址，接著根據域信息，判斷該記錄是否為符合要求的記錄，如此將可快速找到需要的記錄。

四、軟件架構

數據庫式存儲驅動模塊實現結構化的數據記錄在文件系統上的存取，并在此基礎上實現數據記錄的排序、插入、增加以及刪除等功能，該程序模塊的軟件框圖如下圖6所示。每種數據庫占用一個文件，每一個文件都對應有一個與之大小相等映射內存，文件中的數據與內存中的數據是同步的，當應用層需讀/寫數據庫文件時，均要通過映射內存進行中轉；即寫數據庫文件前需先將數據保存在映射內存中，再從映射內存寫回數據庫文件；反之，讀數據記錄時只需要讀取映射內存中的數據。

驅動對上層應用程序提供了增加記錄、刪除記錄、插入記錄等API接口，屏蔽驅動實現細節，同時上層應用程序可以通過數據庫注冊信息表注冊多個文件及文件信息，底層驅動通過數據庫注冊模塊獲取應用層注冊的文件信息來實現多個文件管理。

五、結語

本研究課題提供了一種嵌入式系統中數據存儲和管理的方法，該方法不僅適用于以文件系統文件為存儲對象的嵌入式系統，對于直接以Flash存儲器為存儲對象的嵌入式系統也具有較高指導意義，只要將對文件讀寫操作更換為對Flash的讀寫操作。

參考文獻

[1] 嚴蔚敏，吳偉民．數據結構（C語言版） [M]．清華大學出版社，2011．

[2] 杜春雷．ARM體系結構與編程[M]．清華大學出版社，2010．

[3] JEAN J.ABROSSE著，邵貝貝譯．UC/OS-II源碼公開的實時嵌入式操作系統[M]．中國電力出版社，2001．

[4]SST公司Nor Flash芯片手冊．SST Nor Flash Datasheet．

[5]SUMSUNG公司Nand Flash芯片手冊，Sumsung Nand Flash Datasheet．

作者簡介：葉德焰，廈門雅迅網絡股份有限公司中級工程師，研究方向：嵌入式文件系統。

（責任編輯：劉 艷）