分布式系统中,一般保存多个数据副本,明显可以提高系统可靠性。并且存储这些数据副本的节点,不仅做容灾用,也可以提供服务,作负载均衡。
这里就涉及到一个数据一致性的问题,也就是各副本间要进行同步,来保持最新的数据。在一些一致性需求不辣么强的场景,比如用户获取某个文章的点赞数,读到未及时同步的脏数据也就无所谓了。
但在一些需要强一致性的场景里,这就比较可怕了。比如你银行卡里笼共就100块钱,第一次取了60元,第二次取的时候,请求路由到了未同步的那个副本数据上,你又可以取60元。银行就赔死了。
在这种需要强一致性的系统中,有一个简单的解决策略叫Read Only Write All。比如我分布式系统中有4个数据的副本,辣么当用户修改这个数据时,只有当系统中4个副本都同步为最新数据,才返回修改成功。这样读的时候,就一定是个好的数据了。
但在这种写操作频繁的系统,Write All对系统带来的负担就比较大了。
简单说就是,读很轻松,但写压力山大。那如何优化呢?Quorum算法就是一种方案。
算法的原理在wiki有介绍:
https://zh.wikipedia.org/wiki/Quorum_(%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F)#cite_note-1
wiki上写了它是基于鸽巢原理的。举个栗子:现在,我们有2绿2红4个球,分别放在不同的盒子里(鸽巢),那么,我们只要任意取3个球,就至少有一个绿球。道理很简单。
在我们的分布式系统中,可以把绿球看作新数据,红球看作未更新的脏数据。辣么!我们只要写了2份数据,也就是放了2个绿球,就可以返回写成功了。而这时候,想取出一个绿球(有效数据)就要费力一些了,至少要取3个球。
现在我们把4写一读,转换成了2写3读。这其实是对读写的一种负载均衡,用于减小写数据操作的压力。
当然,写2次读3次我们是肿么设计出来的呢。又要看wiki上Quorum算法原理了。简单来说,就是满足下面2个公式:
分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票数(Vr)或者最小的写票数(Vw)才能读或者写。如果一个系统有V票(意味着一个数据对象有V份冗余拷贝),那么这最小读写票必须满足:
1、Vr + Vw > V
2、Vw > V/2
第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候,它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw 不够Vr,因此不能再有读请求过来了。同理,当读请求已经获得了Vr个冗余拷贝的许可时,写请求就无法获得许可了。
第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。
我们惊奇的发现,上面设计的2写3读,并不符合以上第二条规则。也就是只保证一个数据不被同时读写,但仍不能保证这个数据不被两个请求同时写。。。
3写2读就可以解决了。
Quorum算法的更多相关文章
-
关于NRW算法(Quorum算法)
在分布式系统中,冗余数据是保证可靠性的手段,因此冗余数据的一致性维护就非常重要.一般而言,一个写操作必须要对所有的冗余数据都更新完成了,才能称为成功结束.比如一份数据在5台设备上有冗余,因为不知道读数 ...
-
Zookeeper(一)从抽屉算法到Quorum (NRW)算法
一.抽屉算法 抽屉算法,又名鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则.它是组合数学中一个重要的原理. 具体算法讲的是: 第一抽屉算法: 如果 ...
-
分布式系统之Quorum (NRW)算法
基于Quorum投票的冗余控制算法 Quorom 机制,是一种分布式系统中常用的,用来保证数据冗余和最终一致性的投票算法,其主要数学思想来源于鸽巢原理. 在有冗余数据的分布式存储系统当中,冗余数据对象 ...
-
分布式理论——quorum原理
编者按:本篇文章是网上一些文章的合集,并不是原创,谢谢各位的分享. 一.基于Quorum投票的冗余控制算法 Quorom 机制,是一种分布式系统中常用的,用来保证数据冗余和最终一致性的投票算法,其主要 ...
-
微信、陌陌等著名IM软件设计架构详解
对微信.陌陌等进行了分析,发出来分享一下(时间有些久了) 电量:对于移动设备最大的瓶颈就是电量了.因为用户不可能随时携带电源,充电宝.所以必须考虑到电量问题.那就要检查我们工程是不是有后台运行,心跳包 ...
-
Kafka官方文档翻译——设计
下面是博主的公众号,后续会发布和讨论一系列分布式消息队列相关的内容,欢迎关注. ------------------------------------------------------------ ...
-
Amazon Aurora解读(SIGMOD 2017)
Amazon在SIGMOD 2017发表了论文<Amazon Aurora: DesignConsiderations for High Throughput Cloud-Native Rela ...
-
微信、陌陌等著名IM软件设计架构详解(转)
对微信.陌陌等进行了分析,发出来分享一下(时间有些久了) 电量:对于移动设备最大的瓶颈就是电量了.因为用户不可能随时携带电源,充电宝.所以必须考虑到电量问题.那就要检查我们工程是不是有后台运行,心跳包 ...
-
corosync基本使用
相关rpm: corosync-2.4.0-4.el6.x86_64.rpm The Corosync Cluster Engine and Application Programming Inter ...
随机推荐
-
探索javascript----滚轮事件的兼容
具体使用时,我们还要判断浏览器,记得传入的是兼容事件:var e=window.event||ev; 选择事件:
-
asp.net 微信支付 错误解决方案
asp.net 微信支付 错误解决方案 在网上看到有人解决方案为: 解决方法 出现这种错误网上查出现有的原因是: 订阅号没有相关的权限 账号没有认证,没有相关的权限 那么这里遇到问题两种都不是.开发账 ...
-
STM32学习笔记2-系统时钟知识及程序配置
一:基本知识 1. STM32F103ZE有5个时钟源:HSI.HSE.LSI.LSE.PLL. ①.HSI是快速内部时钟,RC振荡器,频率为8MHz,精度不高. ②.HSE是快速外部时钟, ...
-
一些常用的集合工具的代码块(缓慢更新XD)
鱼的记忆 我发现在项目中常常要用到一些集合的处理,不同的项目我经常会编写自己的集合工具代码块,后来我发现我总是在写一样的代码块(可能是我记性不好吧:),毕竟鱼的记忆只有7秒),所以我意识到了是时候 ...
-
JS中typeof和instanceof用法区别
typeof和instanceof都可以用来判断变量 1.typeof用以获取一个变量或者表达式的类型,typeof一般只能返回如下几个结果: number,boolean,string,functi ...
-
退役前的记录(2018.10.14-NOIP2018)
退役前的记录 诸位好,我是\(CJ\)最菜的\(Oier\),已经是\(G2\)的老年选手了,不知道什么时候就会退役了,总之\(G1\ double\)的机会已经没有了,去年因为联赛失利而止步,而今年 ...
-
POJ 2923 Relocation 装车问题 【状态压缩DP】+【01背包】
题目链接:https://vjudge.net/contest/103424#problem/I 转载于:>>>大牛博客 题目大意: 有 n 个货物,并且知道了每个货物的重量,每次用 ...
-
A-论文一些好的句子
Using our techniques, task set transformation is performed by modifying the parameters related to ea ...
-
Xcode7.3 beta 新功能 https://developer.apple.com/go/?id=xcode-7.3-rn
Xcode7.3 beta 新功能html, body {overflow-x: initial !important;}html { font-size: 14px; } body { margin ...
-
7.Mongodb复制(副本集)
1.复制 什么是复制 复制提供了数据的冗余备份,并在多个服务器上存储数据副本,提高了数据的可用性,并可以保证数据的安全性 复制还允许从硬件故障和服务中断中恢复数据 为什么要复制 数据备份 数据灾难恢复 ...