前文涉及到了很多与Leader相关的算法,大家有木有想过,王侯将相,宁有种乎,既然Leader这么麻烦,干脆还是采用P2P模型吧,来个大家平等的架构。本篇需要和大家探讨的就是多副本下实现民主政治的Quorum机制。至于它是怎么样解决我们在前文提及的各种问题的,接着这篇文章我们继续聊聊~~
有些数据存储系统放弃了Leader的机制,允许任何副本直接接受用户的写操作。(如Amazon的Dynamo,FaceBook的Cassandra,虽然最终FaceBook放弃了Cassandra转而支持Hbase,但是Uber的强势介入让Cassandra后来在开源社区大放异彩。) 每个接受到客户端写请求的节点会转换为一个协调器节点,而协调器节点不强制执行特定的写入顺序。正是这种设计上的差异对数据库的使用方式与数据模型产生了深远的影响。
No-Leader机制是怎么样消除Leader这个角色的存在的呢?答案也很简单:多副本读写。接下来我们来看一个栗子:
假设我们在数据系统之中采用了三副本的结构,如下图所示:User 1234 并行地将所有的副本发送给三个存储节点,并且两个节点可以接受副本的写入,但是其中一个节点不在线,所以副本写入失败。所以在三个副本中有两个副本确认写入成功了:在User 1234收到两个OK响应之后,User就认为写入操作是成功的,忽略了一个副本写入失败。(当然,不是简单的就不管这个写入失败了,后续会有修复机制来补齐这个副本的数据)
image.png
现在假设User 2345开始读取新写入的数据。由于一个节点写入失败了,所以User 234 可能会得到过期的值作为响应。为了解决这个问题,当User 从数据系统之中读取数据时,它不只是将请求发送到一个副本,而是将读取请求并行地发送到多个副本节点。User可以从不同节点获得不同的响应,即来自其他节点的最新值和另一个节点的过期值。这里通过了版本号用于确定哪个值是更新的值。
No-Leader机制导致了数据系统之中可能存在大量过期的值,所以一个节点怎么来修复自身的副本来获取最新值的过程我们就称之为副本修复,No-Leader机制也是通过这样的方式来达到最终一致性的。通常会有这样几种方式:
上文之中提及的例子在三个副本中的两个之上写入成功,我们认为写操作成功了。但是如果三个副本只有的一个副本写入成功了?这时的写操作是否是成功的呢?
答案是否定的?这里其实就是简单的鸽巢原理,这里我不做数学证明了,大家有兴趣的可以自行证明一下。 假设有n个副本,每次写操作必须由w个节点确认为成功,每个读操作读取r个节点。(在上文的例子中,n=3,w=2,r=2)。只要w + r > n,如果读和写操作的总次数大于n,那么读和写操作必然至少有一个副本是相同的,也就是读操作必然可以读到最新写操作的数据。这被我们称之为:Quorum机制,每次读写都需要达到法定人数。
通常 n、w和r通常是可配置的,根据您的需要来修改这些数字。一个常见的选择是使n为奇数(通常为3或5),并设置w=r=(n + 1)/ 2 。如下图所示,如果w < n,如果有n - w个节点不可用,我们仍然可以处理写操作。同样的如果r<n,如果有n - r个节点不可用,我们仍然可以处理读操作。而如果小于所需的w或r节点可用,则写或读操作就会返回错误。
Quorum机制保证了一定能读到最新的副本
Quorum机制实现了最终一致性的模型,但是在可用性上还是有一些极端情况,没法很好处理。如:出现网络抖动时,但是可能系统仍然有许多正常工作的节点。但是副本应该被写入的n个节点发生网络问题,导致了会少于w或r个成功的读写操作,由于不能达到法定的人数,读写操作都会失败。所以这时候数据库系统的设计者面临权衡取舍,能不能通过一些机制,实现更好的可用性呢?
所以这种情况下,我们就可以利用Hinted handoff了(原谅我翻译不好)。这种方式是怎么样实现的呢?写和读操作仍然需要w和r成功的响应,但是可以不强制一定要写如指定的n个节点 (这个涉及到一致性哈希,数据分布的知识,暂时要是理解不了,我后续会有专门的专题来写这个内容,可以先放一放。) 打个比方说,如果你把自己锁在门外,你可能会敲邻居的门,问你是否可以暂时呆在他们的沙发上,一旦你找到钥匙了,你就自己回家了。所以其他节点可以暂存本应该放在另一个节点上的副本,一旦网络中断被修复,其他节点就会把副本转交给主人节点。
所以这种模式既保证了不违反Quorum机制,也大大提高了系统的可用性,被No-leader数据系统广泛采用。
同样的Quorum机制的设计本身就可以允许并发读写操作,并容忍网络中断与高峰延迟。但是这也必然会带来一致性问题,我们来看下面这个例子:
如图所示,有两个Client A与B,同时写入关键字X在一个三副本的数据存储系统之中。Node 1接收来自A的写入,但由于网络中断而从未接收来自B的写入。Node 2首先接收来自A的写入,然后接收B写入。而Node 3则是首先接收来自B的写入,然后接收A的写入。Node 2认为X的最终值是B,而其他Node认为最终值是A.
并发写导致副本冲突
在这样的场景下如何仲裁写入结果成为了一个大问题,思路和我们之前提到的类型:
合并“happen-before"使用一个单一的版本号来捕捉操作之间的依赖关系,但这不足以解决当有多个副本并行写入的情况。相反,我们需要使用每个副本的版本号以及每个键。每个副本在处理写时递增自己的版本号,并跟踪从其他副本中看到的版本号。此信息指示要覆盖哪些值以及作为兄弟版本保存着哪些值。而所有副本的版本号的集合称为版本向量。版本向量从数据节点发送给客户端,所以版本向量让我们可以区分覆盖写与发并行写操作。
好了,到此为止我们终于总结完整了分布式系统之中的副本机制。从Leader-Follower 机制到多Leader机制,最后到No-Leader的机制,并且详细总结了各个机制的实现细节与优缺点,希望大家阅读完之后也能有所收获。