宋 烜，周 薇，韓冀中，崔辰州

(1.北京天文館，北京 100044;2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190;3.中國(guó)科學(xué)院國(guó)家天文臺(tái)，北京 100012)

1 背景

1.1 虛擬天文臺(tái)

天文學(xué)正進(jìn)入一個(gè)多波段數(shù)字巡天的時(shí)代，從射電波段到微波、紅外、可見(jiàn)光、紫外、X射線，整個(gè)波段都會(huì)被覆蓋。這些巡天項(xiàng)目產(chǎn)生的數(shù)據(jù)量通?？梢赃_(dá)到TB甚至PB，這些數(shù)據(jù)也成為天文數(shù)據(jù)的主要來(lái)源［1－2］。一方面，天文數(shù)據(jù)量非常龐大，簡(jiǎn)單估算可知，以0.5″的分辨率，巡天由2×1012像素構(gòu)成，僅單一波段的巡天就產(chǎn)生4 TB數(shù)據(jù)。另一方面，天文數(shù)據(jù)增長(zhǎng)迅速，以斯隆數(shù)字巡天SDSS為例，它用了10年時(shí)間覆蓋8000平方度的天空，得到了大約108個(gè)星或者星系的近40 TB的數(shù)據(jù)。而未來(lái)2個(gè)巡天計(jì)劃PanSTARRS和LSST，只需3晚上就可覆蓋半個(gè)天空，每晚產(chǎn)生的包含5.7×108個(gè)源的數(shù)據(jù)都會(huì)超過(guò)40 TB［3］。因?yàn)樘煳膶W(xué)家需要從巡天數(shù)據(jù)中尋找變化，巡天需要不停地進(jìn)行，會(huì)產(chǎn)生數(shù)十到百億個(gè)目標(biāo)的星表，從而形成巨大的數(shù)據(jù)量。一些大的巡天計(jì)劃和他們的數(shù)據(jù)量列表見(jiàn)表1。

為了天文學(xué)家和公眾可以使用、查詢(xún)世界上所有望遠(yuǎn)鏡的數(shù)據(jù)，虛擬天文臺(tái)的建設(shè)提上了日程［4］。虛擬天文臺(tái)的建設(shè)目標(biāo)就是給全世界天文學(xué)家、教師、天文愛(ài)好者以及公眾提供一個(gè)平臺(tái)，使他們?cè)谑澜缟先魏螘r(shí)間任何地點(diǎn)可以協(xié)同使用全世界天文數(shù)據(jù)與計(jì)算資源。已經(jīng)有19個(gè)國(guó)家和地區(qū)開(kāi)發(fā)了符合國(guó)際標(biāo)準(zhǔn)［5］的可以相互協(xié)作的虛擬天文臺(tái)系統(tǒng)。

虛擬天文臺(tái)一經(jīng)誕生就面臨著龐大天文數(shù)據(jù)存儲(chǔ)與計(jì)算問(wèn)題。隨著數(shù)據(jù)量的增長(zhǎng)，本地星表交叉認(rèn)證、聚類(lèi)等多種數(shù)據(jù)敏感型的需求在增加?，F(xiàn)有的虛擬天文臺(tái)數(shù)據(jù)節(jié)點(diǎn)使用傳統(tǒng)的數(shù)據(jù)庫(kù)系統(tǒng)(DBMS)或者并行數(shù)據(jù)庫(kù)系統(tǒng)(PDBMS)。并行數(shù)據(jù)庫(kù)系統(tǒng)的研究始于20世紀(jì)80年代，大多數(shù)現(xiàn)有的PDBMS設(shè)計(jì)都類(lèi)似于Gamma［6］和Grace PDBMS。在過(guò)去的幾十年，各研究機(jī)構(gòu)實(shí)現(xiàn)了許多提升性能的技術(shù)，包括索引、壓縮、物理化視圖、結(jié)果高速緩存和I/O共享。但是因?yàn)椴⑿袛?shù)據(jù)庫(kù)設(shè)計(jì)之初即做出假設(shè):大規(guī)模集群中的節(jié)點(diǎn)極少失效，即使規(guī)模大至幾十個(gè)(而不是成百上千)［7］?；诖俗龀龅墓こ虒?shí)現(xiàn)，使得并行數(shù)據(jù)庫(kù)在容錯(cuò)能力和異構(gòu)環(huán)境的操作能力有限?，F(xiàn)有數(shù)據(jù)庫(kù)并行效率低，其局限在于:

表1 一些大巡天計(jì)劃的數(shù)據(jù)量Table 1 Data sizes of some surveys

(1)容錯(cuò)。并行數(shù)據(jù)庫(kù)在幾十個(gè)節(jié)點(diǎn)時(shí)性能良好，當(dāng)節(jié)點(diǎn)數(shù)上升至100個(gè)以上時(shí)，就會(huì)出現(xiàn)性能瓶頸［7］，因?yàn)楣?jié)點(diǎn)數(shù)增加后，節(jié)點(diǎn)失效就會(huì)更加頻繁地發(fā)生，因此，不能像并行數(shù)據(jù)庫(kù)當(dāng)初的設(shè)計(jì)原則那樣，認(rèn)為節(jié)點(diǎn)失效是小概率事件。

(2)可擴(kuò)展性。并行數(shù)據(jù)庫(kù)要求節(jié)點(diǎn)都是同構(gòu)的，當(dāng)節(jié)點(diǎn)規(guī)模變大時(shí)，很難保證純同構(gòu)情況，且這種模式擴(kuò)展性也不好。

(3)半結(jié)構(gòu)化數(shù)據(jù)處理能力。天文研究需要的數(shù)據(jù)主要包括星表、星圖、光譜。除了星表是完全結(jié)構(gòu)化的二維表以外，其他數(shù)據(jù)都是非結(jié)構(gòu)化或者半結(jié)構(gòu)化的數(shù)據(jù)，傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)在這個(gè)領(lǐng)域性能較低。

(4)成本因素。并行數(shù)據(jù)庫(kù)系統(tǒng)一般要求使用高端服務(wù)器和商用軟件。在需要大規(guī)模部署的時(shí)候，成本也是不得不考慮的因素。

綜合以上可以看出，使用數(shù)據(jù)庫(kù)系統(tǒng)，面對(duì)海量數(shù)據(jù)，虛擬天文臺(tái)數(shù)據(jù)節(jié)點(diǎn)面臨很大的壓力。

1.2 MapReduce

MapReduce［8］是一個(gè)非常適合分布式計(jì)算的編程模型和計(jì)算平臺(tái)。在MapReduce模型下，程序由用戶(hù)自定義map和reduce兩部分組成。MapReduce通過(guò)3個(gè)基本操作，在shared-nothing結(jié)構(gòu)的集群上，處理大規(guī)模分布式數(shù)據(jù)集。但是MapReduce的非結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)也使得數(shù)據(jù)沒(méi)有適當(dāng)?shù)念A(yù)處理和加工，因而數(shù)據(jù)庫(kù)系統(tǒng)中許多提升性能的工具無(wú)法發(fā)揮作用，如索引。即便如此，已經(jīng)有非常多的應(yīng)用在MapReduce模型下進(jìn)行處理，這其中包括日志分析、機(jī)器學(xué)習(xí)以及其他許多應(yīng)用。

Hadoop［9］是一個(gè)基于谷歌(Google)技術(shù)的開(kāi)源版本。它包括一個(gè)分布式文件系統(tǒng)HDFS和MapReduce計(jì)算模型。基于MapReduce框架，程序員不需要太多的并行處理或者分布式計(jì)算的經(jīng)驗(yàn)，就可以輕松地操縱大規(guī)模的集群系統(tǒng)，無(wú)需考慮硬件細(xì)節(jié)，從而大大提高工作效率。分布式文件系統(tǒng)HDFS是一個(gè)高容錯(cuò)的系統(tǒng)，它可以提供高吞吐量的數(shù)據(jù)訪問(wèn)，非常適合在海量天文數(shù)據(jù)集上使用。另外由于Hadoop在設(shè)計(jì)之初就充分考慮使用大規(guī)模廉價(jià)集群，硬件故障被視為正常狀態(tài)，所以Hadoop可以用低成本建立容錯(cuò)能力和可擴(kuò)展能力非常高的集群。

1.3 星表交叉認(rèn)證

交叉認(rèn)證工作在天文學(xué)研究中起著關(guān)鍵作用。首先，聯(lián)合了多個(gè)波段的數(shù)據(jù)可以獲取天體或相關(guān)天文現(xiàn)象更全面的信息，加深對(duì)認(rèn)證源的物理性質(zhì)、演化規(guī)律的理解;其次，融合數(shù)據(jù)促進(jìn)了新天體、現(xiàn)象、規(guī)律的發(fā)現(xiàn)［10］。所以，星表交叉認(rèn)證是虛擬天文臺(tái)在面對(duì)海量數(shù)據(jù)時(shí)不可避免要面對(duì)的一個(gè)問(wèn)題。

交叉認(rèn)證問(wèn)題可以簡(jiǎn)單闡述為尋找球面上距離相近的點(diǎn)的問(wèn)題。這個(gè)問(wèn)題看似簡(jiǎn)單，但是由于數(shù)據(jù)量極為龐大，并且通常需要在2個(gè)甚至更多的星表之間進(jìn)行匹配，導(dǎo)致問(wèn)題變得復(fù)雜。

一般交叉認(rèn)證算法包括3種:空間索引、像素編號(hào)算法(Pixel-code Algorithm)、平面掃描算法。

在目前MapReduce框架的實(shí)現(xiàn)中，其輸入集合都是以原始的數(shù)據(jù)格式存放，因此采用平面掃描算法可以更好地適應(yīng)此結(jié)構(gòu)，即無(wú)需建立索引，而直接采用排序?qū)崿F(xiàn)。利用支持MapReduce框架的開(kāi)源系統(tǒng)Hadoop，可以達(dá)到非常好的排序性能［11］。

在數(shù)據(jù)庫(kù)系統(tǒng)中，索引的建立會(huì)耗費(fèi)較長(zhǎng)的時(shí)間，有時(shí)會(huì)遠(yuǎn)大于數(shù)據(jù)庫(kù)操作的執(zhí)行時(shí)間。但是，因?yàn)樗饕梢砸淮谓⒍啻卫?，?dāng)數(shù)據(jù)被重復(fù)使用時(shí)，索引的建立是值得的。不過(guò)，大規(guī)模天文星表之間交叉認(rèn)證的工作一般只需要匹配一次就可以作為結(jié)果使用，所以分布式并行數(shù)據(jù)庫(kù)集群在索引上的優(yōu)勢(shì)在這項(xiàng)任務(wù)中沒(méi)有起到太大作用。

本文針對(duì)傳統(tǒng)并行數(shù)據(jù)庫(kù)處理大規(guī)模數(shù)據(jù)的一些缺陷，提出了使用MapReduce框架構(gòu)建虛擬天文臺(tái)數(shù)據(jù)節(jié)點(diǎn)。既發(fā)揮中國(guó)虛擬天文臺(tái)原有架構(gòu)在功能方面的優(yōu)勢(shì)，又使其對(duì)海量天文數(shù)據(jù)處理的能力得到極大加強(qiáng)。最后，本文將MapReduce框架應(yīng)用于本地海量星表交叉認(rèn)證這一具體天文應(yīng)用上，實(shí)驗(yàn)結(jié)果表明，此方案是非常有效的。

2 用MapReduce構(gòu)建虛擬天文臺(tái)數(shù)據(jù)節(jié)點(diǎn)

2.1 系統(tǒng)結(jié)構(gòu)

由于使用標(biāo)準(zhǔn)SQL接口，本文構(gòu)建的虛擬天文臺(tái)數(shù)據(jù)節(jié)點(diǎn)符合中國(guó)虛擬天文臺(tái)的各項(xiàng)標(biāo)準(zhǔn)，從而可以提供標(biāo)準(zhǔn)接口，供更上層的虛擬天文臺(tái)服務(wù)器調(diào)度、查詢(xún)。

系統(tǒng)具體結(jié)構(gòu)如圖1。天文數(shù)據(jù)節(jié)點(diǎn)有5個(gè)模塊，分別由SKYNODE模塊、ADQL模塊、HIVE模塊、HADOOP模塊和VOTABLE模塊組成。其中SKYNODE模塊是天文數(shù)據(jù)節(jié)點(diǎn)的核心，負(fù)責(zé)與其他模塊之間的交互以及SkyNodeInterface接口的發(fā)布;ADQL模塊負(fù)責(zé)將ADQL標(biāo)準(zhǔn)的輸入轉(zhuǎn)換成標(biāo)準(zhǔn)SQL輸入;HIVE模塊負(fù)責(zé)將SQL輸入翻譯成MapReduce任務(wù);HADOOP模塊負(fù)責(zé)處理HIVE模塊翻譯出的MapReduce任務(wù)，得到用戶(hù)需要的結(jié)果;VOTABLE模塊則是將系統(tǒng)輸出轉(zhuǎn)化成標(biāo)準(zhǔn)的VOData格式。

圖1 天文數(shù)據(jù)節(jié)點(diǎn)系統(tǒng)結(jié)構(gòu)圖Fig.1 Architecture of data nodes of the Virtual Observatory

SKYNODE模塊［12］:發(fā)布數(shù)據(jù)訪問(wèn)接口，一共實(shí)現(xiàn)了9種方法。它使用2種方法performQuery()和executePlan()實(shí)現(xiàn)查詢(xún)，其中performaQuery()用來(lái)實(shí)現(xiàn)簡(jiǎn)單查詢(xún)，而executePlan()用于處理復(fù)雜查詢(xún)。其余的方法都是用來(lái)支持查詢(xún)的輔助方法，比如元數(shù)據(jù)列、元數(shù)據(jù)表、節(jié)點(diǎn)狀態(tài)等等。

ADQL模塊［12］:它內(nèi)部實(shí)現(xiàn)了ADQL的解析，并將解析后的對(duì)象通過(guò)翻譯轉(zhuǎn)換查詢(xún)SQL語(yǔ)句送至HIVE模塊。

HIVE模塊:Hive是Hadoop項(xiàng)目下的一個(gè)子項(xiàng)目，它提供了JDBC/ODBC接口，使用者可以通過(guò)SQL執(zhí)行MapReduce。有了Hive，Hadoop看上去就是一個(gè)數(shù)據(jù)庫(kù)。HIVE模塊的主要功能是將SQL輸入翻譯成MapReduce任務(wù)。其中包括子模塊JDBC/ODBC驅(qū)動(dòng)、解析器和翻譯器。

HADOOP模塊:處理MapReduce任務(wù)，由兩部分組成:計(jì)算和存儲(chǔ)。計(jì)算部分是由Hadoop模塊的MapReduce框架完成的，MapReduce的JobTracker負(fù)責(zé)切割任務(wù)，然后將切割好的任務(wù)分發(fā)給TaskTracker執(zhí)行。存儲(chǔ)部分是由Hadoop的HDFS進(jìn)行，其中NameNode切割數(shù)據(jù)，然后將其分發(fā)給多個(gè)Hadoop DataNode。

VOTABLE模塊［12］:根據(jù)天文數(shù)據(jù)的統(tǒng)一數(shù)據(jù)標(biāo)準(zhǔn)，把來(lái)自不同數(shù)據(jù)集的數(shù)據(jù)以標(biāo)準(zhǔn)VOTable格式輸出。它接收Results Set，將結(jié)果轉(zhuǎn)換為VOTabl格式，以VOData對(duì)象輸出。

基于MapReduce框架的虛擬天文臺(tái)數(shù)據(jù)節(jié)點(diǎn)符合統(tǒng)一的數(shù)據(jù)訪問(wèn)接口，可以跟其他天文數(shù)據(jù)節(jié)點(diǎn)一起，給用戶(hù)提供一個(gè)完整統(tǒng)一的、可以使用所有天文數(shù)據(jù)節(jié)點(diǎn)的平臺(tái)。

2.2 運(yùn)行流程

天文數(shù)據(jù)訪問(wèn)門(mén)戶(hù)或客戶(hù)端程序可以調(diào)用performQuery方法(簡(jiǎn)單查詢(xún))或者executePlan方法(復(fù)雜查詢(xún))，將ADQL查詢(xún)語(yǔ)句通過(guò)ADQL模塊直接轉(zhuǎn)換為SQL，然后通過(guò)HIVE處理，轉(zhuǎn)化為MapReduce任務(wù)。HADOOP模塊接受MapReduce任務(wù)，生成處理結(jié)果。具體處理步驟如下:

(1)HDFS的NameNode將輸入文件(星表數(shù)據(jù))按固定大小(16 M到128 M不等，用戶(hù)可以自定義)分塊，然后將分塊后的數(shù)據(jù)分布在不同的Hadoop DataNode上;

(2)對(duì)于HIVE模塊輸出的MapReduce任務(wù)，MapReduce框架中的JobTracker將任務(wù)按Mapper數(shù)目分割;

(3)MapReduce框架遵循計(jì)算向數(shù)據(jù)遷移的原則，將Mapper優(yōu)先安排在有數(shù)據(jù)的節(jié)點(diǎn)上，這樣的處理過(guò)程可以盡量減少數(shù)據(jù)在節(jié)點(diǎn)之間傳輸;

(4)每個(gè)Mapper將計(jì)算出的中間結(jié)果保存在本地，等待Reducer來(lái)取中間數(shù)據(jù)，以便進(jìn)一步處理;

(5)Reducer根據(jù)JobTracker的指示，去Mapper取中間結(jié)果，然后進(jìn)行結(jié)果的歸并，生成最終結(jié)果，保存在HDFS上;

(6)HDFS上的結(jié)果以結(jié)果集的方式輸出到HIVE模塊，然后輸出到VOTABLE模塊，保存為VOData對(duì)象，由executePlan接口輸出。

在數(shù)據(jù)存儲(chǔ)方面，由于HDFS有冗余備份機(jī)制，當(dāng)其中一個(gè)節(jié)點(diǎn)失效后，可以在其他節(jié)點(diǎn)中找到數(shù)據(jù)備份，所以數(shù)據(jù)不會(huì)丟失。在計(jì)算方面，如果某一個(gè)mapper或者reducer失效，JobTracker會(huì)將失效mapper(reducer)上的任務(wù)分給其他mapper(reducer)，因此它很好地解決了1.1節(jié)中的問(wèn)題1。

MapReduce框架中，由于節(jié)點(diǎn)之間是可以互相通信的，不需要通過(guò)NameNode統(tǒng)一通信，所以，NameNode不會(huì)成為MapReduce的瓶頸，它具有良好的可擴(kuò)展性，可以解決1.1節(jié)的問(wèn)題2。

在天文領(lǐng)域，以半結(jié)構(gòu)化或者無(wú)結(jié)構(gòu)化數(shù)據(jù)居多，而MapReduce并行掃描的特點(diǎn)正好適合處理這種類(lèi)型的數(shù)據(jù)，這就解決了1.1節(jié)中問(wèn)題3提到的傳統(tǒng)數(shù)據(jù)庫(kù)對(duì)半結(jié)構(gòu)化數(shù)據(jù)和無(wú)結(jié)構(gòu)化數(shù)據(jù)的支持問(wèn)題。

最初谷歌提出MapReduce框架的初衷就是利用大量的廉價(jià)機(jī)器搭建分布式系統(tǒng)，所以，它把機(jī)器的失效當(dāng)成正常事件，不需要高價(jià)的服務(wù)器搭建系統(tǒng)。

至此已經(jīng)很好地解決了1.1節(jié)中所描述的問(wèn)題。下面以一個(gè)在虛擬天文臺(tái)中非常重要的任務(wù)星表交叉認(rèn)證測(cè)試新數(shù)據(jù)節(jié)點(diǎn)。

3 應(yīng)用

星表交叉認(rèn)證對(duì)虛擬天文臺(tái)來(lái)說(shuō)是最關(guān)鍵的任務(wù)之一，以批量星表交叉認(rèn)證進(jìn)行性能測(cè)試。本節(jié)介紹在新的天文數(shù)據(jù)節(jié)點(diǎn)下，如何進(jìn)行節(jié)點(diǎn)內(nèi)批量天文星表交叉認(rèn)證。

在處理天文星表交叉認(rèn)證問(wèn)題時(shí)，要面對(duì)的不僅是一個(gè)點(diǎn)與點(diǎn)距離的問(wèn)題。由于存在測(cè)量誤差，每一個(gè)星周?chē)即嬖谝粋€(gè)誤差范圍。這使得要處理的是搜索空間重疊的問(wèn)題，如果有重疊發(fā)生，就再使用星等接近等其他規(guī)則進(jìn)行處理，視為兩顆星匹配。

交叉認(rèn)證工作主要分為兩個(gè)步驟:過(guò)濾和優(yōu)選。過(guò)濾是篩選出落在最大誤差矩形內(nèi)的目標(biāo)最小邊界矩形(Minimum Bounding Rectanghes，MBR)，這個(gè)矩形即為最小邊界矩形。優(yōu)選則是在最小邊界矩形中通過(guò)其他規(guī)則逐個(gè)篩選符合要求的目標(biāo)。一般找到最小邊界矩形后的目標(biāo)較少，所以問(wèn)題集中在尋找最小邊界矩形中備選目標(biāo)的工作。

如圖2，圖中星星周?chē)膱A型代表誤差范圍。MapReduce各個(gè)階段的解釋如下:

(1)輸入:星表數(shù)據(jù)，包括赤經(jīng)、赤緯、星名、誤差等屬性。兩種顏色的星星可以表示兩個(gè)星表中的目標(biāo)。

圖2 MapReduce處理過(guò)程Fig.2 Data flow of astronomical cross-identification

(2)Map:按照數(shù)據(jù)流，在Map階段之前的最開(kāi)始階段，兩個(gè)要互相匹配的星表處于兩個(gè)不同的文件中。根據(jù)輸入的星的縱坐標(biāo)，計(jì)算出每顆星所屬的分區(qū)(圖2中的1、2、3)，把分區(qū)號(hào)作為中間key，星數(shù)據(jù)作為中間value，輸出給Reduce。借助于MapReduce框架的功能，相同分區(qū)號(hào)的目標(biāo)被分配到相同的Reduce中處理，然后在每一個(gè)Reduce中使用星的坐標(biāo)位置進(jìn)行平面掃描算法下的匹配查詢(xún)。除了Reduce階段的分布并行掃描，在為每顆星尋找它所屬分條的Map階段，可以并行同時(shí)給每顆星尋找分條，這正是Map階段處理的特長(zhǎng)，Map階段要求計(jì)算的獨(dú)立性，各個(gè)目標(biāo)的計(jì)算互不影響。另外，還需注意對(duì)邊界進(jìn)行特殊處理。在實(shí)現(xiàn)過(guò)程中，讓邊界誤差范圍內(nèi)的點(diǎn)同時(shí)被劃分到2個(gè)分條內(nèi)，可以很好地解決這一問(wèn)題。

至此，每顆星都找到了所屬的分條。處于相同分條的目標(biāo)都在同一個(gè)Reduce中處理。目標(biāo)是測(cè)試點(diǎn)還是目標(biāo)點(diǎn)可以通過(guò)value中設(shè)置一個(gè)屬性區(qū)分。每個(gè)Reduce會(huì)把Map送來(lái)的數(shù)據(jù)先進(jìn)行排序。

(3)Reduce:Reduce階段分為混合(shuffle)和Reduce兩部分。混合是指把從不同Map送來(lái)的key/value進(jìn)行排序，并把相同key的值聚合然后交給Reduce處理。Reduce即平面掃描過(guò)程。

傳統(tǒng)的單機(jī)掃描算法需要把每個(gè)目標(biāo)點(diǎn)與整個(gè)活動(dòng)區(qū)域進(jìn)行比較，活動(dòng)區(qū)域的長(zhǎng)度越長(zhǎng)，同等寬度的面積就越大，包括的測(cè)試點(diǎn)就越多，所以活動(dòng)區(qū)域的長(zhǎng)度決定了傳統(tǒng)平面掃描算法的效率。優(yōu)化這種算法可以通過(guò)分條掃描，減少活動(dòng)區(qū)域的邊長(zhǎng)，這樣就降低了活動(dòng)區(qū)域的面積，直接減少了需要匹配的測(cè)試點(diǎn)的數(shù)量，降低了運(yùn)算量。除此之外，分條以后的各分條掃描可以通過(guò)Hadoop框架分布到集群中的機(jī)器并行掃描運(yùn)算，可以明顯地提高效率。

除了依靠Hadoop框架實(shí)現(xiàn)的混合排序工作，Reduce基本上和典型的平面掃描過(guò)程沒(méi)有區(qū)別。主要分成兩個(gè)階段，過(guò)濾和優(yōu)選。

過(guò)濾:在Reduce階段中進(jìn)行的過(guò)濾工作需要每一個(gè)目標(biāo)的赤經(jīng)、赤緯坐標(biāo)，所以赤經(jīng)、赤緯、星名和誤差等作為中間key/value中的value。在過(guò)濾階段的開(kāi)始，按赤緯排序的數(shù)據(jù)順序讀入從Map送過(guò)來(lái)的中間值，每個(gè)Reduce只處理屬于自己分條范圍內(nèi)的目標(biāo)。這個(gè)階段的主要任務(wù)是找到在所有測(cè)試點(diǎn)的最小邊界矩形范圍內(nèi)的所有目標(biāo)點(diǎn)，即如圖3中心測(cè)試點(diǎn)和正方形覆蓋的所有目標(biāo)點(diǎn)的一對(duì)多關(guān)系。在每一個(gè)分條內(nèi)，通過(guò)全部在內(nèi)存中實(shí)現(xiàn)的平面掃描算法可以非常高效地找出最小邊界矩形。如圖3，t1是目標(biāo)點(diǎn)，要尋找t1為圓心、d為直徑的圓形范圍內(nèi)所有測(cè)試點(diǎn)。

圖3 過(guò)濾和優(yōu)選Fig.3 Illustration of filtering and refinement for object cross-identification

優(yōu)選:過(guò)濾以后的結(jié)果已經(jīng)可以認(rèn)為是匹配的了，只是條件還不夠充分。這個(gè)結(jié)果的形式可以表示為＜目標(biāo)點(diǎn)，［測(cè)試點(diǎn)］＞?？梢栽趦?yōu)選階段對(duì)過(guò)濾階段后結(jié)果再進(jìn)行逐個(gè)精確篩選，看是否符合需求。

(4)輸出:平面掃描后，可以獲得和目標(biāo)點(diǎn)匹配的測(cè)試點(diǎn)的列表。可以看到，本例的結(jié)果是s1/s6匹配。然后把結(jié)果轉(zhuǎn)化為VOTalbe形式供虛擬天文臺(tái)上層服務(wù)器調(diào)度處理。

4 性能評(píng)估

這一節(jié)比較了基于MapReduce框架下天文數(shù)據(jù)節(jié)點(diǎn)和基于傳統(tǒng)數(shù)據(jù)庫(kù)PostgreSQL之間的性能差異。MapReduce集群可以非常方便地部署到成千上萬(wàn)臺(tái)廉價(jià)節(jié)點(diǎn)，而傳統(tǒng)數(shù)據(jù)庫(kù)集群只能達(dá)到幾十臺(tái)的規(guī)模［7］。本測(cè)試使用少量廉價(jià)MapReduce集群與單臺(tái)數(shù)據(jù)庫(kù)進(jìn)行性能比較，目的在于測(cè)試增加少量MapReduce節(jié)點(diǎn)時(shí)的性能提升情況。

4.1 測(cè)試環(huán)境

測(cè)試數(shù)據(jù)來(lái)自2MASS［13］(2μm巡天)和GLIMPSE［14］(紅外銀道面特殊巡天)中的星表數(shù)據(jù)的一部分。數(shù)據(jù)規(guī)模:2MASS:15 433 500行，GLIMPSE:1 344 450行。測(cè)試集群配置為Dell PowerEdge，2.8 G，平均1.5 G內(nèi)存。PostgreSQL測(cè)試機(jī)配置為:P4/3.2 G(HT)/1 G內(nèi)存。

4.2 測(cè)試結(jié)果

首先測(cè)試了不同節(jié)點(diǎn)數(shù)目效率對(duì)比。如圖4，隨著節(jié)點(diǎn)數(shù)目的增多，效率也隨之提高。但加速比也隨著節(jié)點(diǎn)增多而減小，這主要是因?yàn)闇y(cè)試中所選數(shù)據(jù)集規(guī)模較小造成的。

在天文星表交叉認(rèn)證工作中經(jīng)常使用一種DBMS:PostgreSQL［15］，使用它和MapReduce進(jìn)行性能對(duì)比。

使用DMBS進(jìn)行交叉匹配需要使用空間索引，而建立索引需要很長(zhǎng)時(shí)間。在相同數(shù)據(jù)量的情況下，PostgreSQL建立空間索引需要30 min，匹配過(guò)程需要15 min(900 s)。性能對(duì)比如圖5。

圖4 節(jié)點(diǎn)數(shù)效率對(duì)比Fig.4 Comparison of efficiencies(measured in matching time)of different numbers of nodes

圖5 MapReduce與PostgreSQL性能對(duì)比Fig.5 Performance comparison between the MapReduce and PostgreSQL

從上面結(jié)果可以看出在節(jié)點(diǎn)少于4個(gè)的時(shí)候，MapReduce需要的時(shí)間大于PostgreSQL匹配時(shí)間。這說(shuō)明MapReduce在增加少量節(jié)點(diǎn)的情況下就可以獲得比較大的性能提升。而節(jié)點(diǎn)數(shù)大于6個(gè)以后所獲得的性能提升沒(méi)有第4～5個(gè)節(jié)點(diǎn)顯著。但仍可以設(shè)想如果在更大數(shù)據(jù)量情況下，越多節(jié)點(diǎn)應(yīng)該會(huì)獲得更好的效率。

天文星表數(shù)據(jù)一般只需要匹配一次就可以作為結(jié)果一直使用，所以可以認(rèn)為數(shù)據(jù)庫(kù)建立索引時(shí)間與星表匹配計(jì)算時(shí)間和需要與MapReduce進(jìn)行比較，可以看到MapReduce有非常大的優(yōu)勢(shì)。但是在非大規(guī)模兩個(gè)星表匹配查詢(xún)中，如單個(gè)點(diǎn)的匹配查詢(xún)，建立了索引的DBMS性能較好。

5 結(jié)論

本文首次提出將MapReduce框架應(yīng)用于中國(guó)虛擬天文臺(tái)數(shù)據(jù)節(jié)點(diǎn)，并在新框架下實(shí)現(xiàn)了本地星表交叉認(rèn)證并測(cè)試了性能。借助于HDFS分布式存儲(chǔ)，使用非結(jié)構(gòu)化的鍵值對(duì)保存、處理數(shù)據(jù)，以及框架本身良好的設(shè)計(jì)，很好地解決了不僅是性能，而且擴(kuò)展性、成本等多方面的問(wèn)題，超越了原有設(shè)計(jì)。

［1］Djorgovski S G，Brunner R J.Astronomical Archives of the Future:a Virtual Observatory ［J］.Future Generation Computer Systems，1999，16(1):63－72.

［2］Cui Chenzhou，Zhao Yongheng.Worldwide R＆D of Virtual Observatory ［J］.Proceedings of the International Astronomical Union，2007(3):563－564.

［3］Viewing the Heavens through the Cloud ［EB/OL］.［2010-10-22］.http://ssg.astro.washington.edu/research.shtml?research/CluE1.

［4］趙永恒，崔辰州.中國(guó)虛擬天文臺(tái)——任務(wù)、特點(diǎn)、方案 ［EB/OL］.［2010-10-22］.http://www.china-vo.org/docs/cvo_draft.pdf.

［5］IOVA ［EB/OL］.http://www.ivoa.net/.

［6］D J DeWitt，R H Gerber，G Graefe，et al.Gamma—A High Performance Dataflow Database Machine ［C］//Proceedings of the 12th International Conference on Very Large Data Bases.Very Large Data Bases'86.San Francisco:Morgan Kaufmann Publishers Incorpation，1986:228－237.

［7］Abouzeid A，Bbajda-Pawlikowski K，Aabadi D J，et al.Hadoopdb:an Architectural Hybrid of Mapreduce and dbMs Technologies for Analytical Workloads［C］//Proceedings of the2009 VLDB Endowment，2009，2(1):922－933.

［8］J Dean，S Ghemawat.MapReduce:Simplified Data Processing on Large Clusters ［J］.Communications of the ACM，2008，51(1):107－113.

［9］Hadoop ［EB/OL］.http://hadoop.apache.org/core/.

［10］高丹，張彥霞，趙永恒.中國(guó)虛擬天文臺(tái)交叉證認(rèn)工具的開(kāi)發(fā)和應(yīng)用 ［J］.天文學(xué)報(bào)，2008，49(3):348－358.Gao Dan，Zhang Yanxia，Zhao Yongheng.The Development and Application of the Cross-match Tool of China-VO ［J］.Acta Astronomica Sinica，2008，49(3):348－358.

［11］Owen O'malley.TeraByte Sort on Apache Hadoop ［EB/OL］.(2008-05) ［2009-12-14］.http://sortbenchmark.org/YahooHadoop.pdf.

［12］劉波，崔辰州，趙永恒.構(gòu)建中國(guó)虛擬天文臺(tái)的天文數(shù)據(jù)結(jié)點(diǎn) ［J］.天文研究與技術(shù)——國(guó)家天文臺(tái)臺(tái)刊，2006，3(4):355－364.Liu Bo，Cui Chenzhou，Zhao Yongheng.Construction of the SkyNode System for Chinese Virtual Observatory ［J］.Astronomical Research ＆ Technology——Publications of National Astronomical Observatories of China，2006，3(4):355－364.

［13］Cutri R M，Skrutskie M F，Van Dyk S，et al.2MASS All Sky Catalog of Point Sources.The IRSA2MASS All-Sky Point Source Catalog，NASA/IPAC Infrared Science Archive ［EB/OL］.(2003) ［2009-12-14］.http://irsa.ipac.caltech.edu/applications/Gator/.

［14］Churchwell E，Babler B L，Meade M R，et al.The Spitzer/Glimpse Surveys:A New View of the Milky Way ［J］.Publications of the Astronomical Society of the Pacific，2009，121:213－230.

［15］CGP.Report on Cross Matching Catalogues［EB/OL］.(2009-09-29) ［2009-12-14］.http://wiki.astrogrid.org/pub/Astrogrid/DataFederationandDataMining/cross.htm.