分布式系统中的Linearizability一致性的概念介绍

分布式系统中一致性一直是一个大家热衷讨论的话题，这里的一致性是指假如你同时到两个节点读取数据，你很可能看到的是不同的数据。毕竟发生在一个节点上的写操作同步到另外一个节点总是需要时间的。

我们最常见的说法就是“最终一致性”，也就是说假如没有写操作，所有的节点在一段时间之后就会一致了。目前大多数的数据库都是支持这种一致性的，但是这个一致性非常弱。你仔细想想它其实什么都没有保证，比如你写了一个数，你再去读，读到什么值根本就没有任何保证，只是说你最终能读到一致的值，这个最终是多长时间之后谁也不知道。所以说这样的“最终一致性”其实给应用开发带来了很多困难，也有可能导致很多Bug。

那么有没有什么更强的一致性保证呢?答案是当然有，但是需要注意的是一致性越强，它的性能或者错误容忍度就会越差，毕竟十全十美总是很难。本文就来介绍一种强一致性技术：Linearizability。

概述

我们上面提到在一个“最终一致性”的系统中，你同时访问不同的数据replica，得到的值可能是不同的。那么能否有一种机制保证我们任何时候访问同一个数据replica得到的值一直都是相同的呢？这种保证的就是Linearizability背后的思想：任何时候整个系统就像只有一个拷贝一样，不管你访问哪一个replica，得到的结果都是一样的。

上面这个思想就意味着，当一个client成功完成写之后，所有的client都能够读到刚刚写的数据。为了做到这一点，就意味着我们的读总是最新的值，而不是从stale cache读到的，我们来看下面这个图：

这里就是Alice在读最终分数的时候读到的是一个新的值，而Bob在他后面读，只是读到是另外一个replica的数据，而这个replica的数据还没有更新，就导致哪怕Bob在后面读还是读到了一个旧的值。这就是一个典型的不符合Linearizability的例子。

更加复杂的Linearizability

我们上面理解了Linearizability的基本概念，其实在真正的实现中还是需要更加小心。先来看下面这个例子：

上面这个图中的小柱状体开始表示请求发送的时间，结束表示收到了response，这里我们也可以理解，因为不同的网络延时，各个client的柱状体的时间长短是不一致的。在这个图中，开始的时候x的值是0，然后client A和Client B一直不停的读。整个流程如下：

1. Client A的第一个读的值是0，因为这个时候没有什么别的写发生。
2. Client A的最后一个读是1，在一个Linearizability的系统中，只要写完成了，就意味着所有的读都能别更新。
3. 中间和写有交叉的读返回值是不确定的，可能是0也可能是1.

这种可能是0也是1的读其实也是不符合Linearizability的要求的，你想假如是只有一个replica，你可能一会读到0一会儿读到1吗？显然是不会的。只会说某一个时刻变成1之后，它就不会再变回0（没有新的写的话）。所以，为了达到这个目的，我们需要再加一些限制，如下图所示：

这里就保证了，只要有一个读到了1，那么随后的所有读都只会读到1，就如上图中箭头所示，Client A在这个时间点读到了1，那么后续的所有的读都必须看到的是1。

我们下面继续来看一个更加复杂的例子，这里引入了一个新的操作cas(x, y, z) => r，这个意思是假如x==y，那么把x设为z，这个操作的结果是r。

总的思想还是一样的，只要写被一个读看到了，那么所有的读都必须看到它。这里还有几个点比较有意思：

1. 最开始的时候Client B读到的值是1，这个读操作和两个写操作有交叉，就是Client A和Client D的操作。这个还是比较合理的，我们可以认为Client D的写操作先到，然后Client A的写，这个时候x就是1了，最后才是client B的读操作。这个顺序虽然和他们的发送操作时间顺序不同，但是可能因为网络延时等等，最终成为这样的顺序是可以接受的。
2. Cinet B在读到1之后，Client A才返回ok的response。这个顺序也是接受的，因为有可能Client A返回的response被网络延时了。
3. Client B的最后读到2是不符合Linearizability的要求的，为什么呢？因为这个读和Client C的写是有重合的，假如没有别的读，那么返回2是合理的，但是Client A在它之间已经读到了Client C这边的更新，就意味着已经有Client看到了4，那么它之后的所有Client都必须是看到4才符合Linearizability的要求。

Linearizability的使用场景

在详细了解了Linearizability的例子之后，我们来看一下一些Linearizability很重要的使用场景：

锁和leader选举

在单leader系统中，我们需要保证只有一个leader，很多时候leader是通过一个锁来实现的，就是谁得到了锁，谁就是leader，这里对锁就有一个要求，就是必须Linearizable的：所有的节点都必须同意这个节点拿到了锁，否则就会有问题。

Constrains和Uniqueness的保证

唯一性在我们 现实中很常见，比如说你的用户名和邮箱必须是唯一的，一个文件目录中的文件名字必须是唯一等。这些实现都需要Linearizability的保证。其实它和抓一个锁是类似的，想加入一个用户名，就先抓住一个修改这个用户名的锁。

跨通道的依赖

我们来看下面这个例子，你有一个网站，然后可以修改头像，当你上传了新的头像后，有一个后台的线程来压缩照片（这样大小会变小，下载速度会变快），整个系统的架构如下图所示：

一般来说，Web Server得到照片之后，会首先把文件写到file的storage中，然后把一个resize的message放到message queue中，当image resizer得到message之后就会去file storage获取图片，然后resize图片。假如这个file storage不是linearizable的，那么当image resizer去读的时候就有可能读到一个旧的图片或者什么都读不到。当然我们也有别的实现方案去保证这样的场景，但是Linearizable是简单的方法。

总结

本文详细介绍了Linearizable的概念和常见的使用场景，希望大家能够在阅读之后对其有深入的了解。