分布式系统指南大纲之时钟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接收器器
    • 原子时钟用于本地

 

下篇

分布式系统的逻辑时钟

分布式系统指南大纲