当前业界有很多分布式一致性复制协议，比如Paxos，Zab，Viewstamped Replication等，其中Lamport提出的Paxos被认为是分布式一致性复制协议的根本，其他的一致性复制协议都是其变种。但是Paxos论文中只给出了单个提案的过程，并没有给出复制状态机中需要的MultiPaxos的相关细节描述。 Zab协议被应用在Zookeeper中，业界使用广泛，但是没有抽象成通用library。Viewstamped Replication虽然出来的比较早，但是一直没有流行起来，也没有几个实现。基于这几类分布式一致性复制协议可以构建满足CP(强一致性和分区容忍性)的分布式系统，对于可用性会因为保证多数副本存活和选主期间不可读写而打些折扣。 Raft是斯坦福大学RamCloud项目中提出的分布式一致性复制协议，以易于理解著称，自推出之后业界涌现了很多Raft的实现，包括CoreOS的etcd等。Raft比Zab和Viewstamped Replication简化了协议中的状态和交互，更加清晰容易理解，更加容易实现。 节点状态 Leader：接收Client的请求，并进行复制，任何时刻只有一个Leader Follower：被动接收各种RPC请求 Candidate：用于选举出一个新的Leader Raft中Follower长时间没有接受到心跳就会转为Candidate状态，收到多数投票应答之后可以转为Leader，Leader会定期向其他节点发送心跳。当Leader和Candidate接收到更高版本的消息后，转为Follower。具体节点状态转移图如下： 两种RPC RequestVote 由Candidate调用来征集投票 AppendEntries 由Leader调用。也会用作Heartbeat Leader Election Raft中将时间划分到Term，用于选举，标示某个Leader下的Normal Case，每个Term最多只有一个Leader，某些Term可能会选主失败而没有Leader（未达到多数投票应答而超时）。 Raft的选主过程中，每个Candidate节点先将本地的CurrentTerm加一，然后向其他节点发送RequestVote请求，其他节点根据本地数据版本、长度和之前选主的结果判断应答成功与否。具体处理规则如下： 如果now – lastLeaderUpdateTimestamp < elect_timeout，忽略请求 如果req.Term < currentTerm，忽略请求。 如果req.Term > currentTerm，设置req.Term到currentTerm中，如果是Leader和Candidate转为Follower。 如果req.Term == currentTerm，并且本地voteFor记录为空或者是与vote请求中Term和CandidateId一致，req.lastLogIndex > lastLogIndex，即Candidate数据新于本地则同意选主请求。 如果req.Term == currentTerm，如果本地voteFor记录非空并且是与vote请求中Term一致CandidateId不一致，则拒绝选主请求。 如果lastLogTerm > req.lastLogTerm，本地最后一条Log的Term大于请求中的lastLogTerm，说明candidate上数据比本地旧，拒绝选主请求。 上面的选主请求处理，符合Paxos的"少数服从多数，后者认同前者"的原则。按照上面的规则，选举出来的Leader，一定是多数节点中Log数据最新的节点。下面来分析一下选主的时间和活锁问题，设定Follower检测Leader Lease超时为HeartbeatTimeout，Leader定期发送心跳的时间间隔将小于HeartbeatTimeout，避免Leader Lease超时，通常设置为小于HeartbeatTimeout/2。当选举出现冲突，即存在两个或多个节点同时进行选主，且都没有拿到多数节点的应答，就需要重新进行选举，这就是常见的选主活锁问题。Raft中引入随机超时时间机制，有效规避活锁问题。 注意上面的Log新旧的比较，是基于lastLogTerm和lastLogIndex进行比较，而不是基于currentTerm和lastLogIndex进行比较。currentTerm只是用于忽略老的Term的vote请求，或者提升自己的currentTerm，并不参与Log新旧的决策。考虑一个非对称网络划分的节点，在一段时间内会不断的进行vote，并增加currentTerm，这样会导致网络恢复之后，Leader会接收到AppendEntriesResponse中的Term比currentTerm大，Leader就会重置currentTerm并进行StepDown，这样Leader就对齐自己的Term到划分节点的Term，重新开始选主，最终会在上一次多数集合中选举出一个Term>=划分节点Term的Leader。 Log Replication 一旦选举出了一个Leader，它就开始负责服务客户端的请求。每个客户端的请求都包含一个要被复制状态机执行的指令。Leader首先要把这个指令追加到Log中形成一个新的Enrty，然后通过AppendEntries并行的把该Enrty发给其他servers，其他server如果发现没问题，复制成功后会给Leader一个表示成功的ACK，Leader收到大多数ACK后应用该日志，返回客户端执行结果。如果followers crash或者丢包，Leader会不断重试AppendEntries。Logs按照下图组织： 每个Log Enrty都存储着一条用于状态机的指令，同时保存从Leader收到该Enrty时的Term号。该Term号可以用来判断一些Log之间的不一致状态。每一个Enrty还有一个index指明自己在Log中的位置。 Leader需要决定什么时候将日志应用给状态机是安全的，可以被应用的Enrty叫Committed。Raft保证Committed Entries持久化，并且最终被其他状态机应用。一个Log Entry一旦复制给了大多数节点就成为Committed。同时要注意一种情况，如果当前待提交Enrty之前有未提交的Enrty，即使是以前过时的Leader创建的，只要满足已存储在大多数节点上就一次性按顺序都提交。Leader要追踪最新的Committed的index，并在每次AppendEntries（包括心跳）都要捎带，以使其他server知道一个Log Enrty是已提交的，从而在它们本地的状态机上也应用。 每个节点重启之后，先加载上一个Snapshot，再加入Raft复制组，选主或者是接收更新。因为Snapshot中的数据一定是Applied，那么肯定是Committed的，加载是安全的。但是Log中的数据，不一定是Committed的，因为我们没有持久化CommittedIndex，所以不确定Log是否是Committed，不能进行加载。这样先加载Snapshot虽然延迟了新节点加入集群的时间，但是能够保证一旦一个节点变为Leader之后能够比较快的加载完全数据，并提供服务。同理，Follower接收到InstallSnapshot之后，接收并加载完Snapshot之后再回复Leader。 Log Recovery Log Recovery这里分为Current Term修复和Prev Term修复，Log Recovery就是要保证一定已经Committed的数据不会丢失，未Committed的数据转变为Committed，但不会因为修复过程中断又重启而影响节点之间一致性。 Current Term修复主要是解决某些Follower节点重启加入集群，或者是新增Follower节点加入集群，Leader需要向Follower节点传输漏掉的Log Entry，如果Follower需要的Log Entry已经在Leader上Log Compaction清除掉了，Leader需要将上一个Snapshot和其后的Log Entry传输给Follower节点。Leader-Alive模式下，只要Leader将某一条Log Entry复制到多数节点上，Log Entry就转变为Committed。 Prev Term修复主要是在保证Leader切换前后数据的一致性。通过上面Raft的选主可以看出，每次选举出来的Leader一定包含已经Committed的数据（抽屉原理，选举出来的Leader是多数中数据最新的，一定包含已经在多数节点上Commit的数据），新的Leader将会覆盖其他节点上不一致的数据。虽然新选举出来的Leader一定包括上一个Term的Leader已经Committed的Log Entry，但是可能也包含上一个Term的Leader未Committed的Log Entry。这部分Log Entry需要转变为Committed，相对比较麻烦，需要考虑Leader多次切换且未完成Log Recovery，需要保证最终提案是一致的，确定的。Raft中增加了一个约束：对于之前Term的未Committed数据，修复到多数节点，且在新的Term下至少有一条新的Log Entry被复制或修复到多数节点之后，才能认为之前未Committed的Log Entry转为Committed。下图就是一个Prev Term Recovery的过程：...

什么是ZooKeeper ZooKeeper由Yahoo开发，后来捐赠给了Apache，现已成为Apache顶级项目。ZooKeeper是一个开源的分布式应用程序协调服务器，其为分布式系统提供一致性服务。其一致性是通过类似Paxos算法的ZAB协议完成的。其主要功能包括：配置维护、分布式同步、集群管理、分布式事务等。 简单来说，ZooKeeper是一个分布式协调服务框架 。 Paxos算法 https://juejin.im/post/58285877d203090054f6126a ZAB协议 作为一个优秀高效且可靠的分布式协调框架，ZooKeeper在解决分布式数据一致性问题时并没有直接使用Paxos，而是专门定制了一致性协议叫做ZAB(ZooKeeper Automic Broadcast)原子广播协议，该协议能够很好地支持崩溃恢复 。 ZAB中的三个角色 在介绍ZAB协议之前，我们首先来了解一下在ZAB中三个主要的角色，Leader、Follower、Observer。 Leader：集群中唯一的写请求处理者，能够发起投票（投票也是为了进行写请求）。 Follower：能够接收客户端的请求，如果是读请求则可以自己处理，如果是写请求则要转发给 Leader。在选举过程中会参与投票，有选举权和被选举权。 Observer：就是没有选举权和被选举权的Follower。 在ZAB协议中对zkServer(即上面我们说的三个角色的总称)还有两种模式的定义，分别是消息广播和崩溃恢复。 消息广播模式 第一步肯定需要Leader将写请求广播出去，让Leader问问Followers是否同意更新，如果超过半数以上的同意那么就进行Follower和Observer的更新（和Paxos一样）： 这两个队列是用于ZAB的Follower和Observer保证顺序性。何为顺序性，比如我现在有一个写请求A，此时Leader将请求A广播出去，因为只需要半数同意就行，所以可能这个时候有一个FollowerF1因为网络原因没有收到，而Leader又广播了一个请求B，因为网络原因，F1竟然先收到了请求B然后才收到了请求A，这个时候请求处理的顺序不同就会导致数据的不同，从而产生数据不一致问题。 所以在Leader这端，它为每个其他的zkServer准备了一个队列，采用先进先出的方式发送消息。由于协议是通过TCP来进行网络通信的，保证了消息的发送顺序性，接受顺序性也得到了保证。 除此之外，在ZAB中还定义了一个全局单调递增的事务ID：ZXID，它是一个64位long型，其中高32位表示epoch年代，低32位表示事务id。epoch是会根据Leader的变化而变化的，当一个Leader挂了，新的Leader上位的时候，epoch就变了。而低32位可以简单理解为递增的事务id。 定义这个的原因也是为了顺序性，每个proposal在Leader中生成后需要通过其ZXID来进行排序，才能得到处理。 崩溃恢复模式 说到崩溃恢复我们首先要提到ZAB中的Leader选举算法，当系统出现崩溃影响最大应该是Leader的崩溃，因为我们只有一个Leader，所以当Leader出现问题的时候我们势必需要重新选举Leader。 Leader选举可以分为两个不同的阶段，第一个是我们提到的Leader宕机需要重新选举，第二则是当Zookeeper启动时需要进行系统的Leader初始化选举。下面我先来介绍一下ZAB是如何进行初始化选举的。 假设我们集群中有3台机器，那也就意味着我们需要两台以上同意（超过半数）。比如这个时候我们启动了server1，它会首先投票给自己，投票内容为服务器的myid和ZXID，因为初始化所以ZXID都为0，此时server1发出的投票为(1,0)。但此时server1的投票仅为1，所以不能作为Leader，此时还在选举阶段所以整个集群处于Looking状态。 接着server2启动了，它首先也会将投票选给自己(2,0)，并将投票信息广播出去（server1也会，只是它那时没有其他的服务器了），server1在收到server2的投票信息后会将投票信息与自己的作比较。首先它会比较ZXID，ZXID大的优先为Leader，如果相同则比较myid，myid大的优先作为Leader。所以此时server1发现server2更适合做Leader，它就会将自己的投票信息更改为(2,0)然后再广播出去，之后server2收到之后发现和自己的一样无需做更改，并且自己的投票已经超过半数 ，则确定server2为Leader，server1也会将自己变为Follower。整个服务器就从Looking变为了正常状态。 当server3启动发现集群没有处于Looking状态时，它会直接以Follower的身份加入集群。 还是前面三个server的例子，如果在整个集群运行的过程中server2挂了，那么整个集群会如何重新选举Leader呢？其实和初始化选举差不多。 首先毫无疑问的是剩下的两个Follower会将自己的状态从Following变为Looking状态，然后每个server会向初始化投票一样首先给自己投票（这不过这里的zxid可能不是0了，这里为了方便随便取个数字）。 假设server1给自己投票为(1,99)，然后广播给其他server，server3首先也会给自己投票(3,95)，然后也广播给其他server。server1和server3此时会收到彼此的投票信息，和一开始选举一样，他们也会比较自己的投票和收到的投票（zxid大的优先，如果相同那么就myid大的优先）。这个时候 server1收到了server3的投票发现没自己的合适故不变，server3收到server1的投票结果后发现比自己的合适于是更改投票为(1,99)然后广播出去，最后server1收到了发现自己的投票已经超过半数就把自己设为Leader，server3也随之变为Follower。 那么说完了ZAB中的Leader选举方式之后我们再来了解一下崩溃恢复是什么。其实主要就是当集群中有机器挂了，我们整个集群如何保证数据一致性？ 如果只是Follower挂了，而且挂的没超过半数的时候，因为我们一开始讲了在Leader中会维护队列，所以不用担心后面的数据没接收到导致数据不一致性。 如果Leader挂了那就麻烦了，我们肯定需要先暂停服务变为Looking状态然后进行Leader的重新选举（上面我讲过了），但这个就要分为两种情况了，分别是确保已经被Leader提交的提案最终能够被所有的Follower提交和跳过那些已经被丢弃的提案。 确保已经被Leader提交的提案最终能够被所有的Follower提交是什么意思呢？ 假设Leader(server2) 发送commit请求，他发送给了server3，然后要发给server1的时候突然挂了。这个时候重新选举的时候我们如果把server1作为Leader的话，那么肯定会产生数据不一致性，因为server3肯定会提交刚刚server2发送的commit请求的提案，而server1根本没收到所以会丢弃。 那怎么解决呢？ 这个时候server1已经不可能成为Leader了，因为server1和server3进行投票选举的时候会比较ZXID，而此时server3的ZXID肯定比server1的大了。 那么跳过那些已经被丢弃的提案又是什么意思呢？ 假设Leader(server2)此时同意了提案N1，自身提交了这个事务并且要发送给所有Follower要commit的请求，却在这个时候挂了，此时肯定要重新进行Leader的选举，比如说此时选server1为Leader（这无所谓）。但是过了一会，这个挂掉的Leader又重新恢复了，此时它肯定会作为Follower的身份进入集群中，需要注意的是刚刚server2已经同意提交了提案N1，但其他server并没有收到它的commit信息，所以其他server不可能再提交这个提案N1了，这样就会出现数据不一致性问题了，所以该提案N1最终需要被抛弃掉。 Zookeeper的几个理论知识 了解了ZAB协议还不够，它仅仅是Zookeeper内部实现的一种方式，而我们如何通过Zookeeper去做一些典型的应用场景呢？比如说集群管理，分布式锁，Master选举等等。 这就涉及到如何使用Zookeeper了，但在使用之前我们还需要掌握几个概念。比如Zookeeper的 数据模型、会话机制、ACL、Watcher机制等等。 数据模型 zookeeper数据存储结构与标准的Unix文件系统非常相似，都是在根节点下挂很多子节点(树型)。但是Zookeeper中没有文件系统中目录与文件的概念，而是使用了znode作为数据节点。znode是Zookeeper中的最小数据单元，每个znode上都可以保存数据，同时还可以挂载子节点，形成一个树形化命名空间。 每个znode都有自己所属的节点类型和节点状态。其中节点类型可以分为持久节点、持久顺序节点、临时节点和临时顺序节点。 持久节点：一旦创建就一直存在，直到将其删除。 持久顺序节点：一个父节点可以为其子节点维护一个创建的先后顺序，这个顺序体现在节点名称上，是节点名称后自动添加一个由10位数字组成的数字串，从0开始计数。 临时节点：临时节点的生命周期是与客户端会话绑定的，会话消失则节点消失。临时节点只能做叶子节点，不能创建子节点。 临时顺序节点：父节点可以创建一个维持了顺序的临时节点(和前面的持久顺序性节点一样)。 节点状态中包含了很多节点的属性比如czxid、mzxid等等，在Zookeeper中是使用Stat这个类来维护的。下面是一些属性。 czxid：Created ZXID，该数据节点被创建时的事务ID。 mzxid：Modified ZXID，节点最后一次被更新时的事务ID。 ctime：Created Time，该节点被创建的时间。 mtime： Modified Time，该节点最后一次被修改的时间。 version：节点的版本号。 cversion：子节点的版本号。 aversion：节点的ACL版本号。 ephemeralOwner：创建该节点的会话的sessionID，如果该节点为持久节点，该值为0。 dataLength：节点数据内容的长度。 numChildre：该节点的子节点个数，如果为临时节点为0。 pzxid：该节点子节点列表最后一次被修改时的事务ID，注意是子节点的 列表 ，不是内容。 会话 Zookeeper客户端和服务端是通过TCP长连接维持的会话机制，其实对于会话来说你可以理解为保持连接状态。...

CAP理论 在分布式系统中著有CAP理论，该理论由加州大学伯克利分校的 Eric Brewer 教授提出，阐述了在一个分布式系统中不可能同时满足一致性（ Consistency）、可用性（ Availability），以及分区容错性（ Partition Tolerance）。 一致性： 在分布式系统中数据往往存在多个副本，一致性描述的是这些副本中的数据在内容和组织上的一致。 可用性： 描述系统对用户的服务能力，所谓可用是指在用户能够容忍的时间范围内返回用户期望的结果。 分区容错性： 分布式系统通常由多个节点构成，由于网络是不可靠的，所以存在分布式集群中的节点因为网络通信故障导致被孤立成一个个小集群的可能性，即网络分区，分区容错性要求在出现网络分区时系统仍然能够对外提供一致性的可用服务。 对于一个分布式系统而言，我们要始终假设网络是不可靠的，因此分区容错性是对一个分布式系统最基本的要求，我们的切入点更多的是尝试在可用性和一致性之间寻找一个平衡点，但这也并非要求我们在系统设计时一直建立在网络出现分区的前提之上，然后对一致性和可用性在选择时非此即彼。 一致性模型 强一致性 当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值，直到这个数据被其他数据更新为止。 是这种实现对性能影响较大，因为这意味着，只要上次的操作没有处理完，就不能让用户读取数据。 弱一致性 系统并不保证进程或者线程的访问都会返回最新更新过的值。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。但会尽可能保证在某个时间级别（比如秒级别）之后，可以让数据达到一致性状态。 最终一致性 最终一致性也是弱一致性的一种，它无法保证数据更新后，所有后续的访问都能看到最新数值，而是需要一个时间，在这个时间之后可以保证这一点，而在这个时间内，数据也许是不一致的，这个系统无法保证强一致性的时间片段被称为「不一致窗口」。不一致窗口的时间长短取决于很多因素，比如备份数据的个数、网络传输延迟速度、系统负载等。 两阶段提交协议（2PC：Two-Phase Commit） 两阶段提交协议的目标在于为分布式系统保证数据的一致性，许多分布式系统采用该协议提供对分布式事务的支持。顾名思义，该协议将一个分布式的事务过程拆分成两个阶段：投票和事务提交 。为了让整个数据库集群能够正常的运行，该协议指定了一个协调者单点，用于协调整个数据库集群各节点的运行。为了简化描述，我们将数据库集群中的各个节点称为参与者 ，三阶段提交协议中同样包含协调者和参与者这两个角色定义。 第一阶段：投票 该阶段的主要目的在于打探数据库集群中的各个参与者是否能够正常的执行事务，具体步骤如下： 协调者向所有的参与者发送事务执行请求，并等待参与者反馈事务执行结果； 事务参与者收到请求之后，执行事务但不提交，并记录事务日志； 参与者将自己事务执行情况反馈给协调者，同时阻塞等待协调者的后续指令。 第二阶段：事务提交 在经过第一阶段协调者的询盘之后，各个参与者会回复自己事务的执行情况，这时候存在 3 种可能性： 所有的参与者都回复能够正常执行事务。 一个或多个参与者回复事务执行失败。 协调者等待超时。 对于第 1 种情况，协调者将向所有的参与者发出提交事务的通知，具体步骤如下： 协调者向各个参与者发送commit通知，请求提交事务； 参与者收到事务提交通知之后执行commit操作，然后释放占有的资源； 参与者向协调者返回事务commit结果信息。 对于第 2 和第 3 种情况，协调者均认为参与者无法成功执行事务，为了整个集群数据的一致性，所以要向各个参与者发送事务回滚通知，具体步骤如下： 协调者向各个参与者发送事务rollback通知，请求回滚事务； 参与者收到事务回滚通知之后执行rollback操作，然后释放占有的资源； 参与者向协调者返回事务rollback结果信息。 站在协调者的角度，在发起投票之后就进入了WAIT状态，等待所有参与者回复各自事务执行状态，并在收到所有参与者的回复后决策下一步是发送commit或rollback信息。站在参与者的角度，当回复完协调者的投票请求之后便进入READY状态（能够正常执行事务），接下去就是等待协调者最终的决策通知，一旦收到通知便可依据决策执行commit或rollback操作。...

可读代码 什么是“好的代码” 简而言之，代码需要易于理解。很多时候我们都是通过直觉来写代码，我们都知道下面的代码 for (Node* node = list->head; node != NULL; node = node->next) Print(node->data); 比这个代码要更好： Node* node = list->head; if (node == NULL) return; while (node->next != NULL) { Print(node->data); node = node->next; } if (node != NULL) Print(node->data); 很明显前者要比后者简洁。然而看下面两个例子： return exponent >= 0 ? mantissa * (1 << exponent) : mantissa / (1 << -exponent); if (exponent >= 0) { return mantissa * (1 << exponent); } else { return mantissa / (1 << -exponent); } 前者虽然更加简洁，却牺牲了可读性。所以，怎样的代码才是真正的好代码呢？...