計(jì)算密集型海量數(shù)據(jù)查詢處理關(guān)鍵技術(shù)分析

李 儉，郭川軍，姜 微

（哈爾濱金融學(xué)院 計(jì)算機(jī)系，黑龍江 哈爾濱150030）

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

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

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

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

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

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

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

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

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

1.2 面向海量數(shù)據(jù)的索引機(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ù)庫可以對它們進(jìn)行統(tǒng)一的存儲和管理。相比之下，非結(jié)構(gòu)化數(shù)據(jù)包括文本文件、XML數(shù)據(jù)、社交網(wǎng)絡(luò)數(shù)據(jù)等，這些數(shù)據(jù)沒有統(tǒng)一格式，無法用關(guān)系數(shù)據(jù)庫實(shí)現(xiàn)。在復(fù)雜的實(shí)際應(yīng)用中，系統(tǒng)甚至可能需要同時(shí)處理結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)。為了方便用戶對各種數(shù)據(jù)類型的查詢和分析，需要根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)研究合理的數(shù)據(jù)存儲索引機(jī)制，以提高計(jì)算密集型查詢和分析的時(shí)間效率。

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

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

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

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

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

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

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

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

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

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

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

2 并行編程模型

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

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

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

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

3 結(jié)束語

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

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

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

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

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

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

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