分布式系统时空观
我们把分布式系统中，根据因果关系推导出来的事件顺序定义为偏序（partial ordering），一个合理的分布式系统的设计原则是，根据偏序足以理解该分布式系统是否状态正确，并发独立的事件顺序不应该影响对分布式系统状态正确的理解。
另一方面，一个实现了所有事件全排列的全序（total ordering）也是有意义的，能够指导我们准确实现分布式系统。可以认为，全序是一种特殊的偏序，即包括了原先的因果约束的时间顺序，也给并发独立的事件顺序提供了一个唯一、明确仲裁机制。
事实上，在跨机房跨地域场景下，HLC或者TrueTime可以认为是目前已知的实际可行的唯二的方案选举。
单调逻辑时钟
即独立的,全局生效的逻辑时间戳生成器,需要满足以下条件:
- 对于节点Pi,逻辑时间戳在两个连续时间之间自增
- 如果Pi向Pj发送消息m,需要携带自己的逻辑时间戳, 这样Cj可以更新自己的逻辑时间为max(Ci,Cj) + 1
- 对于不同节点, 可以按节点编号, 即使逻辑时间相同, 也可以按节点编号实现偏序->全序
TSO(Timestamp Service Oracle)
通过一个中心授时的服务器提供时间戳服务, TSO架构简单, 并且可以提供严格线性一致的时间戳, Google的Percolator，TiDB，Oceanbase 2.0，PolarDB-X，Postgres-XL等等，均采用了TSO的时间戳解决方案。
缺点:
- 是会引入网络开销, 不过对于数据中心而言延迟非常小, 可以忽略不计。
单点故障， 可以引入多副本状态机， 通过Paxos/Raft共识协议实现分布式可靠性，但是重新选取Leader过程TSO不可用
- 为了性能保证，现在会提前生成一系列序列号，所以一旦需要重新选主，需要获取leader预存上限值，基于此重新生成
- 但是分布式共识其实只是多数派写，如果使用预取在窗口期可能导致双主(原始旧leader发号,也无法提交raft日志, 预取后直接内存发号了),所以需要进一步引入租约, 即等待旧leader租约到期新leader才能发号
- 但是租约又依赖真实时钟,所以租约长度需要大于最大时钟漂移长度
HLC(Hybrid Logical Clock)：尽可能用真实时间但绝不回退，其次用计数器保证因果序
逻辑时钟进阶版, 实现了去中心化，同时考虑物理时钟和逻辑时钟保证因果序。HLC包含wall time（节点视角的系统最大物理时间）和logic time（进阶比较）两部分。
具体实现而言，HLC实现中实际为每个事件准备了三个维度的计量：事件 j 发生时的物理时钟值 pt.j，事件 j 发生时节点所感知到的系统最大物理时钟值 l.j，事件 j 的逻辑时钟部分 c.j，这里 c.j 是用于几个事件在同一个物理时钟值内发生时比较之间的因果关系。
本地事件or发消息： 真实时间没超过我计数器加1，否则跟上并且计数归0
- 先看自己的物理时间pt, 如果物理时间小于记录的已知最大物理时间,那么只能更新逻辑时间表示发生了一件事
- 物理时间大于已知最大物理时间, 那么更新最大物理时间，同时把逻辑时间归0（重新计数）
收到其他节点的消息
- 需要考虑我当前的HLC，对方节点HLC，我的真实时间，这里产生4种情况
- 如果li = lm = pti, 即物理时间一样，那么说明产生额外事件，此时去最大的逻辑时间并加1: cⱼ = max(cⱼ, cₘ) + 1
- Pti <= li && li >= lm，即我的记录的是系统最大时间，不需要更新li，那么ci = ci + 1
- Pti <= lm && li <= lm, 即对方时间更大， 我需要跟上，更新li = lm，ci = cm + 1
- 其他情况，通常是真实时间pti最大，li = pti， ci = 0
示例
HLC的问题是- 如果某个节点物理时钟偏移太大，导致所有HLC值出现问题,实践中，可以设置HLC物理部分偏差的上限，如果收到的消息物理部分值的偏差超过上限，忽略这条消息，同时系统发送告警等待人工介入处理。
TrueTime
它是由硬件和算法组成的高精度物理时钟, 时钟硬件由GPS时钟和原子钟组成, 理论上同时故障可能性很低, 所以更加可靠, 2012年论文发表时，TrueTime的时钟的误差范围是1ms到7ms，平均4ms。
大部分TimeMaster机器安装了GPS天线和接收器。剩下的TimeMaster机器安装了原子钟。TimeMaster之间会相互校验时间，如果某个TimeMaster发现自己的本地时间和其他TimeMaster相比差异很大，会把自己设置为离线，停止工作。客户端向多个TimeMaster查询，防止某个TimeMaster出现故障影响结果
这个系统返回的是时间区间，真实物理时间一定会落入这个区间中，所以误差不会超过区间差值，其他节点接受到消息后，会等到到区间右边界以保证全局序列2025-10-13T00:23:13.png
数据库的应用
很大程度上，数据库领域的时间戳跟快照隔离是紧密相连的。快照隔离（SI，Snapshot Isolation）业界主流的数据库，单机如MySQL、MongoDB，分布式如TiDB、OceanBase，几乎都实现了Snapshot Isolation这一级别的隔离。领域里面的经典之作Clock-SI（参考文献[4]）指出，Snapshot Isolation的正确性包含三点：
- Consistent Snapshot：快照由SnapshotTS标识，事务可见的快照具备一致性的含义是快照包含且仅包含Commit先于SnapshotTS的所有事务；
- Commit Total Order：所有事务提交构成一个全序关系，每次提交都会生成一个新的快照，由CommitTS标识；
- Write-Write Conflict: 事务Ti和Tj有冲突，即它们writeset有交集，且[SnapshotTS, CommitTS]有交集；两个并行事务不允许writeset存在交集，且[SnapshotTS, CommitTS]也不允许有重叠；
相应地，Clock-SI(类HLC算法)(PostgreSQL使用)给出了一个精巧的保证SI的Read和Commit两部分协议，厉害之处在于仅依赖物理时钟，并且在特定条件下触发delay来保证快照一致，时钟误差不影响正确性。Clock-SI的算法如下： - StartTS：直接从本地时钟获取；
- Read：当目标节点的时钟小于StartTS时，进行等待；当事务处于Prepared或者Committing状态时，也进行等待；等待结束之后，即可读小于StartTS的最新数据；这里的Read Delay是为了保证Consistent Snapshot；
- CommitTS：区分出单Partition事务和分布式事务，单Partition事务可以使用本地时钟作为CommitTS直接提交；而分布式事务则选择max{PrepareTS}作为CommitTS进行2PC提交；为了保证CommitTS的全序，会在时间戳上加上节点的id，和Lamport Clock的方法一致；
- Commit：不论是单partition还是多partition事务，都由单机引擎进行WW冲突检测；
参考文献: https://mp.weixin.qq.com/s/3dGpV4hSgNOlwkSJ9pjPrw