分布式跨节点的数据排序 - Lamport Clock

小坤探游架构笔记

发布于 2025-10-11 11:32:05

1800

代码可运行

文章被收录于专栏：小坤探游架构笔记小坤探游架构笔记

运行总次数：0

代码可运行

点击上方小坤探游架构笔记可以订阅哦

在前面的多版值设计中我们聊了如何针对单主复制解决冲突的问题, 但是其存在的不足就是在Multi-Leader 或者是 Leaderless 复制模型的情况无法保证其操作前后的顺序性, 从而在解决冲突的层面上无法决策. 今天我们来聊聊Lamport Clock, 它是一个关注如何捕获操作事件的Happen Before 关系的顺序性, 从而实现跨节点的数据逻辑因果顺序. 由于篇幅有点长, 请耐心阅读!

为什么需要Lamport Clock

在讲述之前, 我们先来分析下在多个Replica节点允许写操作的场景, 比如在下面的一个Multi-Leader 双数据中心的部署架构, 我们有一个UserA 向我们系统依次发起一系列的key = x 以及 key = y 的写操作, 如下:

在上述的架构中我特意多画了终端机器, 用户的终端机器可能是电脑、平板或者手机等设备, 对于用户而言, key = x 是先于 key = y 的写操作, 如果我想看到UserA的操作序列记录, 那么按时间倒序排序依次为key = y , key = x 这样的操作记录. 也就是对于UserA 而言这一系列的操作是具备顺序性的. 如果我们在写操作的时候携带对应的时间戳是不是就可以解决问题了呢?

如果UserA只有一台设备可能问题不大, 我们直接利用携带的时间戳作为版本号, 然后根据版本号存储对应的记录, 就如同之前的多版本值设计讨论那样, 我们有了基于时间戳作为版本号的顺序性依靠, 这个时候我们可以利用时间戳本身天然的顺序性进行决策.

但是如果是多台不同设备呢? 比如UserA 在电脑发起write key = x, time = t1, 接着在手机也发起write key = y, time = t2, 这个时候我们是无法保证两个不同设备的时间戳具备连续性.

其实你也可以把对应的设备看成两台分布式的节点, 在前面我们讲述到分布式不可靠的时钟带来的问题, 系统时间戳不具备单调性, 系统时间戳表示一天中的时间，通常由带有晶体振荡器的时钟机制来测量。这种机制的一个已知问题是，它可能会偏离实际的一天中的时间。为了解决这个问题，计算机通常会配备如NTP（网络时间协议）之类的服务，该服务会将计算机时钟与互联网上的参考时间源进行同步。正因为如此，在特定服务器上连续两次读取系统时间时，时间可能会出现倒退。

由于分布式节点/设备之间的时钟漂移没有上限，因此无法比较两台不同节点/设备上的时间戳。这个时候才会考虑逻辑时钟的实现方式, 也就是今天我们讲述的Lamport Clock.

Lamport Clock实现原理

什么是Lamport Clock呢? Lamport Clock 是由莱斯利·兰波特（Leslie Lamport）在其开创性论文《时间、时钟与分布式系统中的事件排序》（[Lamport1978]）（“Time, Clocks, and the Ordering of Events in a Distributed System” [Lamport1978]）中提出了一种解决方案，即使用逻辑时间戳来追踪操作事件 “Happen Before” 的关系。因此这种利用逻辑时间戳追踪因果性的技术被称为Lamport Timestamp, 这里我称之为Lamport Clock.

根据上述的定义, 我们可以看到Lamport Clock 关注的是事件操作的Happen Before关系, 并非是为了解决数据值冲突的问题, 但由于引入顺序性从而间接帮助我们解决数据值的冲突问题, 由此我们可以得到一个隐藏的细节:

如果事件A Happen Before 事件B, 即 A -> B, 那么对于引入Lamport Clock的两个事件逻辑时钟L(a) 以及 L(b) 满足 L(a) < L(b), 从事件推导逻辑时钟的前后关系.
但是反过来如果L(a) < L(b), 那么事件A 不一定Happen Before 于事件B, 比如前面我们提及的版本号, 版本值的设置取决于服务端在CPU层面的执行顺序, 它们可能是并发关系.

从而我们得到一个结论就是: 通过Lamport Clock 我们可以捕获事件A 以及事件B 之间的Happen Before关系, 从而推导出对应的L(a) 与 L(b) 的大小, 从而间接让我们对操作的一系列值实现跨节点排序, 但是Lamport Clock 却无法帮助我们识别事件之间的并发关系.

那么如何实现一个Lamport Clock呢? 首先, 在先前多版本值设计我们提及采用MVCC存储多个版本值, 这里我们存储多版本key, 那么 多版本key(Versioned Key) 中的版本号version 则采用我们的Lamport Clock.

而MVCCStore则是作为存储多版本key以及对应的数据值的容器, 在容器中为了实现快速的范围检索, 基于Lamport Clock具备有序性的前提下, 我们采用版本号作为后缀, 即 key@version(lamport clock) , 通过key后缀的版本号使得多版本key组成一个自然排序的序列.

如下我们采用链表的方式存储组成一个不同key的多版本序列, 类似于我们LevelDB的跳表结构, 假设有k1, k2, k3 三个key, 分别对应4个递增的版本号L1, L2, L3 且满足 k1 < k2 < k3, 我们定义versionedKey值越大越靠右边, 假如这个时候我们已经向MVCCStore存储依次写入对应的一系例versionedKey, 如果此时插入<k1, L3> 没有发生层级跳跃, 那么就会在L0层插入在<k1,L2>与<k2, L1> 之间, 如下:

如果发生层级跳跃, 那么就会新建一层跳表插入对应的versionedkey, 如下:

最后我们的存储多版本的结构可能就形成如下的方式:

由此我们可以得到以下多版本Key 以及 MVCC存储的伪代码:

class VersionedKey implements Comparable<VersionedKey> {
  int ver;
  String key;

  // 自己实现版本的比较
  public int compareTo(VersionedKey other) {
    int keyCompare = this.key.compareTo(other.key);
    if(keyCompare != 0) {
      return keyCompare;
    }
    return  Integer.compare(this.version, other.version);
  }
}

class MVCCStroe {
  Map<VersionedKey,String> skipMap = new ConcurrentSKipListMap<>();
}

而Lamport Clock的实现伪代码, 其中tick是Lamport Clock的核心方法如下:

class LamportClock {
  int clock;
  public LamportClock(int clock){
    this.clock = clock;
  }

  // 实现LamportTimestamp的核心要素
  public int tick(int reqClock) {
    int max = Math.max(reqClock, clock);
    clock = max + 1;
    return clock;
  } 
}

可见Lamport Clock核心原理是接收客户端携带的reqClock, 与当前存储于服务端的clock进行比较取max值并递增1返回给客户端.

如果我们从请求的角度看Lamport Clock的操作, 同样以KV存储为例, 客户端client向两个存储副本节点, 即分别称之为Blue 以及 Green 节点, 这个时候我们很直观看到客户端操作事件上的顺序性, 如下:

此时Server节点对应操作的伪代码如下:

 public int write(String key, String value, int reqVer) {
      //update own clock to reflect causality
      int writeVer = clock.tick(reqVer);
      mvccStore.put(new VersionedKey(key, writeVer), value);
      return writeVer;
}

有了上述原理基础, 我们再回顾下之前在顺序与因果关系一致性提及的Lamport Clock例子, 其中组成的versionedKey为<Clock, NodeId> 如下:

ClientA 向Node1节点发送写入事件操作, 携带max = 0 (即Lamport Clock), 由于Node1之前没有接收到写操作, 于是max = 0 并递增1 返回ClientA 数据对 <1, 1>, 于是ClientA 以及Node1保存当前最大counter的max = 1.
ClientB 向Node2节点发送写入事件操作, 其过程也和ClientA一样, 最终Node2 以及ClientB 保存的counter最大值为max = 4.
ClientA 再次发起写入事件操作, 但是这个时候给路由到Node2, 并携带自己的counter最大值max = 1 到Node2节点上, 由于Node2最大值max = 4, 于是基于max = 4 递增1 返回给Client为 <5, 2>, 此时ClientA 存储的最大值为 max = 5.
接着我们再看ClientA 携带上一次的请求时钟max = 5 落到Node1 节点, 而Node1 节点会根据ClientA 携带的reqClock = 5 以及自身节点clock = 1 进行比较取max 得到当前的最大值max = 5, 然后递增 1 得到clock = 6 并返回给ClientA 为 <6, 1>, 由此ClinetA 存储最大值为 6 . 同理ClientB 携带max = 4 落到Node2 节点也是一样的逻辑.

不知道你在上述的例子得到了什么信息呢? 对此我自己总结如下:

不论是ClientA 还是 ClientB, 用户在往存储系统发起的系列写操作是具备顺序的, 因为我们看到不论ClientA 还是 ClinetB 其携带的clock 总是递增的.
Node1 以及 Node2 节点也各自保证自身节点clock的顺序, 也就是在自己的节点上clock 是递增的.

细心的你是否会发现, 如果我们ClientA 以及 ClientB 操作的是相同的key, 那么由于Node1 节点存储<6, 1> 以及 Node2 节点存储<6, 2> 的版本, 该以哪个为准呢? 如何进行决策呢? 正如下面的两个用户Bob 以及 Alice 分别向Node1 以及 Node2服务节点发起相同的数据key的写入操作如下:

这个其实没法衡量的, 因为我们这里需要引入对应的业务场景分析, 如果是作为分布式锁Id的获取或者是集群的leader选举投票, 那么我们可以接受用NodeId大小来判断进行决策.

但是如果是上述的Bob 以及 Alice的例子, 应用相同的key对应不同的数据值, 那么是不可行, 因为我们无法捕获到Bob 以及 Alice的写入操作事件Happen Before关系, 如果直接基于NodeId(Clock相同的条件下)的大小采用LWW机制进行判断就会导致数据丢失问题. 可见Lamport Clock无法做到全序, 仅能满足某个维度下的全序顺序性, 即接下来我们来聊聊Lamport Clock的偏序机制.

基于Lamport Clock实现偏序

首先我们有一个前提基础, 那就是基于多Replica节点都提供外部写入操作的能力, 那么我先从一个简单的场景开始.

以开头的UserA向双主部署架构的Replica发起一系列的写入操作, 这个时候我们将系统时间戳替换为Lamport Clock, 那么基于Lamport Clock的原理可知, 需要存储UserA持有的clock, 而这个clock对于持有多端设备的UserA而言是相同, 那么这个时候我们就需要增加维护一份UserA对应的clock存储:

可见我们的架构相比之前更为复杂, 因为这里引入一个额外的存储来维持UserA 以及 Clock的数据存储, 那么这个额外的存储就需要做到数据可靠性以及高可用, 防止数据丢失.

你会发现在上述的流程我不再是写write key = x 以及 key = y 而是分别用write A seq 以及 write B seq 去替换, 为什么呢? 如果A 操作 Happen Before B, 那么对应write A seq 的操作数据是什么其实没那么重要, 它可以是任意数据值, 也可以是日志记录.

如果是日志记录, 我们记录为logA 以及 logB, 由于A Happen Before B, 因此对于UserA 而言看到的操作记录按时间倒序则依次为logB -> logA, 这就是我们的偏序关系, 其中logA 以及 logB 本身就不具备可比较的属性, 但由于我们施以Clock来捕获操作事件A 与事件B 的Happen Before关系, 从而得到Lx < Ly, 因此也可推导出logA < logB, 即操作记录A是先于操作记录B, 而这个顺序仅针对UserA而言是有序的.

那如果是我想看操作同一个key的顺序性呢? 对于这种我觉得大家会更为熟悉的场景, 因为kafka的partition机制正是基于key进行hash/自定义指定分区路由到指定的partition, 类似于如下的方式, 不同的key路由到相同的IDC数据中心, 即:

从上述的架构可以看出: IDC1存储key为name的全序关系, IDC2 存储key为title也为全序关系, 即我们可以捕获到write name = xxx 以及 write title = xxx 的操作因果关系, 但无法捕获write name = xxx 以及 title = xxx 的操作因果关系.

因此我们的偏序关系取决于我们采取key的策略, 如果我们想看用户层面的全序关系, 那么就基于UserId作为key来维护对应的clock, 如果是想看某一个维度层面的全序关系, 那么就基于对应维度的key来维护对应的clock, 入比如上述的name 或者是 title各自的维度.

除了上述的场景, 我们之前也遇到过一个例子, 那就是在一个对话聊天中由于Replication Lag出现了一致性前缀读的情况, 即在一个IM系统中Mr.Poons以及Mrs.Cake都是在一个多人的群聊中, 并且聊天有这样的简短对话,如下:

Mr. Poons
How far into the future can you see, Mrs. Cake?
Mrs. Cake
About ten seconds usually, Mr. Poons.

但是在群聊的第三个用户Observer用户, 我们称之为观察者, 其发起的请求路由如下:

Mrs. Cake
About ten seconds usually, Mr. Poons.
Mr. Poons
How far into the future can you see, Mrs. Cake?

上述这种情况我们称之为一致性前缀读(Consistent Prefix Reads), 其中Mr.Poons 以及 Mrs.Cake在群聊中前后发起的对话是具备因果关系, 因此如果我们考虑采用Lamport Clock来捕获群聊发起的对话事件操作, 那么要怎么实现呢?

其实我们转换下思路, 在一个IM群聊系统中, 用户聊天上下文对话其实就是一个向群聊Id不断进行写操作的事件, 那么我们仅需要捕获到基于群聊Id的写操作事件顺序即可, 我们姑且将群聊Id称之为groupId, 那么这个时候对于Mr.Poons 以及 Mrs.Cake对话则变成如下:

那么要怎么查询呢? 同样以下是我们的一个查询流程:

这个时候我们再思考一个问题, 查询方式是不是太复杂了呢? 那我们能不能简化下, 可以考虑两种方式:

其一是基于上述groupId进行分区, 即相同的groupId路由到相同的IDC中, 那么我们的查询就仅是单个IDC数据中心查询, 此时在一个IDC中就具备一个维度的全序排序顺序的因果逻辑.
第二种方式是提供给外部系统或者伴生系统(非系统内部的, 比如在自建的电商系统中采用第三方支付系统完成支付功能, 第三方支付系统非当前系统职责范围所在, 因此这个支付系统我们称之为伴生系统)使用, 那么这个时候我们可以采用异构数据存储的方式, 通过协调者将<groupId, clock> 组成的以groupId维度, 以clock作为逻辑全序的顺序事件通过CDC的方式发送到对应的异构存储系统进行回放即可.

经过上述的不同场景分析, 可见借助Lamport Clock 的机制可以帮助我们实现跨节点的值排序, 这个值排序并不是我们所谓的自然排序, 而是一种偏序关系.

这种偏序是我们通过捕获操作事件的Happen Before 关系从而推导出事件对应的Clock之间的排序关系. 同时这种偏序关系是基于某一个维度而言, 比如上述的维度有userId、数据key以及群聊groupId, 因此在分布式系统中如果我们只是实现部分维度下的全序关系, 那么Lamport Clock的设计方式将是我们一个比较好的参考范例.

Lamport Clock应用场景与局限性

Lamport Clock 应用场景

谈完Lamport Clock原理机制, 那么它在我们分布式系统中有哪些应用呢? Lamport 时间戳的核心价值在于其简单性和对因果关系的保证。它适用于以下需要轻量级事件排序的场景, 我将自己工作中遇到的各种可能场景进行汇总如下: