高級(jí)操作系統(tǒng) 第2章 分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)

第2章分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)褚龍現(xiàn)chulongxian@126.com回顧-自頂向下設(shè)計(jì)DDBS步驟需求分析概念設(shè)計(jì)視圖設(shè)計(jì)分布設(shè)計(jì)物理設(shè)計(jì)觀察與監(jiān)視系統(tǒng)需求全局概念模式訪問模式外部模式定義局部概念模式物理模式用戶輸入視圖集成用戶輸入反饋反饋回顧-數(shù)據(jù)的分片設(shè)計(jì)初級(jí)水平分片原則

若R={R1,R2,…,Rn},則完整性對(duì)于每一個(gè)元組

tR,RiR使得tRi

不相交性對(duì)

tRi,Rj

使得tRj,ij可重構(gòu)性操作是并∪(可忽略,因?yàn)橥暾蕴N(yùn)含)

R=

∪{R1,R2,…,Rn}回顧-數(shù)據(jù)的分片設(shè)計(jì)初級(jí)水平分片原則

P={p1,p2,…,pn}是一簡(jiǎn)單謂詞集合，為保證分片的正確性，P必須是：完整的：同一分片中的任意兩個(gè)元組被應(yīng)用同樣概率訪問。最小的：集合P中的所有謂詞與應(yīng)用密切相關(guān)。具有完整性和最小性不是必要條件,但是對(duì)于簡(jiǎn)化分配問題有好處回顧-數(shù)據(jù)的分片設(shè)計(jì)謂詞的生成過程例：Emp(e#,name,Loc,sal,A,…)找到常用的AP查詢的simplepredicate

（Ai

Value）如:A<10,A>5,Loc=Sa,Loc=Sb生成“小項(xiàng)”謂詞

消除可能出現(xiàn)的無用謂詞數(shù)據(jù)的垂直分片數(shù)據(jù)的分配設(shè)計(jì)12教學(xué)內(nèi)容DATAID-D方法3教學(xué)目標(biāo)難點(diǎn)

掌握數(shù)據(jù)垂直分片的方法重點(diǎn)掌握數(shù)據(jù)分配設(shè)計(jì)的方法理解DATAID-D方法數(shù)據(jù)垂直分片設(shè)計(jì)方法數(shù)據(jù)分片分配的讀寫代價(jià)計(jì)算模型2.2自頂向下設(shè)計(jì)分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)步驟數(shù)據(jù)的分片設(shè)計(jì)水平分片（上次課程）垂直分片數(shù)據(jù)的分配設(shè)計(jì)2.2.2數(shù)據(jù)的分片設(shè)計(jì)垂直分片和垂直群集

垂直分片通過“投影”操作把一個(gè)全局關(guān)系的屬性分成若干組，基本目標(biāo)是將使用頻繁的屬性聚集在一起。全局關(guān)系R={Ri},i=1,2,…,n如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,i≠j，Ap為R的碼或元組標(biāo)識(shí)符，則稱{Ri},(i=1,2,…,n)是關(guān)系R的一個(gè)垂直分片。如果屬性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=（Ap,A-p),i≠j，A-p為R的一個(gè)或多個(gè)非碼屬性時(shí)，稱{Ri},(i=1,2,…,n)是關(guān)系R的一個(gè)垂直群集。2.2.2數(shù)據(jù)的分片設(shè)計(jì)垂直分片/垂直群集例子

EMP(E#,NAME,SAL,TEL,MAGNUM,DEPT)假定Key:E#

主要應(yīng)用:Sa站點(diǎn)查詢NAME,SAL,TEL;

Sb

站點(diǎn)查詢NAME,MAGNUM,DEPT

垂直分片:EMP1(E#,NAME,SAL,TEL)EMP2(E#,MAGNUM,DEPT)垂直群集:EMP1(E#,NAME,SAL,TEL)EMP2(E#,NAME,MAGNUM,DEPT)2.2.2數(shù)據(jù)的分片設(shè)計(jì)垂直分片例子E1EE22.2.2數(shù)據(jù)的分片設(shè)計(jì)垂直分片例子

E1(#,NM,LOC) E2(#,SAL)E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL)?2.2.2數(shù)據(jù)的分片設(shè)計(jì)屬性的親和關(guān)系非鍵屬性

A1,A2,…,An應(yīng)用

Q1,Q2,….,Qmfreq(Qi)=Qi

的訪問頻率說明：從第一個(gè)應(yīng)用到第K個(gè)應(yīng)用，應(yīng)用本身同時(shí)訪問Ai和Aj的頻率之和2.2.2數(shù)據(jù)的分片設(shè)計(jì)屬性和矩陣

行列調(diào)整尋找分割點(diǎn)，同時(shí)調(diào)整0787521A497044845A34757900A5482010050A245105096A1

A3A4A5A2A12.2.2數(shù)據(jù)的分片設(shè)計(jì)屬性和矩陣

7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]

R2[K,A4,A5]2.2.2數(shù)據(jù)的分片設(shè)計(jì)垂直分片算法窮舉屬性親和矩陣的列排列行與列要同時(shí)調(diào)整發(fā)現(xiàn)好的“分割點(diǎn)”極大化每個(gè)分割內(nèi)的親合力（affinity）,極小化跨分割的訪問2.2.2數(shù)據(jù)的分片設(shè)計(jì)分片小結(jié)水平

初級(jí)：

R 根據(jù)

local屬性

導(dǎo)出：

根據(jù)外鍵關(guān)系垂直

R2.2.2數(shù)據(jù)的分片設(shè)計(jì)分片小結(jié)混合分段RR1R2R11R12R21R22水平垂直2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配的概念在滿足用戶需求的前提下,把設(shè)計(jì)好的數(shù)據(jù)片段分配到相應(yīng)的站點(diǎn)上存儲(chǔ)例子:E(#,NM,LOC,SAL)

R1=

loc=SaE;R2=

loc=SbE

Qa:select…whereloc=Sa...

Qb:select…whereloc=Sb…SiteaSiteb

R1,R2存放在哪??2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配方法分配方法非冗余分配設(shè)計(jì)方法最佳適應(yīng)法冗余分配的設(shè)計(jì)方法所有得益站點(diǎn)法附加復(fù)制法應(yīng)用需求確定非復(fù)制問題的解確定一組站點(diǎn)分配副本確定非復(fù)制問題的解從最有益處增加副本到附加復(fù)制無好處為止其他方法2.2.3數(shù)據(jù)的分配設(shè)計(jì)優(yōu)化問題什么是段的最好配置/什么是最好的冗余副本數(shù):極小化查詢響應(yīng)時(shí)間極大化吞吐量極小化“代價(jià)”...約束?有效的存儲(chǔ)空間有效的帶寬,站點(diǎn)處理能力,…保持

90%的響應(yīng)時(shí)間低于

X（如0.5秒）...2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配的簡(jiǎn)化模型單個(gè)片段

F；站點(diǎn)

S1,…Sm

；

變量

X1,…,Xm

0如果

F不在

Sj上存儲(chǔ)

1如果F在Sj上存儲(chǔ)

Totalcost=ReadCost+WriteCost+ StorageCost

確定

Xj

的值,1jm,使總代價(jià)極小。Xj=2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配的簡(jiǎn)化模型讀代價(jià)

Readcost=[tiMINCi,j]i: 讀申請(qǐng)?jiān)凑军c(diǎn)

ti: 站點(diǎn)Si上的讀申請(qǐng)激活次數(shù)

Ci,j:從Si讀Sj站點(diǎn)分段F的代價(jià)

...3ici,3ci,1ci,2

ti

FFF.12i=1mj2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配的簡(jiǎn)化模型寫代價(jià)....iFFFUpdatesui

Writecost=Xj

ui

C’ij

i:寫申請(qǐng)?jiān)凑军c(diǎn)

j:被更新站點(diǎn)

Xj:0ifFnotstoredatSj 1ifFstoredatSj

ui:站點(diǎn)

Si

上更新激活次數(shù)

C’ij:從站點(diǎn)Si

更新

Sj

分段

F的代價(jià)i=1j=1mm2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配的簡(jiǎn)化模型存儲(chǔ)代價(jià)

StoreCost=

Xi

di

Xi:0ifFnotstoredatSi

1ifFstoredatSi

di:

站點(diǎn)

Si

存儲(chǔ)分段

F的代價(jià)i=1m2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配的簡(jiǎn)化模型目標(biāo)函數(shù)min[tiMINCij+Xj

ui

C’ij] +Xidi

i=1j=1i=1mmm2.2.3數(shù)據(jù)的分配設(shè)計(jì)分配方法“最佳適應(yīng)”方法（非冗余分配）

Bij=

k

Fkj

Nk“所有得益站點(diǎn)”方法（冗余分配）

Bij=

k

Fkj

Rki

-c

k

j’jFkj’

Uki

i片段下標(biāo)j站點(diǎn)下標(biāo)

k應(yīng)用下標(biāo)Fkj

應(yīng)用k在站點(diǎn)j上激活的頻率

Rki

應(yīng)用k被激活一次,對(duì)片段i讀的次數(shù)

Uki

應(yīng)用k被激活一次,對(duì)片段i寫的次數(shù)

Nki

應(yīng)用k被激活一次,對(duì)片段i讀寫的總次數(shù)2.2.3數(shù)據(jù)的分配設(shè)計(jì)水平分片分配方法最佳適應(yīng)法將片斷Ri分配到訪問Ri次數(shù)最多的那個(gè)站點(diǎn)上

Bij=

kFkj*Nki

所有得益站點(diǎn)法將片斷Ri的副本分配到所有得益站點(diǎn)j上Bij=

kFkj*Rki

-c*k

j’≠j

Fkj’*Uki如果Bij

＞0，則站點(diǎn)j是得益站點(diǎn)，放置Ri的一個(gè)副本附加復(fù)制法Di表示片斷Ri的冗余度（副本個(gè)數(shù)）,Fi表示Ri在所有站點(diǎn)都復(fù)制的得益

2.2.3數(shù)據(jù)的分配設(shè)計(jì)垂直分片分配方法rs其他站點(diǎn)tRtRRs網(wǎng)絡(luò)A1A2AsAt

A32.2.3數(shù)據(jù)的分配設(shè)計(jì)垂直分片分配方法假設(shè)關(guān)系R垂直分片Rs和Rt,Rs分配到s站點(diǎn),Rt分配到t站點(diǎn).應(yīng)用組As:自站點(diǎn)s發(fā)出,只使用Rs,得益

BAs=

Fks

Nki

(kAs)應(yīng)用組Ar:自站點(diǎn)t發(fā)出,只使用Rt,得益

BAt=

Fkt

Nki

(kAt)應(yīng)用組A1:由站點(diǎn)r發(fā)出,原先使用Rt或Rs(本地),現(xiàn)在要遠(yuǎn)程，損失

BA1=

Fkr

Nki

(kA1)應(yīng)用組A2:由站點(diǎn)r發(fā)出,原先使用R(本地),現(xiàn)在要兩次遠(yuǎn)程，損失

BA2=

Fkr

Nki

(kA2)應(yīng)用組A3:由不同于站點(diǎn)r,s,t的站點(diǎn)發(fā)出,要訪問Rt和Rs,損失

BA1=

Fkj

Nki

(kA3,j≠r,s,t)分配得益

Bist=BAs+BAt-BA1-BA2-BA32.3DATAID-D方法與集中式數(shù)據(jù)庫的異同設(shè)計(jì)步驟分布要求分析階段分布設(shè)計(jì)階段2.3.1與集中式數(shù)據(jù)庫的異同分布式數(shù)據(jù)庫設(shè)計(jì)階段需求分析概念設(shè)計(jì)分布要求設(shè)計(jì)全局邏輯設(shè)計(jì)分布設(shè)計(jì)局部邏輯設(shè)計(jì)局部物理設(shè)計(jì)收集分