面向海量空間數據的分級存儲模型研究

楊文暉，袁進俊＊，苗 放，1b，2

（1.成都理工大學a.地球探測與信息技術教育部重點實驗室，b.地質災害防治與地質環境保護國家重點實驗室，成都 610059；2.成都大學模式識別與智能信息處理四川省高校重點實驗室，成都 610106）

面向海量空間數據的分級存儲模型研究

楊文暉1a，袁進俊1a＊，苗 放1a，1b，2

（1.成都理工大學a.地球探測與信息技術教育部重點實驗室，b.地質災害防治與地質環境保護國家重點實驗室，成都 610059；2.成都大學模式識別與智能信息處理四川省高校重點實驗室，成都 610106）

空間信息技術和遙感遙測等技術的飛速發展，產生了海量的遙感、地災等行業空間信息數據。如何對海量空間數據進行合理的分級存儲，以滿足大數據時代下空間信息、地理信息等行業應用，這已成為日益緊迫的問題。海量空間數據分級存儲作為一種全新的存儲模式，為解決該問題提出了新的思路。結合海量空間數據的特點和日常數據應用的規律，提出了基于訪問熱度和聚類關聯的海量空間數據分級存儲模型，該模型主要包括熱點數據分級、關聯數據分級、數據的遷移三部分。最后通過嫦娥2號遙感數據模擬訪問試驗，優化了數據升級閥值，證明了分級存儲模型用于海量空間數據的可行性。

空間數據；遙感遙測；分級存儲；密度聚類算法；數據關聯

0 引言

空間數據已廣泛應用于社會各行業、各部門，如城市規劃、交通、銀行、航空航天等。隨著空間信息技術和遙感遙測等技術的飛速發展，產生了海量、實時、異構的空間信息數據。如何對海量空間數據進行合理的分級存儲，以使海量空間數據能夠滿足不斷變化的地理信息等應用的需要，這已成為日益緊迫的問題［1］。海量空間數據分級存儲模型的提出基于四點因素：①數據分級方面，空間數據和所有數據一樣具有2－8效應，即一段時間內只有兩成左右的數據被系統經常用到，所以常被用到的數據應該備份存儲在能被系統快速獲取的設備上［2－3］；②數據存儲方面，數據存儲設備的I／O性能和價格相差很大，比如內存、固態硬盤SSD、磁盤陣列RAID、機械硬盤等，所以應當根據不同數據讀寫速度需求的不同，選擇不同的存儲設備以節約成本提高效率［4－5］；③數據遷移方面，數據本身的價值和使用率也處在不斷變化之中，所以就要求存儲的數據根據其價值和使用頻率的變化動態調整其存儲位置［6－7］；④數據關聯方面，空間數據本身具有地理坐標的特殊屬性，熱點數據的關聯與地理坐標密不可分。基于以上四點因素，海量空間數據分級存儲模型的研究勢在必行。

1 空間數據分級存儲模型基本內容

1.1 空間數據的特點

空間數據表現了地理空間實體的位置、大小、形狀、方向以及幾何拓撲關系。空間數據的組織表達采用柵格數據和矢量數據作為兩種最基本的形式。

遙感影像數據是一種以柵格形式表示的數據。隨著所描述范圍的擴大和空間分辨率的提高，數據量呈幾何級數地增長。

柵格數據是以二維矩陣的形式來表示空間地物的數據組織方式，每個矩陣單位稱為一個柵格單元（cell）。柵格的每個數據表示地物或現象的屬性數據，而矢量數據結構是利用點，線，面的形式來表達現實世界。然而不論是柵格數據還是矢量數據，它們都有個共同的地理坐標屬性。因此我們在對空間數據進行分級存儲時，應當充分利用空間數據的地理坐標屬性。這里在對關聯空間數據進行分級時，就充分利用了空間數據的坐標屬性，采用空間數據密度聚類算法來對關聯的空間數據進行分級。

1.2 密度聚類算法介紹

基于密度聚類算法［8］來判斷熱點數據區域，從而對關聯的熱點數據進行分級。密度聚類算法認為，在整個數據樣本空間中，各目標類族是由一群稠密樣本點組成的，而這些稠密樣本點被低密度區域（噪聲）分割，而密度聚類算法就是要濾過低密度區域，發現樣本稠密的樣本點。

DBSCAN（Density－based Spatial Clustering of Applications with Noise）［9］是一種基于高密度聯通區域的聚類算法，它將類簇定義為高密度相連點的最大集合，它本身對噪聲不敏感，并且能發現任意形狀的類簇。

1.3 空間數據分級存儲模型

本模型采用3級分層結構：硬件層、管理層、應用層（圖1）。

1.3.1 硬件層

硬件層是空間數據的存儲實體，具體的數據遷移操作都實際發生在硬件層。硬件層根據所存儲的數據熱度優先級不同，以及存儲設備自身訪問速度的不同，將數據和存儲設備都由高到低分為一一對應的1級～3級。分別是：存儲1級數據的內存DDR、存儲2級數據的固態硬盤SSD、存儲3級數據的機械硬盤。

所有數據一開始都放置在最低優先級的3級存儲設備上，系統運行中新寫入的數據一開始也都存儲在第3級存儲設備中。當最低級3級設備中的數據優先級提高，需要遷移到較高級別的設備中時，都采用復制的方式把數據拷貝到高優先級的設備中。當高級別的設備（即1級、2級）之間進行數據遷移時，都采用移動的方式進行數據遷移。

表1 設備優先級和數據熱度優先級對照表Tab.1 Equipment priority and data heat priority table

1.3.2 管理層

管理層存儲著所有空間數據的標識，負責整個系統模型的數據訪問管理、數據分級管理和數據遷移管理，管理層的具體功能通過數據管理中心實現。

數據管理中心包含一個數據訪問單元，用于管理數據的訪問操作（圖1）。

圖1 數據訪問示意圖Fig.1 Schematic diagram of data access

數據管理中心記錄了最近一月甚至更久的數據使用記錄。數據使用記錄的格式如表2所示。

表2 數據使用記錄格式Tab.2 The format of Data using record

數據管理中心存儲著所有空間數據的數據標識，這些數據構成一個數據標識散列表中。數據標識的結構如表3所示。

表3 數據標識結構Tab.3 Data identification structure

數據管理中心包含一個分級遷移控制器，它負責數據升級和數據遷移操作。當數據標識的數據使用記錄達到某個熱度升級閥值時，分級遷移控制器對數據進行遷移，并修改該數據標識的優先級和優先訪問位置。

1.3.3 應用層

應用程序根據不同的業務需求對數據進行不同的處理，實現多種多樣的功能。硬件層和管理層對應用層是透明的。當應用層需要請求數據時，直接給管理層發送所請求數據的ID，并從管理層得到該數據的訪問位置。然后應用層再直接從硬件層讀取數據，模型結構圖見圖2所示。

圖2 空間數據分級模型結構圖Fig.2 The spatial data classification model

2 基于訪問頻率和密度聚類的空間數據分級策略

2.1 分級策略思想

該分級策略是一種基于訪問頻率和密度聚類的空間數據分級策略［10］，該策略采用兩套分級規則，①用于調整被訪問數據的優先級；②用于調整關聯數據的優先級。

首先對于被訪問數據，每次數據使用時，數據管理中心都會增加一條數據使用記錄，并定時將該記錄寫入數據標識中，從而使得分級遷移控制器根據該數據最近的使用頻率，判斷該數據是否需要升級或者降級，并將優先級發生變化數據遷移到新的優先級對應的存儲設備中。

其次對于熱點關聯數據，鑒于空間數據具有顯著地地理坐標特性，當有數據提升到較高優先級時，數據管理中心的分級遷移控制器根據空間數據密度聚類算法，可以找到該被訪問數據的關聯數據，從而將熱點數據區域中的關聯數據進行熱度升級，并將其遷移到新的優先級對應的存儲設備中，以此滿足系統對高密度訪問的熱點數據進行快速訪問的需求。

2.2 分級策略實施規則

2.2.1 數據分級存儲規劃

將空間數據的優先級分為1～3級，數字越小優先級越高，數據初始放置的時候，將所有數據的優先級都定為最低優先級別3級。按1～3優先級從高到低的順序，不同優先級的數據分別存儲在內存DDR、固態硬盤SSD、機械硬盤中。

2.2.2 基于訪問頻率的熱點數據分級方法

當數據標識表中某個數據標識的使用記錄的頻率達到某個閥值時，就需要變更該數據的優先級，并對該數據做遷移，再將遷移后的優先訪問位置存入該數據標識中（圖3）。

圖3 熱點訪問數據分級示意圖Fig.3 Classification of hotspot access data

具體步驟：每次應用層使用數據時，管理層的數據管理中心都會在數據使用記錄表中增加一條使用記錄。數據使用記錄表里面存放了一個月甚至更長時間的數據使用記錄，以便以后系統功能擴展使用。數據管理中心的分級遷移控制器，每隔一分鐘定時讀取最近一分鐘的數據使用記錄，再把這一分鐘內的數據使用記錄增加到對應數據ID的數據標識表中，同時刪除該數據標識中一周以前的數據使用記錄，然后統計該數據標識中使用記錄的頻率，再根據以下數據優先級分級規則決定該數據的分級變化，若該數據優先級發生變化，升級遷移控制器則向硬件層下達數據遷移指令，遷移完成后再將新的數據優先訪問地址寫入該數據表示中。

熱點數據優先級分級規則：設定一個數據訪問頻率分級閥值K，對于每分鐘使用次數達到K1次的數據，將優先級直接提升為最高級1級；對于每小時使用次數達到K2次的數據，若當前優先級未達到2以上，則將其優先級直接提升為2級表（表4）。

表4 熱點數據優先級分級規則Tab.4 Hot data priority classification rules

2.2.3 基于密度聚類算法的關聯數據分級方法

當某個數據的優先級被提升到較高級別時，需要查找其關聯數據，然后將得到的關聯數據的優先級也相應提高（圖4）。

圖4 關聯數據升級示意圖Fig.4 Associated data upgrade

具體步驟：當數據管理中心的升級遷移控制器，檢測到某個數據的優先級被提升到較高級別時，升級遷移控制器就通過空間數據密度聚類算法得到其關聯數據的一組數據ID，并將這組數據ID對應的數據優先級提升為該數據優先級的下一級別，并將這些數據依次遷移到新的存儲設備中，然后將新的優先訪問位置更新到數據標識中。

關聯數據優先級分級規則：因為第2級數據的下一級別為最低級3級，所以對第2級數據進行聚類算法查找關聯數據是沒有意義的；同時也因為聚類算法會占用大量計算資源，所以只有當數據的優先級被提高到較高的優先級時，才對該數據進行空間數據密度聚類算法找出其關聯數據，并提升其關聯數據的級別。具體規則為：當某一數據的優先級被提高到1級時，對該數據進行一次空間數據密度聚類算法，對于聚類算法得到的相關數據，若這些相關數據的級別未達到2級以上，則將這些相關數據的優先級提升為2級。

3 空間數據分級存儲模型實驗

3.1 實驗數據及實驗環境

實驗數據對象選擇的是嫦娥2號遙感數據（1T）。作為空間數據的一種，嫦娥2號遙感數據具有量大、數據結構復雜的特點，處理起來速度非常慢。通過對數據進行分級存儲實驗，驗證該方法的效率。

實驗環境部署在三臺DELL PowerEdge 2950服務器上面，一臺部署應用程序用于請求遙感數據；一臺部署數據管理中心用于分級和調度遙感數據；一臺部署為硬件層用于存儲數據，并額外掛載了多種存儲設備，實現數據分級存儲（表5）。

3.2 熱點訪問數據分級策略數據遷移實驗

該實驗通過模擬高頻率數據調用，得到了各數據升級閥值K值在不同取值下的設備利用率，收據訪問命中率及數據平均訪問延遲曲線。

表5 實驗環境Tab.5 Experimental environment

3.2.1 實驗結果

由圖5可以看出，隨著應用程序對數據的持續訪問，一級設備的利用率會不斷增加并逐漸趨于穩定；其中當K1取值10次／s時，設備率利用率最高。

由圖6可以看出，隨著應用程序對數據的持續訪問，數據訪問在一級設備中的命中率不斷增加；但是當K1取值10次／s時，由于設備使用率滿負荷導致命中率陡然降低。

圖5 一級SSD設備利用率在不同K1值的變化曲線Fig.5 Change curve of level 1SSD equipment utilization in differentvalues of K1

圖6 一級SSD設備數據訪問命中率在不同K1值的變化曲線Fig.6 Change curve of level 1SSD equipment data access shot in differentvalues of K1

由圖7可以看出，隨著應用程序對數據的持續訪問，數據訪問的平均延遲逐漸減小，分級存儲的優勢不斷顯現，但是當K1取值10次／s時，由于設備很快滿負荷，導致數據延遲陡然增加。

圖7 數據平均訪問延遲在不同K1值的變化曲線Fig.7 Change curve of average data access delay in different values of K1

3.2.2 實驗分析及結論

綜合以上三個實驗指標，可以發現當K1取值10次／s時，設備利用率最高，但由于設備很快滿負荷運轉，會導致系統運行緩慢，影響數據命中率和數據訪問速度；當看取值20次／s時，數據命中率和數據訪問延遲最佳。綜合分析可以知道，當數據升級閥值K1取值20次／s時，系統的綜合性能最佳。

3.3 關聯數據分級策略數據遷移實驗

該實驗通過對關聯數據的遷移測試，在實驗一中得到的最佳升級閥值K1取值20次／s的情況下，對有無運用關聯數據分級策略二者之間的數據訪問延遲進行比較，以及對二者數據遷移量的大小進行比較，以此驗證關聯數據遷移策略的優勢。

熱點數據升級閥值K1取最佳值20次／s，隨著系統的運行，高級設備中的熱點數據慢慢增加，數據更多的在高速存儲設備中訪問，使得數據訪問的整體延遲逐漸減小，并且在采用了基于空間數據密度聚類算法的關聯數據分級策略后，數據的訪問延遲總體減少，加快了數據的訪問速率。

從圖9可以看出，隨著數據訪問的繼續，系統單位時間內的數據遷移量由高到低逐漸趨于平穩。采用了關聯數據分級策略后，系統的數據遷移量會有所減少，從而緩解了系統的性能。

4 結束語

大數據時代，帶來了海量遙感遙測，地質災害等空間信息數據存儲的問題。作者提出了一種基于熱點訪問頻率的數據分級策略和一種基于空間數據密度聚類算法的數據分級策略。通過對嫦娥2號數據進行模擬實驗，提升了數據升級閾值，大大加快了熱點數據的訪問速率，并充分利用了高級存儲設備的利用率。由于關聯數據分級策略的貢獻，使得設備的數據遷移量明顯降低。整體的分級存儲策略及模型，實現了空間數據的高效存儲，為海量空間信息數據存儲提供了一個可行解決方案。

圖8 有無關聯數據分級策略的數據訪問延遲比較Fig.8 Data access delay compareof associated data and no associated dataclassification strategyin best upgrade threshold

圖9 有無關聯數據分級策略下的單位之間數據遷移量對比Fig.9 Data migration quantity between unitscontrast ofassociated data and no associated datain best upgrade threshold

［1］ 百度百科.面向數據的體系結構［OL］.http：／／baike.baidu.com／subview／649092／12822804.htm. Baidu Encyclopedia.DOA［OL］.http：／／baike.baidu.com／subview／649092／12822804.htm.（In Chinese）

［2］ 聶雪軍，秦磊華，周敬利.內容感知存儲系統中自動分級存儲模型研究［J］.小型微型計算機系統，2011，32 （6）：1151－1156.

NIE X J，QIN L H，ZHOU J L.Research on auto－tiering storage model in content aware storage system ［J］.Journal of Chinese Computer Systems，2011，32 （6）：1151－1156.（In Chinese）

［3］ 劉曉然.基于文件的數據分級存儲的研究與實現［D］.昆明：昆明理工大學，2013.

LIU X R.Research and implementation of data－based hierarchical storage of files［D］.Kunming：Kunming University of Science and Technology，2013.（In Chinese）

［4］ MEI H，LING X，LI G B，A data migration strategy for HSM based on data value［J］.Journal of Information ＆Computational Science，2011，8（2）：312－319.

［5］ ZOLGHADRI M J，MANSOORI E G.Weighting fuzzy classification rulesusing receiver operating characteristics（ROC）analysis［J］.Information Sciences，2007，177（11）：2296－2307.

［6］ 敖莉，于得水，舒繼武，等.一種海量數據分級存儲系統TH－TS［J］.計算機研究與發展，2011，48（6）：1089－1100.

AO L，YU D SH，SHU J W，et al.A tiered storage system for massive data：TH－TS［J］.Journal of Computer Research and Development，2011，48（6）：1089－1100.（In Chinese）

［7］ 呂帥.基于對象的分級存儲系統數據遷移技術研究［D］.長沙：國防科學技術大學，2009.

LV SH.Research on object－based data migration technology of hierarchical storage system［D］.Changsha：National University of Defense Technology，2009.（In Chinese）

［8］ 王芳，張順達，馮丹，等.對象存儲系統中的柔性對象分布策略［J］.華中科技大學學報：自然科學版，2007，35 （3）：46－48.

WANG F，ZHANG SH D，FENG D，et al.Hybrid object allocation policy for object storage systems［J］.Journal of Huazhong University of Science and Technology：Natural Science Edition，2007，35（3）：46－48.（In Chinese）

［9］ 聶躍光.基于密度聚類的空間數據挖掘算法研究［D］.太原：太原科技大學，2008.

NIE Y G.Study of spatial data mining algorithm based on density clustering［D］.Taiyuan：Taiyuan University of Science and Technology，2008.（In Chinese）

［10］馮少榮，肖文俊.DBSCAN聚類算法的研究與改進［J］.中國礦業大學學報，2008，37（1）：105－110.

FENG SH R，XIAO W J.An improved DBSCAN clustering algorithm［J］.Journal of China University of Mining ＆Technology，2008，37（1）：105－110.（In Chinese）

［11］于彥偉，王沁，鄺俊，等.一種基于密度的空間數據流在線聚類算法［J］.自動化學報，2012，38（6）：1051－1058.

YU Y W，WANG Q，KUANG J，et al.An on－line density－based clustering algorithm for spatial data stream［J］.Acta Automatica Sinica，2012，38（6）：1051 －1058.（In Chinese）

Research of tiered storage model for massive spatial data

YANG Wen－hui1a，YUAN Jin－jun1a＊，MIAO Fang1a，1b，2
（1.Chengdu University of Technology a.Key Lab of Earth Exploration ＆Information Techniques of Ministry of Education，Chengdu University of Technology，b.State Key Laboratory of Geohazard Prevention and Geoenvironment Protection，Chengdu 610059，China；2.Key Lab of Pattern Recognition and Intelligent Information Processing of University of Sichuan Province，Chengdu College，Chengdu 610106，China）

With the rapid development of space information technology and remote sensing technology，vast amounts of spatial information data like remote sensing and geological disasterwere produce.How reasonable tier stored massive spatial data to make meet the needs of applications like spatial information and geographic information is becoming an increasingly urgent problem.Hierarchical storage massive spatial data as a new model for solving the problem put forward new ideas.Combined with the characteristics of massive spatial data and rule of daily data application，put forward the data presented hierarchical data storage model and the associated heat－based access massive spatial clustering，the model includes hot data classification，association data classification，data migration in three parts.Finally，simulation access testing on Change 2remote sensing data optimized the threshold of data upgrade；it proved the feasibility of the tiered storage model for spatial data.

spatial data；remote Sensing；tiered storage；density clustering algorithm；data association

TP 301

：A

10.3969／j.issn.1001－1749.2015.06.19

1001－1749（2015）06－0783－07

2014－11－11改回日期：2015－04－19

國家自然科學基金項目（61071121）；成都市經信委科技專項項目（201102153）

楊文暉（1969－），女，副教授，從事計算機技術及應用方向的研究，E－mail：ywhui＠cdut.edu.cn。

＊通信作者：袁進俊（1989－），男，碩士，從事分布式存儲與計算、空間信息技術及應用方向的研究，E－mail：373611905＠qq.com。