分布式系统中的数据同步

许多人在日常工作中都会用到分布式系统，它的好处就是它所提供的稳定性，容错性以及伸缩性使我们能更容易地构建出稳定，高效的应用。然而分布式系统的使用非常具有挑战性，包括数据同步以及理解冲突的意义。

分布式系统中的数据同步本身就是一项非常巨大的挑战。如果光看物理时间戳的话我们无法确定哪个版本的数据才是最新的，因为你无法确保所有的实体的物理时钟都是完美同步的。比如说，两台同步的服务器将时间戳写入到同一个系统中。如果一台服务器慢了哪怕只有几毫秒，很快它就无法得知事件的真实顺序了。为了解决这一问题，我们可以采用基于事件的逻辑时钟而不是真实时间来构建出部分有序的集合。

你可以认为逻辑时钟就是标明系统中的事件的版本的一种方式。通过查看这些有序的集合，我们就能同步系统中的数据，因为我们可以知道哪些数据是最新的，并且可以识别出哪些事件是并发的。

我承认当我第一次听说“向量时钟”或者”Lamport时间戳”这个概念时，我发现它们其实是一些我无法理解的荒唐的数学算法。或许更重要的是，出于恐惧，我在逃避去学习它们。所幸的是，我发现它们其实要比我想像的简单得多。我们来一窥它底层的奥秘并看看它是如何工作的。

Lamport时间戳

Lamport时间戳由Leslie Lamport于21世纪初所发明，是这两者中较简单的一个了。系统中的每个实体都有一个自己的计数器，在处理事件前它会对将该值递增，当它需要和其它实体进行同步的时候也会把这个时间戳带上。再强调一次，这里的时间戳并不是物理时间戳（比如说今天下午1点），而是一些数字，它们只要当和同一系统中的其它时间戳进行比较时才有意义。

假设我们有一个包含三个节点的分布式系统，每个节点都独立地处理事件：



在这个时候，节点1和节点3已经处理了事件A和事件B，并把它们对应的Lamport时间戳增加到了1。但是它们还没有和节点2进行同步，所以我们先继续往下走：



现在节点1和节点3已经同步了，节点1还把自己的时间戳同步了过去，将节点2的时间戳增加到1。我们再往前走一步：



节点3已经处理了2个事件（D和E），并和其它两个节点进行了同步。注意到节点2的Lamport时间戳增加到了3，因为事件E的时间戳已经是3了，所以它直接跳过了2，选择了一个更高的值。

现在我们的节点已经完全同步了，不过这些时间戳能说明什么呢？Lamport证明这个理论的过程“非常深奥”，因此我们这里不会介绍这个算法的细节了，不过我们知道在Lamport的因果关系中，事件B在D之前到达，E发生在F之前，而F发生在G之前。

不幸的是，由于我们没有存储其它节点的状态，因此有些事情我们是无法知道的。比如说，我们无法得知C是在B之前或者之后发生的，或者说它们是并发的。要想知道这些信息，我们得用到向量时钟。

向量时钟

Colin Fidge和Freiedemann Mattern在1988年分别提出了向量时钟的概念，和Lamport时间戳相比，它能提供能详细的信息，也被应用于Riak等系统之中。和Lamport中每个实体分别存储自己的时间戳不同的是，它存储的是时间戳的向量，向量的大小等于系统中实体的数量。每个实体都清楚自己在向量中的位置，以及最后一次同步时它的兄弟节点的时钟。你可以把它看作是这个实体对系统的其它部分的认知的一项记录。

记住，同步事件里面包含发送者的向量时钟。算法通过比较这些时钟，可以更好地确定事件的出现顺序。它会按照下面的规则来比较向量时钟里的每个元素：

如果事件X的所有时间戳都小于或等于事件Y的时间戳，则X事件在Y事件之前发生，它们不是并发的：

如果事件X的所有时间戳都大于或于Y的,那么Y在X之前到来，它们也不是并发的：

如果X的某些时间戳早于Y的，某些又晚于Y，那么这两个事件就认为是并发的，我们无法区分它们的顺序：

了解了这些规则，我们再来看一下前面那个Lamport时间戳的例子，这次我们用的是向量时钟：



使用Lamport时间戳，我们无法确定是否C在B之前发生，但根据向量时钟的最后一条规则，现在我们知道它们实际上是并发的事件。这说明它们是几乎在同一个时间发生的。

向量时钟并非万能的，比如说，他们无法对所有的事件进行排序，因为我们只做到了部分有序——正如前例中的那样，我们只是知道这些事件在同一个时间点发生。因此可以由此检测出并发的写操作，但也正因如此，它们的顺序是无法确定的。

结论

希望现在你能对分布式系统的同步存在的一些独特的挑战能有一个更深入的理解，至少你知道了解决这些问题的一种方式。

在这里更有趣的一点收获就是，你没费多大劲就了解到了你所使用的系统中的最复杂的一部分。当然了，你可能永远也不会自己去写一个向量时钟系统，但这并不重要。重要的是我故意去逃避的那部分难以理解的东西恰恰影响到了我的码农之路。攻克一些难关，深入地理解它们，我相信你一定会学到一些东西的。



原创文章转载请注明出处：

http://it.deepinmind.com


英文原文链接