李 儉，郭川軍，姜 微

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

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

1 關(guān)鍵技術(shù)介紹分析

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

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

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

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

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

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

圖1 分布式存儲系統(tǒng)層次結(jié)構(gòu)

1.2 面向海量數(shù)據(jù)的索引機制

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

1.2.1 結(jié)構(gòu)化數(shù)據(jù)的索引策略

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

1.2.2 非結(jié)構(gòu)化數(shù)據(jù)的索引策略

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

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

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

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

1.3 高效并行聚集查詢技術(shù)

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

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

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

2 并行編程模型

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

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

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

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

3 結(jié)束語

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

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

［2］ 于濱.海量非結(jié)構(gòu)化數(shù)據(jù)分布式分析與檢索［D］.杭州:浙江大學，2012.

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

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

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

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