Quorum机制与NRW算法

2023-10-29 18:08
文章标签 算法 机制 quorum nrw

本文主要是介绍Quorum机制与NRW算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


1.Quorum机制

     Quorum,原指为了处理事务、拥有做出决定的权力而必须出席的众议员或参议员的数量(一般指半数以上)

2.NRW算法

     NRW算法是基于Quorum机制的是一种CP(Consistency&Partion tolerance)算法。用于在数据一致性和可靠性之间达到一种平衡。为了保证系统的正常运行,能够提供可靠的服务,分布式系统中对于数据的存储采用多份数据副本,但是这种解决方案在数据读写的过程中会造成数据的不一致性。我们知道要解决数据一致性问题,就是数据的处理方式采用Read Only Write All原则,即在分布式环境中,所有节点更新完毕后,读操作才能进行,保证数据的强一致性。这种虽然保证了数据的在某一刻的强一致性,但是极其影响系统的性能。在一个读操作非常频繁的分布式环境中,写操作的耗时,直接阻塞了读的操作。导致读和写的负载不均衡。 
     基于 Quorum机制的 NRW算法就是在读和写的负载上达到一定平衡的同时,保证数据的强一致性。机制的主要思想来源于鸽巢原理。即当数据备份存在N份时,k份数据已经更新,那么只要获取NK+1N−K+1个数据副本,至少有一个数据是更新了的。获取其中版本最高的那份数据,即最新的。这样,我们就不必等待所有数据副本全部更新后才去读取数据。把写操作的部分工作转移到了读操作中,使得读写能够在一定程度上达到负载均衡。

3.NRW算法规则

     一般我们都会对程序进行优化,即如何实现最小数据备份的情况下,保证数据一致性和读写的均衡? 
     假设需要备份NN个数据副本,读操作用RR,写操作用WW,操作副本用VV表示。根据鸽巢原理,要保证操作能获得最新数据。则有以下制约条件。 
     1.Vr+Vw>N即读操作副本量+写操作副本量必须大于数据副本量。这就即保证必定有一个副本是操作之后的值,同时保证了数据副本要么处于W写操作中,要么处于R读操作中。这里的读写状态是针对外部来讲的,分布式环境对外部来说,同一时刻只存在一种操作(容斥定理),相当于读写锁,但比加锁(一种悲观的策略)的方式更加高效。对于分布式环境内部,读和写操作只是部分节点的操作。同时限定了最小读副本数量和最小写副本数量。该策略中,只需要保证R+W>NR+W>N,就可以保证强一致性。 如果R+WNR+W≤N,这时读取和写入操作是不重叠的,系统只能保证最终一致性,而副本达到一致的时间则依赖于系统异步更新的实现方式,不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。 
     2.Vw>N/2 保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。如Vw<N/2Vw<N/2的时候,就可能存在一部分数据被一个写操作修改,另一部分数据被另一个写操作修改。 
     如图所示,在分布式环境ABCDEA、B、C、D、E中,根据规则一,那么读写副本量应该至少为6,而现在副本只有5份,则至少有一份CC即在读的数据副本中,也在写的数据副本中,才能保证获取到当前时刻最新的数据。规则二,如果Vw<N/2Vw<N/2,就像如图所示的ABA、B写操作和EDE、D写操作一样,那么这时候整个分布式环境中就存在三种数据,造成数据的不一致性。 
分布式环境

4.读写配置策略

     假设N=5N=5, 如果R=1R=1, 那么WW必须是55. 所以就是写入所有的节点是全部节点,那么读取任何一个节点就可以最新的数据。 有点就是像读写锁了。 
     如果R=5R=5, 那么WW只要是11就可以了。 那么写的效率就非常高。 读取的效率比较低。 
     如果W=N/2+1W=N/2+1, R=N/2R=N/2, 读写之间为达到某个平衡。 是不错的策略。兼顾了性能和可用性,Dynamo系统的默认设置就是这种。 
     R/W的配置的关系决定了哪种操作的开销。

这篇关于Quorum机制与NRW算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/302405

相关文章

java中反射(Reflection)机制举例详解

《java中反射(Reflection)机制举例详解》Java中的反射机制是指Java程序在运行期间可以获取到一个对象的全部信息,:本文主要介绍java中反射(Reflection)机制的相关资料... 目录一、什么是反射?二、反射的用途三、获取Class对象四、Class类型的对象使用场景1五、Class

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Nginx之upstream被动式重试机制的实现

《Nginx之upstream被动式重试机制的实现》本文主要介绍了Nginx之upstream被动式重试机制的实现,可以通过proxy_next_upstream来自定义配置,具有一定的参考价值,感兴... 目录默认错误选择定义错误指令配置proxy_next_upstreamproxy_next_upst

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

MySQL 缓存机制与架构解析(最新推荐)

《MySQL缓存机制与架构解析(最新推荐)》本文详细介绍了MySQL的缓存机制和整体架构,包括一级缓存(InnoDBBufferPool)和二级缓存(QueryCache),文章还探讨了SQL... 目录一、mysql缓存机制概述二、MySQL整体架构三、SQL查询执行全流程四、MySQL 8.0为何移除查

一文详解Java Condition的await和signal等待通知机制

《一文详解JavaCondition的await和signal等待通知机制》这篇文章主要为大家详细介绍了JavaCondition的await和signal等待通知机制的相关知识,文中的示例代码讲... 目录1. Condition的核心方法2. 使用场景与优势3. 使用流程与规范基本模板生产者-消费者示例