向量时钟与分布式时序

约 1741 字大约 6 分钟

distributedvector-clock

2025-05-26

概述

在分布式系统中，由于没有全局时钟，确定事件的先后顺序是一个基本挑战。Lamport时间戳和向量时钟是解决这一问题的经典方案。它们在分布式数据库的冲突检测、因果一致性保证、版本控制等领域有着广泛应用。

物理时钟的局限性

分布式系统中不能依赖物理时钟来确定事件顺序：

时钟漂移（Clock Drift）：不同机器的时钟运行速度不同
NTP同步误差：NTP（网络时间协议）通常有几毫秒到几十毫秒的误差
闰秒：时间调整可能导致时间回退

Lamport时间戳

Leslie Lamport在1978年提出的逻辑时钟方案，是向量时钟的前身。

规则

每个进程维护一个本地计数器 C
每次发生本地事件，C = C + 1
发送消息时附带当前 C 值
接收消息时，C = max(C, 消息中的C) + 1

public class LamportClock {
    private long counter = 0;

    // 本地事件发生
    public synchronized long tick() {
        return ++counter;
    }

    // 发送消息前获取时间戳
    public synchronized long sendTimestamp() {
        return ++counter;
    }

    // 接收到消息时更新时钟
    public synchronized long receiveTimestamp(long receivedTimestamp) {
        counter = Math.max(counter, receivedTimestamp) + 1;
        return counter;
    }
}

局限性

Lamport时间戳只能判断因果关系的充分条件：

如果 a -> b（a先于b），那么 L(a) < L(b) ——正确
但 L(a) < L(b) 不能推出 a -> b ——可能是并发事件

这就是向量时钟解决的问题。

向量时钟

向量时钟（Vector Clock）由Friedemann Mattern和Colin Fidge在1988年独立提出，能够准确判断两个事件之间的因果关系。

原理

每个进程维护一个向量，向量的每个分量对应系统中的一个进程。

public class VectorClock {
    private final Map<String, Long> clock;
    private final String processId;

    public VectorClock(String processId, List<String> allProcesses) {
        this.processId = processId;
        this.clock = new HashMap<>();
        allProcesses.forEach(p -> clock.put(p, 0L));
    }

    // 本地事件
    public Map<String, Long> tick() {
        clock.merge(processId, 1L, Long::sum);
        return new HashMap<>(clock);
    }

    // 发送消息
    public Map<String, Long> send() {
        clock.merge(processId, 1L, Long::sum);
        return new HashMap<>(clock); // 附带在消息中
    }

    // 接收消息
    public void receive(Map<String, Long> otherClock) {
        // 取每个分量的最大值
        otherClock.forEach((process, timestamp) ->
            clock.merge(process, timestamp, Math::max));
        // 自己的分量+1
        clock.merge(processId, 1L, Long::sum);
    }

    /**
     * 比较两个向量时钟的因果关系
     * @return -1: vc1 < vc2 (vc1先于vc2)
     *          0: 并发
     *          1: vc1 > vc2 (vc1后于vc2)
     */
    public static int compare(Map<String, Long> vc1, Map<String, Long> vc2) {
        boolean vc1LessOrEqual = true;
        boolean vc2LessOrEqual = true;

        Set<String> allKeys = new HashSet<>(vc1.keySet());
        allKeys.addAll(vc2.keySet());

        for (String key : allKeys) {
            long v1 = vc1.getOrDefault(key, 0L);
            long v2 = vc2.getOrDefault(key, 0L);
            if (v1 > v2) vc2LessOrEqual = false;
            if (v2 > v1) vc1LessOrEqual = false;
        }

        if (vc1LessOrEqual && !vc2LessOrEqual) return -1;  // vc1 < vc2
        if (vc2LessOrEqual && !vc1LessOrEqual) return 1;   // vc1 > vc2
        if (vc1LessOrEqual && vc2LessOrEqual) return -1;    // 相等
        return 0; // 并发
    }
}

向量时钟示例

版本向量

版本向量（Version Vector）是向量时钟在数据版本控制中的具体应用，用于追踪数据副本的更新情况。

Dynamo风格的冲突检测

public class VersionedValue<T> {
    private T value;
    private Map<String, Long> versionVector;

    // 在节点node上写入新值
    public VersionedValue<T> update(String node, T newValue) {
        Map<String, Long> newVV = new HashMap<>(versionVector);
        newVV.merge(node, 1L, Long::sum);
        return new VersionedValue<>(newValue, newVV);
    }

    // 检测冲突
    public static <T> MergeResult<T> merge(
            VersionedValue<T> v1, VersionedValue<T> v2) {
        int cmp = VectorClock.compare(v1.versionVector, v2.versionVector);
        if (cmp < 0) {
            return new MergeResult<>(v2, false); // v2更新，取v2
        } else if (cmp > 0) {
            return new MergeResult<>(v1, false); // v1更新，取v1
        } else {
            // 并发冲突！需要应用层解决
            return new MergeResult<>(null, true);
        }
    }
}

混合逻辑时钟（HLC）

HLC（Hybrid Logical Clock）结合物理时钟和逻辑时钟的优点，由Kulkarni等人在2014年提出。CockroachDB和MongoDB等系统使用了HLC。

public class HybridLogicalClock {
    private long logicalTime;  // 物理时间部分
    private long counter;      // 逻辑计数器部分

    public synchronized HLCTimestamp now() {
        long physicalTime = System.currentTimeMillis();
        if (physicalTime > logicalTime) {
            logicalTime = physicalTime;
            counter = 0;
        } else {
            counter++;
        }
        return new HLCTimestamp(logicalTime, counter);
    }

    public synchronized HLCTimestamp receive(HLCTimestamp remote) {
        long physicalTime = System.currentTimeMillis();
        if (physicalTime > logicalTime && physicalTime > remote.logicalTime) {
            logicalTime = physicalTime;
            counter = 0;
        } else if (remote.logicalTime > logicalTime) {
            logicalTime = remote.logicalTime;
            counter = remote.counter + 1;
        } else if (logicalTime > remote.logicalTime) {
            counter++;
        } else {
            // logicalTime == remote.logicalTime
            counter = Math.max(counter, remote.counter) + 1;
        }
        return new HLCTimestamp(logicalTime, counter);
    }
}

对比总结

特性	Lamport	向量时钟	HLC
空间复杂度	O(1)	O(N)	O(1)
因果判断	部分（单向）	完整（双向）	部分（单向）
与物理时间关系	无关	无关	近似物理时间
可扩展性	好	受限于N	好
适用场景	全序排列	冲突检测	快照隔离/事务排序

实际应用

Amazon DynamoDB：使用向量时钟（简化版本）进行冲突检测
Riak：使用dotted version vectors优化版本向量
CockroachDB：使用HLC实现可序列化快照隔离
Cassandra：使用Lamport时间戳 + Last Write Wins策略

总结

分布式时序问题是分布式系统的核心挑战之一。Lamport时间戳提供了最简单的全序关系，向量时钟能够精确捕获因果关系和并发性，HLC则在物理时间近似和逻辑因果之间取得了良好平衡。理解这些时钟机制及其权衡，对于设计正确的分布式数据系统至关重要。

贡献者

withesse

更新日志

2026/3/14 13:09

查看所有更新日志

9f6c2-feat: organize wiki content and refresh site setup于 2026/3/14