首页 体育 教育 财经 社会 娱乐 军事 国内 科技 互联网 房产 国际 女人 汽车 游戏

从物理时钟到逻辑时钟

2019-12-30

一个分布式体系,常常需求面临同一份数据在不同时刻的更改,这个更改或许来自不同节点间数据的同步,也或许来自体系关于客户端写恳求的处理,那么这样的更改就或许呈现抵触问题。而依据事情发作次序的抵触问题的处理,是许多分布式体系,在一致性方面,都有必要要细心考虑和妥善处理的问题。我从前阅读过一些互联网上的资料,但是没有发现哪个能比较体系且简练地把这个问题和处理描绘清楚的,我觉得我或许能够做得更好,所以有了本文。下面我来经过简略的比方介绍这类问题的发作,以及应对的思路。

我来举一个简略比方:

你能够看到,往右的箭头表明在一个分布式体系中,A、B、C 三个节点上,实践时刻消逝的时刻轴。节点 A 在 3:00 的时分给 x 赋值 0,并将赋值事情发送给 C;一分钟后 A 上的另一个事情被触发并发送给 B,并在 3:02 的时分,它进一步发作将 x 赋值为 1 的事情,并发送给 C。很明显这个赋值 x 为 1 的事情实践上是在赋值 x 为 0 的事情之后发作的。

但是呢,因为网络的不稳定等原因,赋值 0 较赋值 1 后同步到节点 C,所以在 C 中 x 的终究值是 0,而不是 1。这明显不是咱们希望的。你或许会说,这儿举的比方十分极点,网络传输一般不会有那么长的耗时,但是,这个形成数据不一致的原理却是相同的。

处理这个问题,最直接的思路明显是选用物理时钟,也便是使用肯定时刻。

这儿选用的办法是,给对 x 的赋值事情,添加一个时刻戳,3:00 的时分,节点 A 发作了赋值为 0 的事情;3:02 的时分,节点 B 发作了赋值为 1 的事情。后者先抵达 C 的时分,赋值事情收效,但是在前者抵达 C 的时分,节点 C 检测到上一次的数据改变时刻戳是 3:02,比后抵达的事情后发作,因而丢掉该赋值事情,这样就确保了终究 C 的数据的终究正确性。

这种方法能够简略称为物理时钟,即分布式体系中所有的节点都遵从相同的时刻,即 “肯定” 时刻,但是不管选用怎样的时刻同步机制,不但要确保时刻同步机制一直收效,还要知道,这样的肯定时刻精度总有上限的。 两次数据改变,距离时刻或许十分小,比方便是来源于附近两行代码的履行罢了,这样的时刻距离,即使是最精细的物理时钟,或许都无法感知。

惋惜的是,据我所知,有一些大厂闻名的分布式存储体系中,仍然在选用这样的方法,但是正如你所见,这样的规划其实便是有问题的。

Leslie Lamport 在他的论文 Time, Clocks, and the Ordering of Events in a Distributed System 中介绍了逻辑时钟的概念。 逻辑时钟和物理时钟最大的差异是,它不再关怀肯定的 “时刻” 是多少,转而关怀事情之间的发作次序,即它们的发作先后这一依靠联系。

Lamport 时钟的规矩很简略,每个节点都保护一个永久递加的 “时刻戳”,为了和前面的物理时刻戳差异,我把它称为版别号,事情的传达有必要带着版别号。每逢有事情发作和发送,版别号就自增 1;假如有事情抵达,假如事情版别号比当时版别号还小就扔掉,不然就接收事情,并更新当时的版别号为当时版别号和事情所带着的版别号二者的最大值。

你看图示,这个进程简略描绘如下:

很快,人们发现 Lamport 时钟也有局限性,且看下面的比方,描绘了单纯使用它的时分呈现的问题:

这个进程如下:

你看,这儿的问题是,实践这个赋值为 0 的事情,要比赋值为 1 的事情 ,从肯定时刻的视点来说,要更早发作,但是终究在 C 上这个值却是 0,也便是说,后发作的赋值事情反而被丢掉了。

但是话说回来,即使咱们能够完成一种机制,处理这个问题,即 抵触的时分让这个肯定时刻较晚发作的改变收效,就必定正确吗?

无妨再回看一下前面的三个图,和这第四个图是有差异的。前面三个图的比方中,赋值事情事情传递链中,依靠联系的源头都在 A 上面,这样这两个源头在 A 上的先后次序是十分明晰的——谁先发作,谁后发作,就好比是两行不同方位的代码,谁先履行都是很清晰的。

但是,这第四个图就不是这样的了,一个赋值事情在 A 上生成,另一个在 B 上,且二者的传递链并没有交集。虽然我画的是分布式体系中的两个物理节点,可即使在同一个节点的不同线程或进程中,这样的状况也是或许发作的。

因而,不给出清晰的使用场景,在缺少事情依靠联系的状况下,究竟应该丢掉哪一个赋值 x 的事情,是很难判别的——即使咱们能够以某种方法知道它们谁先发作。举一个详细的比方,公司只要一个免费旅行的名额,职工小明和小王都别离提出申请,那么究竟谁的恳求被经过?是依据恳求抵达时刻的时刻戳,是恳求发送的时刻戳判别,仍是依据小明和小王谁从前给公司做过的奉献大来判别,这便是使用场景的约束了。有了使用场景,关于这样没有相互依靠联系的事情,咱们才干合理地定出抵触处理的战略。不同的分布式体系中也是这样,有依据不同的规范来处理抵触的,乃至也有直接交给用户来处理抵触的。

可见,不管咱们应该采纳哪一种抵触处理的战略,单纯使用 Lamport 时钟存在这样这样一个局限性:并不能很好地辨认出 “缺少事情发作先后的依靠联系而形成抵触” 的景象。

选用向量时钟的方法时,前面说到的单纯版别号,就会变成一个版别号数组,上面记录了每一个节点当时的版别号:

你看上面的图示,每次版别号改变,都会关于这个版别号向量中相应的那一维自增。当 C 收到事情的时分,依据这个向量版别号的巨细就能够做出应该接收仍是回绝的决议了:

相应地,咱们再来看看前面那个 “抵触辨认” 的比方:

如图所示,在 C 上比较这两个事情的时分,一个事情的向量是 [A:0, B:2, C:0],另一个则是 [A:1, B:0, C:0]。 前者在向量 B 上更大,而后者则在向量 A 上更大,这样的对立就意味着抵触的发作。 已然抵触能够被辨认出来,咱们就能够依据体系的预界说来挑选抵触处理战略了。

最终,就好像任何软件上的处理方案都有两面性相同,向量时钟也不是完美的,比方说,在节点数量巨大的状况下,你能够幻想这个版别号的向量维度会十分高,那么传递一个简略的信息,得带着大得多的版别信息这样的 overhead。

热门文章

随机推荐

推荐文章