分布式系统指南大纲之时钟Clock篇
当一个系统被分离成各个独立的部分,我们还是需要某种事件时钟的顺序来帮助我们排序一些事情,比如首先应该这个,然后再是那个。
中国人常说“道”,包括老子《道德经》中说:道可道非常道,那么这个道到底是什么意思?`道`代表有序的规律或因果时序,无论羊肠小道 还是宽广的大道,其形态都是一种线性,这种空间上的线性与依赖时间前后顺序的逻辑线性是一致的,都是代表一种有机有序的演进关系。结合道生一,一生二,二生万物,这种类似数学加法或乘法的推演更证明了这点。
我们创建一个分布式系统实际在创建一个有道的世界。
挂钟Wall Clock
- 理论上, 操作系统时钟在系统事件上给你一个局部的顺序partial order
- NTP可能并没有你想到那么好
- 节点之间无法很好地明确同步
- 硬件会发生时间漂移
- POSIX时间不能被单调地清晰定义
- 你希望衡量的时间尺度可能无法获得。
- 线程会sleep
- 运行虚拟机会sleep(JVM因为垃圾回收会暂停)
- 操作系统也会sleep
- 硬件也可能Sleep
- 因此不能用系统时钟
Lamport 时钟
- Lamport 1977: "Time, Clocks, and the Ordering of Events in a Distributed System"
- 一个处理过程一个时钟,也就是一个节点一个时钟
- 通过状态切换t' = t + 1 也就是累计的方式单调的增加
- 这种时间戳被包括在每个发送的消息中
- t' = max(t, t_msg + 1)
- 如果我们有所有处理过程的整体顺序,我们就能将其用在事件的整体排序上。
- 但是这种顺序可能是完全的直觉的。
向量时钟(Vector Clock 又称矢量时钟)
- 归纳了Lamport时钟到所有处理时钟的向量中
- t_i' = max(t_i, t_msg_i)
- 对于每次操作,增加向量中的处理节点时钟。
- 提供局部排序partial order
- 对于给定一对事件,我们能决定其因果关系。
- 要么相互独立
- 要么A是B的因果的因
- 要么B是A的因果的因
- 对于给定一对事件,我们能决定其因果关系。
- 过去是可被分享,现在是独立的
- 只有 "现在", 独立的状态需要被保护
- 最原始的状态可以被丢弃
- 能够启动垃圾回收收集被丢弃的过去状态
- 在空间中的O(processes)
- 需要协调 GC
- 或者牺牲正确性并且修剪老的 vclock条目(如果不使用垃圾回收)
- 变种
- Dotted Version Vectors - 用于客/服系统,排序更多事件
- 内部树时钟- 适合节点或处理过程来去时使用
GPS和原子时钟
- 比NTP好得多
- 微秒级别的全局分布式全部排序
- 每一个不确定窗口能做一个可能冲突的事情
- 能正确这么做的人只有Google那帮家伙
- Spanner: 全局分布式强一致性事务数据库
- 并且没有开源共享
- 付出更昂贵代价
- 几百个GPS接收器器
- 原子时钟用于本地