副本放置算法

1、raft协议原理

raft

2、单个shard的复制

raft-single
3、Raft group组

raft-group
在一定情况下，copyset的数量不是越多越好，在恢复时间确定的情况下，找到合适的copyset的数量可以降低数据丢失的概率。为了提高存储系统数据可靠性，首先在系统允许的成本范围内选择合适的副本数，再次在系统设计中我们首先优先考虑加快数据恢复时间，在此基础上减小系统的copyset数量。使得在既定的成本下达到尽可能高的可靠性。参考论文《Copysets:Reducing the Frequency of Data Loss in Cloud Storage》，该论文中的实验数据显示，在facebook HDFS集群上作实验，为了有效降低数据丢失概率，数据放置算法，从原来的Random Replicaiton更改为copyset Replication 算法，实验结果说明可 将FaceBook HDFS集群1%节点故障时的数据丢失概率从22.8%降低道0.78%。
在大型集群中，多个节点的同时丢失具有很高的数据丢失概率。例如，考虑使用副本数为3的100个节点的群集，其shard数范围约为10k。同时丢失2个或更多节点具有很高的数据丢失概率，因为可能存在10k shard之外的shard，而该shard在2个丢失的节点上具有3个副本中的2个。在存在多节点故障的情况下，copyset算法可以显着降低了数据丢失的可能性。
根据系统节点数，和副本数量，进行多个轮次的计算，每一轮次把所有节点按照副本数划分为 N／R 个copyset。每次确保其中的copyset 不与当前和之前所有轮次中已经产生的copyset相同，最后数据写入的时候，选择一个copyset 写入即可。 由于每个排列会吧S(Scatter Width) 增加R-1,所以 算法执行P = S/（R-1） 次， K(CopySet数量) = P (N/R) = S/(R-1) (N/R)。
复制集将群集分为不相交的节点集。每组的大小将基于使用的副本数。为每个副本创建单独的副本集。shard应该更喜欢在副本集中分配其副本，而不是在副本集中散布其副本。

所以有两个主要组成部分：

1.管理副本集（哪个节点属于哪个副本集）
副本集分配应考虑节点的位置，以便不会丢失位置容错能力。将节点分配给副本集时，应考虑添加/删除/损坏的节点。
2.重新平衡范围中的所有副本，以尽最大努力将其驻留在单个副本集中。
将副本重新平衡到副本集很重要，但是某些属性（如用户设置的约束）应优先于副本集。
副本集最初将是一个选择加入功能（基于群集设置），并且实现为分散宽度为replication_factor - 1。

管理副本集

该集群将被分为多个副本集。对于群集中的每个副本，将生成单独的副本集。

副本的副本集的要求是

1.对于rf -1的散布宽度，副本集之间的节点应该没有重叠，并且对于散布宽度> = rf（其中rf是复制因子），应使重叠节点最小化。
2.副本集应具有本地容错能力
3.副本集应重新平衡节点的添加/删除/故障。
为系统中使用的每个副本生成副本集。如果对齐了不同副本的副本集，则可以提供更好的容错能力。
副本分配策略采用最佳副本集分割分配算法。

特定的副本的副本集的最佳分配可以如下进行：

1.计算 num_copysets = floor(num_stores/replication_factor)
2.基于机架等特定配置进行存储排序
3.分配副本集到存储，采用轮询调度方案（Round-robin）
例如，有如下存储情况：
Rack1：S1 S2 S3
Rack2: S4 S5 S6
Rack3: S7 S8 S9 S10
复制因子是3的副本集将创建：
num_copysets = 10/3 = 3
CS1: S1 S4 S7 S10
CS2: S2 S5 S8
CS3: S3 S6 S9
Swap
在源副本集和目标副本集之间进行交换，以确保源副本集的多样性增加，而目标副本集的多样性确实减少（或者如果减少，它仍然>复制因子）。

基于源副本集和目标副本集中存在的位置，在源副本集和目标副本集之间进行存储交换。交换所需的条件是：

1.源副本集的多样性<复制因子。这意味着源副本集在特定位置具有两个存储。这些付出之一将是源交换候选者。
2.目标副本集具有源副本集中不存在的局部性（我们称此目标局部性）。来自该地区的商店将成为目标交换候选人。
3.以下之一是正确的
4.目标副本集中不存在源交换候选的位置。

目标副本集

1.在目标位置有两个存储。
2.具有多样性>复制因子。
上面的多样性是指副本集中的位置数量。
上面的要点3确保目标副本集的多样性不会减少（或者如果减少，它就不会低于复制因子）。
进行交换的单个迭代会考虑所有(n choose 2)副本集组合，其中副本集n的数量为。这些迭代将继续进行，直到无法进一步改善所有副本集的多样性之和为止（整个迭代都没有找到交换对象）。
例如，考虑以下我们拥有存储的情况：
Rack1: S1 S2 S3
Rack2: S4 S5 S6
Rack3: S7 S8 S9
Rack4: S10 S11 S12 S13
最初副本集的分配：
CS1: S1 S5 S9
CS2: S2 S6 S10
CS3: S3 S7 S11
CS4: S4 S8 S12 S13
如果存储S6被删除，步骤2之后（将存储分配到相同的副本集ID，直到大小达到rf），我们有了
CS1: S1 S5 S9
CS2: S2 S10
CS3: S3 S7 S11
CS4: S4 S8 S12
再通过添加剩余存储来填充空白点之后
CS1: S1 S5 S9
CS2: S2 S10 S13
CS3: S3 S7 S11
CS4: S4 S8 S12
交换之后（由于CS1和CS2之中CS2有两个存储来自与rack4）
CS1: S1 S5 S13
CS2: S2 S10 S9
CS3: S3 S7 S11
CS4: S4 S8 S12
这种交换策略可能无法实现最佳的多样性，但会尝试确保副本集中的每个位置都不同。

副本集重新生成

考虑用于副本集分配的存储列表将是当前的实时存储。实时存储的计算方式与分配器检测实时存储的方式相同（但不会排除受限制的存储。）如果存储列表稳定且未更改3个心跳数（每个心跳声都有），则会重新生成副本集。间隔10秒）。
副本集分配可以作为原型保留在分布式存储层中。最小化数据移动的副本集策略要求保留副本集（它要求先前的状态为全局状态并在重新启动后仍然有效）。群集中最低的活动节点ID将是管理（持久）副本集。其他节点将定期（每10s）缓存持久化的副本集，并将其用于重新平衡。
仅当存储列表更改时，副本集才会重新生成（并保留）。在稳定状态下，所有节点将定期读取持久化的副本集，而无需重新生成并持久化新的副本集。
对于RF = 3，群集可以容忍每个副本集中一个节点的故障。例如，在最佳情况下（对于RF = 3），一个100个节点的群集可以承受33个节点的同时故障，而不会造成任何数据丢失。

重平衡范围

范围需要重新平衡以包含在副本集中。
HUBBLE目前使用两种范围再平衡器：
1.复制对略
2.存储池管理器

对于平衡使用评分功能：

1.确定范围内要用于新副本的存储
2.当范围超过所需副本数时要删除的副本
3.副本必须从一个存储移动到另一个存储，该范围的结果得分将更高

计分功能考虑一下因素（按优先级顺序排列）：

1.区域约束：在某些区域中具有某些表的约束
2.磁盘已满：检查存储是否太满
3.多样性分数差异：多样性分数与该范围内存在的副本数所处机架的数量成正比。它基于地点的nC2多样性分数，其中n是副本的数量。
4.收敛分数差异：收敛分数用于避免移动shard，移动shard的移动会导致shard的统计信息偏离全局平均值。
5.平衡分数差异：平衡分数是节点的标准化利用率，当前它考虑范围的数量，平衡分数较低的节点是首选。
6.范围计数差异：范围计数较低的存储是首选。

副本集分数

为了将shard重新平衡到副本集中，新的副本评分将添加到分配器中。区域约束和磁盘填充比副本集得分具有更高的优先级。
由于副本集分配考虑了多样性，因此可以将其优先级置于多样性得分之上。
如果满足一下条件，则该副本集得分较高：
1.Shard完全包含在副本集中
2.Shard所在的副本集未得到充分利用。我们希望每个副本集均被加载。如果shard在拷贝集中完全包含x我们应该完全移动到副本集y中。如果副本集y的节点有更低的负载，更多的可用磁盘空间等情况。

以上为副本机制，「分布式技术专题」是国产数据库hubble团队精心整编，专题会持续更新，欢迎大家保持关注。