无leader replication的实现和问题介绍

我们在前面的《多leader replication的实现及常见问题介绍》和《分布式系统之leader-followers Replication深入介绍》分别介绍了多leader和单leader的情况，也许你会好奇是否有无leader的实现呢？答案是肯定的，本文就来深入介绍无leader replication的实现和相关的问题。

其实最早期的时候有很多无leader的实现，就是任何节点都可以进行写。后来慢慢大家就不太使用这个实现了，直到Amazon推出了它的Dynamo系统，这一实现又再次流行起来。现在Riak，cassandra以及Voldermort都是开源的无leader的数据库实现。

如何处理有节点出问题的写

在有leader的架构中，当有节点出现问题（假如在leader上），我们需要做failover，然后才能继续写。而在一个没有leader的结构中，failover就不存在，所以当有节点出问题时，整个流程如下图所示：客户端会给每一个节点发送写的请求，我们现在假设三个节点中有一个失败了，并且我们认为大多数节点写成功就是一个成功写，这里有两个节点写成功了，所以整个写操作是成功的，因此对user1234来说，这个写是ok的。

这样的实现问题很明显，比如说现在节点3恢复了，这个时候，任何到replica3的读都会有问题，因为它丢失了在出问题那段时间的写操作。一个比较简单的解决方案就是，读操作也不是只发送给一个节点，我们同时给三个节点发送，然后根据返回数值所在的version来决定谁是最新的，谁最新我们就使用谁。

读修复和反熵(Anti-entropy)

在分布式系统中，我们希望每一个replica最终都是一样的，所以就希望上文提到的replica3在回来之后能够通过一定的手段修复，就是得到它offline这段时间发生的写操作。那么如何才能达到这个效果呢？一般有以下的方法：

读修复（read pair）

当客户端从多个replica中读取数据的时候，它能看到哪个是最新的，哪些是还有问题的。所以这个时候一个比较常见的方法就是把它看到的最新的值写到它看到的有问题的节点中。这种方法在读比较多的时候很有效，其实可以想象，假如没有读，就没有 机会去比较和重写。

反熵

这个就是后台会有一个线程来不停地检查各个replica之间的差别，当发现有数据差别的时候，就会进行修复，这个和leader不同的是，这个修复不是顺序的，而且可能delay比较大。

Quorums读和写

我们在上面的例子中提到三个节点，有两个写成功，并且我们的读也是两个的话，就可以保证读到最新的写。其实这种读写我们称之为Quorums读和写。准确来讲，假如我们有n个节点，然后写的节点是w个，读的节点是r个，那么quorums读写就是保证w+r>n即可，因为这就意味着我们的读写节点必然有一个是交叉的。也就意味着肯定能读到最新的内容。

就如上图所示，n=5，w=3，r=3，这样哪怕有两个节点是有问题的，我们仍然可以看到replica3包含了最新的写的内容，同时它也被读操作读到了。

虽然上面的定义中是要求w+r>n，其实在现实中，我们很多时候的实现还是会选择>n/2，因为这就基本意味着两者的和肯定大于n了。

但是，是否w+r>n我们就一定什么问题也没有了呢？其实并不尽然，下面是一些常见的可能出问题的情况：

1. 假如写和读同时发生，而这个写只写到了某一些节点，就很难说读到的是不是最新的值了。
2. 假如写是部分成功的，比如说w=3，但是只有两个节点成功了，这个写是失败的，但是并没有去roll back成功的两个写，那么这时读的值很难确定是不是最新的了。
3. 假如一个有新的值的节点突然出现问题了，然后我们从有旧的值得节点来进行replica，这个时候存有新的值的节点就被覆盖成旧的值了，这也就破坏了我们提到的quorum的要求了。

所以，尽管这种方法看起来不错，但是还是有可能会出现这样或那样的问题。

Sloppy Quorum和Hinted Handoff

我们在上文中提到的w+r>n 其实是一种严格的quorum要求，那么假如现实中我们在写的时候w设置的3，但是只有2个节点写成功了，是接受这个写的结果还是直接返回错误呢？你当然可以选择直接返回错误，但是其实还有一种实现就是在这种情况下，我们在n个节点之外再找一个节点去写一下，也保证写了w个节点，只是这里可能有不在n个节点中的节点出现，我们称这种情况为Sloppy Quorum。

当出问题的节点回来之后，任何写到第三节点的值我们需要再写回这个节点，这个过程我们称之为hinted handoff。

这种实现可以大大提高写的成功率，但是很显然它可能会导致读出问题，就是假如交叉的节点正好就是这个第三方的节点，那么我们可能读到就不是最新的值。所以严格来说Sloppy Quorum不是真正的传统意义上的quorum，不过也有其存在的意义。

同时写的探测

和多leader的情况一下，无leader的实现也会遇到同时写的情况。同样也会由于网络延时等等问题，同样的写到各个节点的顺序是不能保证的。如下图所示：

这里有两个client对x进行了设置，而三个节点的表现则互不相同。节点1就只收到了clientA的设置，而没有接收到clientB的设置。节点2则是先收到A的设置再收到B的设置，所以最终呈现的就是B，而节点3则和2相反，先收到了B的设置，后收到A的设置，最后呈现的就是A的设置。

那么如何来解决这个问题呢？下面我们列一些常见的解决方案：

最后写的获胜(LWW)

有一种简单的想法就是谁最后写的，谁就是应该获胜。所以只要我们有方法来区分哪个写是最后的写那么问题就变得简单了。但问题往往就出在这里，如何来区分哪个写是最后写的呢？就像上面两个写，他们几乎同时发生，如何来区分谁先写谁后写呢？一个常见的方法就是用timestamp来做一个id，然后大家进行比较，最终决定谁去谁留（注意的是其实各个server的timestamp也是有可能有偏移的，这个并不一定绝对准确，但也是足够了）。这个方案的一个问题，就是我们会丢掉稍微提前一点点的那个写，假如这种lose是不能接受的，那么可能就需要慎重考虑使用这个方案了。

合并同时的写

这种方案相比上面的方案一个优点就是它不会丢失数据，说白了就是假如有两个写同时发生，那我们就把它们的结果合并。就像上面我们最终呈现的结果既不是A也不是B，而是A/B。当然这种方案也可能有问题，就是后续如何对数据处理，比如这个时候后续有一个删除的操作在if X == A的情况下发生了，你该怎么办。这些都是需要考虑的。

总结

本文就介绍了常见的无leader的实现方案和常见的问题，以及针对这些问题的一些常见处理方法。