微信读书：从Paxos到Zookeeper：分布式一致性原理与实践（阅读摘录）
阅读地址
CAP理论
CAP理论告诉我们，一个分布式系统不可能同时满足一致性(C：Consistency)、可用性(A：Availability)和分区容错性(P：Partition tolerance)这三个基本需求，最多只能同时满足其中的两项。
BASE理论
BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent （最终一致性）三个短语的简写，是由来自eBay的架构师Dan Pritchett在其文章BASE：An Acid Alternative[插图]中第一次明确提出。
2PC与3PC
2PC
2PC，是Two-Phase Commit的缩写，即二阶段提交，是计算机网络尤其是在数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种算法。通常，二阶段提交协议也被认为是一种一致性协议，用来保证分布式系统数据的一致性。目前，绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理的，利用该协议能够非常方便地完成所有分布式事务参与者的协调，统一决定事务的提交或回滚，从而能够有效地保证分布式数据一致性，因此二阶段提交协议被广泛地应用在许多分布式系统中。
3PC
3PC，是Three-Phase Commit的缩写，即三阶段提交，是2PC的改进版，其将二阶段提交协议的“提交事务请求”过程一分为二，形成了由CanCommit、PreCommit和do Commit三个阶段组成的事务处理协议。
Paxos算法
拜占廷将军问题
拜占庭帝国有许多支军队，不同军队的将军之间必须制订一个统一的行动计划，从而做出进攻或者撤退的决定，同时，各个将军在地理上都是被分隔开来的，只能依靠军队的通讯员来进行通讯。然而，在所有的通讯员中可能会存在叛徒，这些叛徒可以任意篡改消息，从而达到欺骗将军的目的。
这就是著名的“拜占廷将军问题”。从理论上来说，在分布式计算领域，试图在异步系统和不可靠的通道上来达到一致性状态是不可能的，因此在对一致性的研究过程中，都往往假设信道是可靠的。而事实上，大多数系统都是部署在同一个局域网中的，因此消息被篡改的情况非常罕见；另一方面，由于硬件和网络原因而造成的消息不完整问题，只需一套简单的校验算法即可避免——因此，在实际工程实践中，可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被篡改的。那么，在这种情况下需要什么样的算法来保证一致性呢？
ZooKeeper的ZAB协议
ZooKeeper并没有完全采用Paxos算法，而是使用了一种称为ZooKeeper Atomic Broadcast（ZAB，ZooKeeper原子消息广播协议）的协议作为其数据一致性的核心算法。
ZAB协议的核心是定义了对于那些会改变ZooKeeper服务器数据状态的事务请求的处理方式，即：
所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的其他服务器则成为Follower服务器。Leader服务器负责将一个客户端事务请求转换成一个事务Proposal（提议），并将该Proposal分发给集群中所有的Follower服务器。之后Leader服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower服务器分发Commit消息，要求其将前一个Proposal进行提交。
ZooKeeper的Watcher的特性
- 一次性
- 客户端串行执行
- 轻量
ZooKeeper的ACL机制
ZooKeeper的ACL权限控制和Unix/Linux操作系统中的ACL有一些区别，读者可以从三个方面来理解ACL机制，分别是：权限模式(Scheme)、授权对象(ID)和权限(Permission)，通常使用“scheme：id：permission”来标识一个有效的ACL信息。
ZooKeeper的会话激活
为了保持客户端会话的有效性，在ZooKeeper的运行过程中，客户端会在会话超时时间过期范围内向服务端发送PING请求来保持会话的有效性，我们俗称“心跳检测”。
单机版ZooKeeper服务器启动流程
集群版ZooKeeper服务器启动流程
Leader
在接收到来自其他服务器的投票后，针对每一个投票，服务器都需要将别人的投票和自己的投票进行PK，PK的规则如下。
- 优先检查ZXID。ZXID比较大的服务器优先作为Leader。
- 如果ZXID相同的话，那么就比较myid。myid比较大的服务器作为Leader服务器。
一旦Leader所在的机器挂了，那么整个集群将暂时无法对外服务，而是进入新一轮的Leader选举。
简单地说，通常哪台服务器上的数据越新，那么越有可能成为Leader，原因很简单，数据越新，那么它的ZXID也就越大，也就越能够保证数据的恢复。当然，如果集群中有几个服务器具有相同的ZXID，那么SID较大的那台服务器成为Leader。
Quorum：过半机器数
这是整个Leader选举算法中最重要的一个术语，我们可以把这个术语理解为是一个量词，指的是ZooKeeper集群中过半的机器数，如果集群中总的机器数是n的话，那么可以通过下面这个公式来计算quorum的值：
例如，如果集群机器总数是3，那么quorum就是2。
请求处理链
使用责任链模式来处理每一个客户端请求是ZooKeeper的一大特色。
Foller
从角色名字上可以看出，Follower服务器是ZooKeeper集群状态的跟随者，其主要工作有以下三个。
- 处理客户端非事务请求，转发事务请求给Leader服务器。
- 参与事务请求Proposal的投票。
- 参与Leader选举投票。
Observer
Observer是ZooKeeper自3.3.0版本开始引入的一个全新的服务器角色。从字面意思看，该服务器充当了一个观察者的角色——其观察ZooKeeper集群的最新状态变化并将这些状态变更同步过来。Observer服务器在工作原理上和Follower基本是一致的，对于非事务请求，都可以进行独立的处理，而对于事务请求，则会转发给Leader服务器进行处理。和Follower唯一的区别在于，Observer不参与任何形式的投票，包括事务请求Proposal的投票和Leader选举投票。简单地讲，Observer服务器只提供非事务服务，通常用于在不影响集群事务处理能力的前提下提升集群的非事务处理能力。
ZooKeeper的消息类型
ZooKeeper的消息类型大体上可以分为四类，分别是：数据同步型、服务器初始化型、请求处理型和会话管理型。
四字命令
高可用集群
要搭建一个高可用的ZooKeeper集群，我们首先需要确定好集群的规模。关于ZooKeeper集群的服务器组成，相信很多对ZooKeeper了解但是理解不深入的读者，都存在或曾经存在过这样一个错误的认识：为了使得ZooKeeper集群能够顺利地选举出Leader，必须将ZooKeeper集群的服务器数部署成奇数。这里我们需要澄清的一点是：任意台ZooKeeper服务器都能部署且能够正常运行。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
Lempel-Ziv (LZ) 算法是一系列无损数据压缩算法，包括LZ77、LZ78和LZW等。这些算法通过利用字典来存储已经遇到的字符串，并用相应的索引来代替重复出现的字符串，从而实现压缩效果。下面是一个简单的例程，展示了如何使用LZ77算法来压缩和解压缩文…
