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

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