分布式

时钟同步及一致性

诸行无常为佛教的三法印之一。诸行无常是说一切世间法无时不在生住异灭中，过去有的，现在起了变异；现在有的，将来终归幻灭。

世间万物都在变化，只有更精确地测量时间，才能分清事物变化的因果、分析规律。

why: 为什么需要时钟同步

  • 应用层:
    测距：速度*耗时=距离，如果时钟不同步，距离也算不准；
    限频：比如限制1秒内只能访问1次，如果时钟不同步，1秒内可能是任意时间范围；

  • 通信
    初始相位、采样对齐能量峰值点：如果不同步，可能每次采样都恰好在能量低谷，什么都采样不到。
    （解决方案：自同步：一个信道里放两个维度的信息，比如tcp在数据头放seqId、或者在信号里混编特殊信息（同步码、巴克码）
    或并联时钟同步信道：单开一个专门的信道放恒定峰值脉冲）

  • 一致性协议：需要时钟来生成合法的epoch/term;

  • db：数据更新，需要确定副本的新旧；

  • 监控：耗时，如果时钟不同步，结束时间-开始时间=耗时就不成立;

  • 日志：事件发生的因果、依赖关系无法根据日志时间确定;

how: 如何达到时钟同步

观察者：

物理时钟

时钟类型 误差 物理意义 造价
日晷（赤道日晷、水平日晷、垂直日晷） 大 天体物理运动。受各种天体运动影响（地球自转会逐渐变慢），不稳定。 天 = 地球自转到太阳照射同一位置的时长（不稳定） 重大缺陷：晚上用不了、下雨阴天也不行。(现代优化：射电望远镜) 低
滴漏/沙漏 大/5min/小时 重力/摩擦力/基本无法与其他时钟同步。 低
摆钟 大/20s/天 锚定重力加速度 (单摆定律)可能受各种天体运动影响（例如月球潮汐），不稳定。 低
石英钟(SiO2) 一般/0.5s/天（优等品） 压电效应/石英晶体振荡器的频率是32768Hz,受温度影响大 低
铯原子钟 极低/1s/2000万年 铯原子(0K)跃迁 9192631770 个周期=1秒(用电子能级跃迁发出的电磁波频率去校准电子振荡器，所以和别的利用天体物理结果的时钟不同步，但更稳定) 很高（十万～百万级）
NTP（Network Time Protocol） 100ms 定期从时间服务器同步时间，所以可以对齐其他类型的时钟。 受网络延迟影响。 低

同一种物理意义的时钟之间可能可以同步，因为物理常数可能相同；（比如原理都是重力加速度时）
不同物理意义的时钟之间一般是无法同步的，因为锚定的规律都不同，这种情况一般都要通过NTP来对齐。

时间标准

UT（世界时、Universal Time）：基于天体观察的时间（太阳（太阳时）或其他恒星（恒星时）换算）。（秒的长度按全年平均计算）
GMT（格林尼治标准时间、Greenwich Mean Time）：以格林尼治天文台为观测点的世界时。
TAI（国际原子时、InternationalAtomic Time）：基于原子钟的时间
UTC（协调世界时）：平时跟随原子时，但为了人们作息使用，定期同步世界时的时间（闰秒）

虽然根据太阳时的时间不太稳定，但是我们地球生物都依赖它来作息，所以只能平时用稳定的时间（如原子时），定期对齐太阳时。
也就是定义UTC的起因（协调）。

逻辑时钟

Time, Clocks and the Ordering of Events in a Distributed System
lamport时间戳

类似于JVM内存模型中Happen Before规则，逻辑时钟的Happen Before规则：

  1. 本地：a和b是同一个进程内的事件，a发生在b之前，则 a → b。
  2. 远程：a和b在不同的进程中，a是发送进程内的发送事件，b是同一消息接收进程内的接收事件，则 a → b。
  3. 传递性：如果a → b并且b → c，则a → c。

JVM内存模型中的Happen Before:
线：线程先start后run;
程：程序顺序（本地性）
原: 原子变量(volatile)先写后读；
锁: 先解锁别人才能获得锁；
终: 先构造才能终结；
中：先中断别人才能检测到中断；
传：以上规则可以传递

逻辑时钟的一种实现：

分布式系统中每个进程Pi保存一个本地逻辑时钟值Ci，Ci (a)表示进程Pi发生事件a时的逻辑时钟值，Ci的更新算法如下：

1
2
3
进程Pi事件：Ci+=p。(实际p一般=1)
进程Pi->进程Pj:  Ci。
进程Pj:  Cj = max (Ci, Cj) + p。(实际p一般=1)

递增序列，事件驱动：只处理偏序关系(happen before)；
（偏序集、一个元素至少有另一个可以比较顺序）
因为可能有不互相依赖的事件，无法判断先后，只能认为是”同时”。

MySQL 5.7二进制日志较之原来的二进制日志内容多了last_committed和sequence_number这两项内容。
这两个值即所谓的”逻辑时间戳标记（Logical Clock）”，可以用于控制多线程复制（MTS）特性。

sequence_number：该值随着事务顺序增长，每个事务对应一个序列号。
该值在事务二阶段提交的Prepare阶段被记录存储，用于标记最新提交的事务。

last_committed：表示事务提交的时候，上次事务提交的序列号（sequence_number），
如果事务具有相同的last_committed，则表示这些事务都在一组内。该值在事务二阶段提交的Commit阶段被记录存储。

逻辑时钟的问题

写：无依赖时无序（同时）；

“同时”带来的问题，有了数据也不知道原因：
a -> b , 则 Ci(a) < Ci(b) // 充分条件
Ci(a) < Ci(b)，不并代表 a->b // 不必要，因为有同时的情况，可能a,b其实同时发生。

读：读往往不带版本号、怎么处理？（也无最新的概念）

偏序和全序

偏序

给定集合S，”≤”是S上的二元关系，若”≤”满足：

1
2
3
4
1. 自反性：∀a∈S，有a≤a；
2. 反对称性：∀a，b∈S，a≤b且b≤a，则a=b；
3. 传递性：∀a，b，c∈S，a≤b且b≤c，则a≤c；
则称"≤"是S上的非严格偏序或自反偏序。

全序

全序关系即集合X上的反对称的、传递的和完全的二元关系（一般称其为 ≤)。
若X满足全序关系，则下列陈述对于X中的所有a,b和c成立：

1
2
3
1. 反对称性：若a ≤ b且b ≤ a 则 a=b
2. 传递性：若a ≤ b且b ≤ c则a ≤ c
3. 完全性：a ≤ b或b ≤ a

偏序 => 全序（增加完全性，任意俩元素都可以比较）：
raft\multi-paxos的解法：把写者变成一个
// 把偏序变全序的核心是增大共识范围，同时降低洪泛通信
其他解法：向量时钟、True Time

向量时钟

数据库亚马逊 Dynamo

解决逻辑时钟的一个朴素方案是：拓展逻辑时钟：从单播、多播事件改成广播；确保全序关系（全序集：任意两个有时间先后顺序）。
（问题：通信成本过于高了，洪泛）

向量时钟的方法：
进程通信时，不但发送本进程时钟，还发送本进程知道的所有其他进程的时钟值（向量V）。

分布式系统中每个进程Pi保存一个本地逻辑时钟向量值VCi，
（向量的长度是分布式系统中进程的总个数）
VCi (j)表示进程Pi知道的进程Pj的本地逻辑时钟值，VCi的更新算法如下：

1
2
3
4
5
6
1.初始: VCi的值全为0：VCi = [0, … , 0]
2.进程Pi事件: VCi[i]+=p (实际p一般=1)
3.进程Pi->进程Pj: VCi
4.进程Pj:
4.1 对于VCj向量中的每个值VCj[k]，VCj[k] = max (VCi[k], VCj[k]) // 更新其他进程的时钟
4.2 VCj[j]+=p (实际p一般=1) // 更新自己的

向量之间如何比较大小：

1
对于每个k，VCi[k]  <= VCj[k]，则VCi ≤ VCj; // 每个元素都要<=

类似的，如果每个元素都相等，那VCi = VCj
如果各个元素的大小关系有大有小不一致，那就是同时。

这个算法大框架和原来的逻辑时钟几乎一样，显然向量的集合是个偏序集。
那么能进一步强化充要条件，也就是，是否有：

1
若VC(a)<VC(b)， 则 a->b。

分类讨论：
1.同一进程内：显然成立；
2.不同进程：
由于VCi(a)<VCj(b),也就是VC内每个元素都小于
直接用VCi[i]来指代有点乱，因为只涉及两维，直接改成x,y也就是:

1
2
3
(x1,y1) < (x2, y2) 等价于:
(1)x1 < x2;
(2)y1 < y2;

假设有其他事件: c(x1, y2) 或 d(x2, y1)来构造传递性：（当然实际可能经过了更多中间节点）

1
2
则a<c, c<b 推导出 a<b
或a<d, d<b 推导出 a<b

综上，虽然向量时钟中依然有”同时”情况，但对于存在因果、依赖的连通子图，已经能形成局部的全序集合，也就是在”视界”内是全序的，已经能满足实际应用。（相比之下，逻辑时钟仅在1度关系内能判定因果）

True Time(TT)

[Spanner: Google’s Globally-Distributed Database]https://pdos.csail.mit.edu/6.824/papers/spanner.pdf

整体架构可以看作一个升级版的NTP.

NTP架构

TT架构

原子钟+GPS时钟（因相对论，更快）+每个数据中心的time mater集群。

误差：1～7ms

接口 返回
TT.now() [earliest,latest] 最大间隔7ms,返回一个范围区间,真实时间位于这个区间内
TT.after(t) boolean，当前真实时间是否晚于t
TT.before(t) boolean，当前真实时间是否早于t

Spanner采用MVCC机制，因此数据副本上需要一个时间戳Si。

读写事务

提交过程：

1
2
1.Si >= TT.now()的lastest，作为提交时间戳；
2.Cond wat: 等待TT.after(Si)为true时才提交；

平均总等待时长8ms，所以同一份数据的tps = 125。

谷歌：We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.
我来翻译一下就是：这性能够了，太依赖事务导致性能不行是业务开发设计有问题。

只读事务

快照读：事务开始后，取TT.now().latest作为过滤(before)的时间戳。

参考资料

https://ost.51cto.com/posts/15990
utc协调事件时：https://kstack.corp.kuaishou.com/article/7767
组提交：https://developer.aliyun.com/article/617776
偏序：https://zhuanlan.zhihu.com/p/44665237
https://zhuanlan.zhihu.com/p/651456126
https://zhuanlan.zhihu.com/p/35473260
http://yang.observer/2020/11/02/true-time/

推荐文章