李 儉，郭川軍，姜 微

（哈爾濱金融學院 計算機系，黑龍江 哈爾濱150030）

隨著社會的數字化變革、因特網的蓬勃發(fā)展及國民經濟的迅猛崛起，全球各個領域的數據呈爆炸式增長。數據作為信息的載體，已成為包括金融經濟、交通物流、國家安全和社會生活等各個領域最核心、最有價值的資源。因此，為了發(fā)現(xiàn)數據背后隱藏的巨大價值，從商業(yè)應用領域到科學計算領域，面對海量數據的計算密集型應用需求日益增加，許多電子商務網站和社交網站需要存儲海量異構的頁面信息、用戶信息以及訪問日志等，并對這些數據進行快速而準確地訪問以及面向商業(yè)市場前景的智能計算。這些典型的計算需求包括用戶購買能力分析、定向廣告投遞效果查詢、產品增值的市場分析等，這些已成為互聯(lián)網中的核心問題?；谶@些海量數據的查詢分析，從中獲取有利于互聯(lián)網用戶體驗的信息，從而形成商業(yè)利益的有效價值鏈是十分有意義且充滿挑戰(zhàn)的工作。實現(xiàn)對計算密集型海量數據的有效查詢，需要從各項技術角度加以協(xié)調。

1 關鍵技術介紹分析

1.1 大規(guī)模分布式存儲技術

大規(guī)模分布式可靠存儲系統(tǒng)可為計算密集型查詢任務提供重要的后臺支撐，同時滿足系統(tǒng)在讀寫效率、查詢速度和吞吐量上的要求。在互聯(lián)網中，計算機用戶實現(xiàn)大規(guī)模的文件存儲、共享和交換時，基本上都是基于P2P技術，比較著名的基于P2P的分布式存儲系統(tǒng)有 Napster、Kazaa、Ocean Store等。其中，Napster將系統(tǒng)中所有計算機節(jié)點認為是同一級別，文件標識號和文件存儲節(jié)點間存在一個約定好的映射關系，這使得用戶在查找某個文件時，可以通過計算快速定位到文件存儲節(jié)點，從而建立連接并下載文件。

隨著計算機技術的飛速發(fā)展，個人計算機進行獨立工作的能力越來越強，而且會有大量的計算和存儲資源處于閑置狀態(tài)，并且一天當中會有近半數以上的計算機處于開機聯(lián)網狀態(tài)。要想在互聯(lián)網的結構特點上，以現(xiàn)有資源為基礎，更有效地發(fā)揮互聯(lián)網的作用，就需要整合互聯(lián)網上眾多零散的個人計算機，將其作為統(tǒng)一的節(jié)點進行管理，并充分利用它們各自的空閑存儲空間，形成一個高可靠、高性能、海量而廉價的分布式存儲系統(tǒng)。

因此，可以將節(jié)點Node和用戶文件File作為系統(tǒng)中的獨立實體，實現(xiàn)分布式存儲系統(tǒng)。該存儲系統(tǒng)在節(jié)點通過網絡連接起來的基礎上，用戶文件以副本的形式存儲到多個較近的節(jié)點中，文件內容會隨著用戶的操作隨時同步更新。對于大文件而言可以直接存儲；對于小文件來說，直接存儲會浪費存儲空間，所以可采用將多個小文件進行聚集壓縮而形成一個復合文件的形式來存儲，而在訪問時可以不解壓而直接對文件進行各種操作。另外，各節(jié)點除了提供存儲空間，還可以提供計算資源，從而使系統(tǒng)更加高效。

從系統(tǒng)功能的角度可以將系統(tǒng)由下至上分為物理層、路由層、數據層、會話層和應用層。物理層是采用網絡將各獨立節(jié)點進行連接，是整個系統(tǒng)的物理基礎；路由層通過路由算法進行節(jié)點和文件定位，以便就近存取文件；數據層通過冗余的文件副本提供數據容錯，同時提供平衡負載和文件壓縮等功能，以便提高文件訪問效率；會話層為用戶提供節(jié)點登錄和目錄管理功能，并保證了數據安全和高效的數據傳輸；應用層為用戶提供了統(tǒng)一的虛擬海量存儲空間接口，用戶在系統(tǒng)任意一個結點上登錄都可以自如地訪問分布式存儲空間，包括上傳、下載文件，還可以實現(xiàn)文件共享。

由于存儲的數據涉及到結構化和非結構化數據，鑒于結構化數據適于實時訪問以及方便存儲敏感數據的優(yōu)點，以及非結構化數據的低成本、高性能、自由性強、可擴展程度的優(yōu)點，在存儲數據的同時，可以將結構化數據和非結構化數據融合存儲，有效整合，以簡代繁，實現(xiàn)數據訪問與共享的有效隔離。分布式存儲系統(tǒng)的系統(tǒng)層次結構如圖1所示。

圖1 分布式存儲系統(tǒng)層次結構

1.2 面向海量數據的索引機制

在數據庫研究領域，數據通常被分成結構化數據和非結構化數據兩種類型。結構化數據具有統(tǒng)一的綱要，關系表中的每個元組都有相同的屬性和數據類型（比如數值或字符串），關系數據庫可以對它們進行統(tǒng)一的存儲和管理。相比之下，非結構化數據包括文本文件、XML數據、社交網絡數據等，這些數據沒有統(tǒng)一格式，無法用關系數據庫實現(xiàn)。在復雜的實際應用中，系統(tǒng)甚至可能需要同時處理結構化和非結構化數據。為了方便用戶對各種數據類型的查詢和分析，需要根據不同的數據結構研究合理的數據存儲索引機制，以提高計算密集型查詢和分析的時間效率。

1.2.1 結構化數據的索引策略

對于海量結構化數據，如果仍要遵循數據一致性規(guī)則，將導致數據更新延遲、局部數據失效、系統(tǒng)擴展性受限等問題。因此，應放寬對數據一致性的要求，取消復雜的關聯(lián)查詢，結合具體的應用場景，提高系統(tǒng)的可用性?？梢圆捎玫古潘饕夹g，通過詞典和倒排鏈表實現(xiàn)字符串到文件的映射，以便根據查詢詞快速定位。對于海量結構化數據，則需要分布式處理索引，通過索引分割建立索引集群。索引分割可以采用混合分割，即根據數據特點分別對索引進行基于文檔的縱向分割和基于詞的橫向分割。此時，整個文檔集合可以局部的縱向分割先劃分成N份，然后對于每一個子文檔集合在M個索引集群節(jié)點上，針對查詢頻率高的詞進行基于“詞”的橫向分割。

1.2.2 非結構化數據的索引策略

對于非結構化數據，首先需要在分析數據的基礎上進行預處理，然后根據不同的數據特點通過適當的算法進行數據原始特征采集和轉化，生成數據的有效特征，從而得到高維數據，最后實現(xiàn)數據的存儲。這里的特征提取算法尤為重要，算法不但要最大程度地降低特征維度，還要保證所提取的數據特征的有效性，力求從中得到更多有價值的數據和信息。

隨著大數據時代的到來，數據維度不斷增加，樹形索引技術已無法滿足日益增加的索引復雜度需求，因此，可以采用LSH算法，利用 Hash函數族，在保持原高維數據空間相似性的前提下，將高維索引數據轉化為低維數據，使高維數據點盡可能地Hash到相同桶中，同時要均衡各節(jié)點的負載，從而有效地解決高維數據的相似性搜索問題。但是LSH算法將會把大量時間用于計算桶合并后查詢點與這些高維數據點集合的距離，以便選取最近的一些數據點作為最終的查詢結果返回，從而浪費大量時間。為了解決這個問題，可以在Hash函數中融入譜分析技術，即對高維數據進行譜分析，對給定的一個高維樣本數據庫進行訓練，通過特征函數分析高維數據樣本的平均分布，以構造譜Hash函數，從而保證將相似的高維數據點Hash到一個相似值上。

對于不同種類的高維數據，則要充分利用概率分布特點，使其映射到不同的節(jié)點空間中，將這種分片策略集成到非結構化數據分布式索引系統(tǒng)中，以實現(xiàn)高效查詢。LSH高維數據劃分與節(jié)點映射如圖2所示。

圖2 LSH高維數據劃分與節(jié)點映射

1.3 高效并行聚集查詢技術

在對海量數據實現(xiàn)了分布式存儲及索引機制的基礎上，還要針對具體查詢進行處理和優(yōu)化。由于海量數據庫的應用中具有大量聚集查詢，因此，要重點針對海量數據的聚集查詢操作進行處理和優(yōu)化。

如果系統(tǒng)經常接收到的查詢是聚合查詢，則可以采用刷新緩存的方法來進行。首先，系統(tǒng)要為每種聚集查詢語句分別建立緩存表，在每一個時間片內執(zhí)行一次聚集查詢操作，然后將帶有時間標記的查詢結果存入到相應的緩存表中，以后一旦有查詢需要處理，則按時間段到相應的緩存表中去匹配即可。其次，如果用戶提交的是已優(yōu)化的聚集查詢，就要按時間將其分解為探測查詢和剩余查詢，最后合并查詢結果即可。

上述方案在收集緩存時需要直接訪問源數據庫，因此只適用于聚集查詢種類不多的情況，如果聚集查詢種類多，勢必會降低系統(tǒng)性能。這時，可以將數據在入庫前就進行分流，一段數據流載入小規(guī)模數據庫，另一段數據流則直接載入源數據庫。當需要收集緩存信息時，就可以直接在小規(guī)模數據庫上進行操作，然后將結果存入緩存。相應的時間片結束時，要在中間結果數據庫中執(zhí)行該時間片內的聚集查詢，然后將查詢結果存入緩存表，同時將中間結果數據庫中該查詢對應的緩存表截斷，以便收集下個時間片的緩存信息。由于中間結果數據庫中的數據容量與主數據庫相比要小得多，因此在其上面做聚集查詢操作效率非常高，并且不會影響到主數據庫系統(tǒng)的性能。

2 并行編程模型

為了使并行編程不依賴于具體的硬件平臺，讓更多的人能夠在比較低的起點上快速有效地開發(fā)并行程序，實現(xiàn)串行程序的并行執(zhí)行，需要設計出合理有效的并行編程模型。并行編程模型可以采用層次化結構設計。

首先，為實現(xiàn)并行編程的平臺無關性，需要將與平臺相關的底層所有并行函數庫進行封裝，用戶可以通過統(tǒng)一的與平臺無關的上層API接口進行并行程序開發(fā)，程序可以在不同的計算平臺上實現(xiàn)編譯，同時將上層API自動映射到和平臺相對應的函數庫中。

其次，為了大規(guī)模計算問題的并行化，解決復雜問題，要通過任務調度策略和數據分配功能，使多任務計算問題在執(zhí)行時達到較低的平行開銷和較好的負載均衡。對一個計算問題，可以根據任務規(guī)模分別采用不同的粒度，并將其劃分為多個獨立的計算單元，然后通過線程的并發(fā)同步解決計算問題。每個任務通過一個數據調度器對數據按行或按列劃分，將數據平均分配到各個線程上，每個數據塊分配給哪個線程可以是順序分配，也可以是循環(huán)分配或是隨機分配。

最后，為了增強系統(tǒng)的可擴展性，應提供應用函數庫和運行時函數庫的擴展手段，使系統(tǒng)可以支持任何最新低層計算平臺，并可針對某一具體應用領域開發(fā)特有的編程模型。

3 結束語

本文致力于面向計算密集型的海量數據查詢處理關鍵技術的分析與研究，探索了在大數據環(huán)境下，根據不同數據的特點搭建分布式存儲系統(tǒng)，以提高查詢效率為目的而采用降維處理實現(xiàn)索引機制，并針對海量數據的聚集查詢操作進行處理和優(yōu)化，同時分析了為面向更多用戶而設計的與平臺無關的并行編程模型。通過這種系統(tǒng)架構，更好地規(guī)劃完成了對計算密集型海量數據的存儲，并實現(xiàn)了高效查詢及數據處理。需要進一步研究的是，如何在分布式高效存儲且低冗余的情況下更好地保證數據的可靠性；如何使并行編程模型的并行執(zhí)行和任務調度對所有編程人員和用戶透明。隨著大數據時代的發(fā)展，海量數據查詢仍是一個值得深入研究的領域。

［1］ 周旭.面向Internet的大規(guī)模分布式存儲技術研究［D］.成都:電子科技大學，2004.

［2］ 于濱.海量非結構化數據分布式分析與檢索［D］.杭州:浙江大學，2012.

［3］ 李卓浩.面向海量數據管理的分布式倒排索引研究與應用［D］.杭州:浙江大學，2012.

［4］ 徐小龍，吳家興，楊庚，等.基于大規(guī)模廉價計算平臺的海量數據處理系統(tǒng)的研究［J］.計算機應用研究，2012（2）:582－585.

［5］ 馬俊濤，黃如生.以混合存儲模型實現(xiàn)云計算平臺對電信海量數據的處理［J］.移動通信，2011（7）:76－79.

［6］ 李婷.一種平臺無關的并行編程模型的設計與實現(xiàn)［D］.合肥:中國科學技術大學，2014.