在分布式系统中,我们通常增加数据的冗余来达到较高的数据可靠性,多副本和纠删码是最常用的两种数据冗余技术。Quorum 机制则是经常配合冗余副本管理的一种机制。
我们先考虑一个简单的场景,你的系统是 3 副本设计,怎么读写流程比较好?直观来讲,写的时候 3 副本都写成功才报告成功,那么读的时候随便读哪个副本都是可以的。这个是最简单的副本策略:write-all-read-one,简称 WARO,也是最常用的一种副本策略。
Write-all-read-one
对于多副本冗余的系统来说,写的时候,所有的副本节点写都成功才算成功(write all),读的时候就可以随便读一个副本即可(read one)。这个就很容易理解,因为有这么个假设存在:只要写成功了,那么多副本的数据就是一致的,你随便读哪个都是正确的数据(不考虑静默或其他问题,静默导致的问题用数据自校验解决)。
现在我们想一个问题,为什么 WARO 的模式下,在读的时候可以随便读任一副本的数据?
关键在于:我们读的是写成功的数据,这个是 Write-All 这个前提保证的。现在思考下优缺点:
优点:
- 实现简单,无需考虑复杂的异常处理,读的时候高效;
缺点:
- 写的可用性不大好,由于更新写操作需要在所有的 N 个副本都成功,写操作才算成功,所以一旦有一个副本异常,写失败,则更新操作不可用。对于更新服务来说,虽然系统由 N 个副本,但系统却无法容忍任何一个副本异常;
- 读的可用性挺好的,N 个副本中,只要由一个副本正常提供服务,系统就可以提供读服务,换句话说,系统可以容忍 N-1 个副本异常;
所以,我们看到 WARO 读写可用性的区别,更新服务的可用性太低了,系统虽然使用了多副本,但是更新操作的可用性等效于没有副本。
能优化这个吗?可以的,其实就是 CAP 理论,WARO 保证了数据的高度一致性,但是牺牲了写更新的可用性,我们的优化思路就是把可用性适当上调,自然数据的一致性就会下调,Quorum 就是提高写更新可用性的一种机制。
Quorum
Quorum 定义
WARO 牺牲写更新的可用性,带来了系统的简洁性,也是读的可用性达到了副本机制的最高状态。我们把 WARO 条件放宽,不要求 Write-all,从而使得读写服务的可用性之间做个折中,这个就是 Quorum。
在 Quorum 机制中,当某次写更新操作 w[i] 在 N 个副本中的 W 个副本都成功,则就称该更新操作为“成功递交的更新操作”,对应的数据为“成功递交的数据”。
- 令 R > N-W,由于更新操作 w[i] 在 W 个副本上成功,所以在读取数据时,最多需要读取 R 个副本则一定能读到 w[i] 更新后的数据 v[i]。
- 如果某次更新 w[i] 在 W 个副本上成功,由于 W+R > N,任意 R 个副本组成的集合一定于成功的 W 个副本组成的集合有交集,所以读取 R 个副本一定能读到 w[i] 更新后的数据 vi。 原理图示:
仔细体会下上面的描述,这个推演是这么来的:
- 由于 WARO 模式下更新操作条件太严苛,我们想提高更新操作的可用性,于是适当放宽,允许更新操作的时候 N 个中有失败的,成功 W 个也没关系,照样返回成功,这样写的可用性就上来了;
- 虽然数据可靠性短时间的内会处于一个不完整的状态,但是带来的是可用性的提升;
- 由于引入 Quorum 机制后,更新操作成功的时候,N 个副本不一定都是最新成功的数据,所以我们读的时候就不能自由的读任意副本,而是一定要读到成功的数据才行,于是才有了每次读都要读 R 个副本,并且 R+W 要满足 > N 才行,因为这样才能保证你读到的 R 个副本里一定有包含正确的数据;
- 保证了 R+W > N 这个条件,才能保证读的副本集合和写的副本集合有交集;
举例子,系统是 5 副本的,令 W=3,R=3,最初 5 个副本数据都一致,都是 v1,某次更新操作 w2 再前 3个副本成功,副本情况变成(v2 v2 v2 v1 v1)。此时,任意 3 个副本组成的集合中一定包含 v2。
其实,上述定义中,令 W=N,R=1,其实就等价 WARO,所以这么来讲,WARO 是 Quorum 机制的一种特例。
思考一个问题:你读 R 个副本数据上来,虽然一定包含了正确的数据,但是你怎么甄别出来正确的数据?记得不要代入你的上帝视角哈。
针对这个问题,我们有个很重要的结论:只依赖 quorum 机制是无法保证数据的强一致性的。因为就算你读到了正确的数据,假如没有其他手段辅组的话,你也是无法甄别出正确的数据的。
举个例子:
- 5 副本的系统,令 W = 3,R=3,初始化值都是 v1,则为 [v1, v1, v1, v1, v1 ]
- 一次写更新之后,系统状态变成 [v2, v2, v2, v1, v1]
- 由于 R=3,根据 qurom 的规则,我们只需要读到 3 份副本数据,就能读到正确的值。穷举下,那么 R =3 ,读到的副本列表有三种情况:
- [v2, v2, v1]
- [v2, v2, v2]
- [v2, v1, v1]
我们看到 无论哪种,v2 都在列表里,我们站在上帝视角,自然知道这个就是正确的数据。但是对于这三种场景,你需要怎么处理才能确保每次都识别出正确的数据是 v2 呢?
其实只有第二种情况 [v2, v2, v2],你才能断定 v2 是正确的,因为列表里只有 v2。
第一种情况 [v2, v2, v1] 和 第三种情况 [v2, v1, v1] 你都还需要其他进一步的手段,你才能识别出正确的数据。比如第一种情况 [ v2, v2, v1 ] 你会取哪个值作为正确的值?v2?因为 v2 是多数?但是第三种情况下 v1 还是多数呢。
这种情况需要进行一些额外的操作来确认正确的副本,而且最终可能还无法区分。
如何确定最新递交的值?
Quorum 机制说明,只需要成功更新 N 个副本中的 W 个,在读取 R 个副本时,满足 W+R > N 的条件时,一定可以读到最新的成功的数据。但由于有更新失败的情况存在,仅仅读到 R 个副本却不一定能确定哪个是正确的数据。
还是以这个举例:假定 N=5,W=3,R=3 的系统,初始化为 [v1, v1, v1, v1, v1],成功一次更新之后,某时刻状态为 [v2, v2, v2, v1, v1] ,也就是前三个副本更新成功,由于 W=3,满足条件,那么本次算成功的更新。
这个时候,读取任何 3 个副本,一定能读到 v2,情况也不多,只有三种情况,我们穷举下:
- [v2, v2, v2]
- [v2, v2, v1]
- [v2, v1, v1]
我们无法判断究竟是 v1,还是v2是最新的成功递交的数据?
我们可以头脑风暴下;
方法一,每次写副本成功,再写一份元数据记录本次请求,比如把成功的版本 v2 记录下来,这样你就有办法知道数据正确的是哪个版本了。
方法二,或者,我们对读取条件做进一步加强:
- 限制递交的更新操作必须严格递增,即只有再前一个更新操作成功才可以递交后一个更新操作,从而成功递交的数据版本号必须是连续递增的;
- 读取 R 个副本,对于 R 个副本中版本号最高的数据,
- 若已存在 W 个,则认为该数据为最新的成功递交的数据
- 若存在个数少于 W 个,假设是 X 个,则继续读取其他副本,直到成功读取到 W 个该版本的副本,则该数据为最新的成功递交的数据;
- 若再所有副本中,该数据的个数还不满足 W 个,则 R 中版本号第二大的为最新的成功递交的副本;
所以我们再思考下,这三种情况:
- [v2, v2, v2]
- 3 个副本都是 v2 ,v2版本的个数 >=3,那么 v2 就是最新成功的版本
- [v2, v2, v1]
- 两个数据是 v2,一个是 v1,那么还需要继续读,有两种情况:
- [v2, v2, v1, v1] :这种情况还需要继续读,因为v2, v1的个数都还不满足 >= 3;
- [v2, v2, v2, v1, v1] :这个时候,终于可以断定,v2 就是成功递交的那个最新数据
- [v2, v2, v2, v1] :v2的个数 >=3 ,所以断定 v2 是最新成功递交的数据;
- [v2, v2, v1, v1] :这种情况还需要继续读,因为v2, v1的个数都还不满足 >= 3;
- 两个数据是 v2,一个是 v1,那么还需要继续读,有两种情况:
- [v2, v1, v1]
- 这个情况类似,也是继续读,知道某个数据版本个数满足条件 >= 3
如果这个继续读的过程失败,或者超时了,那么就无法判断了。
Quorum 结合其他技术
所以,单纯的 Quorum 是有适用范围的,工程实践中一般都是结合其他技术来一起使用。
坚持思考,方向比努力更重要。关注公众号:奇伢云存储,获取更多干货。