基于LOP的分布式數據存儲與查詢技術

羅先錄，葉小平，2，王千秋，李 強

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

1 引 言

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

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

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

2 線序劃分LOP

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

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

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

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

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

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

Step3. 輸出點集Lk.

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

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

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

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

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

例1.假設有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實際上建立起了時態數據集合上的一種具有較強意義的數據結構，而作為一種等價劃分，各個線序分枝等價類之間具有比一般數據子集之間更弱的獨立性，這就為分布式數據存儲的其它工作例如分布式查詢結果整合等提供技術支撐.

3 分布式數據存儲與查詢

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

對于構建了線序劃分LOP的時態數據集合來說，對于時間查詢Qt，其查找過程具有下述特點：

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

當Qt∩maxLOB=?，LOB中所有元素都不是查詢結果；

當Qt?minLOB時，LOB中所有元素都是查詢結果.

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

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

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

分布式數據分配以上述定理多表示的時態數據查詢特征為基礎.

3 數據分配策略

如前所述，LOP實際上已將所有時態數據分片為彼此獨立的LOB，現在我們主要考慮LOB的分布式存儲策略.

主服務器記為Master，其余節點記為Slave.這里的Master和Slave都是節點.Master基本功能設計：

數據分配：建立數據分片和Slave節點數據分配.

查詢任務分配：Master保存分配到每個Slave節點的LOB對應ID和每個LOB的maxLOB.對查詢Qt，通過考察Qt∩maxLOB=?與否，將查詢Qt發送到含有Qt∩maxLOB≠?的LOB的Slave節點.

查詢結果輸出：將各個相應節點滿足時間約束Qt的查詢結果作為最終時間查詢數據集合輸出.

Slave節點基本功能設計：

圖2 基于LOP分布式存儲機制

數據存儲：保存Master配置的數據LOB；

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

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

3.1.1 基于期間均衡分片

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

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

算法2. (時間期間均衡數據分片)設有m各Slave節點，則每個Slave節點分配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. 結束.

3.1.2基于查詢期望分片

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

類似，若VT0∈Γ，其中VT0=[VT0s，VT0e)，所有被VT0包含的VT都位于如圖3所示三角形區域Δ(VT0)內.當查詢期間Q∈Δ(VT0)時，VT是所需查詢結果，即Δ(VT0)是在Q查詢中LOB所能發揮作用的區域.設以Δ(VT0)表示其中包含VT個數，則Δ(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∈Γ，定義隨機變量X(VT)：若VT是查詢結果，X(VT)=1；否則X(VT)=0.隨機變量X(VT)的查詢期望E(X(VT))簡記為E(VT).

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

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

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

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

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

Step1. i=1；

Step2. count=0；P={}；

Step3. 如果count

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

Step5. 結束.

例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

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

3.2 分布式數據查詢

如前面圖2所示，Master負責保存Map，記錄線序分支號與Slave節點的映射，將查詢發送往正確的Slave節點.Slave節點存儲分塊的線序分支Part，執行查詢請求.查詢Q發送給Master節點，Master節點會根據存儲在本地的Map查到需要到哪一塊Part去查找，然后將查詢Q發送往存儲著對應Part的Slave節點.

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

1)Master根據Map，請求查詢的時間區間找到對應的Slave節點

2)將請求發往相應的Slave節點

3)等待Slave節點返回結果

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

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

3.2.1 數據查詢算法

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

例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作為二級索引，進行查詢時，先通過MLOP查找，判斷是否需要在對應的線序分支中進行查找.

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

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

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

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

Step1. out={}；i=1；

Step2. 如果i>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，轉到Step 2；

Step4. 輸出out.

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

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

Step1. out={}；i=1；

Step2. 如果i>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，轉到Step 2；

Step4. 輸出out.

例4. 假設要對例1中生成的LOP進行時間期間的包含查詢，Q=[1，5)，找出所有被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)}.將結果合并得到查詢結果集{[1，3)[1，2)[1，5)[1，4)[2，3)[2，5)[3，5)[4，5)}.

3.2.2 查詢效率分析

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

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

(1)

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

(2)

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

(3)

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

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

3.2.3 自動部署

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

圖4 函數f(x)的圖像Fig.4 Picture of function f(x)圖5 3個節點組成的環Fig.5 A ring consisting of 3 nodes

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

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

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

當進程收到一個當選消息，它將自己標記為非參加者，并記錄消息里的標識為當選進程，并將消息轉發到下一個進程；如果它已經是Master，則終止.

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

假設PC0運行Master，如果經過一段時間的更新后，PC1的EN變為了PC0的2倍，則PC1將選舉消息發送給PC2，如果PC2的EN值比EN(LOP1)小，則轉發消息；如果EN(LOP2)>EN(LO1)，則PC2將作為消息發送.

當消息經過了一個循環又回到了PCi，則PCi被選舉出來運行Master，并向下一個PC發送當選消息.

4 仿真與評估

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

圖6 系統查詢時間隨查詢規模的變化趨勢

實驗需要記錄整個系統的開銷和每一臺Slave節點的查詢開銷與通信開銷.每次實驗使用5組數據，從50個查詢開始，每次增加50個查詢，到250個查詢為止，每一次都在Master上記錄下系統查詢所花費的時間，在Slave節點上記錄下相應的查詢時間與通信時間.

圖7 按期間個數分片時Slave節點的查詢時間與傳輸結果的時間隨查詢規模的變化

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

如圖6、圖8所示的系統查詢開銷，隨著查詢規模的增加，整個系統的查詢時間線性增加.如圖7所示，相對于Slave節點與Master之間的數據傳輸時間，Slave節點上的查詢時間很小.

圖8 系統查詢時間隨查詢規模的變化趨勢

圖10展示了按個數分片LOP和按期望分片LOP的通信時間之間的差異，可以看出，按個數分片時，2個slave節點的

圖9 按查詢期望分片時Slave1節點、Slave2節點的查詢時間與傳輸結果的時間隨查詢規模的變化

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

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

如圖11所示，按時間期間的個數分片時，2個Slave節點的查詢開銷比較接近，按時間期間的查詢期望分片時，Slave1節點與Slave2節點的查詢開銷相差較遠.

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

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

5 結束語

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