分布式系统-时间以及全局状态
What is Time
什么是时间呢？在我们日常生活中时时刻刻离不开的就是时间这一个概念。但实际上，时间就是帮助人们理清事物发生顺序和先后关系的一个标记，有了时间，我们就知道谁先发生、谁后发生。谁对谁产生了影响。我们可以知道此时该干什么事，知道之前吃饭到这次吃饭间隔了多久等等。可以发现，时间和事件发生顺序有紧密的联系。时间本质没有意义，只有我们将某个时间节点赋予了事件，这一串数字才会真正起到它标识的作用。
这篇博客总结的时间具有两个特征：
- 在同一个参考系中事件发生的先后次序是确定的，可以判定事件的因果关系；
- 在不同参考系中事件发生的先后次序是不确定的，不一定能判定事件的因果关系。
不同参考系中无法判定事件的因果关系是因为不像同一参考系，拥有当前的“世界全局信息”。在我们的正常世界中，事件发生时具有因果关系的。比如，妈妈在12.00开始做饭，我12.30吃到了饭，这两个事件是具有因果关系的，必须妈妈先做饭，我才有饭吃。假如此时爸爸在出差的动车上，信号很不好。妈妈开始做饭的时候给爸爸发送了一个微信“我在给儿子做饭”。而儿子在12.30吃饭的时候给爸爸发送了一个“我在吃饭”的消息。由于某些原因，12.30爸爸的手机收到了儿子的消息。而过了十分钟才收到妈妈的消息。在爸爸这个视角（参考系）来看，就出现了儿子吃了饭，妈妈才做饭的因果矛盾。虽然发生的概率很小，但在分布式系统中，却常常发生这样的问题。
上面的场景，是因为对于爸爸妈妈和儿子而言，他们都处于北京时间这一个共同的物理时钟下面。所以就产生了由于通信时延产生的因果矛盾。我们为了方便讨论，可以抽象成三个进程之间的通信。进程A发送了一条消息给进程B和进程C，进程B收到消息则给进程C发送消息，但由于网络原因，进程B的消息先到达了C，而过了一段时间，A发送的消息才被C收到。在C看来，就是B先发生，A后发生。但实际的逻辑是A先发生才导致了B发生。这就是因果不一致。
Lamport Timestamp
那么怎么解决这个问题呢？在解决问题前，有一个重要的概念需要理解，happened-before。他定义了如果事件
同时如果
如果
Lamport提出，对于两个不需要交互的进程而言，不需要时钟同步。只有需要交互的时候才需要，确保事件发生顺序达成一致即可。就像你什么时候吃饭吃了什么，别人根本不需要关心一样。只有你给你爸爸发消息的时候，确保你爸爸先收到妈妈的消息或者仅仅收到你的消息即可。
算法的思想是：
每个进程自身维护一个timestamp。
发送端：每次发生一个事件都自增1。发送消息时，把增加后的timestamp也发过去。
接受端：每次接收到别的进程的消息时，对比本地的timestamp和发过来的timestamp，取最大值，再增加1。如果接收到的消息的timestamp小于本地的timestamp，则忽略此消息。
有了timestamp的加持，进程C如果先收到B的消息，本地的timestamp会与B的timestamp比较，替换成B的timestamp。因为A发消息的时候的timestamp是1，B接收到的时候自增了1，所以B是2，发给C的也是2。如果一段时间后A达到了C，C看到本地的timestamp（2）大于A的timestamp（1），就会选择忽略A的消息。
问题得到了解决。
但此时，又出现了一个问题。如果A第一次发送事件之后，本地发生了一个事件，此时本地的timestamp会增加到2，然后又发生了一个事件，timestamp增加到3。B收到A的消息之后，timestamp刷新为2，然后朝A发送一个消息（此时timestamp会增加到3）。这时，A作为接受端，会发现本地的和接受的timestamp都一样，我们的算法没有处理这个问题。
Vector Timstamp
向量时钟可以解决这种并发条件下的问题。
有ABC，三个进程。每个都维护一个长度为3的初始值为0的向量。当A给B和C发消息时，本地的vector刷新程[1,0,0]。A继续做自己的两个操作，本地vector因此刷新到了[3,0,0]。B接受到A的消息，会对比自己的vector的所有值是否全部小于A（如果全部小或者全部大，则称两个向量可比较，全部小则替换为更大的vector，全部大则忽略此消息，相当于把vector看作一个整体）。B的vector刷新为[1,1,0]。B再向A发送消息，发出的vector为[1,2,0]。A收到消息之后，识别到了本地的[3,0,0]和[1,2,0]不可比较，之后可以制定相关的解决冲突策略（最简单的，保留原来的或采用发过来的）。
Global State
全局状态对于分布式系统十分重要，无论是分布式调试，还是恢复，都需要从某个状态开始。而从前面的部分我们知道，分布式系统内的节点是几乎不可能在物理时钟上达成一致的（即完美的时钟同步），也就是没办法真正保证某一个时间点使进行系统“暂停”。那我们怎么才能让分布式系统拥有“砸瓦鲁多”（JOJO梗，时间暂停术）的能力呢？
答案就是Chandy和Lamport的Snapshot算法。这篇文章讲的很详细。下面仅对我自己的理解做一个总结。
算法的一个很重要的原则是，对于全局快照中保存的任何一个事件，在这个事件之前发生的事件也应该保存在这次快照中，否则就违反了因果一致性。
算法中，假设分布式系统中存在很多进程
算法开始的标志，就是其中一个进程发送了marker消息，可以将marker理解为一为分隔符，代表之前的是这次快照的内容，之后的不记录此次快照。
算法开始时，发起的进程首先会记录自己的状态，然后给所有建立连接的进程广播marker消息。同时为了系统后续的恢复操作，需要持续记录其他进程给他自己发送的消息。
其他进程接收到marker消息分两种情况：
- 当第一次接收到marker消息，比如A发起的snapshot，B收到了A的marker消息，这里表示的语义就是：Ok，我知道A从此刻开始“砸瓦鲁多”了，那我就不需要继续记录A给我发送的其他消息了。因此标记它与A的channel为空。B此时也应当暂停了，因此需要记录自身状态，然后给其他进程所有进程发送marker消息。
- 当第二次收到marker消息，比如B给A发送的，A收到了。这里表示的语义信息时：Ok，我知道B已经收到marker消息了，我也不需要继续记录B给我发的消息了。
相当于每个进程需要收到其他所有进程给他的marker消息，才可以终止记录两者之间channel的记录信息。
当每个进程都第一次收到了marker消息，记录了自己的状态。同时，每个进程的每个通道中第二次都收到了marker消息，记录了通道的状态。标志着snapshot的算法结束。即形成了全局快照。