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

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

中圖分類號(hào)：TP311.133.1

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

文章編號(hào)：1009-3044（2020）04-0163-03

收稿日期：2019-12-05

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

作者簡(jiǎn)介：劉一流（1991—），男，河南許昌人，助理工程師，碩士，主要研究方向?yàn)闀r(shí)空大數(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ù)的崛起，智慧城市在中國(guó)經(jīng)歷了井噴式的發(fā)展。據(jù)政府公開(kāi)信息統(tǒng)計(jì)，僅在2013年至2018，年六年時(shí)間內(nèi)，由各地方政府委托的智慧城市項(xiàng)目的中標(biāo)數(shù)量從12個(gè)激增至162個(gè)，年復(fù)合增長(zhǎng)率超過(guò)45%。智慧交通作為智慧城市的重要組成部分，可通過(guò)對(duì)城市交通時(shí)空數(shù)據(jù)進(jìn)行分析，為公安、公路、交管等部門(mén)的決策提供依據(jù)，以支撐交通誘導(dǎo)、應(yīng)急指揮、線路優(yōu)化等應(yīng)用。

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

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

2 研究現(xiàn)狀

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

2.1 二級(jí)索引

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

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

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

2.2 時(shí)空索引

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 檢索流程設(shè)計(jì)

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

4.3 實(shí)驗(yàn)結(jié)果及分析

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

4.3.1 固定空間條件的查詢測(cè)試

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

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

4.3.2 固定時(shí)間條件的查詢測(cè)試

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

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

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

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

5 結(jié)束語(yǔ)

本文針對(duì)基于HBase存儲(chǔ)的海量時(shí)空數(shù)據(jù)多維查詢場(chǎng)景，結(jié)合智能交通應(yīng)用的查詢特點(diǎn)，在現(xiàn)有研究的基礎(chǔ)上提出了一種基于HBase原生接口的、結(jié)構(gòu)簡(jiǎn)單的時(shí)空索引結(jié)構(gòu)。利用加鹽算法解決現(xiàn)有索引結(jié)構(gòu)的HBase數(shù)據(jù)熱點(diǎn)問(wèn)題，利用GoogleS2算法替換Geohash算法以解決查詢層級(jí)間覆蓋范圍跳變的問(wèn)題。經(jīng)實(shí)驗(yàn)驗(yàn)證，該時(shí)空索引結(jié)構(gòu)設(shè)計(jì)在TB級(jí)存儲(chǔ)場(chǎng)景下獲得了較好的查詢檢索性能，能夠滿足智能交通場(chǎng)景下時(shí)空碰撞、熱力圖、車輛伴隨、道路擁堵分析等應(yīng)用的需求。但是需要：注意的是，該時(shí)空索引中的加鹽算法針對(duì)應(yīng)用場(chǎng)景在時(shí)間條件與空間條件上做了妥協(xié)。在實(shí)踐中需根據(jù)常用時(shí)空條件的范圍對(duì)加鹽算法的參數(shù)進(jìn)行調(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]葉小平，郭歡，湯庸，等.基于相點(diǎn)分析的移動(dòng)數(shù)據(jù)索引技術(shù)[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（）：256-274.

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

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

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

[7]鄒敏昊.基于Lucene的HBase全文檢索功能的設(shè)計(jì)與實(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]房俊，李冬，郭會(huì)云，等.面向海量交通數(shù)據(jù)的HBase時(shí)空索引[J].計(jì)算機(jī)應(yīng)用，2017，37（2）：311-315.

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

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