给一个EC情况下的copyset容错能力以及scatter width的计算方法。因为看原文中假设的都是副本级别的复制
这里假设EC的方案是fragment = 6, parities = 3. 比如经典的RS(6, 3),这里令R = k + r
那么对于一个copyset来说,他的大小就是9。而任意一个copyset中丢掉的数据如果大于parities的数量,这里是4,就会出现丢数据的现象。
按照copyset的算法,任意一种permutation生成的copyset的数量是 N / R个
如果出现任意的r + 1台机器故障,那么可能导致数据丢失的概率是:
* 故障机器的组合有 C(N, r + 1)
种
* 故障机器同时出现在一个copyset中的概率为 #copyset * C(R, r + 1)
,即N / R * C(R, r + 1)
* 那么丢失数据的概率为:N / R * C(R, r + 1) / C(N, r + 1)
- 对比用副本的方法,概率为
N / R / C(N, R + 1)
假设N = 100的话,出现3个节点宕机的时候,3副本和RS(6, 2)丢失数据的概率为
* 0.004329004329004329
而相同配置下,N = 100,R = 3的时候,出现3个节点宕机,副本复制丢失数据的概率为
* 0.00020614306328592044
用代码写了写,感觉ec的case在故障数量比较多的时候不太好算(组合数学没学明白。。)
这里大概给了个图,可以看出来,都使用了copyset复制的情况下,ec丢失数据的概率更大一些。这是因为EC的copyset更大,而copyset内丢失任意的3个副本就会导致丢数据。
延伸出来的一个结论就是,ec本质的tradeoff并不是牺牲了可用性(即恢复的时候需要做计算),而是把丢失数据的风险摊到了其他节点上。从上面的公式中也可以看出来,EC丢失数据的数量是N / (k + r) * C((k + r), r + 1)
,而副本则是N / R
。在k = 2, r = 1的时候,可以发现他们是相同的,随着r的增大,ec能够容忍的副本丢失的数量也更多,随着k的增大,ec的开销也在降低。在极端情况下,k接近n的时候,整个集群只有一个copyset,那么此时任意丢失 r + 1个节点,都会丢失数据,即相当于没有做copyset复制。
* ec的这种方式比较像是group random replication,丢数据的概率和在一个组内做的随机复制是一样的。
* ec的tradeoff是在用数据持久性换数据副本的开销。这里数据持久性体现在,单个节点宕机的时候,会有更多的数据受到影响。以及上面的copyset replication下,丢失数据的概率会更大一些。
* 这里和copyset replication有关稍微有点奇怪,感觉还应该再想想
* 应该不是copyset replication,而是说,如果在丢失同样的节点数的时候,因为EC的copyset更大,所以丢的节点更容易在同一个copyset下,也就更容易导致丢数据。
* 在random replication下,虽然都会丢数据,副本复制的丢数据的量是1 / C(N, R)
,而EC则是C(N - r - 1, k - 1) / C(N, k + r)
,比如N = 100的时候
* 6.184291898577613e-06
* 0.0003463203463203463
* 说明在随机选择的情况下,ec丢失的数据更多一些。直观感觉就是ec的copyset更大,所以更容易受到影响
* 所以数据丢失概率这块:
* random rep < copyset ec = random group rep < copyset rep
* 所以平常说的ec可以提高数据持久型是相对于随机副本复制来说的
文章评论