Lamport 时间戳

概述

Lamport 时间戳(Lamport Timestamp)是 Leslie Lamport 在 1978 年的论文《Time, Clocks, and the Ordering of Events in a Distributed System》中提出的逻辑时钟机制。该论文指出分布式系统中不存在可靠的全局物理时钟,事件顺序应由消息传递形成的因果关系(happened-before 关系)来定义,是分布式计算领域被引用最多的论文之一。

规则

每个进程维护一个本地计数器:发生本地事件时计数器加一;发送消息时把计数器值附在消息上;接收消息时取本地计数器与消息时间戳的较大值再加一。这样保证:若事件 a 因果先于事件 b,则 a 的时间戳严格小于 b。配合进程编号作决胜值,可为所有事件构造一个全序。

局限与影响

Lamport 时钟的反向推断不成立:时间戳小并不代表因果在前,也无法判断两个事件是否并发,这一缺陷由后来的向量时钟弥补。尽管如此,其思想影响深远:分布式互斥、状态机复制、数据库事务时间戳排序都以其为基础。