葉小平 ，周 暢，廖青云，朱峰華

(華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州510631)

在計(jì)算機(jī)應(yīng)用領(lǐng)域中是通過時(shí)態(tài)數(shù)據(jù)描述和處理客觀事物發(fā)展變化.由于時(shí)態(tài)數(shù)據(jù)量巨大，通常采用基于外存的管理方式.目前，數(shù)據(jù)管理發(fā)展趨勢(shì)是“萬維網(wǎng)與數(shù)據(jù)庫技術(shù)的進(jìn)一步融合”［1］，分布式數(shù)據(jù)管理成為應(yīng)用和研究熱點(diǎn).分布式數(shù)據(jù)庫(DDB)技術(shù)經(jīng)歷了2個(gè)發(fā)展階段. 首先是第一代DDB，其基本研究方向是如何在分布式環(huán)境下實(shí)現(xiàn)單機(jī)數(shù)據(jù)庫的各項(xiàng)基本功能(數(shù)據(jù)分布、事務(wù)管理和查詢優(yōu)化等);再就是新一代DDB，其主要研究方向是動(dòng)態(tài)數(shù)據(jù)復(fù)制、緩存技術(shù)和基于網(wǎng)絡(luò)的系統(tǒng)結(jié)構(gòu)體系例如P2P 等［2］. 從應(yīng)用實(shí)現(xiàn)角度考慮，通信開銷和站點(diǎn)負(fù)載均衡是DDB 關(guān)注的重要環(huán)節(jié).對(duì)整個(gè)系統(tǒng)而言，通信開銷除依賴網(wǎng)絡(luò)條件還依賴于數(shù)據(jù)管理功能配置，而站點(diǎn)工作負(fù)載均衡在相當(dāng)程度上依賴于系統(tǒng)中數(shù)據(jù)分布.工作負(fù)載的均衡配置關(guān)系到分布式系統(tǒng)的可靠性(負(fù)載差距過大，最大負(fù)載站點(diǎn)可能就是出現(xiàn)故障的短板)和穩(wěn)定性(負(fù)載失衡是導(dǎo)致系統(tǒng)不穩(wěn)定的主要因素之一). 負(fù)載均衡應(yīng)當(dāng)不只是簡(jiǎn)單的數(shù)據(jù)量均分，主要是根據(jù)數(shù)據(jù)本身特征獲取查詢期望的均衡.

數(shù)據(jù)查詢是數(shù)據(jù)處理的基本要求，時(shí)間本身特有性質(zhì)如單向性(單調(diào)遞增)、多維性(有效、事務(wù)和用戶時(shí)間維等)和相互關(guān)系的復(fù)雜性(Allen 時(shí)間關(guān)系［3］)等，使得時(shí)態(tài)數(shù)據(jù)不能按照關(guān)系數(shù)據(jù)模式處理.時(shí)態(tài)索引就成為實(shí)現(xiàn)查詢的基本途徑.據(jù)所掌握資料，現(xiàn)有基于外存時(shí)態(tài)索引主要有關(guān)于版本管理的事務(wù)時(shí)間索引［4－5］、關(guān)于有效時(shí)間的B+樹索引［6］和關(guān)于雙時(shí)態(tài)的R 樹索引［7］等.時(shí)態(tài)數(shù)據(jù)的海量性和共享性適合于分布管理，但現(xiàn)有時(shí)態(tài)索引大都基于單機(jī).本文采用不同于常規(guī)“代數(shù)”框架，引入“關(guān)系”建立基本數(shù)據(jù)結(jié)構(gòu)，提出一種分布時(shí)態(tài)索引技術(shù)DTindex. DTindex 具M(jìn)LPindex 和LPindex 兩 級(jí)索引結(jié)構(gòu)，可根據(jù)情況靈活配置，并按P2P 架構(gòu)進(jìn)行部署. 為有效實(shí)現(xiàn)DTindex，引入了“查詢期望”概念，通過期望均衡實(shí)現(xiàn)工作負(fù)載均衡;同時(shí)，MLPindex 相對(duì)于LPindex 有2個(gè)以上數(shù)量級(jí)的差異，可根據(jù)需要在某個(gè)Slaver 中部署MLPindex 以作為Master，甚至每個(gè)Slaver 中都可同時(shí)部署MLPindex 和LPindex 以減少相應(yīng)通信開銷.

1 時(shí)態(tài)擬序數(shù)據(jù)結(jié)構(gòu)

時(shí)態(tài)數(shù)據(jù)Td 可看作非時(shí)態(tài)數(shù)據(jù)D 與有效時(shí)間期間VT 構(gòu)成的二元組Td = ＜D，VT ＞，VT =［VTs，VTe)，VTs、VTe 分別表示VT 始點(diǎn)和終點(diǎn)(VTs ≤VTe). 設(shè)Γ 是時(shí)間期間集合. ?uΓ，u =［VTs，VTe)，在VTs－VTe 平面上，稱P(u)=(VTs，VTe)為u 對(duì)應(yīng)的(二維)時(shí)間點(diǎn). 設(shè)P0= (min{VTs(P)}，max{VTe(P)})，PΓ. 由P0開始得到P(Γ)深度優(yōu)先序列記為S(Γ).

定義1 (時(shí)態(tài)擬序和線序劃分)設(shè)E 是時(shí)態(tài)數(shù)據(jù)集合，E 上關(guān)系:Td1，Td2E，Td1Td2?VT(Td1)?VT(Td2)，稱“”是E 上滿足自反性和傳遞性的時(shí)態(tài)擬序(temporal quasi-order).時(shí)態(tài)擬序集合Γ 中一個(gè)全序分枝稱為線序分枝(Linear Order Branch，LOB). 設(shè)Σ 是Γ 上LOB 集合，若?LOBi，LOBjLOP，i≠j，LOBi∩LOBj=?，且∪LOB =Γ，稱Σ 是Γ 上一個(gè)線序劃分(linear order partition，LOP)，并記為L(zhǎng)OP(Γ).

算法1 (LOP 構(gòu)建算法)設(shè)有深度優(yōu)先序列S(Γ).

step1 由S (Γ)首元素u0始至ui0S(Γ)，

step2 由ui0始至ui1:VTe(ui1)= VTe(ui0)∧VTs(ui1)=min{VTs(uj)}，其中，ujS(Γ)∧(?ukS(Γ)，VTs(uk)=VTs(uj)∧VTe(uk)＜VTe(uj))

step3 由ui1始，繼續(xù)“step1”和“step2”，直至umS(Γ)，u'mS(Γ)使得VTe(u'm)＜VTe(um)，S(Γ)中由u0至um的子序列即是一個(gè)LOB1.

step4 由S(Γ)LOB1首元素始，繼續(xù)step1～step3，得LOB2，…，直到S(Γ)=?，即得LOP(Γ).

定義2 (基于LOB 時(shí)間數(shù))設(shè)u =［VTs，VTe)LOB，LOBELOP，序號(hào)為no(LOB). u 基于LOB時(shí)間數(shù)(time number，TN)定義為TN(u，LOB)=no(LOB)×102r+VTe ×10r－VTs，其中r 是Γ 中所有時(shí)間期間中“最大”時(shí)間端點(diǎn)數(shù)的“位數(shù)”.

定理1 (時(shí)間數(shù)基本性質(zhì))①在LOB 內(nèi)，u 和TN(u，LOB)之間的對(duì)應(yīng)是1－1 映射. ②?u，vLOB0，u?v?TN(u，LOB)≤TN(v，LOB)，LOB0是給定的序分枝.

證明略.

2 時(shí)態(tài)擬序數(shù)據(jù)結(jié)構(gòu)

設(shè)時(shí)間期間集合Γ 上LOP = ＜LOB1…，LOBi，LOBi+1，…，LOBm＞，vi= max LOBi. 對(duì)于集合{v1，…，vi，vi+1，…，vm}，由在VTs－VTe 平面上最靠“左”的且VTe(vi0)最大的vi0開始構(gòu)建. 在其上再按照“右優(yōu)先”進(jìn)行線序劃分.得到的線序分支集合記為max(LOP)，如圖1 所示.

圖1 “右優(yōu)先”算法Figure 1 Right first algorithm

這樣，在給定Γ 上可建立兩級(jí)數(shù)據(jù)結(jié)構(gòu)，一是Γ 上基于下優(yōu)先的LOP 結(jié)構(gòu);二是LOP 上基于“右優(yōu)先”算法的max(LOP)結(jié)構(gòu).由定理1，LOB 中元素與基于LOB 時(shí)間數(shù)等價(jià)，可使用基于時(shí)間數(shù)的B+樹對(duì)Γ 進(jìn)行索引.

定義3 (時(shí)態(tài)索引DTindex)分布時(shí)態(tài)索引DTindex(Γ)= ＜MLPindex(Γ)，LPindex(Γ)＞. 其中，①LPindex(Γ):基于B+樹關(guān)于LOP 索引，結(jié)點(diǎn)結(jié)構(gòu)＜TN(u)，LOB ＞(uLOB);②MLPindex(Γ):基于B+樹關(guān)于max(LOP)索引，結(jié)點(diǎn)結(jié)構(gòu)＜TN(v)，vs 所在LOB 編號(hào)＞.

基于DTindex 查詢過程如圖2 所示.首先，通過MLPindex 查找可能查找結(jié)果的LOB 編號(hào);再按照LOB 編號(hào)由MLPindex 得到查找結(jié)果而查找結(jié)果是整個(gè)LOB 或LOB 片段.其中，MLOP 是基于max(LOP)的線序劃分.

圖2 基于DTindex(Γ)查詢Figure 2 Queries based on DTindex(Γ)

例1 設(shè)有深度優(yōu)先序列實(shí)例S(Γ)如圖3 所示.

圖3 深度優(yōu)先序列S(Γ)Figure 3 Depth first sequence S(Γ)

此時(shí)，對(duì)于S(Γ)= ＜［1，8)，［1，7)，［1，5)，［3，5)，［3，4)，［2，9)，［2，8)，［2，7)，［2，6)，［4，6)，［4，5)＞，算法1 實(shí)現(xiàn)如圖4 所示，由此得到LOP=(LOB1，LOB2):LOB1= ＜［1，8)，［1，7)，［1，5)，［3，5)，［3，4)＞，LOB2= ＜［2，9)，［2，8)，［2，7)，［2，6)，［4，6)，［4，5)＞. 此時(shí)v1=max(LOB1)=［1，8)，v2=max(LOB2)=［2，9)，由此得到MLOP=(［2，9)，［1，8)).由此構(gòu)建的DTindex(Γ)如圖5所示.

圖4 下優(yōu)先算法實(shí)現(xiàn)Figure 4 The implementation of down first algorithm

圖5 DTindex(Γ)Figure 5 DTindex(Γ)

設(shè)Q0=［2，4)，由MLOP(Γ)得Q0=［2，4)?［2，9)，Q0=［2，4)∩［1，8)≠?，因此得到編號(hào)為1和2 的LOB 都有可能的結(jié)果.進(jìn)入LPindex(Γ)，由(1，(2，5))得結(jié)果＜1，(1，5)＞，＜1，(1，8)＞，＜1，(1，8)＞;由(1，(2，6))得結(jié)果＜2，(2，7)＞，＜2，(2，8)＞，＜2，(2，9)＞. 最終查詢結(jié)果集合為{＜1，(1，5)＞，＜1，(1，8)＞，＜1，(1，8)＞;＜2，(2，7)＞，＜2，(2，8)＞，＜2，(2，9)＞}.

3 DTindex 分布式實(shí)現(xiàn)

3.1 基于查詢期望的數(shù)據(jù)分布

一個(gè)“好”的分布式系統(tǒng)其站點(diǎn)資源通常均衡，均衡的站點(diǎn)資源應(yīng)當(dāng)與均衡的工作負(fù)載相匹配. 數(shù)據(jù)在各個(gè)站點(diǎn)的均衡配置不只是數(shù)據(jù)量平均分割.設(shè)LOP={LOB1，LOB2，…，LOBm}，最小時(shí)間端點(diǎn)為0，最大為MAXT，此時(shí)至多只有S = (MAXT +1)(MAXT+2)/2個(gè)時(shí)間期間.

定義4 (時(shí)間期間的查詢概率)對(duì)Γ 中VT =［VTs，VTe)，所有被包含在VT 中的時(shí)間期間都在如圖6 所示的帶陰影的三角形區(qū)域Δ(VT)內(nèi). 因此，只有當(dāng)查詢期間Q0Δ(VT)時(shí)，VT 是查詢結(jié)果，即Δ(VT)是查詢中VT 所發(fā)揮作用的區(qū)域. 如以Δ(VT)表示其中包含VT個(gè)數(shù)，定義VT 查詢概率為P(VT)=Δ(VT)/S=(VTe－VTs)2/2S.

圖6 時(shí)間期間VT 的的查詢概率Figure 6 The query probability on time period VT

定義5 (線序劃分的數(shù)學(xué)期望)設(shè)隨機(jī)變量X(VT)∶X(VT)=1 如果VT 是查詢結(jié)果;X(VT)=0如果VT 不是查詢結(jié)果. 此時(shí)，X(VT)數(shù)學(xué)期望E(X(VT))= P(VT). 給 定LOB 中 被 查 詢 到個(gè) 數(shù)N(LOB)=Σ X(VTi)，VTiLOB，N(LOB)數(shù)學(xué)期望E(N(LOB))定義為E(N(LOB))=Σ E(X(VTi))=Σ P(VTi).給定LOP，對(duì)其中LOBi計(jì)算E(N(LOBi))，則數(shù)學(xué)期望EN(LOP)定義為EN(LOP)=Σ E(N(LOBi)).

算法2 (基于查詢期望分割算法)將LOP 分配到n個(gè)站點(diǎn).首先，設(shè)有EN(LOP)，計(jì)算站點(diǎn)應(yīng)分配數(shù)據(jù)的數(shù)學(xué)期望δ(EN(LOP)，n)=EN(LOP)/n.其次，設(shè)LOP ={LOB1，LOB2，…，LOBm}，依次對(duì)各站點(diǎn)分配數(shù)據(jù)，當(dāng)?shù)?個(gè)站點(diǎn)分配數(shù)據(jù)的數(shù)學(xué)期望達(dá)到或接近δ(EN(LOP)，n)時(shí)停止，接著第2 站點(diǎn)，…，直至最后.

3.2 基于C/S 部署

設(shè)系統(tǒng)具有n個(gè)站點(diǎn).在C/S 架構(gòu)下按照算法2將LOP(Γ)分割成LOP(Γ1)，…，LOP(Γn)，分別在Slaver1，…，Slavern建立LPindex(Γ1)和LPindex(Γ2);再按照LOP 在Master 機(jī)建立MLPindex(Γ)，輸入查詢Q0后，通過MLPindex(Γ)得到可能的LOB 編號(hào)，由LOP 在Slave1，…，Slaven分布情況，將相應(yīng)LOB編號(hào)和Q0發(fā)送相關(guān)站點(diǎn)Ti.最終，Master 將各個(gè)Ti結(jié)果整合后輸出.作為一種C/S 架構(gòu)，P2P 中每個(gè)站點(diǎn)具信息交換和服務(wù)功能，可作為Master 接收查詢請(qǐng)求分配查詢事務(wù)，也可作為Slave 執(zhí)行應(yīng)用程序.在DTindex 中，MLPindex 和LPindex 數(shù)據(jù)規(guī)模相差2個(gè)數(shù)量級(jí)以上，Master 主要是確定具有能查詢結(jié)果LOB 編號(hào)并將其發(fā)送到相應(yīng)Slaver，同時(shí)整合各Slave 查詢結(jié)果. 將MLPindex 部署到每臺(tái)Slaver，將某網(wǎng)絡(luò)條件較佳Slaver 作為相應(yīng)Master 以減少通信開銷.

本文仿真環(huán)境為3 臺(tái)PC 機(jī)和1 臺(tái)交換機(jī)組成的100 Mbps 的以太網(wǎng).實(shí)驗(yàn)數(shù)據(jù)為隨機(jī)生成1 千萬個(gè)無重復(fù)的時(shí)間區(qū)間，并按照算法1 產(chǎn)生LOB.這些LOB 組成的LOP 按照算法2 被分割為3個(gè)子LOP1、LOP2和LOP3.隨機(jī)生成750個(gè)查詢區(qū)間Q0并將其分為5 組，各組個(gè)數(shù)分別為50，100，150，200，250.3 臺(tái)PC 都運(yùn)行Slaver，裝載LOP1、LOP2和LOP3并部署LPindex，用Slaver1 運(yùn)行Master 并部署MLPindex.系統(tǒng)關(guān)于每組查詢時(shí)間開銷為Master 分配查詢直到輸出結(jié)果花費(fèi)時(shí)間總和，如圖7 所示.

圖7 Master 查詢過程時(shí)間開銷Figure 7 The time overhead of Master

Slaver 時(shí)間開銷為由Master 接收查詢執(zhí)行到返回結(jié)構(gòu)至Master 的通信時(shí)間. 如圖8～圖10 所示，兩輔機(jī)站點(diǎn)工作負(fù)載基本均衡，呈線性增長(zhǎng).

圖8 Slaver1 工作過程的時(shí)間開銷Figure 8 The time overhead of Slaver1

圖9 Slaver2 工作過程的時(shí)間開銷Figure 9 The time overhead of Slaver 2

圖10 Slaver3 工作過程的時(shí)間開銷Figure 10 The time overhead of Slaver 3

3.3 基于P2P 部署策略

P2P 部署的一個(gè)基本問題是在網(wǎng)絡(luò)中如何選取主站點(diǎn)Master.LOB 的基于“查詢期望”是本文索引分布式擴(kuò)展的基本要素，因此也可用來作為Master選取的基本參數(shù).

由每個(gè)站點(diǎn)中存儲(chǔ)的所有LOB 得到該站點(diǎn)的“查詢期望”，選取“查詢期望”值最大的站點(diǎn)作為Master，具體選定過程通過擴(kuò)展“選舉環(huán)”［8］算法實(shí)現(xiàn).

在邏輯上，各個(gè)站點(diǎn)看做是沿環(huán)排列(如圖11 所示).第i個(gè)站點(diǎn)存儲(chǔ)LOB 集合標(biāo)識(shí)為＜EN(LOPi)，i ＞，其中EN(LOPi)為該站點(diǎn)的“查詢期望”.

圖11 選舉環(huán)算法Figure 11 Algorithm of election rings

首先，每個(gè)站點(diǎn)都為“選舉”中非參加者. 隨機(jī)地由一個(gè)或多個(gè)站點(diǎn)開始一次選舉，發(fā)起選舉站點(diǎn)將自身標(biāo)記為參加者，并將標(biāo)識(shí)放入一個(gè)選舉消息發(fā)送至下一個(gè)站點(diǎn).

其次，當(dāng)某個(gè)站點(diǎn)收到選舉消息時(shí)，比較接受標(biāo)識(shí)和自身標(biāo)識(shí).如果到達(dá)的標(biāo)識(shí)較大，就將消息轉(zhuǎn)發(fā)給下一個(gè)站點(diǎn);如果到達(dá)標(biāo)識(shí)較小，自身又非參加者，則把消息里標(biāo)識(shí)替換為自身標(biāo)識(shí)并轉(zhuǎn)發(fā)消息，而當(dāng)自身已是參加者，則不轉(zhuǎn)發(fā)消息，只轉(zhuǎn)發(fā)一個(gè)選舉消息，進(jìn)程把自己標(biāo)記為參加者.如果收到的標(biāo)識(shí)是接受者自己，則該站點(diǎn)標(biāo)識(shí)最大，成為Master. 當(dāng)選進(jìn)程將自己標(biāo)記為非參加者并向下一個(gè)進(jìn)程發(fā)送一個(gè)當(dāng)選消息，將其標(biāo)識(shí)放入消息.

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

4 結(jié)束語

本文提出了基于查詢期望均衡的數(shù)據(jù)分布算法，通過分布式站點(diǎn)的負(fù)載平衡增強(qiáng)系統(tǒng)的穩(wěn)定性與可靠性;另外，研究DTindex 的P2P 部署策略以減少系統(tǒng)通信開銷和提升系統(tǒng)效率. 由于DTindex 具數(shù)學(xué)支撐，看可作為一種時(shí)間數(shù)據(jù)處理框架，適用時(shí)態(tài)對(duì)象、XML 和移動(dòng)對(duì)象數(shù)據(jù)等.DTindex 具增量式更新機(jī)制，可實(shí)現(xiàn)時(shí)間數(shù)據(jù)的動(dòng)態(tài)復(fù)制，相關(guān)課題將另文討論.

［1］孟小峰，周龍?bào)J，王珊.數(shù)據(jù)庫技術(shù)發(fā)展趨勢(shì)［J］.軟件學(xué)報(bào)，2004，15(12):1822－1836.

［2］STEPHANOS A T，SPINLLIS D. A survey of peer to peer content distribution technology［J］. ACM Comput Surv，2004，36(1):315－371.

［3］ALLEN J F. Maintaining knowledge about temporal intervals［J］.Commun ACM，1983，26(11):832－843.

［4］MORO M M，TSOTRAS V J. Transaction-time indexing［R］∥Temporal Database Entries for the Springer Encyclopedia of Database Systems，Time Center Technical Report TR-90，New York:Springer，2008.

［5］LOMET D，HONG M，NEHME R，et al. Transaction time indexing with version compression［J］. Proceedings of the VLDB Endowment，2008，1(1):870－881.

［6］NASCIMENTO M，DUNHAM M.Indexing valid time database via B+-tree:The MAP21 approch［R］∥Technical Report CSE-97-08，Dallas，USA:School of Engineering and Applied Sciences，Southern Methodist University，1997.

［7］BLIUJUTE R，JENSEN C S，SALTENIS S，et al. Lightweight indexing of bitemporal data［C］∥Proceedings of the 12th International Conference on Scientific and Statistical Database Management.Berlin:IEEE Computer Society，2000:125－138.

［8］COULOURIS G，DOLLIMORE J，KINDBERG T. 分布式系統(tǒng)概念與設(shè)計(jì)［M］.3 版. 金蓓弘，譯. 北京:機(jī)械工業(yè)出版社，2004.