Quorum (分布式系统)

✍ dations ◷ 2025-11-21 04:13:19 #投票,算法

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

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

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

算法来源于。 分布式系统中的每一份数据拷贝对象都被赋予一票。每一个读操作获得的票数必须大于最小读票数(read quorum)(Vr),每个写操作获得的票数必须大于最小写票数(write quorum)(Vw)才能读或者写。如果系统有V票(意味着一个数据对象有V份冗余拷贝),那么最小读写票数(quorum)应满足如下限制:

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

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

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

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

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

相关

  • 方阵 (军事)方阵(英语:phalanx),是一种长方形的大规模军事阵法,通常完全由重步兵手持矛、长柄枪、萨里沙长矛或类似的武器所构成。该词特别用来描述古希腊战争中所使用的这种阵法,虽然古希腊
  • 逻辑门逻辑门是在集成电路上的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以
  • 九泉黄泉,出自儒教经典《左传》中郑伯克段于鄢的故事,郑庄公说待其死后将与母亲在黄泉相见。后在汉字文化圈中用于指人死后所居住的地方。因打井至深时地下水呈黄色,又人死后埋于地
  • 特命全权公使特命全权公使,通常简称公使,是一国元首向驻在国元首派遣的次高外交代表,外交官衔上仅次于特命全权大使,但实质地位、职务以及所享受的外交特权与豁免同大使相同。特命全权公使原
  • 韩国国际广播电台坐标:35°50′00″N 126°50′00″E / 35.83333°N 126.83333°E / 35.83333; 126.83333韩国国际广播电台(韩语:KBS 월드 라디오,简称韩广)是大韩民国的官方国际广播电台,也是韩国
  • 内阁办公厅首席捕鼠大臣内阁办公厅首席捕鼠大臣(英语:Chief Mouser to the Cabinet Office),又译内阁办公厅首席捕鼠官,是居于唐宁街10号的英国首相家猫的头衔,历史上仅韩福瑞(英语:Humphrey (cat))和拉里两
  • 汽车仪表汽车仪表,是汽车专用的一系列仪表。汽车仪表的基本仪表包括车速里程表、转速表、机油压力表、水温表及燃油表。而一些指示和警号灯亦包括在内。车速里程表由两个仪表组成:车速
  • 塞迈雷迪·安德烈塞迈雷迪·安德烈(匈牙利语:Szemerédi Endre,1940年8月21日-),匈牙利数学家,他主要的研究领域为组合数学与理论计算机科学。他自从1986年以来一旦担任美国罗格斯大学的计算机科学
  • 北乃绮北乃绮(日语:北乃 きい,1991年3月15日-)是日本女性演员、女歌手,神奈川县横须贺市出身,所属经纪公司为FOSTER plus(日语:フォスター (芸能プロダクション))。本名不公开。在透过为青少
  • 运算符重载在计算机程序设计中,运算符重载(英语:operator overloading)是多态的一种。这里,运算符(比如+,=或==)被当作多态函数,它们的行为随着其参数类型的不同而不同。运算符并不一定总是符号