诸行无常为佛教的三法印之一。诸行无常是说一切世间法无时不在生住异灭中,过去有的,现在起了变异;现在有的,将来终归幻灭。
世间万物都在变化,只有更精确地测量时间,才能分清事物变化的因果、分析规律。
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
规则:
- 本地:a和b是同一个进程内的事件,a发生在b之前,则 a → b。
- 远程:a和b在不同的进程中,a是发送进程内的发送事件,b是同一消息接收进程内的接收事件,则 a → b。
- 传递性:如果a → b并且b → c,则a → c。
JVM内存模型中的Happen Before:
线:线程先start后run;
程:程序顺序(本地性)
原: 原子变量(volatile)先写后读;
锁: 先解锁别人才能获得锁;
终: 先构造才能终结;
中:先中断别人才能检测到中断;
传:以上规则可以传递
逻辑时钟的一种实现:
分布式系统中每个进程Pi保存一个本地逻辑时钟值Ci
,Ci (a)
表示进程Pi
发生事件a
时的逻辑时钟值,Ci
的更新算法如下:
1 | 进程Pi事件:Ci+=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 | 1. 自反性:∀a∈S,有a≤a; |
全序
全序关系即集合X上的反对称的、传递的和完全的二元关系(一般称其为 ≤)。
若X满足全序关系,则下列陈述对于X中的所有a,b和c成立:
1 | 1. 反对称性:若a ≤ b且b ≤ a 则 a=b |
偏序 => 全序(增加完全性,任意俩元素都可以比较):
raft\multi-paxos的解法:把写者变成一个
// 把偏序变全序的核心是增大共识范围,同时降低洪泛通信
其他解法:向量时钟
、True Time
向量时钟
数据库亚马逊 Dynamo
解决逻辑时钟的一个朴素方案是:拓展逻辑时钟:从单播、多播事件改成广播;确保全序关系(全序集:任意两个有时间先后顺序)。
(问题:通信成本过于高了,洪泛)
向量时钟的方法:
进程通信时,不但发送本进程时钟,还发送本进程知道的所有其他进程的时钟值(向量V)。
分布式系统中每个进程Pi保存一个本地逻辑时钟向量值VCi
,
(向量的长度是分布式系统中进程的总个数)VCi (j)
表示进程Pi知道的进程Pj的本地逻辑时钟值,VCi
的更新算法如下:
1 | 1.初始: VCi的值全为0:VCi = [0, … , 0] |
向量之间如何比较大小:
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 | (x1,y1) < (x2, y2) 等价于: |
假设有其他事件: c(x1, y2)
或 d(x2, y1)
来构造传递性:(当然实际可能经过了更多中间节点)
1 | 则a<c, c<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 | 1.Si >= TT.now()的lastest,作为提交时间戳; |
平均总等待时长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/