分布式系统中的数据同步

jopen 10年前

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

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

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

我承认当我第一次听说“向量时钟”或者”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中每个实体分别存储自己的时间戳不同的是，它存储的是时间戳的向量，向量的大小等于系统中实体的数量。每个实体都清楚自己在向量中的位置，以及最后一次同步时它的兄弟节点的时钟。你可以把它看作是这个实体对系统的其它部分的认知的一项记录。

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