分布式一致性算法

一、Paxos 算法

　　Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。

Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos作为比喻，描述了Paxos小岛中通过决议的流程，

并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，Lamport觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。

自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。

Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，

以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。

然而，Paxos的最大特点就是难，不仅难以理解，更难以实现。

应用：zookeeper

二、Raft 算法

　　Raft是一种管理复制日志的一致性算法。

它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。

Raft将一致性拆分为几个关键元素：

Leader选举
日志复制
安全性

应用：nacos，consle，etcd

三、Zab 协议

四、PacificA 算法

　　PacificA算法是微软亚洲研究院提出的一种用于日志复制系统的分布式一致算法，

与其他的一致性算法相比，PacificA算法主要用于数据的一致性管理，并另辟蹊径采用其他一致性组件来进行配置一致性管理。

五、Bully 算法

　　霸道选举算法是一种分布式选举算法，每次都会选出存活的进程中ID最大的候选者。

　　bully算法是一个分布式系统中动态选择master节点的算法，进程号最大的非失效的节点将被选为master。

应用：es

六、Quorum 机制

　　Quorum 的定义如下：假设有 N 个副本，更新操作 wi 在 W 个副本中更新成功之后，则认为此次更新操作 wi 成功，把这次成功提交的更新操作对应的数据叫做：“成功提交的数据”。

对于读操作而言，至少需要读 R 个副本，其中，W+R>N ，即 W 和 R 有重叠，一般，W+R=N+1。

N = 存储数据副本的数量
W = 更新成功所需的副本
R = 一次数据对象读取要访问的副本的数量

听起来有些抽象，举个例子：

假设我有5个副本，更新操作成功写入了3个，另外2个副本仍是旧数据，此时在读取的时候，只要确保读取副本的数量大于2，那么肯定就会读到最新的数据。至于如何确定哪份数据是最新的，我们可以通过引入数据版本号的方式判断（Quorum 机制的使用需要配合一个获取最新成功提交的版本号的 metadata 服务，这样可以确定最新已经成功提交的版本号，然后从已经读到的数据中就可以确认最新写入的数据。）

七、WARO 机制

　　WARO(Write All Read one)是一种简单的副本控制协议，当Client请求向某副本写数据时(更新数据)，只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。

分布式系统

PacificA

Bigtable

HBase

GFS

HDFS

参考资料

一致性算法分析

Paxos算法详解

理解分布式一致性:Paxos协议之Basic Paxos