分布式数据库-时钟

发表于 2025-02-17 分类于分布式数据库

时钟

该篇主要通过网上文章和deepseek问答的方式学习与记录

必要性，即为什么需要时钟系统

mvcc中区别可见性（用时间戳搜版本链）
保证事务的全局顺序，至少是因果一致性，用于确定某个事务是否可以提交或回滚

时钟系统的选择

中心化的时钟分配方案
HLC时钟方案

HLC时钟与中心化时钟的区别

在分布式系统中，时间戳分配对事务的顺序和一致性至关重要。HLC（Hybrid Logical Clock，混合逻辑时钟）和中心化时间戳分配是两种不同的时间戳管理机制，它们的核心区别体现在架构、依赖关系和适用场景上。以下从多个维度对比两者的差异：

1. 架构设计

维度	HLC	中心化时间戳分配
架构模式	分布式（无中心节点）	中心化（依赖单点或集群）
时间戳生成	每个节点独立维护本地HLC	由中心服务统一分配（如TSO服务）
通信开销	低（仅需少量同步）	高（每次事务需请求中心节点）
可用性	高（无单点故障）	低（中心节点宕机影响全局）

HLC：每个节点独立维护一个混合逻辑时钟（物理时间 + 逻辑计数器），无需全局协调。
中心化分配：依赖中心服务（如Google Spanner的TrueTime、TiDB的TSO）分配全局唯一时间戳。

2. 时间戳依赖

维度	HLC	中心化时间戳分配
物理时钟依赖	依赖本地物理时钟，允许一定偏差	通常依赖高精度时钟（如原子钟、GPS）
逻辑组件	需要逻辑计数器补偿物理时钟偏差	仅依赖物理时间（或逻辑单调递增）
时间戳精度	受限于本地时钟精度和NTP同步	由中心服务保证全局严格单调

HLC：通过逻辑计数器（l）补偿物理时钟偏差（pt），保证因果一致性。
中心化分配：通过中心服务的原子操作（如TrueTime API）生成全局单调递增时间戳。

3. 一致性与性能

维度	HLC	中心化时间戳分配
全局一致性	最终一致（依赖物理时钟同步）	强一致（中心服务保证）
延迟敏感度	低（本地生成时间戳）	高（需等待中心响应）
适用场景	高吞吐、弱网络环境（如边缘计算）	强一致需求场景（如金融交易）

HLC：适用于对延迟敏感但对全局一致性要求较宽松的场景（如IoT、边缘数据库）。
中心化分配：适用于需要严格全局事务顺序的场景（如跨区域数据库事务）。

4. 典型实现案例

HLC：
- CockroachDB：使用HLC实现分布式事务的MVCC（多版本并发控制）。
- Amazon Aurora：在跨分区事务中结合HLC与物理时钟。
中心化时间戳分配：
- Google Spanner：依赖TrueTime API分配时间戳，误差范围可控。
- TiDB：通过TSO（Timestamp Oracle）服务集中分配时间戳。

5. 核心问题与权衡

HLC的优势：
- 去中心化：无单点故障，适合大规模分布式系统。
- 低延迟：本地生成时间戳，避免网络往返开销。
- 因果一致性：通过逻辑计数器维护事件顺序。
HLC的挑战：
- 时钟漂移：依赖NTP同步物理时钟，可能引入偏差。
- 逻辑计数器膨胀：高并发场景下逻辑部分可能快速增长。
中心化分配的优势：
- 强一致性：全局严格单调的时间戳保证事务顺序。
- 简化设计：无需处理分布式时钟同步问题。
中心化分配的挑战：
- 单点瓶颈：中心服务可能成为性能瓶颈或单点故障。
- 网络依赖：跨地域部署时延迟显著增加。

6. 选择建议

选择HLC：
- 系统需要高可用性和分区容忍性（如跨地域部署）。
- 可接受一定的时间戳偏差（如最终一致性场景）。
选择中心化分配：
- 需要严格的事务全局顺序（如金融系统）。
- 物理时钟同步精度高（如部署原子钟或GPS时钟）。

总结

HLC和中心化时间戳分配的本质区别在于如何权衡一致性、可用性和性能。HLC通过分布式逻辑时钟降低对中心服务的依赖，适合大规模、高可用的场景；中心化分配通过集中式权威保证强一致性，适合对事务顺序要求严格的场景。

HLC时钟的设计

HLC 的设计理念

HLC 的核心目标是在分布式系统中实现 因果一致性，同时 避免完全依赖物理时钟（物理时钟可能不同步或存在误差）。HLC 通过以下设计理念达成这一目标：

混合时间戳：结合物理时钟（Physical Time, PT）和逻辑时钟（Logical Clock, LC），物理时间用于近似真实时间，逻辑时间用于在物理时间相同或回退时保证顺序。
无中心化依赖：每个节点独立维护自己的HLC，无需全局协调服务。
容忍时钟偏差：允许物理时钟存在一定偏差（例如通过NTP同步），但通过逻辑计数器补偿偏差。

HLC 的组成

每个HLC时间戳是一个二元组 (pt, l)：

**pt**（物理时间）：节点的本地物理时钟时间（如Unix时间戳，单位毫秒），可能因NTP调整发生跳跃或回退。
**l**（逻辑计数器）：一个整数，用于在pt相同或回退时保证时间戳的唯一性和单调递增性。

HLC 的实现规则

HLC的更新规则是核心，以下是伪代码实现逻辑：

1. 初始化

每个节点维护本地HLC值 c = (pt, l)：

class HLC:
    def __init__(self):
        self.pt = get_local_physical_time()  # 当前物理时间
        self.l = 0                           # 逻辑计数器

2. 生成新时间戳（本地事件）

当节点本地发生事件时（如事务开始）：

def new_event(self):
    # 更新物理时间为当前时间
    new_pt = get_local_physical_time()
    
    # 规则1：pt必须非递减
    if new_pt > self.pt:
        self.pt = new_pt
        self.l = 0          # 物理时间前进，重置逻辑计数器
    else:
        self.l += 1         # 物理时间未变，逻辑计数器递增
    
    return (self.pt, self.l)

3. 接收消息时间戳（跨节点事件）

当节点收到来自其他节点的消息时，消息携带对方的HLC时间戳 c' = (pt', l')：

def receive_message(self, c_remote):
    remote_pt, remote_l = c_remote
    new_pt = max(get_local_physical_time(), remote_pt, self.pt)
    
    if new_pt == self.pt:
        # 物理时间未变，逻辑计数器取最大值+1
        self.l = max(self.l, remote_l) + 1
    elif new_pt == remote_pt:
        # 远程时间更大，逻辑计数器继承remote_l+1
        self.pt = new_pt
        self.l = remote_l + 1
    else:
        # 本地物理时间更大，重置逻辑计数器
        self.pt = new_pt
        self.l = 0
    
    return (self.pt, self.l)

HLC 如何保证因果一致性？

因果一致性要求：如果事件A因果先于事件B，则A的HLC时间戳必须小于B的时间戳。HLC通过以下规则保证这一点：

本地事件顺序：同一节点内的事件，HLC时间戳严格递增（通过l递增）。
跨节点事件顺序：如果节点A发送消息给节点B，则B在接收消息时会将自己的HLC更新为 max(A.pt, B.pt)，并递增逻辑计数器，确保后续事件的时间戳更大。
物理时间的单调性：即使物理时钟回退（如NTP调整），HLC的pt部分只会取当前时间或消息中更大的时间，避免回退。

HLC 与 NTP 的依赖关系

HLC 不完全依赖NTP的严格同步，但需要NTP将物理时钟误差控制在合理范围内：

物理时钟同步：NTP用于校准节点的本地物理时钟，减少不同节点之间的物理时间偏差（例如误差在几百毫秒内）。
容忍时钟回退：当NTP调整导致本地物理时间回退时，HLC通过逻辑计数器补偿：
- 如果本地物理时间回退（例如从 t=100 回退到 t=90），HLC的pt仍然保持之前的值（pt=100），直到本地物理时间再次超过当前pt。
- 逻辑计数器l会在pt未更新时递增，确保时间戳不重复且单调递增。

HLC 的伪代码流程示例

假设两个节点A和B，物理时钟初始同步，但之后B的时钟因NTP调整回退：

步骤	事件	节点A的HLC `(pt, l)`	节点B的HLC `(pt, l)`
1	初始状态	(100, 0)	(100, 0)
2	A发生本地事件	(100, 1)	-
3	A发送消息给B，携带 `(100, 1)`	-	B收到消息后更新为 `(100, 2)`
4	B的物理时钟因NTP回退到90	-	B本地事件生成 `(100, 3)`（物理时间未更新，逻辑计数器递增）
5	B物理时钟恢复后达到101	-	B本地事件生成 `(101, 0)`（物理时间前进，重置逻辑计数器）

HLC 的优势与限制

优势：
- 无单点故障，适用于分布式系统。
- 容忍物理时钟偏差，同时保证因果一致性。
- 时间戳空间占用小（仅需存储pt和l）。
限制：
- 逻辑计数器可能因高并发快速递增（需优化存储）。
- 依赖NTP将物理时钟误差控制在合理范围内。

实际应用案例

CockroachDB：使用HLC实现多版本并发控制（MVCC），确保事务的全局顺序。
分布式日志系统：通过HLC标记日志顺序，避免跨节点时钟偏差问题。

总结

HLC通过 混合物理时间和逻辑计数器，在容忍物理时钟偏差的同时保证了因果一致性。其核心实现规则是：

本地事件时优先使用物理时间，逻辑计数器仅在物理时间不变时递增。
跨节点通信时，通过比较远程和本地时间戳，更新为更大的物理时间，并重置或递增逻辑计数器。

这种设计使得HLC在分布式系统中既能避免中心化时间戳服务的性能瓶颈，又能提供足够的一致性保证。

HLC实现的两阶段提交

1. 两阶段提交流程（基于HLC）

事务T1的执行

1. 事务开始

协调者C 生成事务T1的start_ts = (100, 1)（HLC初始为(100, 0)，调用new_event()后递增为(100, 1)）。

2. 准备阶段（Phase 1）

协调者C 发送准备请求（携带start_ts=(100, 1)）给P1和P2。
参与者P1：
- 收到消息后更新HLC：P1.receive_message(100, 1) → HLC=(100, 2)。
- 锁定数据X，回复“YES”并返回当前HLC=(100, 2)。
参与者P2：
- 收到消息时本地HLC=(90, 5)（物理时钟滞后）。
- 更新HLC：P2.receive_message(100, 1) → pt=max(90, 100)=100，l=max(5,1)+1=6 → HLC=(100, 6)。
- 锁定数据Y，回复“YES”并返回当前HLC=(100, 6)。

3. 生成提交时间戳

协调者C 收到P1和P2的“YES”及它们的HLC=(100,2)和(100,6)。
协调者C 生成commit_ts = max((100,2), (100,6)) = (100,6)，确保其大于所有参与者的HLC。

4. 提交阶段（Phase 2）

协调者C 发送提交请求（携带commit_ts=(100,6)）给P1和P2。
参与者P1：
- 收到commit_ts=(100,6)，更新HLC：P1.receive_message(100,6) → pt=100，l=max(2,6)+1=7 → HLC=(100,7)。
- 将数据X的提交时间戳设为(100,6)，释放锁。
参与者P2：
- 当前HLC=(100,6)，收到commit_ts=(100,6)后更新HLC：l=max(6,6)+1=7 → HLC=(100,7)。
- 将数据Y的提交时间戳设为(100,6)，释放锁。

结果：事务T1成功提交，无冲突。

2. 关键点说明

提交时间戳的生成逻辑

逻辑：协调者必须收集所有参与者在准备阶段返回的HLC，取最大值作为commit_ts，确保其足够大。

HLC的更新规则

在提交阶段，参与者收到commit_ts后，需根据HLC规则更新本地时钟：

def receive_commit(self, commit_pt, commit_l):
    new_pt = max(get_local_physical_time(), commit_pt, self.pt)
    if new_pt == self.pt:
        self.l = max(self.l, commit_l) + 1
    elif new_pt == commit_pt:
        self.l = commit_l + 1
    else:
        self.l = 0
    self.pt = new_pt

参与者接受commit_ts后，其HLC会更新至更大值，避免后续事务因时间戳冲突回滚。

3. 并发事务示例（事务T2）

假设事务T2在T1提交后发起，由另一个协调者C’处理：

1. 事务开始

协调者C’ 生成start_ts=(100,7)（基于本地HLC）。

2. 准备阶段

参与者P1：
- 当前HLC=(100,7)，数据X已提交（版本X@(100,6)）。
- 检查无写冲突，锁定X的新版本，回复“YES”并返回HLC=(100,8)。
参与者P2：
- 当前HLC=(100,7)，数据Y已提交（版本Y@(100,6)）。
- 检查无冲突，锁定Y的新版本，回复“YES”并返回HLC=(100,8)。

3. 提交阶段

协调者C’ 生成commit_ts=max((100,8), (100,8)) = (100,8)。
参与者更新数据版本至(100,8)，事务T2成功提交。

4. 协调者并发处理的可行性

多协调者并发

无锁设计：每个协调者独立生成start_ts和commit_ts，只要按HLC规则生成时间戳，事务顺序由时间戳自然决定。
冲突解决：
- 若两个事务操作同一数据，参与者会根据commit_ts大小决定哪个事务优先提交。
- 例如，若T1的commit_ts=(100,6)，T2的commit_ts=(100,8)，T2的写入会覆盖T1。

示例场景

协调者C处理T1，协调者C’处理T2。
T1的commit_ts=(100,6)，T2的commit_ts=(100,8)。
数据版本按时间戳排序，T2的更新对后续事务可见。