分布式系统原理（5）--Quorum机制

Quorum机制是一种简单有效的副本管理机制

（1）约定

假设：更新操作（write）是一系列顺序的过程，通过其他机制确定更新操作的顺序（例如由primary决定顺序），每个更新操作记为w_i，i为更新操作单调递增的序号，每个w_i执行成功后副本数据都发生变化，成为不同的数据版本，记作v_i。假设每个副本都保存了历史上所有版本的数据

（2）Write-all-read-one

l  简称WARO，一种最简单的副本控制规则，即在更新时写所有的副本，只有在所有的副本上更新成功，才认为更新成功，从而保证所有副本一致，这样在读取数据时可以读任一副本上的数据。

l  缺点：

n  难实现，效率低，严格的WARO机制通常需要将版本号信息存放在某个或某组元数据服务器上。加入更新操作非常频繁，那么记录更新成功的版本号v_i将成为一个关键操作，容易成为瓶颈。另外，为实现强一致性，在读取数据之前必须先读取数据中的版本号，大压力下也容易因为元数据服务器的性能造成瓶颈

n  可用性不高，一旦一个副本异常，更新操作失败，更新服务不可用，容错性差。但对读服务，只要一个副本正常，系统就应可以提供读服务。

（3）Quorum定义

l  WARO牺牲了更新服务的可用性，最大程度的增强服务的可用性，将WARO的条件进行松弛，从而使得可以在读写服务可用性之间做折中，得到Quorum机制。

l  在Quorum机制下，当某次更新操作w_i一旦在所有N各副本中的W个副本上都成功，则就称该更新操作“成功提交的更新操作”，称对应的数据为“成功提交的数据”。令R>N-W，由于更新操作w_i仅在W个副本上成功，所以在读取数据时，最多需要读取R个副本就一定能读到w_i更新后的数据v_i。Quorom机制的原理可以用文森图表示。其中W=N,R=1就是WARO。

l  可用性：限制Quorum参数为W+R=N+1，一旦N-W+1个副本异常，更新服务不可用；一旦N-R+1个副本异常，则读服务一致性下降。

l  强调：仅依赖Quorum机制是无法保证强一致性的，因为仅有quorum机制时无法确定最新已成功提交的版本号，除非将最新已提交的版本号作为元数据由特定的元数据服务器或元数据集群管理。

（4）读取最新成功提交的数据

本节分析在Quorum机制下，如何时钟读取成功提交的数据，以及如何确定最新的已提交的数据。

在quorum机制下，要达到强一致性，也就是始终读取你会最新的成功提交的数据，需要对读取条件做进一步加强。

1. 限制提交的更新操作必须严格递增，即只有在前一个更新操作成功提交后才可以提交后一个更新操作，从而成功提交的数据版本号必须是连续增加的。

2. 读取R个副本，对R个副本中版本号最高的数据，

       2.1若已存在W个，则该数据为最新的成功提交的数据

       2.2若存在的数据少于W个，假设为X个，则继续读取其他副本，若成功读取到W个该版本的副本，则该数据为最新的成功提交的数据，如果所有副本中该数据个数不满足W个，则R中版本号为第二大的为最新的成功提交的副本

可以看出，单纯使用quorum机制，最多需读取R+(W-R-1) = N个副本，任一副本异常，最新版本都可能不可用，实际工程，尽量使用别的技术，回避通过quorum机制读取最新成功提交版本。如quorum机制与primary-secondary控制协议结合，通过读取primary的方法读取到最新已提交数据

（5）基于Quorum机制选择primary

l  在primary机制中引入quorum机制后，primary成功更新W个副本（含primary本身）后向用户返回成功。读取数据是按照一致性要求的不同可以有不同的做法：

n  强一致性：直接读取primary副本或按上节的方法

n  会话一致性：根据之前已经读到的数据版本号在各副本上进行选择性读取

n  弱一致性：选择任意副本读取

l  重选primary，当primary异常时，由某一中心节点选择新的primary，引入quorum机制后的操作是，中心节点读取R个副本，选择R个副本中版本号最高的副本作为新的primary。新primary与至少W个副本完成数据同步后作为新的primary提供读写服务。首先R个副本中一定蕴含了最新的成功提交的数据，再者，虽然不能确定最高版本号的数据一定是成功提交的数据，但新的primary在随后与secondary同步数据，可使得该版本的副本个数达到W，从而使得该版本的数据成为成功提交的数据，有两种可能出现的情况：

（6）工程投影

a）GFS中的Quorum

l  GFS使用WARO机制读写副本，即若更新所有副本成功则认为更新成功，可选任一副本读取数据，若某副本更新失败，则显更失败，副本间是不一致状态，GFS不保证异常状态时副本的一致性，需上层通过Checksum等机制自行判断数据是否合法。

l  GFS中的append操作，一旦append操作某个chuck的副本上失败，GFS会自动新增一个chuck并尝试append操作，由于可以让新增的chuck在正常的机器上创建，从而解决了由于WARO造成的系统可用性下降问题。故GFS不保证append操作一定在文件的结尾进行，由于在新增chuck上重试append，append的数据可能出现多分重复现象，但每个append操作会返回用户最终成功的offset位置，在该位置上，人已读取某个副本一定可以读到写入的数据

l  这种在新增chunk上进行尝试的思路，大大增加了系统的容错能力，提高了系统可用性。

b）Dynamo中的Quorum

l  Dynamo/Cassandra是一种去中心化的分布式存储系统，使用Quorum管理副本，用户可以配置N/R/W的参数，并保证满足R+W>N的quorum要求。

l  但Dynamo是一个没有primary的去中心化系统，由于缺乏中心控制，每次更新操作都可能由不同的副本主导，在出现并发更新、系统异常时，其副本的一致性完全无法得到保障。

l  为了帮助用户解决这种不一致的情况，Dynamo提出了一种clock vector的方法，该方法的思路就是记录数据的版本变化，即记录数据变化的路径的向量，为每个更新操作维护分配一个向量元素，记录数据的版本号及主导该次更新的副本名字。一旦读取到有冲突的副本信息，用户可根据自定义的策略进行合并多个版本数据。

l  Dynamo建议按照数据更新的时间戳进行合并，新数据代替旧数据，若是简单的覆盖写操作，该策略有效，但若是并发的加操作（如：向购物车中加商品），则不适用，会造成数据丢失

c）Zookeeper中的Qrorum

Zookeeper使用的paxos协议本身就是利用了Quorum机制，当利用paxos协议选出了primary后，Zookeeper的更新流量由primary节点控制，每次更新操作，primary节点只需更新超过半数（含自身）的节点后就返回用户成功。每次更新操作都会递增各个节点的版本号（xzid）。

当primary异常，利用paxos协议选举新的primary时，每个节点都会以自己的版本号发起paxos提议，从而保证了选出的新primary是某个超过半数副本集合中版本号最大的副本。过程与（5）类似。

d）Mola*/Armor*中的Quorum

l  Mola*和Armor*系统中所有的副本管理都是基于Quorum，即数据在多数副本上更新成功则认为成功。

l  Mola系统的读取通常不关注强一致性，而提供最终一致性。

l  Armor*，可以通过读取副本版本号的方式，按Quorum规则判断最新已提交的版本。由于每次读数据都需要读取版本号，降低了系统性能，Doris*系统在读取Armor*数据时采用了一种优化思路：由于Doris*系统的数据是批量更新，Doris*维护了Armor*副本的版本号，并只在每批数据更新完成后再刷新Armor*副本的版本号，从而大大减少读取Armor*副本版本号的开销。

e）Big Pipe*中的Quorum

l  Big Pipe*中的副本管理也是采用了WARO机制，但Big Pipe*利用了zookeeper的高可用性解决了WARO在更新失败时副本的不一致的难题。

l  当更新操作失败时，每个副本都会尝试将自己的最后一条更新操作写入zookeeper。但最多只有一个副本能写入成功，若副本发现之前已经有副本写入成功后则放弃写入，并以zookeeper中的记录为准与自身的数据进行同步。另一方面，与GFS更新失败后新建chunk类似，当Big Pipe*更新失败后，会将更新切换到另一组副本，这组副本首先读取zookeeper上的最后一条记录，并从这条更新记录之后继续提供服务。

l  可以看出Big Pipe*中中间态数据的命运完全取决于是哪个副本抢先完成写zookeeper的过程。

最后

以上就是乐观小蝴蝶为你收集整理的分布式系统原理（5）--Quorum机制的全部内容，希望文章能够帮你解决分布式系统原理（5）--Quorum机制所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。