基于LOP的分布式數(shù)據(jù)存儲與查詢技術(shù)

羅先錄，葉小平，2，王千秋，李 強(qiáng)

1(廣東東軟學(xué)院 計算機(jī)科學(xué)與技術(shù)系，廣東 佛山 528225 2(華南師范大學(xué) 計算機(jī)學(xué)院，廣州 510631)

1 引 言

進(jìn)入新世紀(jì)后，互聯(lián)網(wǎng)技術(shù)飛速發(fā)展，各項關(guān)鍵技術(shù)都在更大規(guī)模和更深層面上向互聯(lián)網(wǎng)工程應(yīng)用轉(zhuǎn)化，而Google、Amazon、Alibaba 等互聯(lián)網(wǎng)公司的業(yè)務(wù)發(fā)展于成功運(yùn)營同時也催生了云計算和大數(shù)據(jù)兩大熱門計算機(jī)技術(shù)領(lǐng)域，還為數(shù)據(jù)科學(xué)這門新型計算機(jī)學(xué)科誕生和發(fā)展提供了強(qiáng)大驅(qū)動.在云計算、大數(shù)據(jù)等基于各種應(yīng)用環(huán)境下，研究開發(fā)低成本、高性能、可擴(kuò)展和易用性強(qiáng)的分布式存儲系統(tǒng)就成為構(gòu)建云計算及大數(shù)據(jù)其后臺基礎(chǔ)設(shè)施的主要挑戰(zhàn)[1，2].實際上，基于數(shù)據(jù)管理的分布式系統(tǒng)早已為人們所研究關(guān)注，新世紀(jì)中互聯(lián)網(wǎng)大數(shù)據(jù)應(yīng)用的迅猛興起更為它大規(guī)模深層次應(yīng)用到各類工程實踐當(dāng)中開辟了無比廣闊的發(fā)展空間，人們甚至認(rèn)為，正是那些已經(jīng)對經(jīng)濟(jì)生活和社會活動產(chǎn)生了重大影響互聯(lián)網(wǎng)公司重新定義了大規(guī)模分布式系統(tǒng).

人們通常將大規(guī)模分布式存儲系統(tǒng)分為分布式文件系統(tǒng)、分布式鍵值(Key-Value)系統(tǒng)、分布式表格系統(tǒng)和分布式數(shù)據(jù)庫等四種情形[3].分布式文件系統(tǒng)主要存儲圖形圖片、音頻視頻等非結(jié)構(gòu)化數(shù)據(jù)對象，基本特點(diǎn)數(shù)據(jù)之間缺少關(guān)聯(lián)，例如 Facebook Haystack 及 Taobao File System(TFS)；分布式鍵值系統(tǒng)主要存儲關(guān)系簡單的半結(jié)構(gòu)化數(shù)據(jù)，基本特點(diǎn)是提供基于主鍵的 CRUD(Create/Read/Update/Delete)功能，如Amazon Dynamo 以及 Taobao Tair；分布式表格系統(tǒng)主要存儲關(guān)系較為復(fù)雜的半結(jié)構(gòu)化數(shù)據(jù)，基本特點(diǎn)是在 CRUD 操作基礎(chǔ)上支持掃描某個主鍵范圍，如Google Bigtable 以及 Megastore，Microsoft Azure TableStorage，Amazon DynamoDB 等；分布式數(shù)據(jù)庫可以看作是由單機(jī)關(guān)系數(shù)據(jù)庫擴(kuò)展而來，基本特點(diǎn)是用于存儲結(jié)構(gòu)化數(shù)據(jù)，如MySQL 數(shù)據(jù)庫分片(MySQL Sharding)集群、Amazon RDS 以及Microsoft SQL Azure.相比傳統(tǒng)的分布式系統(tǒng)，如今基于互聯(lián)網(wǎng)公司工程應(yīng)用的分布式系統(tǒng)具有數(shù)據(jù)規(guī)模大(大數(shù)據(jù))和應(yīng)用成本低(廉價PC機(jī)集群)的顯著特征，需要解決數(shù)據(jù)分布、數(shù)據(jù)一致、數(shù)據(jù)容錯、負(fù)載均衡、并發(fā)讀寫和易用性等基本技術(shù)[4]，而這些在邏輯上都會涉及到其中的關(guān)鍵技術(shù)——數(shù)據(jù)分配或數(shù)據(jù)分片，這是由于數(shù)據(jù)分配的適當(dāng)合理與否直接關(guān)系到數(shù)據(jù)的分配和負(fù)載均衡，也關(guān)系到大數(shù)據(jù)運(yùn)行過程中的數(shù)據(jù)自配置和容錯機(jī)制的復(fù)雜與否等.

由于數(shù)據(jù)模式的多樣性，通常大多采用基于鍵值和基于“列”存儲技術(shù)的大數(shù)據(jù)存儲技術(shù)[5].特別是在希望借助于成熟關(guān)系數(shù)據(jù)庫相關(guān)標(biāo)準(zhǔn)與技術(shù)情況下，分布式的基于“列存儲”的Hbase多為人們所選用*http://hbase.apache.org/book.html.有一種實際應(yīng)用是數(shù)據(jù)與相應(yīng)的時間約束密切相關(guān)，例如企業(yè)的人事工資管理、季節(jié)性時令商品的銷售管理、醫(yī)療數(shù)據(jù)記錄管理以及金融往來數(shù)據(jù)管理等.在這其中，可以將數(shù)據(jù)相應(yīng)的時間標(biāo)簽看作是數(shù)據(jù)的一個屬性，按照應(yīng)用需求將相關(guān)數(shù)據(jù)按照時間標(biāo)簽進(jìn)行管理.基于這樣考慮，本文研究一種基于時間標(biāo)簽進(jìn)行數(shù)據(jù)分片的技術(shù).首先是基于時間標(biāo)簽對相應(yīng)數(shù)據(jù)進(jìn)行“等價劃分LOP”[6]，再按照數(shù)據(jù)等價類將數(shù)據(jù)分配在各個節(jié)點(diǎn)；其次根據(jù)劃分等價類特性，在各個節(jié)點(diǎn)統(tǒng)一配置一種基于索引的數(shù)據(jù)查詢機(jī)制，從而完成數(shù)據(jù)的分布式管理.由于數(shù)據(jù)等價類之間并沒有像關(guān)系數(shù)據(jù)那樣的緊密關(guān)聯(lián)，因此可以減弱大數(shù)據(jù)分布式存儲實現(xiàn)過程中的復(fù)雜性和技術(shù)難度.特別是該項技術(shù)還可推廣到帶有空間約束和更一般的時空約束情形，同時適應(yīng)結(jié)構(gòu)化數(shù)據(jù)與半結(jié)構(gòu)及非結(jié)構(gòu)分布式管理需求.

2 線序劃分LOP

帶有時間標(biāo)簽的數(shù)據(jù)通常稱為時態(tài)數(shù)據(jù)，可以將其看作是由一個不含時間因素的部分與一個時間標(biāo)簽構(gòu)成的二元組Td=.為討論方便，本文中時間標(biāo)簽Timestamp設(shè)為數(shù)據(jù)非時間部分D的有效時間期間(valid time period，VT)，并記為VT=[VTs，VTe)，VTs和VTe分別表示VT時間始點(diǎn)和終點(diǎn)(VTs≤VTe).若VTs=VTe，則定義VT=[VTs，VTe)為時刻(instant).設(shè)Td是時態(tài)數(shù)據(jù)，Td的有效時間期間記為VT(Td).

時間期間VT=[VTs，VTe)，由其時間始點(diǎn)VTs，和時間終點(diǎn)VTe確定，因此可以映射VTs-VTe平面上的點(diǎn)，即時間期間VT=[VTs，VTe)和VTs-VTe平面上點(diǎn)P(VT)=(VTs，VTe)是一個1-1對應(yīng).此時，稱P(u)=(VTs，VTe)為u對應(yīng)的(二維)時點(diǎn)(2-dimension time point).

定義1.(時態(tài)擬序和線序劃分)集合E上的滿足自反性和傳遞性的關(guān)系稱為E上的一個擬序關(guān)系.

算法1. (“下右優(yōu)先”LOB構(gòu)建算法)設(shè)u(i，j)為H(Γ)“最左上方”點(diǎn)，P=u(i，j)，Lk={P}，k=1.設(shè)col(i)為第i列各點(diǎn).

Step1. 遍歷col(i)直到最后點(diǎn)K(i，m)(i≤m≤j)，依次將遍歷過的點(diǎn)放入Lk，P=K(i，m).

Step2. 若?N(i+1，m)∈H(Γ)∧VTe(N)≤VTe(K)，將其放入Lk，i++，轉(zhuǎn)step 1；否則，若i=m，執(zhí)行step 3，否則，i++，繼續(xù)執(zhí)行step 2.

Step3. 輸出點(diǎn)集Lk.

Step4. H(Γ)=H(Γ)/ Lk，若H(Γ)≠?，k++，轉(zhuǎn)step 1，否則，算法終止.

通過算法1遍歷H(Γ)所得序列記為∑(Γ)=.按照定義1，Li就是Γ的LOBi(1≤i≤m).設(shè)VTs(Γ)=max{VTs(u)|u∈Γ}，VTe(Γ)=max{VTe(u)|u∈Γ}，則算法1時間復(fù)雜度為(VTs(Γ)×VTe(Γ))/2.

設(shè)Δ0是Γ上的線序劃分，Δ為Γ上任一線序劃分，Δ0是Γ上“最小”線序劃分當(dāng)且僅當(dāng)|Δ0|≤|Δ|，其中，|Δ|表示Δ中線序分支的條數(shù).

按照參考文獻(xiàn)[7，8]可知，在Γ上由算法1得到的線序劃分是Γ上最小線序劃分.

算法1只是求解線序分枝的一種方法，但上述定理說明，從線序分枝個數(shù)“最少”也就是LOP規(guī)模最小(其中線序分枝“最大”)考慮，算法1具有最優(yōu)性質(zhì).

例1.假設(shè)有30個時間期間Σ={[0，3)，[0，4)，[0，5)，[0，6)，[0，8)，[0，9)，[1，2)，[1，3)，[1，4)，[1，5)，[1，6)，[1，7)，[1，8)，[1，9)，[2，3)，[2，5)，[2，6)，[2，9)，[3，5)，[3，7)，[3，8)，[4，5)，[4，7)，[5，7)，[5，8)，[5，9)，[6，7)，[6，8)，[7，8)，[8，9)}；按算法1生成線序劃分LOP如下：

LOB1{[0，9)[0，8)[0，6)[0，5)[0，4)[0，3)[1，3)[1，2)}

LOB2{[1，9)[1，8)[1，7)[1，6)[1，5)[1，4)[2，3)}

LOB3{[2，9)[2，6)[2，5)[3，5)[4，5)}

LOB4{[3，8)[3，7)[4，7)[5，7)[6，7)}

LOB5{[5，9)[5，8)[6，8)[7，8)}

LOB6{[8，9)}

如圖1所示，是以上生成的線序劃分在VTs-VTe平面上的表示.

圖1 Σ生成的線序劃分；共有6個線序分支

LOP實際上建立起了時態(tài)數(shù)據(jù)集合上的一種具有較強(qiáng)意義的數(shù)據(jù)結(jié)構(gòu)，而作為一種等價劃分，各個線序分枝等價類之間具有比一般數(shù)據(jù)子集之間更弱的獨(dú)立性，這就為分布式數(shù)據(jù)存儲的其它工作例如分布式查詢結(jié)果整合等提供技術(shù)支撐.

3 分布式數(shù)據(jù)存儲與查詢

分布式數(shù)0據(jù)存儲的初衷有二：首先是數(shù)據(jù)量巨大，單個節(jié)點(diǎn)無法將其整體保存；其次，存儲目的是使用，需要基于不同的相應(yīng)數(shù)據(jù)查詢特點(diǎn)對各個節(jié)點(diǎn)數(shù)據(jù)進(jìn)行配置.時態(tài)數(shù)據(jù)查詢一般都是先進(jìn)行時間標(biāo)簽查找，再將滿足相應(yīng)時間約束的數(shù)據(jù)進(jìn)行其基于應(yīng)用背景的篩選.基于時間標(biāo)簽查找中的具有代表性的是“包含查找”，即當(dāng)Qt是數(shù)據(jù)查詢的時間約束時，查找所有時間標(biāo)簽包含Qt的相關(guān)數(shù)據(jù).本文主要研究基于時間查找的分布式數(shù)據(jù)部署，以下僅討論時間標(biāo)簽的包含查找.對于數(shù)據(jù)的時間約束和實際應(yīng)用約束整合的一般查找，是一個相對更具挑戰(zhàn)的課題，可參見參考文獻(xiàn)[6-8].

對于構(gòu)建了線序劃分LOP的時態(tài)數(shù)據(jù)集合來說，對于時間查詢Qt，其查找過程具有下述特點(diǎn)：

定理1. (基于LOP查詢特征)設(shè)LOB是LOP的線序分枝，maxLOB和minLOB是其最大元和最小元.

當(dāng)Qt∩maxLOB=?，LOB中所有元素都不是查詢結(jié)果；

當(dāng)Qt?minLOB時，LOB中所有元素都是查詢結(jié)果.

證明：由于LOB中所有元素都包含在maxLOB當(dāng)中，所以當(dāng)Qt∩maxLOB=?，LOB中沒有任何元素包含Qt，LOB中所有元素都不是查詢結(jié)果；再由于minLOB被LOB中任何元素所包含，所以當(dāng)Qt?minLOB時，LOB中任何元素都包含Qt，LOB中所有元素都是查詢結(jié)果.證畢.

由定理1容易推知下述推論成立.

推論1.設(shè)VT∈LOB，若Qt∩VT=?，則VT所有后繼組成的LOB片段都不是查詢結(jié)果；若Qt?VT，則VT所有前驅(qū)組成的LOB片段都是查詢結(jié)果.

分布式數(shù)據(jù)分配以上述定理多表示的時態(tài)數(shù)據(jù)查詢特征為基礎(chǔ).

3 數(shù)據(jù)分配策略

如前所述，LOP實際上已將所有時態(tài)數(shù)據(jù)分片為彼此獨(dú)立的LOB，現(xiàn)在我們主要考慮LOB的分布式存儲策略.

主服務(wù)器記為Master，其余節(jié)點(diǎn)記為Slave.這里的Master和Slave都是節(jié)點(diǎn).Master基本功能設(shè)計：

數(shù)據(jù)分配：建立數(shù)據(jù)分片和Slave節(jié)點(diǎn)數(shù)據(jù)分配.

查詢?nèi)蝿?wù)分配：Master保存分配到每個Slave節(jié)點(diǎn)的LOB對應(yīng)ID和每個LOB的maxLOB.對查詢Qt，通過考察Qt∩maxLOB=?與否，將查詢Qt發(fā)送到含有Qt∩maxLOB≠?的LOB的Slave節(jié)點(diǎn).

查詢結(jié)果輸出：將各個相應(yīng)節(jié)點(diǎn)滿足時間約束Qt的查詢結(jié)果作為最終時間查詢數(shù)據(jù)集合輸出.

Slave節(jié)點(diǎn)基本功能設(shè)計：

圖2 基于LOP分布式存儲機(jī)制

數(shù)據(jù)存儲：保存Master配置的數(shù)據(jù)LOB；

數(shù)據(jù)查詢：按照3.2.1中算法3和算法4完成時間查詢Qt.

基于LOP分布式存儲機(jī)制如圖2所示.

3.1.1 基于期間均衡分片

由推論1可知，查詢開銷與給定LOB所包含元素即時間期間數(shù)量有關(guān)，因此將LOB按照時間期間的個數(shù)做到盡可能的均勻分片是一個合理的選擇，這就使查詢開銷和其他負(fù)載在每一個Slave節(jié)點(diǎn)上大致均衡.

設(shè)maxLOP和minLOP分別是給定LOP中包含元素最多和最少的LOB，記m=(|maxLOP|+|minLOP|)/2，此時可以根據(jù)實際情況選擇閾值α和β，對于|LOB|≥m+α的LOB進(jìn)行分片，使得分片后的各個線序分枝中元素個數(shù)在|minLOP|+β和m之間.此時相當(dāng)?shù)玫搅艘粋€新的線序劃分仍將其記為LOP，設(shè)|{Slave}|表示Slave節(jié)點(diǎn)個數(shù)，此時按照n=|LOP|/|{Slave}|將LOP中的LOB“均衡”分配到各個節(jié)點(diǎn).

算法2. (時間期間均衡數(shù)據(jù)分片)設(shè)有m各Slave節(jié)點(diǎn)，則每個Slave節(jié)點(diǎn)分配n=|LOP|/m個LOB.

Step1. i=1；

Step2. count=0；P={}；

Step3. 如果count

否則，輸出P，Goto Step 2；

Step4. 如果i<=m，Goto 2；否則，輸出P，Goto Step 2；

Step5. 結(jié)束.

3.1.2基于查詢期望分片

VT=[VTs，VTe)可以看做VTs-VTe平面上的點(diǎn)(VTs，VTe).設(shè)maxΓe=max{VTe}，則所有時間期間都位于VTs-VTe平面上一個(max(Γ)+1)(max(Γ)+1)的上三角陣區(qū)域，此時LOP(Γ)中至多有S=(max(Γ)+1)(max(Γ)+2)/2個時間期間VT如圖2所示.

類似，若VT0∈Γ，其中VT0=[VT0s，VT0e)，所有被VT0包含的VT都位于如圖3所示三角形區(qū)域Δ(VT0)內(nèi).當(dāng)查詢期間Q∈Δ(VT0)時，VT是所需查詢結(jié)果，即Δ(VT0)是在Q查詢中LOB所能發(fā)揮作用的區(qū)域.設(shè)以Δ(VT0)表示其中包含VT個數(shù)，則Δ(VT0)=(VT0e-VT0s+1)(VT0e-VT0s+2)/2.

圖3 時間期間[3，5)期望的圖示

如圖3所示，計算VT=[3，5)的期望，時間期間的最大值MAXT=9，S=(9+1)(9+2)/2=55，共有55個時間期間，EN(VT)=6/55.

定義2. (LOP(Γ)的查詢期望)

1)給定查詢Qt，?VT∈Γ，定義隨機(jī)變量X(VT)：若VT是查詢結(jié)果，X(VT)=1；否則X(VT)=0.隨機(jī)變量X(VT)的查詢期望E(X(VT))簡記為E(VT).

對于查詢過程中涉及到的Γ而言，由查詢Qt是隨機(jī)的，所以將X(VT)作為隨機(jī)變量應(yīng)當(dāng)是合理的.

2)?LOB∈LOP(Γ)，LOB中基于Qt的查詢結(jié)果個數(shù)記為N(LOB)=∑X(VTi)，其中VTi∈LOB.此時，N(LOB)可以看做是基于查詢Qt的隨機(jī)函數(shù).隨機(jī)函數(shù)N(LOB)的查詢期望記為E(N(LOB))=∑E(X(VTi))=∑E(VTi)=∑P(VTi).

3)給定LOP，對于Γ中每個VT和LOB，計算出相應(yīng)的E(VT)和E(N(LOB))，由此定義LOP的查詢期望E(LOP)=∑E(N(LOBi))

設(shè)有n個Slave節(jié)點(diǎn)，此時從負(fù)載均衡考慮，每個Slave節(jié)點(diǎn)中各個LOB的查詢期望和大約取為EN(LOP)/n比較合適.由此得到基于節(jié)點(diǎn)查詢期望的數(shù)據(jù)分片算法如下.

算法3. (基于查詢期望的分片策略)按照時間期間查詢期望將LOP分片成n份：

Step1. i=1；

Step2. count=0；P={}；

Step3. 如果count

Step4. 如果i<=n，Goto Step 2；否則，輸出P，Goto Step 5；

Step5. 結(jié)束.

例2.對例1中的線序劃分做分片

LOB1 {[0，9)[0，8)[0，6)[0，5)[0，4)[0，3)[1，3)[1，2)}

LOB2 {[1，9)[1，8)[1，7)[1，6)[1，5)[1，4)[2，3)}

LOB3 {[2，9)[2，6)[2，5)[3，5)[4，5)}

LOB4 {[3，8)[3，7)[4，7)[5，7)[6，7)}

LOB5 {[5，9)[5，8)[6，8)[7，8)}

LOB6 {[8，9)}

E(N(LOB1))= 3.327，E(N(LOB2))=2.8727，E(N(LOB3))=1.27，

E(N(LOB4))= 1.0，E(N(LOB5))=0.618，E(N(LOB6))=0.0545

E(LOP)=∑E(N(LOBi))=9.145

將LOP分片為2份，E(LOP)/2=4.57.

E(N(LOB1))+E(N(LOB2))=6.1997

E(N(LOB3))+E(N(LOB4))+E(N(LOB5))+E(N(LOB6))=2.9425

所以分片的結(jié)果為Part1 {LOB1，LOB2}，Part2 {LOB3，LOB4，LOB5，LOB6}

3.2 分布式數(shù)據(jù)查詢

如前面圖2所示，Master負(fù)責(zé)保存Map，記錄線序分支號與Slave節(jié)點(diǎn)的映射，將查詢發(fā)送往正確的Slave節(jié)點(diǎn).Slave節(jié)點(diǎn)存儲分塊的線序分支Part，執(zhí)行查詢請求.查詢Q發(fā)送給Master節(jié)點(diǎn)，Master節(jié)點(diǎn)會根據(jù)存儲在本地的Map查到需要到哪一塊Part去查找，然后將查詢Q發(fā)送往存儲著對應(yīng)Part的Slave節(jié)點(diǎn).

系統(tǒng)中只有一個Master，將LOP分片后分別放在不同的Slave節(jié)點(diǎn)上，查詢請求發(fā)往Master；然后Master向Slave節(jié)點(diǎn)分發(fā)請求；等待所查詢結(jié)果返回.Master需要保存不同的Slave節(jié)點(diǎn)上保存的索引范圍的信息，查詢時：

1)Master根據(jù)Map，請求查詢的時間區(qū)間找到對應(yīng)的Slave節(jié)點(diǎn)

2)將請求發(fā)往相應(yīng)的Slave節(jié)點(diǎn)

3)等待Slave節(jié)點(diǎn)返回結(jié)果

要將LOP的分片放在不同的計算機(jī)，需要一個分片LOP的方法，本文討論了2種分片線序劃分的方法.

設(shè)時間期間集合Γ由算法1生成的線序劃分LOP={LOB1，LOB2，…，LOBL}.由線序劃分的定義，任一線序分支LOBi內(nèi)的所有時間期間滿足序關(guān)系，記LOBi的最大時間期間為max(LOBi)，最小時間期間為min(LOBi).

3.2.1 數(shù)據(jù)查詢算法

定義3. (時態(tài)數(shù)據(jù)索引，TDindex)對集合Γ的線序劃分LOP的每一個線序分支記錄下最大時間期間，最小時間期間與線序序號.對于線序分支LOBi，記錄(i，max(LOBi)，min(LOBi)).所以對LOP的整個記錄為{(i，max(LOBi)，min(LOBi))|1≤i≤L，L為線序分支的個數(shù)}，記為MLOP.稱(MLOP，LOP)二元組為時態(tài)數(shù)據(jù)索引.

例3. 對于例1中生成的LOP，其MLOP如下：

{(1，[0，9)，[1，2))，(2，[1，9)，[2，3))，(3，[2，9)，[4，5))，(4，[3，8)，[6，7))，(5，[5，9)，[7，8))，(6，[8，9)，[8，9))}

將時間期間集合Γ的MLOP作為一級索引，LOP作為二級索引，進(jìn)行查詢時，先通過MLOP查找，判斷是否需要在對應(yīng)的線序分支中進(jìn)行查找.

時間期間之間的關(guān)系參見Allen提出的13種互不相交且聯(lián)合完備的基本區(qū)間關(guān)系([10]).下面主要討論包含與被包含查詢操作.

假設(shè)要查詢包含時間期間Q=[s，e)的時間期間，由定理2，如果一條線序分支的最大元素max(LOBi)不包含Q，則LOBi中的所有時間期間都不包含Q；如果max(LOBi)包含Q，則需要在LOBi中再使用二分查找.

算法4. (時間期間的包含查詢算法)

輸入時間期間Q，輸出被時間期間Q包含的所有時間期間的集合

Step1. out={}；i=1；

Step2. 如果i>n 轉(zhuǎn)到Step 4；

Step3. 如果min(LOBi)包含Q，在LOBi中使用2分查找到Q的下界inf(Q)，從min(LOBi)到inf(Q)的集合Pi={u|u∈LOBi且Qtu}；out=out∪Pi；如果min(LOBi)不包含Q；i=i+1，轉(zhuǎn)到Step 2；

Step4. 輸出out.

算法5. (時間期間的被包含查詢)

輸入時間期間Q，輸出包含時間期間Q的所有時間期間的集合

Step1. out={}；i=1；

Step2. 如果i>n轉(zhuǎn)到Step 4；

Step3. 如果max(LOBi)包含Q，在LOBi中使用2分查找到Q的上界sup(Q)，從max(LOBi)到sup(Q)的集合Pi={u|u∈LOBi且Qu}；out=out∪Pi；如果max(LOBi)不包含Q；i=i+1，轉(zhuǎn)到Step 2；

Step4. 輸出out.

例4. 假設(shè)要對例1中生成的LOP進(jìn)行時間期間的包含查詢，Q=[1，5)，找出所有被Q包含的時間區(qū)間，首先從MLOP中找出最小時間期間被Q包含的線序分支，一共有3條(1，[0，9)，[1，2))，(2，[1，9)，[2，3))，(3，[2，9)，[4，5)).再分別從1號線序分支中查找出{[1，3)[1，2)}，從2號線序分支中查找出{[1，5)[1，4)[2，3)}，從3號線序分支中查找出{[2，5)[3，5)[4，5)}.將結(jié)果合并得到查詢結(jié)果集{[1，3)[1，2)[1，5)[1，4)[2，3)[2，5)[3，5)[4，5)}.

3.2.2 查詢效率分析

假設(shè)有N個時間期間的集合Γ，枚舉查詢的效率O(N).對集合Γ使用算法3-1得到線序劃分LOP，因為每一條線序分支是有序的，查詢可以使用二分搜索；因此，在一條線序分支內(nèi)查找的時間效率為O(log(n)).

假設(shè)LOP有L條線序分支；第i條有ni個時間期間，則n1+n2+…+nL = N.

(1)

由公式(1)可以知道，使用LOP查詢的效率一定優(yōu)于枚舉查詢的效率.下面具體分析LOP的查詢效率.

(2)

由公式(2)可知，LOP的查詢效率與線序分支的條數(shù)L和時間期間的總數(shù)N有關(guān)，查詢中比較次數(shù)可以較為準(zhǔn)確地寫成：

(3)

函數(shù)f(x)=x-xlog(x)在[0，1]之間的圖像如圖4所示.

如圖4，可以知道，L/N的值越小，則F(L，N)越小，對于給定的時間期間集合，N是一個常量，所以線序分支的個數(shù)越少，查詢效率越高.定理1所表明，算法1可以保證生成的線序劃分是所有線序劃分中線序分支個數(shù)最少的，因此可以得出結(jié)論：由算法1生成的LOP使得查詢效率最優(yōu).

3.2.3 自動部署

EN(LOP)的大小影響著通信開銷，如果Master與EN(LOP)較大的Slave節(jié)點(diǎn)在一臺PC上，可以減少通信開銷，因此可以使用基于環(huán)的選舉算法動態(tài)選擇出EN(LOP)最大的PC作為Master，使用基于環(huán)的選舉算法，邏輯上，PC可以看成是沿環(huán)排列的.如圖5所示是由3個節(jié)點(diǎn)組成的邏輯環(huán).

圖4 函數(shù)f(x)的圖像Fig.4 Picture of function f(x)圖5 3個節(jié)點(diǎn)組成的環(huán)Fig.5 A ring consisting of 3 nodes

選取PCi用作為自己的標(biāo)識.標(biāo)識使用EN(LOPi)比較大小.

初始，每個進(jìn)程是選舉中的非參加者.任何進(jìn)程可以開始一次選舉，將自己標(biāo)記為參加者，然后，把自己的標(biāo)識放入一個選舉消息，并發(fā)送到下一個進(jìn)程.

當(dāng)一個進(jìn)程收到選舉消息時，比較消息的標(biāo)識和自己的標(biāo)識，如果到達(dá)的標(biāo)識較大，將消息轉(zhuǎn)發(fā)給它的下一個進(jìn)程.如果到達(dá)的標(biāo)識較小，自己不是一個參加者，則把消息里的標(biāo)識替換為自己的，并轉(zhuǎn)發(fā)消息；如果自己已經(jīng)是參加者，就不轉(zhuǎn)發(fā)消息.只要是轉(zhuǎn)發(fā)一個選舉消息，進(jìn)程把自己標(biāo)記為參加者.如果收到的標(biāo)識是接受者自己，這個進(jìn)程的標(biāo)識一定最大，該進(jìn)程就成為Master.當(dāng)選進(jìn)程將自己標(biāo)記為非參加者并向下一個進(jìn)程發(fā)送一個當(dāng)選消息，將它的標(biāo)識放入消息.

當(dāng)進(jìn)程收到一個當(dāng)選消息，它將自己標(biāo)記為非參加者，并記錄消息里的標(biāo)識為當(dāng)選進(jìn)程，并將消息轉(zhuǎn)發(fā)到下一個進(jìn)程；如果它已經(jīng)是Master，則終止.

假設(shè)選舉出PCi運(yùn)行Master，如果考慮數(shù)據(jù)的更新，將會影響每個EN(LOP)的大小，如果有一個進(jìn)程j的EN(LOPj)的值顯著的超過原來最大的EN(LOPi)這進(jìn)程j發(fā)起一次選舉.

假設(shè)PC0運(yùn)行Master，如果經(jīng)過一段時間的更新后，PC1的EN變?yōu)榱薖C0的2倍，則PC1將選舉消息發(fā)送給PC2，如果PC2的EN值比EN(LOP1)小，則轉(zhuǎn)發(fā)消息；如果EN(LOP2)>EN(LO1)，則PC2將作為消息發(fā)送.

當(dāng)消息經(jīng)過了一個循環(huán)又回到了PCi，則PCi被選舉出來運(yùn)行Master，并向下一個PC發(fā)送當(dāng)選消息.

4 仿真與評估

本文的實驗環(huán)境：3臺PC規(guī)格相同，CPU為intel core i5，內(nèi)存為4G.通過1臺交換機(jī)連接組成100Mbps的以太網(wǎng).實驗的主要目的是驗證分布式時態(tài)索引的可行性，并且與理論分析對比.

圖6 系統(tǒng)查詢時間隨查詢規(guī)模的變化趨勢

實驗需要記錄整個系統(tǒng)的開銷和每一臺Slave節(jié)點(diǎn)的查詢開銷與通信開銷.每次實驗使用5組數(shù)據(jù)，從50個查詢開始，每次增加50個查詢，到250個查詢?yōu)橹?，每一次都在Master上記錄下系統(tǒng)查詢所花費(fèi)的時間，在Slave節(jié)點(diǎn)上記錄下相應(yīng)的查詢時間與通信時間.

圖7 按期間個數(shù)分片時Slave節(jié)點(diǎn)的查詢時間與傳輸結(jié)果的時間隨查詢規(guī)模的變化

實驗使用的數(shù)據(jù)包含200萬個時間區(qū)間，按照算法1生成的LOP包含2834條線序分支.Master進(jìn)程運(yùn)行于1臺PC，Slave1，Slave2分別運(yùn)行于另外2臺PC.進(jìn)行2次實驗，第1次按照個數(shù)(使用算法4-1)被分片成2份.第2次按照時間期間的查詢期望分片成2份.

如圖6、圖8所示的系統(tǒng)查詢開銷，隨著查詢規(guī)模的增加，整個系統(tǒng)的查詢時間線性增加.如圖7所示，相對于Slave節(jié)點(diǎn)與Master之間的數(shù)據(jù)傳輸時間，Slave節(jié)點(diǎn)上的查詢時間很小.

圖8 系統(tǒng)查詢時間隨查詢規(guī)模的變化趨勢

圖10展示了按個數(shù)分片LOP和按期望分片LOP的通信時間之間的差異，可以看出，按個數(shù)分片時，2個slave節(jié)點(diǎn)的

圖9 按查詢期望分片時Slave1節(jié)點(diǎn)、Slave2節(jié)點(diǎn)的查詢時間與傳輸結(jié)果的時間隨查詢規(guī)模的變化

通信時間差異明顯，而按照期望分片時，2個slave節(jié)點(diǎn)的通信時間幾乎保持一致.

圖10 2種分片方法的通信時間對比

如圖11所示，按時間期間的個數(shù)分片時，2個Slave節(jié)點(diǎn)的查詢開銷比較接近，按時間期間的查詢期望分片時，Slave1節(jié)點(diǎn)與Slave2節(jié)點(diǎn)的查詢開銷相差較遠(yuǎn).

圖11 2種分片方法的查詢時間對比

從對比的圖中可以看出，實驗結(jié)果與第4章對LOP的分片的理論分析得到的結(jié)果是一致的.

5 結(jié)束語

分布式數(shù)據(jù)存儲是大數(shù)據(jù)管理中的關(guān)鍵技術(shù)之一，在實際應(yīng)用當(dāng)中，由于大數(shù)據(jù)來源的多樣性導(dǎo)致數(shù)據(jù)類型與數(shù)據(jù)格式的多樣性，加之大數(shù)據(jù)存儲載體需要大量廉價PC機(jī)參與，由此帶來了諸如數(shù)據(jù)自動配置、數(shù)據(jù)一致性和完整性以及容錯性等一系列新挑戰(zhàn).如果能從節(jié)點(diǎn)數(shù)據(jù)分片開始就為將其考慮在內(nèi)，應(yīng)該對于上述問題解決打下一個良好基礎(chǔ).本文討論一種帶有時間標(biāo)簽的大數(shù)據(jù)類型(時態(tài)大數(shù)據(jù))，按照數(shù)據(jù)的時間標(biāo)簽對其進(jìn)行分片.由于這種基于線序劃分LOP的分片是一種等價劃分，分片后各個部分語義獨(dú)立性較強(qiáng)，因此可以為解決分布式存儲中其他一些技術(shù)問題提供一個較好開端.本文同時還討論了基于LOP分節(jié)點(diǎn)數(shù)據(jù)分配方法，提出了一種基于查詢期望的數(shù)據(jù)分配策略和查詢方案.基本仿真評估表明本文工作的可行性和有效性.本文工作可以應(yīng)用于常規(guī)的分布式數(shù)據(jù)庫，也可應(yīng)用在半結(jié)構(gòu)和非結(jié)構(gòu)數(shù)據(jù)的分布式存儲.