`
m635674608
  • 浏览: 5054605 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

分布式Quorum机制,NWR策略读写模型

 
阅读更多

分布式系统中的读写模型

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

解释:

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

回到文章的开头,我们来看看是怎么运用Quorum机制来解决读写模型中读写的负载均衡。其实,关键的是更新多少个数据副本后,使得读取时总能读到有效数据?

读模型:

假设总共有 N(副本个数) 个数据副本,其中 k 个已经更新,N-k 个未更新的,那么我们任意读取 N-k+1(读取副本的个数)个数据的时候就必定至少有1个是属于更新了的k个里面的,也就是 Quorum 的交集,我们只需比较 读取的 N-k+1 中版本最高的那个数据返回给用户就可以得到最新更新的数据了。

写模型:

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

 

基于Quorum投票的冗余控制算法

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

在有冗余数据的分布式存储系统当中,冗余数据对象会在不同的机器之间存放多份拷贝。但是同一时刻一个数据对象的多份拷贝只能用于读或者用于写。

该算法可以保证同一份数据对象的多份拷贝不会被超过两个访问对象读写。

算法来源于[Gifford, 1979][3][1]。 分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票数(Vr)或者最小的写票数(Vw)才能读或者写。如果一个系统有V票(意味着一个数据对象有V份冗余拷贝),那么这最小读写票必须满足:

  1. Vr + Vw > V

  2. Vw > V/2

第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候,它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw 不够Vr,因此不能再有读请求过来了。同理,当读请求已经获得了Vr个冗余拷贝的许可时,写请求就无法获得许可了。

第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。

 

算法好处

在分布式系统中,冗余数据是保证可靠性的手段,因此冗余数据的一致性维护就非常重要。一般而言,一个写操作必须要对所有的冗余数据都更新完成了,才能称为成功结束。比如一份数据在5台设备上有冗余,因为不知道读数据会落在哪一台设备上,那么一次写操作,必须5台设备都更新完成,写操作才能返回。

对于写操作比较频繁的系统,这个操作的瓶颈非常大。Quorum算法可以让写操作只要写完3台就返回。剩下的由系统内部缓慢同步完成。而读操作,则需要也至少读3台,才能保证至少可以读到一个最新的数据。

Quorum的读写最小票数可以用来做为系统在读、写性能方面的一个可调节参数。写票数Vw越大,则读票数Vr越小,这时候系统写的开销就大。反之则写的开销就小

该算法满足CAP理论的 A(可用性)和P(容错性),不满足 C(一致性)

 

 

NWR 策略读写模型的例子

假设两个进程同时来更新这份数据,进程W1要把值改写成C,进程W2要把值改写成B,那就有可能出现下图的情形,两个进程各拿到一个副本改写,都认为自己的写操作是成功的,结果却留给系统三个不同的副本,这样就出现数据副本不一致的问题。

Swift里的CAP理论和NWR策略应用

  所以公式W> N/2, 实际上变成了一个写的锁,意味着只有写了过半数副本的才算写成功,拿不到的就返回失败,解决了竞争的问题。如下图,W1的会话成功,W2的会话就返回失败。

Swift里的CAP理论和NWR策略应用

  W> N/2,同时意味着不需要把所有的副本都写完,未完成的留给系统自己后台慢慢同步,那这个时候问题就来了,一个新的会话过来读数据的时候,分配到的副本有可能是没来得及更新的。这时候R1读回去的就是过时的数据B,而非最新的数据C

Swift里的CAP理论和NWR策略应用

 第2个公式变形下就是R> N-W,R=2就避免正好倒霉读到没更新的那一个。这样读回去C和B两个数据,再比较后取最新的C。所以W+R> N 能够保证每个读的请求至少读到一份最新的数据,

Swift里的CAP理论和NWR策略应用 

 

 https://my.oschina.net/manmao/blog/618344

分享到:
评论

相关推荐

    分布式系统原理pdf

    Quorum机制则用于在分布式系统中处理数据副本的读写问题,以保证数据的一致性。 日志技术部分,文档讨论了数据库系统中日志技术的应用,包括RedoLog、Checkpoint以及NoUndo/NoRedolog等技术。这些技术对于保持数据...

    基于Quorum系统的分布式访问控制框架研究.pdf

    DACS,可以有效地解决传统访问控制框架中存在的单点故障和安全政策保密问题,同时提供了一个科学依据来指导在不同应用场景下如何选择和优化访问控制策略,以满足对安全性和可靠性有较高要求的军事系统和分布式事务...

    分布式数据库如何平衡一致性和读写延迟.docx

    分布式数据库如何平衡一致性和读写延迟 一致性模型 (Consistency Model) 是分布式数据库中一个非常重要的概念,它决定了系统中数据的一致性和可用性。在分布式数据库中,数据副本的引入可以说是“万恶之源”,因为...

    分布式系统原理介绍

    Quorum机制是一种基于多数派原则的数据同步方法,可以有效地解决分布式系统的读写一致性问题。 日志技术在分布式系统中扮演着重要角色,包括数据库系统日志技术简述、RedoLog与Checkpoint、NoUndo/NoRedolog等。两...

    分布式系统原理介绍.pdf

    Quorum机制是分布式系统中用于读写数据的一种策略,通过多数派的方式保证数据的一致性。日志技术是数据库系统中用于记录数据变化历史的技术,包括Redo Log和Checkpoint等。两阶段提交协议是一种用于实现跨多个节点的...

    分布式系统原理 刘杰

    - **Quorum定义**: 为读写操作定义的最小副本集合。 - **读取最新成功提交的数据**: 通过Quorum机制保证读取的数据是最新的。 - **基于Quorum机制选择Primary**: 确定主节点的过程。 #### 九、日志技术 - **数据库...

    ZooKeeper-分布式过程协同技术详解 PDF

    《ZooKeeper——分布式过程协同技术详解》这本书深入剖析了Zookeeper这一强大的分布式协调系统,旨在帮助读者理解和掌握其核心概念、架构以及故障处理策略。Zookeeper是Apache软件基金会的一个开源项目,它为大型...

    分布式协议与算法1

    10. **NWR算法**:NWR(Node,Write,Read)是关于Quorum选择的一种策略,用于平衡系统的可用性和一致性。 在分布式系统中,通常需要在CAP(Consistency、Availability、Partition Tolerance)三者之间做出权衡。...

    GPFS分布式文件系统架构和原理

    GPFS 提供三套不同的 quorum 机制来判断系统当前的状态,其中 File Descriptor Quorum 是系统内置的,不能做配置,另外两种 Node quorum(仲裁节点机制)和 Tiebreaker Disk quorum(仲裁磁盘机制)方式只能二者选其...

    藏经阁-Cassandra总体介绍.pdf

    Cassandra使用Quorum机制来实现高可用性,Quorum是指在分布式系统中,需要大多数节点同意才能确认写操作的成功。 Cassandra支持两种一致性模型:强一致性(Strong Consistency)和最终一致性(Eventual Consistency...

    quorum_blog:通过仲裁保持一致性的分布式博客

    Quorum机制是保证分布式一致性的一种策略,它源于分布式数据库领域。在quorum_blog项目中,Quorum被用来决定何时提交或应用更改,以确保大多数节点同意这些更改。Quorum的基本思想是在进行写操作时,需要至少超过...

    CCTC 2016 百度王耀-百度的分布式文件系统之路

    - Master节点采用单机Table引擎存储元信息,并使用Zookeeper进行选主,通过QJM(Quorum Journal Manager)机制复制日志,确保数据的一致性和系统的高可用性。 通过这些知识点,我们可以看到百度在分布式文件系统...

    Go-Gorums一个框架用于简化容错基于quorum协议的设计和实现

    这个框架的核心理念是抽象出复杂的分布式系统中的共识算法,让开发者可以专注于业务逻辑,而不需要从头构建底层的容错机制。Quorum协议是一种在分布式系统中确保数据一致性和高可用性的关键技术,它通常应用于数据库...

    分布式算法与云平台研究.pdf

    参数可调的弱quorum机制是一种数据备份策略,该策略通过调整参数来改变系统对于数据一致性的要求,从而在可接受的一致性和系统性能之间进行权衡。弱quorum通过多数写入或多数读取来保证数据副本的一致性,同时又不...

    zookeeper之分布式环境搭建.zip

    在IT行业中,ZooKeeper...不过,要真正掌握Zookeeper,还需要进一步深入研究它的高级特性,如Watcher机制、事务操作以及与其他分布式系统的集成策略。在实践中不断探索,才能更好地利用Zookeeper解决实际的分布式问题。

    字节跳动分布式数据库实践.pptx

    ByteSQL对外提供了多种一致性模型,如P(Partition Tolerance)、C(Consistency)和A(Availability)的权衡选择,以及副本同步协议如Quorum、Raft、Multi-Paxos等。这些协议确保了在分布式环境中数据的一致性和...

Global site tag (gtag.js) - Google Analytics