張 藝 張重陽

（南京理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

人民幣冠字號碼管理指的是對錢幣的身份編號（冠字號碼）進(jìn)行記錄、存儲和分析。冠字號碼的查詢能助推貨幣政策的貫徹落實(shí)和實(shí)施，使銀行與客戶責(zé)任清晰，有效抑制洗錢、行賄、偷稅等違法行為，及時發(fā)現(xiàn)問題鈔票，為執(zhí)法機(jī)關(guān)提供服務(wù)［1］。冠字號碼在錢幣的流通過程中扮演著非常重要的角色。在經(jīng)濟(jì)飛速發(fā)展的今天，銀行業(yè)每天都會產(chǎn)生數(shù)量巨大的冠字號碼信息，這對傳統(tǒng)的人民幣冠字號管理模式形成了很大的壓力與挑戰(zhàn)。目前各大銀行冠字號碼數(shù)據(jù)需要集中到總行管理，支持至少三個月的全行數(shù)據(jù)。

冠字號碼數(shù)據(jù)是一種海量流數(shù)據(jù)，具有體量大、多維度、更新速度快等特點(diǎn)。由于現(xiàn)在銀行業(yè)的發(fā)展，海量的冠字號碼數(shù)據(jù)會隨著時間序列連續(xù)產(chǎn)生。具有良好擴(kuò)展性的HBase分布式數(shù)據(jù)庫適合存儲海量的冠字號碼數(shù)據(jù)。但是由于HBase的設(shè)計特點(diǎn)，在數(shù)據(jù)的插入與查詢實(shí)時性方面還有待提高，其原因?yàn)?/p>

1）實(shí)時數(shù)據(jù)插入效率問題。在HBase中，region是數(shù)據(jù)存儲的基本單位。而面對海量時序數(shù)據(jù)時，如果某個時間段內(nèi)數(shù)據(jù)特別大，數(shù)據(jù)則會按字典序依次插入某個region中，當(dāng)這個region達(dá)到預(yù)設(shè)的閾值時，會觸發(fā)split操作。而大量的split操作對數(shù)據(jù)插入效率影響很大。

2）多維數(shù)據(jù)查詢效率問題。HBase采用的是鍵值對模型，對主鍵有著良好的查詢效率。但是在多維度冠字號碼的實(shí)際查詢中，往往會根據(jù)在一定時間間隔內(nèi)去查詢某些條件，這種多維范圍查詢需要scan表中多個區(qū)域，消耗的代價很大。

為了解決這一問題，本文結(jié)合分布式數(shù)據(jù)庫HBase與具體的冠字號碼數(shù)據(jù)提出了一種基于時間序列的多維索引結(jié)構(gòu)MT-index（Multi-dimensional index based on Time）。

2 相關(guān)工作

近年來，云計算技術(shù)的得到了學(xué)術(shù)界與工業(yè)界的廣泛關(guān)注。而NoSql作為云平臺中的分布式數(shù)據(jù)庫也應(yīng)用于越來越多的地方，這也推動了云數(shù)據(jù)管理索引技術(shù)［2］的發(fā)展。文獻(xiàn)［3］最早提出了在云平臺中使用索引技術(shù)，提出了一種在云環(huán)境中具有兩層索引的計算框架。文獻(xiàn)［4］提出了一種在主存建立列數(shù)據(jù)索引的方法?，F(xiàn)主要的研究分為二級索引技術(shù)與全局局部索引結(jié)合的二層索引方式。

二級索引是一種常用的索引技術(shù)，主要應(yīng)用于鍵值存儲的云數(shù)據(jù)數(shù)據(jù)庫系統(tǒng)中，如HBase。目前基于二級索引的方案主要有ITHBase、IHBase以及CCIndex［5］。其中，ITHBase與IHBase是開源的實(shí)現(xiàn)方案，其原理是索引表存放索引列與原表的鍵值信息，查詢時先通過索引表得到鍵值再根據(jù)鍵值去原表查詢數(shù)據(jù)。然而查詢索引表時得到的鍵值是大量隨機(jī)的，去原表查詢時也需要通過大量隨機(jī)查詢才能得出查詢結(jié)果。為此，ZOU等提出了互補(bǔ)聚簇式索引，稱為CCIndex，CCIndex的方法是把數(shù)據(jù)的詳細(xì)信息也放在索引表中，減少了大量的隨機(jī)查詢，減少了查詢時間，但是會造成索引表空間的增大。CCIndex還給出了一種查詢優(yōu)化機(jī)制以支持多維查詢。二級索引實(shí)現(xiàn)簡單，維護(hù)代價較低，但是多維查詢效率低而且空間冗余大。

文獻(xiàn)［6］中提出了一種動態(tài)多維索引框架，先通過八叉樹對云空間進(jìn)行索引，再使用跳表隨機(jī)訪問層次化的八叉樹索引，實(shí)現(xiàn)了多維查詢，范圍查詢，動態(tài)索引縮放等。文獻(xiàn)［7］提出了多種云索引方案，分別為CAN組織所有節(jié)點(diǎn)，R-樹索引節(jié)點(diǎn)內(nèi)數(shù)據(jù)；集中式R-樹索引全局，KD-樹索引節(jié)點(diǎn)；Chord覆蓋網(wǎng)絡(luò)并使用MX-CIF索引本地。文獻(xiàn)［8］提出了一種MapReduce框架下高維數(shù)據(jù)近似查詢方法。使用MapReduce任務(wù)并行處理的優(yōu)勢將整個數(shù)據(jù)集均勻的劃分到集群中的各個計算節(jié)點(diǎn)，基于劃分的方法構(gòu)建分布式雙層索引。但該方法針對的數(shù)據(jù)集比較穩(wěn)定，沒有考慮索引的更新。文獻(xiàn)［9］提出的A-Tree索引是云環(huán)境下適合點(diǎn)查詢與范圍查詢的分布式多維數(shù)據(jù)索引，A-Tree通過R-Tree實(shí)現(xiàn)索引，但R-Tree的缺點(diǎn)是有很多“重復(fù)覆蓋”的區(qū)域，為此通過Bloom過濾器來選擇查詢區(qū)域。但是由于Bloom過濾器的局限性，當(dāng)數(shù)據(jù)量越大時出現(xiàn)誤判的概率也越大。文獻(xiàn)［10］提出了一種基于改進(jìn)四叉樹的空間劃分方法，再使用Hilbert曲線進(jìn)行局部多維索引。這種索引方法高效的實(shí)現(xiàn)了多維查詢，但構(gòu)建效率復(fù)雜。而如KR+-索引［11］、HQ-Tree［12］、DQuadtree［13］這些多維索引框架都基于經(jīng)典的空間數(shù)據(jù)索引，缺點(diǎn)是空間冗余較大。

3 MT-index

對于使用HBase存儲實(shí)時流數(shù)據(jù)，如果當(dāng)某個時間段數(shù)據(jù)量過大時很容易出現(xiàn)數(shù)據(jù)熱點(diǎn)問題，為了減少數(shù)據(jù)熱點(diǎn)的影響，一般的解決方式是為其建立索引，使得數(shù)據(jù)不會只集中存儲在分布式集群中的某個節(jié)點(diǎn)內(nèi)，而是分散的存入每個節(jié)點(diǎn)中。但是在插入數(shù)據(jù)的同時構(gòu)建索引，對于數(shù)據(jù)插入的實(shí)時性也有一定的影響。因此，為了解決這一問題，MT-index將索引層劃分為全局的粗粒度索引與本地的細(xì)粒度索引，數(shù)據(jù)在插入的時候先按粗粒度索引方式進(jìn)入預(yù)先的分區(qū)中并只對粗粒度索引進(jìn)行維護(hù)，等待數(shù)據(jù)入庫后再進(jìn)行細(xì)粒度索引的建立。這樣的方式在一定程度上緩解了插入實(shí)時性的問題。同時，HBase采用Key-Value的形式進(jìn)行存儲，這種模式只提供了鍵值的快速查詢，對于非鍵值的查詢操作只能使用scan操作，其效率在海量冠字號系統(tǒng)中是不能接受的?，F(xiàn)實(shí)中冠字號碼數(shù)據(jù)的查詢往往是涉及多個查詢條件，比如查詢某段時間內(nèi)某人辦理的業(yè)務(wù)涉及的冠字號碼等，如果是按照HBase提供的過濾器進(jìn)行查詢，則查詢過程消耗太大。為此，在粗粒度索引中使用時間序列與空間曲線結(jié)合的方式對數(shù)據(jù)進(jìn)行劃分并將多維查詢條件降為一維，減少索引元所占空間，使用較少的存儲空間實(shí)現(xiàn)了高效的多維查詢。

3.1 整體框架

整體框架如圖1所示，整個系統(tǒng)由數(shù)據(jù)導(dǎo)入模塊、HBase分布式數(shù)據(jù)庫模塊、索引模塊以及查詢模塊構(gòu)成。數(shù)據(jù)導(dǎo)入模塊負(fù)責(zé)將銀行網(wǎng)點(diǎn)隨時產(chǎn)生的數(shù)據(jù)導(dǎo)入到云存儲空間的HBase中；HBase分布式數(shù)據(jù)庫模塊負(fù)責(zé)將導(dǎo)入的數(shù)據(jù)按鍵值對的形式存入HBase表中，產(chǎn)生的數(shù)據(jù)包括交易流水、交易內(nèi)編碼、冠字號碼、時間、操作代碼、銀行網(wǎng)點(diǎn)編號、機(jī)器號、卡號等字段。同時，HBase也負(fù)責(zé)存儲索引模塊導(dǎo)入的索引表；索引模塊負(fù)責(zé)構(gòu)建與維護(hù)索引數(shù)據(jù)，先通過時間序列與空間曲線對數(shù)據(jù)分區(qū)后進(jìn)行粗粒度的全局索引，當(dāng)數(shù)據(jù)存入對應(yīng)的region之后，再采用二級索引的策略構(gòu)建本地索引；查詢模塊根據(jù)查詢條件先去查詢粗粒度的全局索引，確定數(shù)據(jù)所在的region，再根據(jù)本地的細(xì)粒度索引查詢出具體數(shù)據(jù)。

圖1 系統(tǒng)整體框架

3.2 索引的設(shè)計與實(shí)現(xiàn)

3.2.1 索引結(jié)構(gòu)

索引結(jié)構(gòu)如圖2所示，索引包括了粗粒度索引以及region中細(xì)粒度的二層索引。

1）索引的第一層使用B+樹將時間序列轉(zhuǎn)為索引。由于隨著時間變化會不斷的有冠字號碼數(shù)據(jù)更新進(jìn)入系統(tǒng)，所以在本文中，將時間分為若干個時間段｛［T0，T1］，［T1，T2］，…，［Ti-1，Ti］｝，這些時間段沒有重疊，相加之后為系統(tǒng)需要的時間量。時間段會不斷的后移，在規(guī)定范圍之外的時間段就將其從索引中刪除。使用B+樹索引時間序列，每個葉子節(jié)點(diǎn)指向?qū)?yīng)下層空間曲線所表示的區(qū)域。

2）使用Z曲線［14］對多維數(shù)據(jù)進(jìn)行降維并且分區(qū)。Z曲線是一種通過隔行掃描二進(jìn)制數(shù)字的比特到一個字符串來實(shí)現(xiàn)降維，并將產(chǎn)生的Z區(qū)域按升序填充到線性曲線中?？臻gZ曲線通過降維后分區(qū)，將源數(shù)據(jù)分為連續(xù)的Z空間，每個Z空間都對應(yīng)著曲線上的一個Z值。在冠字號碼數(shù)據(jù)中，對卡號與銀行網(wǎng)點(diǎn)代碼、冠字號碼這三維構(gòu)建多維索引，其意義是查詢某段時間內(nèi)，某個用戶在某個網(wǎng)點(diǎn)取出或者存入的某張錢幣。在查詢時，可以將查詢條件完整輸入也可以輸入個別條件。

3）region中數(shù)據(jù)的本地索引。本文中在數(shù)據(jù)插入HBase表中并且維護(hù)完上兩層索引之后，會構(gòu)建本地索引，本地索引類似開源框架IHbase，其目的是通過查詢條件定位到某一個區(qū)域后，通過二級索引的方式能快速地查詢出數(shù)據(jù)，避免掃描操作。由于這層索引是細(xì)粒度的，相對于上一層構(gòu)建消耗較大，因此選擇在當(dāng)前時間序列結(jié)束后再對前一個時間段的數(shù)據(jù)構(gòu)建本地索引。

圖2 索引結(jié)構(gòu)

圖3 二維Z曲線中范圍查詢

3.2.2 數(shù)據(jù)分區(qū)

HBase中基本的存儲單位是region，每個region都有其對應(yīng)的regionServer維護(hù)。本文的索引方式是時間序列與空間曲線相結(jié)合的方式，若直接按照這兩點(diǎn)設(shè)計RowKey，可能會造成熱點(diǎn)數(shù)據(jù)問題，數(shù)據(jù)會不斷地寫入同一個region中，當(dāng)數(shù)據(jù)量超過了region的閾值便會調(diào)用split方法，數(shù)據(jù)量增長很快的同時split操作的次數(shù)也會很多，對于插入性能影響很大。在region中startKey和endKey是兩個非常重要的元素，決定了這個region中RowKey的范圍。所以在本文中采用了隨機(jī)散列與預(yù)分區(qū)結(jié)合的方法來確定startKey與endKey。因?yàn)镠Base中RowKey不能重復(fù)，所以在系統(tǒng)中使用時間序列與交易內(nèi)編碼結(jié)合的方式生成RowKey。1）先預(yù)測并隨機(jī)產(chǎn)生未來一段時間序列內(nèi)會生成的RowKey，使用MD5的方式轉(zhuǎn)為hash在轉(zhuǎn)為bytes，并將這個值拼接在原RowKey之前，升序后放在一個集合之中。2）根據(jù)預(yù)分區(qū)region的個數(shù)，對整個集合分割，產(chǎn)生對應(yīng)的splitKey。產(chǎn)生的splitKey即可作為region的起始與結(jié)束位置。3）使用HBaseAdmin中的createTable方法指定預(yù)分區(qū)。這樣可以避免熱數(shù)據(jù)插入問題以及大量的region的分裂操作，提高效率。當(dāng)預(yù)分區(qū)的時間序列結(jié)束前，系統(tǒng)會產(chǎn)生下一階段預(yù)分區(qū)的結(jié)果作為下個階段存儲數(shù)據(jù)的region。

3.3 索引效率分析

MT-index多維索引是一種以空間換取時間效率的方式，通過全局的粗粒度索引與本地的細(xì)粒度索引結(jié)合的方式提高數(shù)據(jù)插入以及多維查詢效率。本文使用這種方式的目的在于實(shí)現(xiàn)高效的多維查詢，現(xiàn)分析MT-index在多維查詢方面的效率。多維查詢分為多維點(diǎn)查詢和多維范圍查詢，在多維點(diǎn)查詢時，通過查詢條件的計算，能確切得到數(shù)據(jù)在空間曲線的某個對應(yīng)區(qū)域，查詢的范圍為一個區(qū)域，不存在效率的問題。而在多維范圍查詢時，所涉及到的Z區(qū)域較多，可能會造成無關(guān)區(qū)域的搜索問題。如圖3所示，在一個二維空間中，查詢范圍為（n1，n2），那么需要查詢的區(qū)域應(yīng)該是虛線框中的范圍，對應(yīng)的Z區(qū)域應(yīng)為1，3兩個區(qū)域，但在空間曲線上，則會按序查詢1，2，3三個區(qū)域，這就造成了無關(guān)區(qū)域的搜索，對效率產(chǎn)生了影響。為此，將B+樹與Z曲線結(jié)合，如圖4所示?？梢?，基于時間序列B+樹中非葉子節(jié)點(diǎn)是個三元組

由上面的分析可以得出，粗粒度的全局索引能快速地定位到數(shù)據(jù)所在的空間區(qū)域，盡量減少了無關(guān)區(qū)域的查詢。但是如果查詢所給的范圍很大，最終會有很多個區(qū)域需要查詢，由于在數(shù)據(jù)處理中已經(jīng)進(jìn)行了預(yù)分區(qū)處理，每個region中數(shù)據(jù)量不會有很大偏差，則每個空間Z區(qū)域也不會有很大偏差，符合并發(fā)執(zhí)行的條件，因此使用MapReduce［15］進(jìn)行并發(fā)搜索，提高多維范圍搜索效率。同時，在每個region中，會為其中的數(shù)據(jù)建立二級索引，即將查詢條件作為鍵值，本文中采用用戶卡號，該層索引實(shí)現(xiàn)比較簡單，具體操作為在本地的二級索引表中按條件過濾出對應(yīng)源數(shù)據(jù)的主鍵，目的是避免全區(qū)域的scan操作。

圖4 B+樹與Z曲線結(jié)合結(jié)構(gòu)圖

4 實(shí)驗(yàn)論證

4.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)平臺由Hadoop-2.7.3集群組成，搭建于4個節(jié)點(diǎn)之上，每個節(jié)點(diǎn)上搭建了14.04的64位Ubuntu系統(tǒng)，每個節(jié)點(diǎn)CPU為Inter（R）Core（TM）i5，3.20Hz，內(nèi)存為4G。Hadoop集群中有一個主節(jié)點(diǎn)與三個從屬節(jié)點(diǎn)，分別提供管理與存儲功能。使用的數(shù)據(jù)庫為HBase-1.2.3，在HBase環(huán)境中有HMaster與HRegionServer兩個角色。本實(shí)驗(yàn)中將HMaster部署在主節(jié)點(diǎn)，其余節(jié)點(diǎn)作為從屬節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)采用冠字號碼記錄信息，記錄信息包括交易流水、冠字號碼、時間、銀行網(wǎng)點(diǎn)號、網(wǎng)點(diǎn)機(jī)器號、卡號。HBase表中數(shù)據(jù)格式如表1所示。數(shù)據(jù)通過仿真生成，模仿了100個網(wǎng)點(diǎn)三個月生成的業(yè)務(wù)量。每筆業(yè)務(wù)都有其對應(yīng)的冠字號碼集，截取100萬，300萬，600萬，1000萬數(shù)據(jù)進(jìn)行插入實(shí)驗(yàn)以及1000萬，3000萬，6000萬，10000萬數(shù)據(jù)量進(jìn)行查詢實(shí)驗(yàn)。插入實(shí)驗(yàn)的數(shù)據(jù)是直接調(diào)用HBase中的API而查詢實(shí)驗(yàn)的數(shù)據(jù)則是使用HBase提供的Bulk-Load方式批量導(dǎo)入。在實(shí)驗(yàn)中，使用MT-index與CCIndex以及分布式B+樹進(jìn)行比較。

4.2 數(shù)據(jù)插入實(shí)驗(yàn)

在該實(shí)驗(yàn)中，分別對三種索引結(jié)構(gòu)進(jìn)行四組不同數(shù)據(jù)量的數(shù)據(jù)插入，統(tǒng)計對于插入一定數(shù)量的流數(shù)據(jù)，系統(tǒng)需要消耗的時間。由實(shí)驗(yàn)結(jié)果（圖5）表明，對于數(shù)據(jù)插入方面，三種索引結(jié)構(gòu)的時間都是隨著數(shù)據(jù)量的增加呈現(xiàn)線性增長。當(dāng)數(shù)據(jù)量較小的情況下，MT-index消耗的時間要略大于CCIndex以及分布式B+樹，其原因?yàn)镸T-index需要計算空間曲線Z值以及計算預(yù)分區(qū)，這些時間消耗在總時間中所占比重較大。而當(dāng)數(shù)據(jù)量變大后，MT-index的插入時間則小于CCIndex與分布式B+樹。實(shí)驗(yàn)結(jié)果表明，MT-index在大量的流數(shù)據(jù)情況下，具有較好的數(shù)據(jù)插入性能。其原因在于對于多維索引，分布式B＋樹會根據(jù)多個屬性建立多個索引表，同樣CCIndex的索引冗余很大，構(gòu)建需要較多的時間。而MT-index則采用了Z曲線將多維降為一維，只需要構(gòu)建一個索引表，且采用粗細(xì)粒度索引分離的方式，所以數(shù)據(jù)插入的性能更高。

圖5 數(shù)據(jù)插入耗時

4.3 數(shù)據(jù)查詢實(shí)驗(yàn)

數(shù)據(jù)查詢實(shí)驗(yàn)中，采用4組數(shù)據(jù)進(jìn)行查詢實(shí)驗(yàn)。分別從源數(shù)據(jù)中獲取100份范圍查詢數(shù)據(jù)，在MapReduce框架進(jìn)行連續(xù)實(shí)驗(yàn)，記錄完成時間，再取平均值作為該索引在該數(shù)據(jù)量下的查詢響應(yīng)時間。實(shí)驗(yàn)結(jié)果如圖6所示。相對于分布式B+樹與CCIndex，MT-index的查詢響應(yīng)時間更短。當(dāng)數(shù)據(jù)數(shù)據(jù)較小的時候，三種索引方式的查詢效率差不多，而當(dāng)數(shù)據(jù)量不斷增大，MT-index在查詢效率方面的優(yōu)勢是很明顯的。而且，查詢響應(yīng)時間受數(shù)據(jù)規(guī)模的影響較小。其原因是在MT-index這種索引模式下，最終要查詢的區(qū)域隨著數(shù)據(jù)量的增長變化并不大。所以MT-index具有高效的查詢效率。

圖6 查詢響應(yīng)時間

5 結(jié)語

本文基于HBase提出了一種冠字號碼數(shù)據(jù)的多維索引模型，為海量冠字號碼數(shù)據(jù)的存儲與查詢提供了方案。實(shí)驗(yàn)表明，該方法具有較好的插入、查詢效率，易于實(shí)現(xiàn)，受數(shù)據(jù)規(guī)模影響不大，能夠適用于數(shù)據(jù)規(guī)模不斷增長的實(shí)時冠字號碼數(shù)據(jù)查詢系統(tǒng)。本文的工作重點(diǎn)在于對索引的構(gòu)建，目的是提高實(shí)時數(shù)據(jù)插入與查詢的性能。對于解決海量冠字號碼問題具有重要的參考價值和實(shí)用意義。