張 蕊，李廣云，王 力，李明磊

(1． 信息工程大學(xué)，河南 鄭州 450052； 2． 華北水利水電大學(xué)，河南 鄭州 450045)

一、引 言

海量激光點(diǎn)云數(shù)據(jù)的存儲和處理技術(shù)是目前地理信息系統(tǒng)和測量系統(tǒng)的一個重要研究方向。由車載系統(tǒng)所獲取的建筑物坐標(biāo)數(shù)據(jù)或三維激光掃描系統(tǒng)所獲取的實(shí)測場景數(shù)據(jù)一般為全離散矢量距離點(diǎn)構(gòu)成的“點(diǎn)云”數(shù)據(jù)[1]，為給后期點(diǎn)云數(shù)據(jù)的高效處理做準(zhǔn)備，目前傳統(tǒng)的技術(shù)是預(yù)先基于內(nèi)存對點(diǎn)云構(gòu)建索引以實(shí)現(xiàn)數(shù)據(jù)的有效存儲[2-3]，當(dāng)每個數(shù)據(jù)文件只有KB或MB時，該技術(shù)效果顯著。

然而對于海量離散點(diǎn)云數(shù)據(jù)，數(shù)量級達(dá)到了GB或甚至為TB，并由于單機(jī)內(nèi)存的限制，無法再根據(jù)傳統(tǒng)的基于全內(nèi)存的方法對數(shù)據(jù)進(jìn)行處理。文獻(xiàn)[4—7]中提出了幾種基于外存或數(shù)據(jù)庫的數(shù)據(jù)存儲方法，無法滿足點(diǎn)云數(shù)據(jù)后期處理過程中的交互需求[8]。為達(dá)到在現(xiàn)有計(jì)算機(jī)硬件水平下進(jìn)行海量點(diǎn)云數(shù)據(jù)快速處理的效果，近年來計(jì)算機(jī)領(lǐng)域延伸和發(fā)展了許多新技術(shù)，其中以Google的GFS和Hadoop的HDFS(hadoop distributed file system)最為著名，本文基于HDFS對海量點(diǎn)云數(shù)據(jù)文件的分塊策略提出了新的方法。

二、基于Hadoop的HDFS存儲系統(tǒng)

大數(shù)據(jù)技術(shù)包括大數(shù)據(jù)的存儲、計(jì)算、管理到恢復(fù)等多個方面。其中大數(shù)據(jù)的存儲策略是大數(shù)據(jù)高效處理過程中需要解決的首要關(guān)鍵問題。Hadoop/MapReduce在大數(shù)據(jù)存儲與數(shù)據(jù)處理方面扮演著重要的角色。Hadoop是一個基于云計(jì)算平臺的分布式系統(tǒng)基礎(chǔ)架構(gòu)，是一個用來處理大規(guī)模數(shù)據(jù)的軟件平臺，能可靠地存儲和處理PB級數(shù)據(jù)，且可通過普通機(jī)器組成的服務(wù)集群來存儲和處理數(shù)據(jù)，服務(wù)集群可達(dá)數(shù)千個節(jié)點(diǎn)[8]。

Hadoop是一種典型的主從式結(jié)構(gòu)，主要由HDFS和MapReduce組成，其結(jié)構(gòu)如圖1所示。其中HDFS負(fù)責(zé)對海量數(shù)據(jù)進(jìn)行分布式存儲，具有可靠性高、擴(kuò)展性強(qiáng)、成本低等優(yōu)勢，它的開源性、高容錯性及可以部署在廉價的硬件設(shè)備上的特點(diǎn)是其成為云存儲研究的熱點(diǎn)之一[9]。

圖1 Hadoop基礎(chǔ)架構(gòu)

文件系統(tǒng)是支持上層應(yīng)用的基礎(chǔ)。Hadoop由于有HDFS在底層作支撐，可以方便地實(shí)現(xiàn)“計(jì)算向存儲的遷移”，這與傳統(tǒng)的并行處理技術(shù)MPI(message passing interface)有本質(zhì)區(qū)別，處理TB或PB級的海量數(shù)據(jù)具有很大的優(yōu)勢。HDFS分布式文件系統(tǒng)體系結(jié)構(gòu)如圖2所示，HDFS由一個名字節(jié)點(diǎn)(Namenode)和多個數(shù)據(jù)節(jié)點(diǎn)(Datanode)組成。Namenode是集群中的中心服務(wù)器，負(fù)責(zé)管理文件系統(tǒng)的命名空間(Namespace)以及客戶端對文件的訪問。數(shù)據(jù)節(jié)點(diǎn)通常是多個，一個節(jié)點(diǎn)運(yùn)行一個數(shù)據(jù)節(jié)點(diǎn)進(jìn)程，負(fù)責(zé)管理它所在節(jié)點(diǎn)上的數(shù)據(jù)存儲[10]。

圖2 HDFS體系結(jié)構(gòu)

三、海量激光點(diǎn)云數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)

為描述由激光掃描儀所測量的各個掃描點(diǎn)的詳細(xì)信息，本文把點(diǎn)云數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)為

(ID,ρ,θ,α,x,y,z,I,nx,ny,nz,R,G,B)

如圖3所示，由此可獲得掃描點(diǎn)極坐標(biāo)(ρ,θ,α)，根據(jù)極坐標(biāo)原理即可得掃描點(diǎn)P的三維坐標(biāo)

(1)

I表示回光強(qiáng)度；nx、ny、nz表示由點(diǎn)P的KNN擬合出曲面獲取的法向三分量，如圖4所示；R、G、B表示相機(jī)采集照片貼圖后每點(diǎn)的色彩信息。

圖3 激光掃描儀三維坐標(biāo)系

圖4 法向三分量示意圖

基于激光點(diǎn)云數(shù)據(jù)的特點(diǎn)，并結(jié)合海量數(shù)據(jù)的存儲技術(shù)，本文提出底層采用基于Hadoop的分布式文件系統(tǒng)HDFS存儲數(shù)據(jù)，在存儲文件之前需要對文件進(jìn)行分塊處理，采用的分塊方法直接影響對數(shù)據(jù)的處理和檢索效率。

四、文件分塊策略

在文件分布式存儲過程中，文件分割是其中一個關(guān)鍵步驟。HDFS采用了 64 MB的固定文件分塊大小，這個尺寸遠(yuǎn)遠(yuǎn)大于傳統(tǒng)文件系統(tǒng)的分塊甚至是文件的大小，每個塊及其副本都以普通Linux文件的形式保存在塊服務(wù)器上。如何在文件分布式存儲時對文件進(jìn)行分割，將文件以最優(yōu)分塊大小進(jìn)行存儲，是海量數(shù)據(jù)存儲的一項(xiàng)核心技術(shù)，本文對此提出了3種解決方案。

1. 定長分塊(fixed-size partition，F(xiàn)SP)

FSP是通過HDFS配置好的塊大小對文件進(jìn)行切分，對文件中的激光點(diǎn)云數(shù)據(jù)進(jìn)行順序掃描，將點(diǎn)云數(shù)據(jù)按水平方向均勻分割為若干個大小的數(shù)據(jù)塊，然后將每個數(shù)據(jù)塊分別存儲在HDFS系統(tǒng)中的各個數(shù)據(jù)節(jié)點(diǎn)上，把對一個文件的訪問請求轉(zhuǎn)變?yōu)閷Χ鄠€文件分塊的訪問請求，從而達(dá)到系統(tǒng)負(fù)載均衡，提高數(shù)據(jù)的高吞吐率。

FSP算法的優(yōu)點(diǎn)是簡單、性能高，但它對數(shù)據(jù)插入和刪除非常敏感，處理十分低效，不能根據(jù)內(nèi)容變化作調(diào)整和優(yōu)化。

2. 變長分塊(content-defined partition，CDP)

CDP是將文件分割成長度大小不等的分塊策略。文獻(xiàn)[11]提出制定一個分組因子向量，當(dāng)需要存儲文件時，先得到該文件的大小，通過將文件大小與分組因子進(jìn)行比較，得到最優(yōu)分塊大小。

本文考慮基于文件內(nèi)容對文件進(jìn)行數(shù)據(jù)切分，對不同物體掃描的數(shù)據(jù)存放在不同的數(shù)據(jù)塊中。CDP最大的好處為對同一物體掃描得到的數(shù)據(jù)被分割到一個數(shù)據(jù)塊中，對數(shù)據(jù)進(jìn)行讀取時只需訪問當(dāng)前塊，無需訪問多個數(shù)據(jù)塊。但此方法有可能會引起有的數(shù)據(jù)塊過大，而有的數(shù)據(jù)塊過小。

春天就要來臨了，這群地球上有名的長途旅行家也要開始為每年的春季大遷徙做準(zhǔn)備了。每年春季的3—4月，夏季的7—8月，是馴鹿家族的遷徙時間。那時候，家族中的老老少少齊動身，憑著驚人的耐受力開始路途遙遠(yuǎn)的大遷徙。

3. 混合分塊法

如果變長分塊方法可行，能否把定長分塊和變長分塊結(jié)合起來，充分發(fā)揮二者的優(yōu)勢，彌補(bǔ)各自的缺陷，是需要研究的另一個難點(diǎn)。

五、試驗(yàn)結(jié)果與分析

本文采用的測試環(huán)境為具有6個節(jié)點(diǎn)的服務(wù)集群，其中一臺為NameNode，五臺為DataNode，硬件環(huán)境CPU為Intel core i5-3230M 2.6 GHz，3級緩存，內(nèi)存8 GB，網(wǎng)絡(luò)100 Mbps LAN。數(shù)據(jù)文件大小375.274 MB，存儲了4個模型的三維點(diǎn)云數(shù)據(jù)，點(diǎn)數(shù)為9 854 757。然后，先后采用傳統(tǒng)方法(即不分塊)、定長分塊和變長分塊方法分別對測試數(shù)據(jù)進(jìn)行處理，試驗(yàn)結(jié)果如下所述。

1．傳統(tǒng)方法試驗(yàn)

4個模型的三維點(diǎn)云放在一個文件中，不分塊，處理過程為：

1) 讀取第一個模型的數(shù)據(jù)；

2) 按八叉樹進(jìn)行劃分；

3) 每個點(diǎn)在八叉樹中尋找KNN，按最小二乘平面擬合計(jì)算點(diǎn)法向；

4) 按步驟1)—3)依次處理其余三部分?jǐn)?shù)據(jù)，處理結(jié)果見表1。

表1 用傳統(tǒng)方法對點(diǎn)云數(shù)據(jù)進(jìn)行處理

2． FSP試驗(yàn)

4個模型的三維點(diǎn)云按每塊64 MB進(jìn)行切分，共分為6塊，最后一塊大小為54.849 MB，處理過程為：

1) 6個數(shù)據(jù)塊存儲在一組DataNode中；

2) 每個節(jié)點(diǎn)進(jìn)程需要判斷是否從相鄰數(shù)據(jù)塊中讀取數(shù)據(jù)(本塊中的當(dāng)前塊數(shù)據(jù)是否完全)，然后將完整的數(shù)據(jù)塊按八叉樹進(jìn)行劃分；

3) 各個進(jìn)程中數(shù)據(jù)塊中的各點(diǎn)在相應(yīng)八叉樹中尋找KNN，計(jì)算點(diǎn)法向；

4) 一個節(jié)點(diǎn)可能包含多個塊的部分?jǐn)?shù)據(jù)，依次執(zhí)行步驟1)—3)，處理結(jié)果見表2。

3． CDP試驗(yàn)

4個模型的三維點(diǎn)云按內(nèi)容進(jìn)行切分，共分為4個數(shù)據(jù)塊，對點(diǎn)云數(shù)據(jù)進(jìn)行讀取時只需訪問當(dāng)前塊，處理過程為：

1) 4個數(shù)據(jù)塊分別存儲在一組DataNode中；

2) 每個節(jié)點(diǎn)進(jìn)程都將所處理數(shù)據(jù)按八叉樹進(jìn)行劃分；

3) 各個數(shù)據(jù)塊中各點(diǎn)在相應(yīng)八叉樹中尋找KNN，計(jì)算點(diǎn)法向，處理結(jié)果見表3。

表2 用FSP法對點(diǎn)云數(shù)據(jù)進(jìn)行處理

表3 用CDP法對點(diǎn)云數(shù)據(jù)進(jìn)行處理

由試驗(yàn)結(jié)果可以看出，對點(diǎn)云數(shù)據(jù)進(jìn)行分塊存儲的效果明顯優(yōu)于傳統(tǒng)方法。

六、后續(xù)工作

對海量數(shù)據(jù)的存儲是大數(shù)據(jù)處理的第一步，存儲策略的選擇直接影響到對海量數(shù)據(jù)的計(jì)算和處理效率。對其他數(shù)據(jù)存儲技術(shù)，如數(shù)據(jù)復(fù)制、數(shù)據(jù)壓縮、重復(fù)數(shù)據(jù)刪除及存儲虛擬化技術(shù)等是后續(xù)需要研究的工作。

其次，原始的數(shù)據(jù)存放在HDFS分布式文件系統(tǒng)中，而用戶習(xí)慣通過某種DBMS(database management system)來存取數(shù)據(jù)。因?yàn)檫@樣能夠隱藏文件系統(tǒng)底層技術(shù)，方便對數(shù)據(jù)的管理和用戶操作，可采用分布式數(shù)據(jù)庫系統(tǒng)HBase存取數(shù)據(jù)，對數(shù)據(jù)表中數(shù)據(jù)進(jìn)行分區(qū)處理的海量數(shù)據(jù)管理技術(shù)是后續(xù)需要研究的一個重點(diǎn)。

七、結(jié)束語

HDFS文件系統(tǒng)對海量數(shù)據(jù)進(jìn)行分布式存儲，具有可靠性高、擴(kuò)展性強(qiáng)、成本低等優(yōu)勢，正好滿足當(dāng)前海量激光點(diǎn)云數(shù)據(jù)的存儲需求。本文首先構(gòu)建了海量激光點(diǎn)云數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，在此基礎(chǔ)上提出了3種海量點(diǎn)云數(shù)據(jù)文件的分塊方法，并通過仿真試驗(yàn)驗(yàn)證了定長分塊和按內(nèi)容分塊的有效性，對于混合分塊方法的有效性需進(jìn)一步研究和驗(yàn)證。

參考文獻(xiàn)：

[1] 李婕,鐘若飛,趙文吉. 車載激光點(diǎn)云海量數(shù)據(jù)的管理與快速顯示[J].系統(tǒng)仿真學(xué)報(bào)，2008,20(S1):33-39.

[2] 謝洪.基于地面三維激光掃描技術(shù)的海量點(diǎn)云模型重建關(guān)鍵算法研究[D].鄭州：信息工程大學(xué)，2013.

[3] 黃先鋒,陶闖,江萬壽，等.機(jī)載激光雷達(dá)點(diǎn)云數(shù)據(jù)的實(shí)時渲染[J]. 武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30(11)：975-978.

[4] KlEIN J, KROKOWSKI J, FISCHER M. The Randomized Sample Tree： a Data Structure for Interactive Walkthroughs in Externally Stored Virtual Environments[C]∥Proceedings of the ACM Symposium on Virtual Reality Software and Technology.[S.l.]:VRST,2002:137-146.

[5] 王晏民,郭明.大規(guī)模點(diǎn)云數(shù)據(jù)的二維與三維混合索引方法[J]. 測繪學(xué)報(bào)，2012，41(4):605-612.

[6] BOUBEKEUR T, SCHLICK C. Interactive Out-of-core Texturing with Point-sampled Textures[C]∥Proceedings of the 3rd Eurographics.[S.l.]:IEEE,2006:67-73.

[7] PAJAROLA R. Stream-processing Points[C]∥Proc. VIS’05.[S.l.]:IEEE,2005:239-246.

[8] 邰建華. Hadoop平臺下的海量數(shù)據(jù)存儲技術(shù)研究[D]. 大慶：東北石油大學(xué)，2012:1-8.

[9] 王永洲.基于HDFS的存儲技術(shù)的研究[D]. 南京：南京郵電大學(xué)， 2013:13-44.

[10] 張為民,唐劍鋒,羅治國,等. 云計(jì)算深刻改變未來[M]. 北京：科學(xué)出版社，2009.

[11] 李暉, 樊凱, 王康,等. 云存儲系統(tǒng)中可變分塊大小的塊數(shù)據(jù)分塊方法:中國,201110350575 [P]. 2012-06-20.