Linearizability一致性介绍二

我们在前面《分布式系统中的Linearizability一致性的概念介绍》介绍了Linearizability的基本概念，本文就来详细介绍一下我们如何来实现Linearizability。

我们再来简单回忆一下Linearizability的介绍，他其实就是说所有的replica都像只有一个一样，那么我们是否有个暴力解，就是真的只有一个拷贝，没有replica，这样不就是Linearizable的了？你是对的，哈哈，不过这个显然不是我们想要的答案，毕竟这样一来，如果这个节点出了任何问题，你整个读写就都不能继续了。

那么我们先来看看各种分布式的模型，看看他们能不能Linearizability：

单leader的replication

在单leader的系统中，假如读都是从leader来的话，或者你使用同步更新replica，那是有可能实现Linearizability的，但是注意也只是有可能，毕竟有可能leader出问题，比如leader自己还认为自己是leader，但事实上已经不是了，这种情况就有可能不是linearizability了。

同步算法（Consensus algorithms）

一些同步算法，它能够防止split brain（多个leader）和stale的replica。这种算法的保证下，就是Linearizable的，这也是我们常见的ZooKeeper的实现方式。

多leader的replication

多leader的replication通常来说都是不linearizable的。因为它们通常都是多个写到不同的leader，然后进行async的replica，这个过程甚至有冲突，所以一般来说它天然就是不Linearizable的。

无leader的replication

在无leader的实现中，一般会有r+w>n这样的设定，看起来是一个很强的一致性设置。但通常来说还是很难说它一定是Linearizable的，这主要取决于他具体是如何实现的。我们后面来详细分析。

Linearizability和Quorums

有人认为严格Quorum的读和写就能保证Linearizability，事实上不尽然，我们来看下面这个例子：

在这里，x的初始值是0。然后有一个Writer去把x更新成1了，这里的write是3个，即w=3，n=3。然后同时Reader A去读，这里r=2，所以它读了replica2和replica3，读出来的值是0或者1。在这之后，Reader B也去读，它读了Replica 1和Replica 2，很不幸，这两个replica都还没有更新，所以读出来的值是0，这里就出现了问题，B在A后面读，但是它竟然读到了一个旧的值。而这里的w+r>n的，所以我们不能简单认为Quorum读写就一定会Linearizable。

CAP理论

不管你是怎样的模型，单leader也好，多leader也罢，基本上都要面临下面这些取舍：

1. 假如你的应用要求Linearizability，那么假如有replica不能和别的replica连接因为各种各样的原因，比如网络等等，那么这些replica就不能处理读请求。
2. 假如你的应用不要求Linearizability，那么任何replica都可能会被读或者写，哪怕他们之间有各种各样的连接问题，都可以继续单独进行工作。

这其实就是著名的CAP理论（Consistency，Availability，Partition tolerance），只能满足其中两个。当然这个理论最大的问题就是partition tolerance只指network连接，或者说节点之间能否通信（不涉及节点延时等等）。这里我就不展开说了，相信很多文章都会介绍这个。

Linearizability和网络延迟

虽然Linearizability很有用，但是事实上并没有多少数据库真的实现Linearizability ，主要原因还是它对性能的影响太大了。尤其在网络延迟很大的情况下，linearizable的读写所消耗的性能都很可观。而且没有什么好的算法可以解决这个问题，除非你不需要Linearizability，Okay这其实也是很多数据库最终的选择。

总结

本文把前一篇文章中没有介绍的内容再补充介绍了一下，希望大家能够对Linearizability有充足的了解。