开发者社区> 亦才> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

分布式系统之Quorum (NRW)算法

简介:
+关注继续查看

基于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越小,这时候系统写的开销就大。反之则写的开销就小。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Dragonfly 基于 P2P 的文件和镜像分发系统
Dragonfly 是一款基于 P2P 的智能镜像和文件分发工具。它旨在提高大规模文件传输的效率和速率,最大限度地利用网络带宽。在应用分发、缓存分发、日志分发和镜像分发等领域被大规模使用。
110 0
Dragonfly 基于 P2P 的文件和镜像分发系统
业界软件生态在优化 HTTPS 的性能上也做了诸多探索,传统的软件优化方案在软件层面的优化无法满足流量日益增长的速度,CPU 硬件加速成为业界一个通用的解决方案。
286 0
dubbo + zookeeper + spring 分布式系统(二)
dubbo + zookeeper + spring 分布式系统(二)
64 0
Dubbo服务治理篇——分布式服务子系统的划分
1. 将系统中独立的业务抽取出来,按业务的独立性进行垂直划分,抽象出基础服务层。 2.基础服务为上游业务的功能 实现提供支撑,基础服务应用本身无状态,可随着系统的负荷灵活伸缩来提供服务能力。
59 0
使用Cloudreve自建不限速的网盘,支持离线下载
最近PanDownload和百度网盘的事件闹得沸沸扬扬的,不如自建一个不限速的网盘体验一下。
5684 0
从分布式一致性算法到区块链共识机制
本文将从传统的分布式一致性问题说起,再次重温我们需要面对的问题挑战、已有的理论研究、以及相应的一致性算法,并简要分析这些一致性算法的适用性与局限性,以及这些传统一致性算法与崭新的区块链技术的结合。另外,将从区块链中一致性问题的全新视角“人的可信”出发,重点阐述公有链领域中的共识算法与机制。
3666 0
从分布式一致性到共识机制(一)Paxos算法
区块链首先是一个大规模分布式系统,共识问题本质就是分布式系统的一致性问题,但是又有很大的不同。 工程开发中,认为系统中存在故障(fault),但不存在恶意(corrupt)节点,而区块链,特别是公开链是落地到物理世界中,涉及到人性和利益关系,不可避免的存在信任以及恶意攻击问题。
2539 0
《BREW进阶与精通——3G移动增值业务的运营、定制与开发》连载之15---BREW精要之集中分布式应用管理和内容分发
版权声明:本文为半吊子子全栈工匠(wireless_com,同公众号)原创文章,未经允许不得转载。
795 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
PolarDB-X 基于 X-Paxos 一致性协议的高可用
立即下载
探究高性能的海量节点树
立即下载
低代码开发师(初级)实战教程
立即下载