高级操作系统 第2章 分布式数据库系统设计

第2章分布式数据库系统设计褚龙现chulongxian@126.com回顾-自顶向下设计DDBS步骤需求分析概念设计视图设计分布设计物理设计观察与监视系统需求全局概念模式访问模式外部模式定义局部概念模式物理模式用户输入视图集成用户输入反馈反馈回顾-数据的分片设计初级水平分片原则

若R={R1,R2,…,Rn},则完整性对于每一个元组

tR,RiR使得tRi

不相交性对

tRi,Rj

使得tRj,ij可重构性操作是并∪(可忽略,因为完整性蕴含)

R=

∪{R1,R2,…,Rn}回顾-数据的分片设计初级水平分片原则

P={p1,p2,…,pn}是一简单谓词集合，为保证分片的正确性，P必须是：完整的：同一分片中的任意两个元组被应用同样概率访问。最小的：集合P中的所有谓词与应用密切相关。具有完整性和最小性不是必要条件,但是对于简化分配问题有好处回顾-数据的分片设计谓词的生成过程例：Emp(e#,name,Loc,sal,A,…)找到常用的AP查询的simplepredicate

（Ai

Value）如:A<10,A>5,Loc=Sa,Loc=Sb生成“小项”谓词

消除可能出现的无用谓词数据的垂直分片数据的分配设计12教学内容DATAID-D方法3教学目标难点

掌握数据垂直分片的方法重点掌握数据分配设计的方法理解DATAID-D方法数据垂直分片设计方法数据分片分配的读写代价计算模型2.2自顶向下设计分布式数据库系统设计步骤数据的分片设计水平分片（上次课程）垂直分片数据的分配设计2.2.2数据的分片设计垂直分片和垂直群集

垂直分片通过“投影”操作把一个全局关系的属性分成若干组，基本目标是将使用频繁的属性聚集在一起。全局关系R={Ri},i=1,2,…,n如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,i≠j，Ap为R的码或元组标识符，则称{Ri},(i=1,2,…,n)是关系R的一个垂直分片。如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=（Ap,A-p),i≠j，A-p为R的一个或多个非码属性时，称{Ri},(i=1,2,…,n)是关系R的一个垂直群集。2.2.2数据的分片设计垂直分片/垂直群集例子

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

主要应用:Sa站点查询NAME,SAL,TEL;

Sb

站点查询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数据的分片设计垂直分片例子E1EE22.2.2数据的分片设计垂直分片例子

E1(#,NM,LOC) E2(#,SAL)E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL)?2.2.2数据的分片设计属性的亲和关系非键属性

A1,A2,…,An应用

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

的访问频率说明：从第一个应用到第K个应用，应用本身同时访问Ai和Aj的频率之和2.2.2数据的分片设计属性和矩阵

行列调整寻找分割点，同时调整0787521A497044845A34757900A5482010050A245105096A1

A3A4A5A2A12.2.2数据的分片设计属性和矩阵

7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]

R2[K,A4,A5]2.2.2数据的分片设计垂直分片算法穷举属性亲和矩阵的列排列行与列要同时调整发现好的“分割点”极大化每个分割内的亲合力（affinity）,极小化跨分割的访问2.2.2数据的分片设计分片小结水平

初级：

R 根据

local属性

导出：

根据外键关系垂直

R2.2.2数据的分片设计分片小结混合分段RR1R2R11R12R21R22水平垂直2.2.3数据的分配设计分配的概念在满足用户需求的前提下,把设计好的数据片段分配到相应的站点上存储例子:E(#,NM,LOC,SAL)

R1=

loc=SaE;R2=

loc=SbE

Qa:select…whereloc=Sa...

Qb:select…whereloc=Sb…SiteaSiteb

R1,R2存放在哪??2.2.3数据的分配设计分配方法分配方法非冗余分配设计方法最佳适应法冗余分配的设计方法所有得益站点法附加复制法应用需求确定非复制问题的解确定一组站点分配副本确定非复制问题的解从最有益处增加副本到附加复制无好处为止其他方法2.2.3数据的分配设计优化问题什么是段的最好配置/什么是最好的冗余副本数:极小化查询响应时间极大化吞吐量极小化“代价”...约束?有效的存储空间有效的带宽,站点处理能力,…保持

90%的响应时间低于

X（如0.5秒）...2.2.3数据的分配设计分配的简化模型单个片段

F；站点

S1,…Sm

；

变量

X1,…,Xm

0如果

F不在

Sj上存储

1如果F在Sj上存储

Totalcost=ReadCost+WriteCost+ StorageCost

确定

Xj

的值,1jm,使总代价极小。Xj=2.2.3数据的分配设计分配的简化模型读代价

Readcost=[tiMINCi,j]i: 读申请源站点

ti: 站点Si上的读申请激活次数

Ci,j:从Si读Sj站点分段F的代价

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

ti

FFF.12i=1mj2.2.3数据的分配设计分配的简化模型写代价....iFFFUpdatesui

Writecost=Xj

ui

C’ij

i:写申请源站点

j:被更新站点

Xj:0ifFnotstoredatSj 1ifFstoredatSj

ui:站点

Si

上更新激活次数

C’ij:从站点Si

更新

Sj

分段

F的代价i=1j=1mm2.2.3数据的分配设计分配的简化模型存储代价

StoreCost=

Xi

di

Xi:0ifFnotstoredatSi

1ifFstoredatSi

di:

站点

Si

存储分段

F的代价i=1m2.2.3数据的分配设计分配的简化模型目标函数min[tiMINCij+Xj

ui

C’ij] +Xidi

i=1j=1i=1mmm2.2.3数据的分配设计分配方法“最佳适应”方法（非冗余分配）

Bij=

k

Fkj

Nk“所有得益站点”方法（冗余分配）

Bij=

k

Fkj

Rki

-c

k

j’jFkj’

Uki

i片段下标j站点下标

k应用下标Fkj

应用k在站点j上激活的频率

Rki

应用k被激活一次,对片段i读的次数

Uki

应用k被激活一次,对片段i写的次数

Nki

应用k被激活一次,对片段i读写的总次数2.2.3数据的分配设计水平分片分配方法最佳适应法将片断Ri分配到访问Ri次数最多的那个站点上

Bij=

kFkj*Nki

所有得益站点法将片断Ri的副本分配到所有得益站点j上Bij=

kFkj*Rki

-c*k

j’≠j

Fkj’*Uki如果Bij

＞0，则站点j是得益站点，放置Ri的一个副本附加复制法Di表示片断Ri的冗余度（副本个数）,Fi表示Ri在所有站点都复制的得益

2.2.3数据的分配设计垂直分片分配方法rs其他站点tRtRRs网络A1A2AsAt

A32.2.3数据的分配设计垂直分片分配方法假设关系R垂直分片Rs和Rt,Rs分配到s站点,Rt分配到t站点.应用组As:自站点s发出,只使用Rs,得益

BAs=

Fks

Nki

(kAs)应用组Ar:自站点t发出,只使用Rt,得益

BAt=

Fkt

Nki

(kAt)应用组A1:由站点r发出,原先使用Rt或Rs(本地),现在要远程，损失

BA1=

Fkr

Nki

(kA1)应用组A2:由站点r发出,原先使用R(本地),现在要两次远程，损失

BA2=

Fkr

Nki

(kA2)应用组A3:由不同于站点r,s,t的站点发出,要访问Rt和Rs,损失

BA1=

Fkj

Nki

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

Bist=BAs+BAt-BA1-BA2-BA32.3DATAID-D方法与集中式数据库的异同设计步骤分布要求分析阶段分布设计阶段2.3.1与集中式数据库的异同分布式数据库设计阶段需求分析概念设计分布要求设计全局逻辑设计分布设计局部逻辑设计局部物理设计收集分