论大型集群中的数据丢失

经常用到的复制套路有三种：数据库保证将每份数据都拷贝到三个不同计算机上的三个独立的磁盘上。这么做的原因很简单：磁盘只会在某个瞬间出现问题，如果一个磁盘挂掉了，你可以是有时间去把它替换掉，然后你仍然可以从你另外两份拷贝中拿出一份来恢复数据并写到新的磁盘上。在你恢复磁盘之前第二个磁盘也挂掉的概率太低了，你的磁盘在同一时刻都挂掉的可能性就如同小行星撞击地球一样微乎其微。

我们还特地进行了计算，一个磁盘坏掉的可能性差不多是0.1%（可能比较粗略），两个磁盘挂掉的可能性差不多是10的-6次方，三个磁盘同时挂掉的可能性大概是10的-9次方，也就是十亿分之一。这个计算表明一个磁盘的出错是独立于其他磁盘的出错的——这不是很准确，举个例子，如果你的磁盘都是从一个生产线上生产出来的，那么它们有可能都是坏的——但是这对于我们的想法来说已经是足够好了的。

迄今为止，这看起来是合乎情理的，但是不幸的是这对于许多数据存储系统都不是正确的。在这篇博客中我将向大家展示下这是为什么。

如果你的数据库集群仅仅包含三个机器，所有机器同时都挂掉的可能性实在太低了（排除相关的错误，比如一个数据中心被毁坏了）。然而一旦你使用了更大的集群，那么问题也相应地会发生变化。你在集群中使用了更多的节点和磁盘，你丢失数据的可能性就会变大。

这是根据计算得来的，你可能会想“真的吗？我已经把数据复制到三个磁盘上了。失败的可能性怎么会根据集群的增大而变高呢。管集群容量什么事？”但是我计算了下可能性，并通过下面的图标来向你讲明原因：

很明显，这不是一个节点失败的可能性——这是永久丢失所有三份拷贝数据的可能性，所以从备份中恢复数据只是保守的方法。你的集群越大，你丢失数据的可能性就越大。这可能是当你考虑为复制数据支付时你可能不会想到的。

图的Y轴有点随意，依赖了很多设想，但是线条的方向是难以置信的。基于之前的设想，在某个时刻一个节点失败的可能性是0.1%，然而图上显示的是，在一个具有8000个节点的集群中，永远失去一份数据的三个拷贝的概率大约是0.2%。是的没错，丢失所有三个拷贝的风险是丢失一个节点的数据的风险的两倍。那么这些拷贝用来做什么呢？

从这幅图上直觉地判断：在一个拥有8000个节点的集群中一些节点在某些时刻宕机的事件是时常发生的。这也许不是一个问题：一定概率的乱象和节点替换是可以推断的，还有一部分是例行的维护。然而，如果你很不幸，你复制的节点数据的目的节点都挂掉了，那么你的数据就永远找不回来了。数据的丢失紧紧是在集群的整体数据集中比较小的部分，但是当你丢失了三份复制，你可能认为“我确实不想丢失这些数据，”而不是“我没想到偶然性地丢失了一些数据，尽管它们不是很大量的。”可能这部分丢失的数据是很重要的一部分数据。

所有三份复制都是坏节点的可能性要依赖于系统采用的复制算法。上图仅仅依赖于数据被分成一定数量的分区（或者叫分片），这样每个分区都存储了三个随机选择的节点（或者叫做伪随机哈希函数）。这是一致性哈希的特例，用在Cassandra和Riak（据我所知）。我不太确定其他系统是怎样分配复制工作的，所以是从那些懂得多存储系统的内部原理的人了解到。

让我使用一个复制数据库的概率模型向你展示我是怎样计算上图的。

假设一个独立节点丢失数据的概率是p=P（节点损失）。我打算忽略在这个模型中的时间，简要看下在某些时间段失败的概率。举个例子，我们可以假设p=0.001是某一天一个节点失败的概率，花费一天时间去替换节点和将丢失数据转储到新的节点上也是合乎情理的。简单来讲，我并不想区分节点失败和磁盘失败，我只会把永久性失败拿来说事儿。

设n为集群的节点数量。f为失败的节点数量（假设失败是相对独立的）是二项分布的：

表达式是f个节点失败的概率，表达式是保证n-f个节点不失败的概率，是按照不同的方式从n中摘出f个节点的数量。读作“n选择f”，它被定义为：

。。。。。。

具体的推导过程这里也就不加详细描述了。基于上面的公式，可以推导出在一个具有n个节点，复制因子是（复制的备份节点数量）的集群丢失一个或更多分区的概率。如果失败的节点数f比复制因子要少，我们可以确信没有数据丢失。然而，我们需要增加所有的可能性，在f位于r和n之间的时候：

这稍微有些冗长，不过我认为它是精确的。如果你让r=3，p=0.001，k=256n，n在3和10000之间，然后你就能得到上面那个图。我写了一些ruby程序去实现这个计算。

我们使用了联合绑定的到一个更简单的猜想结果：

尽管一个分区的失败不是完全独立于其他分区的，这个猜想仍然适用。它好像更加接近实验结果了：在途中，数据丢失概率更像是一条直线，和节点数量是成正比的。猜想表明概率是和数量成正相关的，我们假设了每个节点有固定的256个分区。

在实践中表现怎么样，我不太确定。但是我认为这是一个很有意思的计算敏感现象。我听说过导致具有大型数据库集群的公司徽有真实数据丢失的情况。但是文章和报道中倒不是很常见。如果你现在正在研究这方面的课题，可以给我说下。

计算的结果表明：如果你想减少数据丢失的可能性，你应该减少分区数量，并增加复制因子。使用更多的备份花费更多，所以在考虑大型集群时这一点已经花费很大了。然而，分区数量表明一个有意义的负载均衡处理。Cassandra原来是一个节点一个分区，但是后来变成了每个节点256个分区来应对更好的负载分布和高效的二次平衡。

你需要在这些起真正作用之前找到合理的大型集群，但是上千级别的集群是很多大型公司采用的。所以我很感兴趣听到在这个领域有实操经验的人的讲述。如果10000个节点每天永久丢失数据的概率控制在0.25%以内，那意味着一年有60%的数据都会丢失。

作为一名分布式数据系统的设计者看到了这篇文章之后有什么想法？如果我讲的是对的，设计复制方案时就应该加入更多的考虑。希望这片文章可以提升你对现实的重视。因为3个复制节点确实不是那么的安全。