专题四(二)数据的分片与分配设计.pptVIP

数据片段的位置分配设计 分片设计：水平分片、垂直分片 分配设计：数据片段的位置分配设计 数据片段位置分配的方法 非冗余分配：比较简单。例如：最佳适应法，对每一种分配都进行估算，然后选择最佳的站点。不考虑把一个片段与一个相关片段放在同一站点。 冗余分配：比较复杂。片段有复制，复制的利益随着检索与更新间的比值而增加，因为维护数据的一致性需要将更新传播到所有的副本。有两种方法：所有得益站点法和附加复制法。 冗余分配 所有得益站点法：首先确定非复制问题的解，然后在全部站点中确定一组站点，给这组中的每一个站点分配片段的一个副本，这些站点所得到的好处比付出的费用合算。 附加复制法：首先确定非复制问题的解，然后从最有益处起逐步附加复制的副本，此过程直到所附加复制已没有明显好处时结束。这种方法考虑到随着冗余的增加而收益逐渐减少的情况。一般情况下，当一个片段只有2、3个副本时，系统的得益在增加，但当副本数再增加时，系统的得益就不再明显增加。 数据片段分配的费用和得益估算 假定： i: 表示片段的下标； j: 站点的下标； k: 表示应用的下标； Fkj:表示应用k在站点j上被激活的频率； Rki:表示应用k被激活一次对片段i进行检索访问的次数； Uki:表示应用k被激活一次对片段i进行更新访问的次数； Nki=Rki+Uki:表示应用k被激活一次对片段i进行访问的总次数； 非冗余分配使用最佳适应法 非冗余分配使用最佳适应法：将片段i分配到访问i次数最多的那个站点上。在站点j上访问片段i的本地访问次数为： Bij=Σk ( Fkj * Nki) 片段i分配在Bij最大的那个站点上。 冗余分配使用所有得益站点法 冗余分配使用所有得益站点法：将片段i分配到所有得益站点j上。所有得益是指这样一些站点，本地应用的检索访问次数总比从任何一个其他站点发出的应用对片段i进行更新的访问的损失要多。估算差额： Bij=Σk ( Fkj * Rki) - c* Σk Σj’j ( Fkj’ * Uki) 其中c是度量更新访问费用与检索访问费用之比的一个常数，c=0。 如果Bij0,则站点j 为得益站点，将存放片段i的一个副本 冗余分配使用附加复制法 举例(p51)： 网络上的站点：r,s,t,以及其它站点； 将站点r上的关系R垂直分成两个片段Rs和Rt，并将它们分别分配在站点s和t上。 站点r上运行应用组A1,A2；站点s上运行应用组As；站点t上运行应用组At；其他站点运行应用组A3； 应用组As: 自站点s发出，只使用Rs,是本地应用，得益： BAs=Σk ( Fks * Nki) (k属于As) 应用组At: 自站点t发出，只使用Rt,是本地应用，得益： BAt=Σk ( Fkt * Nki) (k属于At) 应用组A1: 自站点r发出，使用Rs或Rt,需要进行远程访问，损失： BA1=Σk ( Fkt * Nki) (k属于A1) 应用组A2: 自站点r发出，使用R,需要进行远程访问，损失： BA2=Σk ( Fkt * Nki) (k属于A2) 应用组A3: 位于其他站点上，使用R,需要进行远程访问，损失： BA3= Σ Σk ( Fkj * Nki) (k属于A3, jr,s,t) 系统的得益公式： BAist =BAs+BAt-BA1-BA2-BA3 为了区分检索和更新访问之间的费用差别，用(Rki+C*Uki)代替Nki * * 令Di表示片段i的冗余度（副本的个数），Fi表示片段i在每个站点全部复制的得益， Di与Fi存在如下关系： β（Di ） = (1-2**(1-Di))*Fi 可以看出： β（1）=0 ； β（1）=Fi/2 ；β（3）=3Fi/4 ； 估算站点j引入新副本i的得益： Bij=Σk ( Fkj * Rki) - c* Σk Σj’j ( Fkj’ * Uki) + β（Di ）