摘要：針對HBase無法直接實現(xiàn)海量時空數(shù)據(jù)查詢的問題，結(jié)合智能交通的常用場景，提出一種基于原生HBase接口的、結(jié)構(gòu)簡單的時空索引設(shè)計。首先引入基于時間與空間信息的加鹽算法作為索引前綴，以避免產(chǎn)生HBase數(shù)據(jù)讀寫熱點。然后利用Google S2算法將經(jīng)緯度信息降維為一維編碼，與時間、數(shù)據(jù)類型標(biāo)識等字段組合形成時空索引。最后通過實驗驗證了所提出的HBase時空索引設(shè)計在TB級存儲場景下多維查詢的性能和數(shù)據(jù)分布。

關(guān)鍵詞：智能交通;時空索引;HBase;加鹽算法;GoogleS2

中圖分類號：TP311.133.1

文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）04-0163-03

收稿日期：2019-12-05

基金項目：重慶市公安局科技攻關(guān)計劃項目（項目編號：G2018-15）

作者簡介：劉一流（1991—），男，河南許昌人，助理工程師，碩士，主要研究方向為時空大數(shù)據(jù)挖掘。

Spatio-temporal Index for Intelligent Transportation System Based on HBase

LIU Yi-liu

（Chongqing Municipal Public Security Bureau，Chongqing 401 120，China）

Abstract：Focusing on the issue that HBase couldn ' t execute multiple analysis directly when processing massive traffic data，a spatio-temporal index Based on HBase was proposed to support intelligent transportation applications.Firstly，a salting algorithm with temporal parameter and spatial parameter was introduced to generate rowkey prefix in order to avoid the data workload hot spot.Secondly，the di-mensionality reduction method Based on Google S2 was used to convert two-dimensional spatial position data into one-dimensional code，then the code was combined with elements like temporal dimension，data type and so on to generate the whole spatio-temporal in-dex.Finally，the experimental results show that the proposed HBase spatio-temporal index can effectively improve the traffic data que-ry performance when the data storage size is over TB.

Key words：intelligent transportation;spatio-temporal index;HBase;salting algorithm;Google S2

1 背景

隨著5G等新一代信息技術(shù)的崛起，智慧城市在中國經(jīng)歷了井噴式的發(fā)展。據(jù)政府公開信息統(tǒng)計，僅在2013年至2018，年六年時間內(nèi)，由各地方政府委托的智慧城市項目的中標(biāo)數(shù)量從12個激增至162個，年復(fù)合增長率超過45%。智慧交通作為智慧城市的重要組成部分，可通過對城市交通時空數(shù)據(jù)進行分析，為公安、公路、交管等部門的決策提供依據(jù)，以支撐交通誘導(dǎo)、應(yīng)急指揮、線路優(yōu)化等應(yīng)用。

依托監(jiān)控、物聯(lián)網(wǎng)等技術(shù)，城市交通所產(chǎn)生的時空數(shù)據(jù)量級呈爆炸式發(fā)展，傳統(tǒng)關(guān)系型數(shù)據(jù)庫在存儲與處理這些數(shù)據(jù)時顯得力不從心。以HBase為代表的分布式NoSQL數(shù)據(jù)庫在海量數(shù)據(jù)存儲場景下具有優(yōu)異的表現(xiàn)，并能集成MapReduce、Spark等計算框架作為工具對存儲的數(shù)據(jù)進行大規(guī)模分析。但HBase 自身也存在種種限制，如只有在基于Rowkey查詢時才能獲得高性能、只能通過內(nèi)置Filter執(zhí)行過濾操作、原生不支持SQL語句等。

目前已有部分將HBase應(yīng)用于時空數(shù)據(jù)的研究。時空數(shù)據(jù)的快速檢索查詢一般都是通過建立高效的時空索引來實現(xiàn)，常用的時空索引包括R-Trees、Quad-Trees和K-DimensionTreesl[1-4]等結(jié)構(gòu)。但上述時空索引方案在落地過程中，存在結(jié)構(gòu)復(fù)雜、數(shù)據(jù)存儲不平衡、對存儲組件入侵性大等缺點。本文主要討論一種基于原生HBase接口的，針對智慧交通特有場景，設(shè)計結(jié)構(gòu)簡單高效、對組件無侵入的索引方案，以支撐TB級智慧交通時空數(shù)據(jù)的檢索。

2 研究現(xiàn)狀

原生的HBase接口僅提供了Get、Scan、Filter等基礎(chǔ)查詢操作，不支持?jǐn)?shù)據(jù)多維查詢。隨著HBase的大規(guī)模應(yīng)用，其在多維查詢方面的限制也日益明顯。國內(nèi)外關(guān)于HBase如何支持多維時空索引的研究從未停止過。下面針對主要研究結(jié)果做簡要介紹：

2.1 二級索引

國內(nèi)外主要的Paas層廠商在其Hadoop平臺中將HBase二級索引作為一種企業(yè)增強特性，以彌補HBase在多維查詢方面的短板。其思路是通過借助協(xié)處理器[5]、Solr[6]、ElastieSearch[7]等組件為所需查詢的維度生成二級索引。

以華為的HIdex方案為例，每當(dāng)插入一條數(shù)據(jù)時，會通過RegionServer上的協(xié)處理器對該數(shù)據(jù)中需要索引的列生成二級索引。用戶在查詢索引列數(shù)據(jù)時，通過調(diào)用華為重寫的SingleColumnValueFilter等過濾器，會自動查詢二級索引，極大的縮短查詢時間。

二級索引作為一種通用的多維索引解決方案，其缺點也非常明顯，基于協(xié)處理器的二級索引在列簇設(shè)置TL的場景下會出現(xiàn)索引與原始數(shù)據(jù)不一致的情況，多列數(shù)據(jù)做聯(lián)合索引的場景下查詢條件依然受限?；贓lasticSearch和Solr的實現(xiàn)的二級索引方案受搜索引擎組件自身性能的限制。并不適合直接拿來做時空數(shù)據(jù)檢索。

2.2 時空索引

GeoMesal[8]是一款由LocationTech開源的地理大數(shù)據(jù)處理工具套件，借助HBase、Cassandra、Accumulo等分布式存儲，通過基于三階Z-order填充曲線方法的Z3/XZ3索引，對經(jīng)度、緯度時間三個維度進行編碼，向用戶提供大規(guī)模時空數(shù)據(jù)查詢能力。該方案對HBase組件的侵入較大，時空數(shù)據(jù)的寫人和讀取請求都需通過獨立的GeoServer處理，不利于與Mapreduce、Spark等分布式計算引擎進行整合。

文獻(xiàn)[9]和文獻(xiàn)[10]分別提出了兩種基于Geohash編碼與時間組合的時空索引結(jié)構(gòu)，這類索引實現(xiàn)簡單，對組件無入侵。文獻(xiàn)[9]中的索引方案以時間中的年月部分和Geohash前綴組合作為Rowkey，通過列簇和列名區(qū)分不同日期的數(shù)據(jù)。該方案在數(shù)據(jù)日增量過億的場景下，單個Rowkey下存儲的數(shù)據(jù)過多，無法獲得理想的查詢性能。文獻(xiàn)[10]中探討了四種時間與Geohash組合生成Rowkey的方式，并分析了每種組合所適用的場景。但四種方案都使用時間或Geohash字段作為Rowkey前綴，在實踐中都會造成HBase讀寫熱點等問題，無法發(fā)揮HBase分布式存儲的優(yōu)勢。同時，上述兩種方案所依賴的Geohash算法在空間填充曲線上存在突變，并且Geohash在選擇不同長度的前綴查詢時，覆蓋范圍跳變很大，在實踐中很難選擇合適的前綴長度。只能用較大范圍的前綴覆蓋需要查詢的區(qū)域，對數(shù)據(jù)再做過濾，直接影響到查詢效率。

3 基于HBase的時空數(shù)據(jù)索引方案

本文在研究各種Geohash編碼與時間組合生成時空索引方案的基礎(chǔ)上，借鑒其將經(jīng)緯度編碼降維后與時間組合的思路，針對HBase存在讀寫熱點、Geohash覆蓋范圍跳變等問題做出改進。在HBase原生接口的基礎(chǔ)上，設(shè)計一種無入侵、結(jié)構(gòu)簡單的時空索引。

3.1 索引結(jié)構(gòu)設(shè)計

通過對智能交通場景下應(yīng)用需求進行調(diào)研，在時空碰撞、車輛伴隨、道路擁堵分析等應(yīng)用中，一般查詢的時間條件跨度為小時級別，常用空間查詢條件的覆蓋范圍多數(shù)不超過60000平方米，要求當(dāng)查詢條件均符合上述范圍時能實時響應(yīng)查詢請求。同時支持超出上述條件范圍的查詢請求，以支撐熱力圖、人流遷徙等應(yīng)用。

針對上述應(yīng)用需求，將經(jīng)緯度通過Google S21[11]算法降維編碼生成CellID，并將時間與CllID等信息組合作為HBase Rowkey構(gòu)建時空索引，具體結(jié)構(gòu)如圖1所示，索引由五部分組成。

第一部分是鹽值，鹽值由時間和CelID值計算得到。首先截取數(shù)據(jù)中時間的年月日小時（yyMMddhh）部分，CellID以能夠覆蓋常用查詢范圍為基準(zhǔn)，截取固定長度的前綴。然后將截取后的時間與CellID前綴合并做散列運算，散列運算的返回結(jié)果范圍控制在0到255之間，放在Rowkey的第一個字節(jié)。在HBase建表時，根據(jù)存儲數(shù)據(jù)的總量對表格做預(yù)分區(qū)，預(yù)分區(qū)數(shù)量最高支持256個。時空數(shù)據(jù)基于其鹽值均勻地分布在不同分區(qū)中，以解決HBase寫熱點的問題。

第二部分是時間，時間被截成年月日時（yyMMddhh）和分秒（mmss）兩部分，其中yyMMddhh部分用于將數(shù)據(jù)按小時維度切割，以在查詢時間條件為小時級時獲得最佳的性能。由于mmss部分拼接在CellID后，所以該部分不能作為Scan操作時的過濾條件，只能在Scan的結(jié)果返回后對結(jié)果集再做過濾。

第三部分是elID，CllID是基于GoogleS2算法將經(jīng)緯度映射為投影上的坐標(biāo)后，通過希爾伯特填充曲線對坐標(biāo)編碼后生成的一個長整形數(shù)字。S2算法可以通過兩個CellID限定的區(qū)間范圍表示地圖上的一個區(qū)域。與Geohash相似的是S2可根據(jù)CllID前綴的長度控制其覆蓋的范圍，但是elllID不同長度的前綴覆蓋范圍跳變比Geohash更為平緩，同時可以通過調(diào)用S2庫的getCovering方法計算任意多邊形內(nèi)包含的所有S2塊。比Geohash使用更為簡潔。

第四部分是數(shù)據(jù)類型標(biāo)識，在智慧交通場景下，往往既希望能將不同部門采集的數(shù)據(jù)整合使用，又希望在需要時單獨查詢其中的某一種。通過在索引結(jié)構(gòu)中增加數(shù)據(jù)類型標(biāo)志字段，缺省情況下可默認(rèn)查詢所有類型的數(shù)據(jù)，當(dāng)需要查詢某個固定類型的數(shù)據(jù)時，通過添加FuzzyRowFilter可過濾指定數(shù)據(jù)類型標(biāo)識的數(shù)據(jù)。

第五部分是數(shù)據(jù)MD5，將例如車牌等信息的MD5值作為時空索引的后綴，既可以避免時間、空間、數(shù)據(jù)類型標(biāo)識完全相同的數(shù)據(jù)在寫入時相互覆蓋，也可以在時空碰撞等場景通過MD5實現(xiàn)去重。

通過上述五部分組合生成的Rowkey即為時空索引，索引對應(yīng)的數(shù)據(jù)主體內(nèi)容通過ProtoBuf序列化為二進制數(shù)組，作為Rowkey對應(yīng)的內(nèi)容存人列簇中。

3.2 檢索流程設(shè)計

該索引設(shè)計在時間跨度小于一小時、查詢空間條件未超過鹽值中CellID截取范圍的情況下能夠獲得最佳檢索性能。在上述理想條件下，根據(jù)查詢時間條件的年月日小時（yyMMddhh）部分和空間條件所對應(yīng)的CellID值可直接計算出HBaseScan操作的Rowkey范圍，再對返回數(shù)據(jù)中時間的分秒（mmss）部分做過濾，即可獲得符合條件的所有結(jié)果。但在實際應(yīng)用中，查詢時間條件可能會橫跨數(shù)天，查詢空間條件也可能需要一組Cel-IID才能覆蓋。此時上述時空索引設(shè)計無法直接獲得查詢結(jié)果，需要對查詢條件進行分解。檢索流程如圖2所示。

對于需要分解的查詢請求，首先按小時對查詢的時間條件進行分割。然后調(diào)用Google S2算法庫中的getCovering方法，獲取查詢區(qū)域包含的所有S2塊。將分割后的時間和S2塊組合為一組請求，并行向HBase發(fā)起查詢。最后將所有返回結(jié)果過濾后執(zhí)行并集操作，即可獲得符合時空檢索條件的數(shù)據(jù)。由于不同請求計算出的鹽值不一樣，分解后的查詢操作會被分發(fā)到不同的分區(qū)上并行執(zhí)行，以充分發(fā)揮HBase作為分布式存儲的優(yōu)勢。

4 實驗結(jié)果及分析

4.1 實驗環(huán)境與數(shù)據(jù)

本文實驗的硬件環(huán)境為40臺至強E5-2620CPU、256CB內(nèi)存、48TB硬盤配置的服務(wù)器。軟件環(huán)境為Hadoop 2.5.0、HBase 0.98.6、JDK 8、Centos 6操作系統(tǒng)。

實驗數(shù)據(jù)來自某智能交通項目。該項目平均每日時空數(shù)據(jù)條目增量為百億級，總計存量數(shù)據(jù)超過千億條，除去備份等因素，原始時空數(shù)據(jù)經(jīng)Snappy算法壓縮后占用存儲約60TB。原始數(shù)據(jù)樣例如表1所示。

4.3 實驗結(jié)果及分析

本文實驗的主要目的是測試在不同區(qū)域范圍、不同時間范圍下時空索引的性能表現(xiàn)。同時統(tǒng)計該時空索引下HBase各分區(qū)數(shù)據(jù)分布情況，驗證是否存在熱點。

4.3.1 固定空間條件的查詢測試

模擬針對某商圈車流分析場景，查詢空間條件固定為6萬平方米的矩形，分別記錄查詢不同時間條件下返回的數(shù)據(jù)條數(shù)和耗時，形成統(tǒng)計圖如圖3所示。

可見隨著查詢時間范圍的增加，返回數(shù)據(jù)條數(shù)呈類似線性增長。受HBase拉取數(shù)據(jù)量增加的影響，查詢耗時有所增加。但得益于查詢被分割成多個查詢請求多線程執(zhí)行，在查詢時間條件超過60分鐘的情況下，查詢耗時并沒有隨著時間條件呈線性增加，穩(wěn)定在3.5秒左右。

4.3.2 固定時間條件的查詢測試

隨機設(shè)定查詢時間范圍為一小時。分別記錄查詢不同空間條件下返回的數(shù)據(jù)條數(shù)和耗時，形成統(tǒng)計圖如圖4所示。

隨著空間條件的范圍不斷擴大，返回數(shù)據(jù)條數(shù)和耗時都有了明顯增加。在查詢空間條件小于20000平方米的情況下，因查詢請求未滿足分解條件，只會通過單線程拉取數(shù)據(jù)，此時從HBase拉取數(shù)據(jù)的平均速度在每秒25000條左右。當(dāng)查詢空間條件大于20000平方米時，查詢會按照空間條件被分解為多個請求并行處理，拉取數(shù)據(jù)的平均速度增加至每秒85000條。隨著查詢的空間條件進-步增加，分解后的請求并行數(shù)會隨之增加，進而提升每秒從HBase拉取數(shù)據(jù)的速度，減少查詢耗時。

4.3.3 存量數(shù)據(jù)的分區(qū)分布統(tǒng)計

根據(jù)HBase在HDFS存儲路徑下各個分區(qū)所對應(yīng)的文件大小。形成統(tǒng)計圖如下圖5所示。在建表時預(yù)置了256個分區(qū)，最大分區(qū)249GB，最小分區(qū)為226GB。得益于加鹽算法的調(diào)優(yōu)，從分布看，絕大多數(shù)分區(qū)的大小控制在230GB到245GB之間。沒有出現(xiàn)數(shù)據(jù)熱點的情況。

5 結(jié)束語

本文針對基于HBase存儲的海量時空數(shù)據(jù)多維查詢場景，結(jié)合智能交通應(yīng)用的查詢特點，在現(xiàn)有研究的基礎(chǔ)上提出了一種基于HBase原生接口的、結(jié)構(gòu)簡單的時空索引結(jié)構(gòu)。利用加鹽算法解決現(xiàn)有索引結(jié)構(gòu)的HBase數(shù)據(jù)熱點問題，利用GoogleS2算法替換Geohash算法以解決查詢層級間覆蓋范圍跳變的問題。經(jīng)實驗驗證，該時空索引結(jié)構(gòu)設(shè)計在TB級存儲場景下獲得了較好的查詢檢索性能，能夠滿足智能交通場景下時空碰撞、熱力圖、車輛伴隨、道路擁堵分析等應(yīng)用的需求。但是需要：注意的是，該時空索引中的加鹽算法針對應(yīng)用場景在時間條件與空間條件上做了妥協(xié)。在實踐中需根據(jù)常用時空條件的范圍對加鹽算法的參數(shù)進行調(diào)優(yōu)，以獲得最佳查詢性能。

參考文獻(xiàn)：

[1]Kothuri R K V，Ravada S，Abugov D.Quadtree and R-tree in-

dexes in oracle spatial[C]/Proceedings of the 2002 ACM SIG-MOD international conference on Management of data一SIG-MOD '02，June 3-6，2002.Madison，Wisconsin.New York，USA：ACM Press，2002.

[2]Gong J，Ke S，Zhu Q，et al.An efficient trajectory data index

integrating R-tree，hash and B*-tree[J].Acta Geodaetica et Cartographica Sinica，2015，44（5）：570-577.

[3]葉小平，郭歡，湯庸，等.基于相點分析的移動數(shù)據(jù)索引技術(shù)[J].計算機學(xué)報，2011，34（）：256-274.

[4]尹章才，李霖，王琤.基于HR-樹擴展的時空索引機制研究[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2007，32（12）：1131-1134.

[5]丁飛，陳長松，張濤，等.基于協(xié)處理器的HBase區(qū)域級第二索引研究與實現(xiàn)[J].計算機應(yīng)用，2014（z1）：181-185.

[6]王文賢，陳興蜀，王海舟，等.一種基于Solr的HBase海量數(shù)據(jù)二級索引方案[].信息網(wǎng)絡(luò)安全，2017（8）：39-44.

[7]鄒敏昊.基于Lucene的HBase全文檢索功能的設(shè)計與實現(xiàn)[D].南京：南京大學(xué)，2013.

[8]James N Hughes，Andrew Annex，Christopher N.Eichelberger，Anthony Fox，Andrew Hulbert，Michael Ronquest.GeoMesa：a distributed architecture for spatio-temporal fusion[P].Defense + Security Symposium，2015.

[9]Fox A，Eichelberger C，Hughes J，et al.Spatio-temporal index-

ing in non-relational distributed databases[C]//2013 IEEE International Conference on Big Data，October 6-9，2013.Sili-con Valley，CA，USA.EEE，2013：.

[10]房俊，李冬，郭會云，等.面向海量交通數(shù)據(jù)的HBase時空索引[J].計算機應(yīng)用，2017，37（2）：311-315.

[11].Google.S2 Geometry[EB/OL].（2019-12-03）.http：//s2geome-try.io.

[通聯(lián)編輯：謝媛媛]