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

（1.廣東工業(yè)大學(xué)計(jì)算機(jī)學(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)幾何級(jí)增長，對(duì)分布式計(jì)算與數(shù)據(jù)存儲(chǔ)提出更高要求。在企業(yè)大數(shù)據(jù)應(yīng)用需求推動(dòng)下，Hadoop、Storm 和Flink 等分布式計(jì)算框架相繼出現(xiàn)并顯著加快了數(shù)據(jù)處理速度，其中Storm 是一種分布式流式計(jì)算處理框架，可使任務(wù)分布到集群中進(jìn)行。Google 公司的GFS、HDFS 以及基于CEPH 的CephFS 等分布式存儲(chǔ)系統(tǒng)支持文件及對(duì)象的快速讀寫，可存儲(chǔ)大規(guī)模數(shù)據(jù)。key-value 模型［1］與以Redis 為代表的NoSQL 型數(shù)據(jù)庫是目前使用廣泛的存儲(chǔ)模型。

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

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

1 相關(guān)背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 二級(jí)索引支持

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

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

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

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

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

算法1Tars 模型二級(jí)索引算法

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

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

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

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

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

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

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

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

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

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

表1 實(shí)驗(yàn)配置信息Table 1 Experiment configuration information

4.1 索引壓縮存儲(chǔ)的性能評(píng)估

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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