This post is the 1 / 3 post in Paper Reading Series.

一个遥远的城邦过着自给自足的生活,每个人都独立自主,诚实守信,互相信任,城邦中所有的事情都通过民主的方式决定。但是他们基础设施很差劲,投出去的票经常路上就丢了(丢包);每个人又时不时的很忙,导致收到了提案也没功夫投票(节点下线);城邦还总是发生地震,导致交通彻底断开(网络分区)。所以聪明的他们为了解决这个问题想了很多办法,一个思路是多数派原则,任何一个提案只要有多数派通过了,那它就会生效,还有一个思路是先票选出交通发达,有钱有闲,大陆架稳定的人,然后采取一票否决制,只要有一个人不同意,那提案就不会通过。

今天将要介绍的 Hermes 采用的是第二种思路,先通过其他的协议(比如 Vertical Paxos)选举出一组稳定的成员,然后在成员中进行广播。


外星人问题

有一个这个遥远的城邦来了个外星人,他对这种民主体制非常感兴趣,所以他找来了一个城邦居民,问了他一些问题:

  • 提案 允许外星人加入城邦 这个提案通过了吗?(读)
  • 能不能帮我提交 允许外星人加入城邦 这个提案并投赞同票?(写)
  • 能不能帮我看一下提案 允许外星人加入城邦 通过没有,如果没过就帮我提一个(原子操作: RMW,Read-Modify-Write)

外星人问题实际上对应业务中的一种常见需求:分布式 K-V 或者分布式锁。而 Hermes 主要关心的就是在分布式内存存储:各个节点都在同一个数据中心,客户端主要通过发送读/写请求与节点交互,通常的,这些节点还会将数据存储在内存中,并使用 RDMA 或 DPDK 来实现低延迟高吞吐。

Hermes 协议细节

面对外星人的诚恳请求,这位城邦居民动了恻隐之心,所以他决定帮助这位外星人。按照城邦 Hermes 规定,作为接收这个请求的人,他成为了这个提案的发起者(Coordinator)。在完成一些 paper work 之后,他首先向议会(Followers)中的所有人发送草案,在收到了大家确认收到的请求之后,他就告诉外星人这个提案已经被通过了,然后他向议会所有人发出了最后生效的议案。

基本概念

Invalidations

如上图所示,Coordinator 会向 Followers 广播两次:第一次叫做 Invalidation (INV),Follower 收到 INV 之后会将这个 Key 设置为 Invalid 状态,意味着这个 Key 当前不能对外提供服务;第二次叫做 Validation (VAL),Follower 收到 VAL 之后会更新这个 Key 的状态为 Valid,此时才会真的对外提供服务。只有当 Key 处在 Valid 状态时,节点才会返回这个 Key,否则都会 block 住。

为了解决并发问题,Hermes 引入了逻辑时间戳:

Logical timestamps

Hermes 中的每次写都会附加一个基于 Lamport Timestamp 的逻辑时间戳,这个时间戳仅在 Coordinator 节点内部进行计算,不需要外部的服务或节点参与。这个时间戳由每个 Key 的 Version Number 和节点的 Node ID 组成。其中 Key Version Number 会在每次写的时候自增,而 Node ID 则在节点启动时进行分配。当两个时间戳进行比较的时候,遵循这样的原则:总是先比较 Key Version Number,若 Key Version Number 一致,则比较 Node ID。

为了避免公平性问题,论文中提出可以采用虚拟 Node ID 的方案,比如说给 Node 1 分配 {1,4,7,10},给 Node 2 分配 {2,5,8,11},给 Node 3 分配 {3,6,9,12}。在每次 Write 的时候随机选择一个作为本次请求的 Node ID。

请求处理

在 Hermes 协议中,所有的读请求都在本地完成:当 Key 处于 Valid 状态时返回,否则就 block。当 block 的时间超过给定的 mlt (message-loss timeout) 时,这个节点会重放自己收到的 INV 请求,开始执行一次 Write 操作,当 Write 操作完成的时候,这个 Key 会变为 Valid 状态并返回。与 Read 相似的是,只有当 Key 处于 Valid 状态时,节点才能发起一次 Write 操作,否则就会 block。当 block 的时间超过给定的 mlt,一样会重放自己收到的 INV 请求。

在 Wirte 操作中,Coordinator 会做如下事情:

  • 更新 Key Version Number,附加上自己的 Node ID 作为本次 Write 请求的时间戳
  • 广播 INV 消息,将 Key 设置为 Write 状态,并本地 apply 新的值
  • 一旦收到所有节点的 ACK,将 Key 设置为 Valid 状态
  • 广播 VAL 消息

Follower 则会做这些:

  • 收到 INV 消息时,将消息中的时间戳和自己本地的时间戳做对比。当且仅当消息中的时间戳比本地高时将这个 Key 设置为 Invalid 状态并更新 Key 的时间戳和值,否则就什么都不做。
  • 无论时间戳比较的结果是什么,总是返回一个 ACK
  • 收到 VAL 消息时,当且仅当消息中的时间戳与本地一致时将 Key 更新为 Valid 状态,否则就直接忽略这个 VAL 消息。

从目前了解到的信息来看,Hermes 实现起来并不难。

RMW 操作

为了支持 RMW 操作,Hermes 协议中做了如下调整:

  • 在 Metadata 中加入了二进制标记 RMW_flag 以支持区分 RMW 操作和 Write 操作
  • 在构造时间戳的时候:如果是 Write 操作,Key Version Number 会自增 2;如果是 RMW 操作,则会自增 1
  • 当且仅当 Follower 收到的 INV 消息中的时间戳比本地高时才会返回对应的 ACK,否则会返回一个基于本地存储状态的 INV
  • 在 Coordinator 等待 ACK 过程中如果收到了更高时间戳的 INV,则会直接放弃本次操作

构造时间戳的方式是一个很有意思的想法:假设对同一个 Key 出现了并发的 Write 和 RMW 操作,则 Write 总是会成功,这使得 Hermes 保证了两个特性:

  • Write 总是会成功
  • 至多有一个并发的 RMW 会成功

总结

我在读论文时遇到的最大问题是经常忘记 Hermes 依赖一组稳定的成员,而这组成员需要其他的协议来选举出来,所以 Hermes 实际上并不需要处理成员永远下线这种情况。

本文介绍了 Hermes 复制协议的读写流程与 RMW 操作的实现,其中省略了很多细节,比如故障恢复,成员变更等情况的处理还有与 ZABCRAQ 等协议的对比,想了解这些细节的同学可以阅读他们的论文。Hermes 提供了 TLA+ 来证明他们的正确性,不过我对 TLA+ 缺乏研究,所以请允许我忽略这一部分的内容。

希望本文能为大家理解 Hermes 协议有所助益~

参考资料