Quorum一致性算法简介

背景

一个组包含若干副本集合,个数为N。每个副本集合存储着items的集合,这个集合可以是文件或者内容,每个item有着唯一的标示和一个状态,我们称之为NWR问题。

定义

R:定义R为读的最小票数,W:定义为写的最小票数。N为副本个数。
每个副本集存储着同一个item的不同的版本号码,越大的版本号标示这个数据是最近的。
读的个数是对写的个数感兴趣的,因为读到的数据应该是大多数写成功的结果。

公式

R+W>N;读写的票数和应该大于总的副本集数(节点数)
W>N/2;写的票数应该大于一般的副本集数(节点数)

举例

对于一个三个副本集组,有着如下的可能:
R=3,W=1:这个有着高效的写性能,但是昂贵的读数据开销,对于读较多的场景,这种尤其较为糟糕。并且在一个副本节点异常或者失败的情况下,写不成功。一般来说我们需要保证W>1。
R=1,W=3:这种分配对于读较多的场景较为友好,但是对于一个节点写失败的情况会导致等待此节点恢复写才能完成写的操作。
R=2,W=2:对比上面是一种较为优化的分配方案,虽然增加了读消耗的花费。

分段描述

写操作

写操作分为一段或者两段
1、发出一个读请求给所有的副本集合,等待一个读提议的回复,获取一个最大的版本号
2、发出一个包含状态和最新版本的写请求给所有的副本集,等待一个写提议的返回,如果返回表示操作完成并返回状态码给client。
如果存在并发的写,需要使用方保持写的安全性。第一步的读请求可以避免,如果客户端知道正确的版本数据。

读操作

读操作也可以分为一段或者两段请求
1、发起一个读请求给所有的副本集合,等待一个读提议的返回,如果所有的版本返回一致的状态,那么返回结果给客户端。
2、否则发起一个大版本数据的写请求给所有副本集合,等待写提议的返回,如果返回成功,则返回结果给客户端。
第二步称之为”回写”段,通常情况下,第二段是没必要的,因为在写请求的操作中所有可用的写返回是一致的数据,那么在读返回中,都是同样的返回数据。

特性

协议需要提供原子性(线性性)

参考

维基百科 Quorum


版权声明:本文为博主原创文章,未经允许不得转载。