本文是MIT6.824 对于线性一致讨论的内容记录，翻译内容来自于文末的参考资料，文中也夹杂了自己里理解描述。此时我还没有做Lab3，对课程中所说的重复请求处理还并不理解，希望做完Lab3后能理解这个问题。
如何确定分布式系统的运行是正确的？
当一个副本服务或者任意其他服务正确运行意味着什么？绝大多数时候，我都避免去考虑太多关于正确的精确定义。但是事实是，当你尝试去优化一些东西，或者当你尝试去想明白一些奇怪的corner case，如果有个正确的方式定义什么是正确的行为会比较方便。例如当客户端通过RPC发送请求副本服务时，可能是请求重发，可能是服务故障正常加载快照，或者客户端发送了请求并且得到了返回，但是这个返回是正确的吗？我们该如何区分哪个返回是正确的？所以我们需要一个非常正式的定义来区分，什么是对的，什么是错的。
我们对于正确的定义就是线性一致（Linearizability）或者说强一致（Strong consistency）。通常来说线性一致等于强一致。一个服务是线性一致那么它就表现只有一个服务器，并且服务器没有故障，这个服务器每次执行一个客户端请求，并没有什么奇怪的事情发生。
线性一致性的定义
**一个系统的执行历史（execution history）是一系列客户端的请求，或者这是来自多个客户端的多个请求。如果执行历史整体可以按照一个顺序排列，且排列顺序与客户端请求的实际时间相符合，那么它是线性一致的。**当一个客户端发出一个请求，得到一个响应，之后另一个客户端发出了一个请求，也得到了响应，那么这两个请求之间是有顺序的，因为一个在另一个完成之后才开始。一个线性一致的执行历史中的操作是非并发的，也就是时间上不重合的客户端请求与实际执行时间匹配。并且，每一个读操作都看到的是最近一次写入的值。
线性一致的例子1
下面是一些例子来讨论以下的这些执行历史是否是线性化的。
下图使用W表示写操作，R表示读操作，竖线左端表示操作开始，竖线右端表示操作结束。首先有一个请求将x设置为1，此后还有另一个写操作将x设置为2。在其他客户端发送了一个读请求，读取到x的值为2，还有一个客户端读取到的值为1。
如果我们观察到了这样的输入输出（执行历史），那么这样的执行历史是线性一致的吗？生成这样结果的系统，是一个线性一致的系统吗？或者系统在这种场景下，可以生成线性一致的执行历史吗？
要达到线性一致，我们需要为这里的4个操作生成一个线性一致的顺序。所以我们现在要确定顺序，对于这个顺序，有两个限制条件：
- 如果一个操作在另一个操作开始前就结束了，那么这个操作必须在执行历史中出现在另一个操作前面。
- 执行历史中，读操作，必须在相应的key的写操作之后。
我们需要为这四个操作生产一个顺序，其中Wx2在Wx1之后执行，因此，在总的顺序中Wx2必须是在Wx1之后执行；第一个读操作x=2，则读操作要求在Wx2之后执行；第二个读操作x=1，假定x一开始的值不是1，那么第二个读操作必须在第一个写操作之后进行，这样第一个写操作才能为第二个读操作提供x=1的结果，所以第二个读必须在第二个写之前。由此就会有了以下的顺序。如果将下图中的箭头平展将会得到这个顺序: Wx1 Rx1 Wx2 Rx2。可以发现总的执行历史是线性一致的。首先是将X写1，之后是读X得到1，之后将X写2，之后读X得到2。（这里可以这么理解，左边是一个多副本系统的输入输出，因为分布式程序或者程序的执行，产生了这样的时序，但是在一个线性一致的系统中，实际是按照右边的顺序执行的操作。左边是实际时钟，右边是逻辑时钟。）
非线性一致的例子1
首先将x写为1，再将x写为2；然后有两个读操作，第一个读操作在第一个写操作后执行，在第二个写操作之前完并且得到的结果是2，此外还有一个读操作在第一个读操作之后完成并且返回了值1。我们接下来需要讨论这四个操作是否有一个执行顺序满足线性一致。
首先将值写为2在将值写为1的写操作之后，那么在总的执行历史上，Wx2应该是在Wx1之后；再看第一个读操作返回的结果是2，那么Rx2应该是在Wx2之后（读操作要在写操作之后）；第二个读请求得到的值是1，因为返回1的操作必须要在设置1的操作之后，更为重要的是需要在写x=2之前，所以有了以下的顺序。
在上面的限制条件下，这个顺序里面存在一个循环，因此没有一个能满足线性一致的顺序满足约束条件（其实就是说冲突了）。因此这里的执行历史不是线性一致的，所以生成这样结果的系统不是线性一致的系统。但是只要去掉循环里面的任意一个请求，就可以打破循环，又可以是线性一致的了。
线性一致例子2
下图的例子中，首先是将x设置为0，然后有一个写请求将x设置为1，还有一个写请求是将x设置为2，此外还有两个读请求，但是先读到的是x=2，再读到的x是1。这让人看起来挺迷惑的，属于是线性一致的吗？
根据约束条件，我们可以得到首先写请求Wx0是最先执行的（约束1），Wx1和Wx2看起来是并发执行的，并不能直接确定两个的先后，但是可以通过两个读请求来判断，第一个读请求得到的值是2，那么必须是再读取之前就已经进行了x=2的写入，所以Wx2必定先于Rx2，然后再是Wx1，再是Rx1。将操作顺序平展得到的是Wx0 Wx2 Rx2 Wx1 Rx1，这是一个满足线性一致的。
线性不一致例子2
在上一个例子的基础上又添加了一个客户端对服务器的读，Client 2 先读取到的x=1，然后再读取到的是x=2，那么这个线性一致的吗？
线性一致的一个条件是，对于整个请求历史记录，只存在一个序列，不允许不同的客户端看见不同的序列，或者说不允许一个存储在系统中的数据有不同的演进过程。这里只能有一个序列，所有的客户端必须感受到相同的序列。而在上图中C1和C2却有着不一样的结果，也暗自说明无法找到一个线性一致的顺序。
最直观的证据是我们可以找到一个带环的顺序。
C1要读取到x=2，那么表示Wx2要先执行，C2要读取到X=1，则表明Wx1要先于Rx2，在从C1的顺序上看，Rx2要先于Rx1只能是Rx2之后立即执行Wx1，在C1上执行读请求才有可能读取到x=1；从C2的顺序上来看，后续要读取到x=2，则Wx2要先于Rx2执行，并晚于Rx1，此时就会发现这中间出现了一个环，因此无法构建一个线性一致的顺序，所以这不是线性一致的。
期间有学生提问：
学生提问：所以说线性一致不是用来描述系统的，而是用来描述系统的请求记录的？
Robert教授：这是个好问题。线性一致的定义是有关历史记录的定义，而不是系统的定义。
所以我们不能说一个系统设计是线性一致的，我们只能说请求的历史记录是线性一致的。
如果我们不知道系统内部是如何运作的，我们唯一能做的就是在系统运行的时候观察它，
那在观察到任何输出之前，我们并不知道系统是不是线性一致的，我们可以假设它是线性一致的。
之后我们看到了越来越多的请求，我们发现，哈，这些请求都满足线性一致的要求，那么我们认为，
或许这个系统是线性的。如果我们发现一个请求不满足线性一致的要求，那么这个系统就不是线性一致的。
所以是的，线性一致不是有关系统设计的定义，这是有关系统行为的定义。
所以，当你在设计某个东西时，它不那么适用。
在设计系统的时候，没有一个方法能将系统设计成线性一致。
除非在一个非常简单的系统中，你只有一个服务器，一份数据拷贝，并且没有运行多线程，
没有使用多核，在这样一个非常简单的系统中，要想违反线性一致还有点难。
但是在任何分布式系统中，又是非常容易违反线性一致性。
从上述两个例子可以学习到的是：对于系统执行写请求，只能有一个顺序，所有客户端读到的数据的顺序，必须与系统执行写请求的顺序一致。
非线性一致的例子3
下图是一个明显非线性一致的情况，首先Wx1，Wx2，然后读取到x=1。这是一个很简单的例子，它明显不是线性一致的，因为线性一致要求生成的序列与实际时间匹配，这意味着，唯一可能的序列就是写X为1，之后写X为2，之后读X得到1。但是这个顺序明显违反了线性一致的第二个限制，因为读X得到1的前一个写请求是写X为2，这里读X应该返回2，所以这里明显不是线性一致的。
在这个例子中我们能学习到的是：对于读请求不允许返回旧的数据，只能返回最新的数据。或者说，对于读请求，线性一致系统只能返回最近一次完成的写请求写入的值。
关于超时和重传的讨论
在这个例子中C1 先执行Wx3，然后Wx4；C2在C1完成Wx3后发送了一个读请求，但是始终没有收到回复。
造成这个问题的可能原因是：
- Leader在某个时间故障了
- 这个客户端发送了一个读请求，但是这个请求丢包了因此Leader没有收到这个请求
- Leader收到了这个读请求并且执行了它，但是回复的报文被网络丢包了
- Leader收到了请求并开始执行，在完成执行之前故障了
- Leader执行了这个请求，但是在返回响应的时候故障了
不管是哪种原因，从客户端的角度来看，就是发送了一个请求，然后就没有回复了。在大多数系统的客户端内部实现机制中，客户端将会重发请求，或许发给一个不同的Leader，或许发送给同一个Leader。所以，客户端发送了第一个请求，之后没有收到回复并且超时之后，或许在这里发送了第二个请求。
服务器处理重复请求的合理方式是，服务器会根据请求的唯一号或者其他的客户端信息来保存一个表。这样服务器可以记住，哦，我之前看过这个请求，并且执行过它，我会发送一个相同的回复给它，因为我不想执行相同的请求两次。例如，假设这是一个写请求，你不会想要执行这个请求两次。所以，服务器必须要有能力能够过滤出重复的请求。第一个请求的回复可能已经被网络丢包了。所以，服务器也必须要有能力能够将之前发给第一个请求的回复，再次发给第二个重复的请求。所以，服务器记住了最初的回复，并且在客户端重发请求的时候将这个回复返回给客户端。如果服务器这么做了，那么因为服务器或者Leader之前执行第一个读请求的时候，可能看到的是X=3，那么它对于重传的请求，可能还是会返回X=3。所以，我们必须要决定，这是否是一个合法的行为。
你可能会说，客户端在这里发送的（重传）请求，这在写X为4的请求之后，所以你这里应该返回4，而不是3。这里取决于设计者，但是重传本身是一个底层的行为，或许在RPC的实现里面，或许在一些库里面实现。但是从客户端程序的角度来说，它只知道从第一条竖线的位置发送了一个请求，并在第二条竖线的位置收到了一个回复，这是从客户端角度看到的所有事情。所以，返回X为3是完全合法的，因为这个读请求花费了一个很长的时间，它与写X为4的请求是完全并发的，而不是串行的。
因此对于这个读请求，返回3还是返回4是合法的得取决于读请求是从上图得位置发起得还是在下图得这种情况发起。
所以，如果你的客户端有重传，并且你要从客户端的角度来定义线性一致，那么一个请求的区间从第一次传输开始，到最后应用程序实际收到响应为止，期间可能发生了很多次重传。
参考资料
- https://zhuanlan.zhihu.com/p/208394772 肖宏辉知乎翻译
- https://www.bilibili.com/video/BV1iD4y1U7gu?p=8&vd_source=5ffb8cc8d870cbb196e9e171aff854d6 B站翻译视频
- M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3), July 1990
附件
- {% asset_link Linearizability.pdf %}