向量时钟 (Vector Clock)

概述

向量时钟(Vector Clock)是分布式系统中用于捕获事件之间因果关系(happened-before 关系)的逻辑时钟机制,由 Colin Fidge 与 Friedemann Mattern 于 1988 年分别独立提出,是 Lamport 逻辑时钟的扩展。

工作原理

在 N 个节点的系统中,每个节点维护一个长度为 N 的整数向量。节点发生本地事件时,将自己对应的分量加一;发送消息时附带整个向量;接收消息时,对向量逐分量取本地值与消息值的最大值,再将自身分量加一。比较两个向量时:若一个向量的所有分量都小于等于另一个且至少一个严格小于,则前者因果先于后者;若互不满足,则两个事件是并发的——这正是向量时钟相对 Lamport 时钟的关键优势。

应用

向量时钟广泛用于检测分布式副本的写冲突。Amazon Dynamo 论文使其广为人知:Dynamo 用向量时钟为对象的多个版本标注因果历史。其缺点是向量大小随节点数线性增长,实践中常配合修剪策略。