鄭曉東 王 梅 陳德華 張碧瑩

(東華大學計算機科學與技術(shù)學院 上海 201620)

0 引 言

大數(shù)據(jù)時代已然來臨。時間作為客觀事物的固有屬性，幾乎所有信息都顯式或隱式地具備時態(tài)特征。大數(shù)據(jù)的產(chǎn)生往往也是經(jīng)過時間累積形成，因此大數(shù)據(jù)也被理解為針對某個對象在時空兩個維度上的“全息”數(shù)據(jù)。若對數(shù)據(jù)進行時態(tài)的關(guān)聯(lián)分析，有望挖掘出數(shù)據(jù)的巨大價值，從而使得研究和使用數(shù)據(jù)的“時態(tài)”信息意義日顯突出，對時態(tài)數(shù)據(jù)管理查詢技術(shù)的研究十分迫切。

在考慮數(shù)據(jù)的時態(tài)信息時，被打上時間標簽的數(shù)據(jù)，會伴隨著時間的延伸而生效或失效。因此，對于一個實體來說，它會擁有多個數(shù)據(jù)記錄，很明顯傳統(tǒng)默認時間點的靜態(tài)“快照”式數(shù)據(jù)存儲模式難以滿足時態(tài)查詢需求。一些時態(tài)數(shù)據(jù)庫模型被相繼提出，如TimeDB[1]等。與此同時，Oracle、IBM DB2[2]、SAP HANA[3]等知名的商業(yè)數(shù)據(jù)庫也開始支持一些簡單的時態(tài)查詢功能，包括時間旅行，時態(tài)聚合以及時態(tài)連接等。以時態(tài)連接為例，檢索“在相同時間點中，兩個銀行賬戶數(shù)據(jù)表中存款相同的客戶存款額度”，需要在時間以及對象兩個維度上進行雙向篩選，如何在龐大的數(shù)據(jù)集進行快速、高效的時態(tài)操作執(zhí)行成為一個十分有挑戰(zhàn)性的問題。

索引是數(shù)據(jù)庫中加速查詢的有效技術(shù)。為此，研究者從不同角度為時態(tài)數(shù)據(jù)模型提出了多種時態(tài)索引技術(shù)。文獻[4]提出的基于B+樹Time Index索引以及文獻[5]中提出的Historical R樹索引對傳統(tǒng)樹型索引進行擴展已支持時態(tài)數(shù)據(jù)，文獻[6]針對時態(tài)XML數(shù)據(jù)，構(gòu)建不同的時態(tài)索引模型以支持時態(tài)查詢。近來，SAP HANA提出的Timeline索引[7]以及雙時態(tài)索引技術(shù)[8]采用順序結(jié)構(gòu)實現(xiàn)高效的時態(tài)查詢。然而，目前所設計的大部分索引均在單機環(huán)境下實現(xiàn)，當數(shù)據(jù)集規(guī)模較大時，上述方法將花費較高的代價在遍歷龐大的索引樹或索引隊列上。同時，其索引結(jié)構(gòu)和查詢算法的執(zhí)行效率對機器性能的要求極高，以支持SAP HANA的Timeline時態(tài)索引為例，其執(zhí)行默認的機器內(nèi)存達192 GB[7]。上述問題極大地限制了索引技術(shù)的普遍應用和查詢效率的提升。

在數(shù)據(jù)規(guī)模不斷增長的今天，越來越多的應用都是基于存儲在分布式系統(tǒng)中的大規(guī)模數(shù)據(jù)。Spark分布式處理框架通過將海量數(shù)據(jù)分發(fā)至各個計算節(jié)點，并基于彈性數(shù)據(jù)集RDD及MapReduce技術(shù)極大地加快了數(shù)據(jù)的處理速度[9]。然而該框架中并沒有對hdfs中文件的行級記錄進行索引，本文基于Spark分布式計算平臺設計并實現(xiàn)了一種分布式時態(tài)索引方法。該方法首先提出時態(tài)數(shù)據(jù)集的分段索引構(gòu)造策略，進一步設計基于Spark的時態(tài)索引構(gòu)建方法及基于Spark RDD的并行查詢策略。本文主要內(nèi)容如下：

1) 以Timeline索引為例，提出時態(tài)索引在Spark集群上的構(gòu)建方法，設計分布式時態(tài)索引的并行查詢框架。根據(jù)時態(tài)查詢所涉及的Spark RDD分區(qū)模式的不同，將其分為分區(qū)獨立查詢，跨區(qū)查詢以及跨段查詢，并對不同模式的時態(tài)查詢提出了優(yōu)化的分布式查詢算法，提高查詢效率。

2) 優(yōu)化輔助索引結(jié)構(gòu)，加快“給定時間點查詢”這一原子操作的效率，從而極大地提升時態(tài)聚合，時態(tài)旅行等分區(qū)獨立查詢的查詢效率。進一步針對跨RDD分區(qū)及跨段的時態(tài)連接復雜查詢，分別設計復合索引結(jié)構(gòu)輔助查詢，確保本文方法對數(shù)據(jù)規(guī)模的有效自擴展性同時降低集群硬件配置需求。

3) 在基準數(shù)據(jù)上，進行本文所提方法的有效性驗證，證明了本文提出的索引策略的實用性和高效性。

1 相關(guān)工作

1.1 時態(tài)索引

傳統(tǒng)數(shù)據(jù)庫中索引技術(shù)是提高查詢效率的關(guān)鍵技術(shù)之一，同樣對于時態(tài)數(shù)據(jù)，合適的索引結(jié)構(gòu)將有效地支持時態(tài)操作。時態(tài)數(shù)據(jù)索引大致可歸為兩類：樹索引和隊列索引。最早提出的時態(tài)數(shù)據(jù)索引結(jié)構(gòu)Time Index就是基于B+樹構(gòu)建的，該索引針對每個時間間隔的結(jié)束時刻作為索引值建立B+樹，每個葉子結(jié)點記錄該時間點各事件的生效失效狀態(tài)[4]。但是該索引在時間跨度較大的情況下會引起較大的空間開銷，同時這種基于B樹的時態(tài)索引在構(gòu)建時依賴于數(shù)據(jù)的時間有序性。另一種樹形結(jié)構(gòu)R樹雖然最初的設計思想是為了索引空間數(shù)據(jù)，但是它被用來存儲時間同樣適合。文獻[5]提出了Historical R樹，每個時間戳都建立一個R樹，且一個Historical R樹中未發(fā)生變化的記錄對應的結(jié)點只保存一個以節(jié)省空間。同時，除了這種以單一一個數(shù)據(jù)結(jié)構(gòu)來索引全部數(shù)據(jù)外，還有以樹形結(jié)構(gòu)為基礎，為每一個時間版本構(gòu)建一個樹來索引時態(tài)數(shù)據(jù)的方法，如MVBT索引[10]和MV3D-RT索引[11]。相對于樹形時態(tài)索引，基于隊列的時態(tài)索引研究較少，文獻[7]提出了Timeline時間線索引，該索引應用于HANA，在內(nèi)存中為時態(tài)數(shù)據(jù)建立一張時態(tài)表，每一個時態(tài)表對應一個Timeline時間線索引，在時間線上保存著各個數(shù)據(jù)的生效失效時間，該索引支持多種時態(tài)操作。

目前對于時態(tài)數(shù)據(jù)的操作主要分為時間旅行，時態(tài)聚合和時態(tài)連接。時間旅行是查詢數(shù)據(jù)在過去或未來某個時間點或時間段所具有的狀態(tài)，可以通過時間旅行回溯到某個時間版本的數(shù)據(jù)庫狀態(tài)。時態(tài)聚合和時態(tài)連接都是基于時間旅行所進行的操作，時態(tài)聚合是指對某個時間點或時間區(qū)間的有效記錄進行聚合操作。時態(tài)連接是指對指定時間點下的有效記錄進行連接操作。如今對于時態(tài)索引的研究還處于一個發(fā)展階段，現(xiàn)階段已提出的時態(tài)索引大多數(shù)僅僅支持有限的時態(tài)操作，部分更是僅支持時間旅行，無法有效地支持時態(tài)聚合和時態(tài)連接等復雜查詢操作。

1.2 分布式索引

分布式計算框架如Spark、Hadoop，采用的是分布式的文件系統(tǒng)，通過將大文件進行分片，切分成多個分片文件存儲在多個存儲節(jié)點上。平臺在需要對該文件數(shù)據(jù)進行計算時，各個分片文件加載至多個計算節(jié)點上進行獨立計算，計算子結(jié)果將返回主節(jié)點進行后續(xù)操作。這種存儲計算模式雖然解決了大數(shù)據(jù)計算處理的效率問題，但是在對數(shù)據(jù)文件進行行級訪問時，盡管數(shù)據(jù)文件的切分且分布式的讀取加快了讀取速度，其大量的時間浪費在了文件的尋道遍歷上。Haojun Liao提出了應用在Hadoop的分布式文件系統(tǒng)上的多維索引，考慮到HDFS中塊大小、索引節(jié)點大小、網(wǎng)絡中的數(shù)據(jù)通信等影響查詢速度的因素，通過構(gòu)建類似于R樹的層次結(jié)構(gòu)索引，避免查詢時無意義的窮舉減少查詢響應時間[12]。Gankidi等[13]提出通過構(gòu)建B+樹管理HDFS數(shù)據(jù)，索引維持在SqlSever中，用戶可以通過SQL查詢HDFS數(shù)據(jù)。Xie等[14]提出建立在Spark平臺上用于管理空間數(shù)據(jù)的兩級索引結(jié)構(gòu)，該索引維持在RDD中，區(qū)域索引保存空間區(qū)域中的數(shù)據(jù)信息，而全局索引管理著每個區(qū)域索引的邊界信息。

總的來說，現(xiàn)有的時態(tài)索引技術(shù)尚處于研究階段，大多數(shù)索引結(jié)構(gòu)無法有效地支持時態(tài)操作，并且在面對大規(guī)模時態(tài)數(shù)據(jù)時，索引空間代價較大，效率變低，而傳統(tǒng)的分布式索引大多是面向隱性時間屬性數(shù)據(jù)，無法有效地支持對歷史信息的相關(guān)操作。

2 基于Spark的時態(tài)索引

2.1 定義和符號

定義1時態(tài)表(Temporal Table)。包含具有時態(tài)屬性的數(shù)據(jù)的表。

定義2時間區(qū)間(Period)。表示一個數(shù)據(jù)合法持續(xù)的時間，包括它的開始和結(jié)束。本文使用包含-排除方法來建模時間區(qū)間，使用[start, end)來表示。在實現(xiàn)過程中分別通過時態(tài)表的兩列來分別表示記錄的開始時間和結(jié)束時間。

定義3時間版本(versionID)。指時間區(qū)間內(nèi)離散的時間點，這些時間點是單調(diào)遞增的，本文將這些時間點稱之為versionID。

表1給出了一個時態(tài)表的例子。該實例模擬了一個銀行系統(tǒng)，Alice在101時間點在銀行存入＄100，Alice在銀行的存款為＄100這個狀態(tài)在數(shù)據(jù)庫中維持到了103時間點，即103時間點后(包含103時間點)第一條記錄失效，第四條記錄生效，表明Alice在103時間點在銀行存入＄500使銀行的存款到達＄600。同理，Ann在102時間點在銀行存入＄500，第二條記錄在102時間點到107時間點有效，第三條記錄表示Grace在103時間點在銀行存入＄300，直到目前為止，Grace在銀行的存款都為＄300。

表1 時態(tài)表

2.2 索引結(jié)構(gòu)

不論是基于樹結(jié)構(gòu)或是順序結(jié)構(gòu)的時態(tài)索引，均需在其索引結(jié)點中記錄各時間點下事件的生效失效狀態(tài)。以圖1(a)給出的Timeline索引結(jié)構(gòu)為例，其中“+”表示該數(shù)據(jù)在對應時間版本下開始生效，“-”表示數(shù)據(jù)失效。上述索引可以有效地支持多種時態(tài)操作，然而其也存在著明顯的缺陷。在執(zhí)行時態(tài)操作時，由于索引只保存了各個記錄的生效失效狀態(tài)，如果要獲取到某一時間版本下的有效數(shù)據(jù)，如查詢“106時間版本下的有效數(shù)據(jù)”，系統(tǒng)無法避免地需要從頭遍歷事務層至查詢時間版本，以得到“106時間版本下第二條記錄及第五條記錄有效”的信息。每一次的時態(tài)操作都會重復性的遍歷索引，這種低效的重復性工作造成了極大的時間代價。

圖1 checkpoint結(jié)構(gòu)

因此，在Timeline時態(tài)索引中，同時維護檢查點(checkpoint)輔助索引結(jié)構(gòu)。checkpoint中保存了當前時間下所有記錄的有效狀態(tài)，這種類似于快照的設計結(jié)構(gòu)省去了在每次時態(tài)操作時需要從頭遍歷時間線索引所引起的大量開銷，可以較為快速地獲取指定時間版本下的有效記錄，對于優(yōu)化索引的檢索效率至關(guān)重要。由于checkpoint的創(chuàng)建代價較大，一般在一個較大的時間間隔下創(chuàng)建一個新的checkpoint結(jié)構(gòu)。

2.3 基于Spark的分段時態(tài)索引框架

Spark上的所有數(shù)據(jù)操作都依賴于彈性分布式數(shù)據(jù)集(RDD)，RDD被分布式的存儲在集群的各個節(jié)點上，程序方能分布式的執(zhí)行。給定當前時態(tài)表T，由于時態(tài)表中數(shù)據(jù)是以時間特性排序的，為了保證各分區(qū)中數(shù)據(jù)的時態(tài)均衡性，應用Spark自帶Hash Partition方法針對ROW_ID列進行哈希劃分，從而得到RDD的各個分區(qū)。各RDD迭代本分區(qū)數(shù)據(jù)并行創(chuàng)建索引，因此RDD類型為一個二元組(TT，TI)，其中TT即Temporal Table是本數(shù)據(jù)分區(qū)中的時態(tài)表，TI即Temporal Index是針對于本分區(qū)時態(tài)數(shù)據(jù)構(gòu)建的時態(tài)索引。很明顯，隨著時間推移，時態(tài)表T中的數(shù)據(jù)不斷累積。為保證本文方法對數(shù)據(jù)規(guī)模的有效自擴展性。同時，為了避免當數(shù)據(jù)增大，RDD在進行迭代計算時產(chǎn)生的內(nèi)存溢出問題，首先將數(shù)據(jù)進行切分。給定當前時態(tài)表T={t1,t2,tn}，n為數(shù)據(jù)記錄條數(shù)，將其切分為T={T1,T2,Tm}，m為數(shù)據(jù)段個數(shù)。對每個數(shù)據(jù)段Ti按如上所述方法構(gòu)建索引，通過設定m的大小以控制各段RDD的大小。同時，在Spark集群中維持全局索引來調(diào)度對應查詢時段所涉及的各數(shù)據(jù)段索引RDD進行相關(guān)查詢操作。

3 基于索引的時態(tài)查詢執(zhí)行

時態(tài)數(shù)據(jù)的查詢操作可分為時間旅行、時態(tài)聚合、時態(tài)連接三種時態(tài)操作。根據(jù)操作所涉及的Spark RDD數(shù)據(jù)對象，本文將查詢分為分區(qū)獨立，跨區(qū)查詢，跨段查詢，如圖2所示。并且對于每類查詢，本文均針對性地提出優(yōu)化的輔助索引結(jié)構(gòu)及查詢算法，以充分發(fā)揮分布式的優(yōu)點，提高時態(tài)檢索效率。

圖2 構(gòu)建在Spark集群上的時態(tài)查詢分類

3.1 分區(qū)獨立查詢

本文將時態(tài)索引構(gòu)建在Spark集群中的RDD上，當集群讀取至RDD上后，各個分區(qū)根據(jù)分區(qū)數(shù)據(jù)構(gòu)建本分區(qū)索引。分區(qū)獨立查詢即指各個分區(qū)數(shù)據(jù)之間不必進行通信，各個分區(qū)在檢索完本分區(qū)索引后直接返回結(jié)果集。

在幾種時態(tài)操作中，時間旅行屬于典型的分區(qū)獨立型查詢。時間旅行是查詢某一時間版本versionID下數(shù)據(jù)庫記錄的狀態(tài)信息，也就是得到該時間版本數(shù)據(jù)庫的有效數(shù)據(jù)集。以時間旅行為例，詳細描述分區(qū)獨立查詢在Spark集群的執(zhí)行流程：在獲取到待查versionID后，IndexRDD各分區(qū)索引先檢索本分區(qū)的checkpoint集合，獲取到最鄰近且早于查詢時間版本的checkpoint，根據(jù)checkpoint中的標志位查詢對應行向量分段數(shù)據(jù)，獲取到該時間版本下的有效數(shù)據(jù)。若checkpoint的時間版本和查詢時間相同，該分區(qū)即可返回結(jié)果集；若與查詢時間不等，則根據(jù)checkpoint的時間版本在時態(tài)索引中的位置信息接著向下遍歷時態(tài)索引，直到遍歷至查詢時間在時態(tài)索引中的位置，整合計算得到該分區(qū)的有效數(shù)據(jù)集后返回給驅(qū)動節(jié)點。

傳統(tǒng)的checkpoint結(jié)構(gòu)需要遍歷行向量來查看對應時間版本的數(shù)據(jù)庫狀態(tài)，由于checkpoint中會存儲和時態(tài)表同等大小的行向量，若設時態(tài)表大小為n，其遍歷次數(shù)為n。然而由于數(shù)據(jù)的時效性，在給定時間版本下同一對象的時態(tài)數(shù)據(jù)只有一條是生效的，且有效數(shù)據(jù)具有區(qū)域性(即一個時間版本下的有效數(shù)據(jù)大多會集中在行向量的一個分段內(nèi))，造成大量的無效遍歷。為此，本文首先利用Spark 分布式和并行處理特點，對checkpoint結(jié)構(gòu)進行優(yōu)化，即對checkpoint中行向量進行固定長度的分段，并添加記錄各分區(qū)有無有效記錄的標記flag結(jié)構(gòu)。如圖3所示，checkpoint分為標志位和有效數(shù)據(jù)位兩部分，在有效數(shù)據(jù)部分按行號分段，并在標志位增設標志，記錄該分段在指定時間版本下是否存在有效的行號。在具體查找時，即可根據(jù)標志位大量過濾無效記錄。

圖3 優(yōu)化checkpoint

優(yōu)化checkpoint中的分段標志位簡化了遍歷復雜度，分段標志位為真再去遍歷對應分段數(shù)據(jù)的有效性，若為假則直接跳過該分段。假定分段步長為l，則時間復雜度近乎簡化為(n/l+l)，且各個分段可并行遍歷，極大地降低獲取checkpoint下有效數(shù)據(jù)的時間開銷。同時，由于數(shù)據(jù)記錄隨時間的累計特性，在下一個時刻點對checkpoint創(chuàng)建時，僅需追加新增段，原有分段可重用，大大降低了checkpoint的創(chuàng)建復雜度。

3.2 跨區(qū)查詢

跨區(qū)查詢涉及到存儲索引信息的RDD各分區(qū)數(shù)據(jù)間的通信，各分區(qū)間需要進行聯(lián)合計算。時態(tài)連接就是最為典型的跨區(qū)查詢，時態(tài)連接在時態(tài)操作中是一種較為復雜的操作，同時涉及到時間維度和對象維度的連接操作，如查詢“在相同時間點中，兩個銀行賬戶數(shù)據(jù)表中存款相同的客戶存款額度”。上述時態(tài)連接可以劃分成兩個階段，第一個階段利用時態(tài)索引以及checkpoint得到每個時間版本下兩個數(shù)據(jù)集各分區(qū)的有效記錄集合；第二個階段是在相同查詢點的有效記錄集合中，根據(jù)查詢條件以一定的連接規(guī)則對兩個數(shù)據(jù)集的有效記錄進行連接以得到查詢結(jié)果。通過改進checkpoint結(jié)構(gòu)雖然加快了第一階段獲取當前時間版本下有效記錄的速度，但第二階段低效的兩兩條件匹配付出了O(n2)的時間開銷，盡管將索引應用在Spark集群，采用分布式的計算方法加快了匹配速度，但是存在集群中節(jié)點相互通信、數(shù)據(jù)拉取等問題，Spark集群上的時態(tài)連接速度并不理想。

針對于時態(tài)連接過程中出現(xiàn)的低效的兩兩匹配以及大量p的數(shù)據(jù)通信問題，本文采用面向?qū)ο缶S度的輔助索引來優(yōu)化時態(tài)連接效率。如圖4所示，在通過第一階段獲取到有效記錄后，在時態(tài)連接的第二階段，各個數(shù)據(jù)節(jié)點不再進行數(shù)據(jù)廣播，而是采用將全部有效數(shù)據(jù)進行混洗重分區(qū)，以各個記錄的對象維度字段為key值進行hash混洗重分區(qū)，因此新的數(shù)據(jù)分區(qū)具有封閉性。即將連接的記錄限制在本地分區(qū)，不用再進行數(shù)據(jù)通信來進行連接，這樣的輔助索引結(jié)構(gòu)不僅減少了數(shù)據(jù)通信引起的極大開銷，而且縮減連接次數(shù)，提高了時態(tài)連接效率。具體的連接算法如算法1所示。

圖4 優(yōu)化后的時態(tài)連接查詢過程

算法1時態(tài)連接

輸入：versionIDRange時間版本范圍，joinCondition連接條件；

輸出：Result查詢結(jié)果集；

1．for versionID_i in versionIDRange

2．RA,RA←temporalTravel(versionID_i);

/*時間旅行獲取數(shù)據(jù)表的有效記錄*/

3．Repartition(RA) and Repartition(RB);

/*以對象維度對RA和RB重分區(qū)*/

4．for partitionA in RA

5．for partition in RB

6．if partitionA.partitionNum==partition.partitionNum

7．Result←Join(partitionA,partitonB)；

/*擁有分區(qū)號相同的RDD進行連接*/

8．end if

9．end for

10．end for

11．end for

3.3 跨段查詢

Spark集群的一切操作都是基于RDD的。在根據(jù)數(shù)據(jù)集構(gòu)建索引時，RDD需要將所有數(shù)據(jù)都讀進內(nèi)存進行迭代計算，由于集群節(jié)點可以申請到的內(nèi)存是有限的，當分區(qū)數(shù)據(jù)的計算量到達節(jié)點上限時就會內(nèi)存溢出導致計算失敗，為了避免這種情況，我們采用跨段的查詢方式。

跨段查詢就是對大數(shù)據(jù)進行分段處理，各個分段獨立構(gòu)建索引，將分段數(shù)據(jù)集及索引打包存儲至HDFS。考慮到時態(tài)數(shù)據(jù)具有時效性，每一個數(shù)據(jù)集同樣有一個時效性，數(shù)據(jù)集中記錄最早的有效時間以及最晚的失效時間即為該數(shù)據(jù)集的時間跨度。將時間跨度的相關(guān)信息設計到索引結(jié)構(gòu)中將有效地加快查詢速度，避免遍歷過多的時間相錯的數(shù)據(jù)集。因此，本文設計雙hash結(jié)構(gòu)來索引HDFS中的相關(guān)的索引文件，當執(zhí)行時態(tài)操作時，由全局索引調(diào)配符合時間跨度的數(shù)據(jù)集及索引至Spark集群進行后續(xù)操作。

如圖5所示，全局索引包括索引表和索引矩陣兩部分，索引表保存各個索引結(jié)構(gòu)的存儲號、時間跨度，以及HDFS中的存儲地址。索引矩陣將各個索引結(jié)構(gòu)的存儲號保存到對應時間跨度的塊中，索引矩陣的橫縱坐標為索引文件跨度的對應的hash值，橫坐標為開始時間，縱坐標為失效時間。

圖5 全局索引

當進行時態(tài)操作時，先訪問全局索引的索引矩陣，根據(jù)時態(tài)操作的時間字段查詢矩陣的對應區(qū)域，獲取到與操作時間有交錯的索引的存儲號。再根據(jù)存儲號在索引表中查詢到其數(shù)據(jù)及索引在HDFS中的儲存地址，Spark集群逐一加載涉及到的數(shù)據(jù)集和索引至內(nèi)存中執(zhí)行時態(tài)操作，最后將結(jié)果集進行合并即為查詢結(jié)果。如“查詢時間為2 005至3 078各個時間點的數(shù)據(jù)庫信息”，索引矩陣以1 000個時間版本為步長，邊長6為例，則計算其開始結(jié)束的hash值為2和3，根據(jù)hash值訪問索引矩陣的對應區(qū)域(即藍色陰影標注區(qū)域)得到有時間交錯索引的存儲號，即可檢索對應索引表找到其HDFS地址。

跨段查詢算法如算法2所示，其中g(shù)etHashCode(versionID)為計算時間的哈希值；serachIndexMartix(hashCode,indexMartix)為掃描索引矩陣，獲取對應位置的索引塊號。judgeTimeRegion(item,querytime,indexTable)為檢索索引表，獲取時間區(qū)域有重疊的索引塊號。之后調(diào)用readIndexFromHDFS(path)從HDFS中讀取時態(tài)索引，進而進行時間旅行temporalTravel(temporalIndex,versionID)得到查詢結(jié)果。

算法2跨段查詢

輸入：versionID時間版本，indexMartix索引矩陣，indexTable索引表；

輸出：Result查詢結(jié)果集；

1．hashCode←getHashCode(versionID);

2．I←searchIndexMartix(hashCode);

3．For otem in I

4．P←judgeTimeRegion(item,versionID,indexTable);

5．End for

6．For path in P

7．temporalIndex←readIndexFromHDFS(path);

8．Result←temporalTravel(temporalIndex,versionID);

9．End for

3.4 索引更新

時態(tài)數(shù)據(jù)是帶有時間屬性的，這種特性也預示著時態(tài)數(shù)據(jù)會隨著時間不斷地增加，集群需要在新數(shù)據(jù)上添加索引以加快訪問速度，并且集群無法將不斷增大的數(shù)據(jù)及索引都維護在Spark集群中，需要一個索引的更新管理策略來控制Spark讀取對應時間點或時間段所涉及的索引結(jié)構(gòu)。時態(tài)數(shù)據(jù)的時效性特點導致了時態(tài)記錄存在時間跨度且這種時間跨度是無法預料的，集群無法預知同一個對象所產(chǎn)生的下條記錄的時間跨度長短。如果將新產(chǎn)生的時態(tài)記錄索引到原有的索引結(jié)構(gòu)中，需要在索引結(jié)構(gòu)中進行頻繁的隊列移動，將新的索引節(jié)點插入到對應位置，并且這種插入式的方法無法批量操作，索引只允許逐一的進行插入，這種低效的更新策略是無法滿足當今的查詢需要的。

由于將新的時態(tài)數(shù)據(jù)索引到原有索引結(jié)構(gòu)上這種索引更新策略所引起的時間開銷要大于直接重構(gòu)索引，本文擬采用滯后更新的索引更新策略。原有索引不去索引新的數(shù)據(jù)，而是當新的數(shù)據(jù)積累到一定量時，對新數(shù)據(jù)單獨構(gòu)建索引結(jié)構(gòu)。

4 實驗與結(jié)果

為了證明在Spark集群上構(gòu)建時態(tài)索引的高效性，本節(jié)進行了以下幾個方面的實驗：(1) 在Spark集群環(huán)境下利用優(yōu)化的checkpoint和原始checkpoint性能對比；(2) 在Spark環(huán)境下時態(tài)連接的性能效率；(3) 在Spark環(huán)境下分段索引性能分析。

4.1 實驗環(huán)境

本次實驗中Spark部分試驗是在是由5臺機器構(gòu)成的Spark on standalone集群系統(tǒng)上完成的，1個master節(jié)點和4個slave節(jié)點，各節(jié)點CPU為Intel(R) Core(TM) i7-3770 CPU @ 3.40 GHz，6 GB內(nèi)存空間，采用CentOS 6.8系統(tǒng)，Scala版本為2.11.8，Spark版本為2.0.0。

4.2 實驗數(shù)據(jù)集

本實驗在TPC-H基準數(shù)據(jù)集的基礎上擴展時態(tài)屬性，并通過TPC-C事務生成基準數(shù)據(jù)集的歷史數(shù)據(jù)[15]。本實驗采用數(shù)據(jù)集如表2所示。

表2 實驗數(shù)據(jù)集

其中，SF_0為TPC-H生成數(shù)據(jù)的比例因子；SF_H為TPC-C生成數(shù)據(jù)的比例因子，即數(shù)據(jù)集中時間版本的規(guī)模；lineitem表示數(shù)據(jù)集的總行數(shù)，version表示時間版本規(guī)模。

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

4.3.1 checkpoint優(yōu)化前后性能對比

為了規(guī)避時態(tài)操作時分段查詢干擾checkpoint性能判斷的問題，本實驗在小型數(shù)據(jù)集基礎上對比checkpoint優(yōu)化前后的性能變化，確保數(shù)據(jù)在一個數(shù)據(jù)段中。實驗中查詢給定versionID的數(shù)據(jù)庫有效記錄。實驗結(jié)果如圖6所示，圖中橫坐標為查詢的versionID。

圖6 checkpoint優(yōu)化性能對比

圖中查詢時間隨著查詢時間版本的增長出現(xiàn)折現(xiàn)波動，這是因為checkpoint保存了對應時間版本下的數(shù)據(jù)庫狀態(tài)，無需遍歷索引，而兩個checkpoint中的時間版本數(shù)據(jù)庫狀態(tài)需要遍歷時間線索引的對應區(qū)間，所以在checkpoint時間點上查詢時間突然下降，查詢兩個checkpoint間的時間版本數(shù)據(jù)庫狀態(tài)查詢時間是線性增長的。實驗結(jié)果表明，優(yōu)化后的checkpoint相對于原始checkpoint結(jié)構(gòu)在時態(tài)旅行上提升40%左右。由于優(yōu)化后的checkpoint將visible rows分段，并添加對應的標識位，減去了不必要的遍歷的時間，這對于查詢性能的提升是顯著的。并且當數(shù)據(jù)集變大時，checkpoint中需要保存的記錄號變多了，則利用checkpoint進行時態(tài)操作時的遍歷量變大，而優(yōu)化的checkpoint規(guī)避了這種遍歷所引起的時間開銷，也就是說數(shù)據(jù)量越大時，優(yōu)化的checkpoint對于性能的提升越明顯。

4.3.2 跨區(qū)查詢時間開銷

實驗結(jié)果如圖7所示，優(yōu)化后連接算法的執(zhí)行效率要明顯由于原有連接算法。進行連接優(yōu)化后，時間開銷隨連接記錄數(shù)增加呈線性增長，而未優(yōu)化的連接算法呈幾乎指數(shù)級的增長態(tài)勢。在連接量較少時，原有連接算法略優(yōu)于優(yōu)化算法，這是因為數(shù)據(jù)混洗引起的時間開銷高于優(yōu)化的時間代價。而連接的記錄數(shù)越多，優(yōu)化的連接算法優(yōu)勢越大，其原因主要在于未優(yōu)化連接操作低效地兩兩連接，而優(yōu)化后連接算法通過hash成功規(guī)避了低效連接操作，縮小了連接范圍。

圖7 跨區(qū)查詢性能對比

4.3.3 跨段查詢時間開銷

實驗結(jié)果如圖8所示，在四次不同時間版本跨度的查詢中，有三次查詢的耗時在5秒左右，只有最后一次查詢的時間開銷為10秒，這是因為前三次范圍查詢只涉及一個數(shù)據(jù)段，最后一次范圍查詢涉及到了兩個數(shù)據(jù)段。Spark集群將時態(tài)數(shù)據(jù)分段構(gòu)建索引，在進行時態(tài)操作時，集群首先查詢?nèi)炙饕?，將時態(tài)區(qū)間與查詢時間版本有交叉的索引文件逐一從HDFS讀入Spark集群進行查詢。同時，由實驗數(shù)據(jù)可知，在進行范圍查詢時往往只涉及到一至兩個數(shù)據(jù)段，這是因為數(shù)據(jù)本身的時態(tài)特性就決定了數(shù)據(jù)本身在時間維度上是聚集連續(xù)的，在進行時態(tài)范圍查詢時只涉及到少數(shù)的數(shù)據(jù)段。因此，分段查詢在解決了數(shù)據(jù)量過大無法構(gòu)建索引問題的同時，還保證了查詢的效率。

圖8 跨段查詢時間開銷

5 結(jié) 語

本文針對現(xiàn)有時態(tài)索引在數(shù)據(jù)量過大，普通硬件環(huán)境難以支持的問題，基于時態(tài)數(shù)據(jù)的特性，提出基于Spark的分布式時態(tài)索引方法。該方法在Spark集群上按數(shù)據(jù)分區(qū)單獨構(gòu)建時態(tài)索引，在此基礎上優(yōu)化輔助索引checkpoint結(jié)構(gòu)，設計面向?qū)ο缶S度的輔助索引以及全局雙hash結(jié)構(gòu)，全面高效地支持各種時態(tài)查詢操作。最后，通過基準數(shù)據(jù)集上的實驗驗證了所提方法的有效性。目前本文所實現(xiàn)的Spark時間索引是在離線數(shù)據(jù)的基礎上，在接下來的研究中，我們準備實現(xiàn)實時監(jiān)控的流式構(gòu)建時態(tài)索引系統(tǒng)，并進一步優(yōu)化在跨區(qū)查詢時面對大量混洗數(shù)據(jù)的查詢算法。

參 考 文 獻

[1] Yong Tang.TimeDB-A Temporal Relational DBMS[OL].[2015-03-05].http://www.timeconsult.com/software/software.html, 1999.

[2] Saracco C M,Nicola M,Gandhi L.A matter of time:Temporal data management in DB2 10[R].Technical report,IBM,2012.

[3] Kaufmann M,Fischer P M,May N,et al.TPC-BiH:A Benchmark for Bitemporal Databases[M]//Performance Characterization and Benchmarking.Springer International Publishing,2013:16-31.

[4] Elmasri R,Wuu G T J,Kim Y J.The time index:An access structure for temporal data[C]//Proceedings of the 16th International Conference on Very Large Data Bases.San Francisco,CA:Morgan Kaufmann Publishers,1990:1-12.

[5] Tao Y,Papadias D.Efficient historical R-trees[C]//Scientific and Statistical Database Management,2001.SSDBM 2001.Proceedings.Thirteenth International Conference on.IEEE,2001:223-232.

[6] Zhang F,Wang X,Ma S.Temporal XML Indexing Based on Suffix Tree[C]//Acis International Conference on Software Engineering Research,Management and Applications.IEEE,2009:140-144.

[7] Kaufmann M,Manjili A A,Vagenas P,et al.Timeline index:a unified data structure for processing queries on temporal data in SAP HANA[C]//ACM SIGMOD International Conference on Management of Data.ACM,2013:1173-1184.

[8] Kaufmann M,Fischer P M,May N,et al.Bi-temporal Timeline Index:A data structure for Processing Queries on bi-temporal data[C]//IEEE,International Conference on Data Engineering.IEEE,2015:471-482.

[9] Zaharia M,Chowdhury M,Franklin M J,et al.Spark:cluster computing with working sets[C]//Usenix Conference on Hot Topics in Cloud Computing.USENIX Association,2010:10-10.

[10] Becker B,Gschwind S,Ohler T,et al.An asymptotically optimal multiversion B-tree[J].The VLDB Journal,1996,5(4):264-275.

[11] Tao Y,Papadias D.MV3R-Tree:A Spatio-Temporal Access Method for Timestamp and Interval Queries[C]//VLDB 2001,Proceedings of,International Conference on Very Large Data Bases,September 11-14,2001,Roma,Italy.DBLP,2001:431-440.

[12] Liao H,Han J,Fang J.Multi-dimensional Index on Hadoop Distributed File System[C]//International Conference on Networking,Architecture,and Storage,Nas 2010,Macau,China,July.2010:240-249.

[13] Gankidi V R,Teletia N,Patel J M,et al.Indexing HDFS data in PDW[J].Proceedings of the VLDB Endowment,2014,7(13):1520-1528.

[14] Xie D,Li F,Yao B,et al.Simba:Efficient In-Memory Spatial Analytics[C]//International Conference on Management of Data.ACM,2016:1071-1085.

[15] Funke F,Kemper A,Krompass S,et al.Metrics for measuring the performance of the mixed workload CH-benCHmark[C]//Tpc Technology Conference on Topics in PERFORMANCE Evaluation,Measurement and Characterization.Springer-Verlag,2011:10-30.