Copysets: Reducing the Frequency of Data Loss in Cloud Storage
0x00 问题
这篇Paper很有意思，这里提到的问题解决起来不是很复杂的问题，但是能发现这个问题倒是需要一些灵感。在大型的分布式存储系统中，一般有很多的node，数据以多副本的方式保存。如果这些副本是从node中随机寻去的若干个，比如3个，那么在1%的节点故障的情况下，有数据丢失的可能性是多少呢。这里在加上机器是同时故障的情况下(如果没有及时发现故障数据的情况下，其实也和同时故障差别不大了)，如果有5000个节点，则有数据丢失的可能性接近了100%，
With this scheme, we will only lose data if all the nodes in a copyset fail simultaneously. For example, with 5000 nodes, this reduces the data loss probabilities when 1% of the nodes fail simultaneously from 99.99% to 0.15%.
Copysets引入了几个概念，N表示node数量，R表示一个数据的副本数量，S表示副本会在S个节点中随机选取。比如在R = 3, N = 9 and S = 4，数据的第一个副本放到node 1，则剩余的副本可能放到2，3，4，or 5。这样可以创建54个不同的copysets，故障3个的情况下，丢失数据的可能性是, \(\\ \frac{\# copysets}{(_R^N)} = \frac{54}{(_3^9)} = 0.64\) 如果用随机放置的方法，很容易用概率的方法计算，假如数据足够多， \(p = \frac{(_R^N)}{(_F^N)}\) 分母为故障F个node的可能组合，分子为Copyset的数量。如果F = R，则会发现其是p = 1。这里F大欲等于1才有意义。当然这里要求数据足够多，每个可能的copyset都有数据。如果没有这么多数据的话，如果每个份数据都是独立分布的话，分子应该是数据对象的数量。如果多份数据组成group，则可以认为是这个group的数量。另外常见的数据分布的情况下，会考虑避免在同一个机架，变化的值有可能的copyset数量。如果机架数量J大于副本数据R，则有下列式子。即先随机选择机架，然后在机架中选择保存到哪里， \(\# copysets = (_R^J)\cdot(_1^{(N/J)})\) 用数据去模拟的话，可能发现向HDFS这样的系统，随机选择的话，很小部分的机器数据丢失就可能造成很大概率的整个系统有数据丢失。
0x01 思路
这里提出的思路称之为Copysets Replication。基本思路如下，
- 算法分为两个阶段，第一个是permutation阶段。创建node的随机排列，即permutations。排列的数量P=S/(R-1)，向上取整。每个排列分为R组，每组为一个copyset。这个permutation生产的时候添加一些限制条件，比如不能让一个机架下面的，or 网络等方面限制的在同一个copyset里面。
- 随机选择一个node保存第一个副本，其它的副本放到和这个node在一个copyset中的其它节点上。有这个node的copyset数量和P的数量一致。
P不能太大，也不能太小。太大会造成丢失数据风险增大，太小有可能会造成一些不均衡，访问同一个copyset数据带宽等收到限制等。
0x02 评估
这里的具体信息可以参看[1].
Tiered Replication: A Cost-effective Alternative to Full Cluster Geo-replication
0x10 问题&思路
Tiered Replication是前面的Copysets Replication的进化，它主要优化的问题是Copysets Replication对灵活性不足的问题。其基本的算法如下：
- Tiered Replication是一个节点的在多少个copyset里面的意思，称之为scatter width。这个初始化的时候都为0，set为空。循环操作，知道每个节点的scatter width都不小于S为止：对于集群中node的scatter width不足的节点，根据scatter width排序之后，选择最小的几个加进去（这个要考虑其他的限制条件），形成其它的新的copyset。
算法整体上也很简单，而且后面添加 or 删除node的时候：添加可以继续根据上面的算法创建copyset，删除的话删除copyset即可。
0x11 评估
这里的具体信息可以参看[2].
参考
- Copysets: Reducing the Frequency of Data Loss in Cloud Storage, ATC ‘13.
- Tiered Replication: A Cost-effective Alternative to Full Cluster Geo-replication, ATC ‘15.
