一致性算法之Quorum NRW

超、凢脫俗 2022-06-15 10:54 343阅读 0赞

分布式系统的设计中会涉及到许多的协议、机制用来解决可靠性问题、数据一致性问题等，Quorum 机制就是其中的一种。我们通过分布式系统中的读写模型来简单介绍它。

### 分布式系统中的读写模型 ###

分布式系统是由多个节点（指代一台服务器、存储设备等）构成，由于网络异常、宕机等节点并不能保证正常工作，特别是在节点数量很大的时候，出现异常状况的节点几乎是肯定的。为了保证系统的正常运行，能够提供可靠的服务，分布式系统中对于数据的存储采用多份数据副本（注：这里的副本并非只用来备份，它可参与提供系统服务）来保证可靠性，也就是其中一个节点上读取数据失败了那么可以转向另外一个存有相同数据副本的节点读取返回给用户。这个过程对于用户来说是透明的。那么随之而来的就会带来数据的副本数据的不一致性，例如：用户提交一次修改后，那么原先保存的副本显然就与当前数据不一致了。解决这个问题最简单的方法 Read Only Write All ，就是在用户提交修改操作后，系统确保存储的数据所有的副本全部完成更新后，再告诉用户操作成功；而读取数据的时候只需要查询其中的一个副本数据返回给用户就行了。 在很少对存储的数据进行修改的情形下（例如存档历史数据供以后分析），这种解决方案很好。如遇到经常需要修改的情形，写操作时延时现象就很明显，加上并发或者连续的执行的话效率就可想而知了。实质，这是由于 Write 和 Read 负载不均衡所致，Read 很轻松，Write 深表压力！

![2012072321410618.jpg][]

那么有没有一种方案能够不需要更新完全部的数据，但又保证返回给用户的是有效数据的解决方案呢？Quorum机制便是一种选择。

### 从小学的抽屉原理说起 ###

为什么从抽屉原理说起？一来大家对这个比较熟悉，二来它与Quorum机制有异曲同工的地方。回顾抽屉原理，2个抽屉每个抽屉最多容纳2个苹果，现在有3个苹果无论怎么放，其中的一个抽屉里面会有2个苹果。那么我们把抽屉原理变变型，2个抽屉一个放了2个红苹果，另一个放了2个青苹果，我们取出3个苹果，无论怎么取至少有1个是红苹果，这个理解起来也很简单。我们把红苹果看成更新了的有效数据，青苹果看成未更新的无效数据。便可以看出来，不需要更新全部数据（并非全部是红苹果）我们就可以得到有效数据，当然我们需要读取多个副本完成（取出多个苹果）。这就是Quorum机制的原型，其实质是将Write All 的负载均衡到 Read Only 上。

### Quorum机制 ###

苹果抽屉理论只是对它的理解，引用参考文献中对Quorum的定义：

![2012072315290094.png][]

简单概括说来就是， Quorum 是一种集合 , l 中任意取集合S,R ，S,R 都存在交集。当然，本文并不打算多讲它的数学定义方面的理解，这里只是提供个信息，看不懂也没事联系到前面的分布式读写模型就能很容易理解这个了。

回到文章的开头，我们来看看是怎么运用Quorum机制来解决读写模型中读写的负载均衡。其实，关键的是更新多少个数据副本后，使得读取时总能读到有效数据？回想我们的的红苹果，假设总共有 N 个数据副本，其中 k 个已经更新，N-k 个未更新的，那么我们任意读取 N-k+1 个数据的时候就必定至少有1个是属于更新了的k个里面的，也就是 Quorum 的交集，我们只需比较 读取的 N-k+1 中版本最高的那个数据返回给用户就可以得到最新更新的数据了。

那么对于写模型呢？我也只需要完成 k个副本的更新后，就可以告诉用户操作完成而不需要 Write All 了，当然告诉完用户完成操作后，系统内部还是会慢慢的把剩余的副本更新，这对于用户是透明的。可以看到，我们把 Write 身上的部分负载转移到了Read上，Read读取多个副本，使得Write不会过于劳累，不好的是弱化了分布式系统中的数据一致性。至于转移多少负载比较合适，这个需要根据分布式系统的具体需求中对数据一致性的要求。不过，CAP 理论告诉我们没有完美的方案。

### 原理应用 ###

为保证在各个节点副本数据一致性，以前一般采用加锁的方法。 然而加锁是悲观的方法，对性能影响比较大。

N表示数据所具有的副本数。  
      R表示完成读操作所需要读取的最小副本数，即一次读操作所需参与的最小节点数目。  
      W表示完成写操作所需要写入的最小副本数，即一次写操作所需要参与的最小节点数目。  
  
      该策略中，只需要保证R + W>N，就可以保证强一致性。 如果R + W ≤ N，这时读取和写入操作是不重叠的，系统只能保证最终一致性，而副本达到一致的时间则依赖于系统异步更新的实现方式，不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。  
  
      假设N=5， 如果R=1， 那么W必须是5. 所以就是写入所有的节点是全部节点，那么读取任何一个节点就可以最新的数据。 有点就是像读写锁了。  
      如果R=5， 那么W只要是1就可以了。 那么写的效率就非常高。 读取的效率比较低。   
      如果R=N/2+1， W=N/2， 读写之间为达到某个平衡。 是不错的策略。

兼顾了性能和可用性，[Dynamo系统][Dynamo]的默认设置就是这种。

[2012072321410618.jpg]: /images/20220615/6be3e1cc3a004ec88dee210b3a98c0ae.png
[2012072315290094.png]: /images/20220615/fa689d9abbf04500bbc3dd80ca3a403a.png
[Dynamo]: http://www.linuxeye.com/architecture/1679.html