面向軌跡流數(shù)據(jù)的索引構(gòu)建與存儲方法研究

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

（1.廣東工業(yè)大學(xué)計算機學(xué)院，廣州 510006；2.佛山科學(xué)技術(shù)學(xué)院數(shù)學(xué)與大數(shù)據(jù)學(xué)院，廣東佛山 528000；3.依圖網(wǎng)絡(luò)科技有限公司新加坡研發(fā)部，新加坡 018960）

0 概述

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

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

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

1 相關(guān)背景

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

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

對數(shù)據(jù)庫查詢?nèi)罩镜葰v史數(shù)據(jù)及記錄的利用也是當前的研究熱點。若數(shù)據(jù)服務(wù)系統(tǒng)待處理的查詢請求與歷史查詢?nèi)罩綧 特征相同，則可通過處理M來更新計算數(shù)據(jù)索引的值；若特征不相同，則可先預(yù)測查詢負載情況，再利用查詢負載對當前索引結(jié)構(gòu)進行調(diào)優(yōu)［14-15］。文獻［16］針對日志數(shù)據(jù)設(shè)計與實現(xiàn)高效的并發(fā)數(shù)據(jù)，將其寫入系統(tǒng)流水以提高數(shù)據(jù)加載性能，并允許應(yīng)用程序訪問加載中的數(shù)據(jù)。文獻［17］結(jié)合機器學(xué)習(xí)提出學(xué)習(xí)索引結(jié)構(gòu)，利用機器學(xué)習(xí)對數(shù)據(jù)建模以替代傳統(tǒng)索引。然而查詢?nèi)罩竞徒Ｐ枰刻幚頂?shù)據(jù)以及對歷史數(shù)據(jù)的大規(guī)模分析，在本文實時數(shù)據(jù)場景下，采用索引優(yōu)化結(jié)構(gòu)無法實現(xiàn)實時可見，不能有效進行索引調(diào)優(yōu)。

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

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

2 流式數(shù)據(jù)存儲與查詢模型的基本原理

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

1）提高模型并發(fā)讀寫能力。根據(jù)數(shù)據(jù)分區(qū)劃分模式，接收不斷流入的數(shù)據(jù)后，將其轉(zhuǎn)發(fā)到不同機器與組件進行內(nèi)存索引；查詢數(shù)據(jù)時，將查詢切分為子查詢，并將請求分發(fā)到不同索引組件和文件系統(tǒng)。

2）提高數(shù)據(jù)索引與存儲能力。寫入數(shù)據(jù)在內(nèi)存中被組織為索引模式，并在達到閾值后進行壓縮存儲到分布式文件系統(tǒng)。

3）提高查詢的多級索引能力?；跀?shù)據(jù)模型索引主鍵（key）和時間范圍的查詢雖然能被高效地執(zhí)行，但要提高其他屬性的查詢效率，還需進一步構(gòu)建二級索引。

2.1 數(shù)據(jù)模型與假設(shè)

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

2.2 模型結(jié)構(gòu)

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

圖1 Tars 模型結(jié)構(gòu)Fig.1 Tars model structure

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

3 流式數(shù)據(jù)存儲與查詢模型的實現(xiàn)

3.1 數(shù)據(jù)索引和壓縮存儲原理

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

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

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

圖2 數(shù)據(jù)塊文件存儲結(jié)構(gòu)Fig.2 Storage structure of data block file

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

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

圖3 葉節(jié)點布局結(jié)構(gòu)Fig.3 Leaf node layout structure

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

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

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

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

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

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

3.2 二級索引支持

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

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

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

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

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

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

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

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

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

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

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

5）當所查詢數(shù)據(jù)仍緩存于內(nèi)存中時，無需對數(shù)據(jù)塊文件進行過濾。

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

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

本文Tars 模型采用流數(shù)據(jù)處理系統(tǒng)的拓撲結(jié)構(gòu)并基于Apache Storm 分布式流數(shù)據(jù)處理系統(tǒng)來實現(xiàn)。在該模型中，各服務(wù)層分別是拓撲結(jié)構(gòu)中的不同組件，這些組件通過自定義路由規(guī)則進行連接。其中，Storm 負責(zé)組件的資源分配與數(shù)據(jù)傳輸通信，CephFS 負責(zé)數(shù)據(jù)塊文件的分布式存儲。

本文實驗使用真實數(shù)據(jù)集T-drive［24］。實驗在16臺t2.2xlarge 亞馬遜EC2 集群中進行，每臺機器運行2 個數(shù)據(jù)調(diào)度服務(wù)、2 個索引服務(wù)、1 個查詢調(diào)度服務(wù)和2 個查詢服務(wù)層服務(wù)。通過采取集群統(tǒng)一配置，可避免實驗過程中內(nèi)存、CPU、網(wǎng)絡(luò)等機器配置對實驗結(jié)果的影響，實驗相關(guān)配置信息如表1 所示。

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

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

在塊存儲數(shù)據(jù)文件（StoreFile）進行數(shù)據(jù)層壓縮存儲時，將不同條件下各種壓縮方法的索引壓縮性能進行比較，結(jié)果如圖4 所示。圖4（a）為不同壓縮方法下模型的數(shù)據(jù)插入速率變化情況?？梢钥闯?，與StoreFile 不壓縮直接寫入到文件系統(tǒng)相比，壓縮后存儲的數(shù)據(jù)插入速率明顯提高，這是因為數(shù)據(jù)壓縮后減少從內(nèi)存到文件系統(tǒng)的磁盤I/O 讀寫時間，且小數(shù)據(jù)容量的壓縮時間較少，縮短了數(shù)據(jù)寫入時導(dǎo)致該服務(wù)器數(shù)據(jù)插入工作的停滯時間。

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

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

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

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

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

4.2 復(fù)雜查詢條件下的查詢性能評估

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

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

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

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

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

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

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

5 結(jié)束語

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