基于HBase的時態信息索引策略范文

本站小編為你精心準備了基于HBase的時態信息索引策略參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《廣東工業大學學報》2014年第二期

1時態信息在HBase的存儲模型

Hadoop是一個開源的云計算框架，向用戶提供系統底層細節透明的分布式基礎架構．Hadoop生態系統中的Commom、Avro、Chukwa、Hive、HBase等子項目提供了互補性服務或是核心層上提供了更高級的服務．HBase適于存儲松散型的非結構化數據，即是介于映射（key／value）和關系型數據之間的數據．其表索引由行關鍵字、列關鍵字和時間戳組成，表中的數據可以有多個版本（通過時間戳區分），并且能動態地實現數據列族的添加．不同于RDBMS具有豐富的數據類型和存儲方式，HBase只有簡單的字符串類型，所有的用戶所需的類型都額外自行處理獲得，同時由于HBase的非事務性，是通過犧牲一些高級的查詢能力以換取更好的在分布式環境下的性能，故不支持多表連接進行復雜的查詢操作，也沒有時態語義的約束．HBase向下提供了存儲，以分布式文件系統（HDFS）為底層框架，向上提供了運算，能使用MapReduce計算模式來并行處理大規模數據．對于電子醫療時態信息數據集R＝∑rk＝1Rk（k＝1，2，…，r）的存儲，在HBase中進行數據模型的構建：將時態數據所描述的對象（患者）的根本特征作為主鍵，即KeyRow，可表示為病人的姓名或編號ID；列族是對事務屬性的擴展性描述，能更詳盡地描述事物所抽象出來的各種屬性，HBase的靈活性可以實現對列族的自由添加．為了對臨床醫療數據的時態特性進行描述，本文引入時態列族用于記錄患者在就診過程不同時段內病況信息的時態屬性值，即Column：Temporal，它可以用時間點、時態區間或者時態集合作為時態信息的描述對象，本文基于具體醫療應用背景使用時態集合作為時態信息存儲的基本單元；對于病人信息的非時態屬性值的描述，可以通過添加列族Column：Notemporal實現，它可以用來描述患者的病癥、年齡、既往病史、用藥情況、主治醫生等其他信息，但這些信息對于不同的患者來說并不具備高度的一致性，若無相關聯的信息，則該列族中所對應的數據項可設置為空．為保證電子醫療數據的完整性，也可繼續動態添加類似的列族．構建以時態集合為醫療時態數據存儲單元的時態數據模型（Thbase）如表1所示．醫療信息中時態屬性值的表示方式由具體醫療背景決定．由于患者在診療活動中的時態信息往往由若干在時序上間斷的信息構成，比如病人發燒時間，可能僅僅某些天若干時段高燒，又如某些流行性疾病如傷寒、癲癇病等通常表現出反復發作的特性．因此為了兼顧信息的語義分析處理，采用時態集合作為醫療信息的時態屬性值的描述手段．時態集合是時間點和時態區間在時序上的疊加，相對于時間點和時態區間的單一表達性，它可根據對象在時態論域的多樣性特征變化更為靈活和精確體現出其時態性，適于診療信息對象整個病理周期的全程記錄，清晰明了，若將時態元素拆分通常不能滿足正確性、完備性需要，往往會失去時態語義；另一方面通過合并時間點和時態區間這兩種時態數據類型，在數據庫中進行海量信息存儲能夠最大限度地壓縮存儲空間并減少數據冗余．

2時態集合的聚類策略

由于Hadoop的分布式特征，數據是按分塊的形式存儲在集群的各個節點上．HBase將邏輯上很大的一張數據表在存儲實現時以一定的方式進行“切割”形成不同的區域，即時態信息存儲表根據行被分成了多個HRegions，每個HRegions又包含一個較大的數據集．若以列族作為查詢條件，只能根據行鍵從第一行數據開始查找，掃描全表直到查詢到相關的數據為止，這樣顯然是十分低效的．對于海量數據的快速檢索方法，目前的研究成果包括B樹及其變形樹的檢索，哈希檢索，分布式哈希表（DistributeHashTable，簡稱DHT）檢索等．因此結合Hadoop體系特性，本文采用分布式哈希表作為海量時態信息的索引方式．由于THBase模型以時態集合作為存儲對象，其數據結構較為復雜，直接在該類型的數據上構建索引難度較大．考慮到現階段較為成熟的空間索引模式更適于海量非結構化數據的組織，因此，本文首先需將時態數據向空間數據轉化，對以時態集合為存儲對象的時態信息進行空間映射，構造二維空間上的時態數據區域集，在此基礎上再作數據集劃分、數據的聚類操作，得到若干層次的時態數據域，并以這些時態數據域作為各級索引表的主鍵．

2．1時態集合的空間映射在HBase中，對于任意一條電子醫療時態記錄記錄時間的終點，且Ps≤Pe．由于作為時態信息描述對象的時態集合是由若干時間點和時態區間構成，結構較為復雜，對于任意DRt，其維度（包含的時間點和時態區間的數目）并不恒定，若對時態屬性進行索引構建，需簡化其表示方法．借鑒空間索引的實現方式，將其映射到二維空間，再以空間數據劃分方式實現聚類．定義1（時態數據區域）將時態屬性值映射到二維空間所得到的二維空間區域．任意的時態數據Rf、IjRf是時態集合DRt任意一個時間點或時態區間，以（0，0）為原點，時態集合中各時態區間起始點所代表的時間軸為X軸、各時態區間終止點所代表的時間軸為Y軸，建立二維空間上的XY垂直坐標系．（Ⅰ）對于時態區間IjRf＝［PRf，s，PRf，e］，PRf，s所在為橫坐標（X坐標），PRf，e所在為縱坐標（Y坐標）．那么，時態區間IjRf在空間坐標系中則可以表示為時態數據區域S（IjRf），該區域是由X≥PRf，s、Y≤PRf，e以及Y≥X共同圍成的區域構成．事實上，由于時態信息具有一定的粒度性，該區域包含若干獨立的、離散的時間點，如圖1所示．（Ⅱ）由于時間點可表示為起始時間與終止時間一致的時態區間，因此，時間點在二維空間上可表示為時態數據點．

2．2時態數據區域的劃分策略在設計HBase海量時態數據索引結構時，數據或數據空間的劃分是至關重要的環節，好的數據劃分策略會提高數據庫I／O吞吐性能及系統數據吞吐能力，從而提高整個系統的檢索性能．在將THBase中所有的時態集合映射為時態數據區域集合S（t）后，如何對已空間化的時態數據區域進行數據組織？針對時態數據區域S（t）結構復雜、數據量大以及數據之間存在著空間拓撲關系等特點，本文在K－均值聚類算法的基礎上，提出在分布式系統下的時態數據區域S（t）的數據劃分方案如下。

3基于HBase多級哈希索引表的設計

在分布式集群存儲系統中，數據的組織優化是提高存儲系統性能的有效方法之一．而索引是存儲系統重要的部分，它直接決定數據的存取效率，影響數據分析與應用效率．在HBase分布式存儲結構中，對時態信息構建索引可以極大地提高對HBase中數據的訪問速度，有效地避免對非主鍵的全表掃描所產生的巨大系統開銷．同時由于HBase“一次寫入多次讀取”的特點，并不需要頻繁進行表結構的更新和數據的添加、刪除操作，因此為海量時態信息存儲表建立索引是十分必要的．本文在分布式哈希表（DHT）的基礎上，提出THBase模型下的多級索引表DHT算法（tDHT）．設→D為THBase所存儲的時態集合值域，D代表時態記錄R的時態屬性值。對于多級哈希索引表構建，本文提出的tDHT算法將THBase時態列族Column：Temporal的時態屬性值進行聚類，并以此作為行鍵，即KeyRow，并以THBase的KeyRow作為列族重新構造數據表．對于THBase時態信息的檢索，索引結構可實現根據列值快速地定位相關數據所在的行，由此構成THBase的一級索引，再以一級索引表為原表，按照上述方式構建多級索引表．這樣，各級HBase索引表除了以上一級的時態數據子區域作為KeyRow之外，僅需要再構建時態索引列族Column：TIndex作為新的時態索引列族即可．如此，索引表結構以及所包含的信息比原表要精簡得多，訪問索引表所消耗的時間也較少．

3．1一級索引表結構的設計根據THBase模型以及HBase存儲結構的特點，首先構建HBase的一級時態索引結構TIndex－1．以時態數據區域聚類生成的一級時態子區域r（1）i（i＝1，2，…，K）為KeyRow，即TIndex1的主鍵，同時建立時態索引列族Column：Tindex，以THBase的主鍵KeyRow（患者編號）作為該列族的（Key，Value）取值．則構建的HBase一級索引表目錄如表2所示定義2（時態檢索域）將用戶的時態檢索請求（通常是時態區間或時態集合）按照上文所述的方式映射為時態數據域，稱為時態檢索域．索引表與原表通過原表的KeyRow（患者編號）建立映射關系．用戶進行時態檢索時，將時態檢索域分別與一級索引表的所有RowKey（一級時態子區域）進行運算：（Ⅰ）若兩者存在交集，則讀取列族TIndex1的值，獲取此值后以該值作為HBase時態信息存儲表（THBase）的KeyRow，讀取相應的時態信息；（Ⅱ）若不存在交集，則不再讀取該RowKey對應的列族TIndex1的值，時態檢索域與索引表的下一行RowKey值進行比較．

3．2多級索引表結構的設計采用多級哈希表索引可以進一步提升檢索性能．根據本文所提出的（tDHT）算法。當用戶提交涉及時態信息的查詢請求時，首先進入第N級的哈希索引表中快速檢索，根據時態檢索域與N級索引表KeyRow主鍵r（n）i的空間重疊性，若存在重疊區域，則掃描時態索引列族Column：TIndex，繼續判斷兩者是否存在交集，然后根據（Key，Value）中Key所對應的Value值進入N－1級哈希索引表，由此通過上一級索引表的時態索引列族與下一級索引表主鍵建立哈希映射關系，以時態檢索域與各級時態數據子區域r（n）i進行各層索引表的關聯條件判斷，以此類推直到獲取用戶需數據的地址信息并定位到數據為止．

4性能測試

搭建測試平臺進行多級分布式哈希表索引結構的性能驗證．本文采用HBase0941和Hadoop0210進行實驗，將其部署在5個物理計算機節點上，搭建Hadoop集群，其中1個節點作為Master節點，其余4個作為Slave節點．每臺PC機的系統參數配置為：CPU（Inter（R）Core（TM）i3M350＠227GHz）、RAM（400GB）和硬盤（500GB）．為了獲取更好的穩定性，實驗在Linux系統（ubuntu1104desktopi386）下進行，使用openssh實現系統內節點無密碼互訪．本文采用的是以時態集合方式進行重構的電子醫療時態數據，將其寫入到HBase中作為測試數據，并進一步對設計的不同N值的多級索引表tDHT算法與HBase按主鍵掃描方法進行查詢時間的性能比較．實驗中用來進行查找時間對比的基礎時態數據量分別為10萬、1000萬、2000萬和4000萬，由于HBase只能根據RowKey進行查詢，不支持對非主鍵（如列族）條件查詢．在獲取所要查詢的時態數據主鍵或是按照某些列族的屬性取值一致性的前提下，抽取、過濾所得時態列族的時態屬性值，通過并、交等操作完成Map／Reduce并行編程模式下的時態集合關系代數演算，實現對時態數據的查找．在不構建索引以及構建不同級數的分布式哈希索引表索引（N＝3，5）的時態數據檢索時間如表3所示．為了更直觀地展示實驗結果，繪制時態數據查找的時間對比折線如圖3所示．由表3、圖3的時態檢索的時間對比分析可知，相對于全表的條件查找，使用HBase進行存儲的分布式哈希表索引能較大程度地改善系統對于時態信息查詢的性能，特別是當時態數據量達到千萬級以上時，構建索引在查找時具有非常巨大性能優勢，能極大地縮短檢索所需時間；而索引級數N的取值不同，也在一定程度上影響時態檢索的性能，當數據量不大時，索引級數越高，各級索引表的數據量則較小，多表映射所造成的時間損耗抵消了部分由于更精細的數據集劃分帶來的優勢，N值的大小對索引性能的提升不夠明顯，但當存儲的時態數據量加大，各級索引表長度急劇增長時，索引結構tDHT（N＝5）相對于tDHT（N＝3）在進行時態信息搜索時所需的查詢時間幾乎呈幾何遞減趨勢，當數據量達到千萬級以上時差異性更為突出．由此可得，構建分布式哈希索引能較大程度地改善時態檢索性能。

5結語

時態屬性，作為刻畫事物的一個重要維度，對時態信息檢索、時態知識推理、時態數據挖掘等研究領域均有深遠的影響．針對海量的非結構化電子醫療時態數據，以時態集合作為基本的時態數據存儲結構，本文提出使用Hadoop平臺下分布式存儲系統HBase進行數據存取，并在此基礎上構建多級分布式哈希表以提升對海量時態信息檢索的性能．鑒于以時態集合為基本存儲元素的時態信息結構復雜，故借鑒對空間數據的處理方法將時態信息映射為空間數據區域，進行數據集的聚類以及劃分等數據重構和組織操作，構建N級時態數據子區域，并設計基于HBase的多級分布式哈希表索引（tDHT）算法，以各級時態子區域作為對應索引表的主鍵，并通過時態索引列族建立上、下級索引表主鍵的映射關系，實現N級索引目錄與原時態信息存儲表的關聯，完成多級分布式哈希表的構造．通過測試驗證了所構建的索引結構在Hadoop平臺下對于海量時態信息進行檢索的有效性．需要指出的是，本文是在單一時間粒度的前提下開展的確定性時態信息的研究，針對的是公歷系統，顯然這是較為理想的時態數據處理模型．然而在現實生活中涉及的多粒度、模糊的、不確定的時態信息，不僅需要進行不同時態粒層的映射轉換，還需額外地增加時態因子以描述時態信息的不確定性程度，這還需要另行研究．另外，針對不同的時態數據集，索引級數N的取值大小與性能提升程度的對應關系仍然需要進一步研究．

作者：陳磊封朝永單位：廣東工業大學計算機學院