基于NAND Flash的AFC嵌入式數據庫設計

王彬彬 蔣夢雅 侯博正

（1徐州地鐵運營有限公司， 徐州 221000；2江蘇建筑職業技術學院， 徐州 221000；3徐州地鐵運營有限公司， 徐州 221000）

引言:軌道交通自動售檢票（Automatic Fare Collection，AFC）系統是軌道交通運營管理的核心系統之一，實現售票、檢票、計費和統計等。

讀寫器是AFC系統的重要部件之一，用于實現對票卡的讀寫，在軌道交通AFC系統的終端設備中大量使用。隨著票務業務的發展，國內城市陸續使用業務內置型讀寫器來取代傳統讀寫器。業務內置型讀寫器是指將票卡處理流程程序集中到讀寫器內部，設備上位機只需發送業務操作命令（如進站、出站等），接受讀寫器返回的業務處理結果，業務操作流程由讀寫器獨立完成，讀寫器成為了獨立的票務處理終端。為了有效地對交易數據進行查詢和審計，AFC系統對讀寫器保存交易數據也提出了要求。讀寫器作為一種嵌入式設備，通常采用NAND Flash存儲器快速保存大量數據，但是NAND Flash寫入比讀取代價高，且擦除代價更高。

綜上，AFC系統數據存儲、索引建立和數據更新等問題的提出，使得研究基于NAND Flash的AFC嵌入式數據庫十分必要。

1 數據源

AFC系統中的數據類型眾多。包括交易數據、寄存器數據、狀態數據、收益管理數據、設備基本信息、各類參數和數據字典等。

1.1 本文主要數據及特點

本文討論的是經由業務內置型讀寫器處理的數據，主要有交易數據、黑名單和審計數據等。

（1）交易數據。讀寫器產生的交易數據保存在本地數據庫，定時通過網絡上傳給上位機設備，再由上位機設備上傳給AFC中心數據庫保存。

（2）黑名單。黑名單由AFC中心產生，通過上位機設備下發到讀寫器中。由讀寫器完成黑名單鎖卡、跟蹤等操作。

（3）審計數據。審計數據主要指一些票卡統計值，包括進站人數、刷卡次數和消費金額等。

由上可知，不同數據有著不同的特點。交易數據按順序產生，且與金額相關，必須保證每筆交易都不能錯漏，除了要求順序上傳外，還要求根據票卡號進行數據查詢。黑名單數據定期更新，相對靜態，且數量巨大，要求能供讀寫器快速查詢。審計數據的主要特點是更新頻繁。下面本文將對業務內置型讀寫器進行硬件設計。

1.2 業務內置型讀寫器硬件設計

目前AFC系統普遍使用業務內置型讀寫器，本文設計采用嵌入式技術的業務內置型讀寫器，其中32位CPU接口和NAND Flash存儲器、SDRAM存儲器組成處理器最小系統。

主要數據存放在NAND Flash存儲器上。非易失性RAM用以保存臨時重要數據，如日志數據庫；和變化頻繁的數據，如審計數據等。其硬件結構如圖1所示。

圖1 業務內置型讀寫器硬件結構圖

2 嵌入式數據庫設計

數據庫目前存在以硬盤介質為模型設計，沒有考慮到NAND Flash的特性等缺點。且嵌入式數據庫系統技術發展迅速，使用NAND Flash作為存儲介質的嵌入式數據庫，為實現均衡讀寫、減少擦寫次數、保證NAND Flash的使用壽命、提升訪問性能，本文將設計一種全新的嵌入式數據庫。

2.1 交易數據的存儲和索引

交易數據按順序產生，同時上傳也是按順序進行，且每筆都要更新，本文選擇交易票卡號和時間作為關鍵碼。由于 B+樹存儲特點與 AFC交易數據特點較吻合。此外，Hash通過計算來獲得地址，提高查詢的效率，因此，交易數據選擇B+樹上建立Hash索引。

如圖2所示，具有相同的Hash值的k在Hash表的同一項中用B+樹組織，B+樹的葉子節點用鏈表進行存儲。插入和查找操作最大時間復雜度為

圖2 Hash B+樹數據結構

交易數據以票卡號和時間作為關鍵碼，存放在B+樹的葉子節點中，存儲結構如圖3所示：

圖3 存儲結構圖

2.2 黑名單的存儲和索引

黑名單的特點是定期更新，主要進行查找操作。黑名單以票卡號作為關鍵碼。

哈希（Hash）桶方式，首先通過哈希函數將黑名單卡號字符串映射到桶哈希表的一個哈希桶。每一個哈希桶由一個或者少數幾個哈希塊鏈接而成。桶哈希表如圖4所示。

圖4 桶哈希表

字符串哈希算法較多，經過比選最終選用APHash函數，代碼如下：

哈希桶方式需要事先選定一個合適的桶數，即桶哈希表的項數，過大會浪費空間，過小則使每個桶的鏈變長而降低存取性能。由于AFC設備每種設備的狀態數量有數百個至上千個不等，因此，本哈希表的項數設定為100左右的素數：101。

使用APHash算法對系統常用的355個狀態標簽名進行散列后將散列值對100取模，得到其散點圖如圖5所示：

圖5 散點圖

2.3 性能分析

交易數據采用Hash表與B+樹相結合的索引方式，日志模型的B+樹比較適合寫入頻繁的數據庫應用，符合交易數據的特點。

3 結束語

本文在分析AFC系統交易數據、黑名單和審計數據特點的基礎上，并結合現有NAND Flash存儲技術，進行了嵌入式數據庫的設計，其中交易數據采用Hash表與B+樹相結合的索引方式。提高了AFC系統數據查詢與數據更新等的效率。

[1]何鐵軍，宋亞娜，王健，等. AFC業務內置型讀寫器研究與應用[J]. 都市快軌交通. 2011(01): 104-108.

[2]康亮，顧峰磊，戚正偉. 基于NAND Flash的嵌入式數據庫索引機制的改進[J]. 計算機應用與軟件. 2008, 25(7): 277-279.

[3]Wu C, Chang L, Kuo T. An efficient R-tree implementation over flash-memory storage systems[C]. ACM, 2003,17-24.