Cloud Computing之时钟和顺序Time and Ordering

参考文献：

Lamport’s logical clock
强一致性、顺序一致性、弱一致性和共识

这章重点介绍了分布式系统下各种类型的时序，其实在分布式场景下并不需要确切的时间，我们只是需要时间来对事件进行排序ordering. 并且还聊到了哪种order顺序是正确correct的，这其实没有绝对的定论，而是要根据各种场景选择合适的顺序，重点在于不同的节点对于正确性correctness的定义需要一致。

Total order

all replicas process messages in same order, 对于多个replica节点来说，所有的replica节点都遵循相同的处理顺序，但是不一定服从real-time，也就是不一定和client发来的处理顺序一致。

与之相对应的是顺序一致性（Sequential Consistency）

Implementation of total order

Total-order是可以实现的，不过需要选出一个leader，并且每次分发消息的时候都需要一个时间戳。

Linearizability

total order + respect the real-time，在total order的情况下加上了real-time的要求，即和client发来的处理顺序一致，并且所有replicas都是相同的处理顺序。

linearizability是没法在distributed system分布式系统中实现的，这里有个CAP的理论，参考轻松理解CAP理论，简单来说就是在P的场景下，无法保证C和A同时成立，除非有特殊的场景设计，比如Google对P的场景进行了独特的设计。

但是linearizability却可以在parallel system并行系统中实现，因为这个系统是个同步的场景synchronous setting，并且parallel system就应当保证linearizability的唯一正确性。

与之相对应的一致性叫做 线性一致性（Linearizability），还可以叫强一致性（Strong Consistency）外，还叫做原子一致性（Atomic Consistency）、立即一致性（Immediate Consistency）或外部一致性（External Consistency）

FIFO order

different servers can get different orders as long as the order from the same client is preserved. 这里强调了多个client的要求，对于多个replica server来说，他们是可以按不同的顺序处理消息的，但是对于给他们发消息的每个client，每个服务器server需要按client发来的消息一样的顺序对消息进行处理。

Implementation of FIFO-order

同样可以在distributed system中实现，clients需要维护一个本地的计数器，server端需要为每一个client维护一个处理队列。

Happen-before ordering

可以通过逻辑表示出发送方和接收方的顺序关系。

这里我们重点关注如何在日志中记录这种前后关系，也就是采用了Lamport’s Logical Clock的方法如下：

简单理解来看，对于同一个process的先后事件，后一个事件为前一个LC++，对于不同process具有happen-before关系的事件，后一个事件也为前一个LC++，最终该事件的LC为这两个值中的max. 假设$P^i$给$P^j$发消息，$L{C}^j=max(1+L{C}^i,1+L{C}^j)$。

但是这种记录方法有它的局限性，即当LC(x)

Causal ordering

Causal ordering可以表示不同进程间的因果关系，下面这个例子很生动，如果我们只是维持FIFO order，那么分别保证了mother(client)的顺序和father(client)的顺序，但是它们两者综合起来看就会产生意想不到的后果。因此我们需要一种因果关系去表征不同process间的关系，这就是causal relationship。

在实现上，采取了vector clock这种时钟，VC不是一个值，而是一个有N个分量的向量，其中N是processors的个数。在进行更新的时候，和Logistic Clock一样是取最大值，不过是对每一个分量都要取当前的最大值；对于先后事件时间$VC$的更新，假设$P^i$给$P^j$发消息，接受者$P^j$需要在$V{C}^j$第j个分量上+1，即$V{C}^j[j]+1$，然后和发送者$P^i$原来在第j个分量上的值$V{C}^i[j]$进行比较，$$V{C}^j\leftarrow \left[\max (V{C}^j[1],V{C}^i[1]),...,\max (V{C}^j[j]+1,V{C}^i[j]),...,\max (V{C}^j[n],V{C}^i[n])\right]$$

与之对应的是因果一致性（Causal Consistency）,这是弱一致性中最终一致性的一种，参考 强一致性、顺序一致性、弱一致性和共识里面别的分类。

Summary