首页/ 产业/ Quorum(NRW)算法机制简介

Quorum(NRW)算法机制简介

Quorum 机制,是一种分布式系统中常用的,用来保证数据冗余和最终一致性的投票算法,其主要数学思想来源于鸽巢原理。

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


分布式系统中的读写模型

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



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


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

Quorum机制
以上的抽屉理论只是对它的理解,引用参考文献中对Quorum的定义:

                  
Quorum(NRW)算法机制简介配图(1)
简单概括说来就是, 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 理论告诉我们没有完美的方案。


冗余控制算法

在有冗余数据的分布式存储系统当中,冗余数据对象会在不同的机器之间存放多份拷贝。但是同一时刻一个数据对象的多份拷贝只能用于读或者用于写。该算法可以保证同一份数据对象的多份拷贝不会被超过两个访问对象读写。
分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票数(Vr)或者最小的写票数(Vw)才能读或者写。如果一个系统有V票(意味着一个数据对象有V份冗余拷贝),那么这最小读写票必须满足:
  • Vr + Vw > V
  • Vw > V/2
第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候,它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw 不够Vr,因此不能再有读请求过来了。同理,当读请求已经获得了Vr个冗余拷贝的许可时,写请求就无法获得许可了。
第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。
在分布式系统中,冗余数据是保证可靠性的手段,因此冗余数据的一致性维护就非常重要。一般而言,一个写操作必须要对所有的冗余数据都更新完成了,才能称为成功结束。比如一份数据在5台设备上有冗余,因为不知道读数据会落在哪一台设备上,那么一次写操作,必须5台设备都更新完成,写操作才能返回。
对于写操作比较频繁的系统,这个操作的瓶颈非常大。Quorum算法可以让写操作只要写完3台就返回。剩下的由系统内部缓慢同步完成。而读操作,则需要也至少读3台,才能保证至少可以读到一个最新的数据。
Quorum的读写最小票数可以用来做为系统在读、写性能方面的一个可调节参数。写票数Vw越大,则读票数Vr越小,这时候系统写的开销就大。反之则写的开销就小。

本文来源于陀螺财经专栏作家:白楼东,白楼东

现已在陀螺财经发布32篇内容,累计总热度10万+。陀螺财经现已开放专栏入驻,详情请见入驻指南:https://www.tuoluocaijing.cn/article/detail-27547.html

白楼东专栏:https://www.tuoluocaijing.cn/columns/author460488

本文网址:https://www.tuoluocaijing.cn/article/detail-62091.html

收藏

免责声明:
1、本文版权归原作者所有,仅代表作者本人观点,不代表陀螺财经观点或立场。
2、如发现文章、图片等侵权行为,侵权责任将由作者本人承担。

相关文章

白楼东
个人认证

32篇

文章总数

10万+

总热度

热门文章

rss订阅