Implementing Linearizability at Large Scale and Low Latency

​ CAP理论中的强一致性C，也就是线性一致性（linearizability）想必大家都有所耳闻，但是如何实现linearizability是一个问题，在ATC 2014，Raft extended version[1] (第8章Client interaction) 有一个简单的方案描述：

The solution is for clients to assign unique serial numbers to every command. Then, the state machine tracks the latest serial number processed for each client, along with the associated response. If it receives a command whose serial number has already been executed, it responds immediately without re-executing the request.

​ 翻译成中文大概是：

就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不是重新执行指令。

​ 但是没有任何其它细节，到2015，他们团队Platform Lab在SOSP 2015发表了他们的解决方案Reusable Infrastructure for Linearizability（RIFL）[2]。

​ 实际上，几年前开发Raft协议框架的时候有看过RIFL这个方案；最近”挖坟“出来聊这个话题，是因为最近测试过程中遇到一个因为rpc回退造成stale request覆盖新写而出现数据一致性的问题，大概的场景是client-server结构，client发送rpc request给server，server将收到的rpc request解析写入后端的分布式存储系统，client和server之间走rdma网络，stale request造成数据一致性问题的大致过程如下：

1. client发送一个write req A 给server
2. write req A进入rpc框架queue排队，因为RDMA网络原因，write req A还没来得及发送出去，就超时了（而此时：rpc框架也因为大量请求未能及时发送出去，判定网络出现问题，从RDMA退化到TCP）
3. write req A超时之后，rpc框架发起重试，走TCP发送write req A retry，很快write req A retry发送到了server，server端成功处理后给client返回成功
4. client又来一个write req B覆盖写这个range，很快req B被server端处理完成了，并向client返回成功
5. （坑爹的来了）rpc框架内部判定网络恢复正常，又恢复到RDMA模式，在rpc框架queue里面排队的write req A没有被扔掉，又开始重新被处理，发送给server端，导致stale req（write req A）覆盖新写write req B的数据写入，造成了数据覆盖写丢失

​ 上面这个问题就是今天又”挖坟“来聊linearizability实现的背景，因为如果不想改rpc框架实现，解决这个问题首先想到的就是RIFL方案。

2. Exactly once

​ 在讲如何实现Linearizability前，先简单回顾下Linearizability是什么 ？[2] （图片来自[3]）

each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response

​ 如上定义Linearizability强调是的exactly once，也就是只能执行一次（exactly once between its invocation and its response ），相对比的就是at-least-once semantics，一般rpc都是这种语义，所以rpc框架client可以无脑重试，直到它认为server端成功接收到，rpc框架并不关心server端之前是否成功接收到。

​ 显然上面stale request的例子就违背exactly once。我们知道Raft协议保证了多副本强一致性，每一个op req原子和瞬间的被执行，且一旦执行成功，对所有的client可见，但是Raft协议并不感知业务的request是否是同一个，所以并不能拦截stale request，做不到业务层的exactly once，所以需要和client配合，感知到request的唯一性，来实现exactly once，从而实现业务上的Linearizability。

​ 更多Linearizability定义这里就不展开了；之前有写两篇专门讨论，可以移步到：线性一致性：什么是线性一致性？ 、分布式线性一致性：理论&验证

3. RIFL

RIFL实现Linearizalibity的方法一句话概述就是Raft论文的那句话：

就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

具体到RIFL的细节，就有如下几个问题需要解决：

• （1）Unique identification for each RPC

​ 要保证server能知道req是否被执行过，首先就需要client给每个req生成一个唯一的标识，这个好说，通过client id + seq num组合一般不难做到，client id全局唯一，seq num单调递增即可。

• （2）Durable completion record

​ 在 Server端，每个req都会有一个对应Completion Record（CR）记录并持久化。CR组成：

1. request 唯一标识
2. 操作对象唯一标识

这样做得目的不难理解，就是如果全部都持久化了，那下次stale req过来，server就可以拒绝了。

• （3）Retry Rendezvous

​ 简单持久化，肯定不够，因为在分布式系统中crash recovery是常态，解法也很简单，就是CR走Raft或者其它数据复制协议和Op log一起复制给多副本，这样，无论发生什么样的failover，Raft协议可以保证CR在多个副本的一致。在发生failover之后，新主只需要回放raft log的就可以得到最新一致的CR，这样client的stale req就可以被server拦截掉了。

• （4）Garbage Collection

​ CR如何回收也是一个问题 ？

1. client每次收到server OK之后，会更新firstIncomplete req id，也就是最小未完成的req id，并且firstIncomplete req id会通过一定的机制定期的告诉server端（例如每次通过给server发送req捎带过去）
2. 这样server端就可以把小于firstIncomplete req id全部回收掉了，而对于client再发送小于firstIncomplete req id的request，就可以认定为stale req直接扔掉了

• （5）整体流程

​ 再来看整体流程就不复杂了：

1. client发送request携带上唯一标识
2. server收到request之后执行checkDuplicate

a. 如果request的id没有记录，且大于firstIncomplete，那么说明是第一次见，server直接处理request

b. 如果request已经被处理过了，那么直接返回之前的处理结果

c. 如果request正在被处理，还没处理完，那么直接忽略这个request

d. 如果request的id没有记录，且<firstIncomplete，那么说明是stale request，向client返回error

​ RIFL整体思路介绍完了，更多的细节，感兴趣的可以参考论文。

• notes

限于作者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献中列表注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处

[1]. Ongaro D, Ousterhout J. In search of an understandable consensus algorithm (extended version)[J]. 2013.

[2]. Lee C, Park S J, Kejriwal A, et al. Implementing linearizability at large scale and low latency[C]//Proceedings of the 25th Symposium on Operating Systems Principles. 2015: 71-86.

[3]. PPT for SOSP 2015 "Implementing Linearizability at Large Scale and Low Latency".https://ramcloud.atlassian.net/wiki/spaces/RAM/pages/6848659/RAMCloud+Presentations?preview=/6848659/24248380/SOSP15_seojin.pptx