这篇文章主要用来介绍Kafka & Zookeeper相关基础知识。
1. Kafka是由Linkedin开发，是一个分布式、支持分区的（partition）、多副本的（replica），基于zookeeper协调的分布式消息系统，它的最大的特性就是可以实时的处理大量数据以满足各种需求场景，之后于2010年贡献给了Apache基金会并成为顶级开源项。
2. Zookeeper是专为分布式系统设计的开源协调系统，类似一个大管家，用来管理分布式应用的数据管理问题。Zookeeper本身就是高可用的，基于Cluster（一个Leader，多个Follower）的。ZooKeeper是以Fast Paxos算法为基础，实现同步服务，配置维护和命名服务等分布式应用。
根据官方文档，我简单部署了Kafka示例。
《Paxos到Zookeeper：分布式一致性原理与实践》从分布式一致性的理论出发，向读者简要介绍几种典型的分布式一致性协议，以及解决分布式一致性问题的思路，其中重点讲解了Paxos和ZAB协议。同时，本书深入介绍了分布式一致性问题的工业解决方案——ZooKeeper，并着重向读者展示这一分布式协调框架的使用方法、内部实现及运维技巧，旨在帮助读者全面了解ZooKeeper，并更好地使用和运维ZooKeeper。全书共8章，分为五部分：第一部分（第1章）主要介绍了计算机系统从集中式向分布式系统演变过程中面临的挑战，并简要介绍了ACID、CAP和BASE等经典分布式理论；第二部分（第2～4章）介绍了2PC、3PC和Paxos三种分布式一致性协议，并着重讲解了ZooKeeper中使用的一致性协议——ZAB协议；第三部分（第5～6章）介绍了ZooKeeper的使用方法，包括客户端API的使用以及对ZooKeeper服务的部署与运行，并结合真实的分布式应用场景，总结了ZooKeeper使用的最佳实践；第四部分（第7章）对ZooKeeper的架构设计和实现原理进行了深入分析，包含系统模型、Leader选举、客户端与服务端的工作原理、请求处理，以及服务器角色的工作流程和数据存储等；第五部分（第8章）介绍了ZooKeeper的运维实践，包括配置详解和监控管理等，重点讲解了如何构建一个高可用的ZooKeeper服务。
在一个分布式系统中，由于节点故障、网络延迟等各种原因，根据CAP理论，我们只能保证一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance）中的两个。
对于一致性要求高的系统，比如银行取款机，就会选择牺牲可用性，故障时拒绝服务。MongoDB、Redis、MapReduce使用这种方案。
对于静态网站、实时性较弱的查询类数据库，会牺牲一致性，允许一段时间内不一致。简单分布式协议Gossip，数据库CouchDB、Cassandra使用这种方案。
图1
如图1所示，一致性问题，可以根据是否存在恶意节点分类两类。无恶意节点，是指节点会丢失、重发、不响应消息，但不会篡改消息。而恶意节点可能会篡改消息。有恶意节点的问题称为拜占庭将军问题，不在今天的讨论范围。Paxos很好地解决了无恶意节点的分布式一致性问题。
背景
1990年，Leslie Lamport在论文《The Part-Time Parliament》中提出Paxos算法。由于论文使用故事的方式，没有使用数学证明，起初并没有得到重视。直到1998年该论文才被正式接受。后来2001年Lamport又重新组织了论文，发表了《Paxos Made Simple》。作为分布式系统领域的早期贡献者，Lamport获得了2013年图灵奖。
Paxos算法广泛应用在分布式系统中，Google Chubby的作者Mike Burrows说：“这个世界上只有一种一致性算法，那就是 Paxos（There is only one consensus protocol, and that's Paxos）”。
后来的Raft算法、是对Paxos的简化和改进，变得更加容易理解和实现。
Paxos类型
Paxos本来是虚构故事中的一个小岛，议会通过表决来达成共识。但是议员可能离开，信使可能走丢，或者重复传递消息。对应到分布式系统的节点故障和网络故障。
图2
如图2所示，假设议员要提议中午吃什么。如果有一个或者多个人同时提议，但一次只能通过一个提议，这就是Basic Paxos，是Paxos中最基础的协议。
显然Basic Paxos是不够高效的，如果将Basic Paxos并行起来，同时提出多个提议，比如中午吃什么、吃完去哪里嗨皮、谁请客等提议，议员也可以同时通过多个提议。这就是Multi-Paxos协议。
Basic Paxos
角色
Paxos算法存在3种角色：Proposer、Acceptor、Learner，在实现中一个节点可以担任多个角色。
图3
- Proposer负责提出提案
- Acceptor负责对提案进行投票
- Learner获取投票结果，并帮忙传播
Learner不参与投票过程，为了简化描述，我们直接忽略掉这个角色。
算法
运行过程分为两个阶段，Prepare阶段和Accept阶段。
Proposer需要发出两次请求，Prepare请求和Accept请求。Acceptor根据其收集的信息，接受或者拒绝提案。
Prepare阶段
- Proposer选择一个提案编号n，发送Prepare(n)请求给超过半数（或更多）的Acceptor。
- Acceptor收到消息后，如果n比它之前见过的编号大，就回复这个消息，而且以后不会接受小于n的提案。另外，如果之前已经接受了小于n的提案，回复那个提案编号和内容给Proposer。
Accept阶段
- 当Proposer收到超过半数的回复时，就可以发送Accept(n, value)请求了。 n就是自己的提案编号，value是Acceptor回复的最大提案编号对应的value，如果Acceptor没有回复任何提案，value就是Proposer自己的提案内容。
- Acceptor收到消息后，如果n大于等于之前见过的最大编号，就记录这个提案编号和内容，回复请求表示接受。
- 当Proposer收到超过半数的回复时，说明自己的提案已经被接受。否则回到第一步重新发起提案。
完整算法如图4所示：
图4
Acceptor需要持久化存储minProposal、acceptedProposal、acceptedValue这3个值。
三种情况
Basic Paxos共识过程一共有三种可能的情况。下面分别进行介绍。
情况1：提案已接受
如图5所示。X、Y代表客户端，S1到S5是服务端，既代表Proposer又代表Acceptor。为了防止重复，Proposer提出的编号由两部分组成：
序列号.Server ID
例如S1提出的提案编号，就是1.1、2.1、3.1……
图5 以上图片来自Paxos lecture (Raft user study)第13页
这个过程表示，S1收到客户端的提案X，于是S1作为Proposer，给S1-S3发送Prepare(3.1)请求，由于Acceptor S1-S3没有接受过任何提案，所以接受该提案。然后Proposer S1-S3发送Accept(3.1, X)请求，提案X成功被接受。
在提案X被接受后，S5收到客户端的提案Y，S5给S3-S5发送Prepare(4.5)请求。对S3来说，4.5比3.1大，且已经接受了X，它会回复这个提案 (3.1, X)。S5收到S3-S5的回复后，使用X替换自己的Y，于是发送Accept(4.5, X)请求。S3-S5接受提案。最终所有Acceptor达成一致，都拥有相同的值X。
这种情况的结果是：新Proposer会使用已接受的提案
情况2：提案未接受，新Proposer可见
图6 以上图片来自Paxos lecture (Raft user study)第14页
如图6所示，S3接受了提案(3.1, X)，但S1-S2还没有收到请求。此时S3-S5收到Prepare(4.5)，S3会回复已经接受的提案(3.1, X)，S5将提案值Y替换成X，发送Accept(4.5, X)给S3-S5，对S3来说，编号4.5大于3.1，所以会接受这个提案。
然后S1-S2接受Accept(3.1, X)，最终所有Acceptor达成一致。
这种情况的结果是：新Proposer会使用已提交的值，两个提案都能成功
情况3：提案未接受，新Proposer不可见
图7 以上图片来自Paxos lecture (Raft user study)第15页
如图7所示，S1接受了提案(3.1, X)，S3先收到Prepare(4.5)，后收到Accept(3.1, X)，由于3.1小于4.5，会直接拒绝这个提案。所以提案X无法收到超过半数的回复，这个提案就被阻止了。提案Y可以顺利通过。
这种情况的结果是：新Proposer使用自己的提案，旧提案被阻止
活锁 (livelock)
活锁发生的几率很小，但是会严重影响性能。就是两个或者多个Proposer在Prepare阶段发生互相抢占的情形。
图8 以上图片来自Paxos lecture (Raft user study)第16页
解决方案是Proposer失败之后给一个随机的等待时间，这样就减少同时请求的可能。
Multi-Paxos
上一小节提到的活锁，也可以使用Multi-Paxos来解决。它会从Proposer中选出一个Leader，只由Leader提交Proposal，还可以省去Prepare阶段，减少了性能损失。当然，直接把Basic Paxos的多个Proposer的机制搬过来也是可以的，只是性能不够高。
将Basic Paxos并行之后，就可以同时处理多个提案了，因此要能存储不同的提案，也要保证提案的顺序。
Acceptor的结构如图9所示，每个方块代表一个Entry，用于存储提案值。用递增的Index来区分Entry。
图9
Multi-Paxos需要解决几个问题，我们逐个来看。
1. Leader选举
一个最简单的选举方法，就是Server ID最大的当Leader。
每个Server间隔T时间向其他Server发送心跳包，如果一个Server在2T时间内没有收到来自更高ID的心跳，那么它就成为Leader。
其他Proposer，必须拒绝客户端的请求，或将请求转发给Leader。
当然，还可以使用其他更复杂的选举方法，这里不再详述。
2. 省略Prepare阶段
Prepare的作用是阻止旧的提案，以及检查是否有已接受的提案值。
当只有一个Leader发送提案的时候，Prepare是不会产生冲突的，可以省略Prepare阶段，这样就可以减少一半RPC请求。
Prepare请求的逻辑修改为：
- Acceptor记录一个全局的最大提案编号
- 回复最大提案编号，如果当前entry以及之后的所有entry都没有接受任何提案，回复noMoreAccepted
当Leader收到超过半数的noMoreAccepted回复，之后就不需要Prepare阶段了，只需要发送Accept请求。直到Accept被拒绝，就重新需要Prepare阶段。
3. 完整信息流
目前为止信息是不完整的。
- Basic Paxos只需超过半数的节点达成一致。但是在Multi-Paxos中，这种方式可能会使一些节点无法得到完整的entry信息。我们希望每个节点都拥有全部的信息。
- 只有Proposer知道一个提案是否被接受了（根据收到的回复），而Acceptor无法得知此信息。
第1个问题的解决方案很简单，就是Proposer给全部节点发送Accept请求。
第2个问题稍微复杂一些。首先，我们可以增加一个Success RPC，让Proposer显式地告诉Acceptor，哪个提案已经被接受了，这个是完全可行的，只不过还可以优化一下，减少请求次数。
我们在Accept请求中，增加一个firstUnchosenIndex参数，表示Proposer的第一个未接受的Index，这个参数隐含的意思是，对该Proposer来说，小于Index的提案都已经被接受了。因此Acceptor可以利用这个信息，把小于Index的提案标记为已接受。另外要注意的是，只能标记该Proposer的提案，因为如果发生Leader切换，不同的Proposer拥有的信息可能不同，不区分Proposer直接标记的话可能会不一致。
图10
如图10所示，Proposer正在准备提交Index=2的Accept请求，0和1是已接受的提案，因此firstUnchosenIndex=2。当Acceptor收到请求后，比较Index，就可以将Dumplings提案标记为已接受。
由于之前提到的Leader切换的情况，仍然需要显式请求才能获得完整信息。在Acceptor回复Accept消息时，带上自己的firstUnchosenIndex。如果比Proposer的小，那么就需要发送Success(index, value)，Acceptor将收到的index标记为已接受，再回复新的firstUnchosenIndex，如此往复直到两者的index相等。
总结
Paxos是分布式一致性问题中的重要共识算法。这篇文章分别介绍了最基础的Basic Paxos，和能够并行的Multi-Paxos。
在Basic Paxos中，介绍了3种基本角色Proposer、Acceptor、Learner，以及提案时可能发生的3种基本情况。在Multi-Paxos中，介绍了3个需要解决的问题：Leader选举、Prepare省略、完整信息流。
在下一篇文章中，我们将实现一个简单的demo来验证这个算法，实现过程将会涉及到更多的细节。
背景
Paxos算法是Lamport于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使Lamport在八年后重新发表到TOCS上。即便如此paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述。可见Lamport对paxos算法情有独钟。近几年paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪，其中的chubby锁服务使用paxos作为chubby cell中的一致性算法，paxos的人气从此一路狂飙。
Paxos是什么
Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致，是分布式计算中的重要问题。
Paxos的两个原则
安全原则---保证不能做错的事
1. 只能有一个值被批准，不能出现第二个值把第一个覆盖的情况
2. 每个节点只能学习到已经被批准的值，不能学习没有被批准的值
存活原则---只要有多数服务器存活并且彼此间可以通信最终都要做到的事
1. 最终会批准某个被提议的值
2. 一个值被批准了，其他服务器最终会学习到这个值
Paxos的两个组件
Proposer
提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。
Acceptor
提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值
Paxos定义
接下来用举例的方式一步一步解释Paxos为了完成一致性，必须要解决的一些问题。这里为了方便解释，假设每一台服务器都是一个Proposer，也是一个Acceptor
一个Acceptor
首先从最简单的方式开始，假设只有一个Acceptor，让它做决定是否批准一个值
如上图，每一个proposer提议一个值给Acceptor来批准，然后Acceptor批准一个值作为最终的值。
但是这种简单的方式，没有办法解决Acceptor crash的问题，如果唯一的Acceptor crash了，就没有办法知道哪个值被选择了，就需要等待它重启，这一条违反了存活原则，这个时候有4台服务器存活，但已经没有办法工作了。
多个Acceptor
为了解决这个问题，就必须要用到一种多数选择的方法。使用一个Acceptor的集合。然后只有其中的多数批准了一个值，这个值才可以确实是被最终被批准的。为了达到目的也需要一些技巧。
批准第一个达到的值
首先规定每个Acceptor必须批准第一个到达的值。哪个值达到多数批准就是最终批准的值
但是有一个问题，比如上图，因为没有值被多数批准，无法批准一个最终的值出来。这就需要Acceptor批准了一个值之后还要根据某种规则批准不同的值
批准每个提议的值
接下来规定Acceptor批准每个提议的值，但是这也会带来一个问题，可能会批准出多个值
如图，S1发出提议，S1，S2，S3批准 red为最终批准的值。S5随后发出提议，s3，S4，S5批准，blue又为最终批准的值。此时S1，S2最终批准red，S3，S4，S5最终批准blue，这就违背了我们的一致性原则，最终只有一个值被选择。
二段提交原则
要解决这个问题，就要S5在发送自己的提议之前，优先检查有没有已经被批准的值，如果有应该提议已经被批准的值而放弃自己的值，也就是放弃自己的blue改为提议red，这样最终只有一个值被批准就是red。这个就是经典的二段提交原则。
不幸的是，二段提交还是存在另一个问题。
如图，S1在发送提议之前，检查没有值被批准，因此提议red。但同时在所有Acceptor批准之前，S5也要进行提议，这个时候也检查出没有值被批准，所以它也把自己的blue作为提议发送给acceptor。接下来S5的提议优先到达S3，S4，S5，这些Acceptor先批准了blue，达到多数所以blue最终被批准了。但是随后S1，S2，S3接收到了red进行批准。所以又出现了批准出多个值的问题。
提议排序
这个问题要解决，就需要一旦Acceptor批准了某个值，其他有冲突的值都应该被拒绝。也就是说S3随后到达的red应该被拒绝，为了做到这一点。需要对Proposer进行排序，将排序在前的赋予高优先级，Acceptor批准优先级高的值，拒绝排序在后的值。
为了将提议进行排序，可以为每个提议赋予一个唯一的ID，规定这个ID越大，优先级越高
在提议者发送提议之前，就需要生成一个唯一的ID，而且需要比之前使用的或者生成的都要大
提议ID生成算法
在Google的Chubby论文中给出了这样一种方法：假设有n个proposer，每个编号为ir(0<=ir<n)，proposor编号的任何值s都应该大于它已知的最大值，并且满足：s %n = ir => s = m*n + ir
proposer已知的最大值来自两部分：proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值
以3个proposer P1、P2、P3为例，开始m=0,编号分别为0，1，2
1. P1提交的时候发现了P2已经提交，P2编号为1 > P1的0，因此P1重新计算编号：new P1 = 1*3+0 = 4
2. P3以编号2提交，发现小于P1的4，因此P3重新编号：new P3 = 1*3+2 = 5
Paxos算法
到此阶段，要保证Paxos的两个原则已经都满足了，Paxos也就顺利的实现了。
二段提交
prepare 阶段：
1. Proposer 选择一个提案编号 n 并将 prepare 请求发送给 Acceptors 中的一个多数派；
2. Acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 Acceptor 将自己上次接受的提案回复给 Proposer，并承诺不再回复小于 n 的提案；
acceptor阶段：
1. 当一个 Proposer 收到了多数 Acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的 Acceptors 发送 accept 请求，包括编号 n 和根据 prepare阶段 决定的 value（如果根据 prepare 没有已经接受的 value，那么它可以自由决定 value）。
2. 在不违背自己向其他 Proposer 的承诺的前提下，Acceptor 收到 accept 请求后即接受这个请求。
prepare阶段有两个目的，第一检查是否有被批准的值，如果有，就改用批准的值。第二如果之前的提议还没有被批准，则阻塞掉他们以便不让他们和我们发生竞争，当然最终由提议ID的大小决定。整个过程如下图
原文链接：https://blog.csdn.net/heiyeshuwu/java/article/details/42426811