许多人在日常工作中都会用到分布式系统,它的好处就是它所提供的稳定性,容错性以及伸缩性使我们能更容易地构建出稳定,高效的应用。然而分布式系统的使用非常具有挑战性,包括数据同步以及理解冲突的意义。
分布式系统中的数据同步本身就是一项非常巨大的挑战。如果光看物理时间戳的话我们无法确定哪个版本的数据才是最新的,因为你无法确保所有的实体的物理时钟都是完美同步的。比如说,两台同步的服务器将时间戳写入到同一个系统中。如果一台服务器慢了哪怕只有几毫秒,很快它就无法得知事件的真实顺序了。为了解决这一问题,我们可以采用基于事件的逻辑时钟而不是真实时间来构建出部分有序的集合。
你可以认为逻辑时钟就是标明系统中的事件的版本的一种方式。通过查看这些有序的集合,我们就能同步系统中的数据,因为我们可以知道哪些数据是最新的,并且可以识别出哪些事件是并发的。
我承认当我第一次听说“向量时钟”或者”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
英文原文链接
分享到:
相关推荐
关于分布式异构数据库数据同步系统的研究PDF版本
#资源达人分享计划#
本课程的内容涉及分布式系统的基本概念、基本原理和基本方法,具体涵盖了分布计算系统的基本概念和体系结构,分布计算系统的进程通信,分布式程序设计语言,命名与保护,分布式同步和互斥机构,死锁问题及其处理技术...
为实现槽波地震数据采集系统中各个采集终端之间及同一采集终端2个通道之间的同步,设计了一种分布式的双通道槽波地震数据同步采集系统。该系统采用弱信号调理电路提高地震信号的信噪比,采用八通道同步采样芯片实现了...
ZooKeeper是一个开源的分布式协调服务框架,它用于管理大型分布式系统中的数据一致性和同步。在分布式环境中,ZooKeeper通过其高效的节点管理、数据同步和分布式锁等功能,为集群提供了稳定可靠的协调服务。 在搭建...
本文介绍了基于SAR ADC的系统和基于sigma-delta (∑-Δ) ADC的分布式数据采集系统同步的传统方法,且探讨了这两种架构之间的区别。我们还将讨论同步多个Σ-Δ ADC时遇到的典型不便。最后,提出一种基于AD7770采样...
分布式数据库同步系统(解决中美异地机房)
无状态分布式系统的高可用问题主要包括处理消息的服务节点可以随机选择、不必处理数据复制和同步的问题、系统容量和高可用能力可以同步提升、服务节点可以随意迁移,不必固定 IP 和存储等。 有状态分布式系统的高...
#资源达人分享计划#
LinkedIn最近发布了一套源无关的分布式数据同步系统Databus。简单说,就是把交易数据同步到各个不同的应用中。一个大的特色是这系统采用pull模式从log中取得数据,以达到对生产系统最小影响。 标签:...
异构数据库数据同步分布式系统毕业论文.doc
#资源达人分享计划#
1.3 分布式系统的定义 1.4 我们的模型 1.5 互连网络 1.6 应用与标准 1.7 范围 1.8 参考资料来源 参考文献 习题 第2章 分布式程序设计语言 2.1 分布式程序设计支持的需求 2.2 并行/分布式程序设计语言概述 ...
.基于_GPS_技术实现分布式数据同步采集系统
#资源达人分享计划#
分布式同步控制是确保分布式系统中各节点协调一致、数据一致性和系统稳定性的重要技术,它确保了各个节点能够协调一致地工作,维护数据的一致性,同时保障整个系统的稳定性。这项技术通过多种机制和算法,实现了节点...
Go Sync提供了一个可供开发人员在应用程序中使用的同步框架。
#资源达人分享计划#
#资源达人分享计划#
分布式数据采集系统中的时钟同步.docx