【Day 4】物理时间、happens-before 关系、causality

回家再修文，先发ㄌ
晚点要补一下前一篇的 failure detectors

介绍分散式系统中的时间，主要分为

• physical clocks: count number of seconds elapsed
• logical clocks: count events, e.g. messages sent

这篇笔记在物理时间 3.1 3.2 不做太多着墨，
只需要知道因为误差的关系，
分散式系统间的讯息传递不能以物理时间当作时戳，
否则可能会有时空旅行的可能。

3.3 会介绍逻辑时间的数学关系，以迎接第 4 章: Logical clock。

3.1 Physical clocks

对於分散式系统来说，物理时间较少使用。

• 石英 quartz clock: 便宜、不够精确，容易因为温度上升而失准。是现代电子表最常使用的。
• atomic clock: 贵

UTC

根据 atomic 时间，但会依据地球自转而有所校正。

GMT

leap seconds

校正 UTC 来大致符合地球自转。
每年可能 +- 1 秒，会提前公告。
而这个东西会造成很大的问题！！
通常程序会直接忽略 leap seconds，对於一些系统来说这是很严重的事情。

leap second smearing

3.2 Clock synchronisation

• clock drift: 一个时钟与精准时间的误差
• clock skew: 两个时钟在某时刻的差距

如果两个时钟都有各自的 drift，那他们的 skew 随着时间增加，所以需要 sync。
i.e. a时钟慢了1秒，b时钟快了1秒，每秒这两个时钟差就多2秒。

Network Time Protocol (NTP)

clock server 的层级：

• Stratum 0: atomic clock or GPS receiver
• Stratum 1: synced directly with stratum 0 device
• Stratum 2: servers that sync with stratum 1, etc.

Estimating time over a network

时间校正

根据 client 和 server 的时间差，调整 client 时钟的策略有 3 种：

• slew: 加快或调慢一点点比例。
• step: 把 client 调为 server 时间。
• panic: 差异太大了，不做任何事，交给人解决。

Physical clock 主要分两种，用错麻烦多

Time-of-day clock

• 从固定日期开始计算的时间 (e.g. 1 January 1970 epoch)
• 可能突然增加或倒退（NTP stepping）
  因为 leap second 调整
• 不同 node 可用此 Timestamps 比较
  Java: System.currentTimeMillis()
  Linux: clock_gettime(CLOCK_REALTIME)

Monotonic clock

• 从 arbitrary point 开始计算的时间 (e.g. 从机器开机开始计时)
• 只会增加
  moves at a nearly constant rate
• Good for measuring elapsed time on a single node
  Java: System.nanoTime()
  Linux: clock_gettime(CLOCK_MONOTONIC)

Summary

所以单个电脑上要对某个动作计时，应该使用 monotonic clock。
如果是分散式系统，不得已得用 physical clock 来比较不同电脑的时间，则用 time-of-day clock。

3.3 Causality and happens-before

为什麽分散式系统上不能用物理时间？

再怎麽努力与 NTP sync，每个电脑上的物理时间还是有可能会有一点点误差。
若以物理时间来重新排序讯息，一个不小心就可能时空旅行。
time skew > one way network delay?? 不太懂 3:27

happens-before

定义 happens-before relation
a -> b 代表 a happens-before b iff:

• a b 两事件在同个 node 上发生，a 先执行，b 後执行。
• a b 两事件在不同 node 上发生，a 是 n1 的传送事件，b 是 n2 的接收事件。这应该很好理解。
• 递移律：今天有的事件 c，a -> c，c -> b ，可以推得 a -> b。

happens-before 是个 partial order，
有可能 既不是 a -> b 也不是 b -> a，称之 concurrent。
a || b。

什麽？为什麽可以不是 ａ－> b 也不是 ｂ-> a?

这可能小小的违反我们的直觉，
但 happens-before 关系是一种相对关系，
而我们直觉是基於物理时间的。

在分散式系统上，
如果不能使用物理时间，
那若没有讯息传递，例如两个 nodes 之间完全不联系，
我们无从去比较出两个 node 上事件的 happens before relation 的。

concurrent 不代表 spontaneous！！
只是这两个 events 不知道对方先发生还是後发生、无法比较而已。

• partial order: 能够将一个 set 中的部分元素做排列
• total order: 能够将一个 set 中的所有与素做排列

因果关系 Causality

happens-before relation 是一种可以讨论分散式系统上事件之间因果关系的数学关系。

a -> b: a 可能 have caused b
a || b: a 不可能 have caused b

causal order
是代表
若 a causes b, then a happens before b?

似乎是从物理借镜来的概念。
如果今天两个事件发生的「距离够远」，就算时间很相近，但他们却不会有关系，a 不可能影响 b。
分散式系统注重讯息的顺序，其中也有同样的概念，就是如果 a 跟 b 没有 causal 关系的话，或许我们并不是很在意他们实际是不是在差不多的时间发生。
a || b : a 不可能 have caused b!