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有充足的了解。

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *