Consistency Model

在分布式系统中，多个进程产生的事件应该如何排列？采用一致性模型定义

顺序一致性

同一进程里的事件先后顺序要保留
每次读取的变量都是最新值
系统只能采用一种满足要求的排序，对外看起来有统一的全局顺序

对不同进程的事件顺序没有要求

线性一致性

同一进程的事件先后顺序要一致
每次读取的变量都是最新值
如果不是并发事件（在时间上有重叠），不同进程的事件先后顺序要一致
系统只能采用一种满足要求的排序，对外看起来有统一的全局顺序

因果一致性

满足 happens-before关系

Lamport 时钟

每次进程发出新事件前，将 Lamport 时钟 +1，附在事件上
1
2
3
4
# event happens
time = time + 1;
send(message, time);
进程接收事件后，本进程 Lamport 时钟 = Max(reveive_time, time) + 1
1
2
3
(message, incoming_time) = receive();
time = max(incoming_time, time) + 1;
根据 Lamport 时钟定义 happens-before ，分布式系统的事件如果不满足 happens-before 关系，就是并行事件
基于 Lamport 时钟的分布式事件（不能依赖物理时钟），有一个确定的先后顺序来在状态机执行，并且确保最后状态一致
- happens-before 关系
- 不满足则对比进程 ID

基于 Lamport 时钟的异常行为

有一台分布式系统 X 能够查询比赛得分，采用 Lamport 为请求打上时间戳
A 和 B 正在观看比赛，A 发现了一个新得分，于是到 X 发出 Request A 查询得分，然后花几分钟打电话通知 B 。B 发出 Request B 查询得分，由于 X 认为 Request B 和 Request A 之间没有 happens-before ，X 给 Request B 打上一个比 Request A 更小的时间戳
因此，在 X 全局排序事件后，B 没能看到最新得分

本质上，Request A 和 Request B 存在 happens before，但是这个因果关系发生在系统 X 外的真实世界，X 无法观察到。所以 Lamport 时钟要与真实的物理时钟绑定

物理时钟需要多精确，才能杜绝异常行为？