一種面向智能交通場景的HBase時空索引設計

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

關鍵詞：智能交通;時空索引;HBase;加鹽算法;GoogleS2

中圖分類號：TP311.133.1

文獻標識碼：A

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

收稿日期：2019-12-05

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

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

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等新一代信息技術的崛起，智慧城市在中國經歷了井噴式的發展。據政府公開信息統計，僅在2013年至2018，年六年時間內，由各地方政府委托的智慧城市項目的中標數量從12個激增至162個，年復合增長率超過45%。智慧交通作為智慧城市的重要組成部分，可通過對城市交通時空數據進行分析，為公安、公路、交管等部門的決策提供依據，以支撐交通誘導、應急指揮、線路優化等應用。

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

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

2 研究現狀

原生的HBase接口僅提供了Get、Scan、Filter等基礎查詢操作，不支持數據多維查詢。隨著HBase的大規模應用，其在多維查詢方面的限制也日益明顯。國內外關于HBase如何支持多維時空索引的研究從未停止過。下面針對主要研究結果做簡要介紹：

2.1 二級索引

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

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

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

2.2 時空索引

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

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

3 基于HBase的時空數據索引方案

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

3.1 索引結構設計

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

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

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

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

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

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

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

通過上述五部分組合生成的Rowkey即為時空索引，索引對應的數據主體內容通過ProtoBuf序列化為二進制數組，作為Rowkey對應的內容存人列簇中。

3.2 檢索流程設計

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

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

4 實驗結果及分析

4.1 實驗環境與數據

本文實驗的硬件環境為40臺至強E5-2620CPU、256CB內存、48TB硬盤配置的服務器。軟件環境為Hadoop 2.5.0、HBase 0.98.6、JDK 8、Centos 6操作系統。

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

4.3 實驗結果及分析

本文實驗的主要目的是測試在不同區域范圍、不同時間范圍下時空索引的性能表現。同時統計該時空索引下HBase各分區數據分布情況，驗證是否存在熱點。

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

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

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

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

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

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

4.3.3 存量數據的分區分布統計

根據HBase在HDFS存儲路徑下各個分區所對應的文件大小。形成統計圖如下圖5所示。在建表時預置了256個分區，最大分區249GB，最小分區為226GB。得益于加鹽算法的調優，從分布看，絕大多數分區的大小控制在230GB到245GB之間。沒有出現數據熱點的情況。

5 結束語

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

參考文獻：

[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]葉小平，郭歡，湯庸，等.基于相點分析的移動數據索引技術[J].計算機學報，2011，34（）：256-274.

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

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

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

[7]鄒敏昊.基于Lucene的HBase全文檢索功能的設計與實現[D].南京：南京大學，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]房俊，李冬，郭會云，等.面向海量交通數據的HBase時空索引[J].計算機應用，2017，37（2）：311-315.

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

[通聯編輯：謝媛媛]