逻辑时钟的概念让区块链和其他分布式系统有序起来
“时间“是岁月更迭中的永恒话题。围绕时间的探讨一直在区块链以及其他分布式系统中进行。时间连接起进程与节点,我们也用时间的“粒”度来衡量连块成链的去中心化网络。
分布式系统中关于时间的难题在于,不同参与者的“物理时钟”很难达成完全一致。分布式系统大师Lamport提供了去中心化的方法,将问题转化为时间与顺序的联系,提出了逻辑时钟的概念,就像为包括区块链在内的分布式系统引入了“生物钟”。
stakefish编译休假分析师,存在开发者Eigenmann院长的一篇文章,金银行情介绍Lamport关于时间,时钟和顺序的论述,为大家提示理解区块链和分布式系统时间另一个角度。
关于分布式系统的系列文章,用哪个话题开篇比较合适呢?以太坊的隐私交易协议阿兹特克?以难以掌握著称的Paxos算法?这些话题还是留在以后写。今天,我选了一个基础话题作为开篇:分布式系统的时间话题。
本文解读的是图灵奖得主,计算机大师Leslie Lamport的知名论文《分布式系统内的时间,时钟和事件顺序(时间、时钟和事件的顺序在一个分布式系统)》。很久之后重读这篇文章并提炼关键概念,另有一番趣味。
不熟悉Leslie Lamport的朋友可以大概了解一下,他以创造乳胶,TLA + Paxos而闻名,还论述了拜占庭将军问题。当然还有Lamport时钟(第一个逻辑时钟),在本文中我们也将对其基本概念进行介绍。
先来看看分布式系统的定义.Lamport给出的定义是这样的:
“如果一个系统内信息传递的延迟,与单一进程里的事件间隔的时间相比是不能忽略不计的,则称之为分布式系统。”
我喜欢这个定义,因为其专注在发出和收取消息之间的延迟上。
明确了定义,我们开始正式介绍。
顺序
为事件排序在本地再简单不过了。你只需在发生的时候为每一个事件赋予一个时间戳就好了。我们能够获得所有事件的总体顺序,也就意味着,所有事件都能够按照特定顺序排列。
但这个问题在分布式系统的情境下就困难多了。为什么呢?
一切皆因分布式系统的一个非常简单的性质:在节点之间传递的消息在发出之后,在未来的任何时间点都可能到达0次,1次或多次。这样的话,分布式系统的各个节点之间就不能就时间达成一致。举例来说:
一个节点可以向另一个节点发送一条消息标注当前时间是12:00:00,但是接收者不知道消息用了多长时间传递,也就没办法确认到达时是否仍为12:00:00。如果这样,节点之间来来回回传一整天消息也无法确定信息是否同步。如果不能在时间上达成一致,我们也就不能在事件顺序上达成共识
那怎么解决这个问题吗?
在分布式系统内,多个节点通过互相发送信息进行交流。节点收到信息首先确认这个信息,然后执行他的下一个事件。这样的顺序,本来就显示了一种“因果关系”:信息必须先被发出,才能被收的到。
译注:这种因果关系是一种时序关系,不是逻辑上的原因和结果的关系。
那么根据因果关系就能得出顺序:发消息肯定在被他被接收之前。单看A, B两个事件,我们就能给出“发生在……之前(之前)”的关系来描述顺序了。
现在,无需系统物理时间概念就可以识别这种关系:如果A对B造成了因果影响,事件一个肯定发生在事件B之前。因果关系让我们确定系统中相关事件的顺序,是一种偏序(偏序)。
偏序也有一个局限性:如果不能确定相关性,我们可能不知道系统中每个事件的确切顺序。因为可能有许多事件会在整个系统内并发(concorrent),并非所有节点都知道这些事件的发生。
时钟
不过既然我们已经有了偏序,接下来把时钟添加到系统中,就能获取系统中的所有事件的总序(总订单)。
刚才我们已经知道了在分布式系统里使用物理时钟是不可行的,那么我们就需要使用逻辑时钟。逻辑时钟本质上是一个函数,能够给事件分配一个数字。这个数字表示事件发生的时间(从现在开始我们将把这个数字称为时间),与物理时间没有任何关系。
我们假设在这个分布式系统里的每个节点都有一个时钟。这个时钟随着在执行的事件间滴答行进,但时钟的行进并不被视为系统中的事件。对于系统中某个节点上发生的每个事件,逻辑时钟都会为该事件分配一个数字。根据这个假设,我们可以满足以下时钟条件:
∀a、b a→b⟹C (a) < C (b)
以上表达式代表什么意思呢?
箭头”→“表示“发生在……之前(发生过)”,而C代表时钟函数,可简单的理解为时间,所以要表达意思就是:对于每一个事件a, b,如果一个发生在b之前,那么一个的时间要小于b的时间。
但反推不成立,仅因为一个事件的时间比另一个事件的时间小,
99金银并不能说这个事件发生在前,他们可以是并发的。
在上面的图片中,我们可以看到节点α上,时间1和时间2各发生了1个事件;节点β在自己的时间1发生了1个事件。在节点α的时间1和时间2发生的事件,与在节点β的时间1发生的事件是并发的,没有因果联系。
如果a和b是单个节点上的两个事件,且一个发生在b之前,则一个的时间应该小于b的时间。
如果一个是一个发送消息的节点,b是另一收到消息的节点,那么一个的时间仍然应该小于b的时间。
节点需要在事件之间让时钟进行计时。如果不是,则必须将时钟调快到比从其他节点接收到的任何消息中包含的时间更晚的时间。b就可以在时钟调快之后发生了。
现在好啦,我们可以使用满足这些条件的时钟,建立整个分布式系统的总序啦,这里只是简单的根据各个事件的时钟给出的时间来排的序。
用例
最后我们设置一个状态机来看看逻辑时钟的用法。比如我们有一个分布式系统,多个节点都想访问其中的共享资源,每次只能访问一个节点。状态机需要满足以下条件:
条件1:可以访问资源的节点必须先释放资源,然后其他节点才能访问他。
条件2:对资源的请求必须按照发出请求的顺序被授予访问权。
第三条件:如果每个被授予访问权的节点最终都释放了资源,那么每个请求最终都会被授权。
为什么不引入一个中间协调者呢?因为这样的话,如果发生较早的请求却较晚到达,就不能满足条件2了;另一个原因是,我们希望采取去中心化的解决方案。
所以我们还是要构建条件,满足这个逻辑时钟。如何满足条件呢?
Lamport为我们提供了一个去中心化解决方案。首先,我们要让所有节点储存一个请求队列。其次,要满足一些简单的假设:
假设1:所有消息都按发送的顺序接收。
假设2:所有消息最终都被接收。
假设3:每个节点都可以直接向系统中的所有其他节点发送消息。
如果有更复杂的算法和协议,可以忽略以上假设。
现在我们可以定义满足这3个条件的算法,并在实践中展示时钟的功能:
1,如果一个节点想要请求一个资源,他会用当前时间创建一个请求,将他添加到他的队列中,并将他发送给其他每个节点。
2,所有其他节点将这个请求放入他们的队列中并发回响应消息。
3、释放资源的节点发送带有当前时间的释放消息,并从其队列中删除原来的请求。
4,当节点收到释放的消息时,他将从自己的队列中清除相关请求。
5、当一个节点在他的队列中有自己的排在任何其他请求之前请求时(按照时间总序),他可以自由地访问该资源,并且他在该时间之后从所有其他节点接收到消息。
上述算法是完全由各个节点独立执行的去中心化算法,他利用时钟来对请求按总序进行排序,从而实现对资源的访问和节点间的协调。
好啦,我们通过文章大概了解到如何使用这些逻辑时钟对分布式系统中的事件进行排序,并分析了分布式系统访问资源时确定顺序的实际应用问题。欢迎大家的意见反馈,我将继续更新更多关于分布式系统的文章。