面向軌跡流數據的索引構建與存儲方法研究

蔡瑞初，林峰極，郝志峰，2，王 立，溫 雯

（1.廣東工業大學計算機學院，廣州 510006；2.佛山科學技術學院數學與大數據學院，廣東佛山 528000；3.依圖網絡科技有限公司新加坡研發部，新加坡 018960）

0 概述

隨著信息處理技術的快速發展，人們生活各方面產生的數據量呈現幾何級增長，對分布式計算與數據存儲提出更高要求。在企業大數據應用需求推動下，Hadoop、Storm 和Flink 等分布式計算框架相繼出現并顯著加快了數據處理速度，其中Storm 是一種分布式流式計算處理框架，可使任務分布到集群中進行。Google 公司的GFS、HDFS 以及基于CEPH 的CephFS 等分布式存儲系統支持文件及對象的快速讀寫，可存儲大規模數據。key-value 模型［1］與以Redis 為代表的NoSQL 型數據庫是目前使用廣泛的存儲模型。

在移動社交網絡和基于位置的服務領域，每秒都會有大量軌跡數據產生。為便于分析與管理，數據存儲系統需在存儲高速軌跡數據流的同時支持低延遲的時間范圍查詢。例如，在以每秒約百萬個元組的速度記錄實時GPS 數據的同時，對最近5 min 內獲取的某個地理區域中全部GPS 數據進行交互式查詢。然而現有的HBase 等數據存儲方案無法同時實現數據的高速插入與低延遲時間范圍查詢。此外，對大量數據進行低延遲時間范圍查詢需在時空列上創建索引，且元組插入與索引更新結合后產生大量時間開銷，導致高吞吐量的插入無法實現。同時，由于眾多場景要求數據元組在其到達時立即可見，因此不能采用基于批處理的插入來降低索引更新成本。

為實現海量流數據的實時存儲與高效查詢，本文提出一種分布式數據處理方法。針對高吞吐量流數據，構建具有對應拓撲結構的分布式集群模型，采用數據分區模式和基于內存索引的壓縮存儲方法，降低底層文件系統負載壓力并提高數據插入效率，通過多級索引機制提升復雜查詢的分解與訪問效率，減少無關數據的查詢處理，同時構建完整的分布式存儲系統，以支持join 和聚集函數等數據庫常用復雜查詢模式。

1 相關背景

集群架構、索引結構、機器性能以及事務支持等因素均會影響流數據的寫入速率，目前HBase［2］、Dynamo［3］、BigTable［4］、CLAIMS［5］和Druid［6］等數據存儲方案主要通過分布式集群來存儲和管理大量數據。BigTable 及其開源實現HBase 將數據組織為分布式多維排序映射，并可提供高效的可擴展查詢，但以其為代表的鍵值在時間范圍上對數據庫查詢能力較差。Druid 通過數據預聚合和倒排索引實現快速查詢與實時分析，可用于海量事件流數據的存儲及分析。然而Druid 和BTrDb［7］等時間序列數據庫在時間屬性外的第二維索引能力較差。

索引是一種常用技術，在高頻范圍屬性上創建索引可顯著提升查詢性能。然而以高速率插入元組時，會造成索引維護開銷太大。目前批量加載/插入方法是一次插入一批，并非單獨插入各元組來分攤開銷。當前關于索引技術的研究主要集中于哈希（Hash）函數、LSM 樹和B+樹。例如，文獻［8］提出一種分布式批量插入方法，對跨分區的負載平衡進行優化。然而，這些技術并不適用于數據元組在寫入后要求立即可見的情況。LSM-tree［9］及其變形［10-11］在不進行批處理的情況下可提高插入性能，因此被廣泛應用于HBase、MongoDB、Cassandra［12］和InfluxDB等多種數據庫管理系統。文獻［13］提出cLSM-tree對LSM 樹索引的并發機制進行優化，可在服務器CPU 多核環境下實現高擴展性，其關鍵思想是將B+樹維持在兩層或更多層中，且較高層的節點保存在容量較小的內存中。然而由于上層數據達到一定數量后需與低層數據合并，會造成大量合并的開銷，因此導致LSM 樹的插入性能不高。

對數據庫查詢日志等歷史數據及記錄的利用也是當前的研究熱點。若數據服務系統待處理的查詢請求與歷史查詢日志M 特征相同，則可通過處理M來更新計算數據索引的值；若特征不相同，則可先預測查詢負載情況，再利用查詢負載對當前索引結構進行調優［14-15］。文獻［16］針對日志數據設計與實現高效的并發數據，將其寫入系統流水以提高數據加載性能，并允許應用程序訪問加載中的數據。文獻［17］結合機器學習提出學習索引結構，利用機器學習對數據建模以替代傳統索引。然而查詢日志和建模需要批量處理數據以及對歷史數據的大規模分析，在本文實時數據場景下，采用索引優化結構無法實現實時可見，不能有效進行索引調優。

支持高吞吐量和實時查詢的WaterWheel 模型［18］只能在單一的查詢請求下，對計算機資源實時進行最優化分配。而在分布式流式處理任務中，常出現高并發度的查詢請求，會根據系統當前不同環節的資源使用與任務執行情況，對已處理完畢且處于空閑狀態的任務推送下一個請求，以保證系統不同環節始終處于任務負載狀態。WaterWheel 是通過串行化執行每次查詢請求，返回結果后再處理下一個請求，導致集群內部分節點在完成子查詢請求后到下次查詢請求被分配到該節點之前，一直處于查詢空閑狀態。

從總體來看，現有分布式存儲系統具有支持流數據處理的能力，卻無法提供較好的流數據高速插入與低延時時間范圍查詢性能。針對該問題，本文提出一種流式數據存儲與查詢模型Tars，在數據插入時進行內存索引和文件壓縮存儲，并在查詢時進行查詢分解以及構建多級索引。在系統模型整體搭建方面，本文基于流數據處理框架Storm 構建包含調度層與服務層組件的拓撲結構，調度層負責源數據的劃分轉發與查詢的拆解分配，服務層負責數據的內存索引和子查詢的任務執行。在系統模型數據存儲方面，數據在內存索引中基于template B+樹［19］構建索引結構，并在超過閾值后將其分組壓縮存儲到CephFS 中（Ceph［20］是一種能自動均衡和恢復且可擴展的高性能分布式存儲系統，其提供了文件系統服務CephFS）。在系統模型查詢調度方面，本文基于數據范圍分區劃分模式對查詢進行分解，通過構建多級索引，只讀取符合復雜查詢條件的數據文件，以保證提供高效查詢。

2 流式數據存儲與查詢模型的基本原理

基于位置信息的流數據要實現數據的實時性和完整性，需要盡可能降低實時寫入海量數據時查詢數據服務帶來的性能影響，并提高模型查詢重復數據時的優化能力。本文主要從以下方面優化模型的存儲與查詢能力：

1）提高模型并發讀寫能力。根據數據分區劃分模式，接收不斷流入的數據后，將其轉發到不同機器與組件進行內存索引；查詢數據時，將查詢切分為子查詢，并將請求分發到不同索引組件和文件系統。

2）提高數據索引與存儲能力。寫入數據在內存中被組織為索引模式，并在達到閾值后進行壓縮存儲到分布式文件系統。

3）提高查詢的多級索引能力。基于數據模型索引主鍵（key）和時間范圍的查詢雖然能被高效地執行，但要提高其他屬性的查詢效率，還需進一步構建二級索引。

2.1 數據模型與假設

本文中數據元素以四元組形式存在，其中x、y、t和e分別為經度、緯度、時間戳和有效負載。在數據插入之前，可在x和y上應用Z-order 將輸入數據元組轉換為，其中z為位置鍵（以下簡稱為鍵）。本文假設元組以其時間戳的遞增順序到達，用戶查詢基于一系列鍵和時間戳的建立，使得時間和鍵形成二維空間R。將一段范圍的時間和鍵分別稱為時間間隔和鍵間隔，若給定任意時間間隔和鍵間隔，則在R中可唯一確定一個矩形區域。

2.2 模型結構

本文提出的Tars 模型可在一組分布式服務器集群上運行并通過局域網絡互連，其結構如圖1 所示。其中，消息中間件傳遞的實時流數據是數據來源，其由數據入口處理層（數據調度層）接收，再根據數據分區劃分規則分發到下游索引服務層。索引服務層將實時流數據插入到模板B+樹中作為索引結構，在其超過閾值后進行分組壓縮，并以數據塊形式寫入分布式文件系統CephFS 中。元數據管理服務器通過zookeeper 和R樹［21］維護系統的狀態，其中包括數據調度層對數據的分區模式和數據塊的元數據信息。

圖1 Tars 模型結構Fig.1 Tars model structure

本文模型支持多用戶查詢的并發處理，查詢調度層根據查詢標準和元數據服務層的信息將用戶查詢轉換為獨立子查詢，并在索引服務層和查詢服務層間并行執行，然后將查詢結果返回到各自聚合服務器進行聚合函數處理，再合并返回給對應用戶。下文分別介紹高吞吐量數據插入中使用的數據索引存儲方法（見圖1 中實線指示的路線）和實時查詢處理方法（見圖1 中虛線指示的路線）。

3 流式數據存儲與查詢模型的實現

3.1 數據索引和壓縮存儲原理

常用的內存索引技術包括B+樹、LSM 樹以及bulk loading 等。本文場景中需要插入大量的實時數據元組，而B+樹在節點插入時要進行分裂，在插入海量數據元組時會帶來較大分裂開銷，導致效率降低。LSM 樹需不斷將兩層索引進行合并，存在較大時間開銷，不適用于實時應用場景。bulk loading 技術通過批量插入數據元組可減少節點分裂導致的性能下降，但其更適用于批處理場景，而不適用于實時數據查詢。因此，本文對模板B+樹進行改進，以提升索引的壓縮存儲與持久化能力。

在數據寫入方面，本文數據以時間事件為驅動，并要求數據具有實時可見性，因此采用范圍分區（根據鍵值范圍和時間范圍進行劃分）的方式將不同范圍的數據以模板B+樹形式寫入內存中并構建索引，以增強在內存中快速寫入與查詢能力。當數據在B+樹索引中達到預設值大小（如16 MB）時，考慮其持續增長會影響內存索引效率并增強數據持久化能力，因此需要將數據以數據塊形式壓縮后寫入底層分布式文件系統中。當查詢范圍和數據塊文件的區間范圍有交集時，系統將從文件系統中讀取并解析數據塊，并檢索出符合查詢條件的數據元組。

數據塊的設計布局是一個重要環節，合理的布局能有效減少查詢時解析的數據量。例如，當一個查詢只覆蓋部分數據塊文件時，若采用較合理的數據塊布局，則無需從文件系統中讀取整個數據塊就可訪問到所需要的數據元組。圖2 為數據塊文件的存儲結構，其中包括template索引層和compressed chunk壓縮數據層。索引層存儲模板B+樹的非葉節點部分會按照樹的層級自上到下且自左到右的連續存儲。每個節點均額外記錄了key 數組對應孩子節點的偏移量。當該子節點為非葉節點時，偏移量為指向索引層的一個數組；當該子節點為葉節點時，偏移量指向壓縮數據層并分為兩個數組，即該子節點所在葉節點分組的組內和組間偏移量。

圖2 數據塊文件存儲結構Fig.2 Storage structure of data block file

數據層采用分組并壓縮的布局形式從左到右有序存儲模板B+樹全部葉子節點，根據預設的組容量k，從最左側葉節點開始以k個為一組進行壓縮，生成壓縮數據塊，一直壓縮到最右側葉節點。每個壓縮數據塊互相獨立，并記錄組內葉節點中數據元組的鍵值范圍，從而使壓縮數據塊在滿足查詢條件覆蓋范圍的同時，能根據偏移量進行針對性讀取，以避免讀取整個數據塊。

壓縮數據塊中葉節點布局包括索引部分和數據部分，如圖3 所示。索引部分為一個key 數組，包含與數據元組對應的一個數組偏移量。數據部分為一個數據元組數組，其存儲了流入系統的原始數據元素。在獲取葉節點后，使用二分法在索引部分key數組中找到數據元組對應的偏移量，然后根據偏移量找到數據部分對應的數據元組，即為查詢結果。

圖3 葉節點布局結構Fig.3 Leaf node layout structure

因為數據塊文件所存儲數據（模板B+樹）的鍵值分布會隨插入元組的變化而改變，所以元組并不總是穩定地平均分布在葉節點中。如果模板B+樹在保持整體分布穩定的同時，部分葉節點的溢出元組較其他葉節點仍較多，則會給數據塊文件的壓縮解壓帶來額外開銷。由于不同葉節點分組采用并行壓縮，如果某個分組的葉節點數據過多未被處理完畢，則將導致整個數據塊持久化過程阻塞和時間開銷增多，從而造成計算資源的浪費，因此為使模板B+樹在應對不穩定葉節點分布而進行壓縮存儲時更有魯棒性，本文提出一種模板B+樹在持久化時的分組壓縮方法，用來計算葉節點分組時每組應分配的葉節點個數。

假設系統所在服務器的線程數預設值為m（即系統可并發處理的葉節點壓縮組個數），L（?-，?+）為模板B+樹的葉節點區間，則模板B+樹的葉節點范圍P=｛?1，?2，…，?i｝，N為模板B+樹的全部葉節點，D為模板B+樹的全部數據元組。在L（?-，?+）和U1≤i≤N Li中，對于任意的i≠j，Li與Lj交集為空。因此，每個葉節點分組中分配較理想的葉節點個數為：

當分組中實際存儲的數據元組數量大于或等于樹中的一系列元組之和的比率J=2/|D|時，可認為當前葉節點分組不適用。為適應當前數據元組分布的范圍，需重新規劃葉節點壓縮的分組。

利用葉節點分組個數m和當前模板B+樹的全部數據元組個數D，結合數據元組在模板B+樹中的分布范圍，可重新確定葉節點的分組結構。對于模板B+樹而言，葉節點鍵值從左向右依次遞增，如果用V表示數據元組的鍵值數組，用V［i］表示該數組中的第i個元素，則可直觀地為元組鍵值平均分配K個新劃分范圍Q={V1，V2，…，Vk}，V1的范圍表示為：

根據新元組分組劃分范圍Q和式（1）的葉節點理想分組范圍K，可重新調整當前葉節點分組并構建新的壓縮數據文件。假設系統線程數m=3，當前有一棵具有6 個葉節點的模板B+樹，這棵B+樹存儲[0，20) 范圍內的數據，數據范圍劃分為：V={[0，4)，[4，7)，[7，10)，[10，13)，[13，16)，[16，20)}，且當前模板B+樹的葉節點實際上已插入數據元組集合P={[2]，[4]，[7，8，9]，[10，11，12]，[17]}，樹的大小已達到閾值，需要存儲到底層的分布式文件系統。根據式（1）計算得到葉節點分組結果K=3，則葉節點被分為3 組，在每組中，Q1={2，4}，Q2={7，8，9，10，11，12}，Q3={17}，其中Q2的數據元組占總數據元組的比率J`=2/3，與當前模板B+樹的J相等，因此根據式（2），對數據元組重新劃分范圍得到：Q1={2，4，7}，Q2={8，9，10}，Q3={11，12，17}。對應到葉節點中，即：將數據元組集合P的第3 個葉節點的元組｛7｝拆分到第1 個葉節點分組中，將P的第4 個葉節點的元組｛11，12｝拆分到第3 個葉節點分組中，并在壓縮時記錄其所在分組的數據塊文件字節偏移量與組內偏移量，從而在查詢時進行訪問。

當一個查詢分解為獨立的子查詢后，為查找已存儲到分布式系統中的數據元組是否符合查詢條件，系統需在數據塊索引層中獲取滿足查詢條件的元組偏移量。根據數據元組所在葉節點的組間偏移量，先找到其對應的葉節點分組并解壓，再根據數據元組在葉節點中的組內偏移量找到數據元組。為提高數據訪問的局部性，數據元組的key 在索引層的存儲順序與數據元組在數據層的存儲順序一致。

3.2 二級索引支持

為獲得查詢所覆蓋的數據區域集合，元數據服務器使用R 樹來存儲數據區域。當系統接收到查詢（kq和tq分別為查詢的key 區間和時間區間，fq為謂詞函數）時，查詢服務器會訪問元數據服務器中的R 樹，并獲取一組查詢q所涵蓋的區域Rq。每個數據區域，其中ki和ti分別為數據區域的key 區間和時間區間，生成子查詢qi=并發送給相應的索引服務器或查詢服務器進行處理。

根據數據區域劃分模式，模型中基于key 和時間范圍的查詢能被高效地執行（見2.1 節），即可用key和時間屬性為主索引來組織數據的分布。當查詢條件涉及到key 和時間外的其他屬性時，為避免對結果數據進行遍歷并提供在非主鍵查詢上的高效索引和快速查詢能力，需建立對應屬性的二級索引，并將索引表保存在本地緩存與鍵值對數據庫中，以獲得更好的可擴展性和容錯能力。在實際應用中存在查詢多個非主鍵屬性組合的要求，因此，類似于數據庫中的多字段索引，對于多個非主鍵屬性列的組合查詢情況，本文基于多個非主鍵屬性列建立組合索引。

在軌跡流數據的應用場景中，用戶會根據經度和緯度等基本信息構建一個查詢條件，其中經度和緯度區間ki、時間范圍區間qi等鍵值屬性范圍均可劃分，因此查詢步驟如下：1）對查詢進行分解，構建獨立區間的子查詢qi（其具有相同的謂詞函數f，可為用戶提供非主鍵組合查詢條件）；2）系統對數據進行分層索引，數據在未達到內存閾值前，先存儲于內存的多個模板B+樹中，當超過內存閾值后，再壓縮存儲于持久化文件系統CephFS 內，由于兩者均可在不同服務進程中進行并發處理，因此如何充分利用并發查詢的能力也是本文考慮的問題?？紤]到非主鍵組合索引的建立，在獨立子查詢分配到各服務進程之前，先通過非主鍵組合索引找到本次查詢請求可能覆蓋的內存B+樹和持久化數據文件，再基于這部分數據進行模板B+樹內部的數據索引查詢，以減少不相關數據的查詢開銷。

在本文Tars 模型中，考慮到復雜查詢針對非主屬性的查詢條件，因此采用“是/否”的形式轉換為“0”和“1”的問題?！?”表示有符合條件的數據，子查詢可以進行下一步處理；“0”表示沒有符合條件的數據，子查詢可以被忽略。類似于文獻［22-23］中Bloom 過濾器與網絡流量的結合應用，本文將預設的一個或多個數據元組屬性通過Bloom 過濾器的k個Hash 函數映射到位數組中k個位置上，并將這k個位置的值均設置為1，表示該屬性值可能存在于數據塊文件中。

設ε為Bloom 過濾器的最大誤判率，N為集合元素個數，m為Bloom 過濾器位數組長度，k為Bloom過濾器Hash 函數的最優個數，q為查詢時分解的一系列獨立子查詢，data 為流入系統的數據元組，array 為組合索引對應的位數組，QList 為最終需要執行的子查詢列表，則對本文模型二級索引算法描述如下：

算法1Tars 模型二級索引算法

上述算法的具體步驟如下：

1）采用Compute Hash 操作通過預設最大誤判率ε、期望集合元素個數N計算出位數組長度m和Hash 函數最優個數k。

2）通過In it Hash Array 操作根據參數k和m構建Bloom 過濾器，并將一維數組的值均初始化為0。

3）當流入系統的數據元組插入到模板B+樹時，利用Indexing 操作將其二級索引屬性值映射到對應的Bloom 過濾器中。

4）對于查詢分解的獨立子查詢條件，使用Has Persistence 操作判斷該查詢范圍的數據是否已寫入文件系統中，如果是，則執行步驟5，返回查詢結果為真；否則執行步驟6。

5）當所查詢數據仍緩存于內存中時，無需對數據塊文件進行過濾。

6）當查詢范圍數據所在的內存索引已達到閾值并寫入文件系統中時，如果指定屬性的值存在于對應的Bloom 過濾器中，則利用Array HasQ 方法，將子查詢q放入查詢列表QList 準備進行下一步查詢處理，同時返回查詢結果為真；否則對子查詢進行過濾，并返回查詢結果為假。

4 實驗與結果分析

本文Tars 模型采用流數據處理系統的拓撲結構并基于Apache Storm 分布式流數據處理系統來實現。在該模型中，各服務層分別是拓撲結構中的不同組件，這些組件通過自定義路由規則進行連接。其中，Storm 負責組件的資源分配與數據傳輸通信，CephFS 負責數據塊文件的分布式存儲。

本文實驗使用真實數據集T-drive［24］。實驗在16臺t2.2xlarge 亞馬遜EC2 集群中進行，每臺機器運行2 個數據調度服務、2 個索引服務、1 個查詢調度服務和2 個查詢服務層服務。通過采取集群統一配置，可避免實驗過程中內存、CPU、網絡等機器配置對實驗結果的影響，實驗相關配置信息如表1 所示。

表1 實驗配置信息Table 1 Experiment configuration information

4.1 索引壓縮存儲的性能評估

在塊存儲數據文件（StoreFile）進行數據層壓縮存儲時，將不同條件下各種壓縮方法的索引壓縮性能進行比較，結果如圖4 所示。圖4（a）為不同壓縮方法下模型的數據插入速率變化情況。可以看出，與StoreFile 不壓縮直接寫入到文件系統相比，壓縮后存儲的數據插入速率明顯提高，這是因為數據壓縮后減少從內存到文件系統的磁盤I/O 讀寫時間，且小數據容量的壓縮時間較少，縮短了數據寫入時導致該服務器數據插入工作的停滯時間。

由圖4（b）和圖4（c）可以看出，在不同的key 選擇率和不同查詢時間范圍（距離請求最近5 s、60 s 和300 s）內，查詢時延在進行數據壓縮處理后明顯降低。根據查詢鍵值范圍，在元數據層找到StoreFile壓縮時數據層每個分組偏移量和組內每個葉節點偏移量，就可跳過無效檢索數據，僅讀取指定葉節點數據，從而降低時延。此外，Snappy 壓縮方法在數據插入和查詢時有較好的性能表現，其原因是該壓縮方法適合大量數據傳輸場景，數據壓縮速度是其他壓縮方法的1.5 倍～1.7 倍，而本文模型涉及到數據的內存索引，需壓縮存儲到文件系統并進行實時數據訪問，要求數據傳輸通信效率較高，且Snappy 壓縮方法不會占用大量CPU，當本文模型混合負載復雜流數據進行統計聚合工作時，在資源方面對任務影響較小，保證了查詢時延的穩定性。

圖4（d）為不同壓縮方法壓縮率的對比情況?？梢钥闯觯珿ZIP 作為CPU 密集型方法壓縮率較高，但由于其會影響模型對數據的計算處理，因此在數據存儲和查詢性能上均表現較差。Snappy 壓縮率相對較低，但能滿足本文模型對數據文件快速壓縮解壓以提高數據在拓撲結構中快速流轉的場景要求，其作為StoreFile 的數據分組壓縮存儲方法，具有較好的性能表現。

圖4 不同條件下不同方法的索引壓縮性能Fig.4 Index compression performance of different methods under different conditions

圖5 為不同StoreFile 存儲容量和鍵范圍對本文模型的數據壓縮存儲性能影響的評估結果。由圖5（a）可以看出，當StoreFile 容量小于32 MB 時，模型數據寫入速率隨容量增大而提高，其原因是降低內存索引服務器中StoreFile 達到閾值后落盤到文件系統的頻率，縮短系統磁盤I/O 讀寫時間與數據插入索引停止時間（寫文件時該內存索引服務器的數據插入索引會暫停，直到數據完成在文件系統的寫入）。當StoreFile 容量超過32 MB 后，模型數據寫入速率隨容量增大而降低，這是因為StoreFile 所需壓縮存儲時間成本較高，導致數據插入索引工作停滯狀態過長。圖5（b）為本文模型在不同鍵范圍與StoreFile 容量下查詢時延的變化情況?？梢钥闯?，查詢時延隨著StoreFile 容量增大而升高，其原因是每個StoreFile 均有不同的鍵值范圍和時間域范圍，而根據壓縮存儲形式可以僅讀取StoreFile中指定的一系列葉節點以及葉節點中指定的部分數據，因此，對于給定鍵值范圍的獨立子查詢，其數據讀取范圍與StoreFile 容量成正比例增長。當StoreFile 容量接近8 MB 時，數據查詢時延趨于穩定，這是因為當StoreFile 容量較小時，數據壓縮比較低，壓縮所需時間和壓縮后StoreFile 的大小變化較小，而CephFS 底層為OSD 塊存儲形式，其讀取塊數據存在訪問時延，當StoreFile 容量較小時，該訪問時延會占較大比例，使得查詢時延趨于平穩。由上述分析可知，當StoreFile 容量取值為8 MB 時，在存儲和查詢上具有更優的數據壓縮性能。

圖5 本文模型壓縮存儲性能評估結果Fig.5 Performance evaluation results of compressed storage of the proposed model

4.2 復雜查詢條件下的查詢性能評估

在查詢性能評估引入二級索引方式后，在帶有謂詞函數等復雜條件下，將本文Tars 模型和WaterWheel 模型的查詢性能進行比較，結果如圖6所示。其中，WaterWheel 獲取所有符合鍵值范圍和時間范圍的查詢結果并返回到查詢調度層，然后統一通過謂詞函數條件來串行過濾處理結果，其不支持多用戶查詢的并行調度處理。由圖6 可以看出，本文模型在不同時間范圍下查詢延遲較WaterWheel更小，且隨著key 選擇率的增加，該性能差距更明顯，這是由于WaterWheel 不支持查詢分解時對子查詢的二級索引，需讀取全部符合key 和時間范圍的內存索引與分布式文件數據塊，再統一進行謂詞函數條件過濾，并在查詢調度層對多用戶查詢結果進行串行化處理后返回給用戶，因此查詢時延較高。本文模型使用Bloom 過濾器建立謂詞函數條件值與位圖數組的映射關系，通過對每個獨立子查詢進行二級索引，能提前判斷是否存在滿足該索引的StoreFile，如果不存在，則直接將子查詢進行過濾，減少了無效查詢時間。

圖6 不同時間范圍內2 種模型的二級索引查詢性能對比Fig.6 Performance comparison of two models for secondary index queries in different time ranges

圖7 為查詢分解后通過二級索引確定（經Bloom過濾器過濾）的有效和無效子查詢的百分比（簡稱為二級索引命中百分比）。通過本文模型的二級索引檢測可知，在帶有復雜謂詞函數的查詢中，滿足鍵值范圍和時間范圍的子查詢超過80%為無效子查詢，本文忽略這些無效子查詢。上述結果驗證了模型支持二級索引的重要性。

圖7 本文模型二級索引命中百分比Fig.7 Percentage of hits in the secondary index of the proposed model

在不同時間范圍和key 選擇率下將本文Tars 模型與HBase、WaterWheel 模型在T-drive 數據集上的查詢性能進行對比，結果如圖8 所示。其中，HBase、WaterWheel 模型在底層均使用HDFS（大數據解決方案通用的分布式文件系統，支持海量數據離線批處理）作為分布式文件系統。為保證3 種方法的查詢性能在相同條件下可進行比較，將插入速率統一設置為每秒50 000 個元組（HBase 最大插入速率的一半）。

由圖8 可以看出，Tars 在不同的key 選擇率與時間范圍下查詢延遲均少于HBase 和Waterwheel。隨著key 選擇率不斷提升，HBase 與其他兩種模型的查詢延遲差距逐漸增大，其原因是HBase 不支持在非key 屬性上的范圍索引，其需讀取全部符合key 選擇率的元組并測試其是否符合時間范圍，造成查詢延時較高。本文模型在全局劃分出二維區域R，并將查詢分解為獨立子查詢，經過二級索引處理后，可過濾掉不符合查詢條件謂詞函數f 的StoreFile，從而減少查詢時延。WaterWheel 不支持二級索引，其使用HDFS 作為底層文件系統，在處理實時數據任務時基本時延較高，而Tars 采用增量式存儲形式處理數據，其歷史數據變更較少，無需進行目錄結構維護，因此將CephFS 作為文件系統能加大數據壓縮存儲容量并提升多級索引的效率。

圖8 不同時間范圍和key 選擇率下3 種模型的查詢性能對比Fig.8 Query performance comparison of three models under different time range and key selection rate

5 結束語

本文提出一種面向軌跡流數據的壓縮存儲和多級索引方法，構建數據分區和內存索引并分組壓縮存儲到分布式文件系統以提高模型存儲效率，采用流數據多級索引方法，保證復雜條件函數下查詢分解的穩定性。實驗結果表明，與傳統HBase、WaterWheel 等方法相比，該方法具有更高的數據存儲性能與查詢效率。后續考慮將承載模型數據傳輸和網絡通信的拓撲結構Apachestorm 模型替換為微服務模型，解決網絡數據傳輸速率受帶寬限制的問題。