分布式系统中的 quorum 机制

在分布式系统中,我们通常增加数据的冗余来达到较高的数据可靠性,多副本和纠删码是最常用的两种数据冗余技术。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。 原理图示: image.png

仔细体会下上面的描述,这个推演是这么来的:

  1. 由于 WARO 模式下更新操作条件太严苛,我们想提高更新操作的可用性,于是适当放宽,允许更新操作的时候 N 个中有失败的,成功 W 个也没关系,照样返回成功,这样写的可用性就上来了;
    1. 虽然数据可靠性短时间的内会处于一个不完整的状态,但是带来的是可用性的提升;
  2. 由于引入 Quorum 机制后,更新操作成功的时候,N 个副本不一定都是最新成功的数据,所以我们读的时候就不能自由的读任意副本,而是一定要读到成功的数据才行,于是才有了每次读都要读 R 个副本,并且 R+W 要满足 > N 才行,因为这样才能保证你读到的 R 个副本里一定有包含正确的数据;
    1. 保证了 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 机制是无法保证数据的强一致性的。因为就算你读到了正确的数据,假如没有其他手段辅组的话,你也是无法甄别出正确的数据的。

举个例子:

image.png

  1. 5 副本的系统,令 W = 3,R=3,初始化值都是 v1,则为 [v1, v1, v1, v1, v1 ]
  2. 一次写更新之后,系统状态变成 [v2, v2, v2, v1, v1]
  3. 由于 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,满足条件,那么本次算成功的更新。

image.png

这个时候,读取任何 3 个副本,一定能读到 v2,情况也不多,只有三种情况,我们穷举下:

  • [v2, v2, v2]
  • [v2, v2, v1]
  • [v2, v1, v1]

我们无法判断究竟是 v1,还是v2是最新的成功递交的数据?

我们可以头脑风暴下;

方法一,每次写副本成功,再写一份元数据记录本次请求,比如把成功的版本 v2 记录下来,这样你就有办法知道数据正确的是哪个版本了。

方法二,或者,我们对读取条件做进一步加强:

  1. 限制递交的更新操作必须严格递增,即只有再前一个更新操作成功才可以递交后一个更新操作,从而成功递交的数据版本号必须是连续递增的;
  2. 读取 R 个副本,对于 R 个副本中版本号最高的数据,
    1. 若已存在 W 个,则认为该数据为最新的成功递交的数据
    2. 若存在个数少于 W 个,假设是 X 个,则继续读取其他副本,直到成功读取到 W 个该版本的副本,则该数据为最新的成功递交的数据;
    3. 若再所有副本中,该数据的个数还不满足 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, v1, v1]
    • 这个情况类似,也是继续读,知道某个数据版本个数满足条件 >= 3

如果这个继续读的过程失败,或者超时了,那么就无法判断了。

Quorum 结合其他技术

所以,单纯的 Quorum 是有适用范围的,工程实践中一般都是结合其他技术来一起使用。


坚持思考,方向比努力更重要。关注公众号:奇伢云存储,获取更多干货。 关注我公众号, 获取更多干货