1、分布式环境中 事件的 偏序关系 happens before 的介绍
实际上 时间 是一件难以把握的事情，不知道 你们有没有感觉，在引入业务时间约束的分布式系统里，处理时间是一件特别头疼的事情，因为不同机器的时间是不一定一致的。
而且，我们根本无法精确衡量时间，我们制作出来的钟表，必然在行进过程中存在误差，因此我们定义 happens before 关系的时候，应该要排除掉物理的时钟。
happens before 关系本质上是 因果关系，在lamport的设定里，happens before关系具现化如下：
happens before 用符号 → 表示，其代表
1、如果事件a,b都在同一个进程内，如果 代码执行顺序中 a 在 b 之前，那么 a →b
2、进程间可以通过收发信息进行通讯，进程x发信息事件为a，进程y收信息事件为b，那么a->b
3、如果a→b,b→c那么a→c
如果 a,b是两个不同的事件，且 a !→ b，b !→ a，那么我们就称a,b是并发的。（超级赞的定义！！！）
2、一个逻辑时钟算法
时钟可以抽象成 为发生的事件 进行编码的工具，编码 代表 该时间发生的时间。
我们定义C为全局逻辑时钟，一个合理的逻辑时钟产生的 编码 符合以下条件即可：
if a->b then C(a)<C(b)
约束条件很简单，那么对于两个并发的事件a,b，可以设定成 C(a)>C(b),也可以设定成C(b)<C(a),并没有关系，开心就好
既然约束条件简单，那么看一下lamport设定的 happens before 关系，可以推出一个逻辑时钟算法如下：
我们定义 Ci 为 进程Pi 的时钟，Ci(a)表示 Ci 为事件 a 进行的编码
1.每个进程Pi在任意连续的两个事件之间会增加Ci的值
2.(a)如果事件a代表了进程Pi发送消息m的事件，那么消息m包含的时间戳Tm=Ci(a).
(b)在收到消息m后，进程Pj会设置Cj的值使得它大于等于它的当前值并大于Tm.
3、事件严格全序排列算法
有了上述的逻辑时钟算法，我们就可以为所有的事件进行编码，从而得到关于逻辑时间的全序关系
但是上述的算法有可能为不同的进程的并发事件分配同一个时间编码，为了去除这种情况，得到一个关于逻辑事件 的严格的全序关系，lamport给出了以下的算法设定
define a relation => as follows:
if a is an event in process Pi and b is an event in process Pj, then a => b if and only if either (1) Ci(a) < Cj(b) or (2) Ci(a) = Cj(b) and Pi 《 Pj. （“《”指代啊 进程间任意定义的一个全序关系,例如 进程的编号 ）
这样 =>就是一个 进程的事件间 严格全序关系。因为逻辑时钟的实现不唯一，因此 这种全序关系 也可以有很多个，只有偏序关系是唯一的。(PAXOS算法也用了这中全序编码算法)
那得到这么一个全序关系有什么用？Lamport给我们举了个栗子
假设需要一个分布式锁的服务,满足以下需求，
(I) A process which has been granted the resource must release it before it can be granted to another process.拿到锁的进程，在释放锁之前，其他进程都不能获得锁
(II) Different requests for the resource must be granted in the order in which they are made. 获得锁的顺序必须跟锁请求发起的顺序一致。（*而不是接收到请求的顺序）
(III) If every process which is granted the resource eventually releases it, then every request is eventually granted. 如果获得锁的进程最终都都会释放锁的话，那么每一个 锁请求 最终都会请求成功
lamport给出了这么一个依赖于 事件全序关系 的算法（这个算法中默认 发送的消息是 按发送的顺序接收到的，且最终一定会接收到的，但这个实现并没在算法中体现，要实现的话，发送序号+ACK就能实现）,满足上述需求：
1. To request the resource, process Pi sends the message Tm:Pi requests resource to every other process, and puts that message on its request queue, where Tm is the timestamp of the message.
2. When process Pj receives the message Tm:Pi requests resource, it places it on its request queue and sends a (timestamped) acknowledgment message to Pi.
3. To release the resource, process Pi removes any Tm:Pi requests resource message from its request queue and sends a (timestamped) Pi releases resource message to every other process.
4. When process Pj receives a Pi releases resource message, it removes any Tm:Pi requests resource message from its request queue. . Process Pi is granted the resource when the following two conditions are satisfied:
(i) There is a Tm:Pi requests resource message in its request queue which is ordered before any other request in its queue by the relation =>. (To define the relation "=>" for messages, we identify a message with the event of sending it.)
(ii) Pi has received a message from every other process timestamped later than Tm.
Note that conditions (i) and (ii) of rule 5 are tested locally by Pi.
一大串鸡肠，表达的意思实际上是，
1、每个 进程都会保存一个队列，这个队列用于存储自己或者其他进程的锁获取请求，这些请求是按照 全序关系=>排列的。
2、一个进程 Pi 如果他自己的 获取锁请求，Tm:Pi排在最前面，且接收到了其他所有进程的大于 Tm的消息后，那么 进程自身就能认为 自己获得了锁。因为 收到消息的顺序跟发送消息的顺序是一致的，因此收到了其他所有进程大于Tm的消息后，Pi已经收集齐了所有时间小于 Tm的 事件，发现自己的请求Tm:Pi资源请求依然是最小的话，那么，自己必然是 锁 的拥有者。显然，这就满足了 需求（II）
3、释放锁的请求由 资源获得者 Pi发起，发起之后，其余进程才能将各自队列中Pi对应的锁请求消除，因此必然能保证需求(I)
4、因为锁释放的消息最终都传到各个进程中，因此(III)也能满足
因此本算法是可以达到指定目标的，但本算法在某个进程宕机时，就无法跑下去了╭(╯^╰)╮
4、关于逻辑时钟算法的一些异常
假设存在一个用上述逻辑时钟保证报名顺序的报名系统中，张三 在系统中报名了后，打电话给 李四，让李四也去系统中报名 这样的话，李四的报名是有可能早于张三的。
因为 打电话这个行为 是在逻辑时钟的系统之外，系统没办法获得 张三报名->打电话，打电话->李四报名 这个信息，因此张三报名和李四报名 在报名系统中，是并发的。
要怎么解决这个问题？有两种方法：
1、将打电话这个操作的信息保存到系统中，就是说建立 上面提到的->关系
2、实现一个 强逻辑时钟算法，满足以下条件：在软件系统中的两个事件 a,b，如果 a,b在真实时钟里存在 happens before关系（用-->表示），那么C(a)<C(b)
然后Lamport说：
One of the mysteries of the universe is that it is possible to construct a system of physical clocks which, running quite independently of one another, will satisfy the Strong Clock Condition.
（我们可以构造 多个相互独立运行的物理时钟系统，并让他们协调合作构成一个整体的 符合 强逻辑时钟 的 分布式时钟算法系统）
5、物理时钟（以下为直接摘抄译文，自己看文章理解的不太好）
有效的物理时钟应该有以下特性：
PC1、对于所有的t，dCi(t)/dt≈1，也就是说 存在一个常数k，对于所有的i：| dCi(t)/dt -1|<k
PC2、对于所有的i,j：| Ci(t)-Cj(t)|<e. e为一个足够小的常数。
两个不同的时钟永远都不会以相同的速率走动，这意味着它们之间的偏差会越来越大。因此我们必须要设计一种算法来保证PC2总是成立。但是，首先我们来看一下k和e要多小才能避免异常行为。
令u表示满足如下条件的值：如果事件a发生在物理时间t，同时b是发生在另一个进程中的满足a->b事件，那么b肯定发生在物理时间t+u之后。
换句话说，u需要小于进程间消息传输的最短时间。我们可以用进程间的距离除以光速的值作为u的值。(信息传播最快的速度为光速，视乎信息传播形式，传播速度可能远慢于光速)
为避免异常行为，我们必须保证对于任意i,j,t：Ci(t+u)-Cj(t)>0
现在由上述三条公式推导出 e,k,u的关系：
由 Ci(t+u)-Cj(t)>0 得 Ci(t+u) -Ci(t) + Ci(t) - Cj(t) > 0 , Ci(t+u) -Ci(t) > -Ci(t) + Cj(t) .
由 | Ci(t)-Cj(t)|<e 得，-Ci(t) + Cj(t) 的最大值为 e,因此 Ci(t+u) -Ci(t) >= e
由| dCi(t)/dt -1|<k， 因此 1+k > dCi(t)/dt > 1-k，--》 Ci(t+u) -Ci(t) > (1-k)(t+u-t) --> Ci(t+u) -Ci(t) > (1-k)u
由 Ci(t+u) -Ci(t) > (1-k)u，说明Ci(t+u) -Ci(t)的最小值可能为(1-k)u， 为了保证Ci(t+u) -Ci(t) >= e成立, (1-k)u >=e 即可
由 | Ci(t)-Cj(t)|<e 得，-Ci(t) + Cj(t) 的最大值为 e,因此 Ci(t+u) -Ci(t) >= e
由| dCi(t)/dt -1|<k， 因此 1+k > dCi(t)/dt > 1-k，--》 Ci(t+u) -Ci(t) > (1-k)(t+u-t) --> Ci(t+u) -Ci(t) > (1-k)u
由 Ci(t+u) -Ci(t) > (1-k)u，说明Ci(t+u) -Ci(t)的最小值可能为(1-k)u， 为了保证Ci(t+u) -Ci(t) >= e成立, (1-k)u >=e 即可
推导的这个公式(1-k)u >=e 可以理解为，最小的信息传达的时间，要大于误差时间。
PC1这个条件由我们物理时钟的实现技术保证，典型的由晶体控制的时钟来说，k<=10^-6
我们来看看保证PC2实现的算法，即一个物理时钟同步算法
证明实在看不下去了，以后有空再回顾一下，说一下结论：
THEOREM.假设一个半径为d的由多个进程组成的强连通图始终满足规则IR1’和IR2’。同时对于任意消息 m，Um<=某常数U,以及任意时刻t>=t0来说：(a)PC1成立.(b)存在常数τ和ε，每τ秒都会有一个消息在不可预测的延迟部分小 于ε的情况下在每条边上传送。那么PC2就能被满足，同时对于所有的t>t0+τd，e≈d(2kτ+ε)，这里我们假设 U+ε<<τ。
IR1’.对于每个i，如果Pi在物理时间t未收到消息，那么Ci是在时间t就是可微分的并且dCi(t)/dt>0.
IR2’. (a)如果Pi在物理时间t发送了一个消息m，那么m将包含一个时间戳Tm=Ci(t).(b)当在时间t’接收到消息m时，进程Pj将设置Cj(t’) 等于max(Cj(t’-0),Tm+Um).(注：Cj(t’-0)=[limCj(t’-|&|),&->0])
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于