taoCMS是基于php+sqlite/mysql的国内最小(100Kb左右)的功能完善、开源免费的CMS管理系统

Quorum NRW理论详解

2014-03-14

这一理论是基于集群式存储的,其原理是如果集群有N个结点,那么如果我们每次写操作需要至少同步到W个结点才算成功,而每次读操作只要从R个结点读数据就一定能保证其得到正确结果(如果某一结点有此数据,既成功,如果所有R个结点都无数据,则说明无此数据)。而NRW之间的关系必须满足N < R + W 。其实这一理论并不难理解,我们可以将这个不等式做一下移项:R > N – W ,我们有N个结点,写的时候最少写W个才算成功,也就是W个结点有这份数据,那么N-W就是说可能没有某一份数据的最大结点数。最多可能有N-W个结点没有某一数据,那如果我们进行数据读取操作时,读到大于N-W个结点,那么必然有一个以上的结点是有这份数据的。所以要求R > N – W。

  所以可能你已经想明白了,为了防止数据丢失,我们采用的实际是简单的冗余备份的方法。数据写到多台机器会比写单台机器的磁盘快吗?对。相对于直接的磁盘操作,跨网络进行内存操作可以更快。其最简单的例子就是改进的一致性hash,(关于一致性hash请看这里):


  上图摘自Amazon的Dynamo文档,key的hash值位于A,B结点间的数据,并不是只存在B结点上,而是顺着环的方向分别在C和D结点进行备份。当然这样做的好处并不完全在于上面说的冗余备份。

  当然,很多时候是上面两种解决方法同时使用以保证数据的高可用性。



 数据一致性实现技术

分布式存储在不同的节点的数据采取什么技术保证一致性,取决于应用对于系统一致性的需求,在关系型数据管理系统中一般会采用悲观的方法(如加锁),这些方法代价比较高,对系统性能也有较大影响,而在一些强调性能的系统中则会采用乐观的方法。

 Quorum系统NRW策略

对于数据不同副本中的一致性,采用类似于 Quorum 系统的一致性协议实现。这个协议有三个关键值N、R和W。

N表示数据所具有的副本数。

R表示完成读操作所需要读取的最小副本数,即一次读操作所需参与的最小节点数目。

W表示完成写操作所需要写入的最小副本数,即一次写操作所需要参与的最小节点数目。

该策略中,只需要保证R + W>N,就可以保证强一致性。

例如:N=3,W=2,R=2,那么表示系统中数据有3个不同的副本,当进行写操作时,需要等待至少有2个副本完成了该写操作系统才会返回执行成功的状态,对于读操作,系统有同样的特性。由于R + W > N,因此该系统是可以保证强一致性的。

R + W > N会产生类似Quorum的效果。该模型中的读(写)延迟由最慢的R(W)副本决定,有时为了获得较高的性能和较小的延迟,R和W的和可能小于N,这时系统不能保证读操作能获取最新的数据。

如果R + W > N,那么分布式系统就会提供强一致性的保证,因为读取数据的节点和被同步写入的节点是有重叠的。在关系型数据管理系统中,如果N=2,可以设置为W=2,R=1,这是比较强的一致性约束,写操作的性能比较低,因为系统需要2个节点上的数据都完成更新后才将确认结果返回给用户。

如果R + W ≤ N,这时读取和写入操作是不重叠的,系统只能保证最终一致性,而副本达到一致的时间则依赖于系统异步更新的实现方式,不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。

R和W的设置直接影响系统的性能、扩展性与一致性。如果W设置为1,则一个副本完成更改就可以返回给用户,然后通过异步的机制更新剩余的N W的副本;如果R设置为1,只要有一个副本被读取就可以完成读操作,R和W的值如较小会影响一致性,较大则会影响性能,因此对这两个值的设置需要权衡。

下面为不同设置的几种特殊情况。

当W = 1,R = N时,系统对写操作有较高的要求,但读操作会比较慢,若N个节点中有节点发生故障,那么读操作将不能完成。

当R = 1,W = N时,系统要求读操作高性能、高可用,但写操作性能较低,用于需要大量读操作的系统,若N个节点中有节点发生故障,那么写操作将无法完成。

当R = Q,R = Q(Q = N / 2 + 1)时,系统在读写性能之间取得了平衡,兼顾了性能和可用性,Dynamo系统的默认设置就是这种,即N=3,W=2,R=2。

类别:技术文章 | 阅读:314183 | 评论:0 | 标签:quorum nrw

想收藏或者和大家分享这篇好文章→

“Quorum NRW理论详解”共有0条留言

发表评论

姓名:

邮箱:

网址:

验证码:

公告

taoCMS发布taoCMS 3.0.2(最后更新21年03月15日),请大家速速升级,欢迎大家试用和提出您宝贵的意见建议。

捐助与联系

☟请使用新浪微博联系我☟

☟在github上follow我☟

标签云