Consistency and Consensus (3-2) - Lamport Timestamp

续 Day 17

序列号排序 (Sequence Number Ordering)

使用 timestamp 是排序事件的好方法，我们曾在 2021 Day 11 - 顺序性事件的时间戳记 看过用 timestamp 做排序的例子，当时我们提到可以使用 逻辑时钟 (logical clocks) 来取代 日历钟 (time-of-day)，逻辑时钟通常就是使用 counter 针对每个操作做累加（也就是序列号），透过序列号或 timestamp 你很轻松的就能知道全局顺序。

single-leader 类型的数据复制资料库很好实作序列号，leader 就帮每个写入计数就好了，那麽非 single-leader 类型的资料库该怎麽办呢？

非因果关系序列号产生器 (Noncausal sequence number generators)

在实务上替非 single-leader 资料库（multi-leader, leaderless）建置序列号有以下 3 种方法：

• 每一个节点可以产生自已独立的序列号，举例来说若你有 2 个节点，节点 A 只产生单数，节点 B 只产生偶数这样。
• 使用老方法帮每个操作加上来自日历钟的 timestamp。
• 预先分配序列号区块，举例来说节点 A 每次都是取得 1 ~ 1000 的序列号区块，节点 B 取得 1001 ~ 2000 的序列号区块，然後每个节点独立的分配该区块的号码。

相比 single-leader 来看，这 3 个方法都有很好的可扩充性，然而，这些序列号不符合因果关系。

Lamport timestamp

救星来了，马上要来介绍一个能在分散式系统产生有因果关系的序列号方法，Lamport timestamp，来自 1978 年由 Leslie Lamport 发表，这也是在分散式系统领域中被引用最多次的论文之一。

Lamport timestamp 提供有因果关系全局顺序的方式如下图 9-8， 每一个节点都有唯一的 ID，且每个节点都会计算已执行操作的数量，Lamport timestamp 资料就是个简单的 (counter, 节点 ID)，2 个节点或许会有一样的 counter，但是加入节点 ID 後，就能是该 timestamp 成为唯一。

Lamport timestamp 基本上跟日历钟没啥关系，但它能提供全局顺序，如果你想比较 2 个 Lamport timestamp 大小，首先就看 counter 谁大，倘若 2 个 timestamp counter 相同，就以节点 ID 大小为主。

另外每个节点跟 Client 都要追踪最大 counter 值，所以每一个 request 都要包含目前所知的最大值，当一个节点接收 request 或回覆 response 时，若目前收到的最大 counter 值大於自已的值，要立马对齐自己 counter 值至最大值。

如上图 9-8， 当 Client A 从节点 2 接收到 counter 值为 5，然它会发送最大值 5 给节点 1，那时节点 1 counter 值 是 1， 所以它会加 5 变成 6，然後再回传回去。

因为最大 counter 值会在每一个操作中被携带，所以该方案能确保 Lamport timestamp 的排序与因果关系一致。