偏序和全序

Lamport的

1. 如何定义偏序? 如何将一个从偏序转化为全序?

2. 在阐述全序关系有什么用时, 涉及到分布式系统的状态机问题, 并提出全序问题可以被用于解决分布式系统的一致性问题 

我很快就意识到该定义事件全序关系的算法可以用来实现任意的分布式系统.  一个分布式系统可以描述为一个特殊的具有多个由网络互联的处理器的串行状态机. 如果能够对输入请求进行全排序, 就能够实现任何由网络互联的处理器组成的状态机, 因此也就可以实现任意的分布式系统.  为了表明这一点, 论文采用了一个我能想到的最简单的分布式系统实例—分布式互斥算法作为例子

 

偏序和全序, 全序是特殊的偏序

设A是一个非空集，P是A上的一个关系，若关系P是自反的、反对称的、和传递的，则称P是集合A上的偏序关系

在集合A中，如果对于任意a∈A, b∈A, 有aRb或bRa，即A中的每对元素都满足关系R，则集合A上的偏序R是全序的

全序, 集合任意两个元素之间都是有序的, 线性关系 

偏序, 只有部分元素之间有顺序关系, 非线性, 比如分布式系统中的并发关系 

如下图, a中v2和v3是并发关系, 无线性顺序, 所以a表示偏序关系 

对于b, 只需要添加条表示v2和v3之间的连线, 就变为全序关系

偏序, 逻辑时钟

顺序问题, 其实就是定义"happen before"关系, 怎样定义a在b之前发生? 

简单的通过物理时钟(即绝对参照系)是否可以? 可以, 前提是在不同地方的物理时钟没有误差  这个几乎是不可能的, 所以需要物理时钟同步, 这也是个研究方向...最近google发布的spanner的核心技术包含用卫星进行全球的datacenter之间的时钟同步

既然使用绝对的物理时钟比较困难, 作者想到狭义相对论, 即通过严格的因果关系来确定顺序 

对于参照系, 选取不同的参照系可能会有不同的顺序的判断, 但是对于严格的因果关系, 无论在什么参照系下都不会改变的

狭义相对论告诉我们时空中的事件并不存在一个始终如一的全序关系, 不同的观察者对两个事件谁先发生可能具有不同的看法. 当且仅当事件e2是由事件e1引起的时候, 事件e1和e2之间才存在一个先后关系

对于进程内的事件,具有明确的因果关系, 如下图, 对于process P, p1, p2, p3, p4是有固定顺序的 

但对于进程间的事件, 如果两个进程没有关联或通信, 是无法判断顺序的  只有当两个进程间产生通信后, 产生因果关系, 从而来确定顺序  如p1为发消息给Q事件, 而q2为从P收到消息事件, 则p1和q2间有明确的因果关系, 故可以说p1 "happen before" q2, 即p1 –> q2

而对于没有明确的因果关系的事件, 无法判断其顺序, 只能认为他们属于"concurrent” 

比如对于p1和q1, 你无法判断哪个先发生

偏序'->' Definition

满足如下三个条件的最小关系： 

(1)如果a和b是同一个进程中的事件，并且a在b前面发生，那么 a->b 

(2)如果a代表了某个进程的消息发送事件，b代表另一进程中针对这同一个消息的接收事件，那么a->b 

(3)如果 a->b且b->c，那么a->c (传递性)

 

引入逻辑时钟(Logical Clocks)来表示相对关系, 所谓逻辑即不象物理时钟记录具体的时间, 而这是通过比如递增编号来表示事件之间的相对关系(即因果关系)

逻辑时钟定义

Clock Condition.对于任意事件a,b：如果a->b，那么C(a) < C(b), 反之不然, 因为有可能是concurrent

C1.如果a和b都是进程Pi里的事件，并且a在b之前，那么Ci(a)<Ci(b)

C2.如果a是进程Pi里关于某消息的发送事件，b是另一进程Pj里关于该消息的接收事件，那么Ci(a)<Cj(b)

右图, 假设虚线表示逻辑时钟的ticks(逻辑时钟的计数单位), 则进程内的事件之间至少有一个tick, 并进程间的消息线至少跨越一个tick

为了确保满足条件C1和C2, 进程只需要遵守如下的实现规则即可：

IR1.每个进程Pi在任意连续的两个事件之间会增加Ci的值

IR2.如果事件a代表了进程Pi发送消息m的事件，那么消息m包含的时间戳Tm=Ci(a). 在收到消息m后，进程Pj会设置Cj的值使得它大于等于它的当前值并大于Tm.

Ordering The Events Totally, 全序

全序需要解决的问题, 当出现concurrent时, 怎样排序? 

这个其实没有绝对的标准, 文章中以进程间的任意的一个全序关系Pi<Pj来决定顺序, 至于如何定义进程间的全序, 可以自定义  当然你可以使用其他的标准在产生全序 结论是, 偏序由系统中的事件唯一确定的, 而更具不同的Clock Condition可以产生不同的全序关系

全序关系"=>"定义 

假设a是进程Pi中事件，b是进程Pj中的事件，那么当且仅当满足如下条件之一时:  (1)Ci(a)<Cj(b);  (2)Ci(a)=Cj(b)且Pi<Pj，  那么我们就认为“a=>b”

 

全序问题的价值, 解决分布式一致性问题

需要满足如下条件, 

(1)已经获得资源授权的进程，必须在资源分配给其他进程之前释放掉它；

(2)资源请求必须按照请求发生的顺序进行授权；

(3)在获得资源授权的所有进程最终释放资源后，所有的资源请求必须都已经被授权了。

其实这个问题关键就在于(2)中, 如何分布式的环境下确定请求发生的顺序? 

使用中央调度进程按照资源请求被收到的顺序, 是否可行? (不考虑安全性, 即单点问题) 

论文认为不可行, 因为要求是按照请求发生的顺序, 由于网络问题, 请求被接受顺序可能和发生顺序完全不同

于是, 我们需要使用上面讨论的时钟系统, 并为所有的资源请求和释放事件提供了一个全序关系 

首先是建立时钟系统, 为所有的申请和释放事件加上逻辑时钟(时间戳) 

申请和释放都需要想所有的进程发送带有时间戳的消息 

所有进程收到申请时, 都需要回复带有时间戳的消息 

当一个进程已经接受到所有进程发来的消息后, 就可以使用上面的全序定义, 为所有事件排全序“=>” 

如果本进程的请求排在最前面, 则可以占有资源, 否则必须等其他进程的释放请求 

此处基于消息一定按照发送顺序被接收到假设, 即当从所有进程都收到了时间戳>Tm的消息, 则可以证明, 我的请求是最先发生的

先我们假设，对于任意的两个进程Pi和Pj，它们之间传递的消息是按照发送顺序被接收到的, 并且所有的消息最终都会被接收到。 

每个进程会维护一个它自己的对其他所有进程都不可见的请求队列。我们假设该请求队列初始时刻只有一个消息T0:P0资源请求，P0代表初始时刻获得资源授权的那个进程，T0小于任意时钟初始值 

1. 为请求该项资源，进程Pi发送一个Tm:Pi资源请求消息给其他所有进程，并将该消息放入自己的请求队列，在这里Tm代表了消息的时间戳

2. 当进程Pj收到Tm:Pi资源请求消息后，将它放到自己的请求队列中，并发送一个带时间戳的确认消息给Pi。(注：如果Pj已经发送了一个时间戳大于Tm的消息，那就可以不发送)

3. 释放该项资源时，进程Pi从自己的消息队列中删除所有的Tm:Pi资源请求，同时给其他所有进程发送一个带有时间戳的Pi资源释放消息

4. 当进程Pj收到Pi资源释放消息后，它就从自己的消息队列中删除所有的Tm:Pi资源请求

5. 当同时满足如下两个条件时，就将资源分配给进程Pi：

   a) 按照“=>”关系排序后，Tm:Pi资源请求排在它的请求队列的最前面

   b) i已经从所有其他进程都收到了时间戳>Tm的消息

这个算法的问题是不允许进程fail, 并对网络状况有比较理想的假设, 否则都会导致无法找到全序 

所以理论和启发意义大于实际意义 

可以认为该思想启发了Paxos和vector clock等相关算法 

对于不稳定环境的强一致性问题, paxos算法给出更好的答案 

对于高并发的高可用性问题, vector clock技术参照该论文给出偏序的方案

本文章摘自博客园，原文发布日期：2013-04-13