数据片分配的一般原则

2023-10-28 理论教育版权反馈

【摘要】：在确定数据片分配时，有两种截然不同的方式，非冗余分配方式与冗余分配方式。需要指出的是，这里忽略了放置数据片后它们之间的相互影响。确定一个节点集合，并在这些节点上为每个数据片分配一个最佳版本。注意，这只是一种贪心的算法，从而忽略了“相互”效应，即增加一个副本，但对原来分配的影响我们没有考虑，因此最后的结果不见得是最佳的。

在确定数据片分配时，有两种截然不同的方式，非冗余分配方式与冗余分配方式。

相对而言，确定非冗余分配方式要简单些。即采用择优（best-fit）方法，这时列出所有可能的分配方案，选择其中最佳的一种方案。需要指出的是，这里忽略了放置数据片后它们之间的相互影响。

注意，副本的存在增加了复杂性，原因如下。

（1）每个分片的副本数成了问题的变数。

（2）选择合适的读应用模式，由于有各种选择余地，因此更复杂了。

为了确定数据片的冗余分配，可以选择如下方式。

（1）确定一个节点集合，并在这些节点上为每个数据片分配一个最佳版本。这个集合（或方法）称为全部最佳节点（all beneficial sites）。

（2）一旦解决了非冗余分配问题，就可以着手解决冗余副本分配问题。可以逐步增加副本数，并给它们分配节点，选择所有可能在节点中受益-开销差最大（必须大于0）的节点分配一个副本，直到不再存在有益的附加副本节点为止。

注意，这只是一种贪心的算法，从而忽略了“相互”效应，即增加一个副本，但对原来分配的影响我们没有考虑，因此最后的结果不见得是最佳的。所以，期待大家继续研究。

下面进行定量分析。为了进行定量分析，需要定义一些参数，这些参数有数据片分布，以及分布式数据库的节点标识、应用情况等。(www.chuimin.cn)

上面讨论的是一个全局关系R，下面是一些涉及设计的参数。

●i是数据片的编号。