奇伢云存储

奇伢云存储

qiyaqingli

© 2021

分布式系统中的 quorum 机制
  • 分布式
  • quorum
May 12, 2020

[TOC]

在分布式系统中，我们通常增加数据的冗余来达到较高的数据可靠性，多副本和纠删码是最常用的两种数据冗余技术。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 是有适用范围的，工程实践中一般都是结合其他技术来一起使用。

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