分布式原理学习

通过分布式原理的学习。明白了很多现如今的分布式系统的设计细节的原理所在。

1.关于ZooKeeper为代表的工程实现选用TCP进行传输：

TCP协议的优势：

TCP协议为应用层提供了可靠的、面向连接的传输服务。TCP协议是最优秀的传输层协议之一，
其设计初衷就是在不可靠的网络之上建立可靠的传输服务。TCP 协议通过为传输的每一个字节设置
顺序递增的序列号，由接收方在收到数据后按序列号重组数据并发送确认信息，当发现数据包丢失
时，TCP 协议重传丢失的数据包，从而 TCP 协议解决了网络数据包丢失的问题和数据包乱序问题。
TCP 协议为每个 TCP 数据段（以太网上通常最大为 1460 字节）使用 32 位的校验和从而检查数据错
误问题。TCP 协议通过设置接收和发送窗口的机制极大的提高了传输性能，解决了网络传输的时延
与吞吐问题。TCP 协议最为复杂而巧妙的是其几十年来不断改进的拥塞控制算法，使得 TCP 可以动
态感知底层链路的带宽加以合理使用并与其他 TCP 链接分享带宽（TCP friendly）。

TCP协议在分布式系统中的不足：
上述种种使得 TCP 协议成为一个在通常情况下非常可靠的协议，然而在分布式系统的协议设计
中不能认为所有网络通信都基于 TCP 协议则通信就是可靠的。一方面，TCP 协议保证了 TCP 协议
栈之间的可靠的传输，但无法保证两个上层应用之间的可靠通信。通常的，当某个应用层程序通过
TCP 的系统调用发送一个网络消息时，即使 TCP 系统调用返回成功，也仅仅只能意味着该消息被本
机的 TCP 协议栈接受，一般这个消息是被放入了 TCP 协议栈的缓冲区中。再退一步讲，即使目的
机器的 TCP 协议栈后续也正常收到了该消息，并发送了确认数据包，也仅仅意味着消息达到了对方
机器的协议栈，而不能认为消息被目标应用程序进程接收到并正确处理了。当发送过程中出现宕机
等异常时，TCP 协议栈缓冲区中的消息有可能被丢失从而无法被目标节点正确处理。更有甚者，在
网络中断前，某数据包已经被目标进程正确处理，之后网络立刻中断，由于接收方的 TCP 协议栈发
送的确认数据包始终被丢失，发送方的 TCP 协议栈也有可能告知发送进程发送失败。另一方面，TCP
协议只能保证同一个 TCP 链接内的网络消息不乱序，TCP 链接之间的网络消息顺序则无法保证。但
在分布式系统中，一个节点向另一个节点发送数据，有可能是先后使用多个 TCP 链接发送，也有可
能是同时并发多个 TCP 链接发送，那么发送进程不能认为先调用 TCP 系统调用发送的消息就一定
会先于后发送的消息到达对方节点并被处理

ZooKeeper采用TCP的考虑：
基于上面两方面的考虑，ZooKeeper选用TCP进行传输，主要考虑到以下两个方面：
首先，Zookeeper 的协议运行依赖 TCP 协议实现 FIFO，Zookeeper 通过 TCP 协议获得两点保障：
1、数据总是严格按照 FIFO（first in first out）规则从一个节点传递到另一个节点的；2、当某个 TCP
链接关闭后，这个链接上不再有数据传递。由于 TCP 协议为传输的每一个字节设置了序列号
(sequence number)及确认(acknowledgment)，上述两点在 TCP 协议上是完全可以保证的。需要注意的
是Zookeeper并不要求TCP协议可以可靠的将数据传输到对端节点，基于 TCP 协议实现真正意义上的可靠传输也是做不到的。Zookeeper 基于 TCP 的上述两点保障，可以较大的简化问题模型，忽略诸如网络消息乱序、网络消息重复等的异常，从而较大的简化协议设计。

从此可以看到ZooKeeper采用TCP是为了更好解决分布式系统中的网络异常情况。网络异常主要包括消息丢失、消息乱序、数据错误等因素。

2关于判定集群中节点中的状态，主要是使用了lease机制。ZooKeeper中的实现
关于lease机制的详细内容我就不说了，这种机制相较于传统的心跳机制更加强大，传统的基于心跳机制可能会出现很多问题，比如下面的情况：

节点 A、B、C 可以周期性的向 Q 发送心跳信息，如果节点 Q 超过一段时间收不到某个节点的心跳则认为这个节点异常。这种方法的问题是假如节点 Q 收不到节点 A 的心跳，除了节点 A 本身的异常外，也有可能是因为节点 Q 与节点 A 之间的网络中断导致的。在工程实践中，更大的可能性不是网络中断，而是节点 Q 与节点 A 之间的网络拥塞造成的所谓“瞬断”，“瞬断”往往很快可以恢复。另一种原因甚至是节点 Q 的机器异常，以至于处理节点 A 的心跳被延迟了，以至于节点 Q 认为节点 A 没有发送心跳。假设节点 A 本身工作正常，但 Q 与节点 A 之间的网络暂时中断，节点 A 与节点 B、C 之间的网络正常。此时节点 Q 认为节点 A 异常，重新选择节点 B 作为新的 primary，并通知节点 A、B、C 新的 primary 是节点 B。由于节点 Q 的通知消息到达节点 A、B、C 的顺序无法确定，假如先到达 B，则在这一时刻，系统中同时存在两个工作中的 primary，一个是 A、另一个是 B。假如此时 A、B 都接收外部请求并与 C 同步数据，会产生严重的数据错误。上述即所谓“双主”问题，虽然看似这种问题出现的概率非常低，

lease机制实现：

由中心节点向其他节点发送 lease，若某个节点持有有效的 lease，则认为该节点正常可以提供服

务。用于例 2.3.1 中，节点 A、B、C 依然周期性的发送 heart beat 报告自身状态，节点 Q 收到 heart beat

后发送一个 lease，表示节点 Q 确认了节点 A、B、C 的状态，并允许节点在 lease 有效期内正常工

作。节点 Q 可以给 primary 节点一个特殊的 lease，表示节点可以作为 primary 工作。一旦节点 Q 希

望切换新的 primary，则只需等前一个 primary 的 lease 过期，则就可以安全的颁发新的 lease 给新的

primary 节点，而不会出现“双主”问题。

在实际系统中，若用一个中心节点发送 lease 也有很大的风险，一旦该中心节点宕机或网络异常，

则所有的节点没有 lease，从而造成系统高度不可用。为此，实际系统总是使用多个中心节点互为副

本，成为一个小的集群，该小集群具有高可用性，对外提供颁发 lease 的功能。chubby 和 zookeeper

都是基于这样的设计。

ZooKeeper中的lease机制
Zookeeper 中的 secondary 节点（在 zookeeper 中称之为 follower）并不向 primary

节点（在 zookeeper 中称之为 leader）发送 lease，zookeeper 中的 secondary 节点如果发现没有 primary

节点则发起新的 paxos 选举，只要 primary 与 secondary 工作正常，新发起的选举由于缺乏多数

secondary的参与而不会成功。与Chubby类似的是，Zookeeper的primary节点也会向client颁发lease，

lease 的时间正是 zookeeper 中的 session 时间。在 Zookeeper 中，临时节点是与 session 的生命期绑定

的，当一个 client 的 session 超时，那么这个 client 创建的临时节点会被 zookeeper 自动删除。通过监

控临时节点的状态，也可以很容易的实现对节点状态的监控。在这一点上，zookeeper 和 chubby 完

全是异曲同工。

ZooKeeper中的案例实现如下：

ZooKeeper上创建一个EPHEMERAL类型的目录节点，然后每个Server在它们创建目录节点的父目录节点上进行监视。

3.关于副本的控制策略，由于ZooKeeper采用的paxos算法中就参考了Quorum机制。

Zookeeper 使用的 paxos 协议本身就是利用了 Quorum机制，当利用 paxos 协议外选出 primary 后，Zookeeper 的更新流量由 primary 节点控制，每次更新操作，primary 节点只需更新超过半数（含自身）的节点后就返回用户成功。每次更新操作都会递增各个节点的版本号（xzid）。当 primary 节点异常，利用 paxos 协议选举新的 primary 时，每个节点都会以自己的版本号发起 paxos 提议，从而保证了选出的新 primary 是某个超过半数副本集合中版本号最大的副本。这个原则与 2.4.5 中描述的完全一致。值得一提的是，在 2.4.5 中分析到，新 primary 的版本号未必是一个最新已提交的版本，可能是一个只更新了少于半数副本的中间态的更新版本，此时新primary 完成与超过半数的副本同步后，这个版本的数据自动满足 quorum 的半数要求；另一方面，新 primary 的版本可能是一个最新已提交的版本，但可能会存在其他副本没有参与选举但持有一个
大于新 primary 的版本号的数据（中间态版本），和 2.4.5 分析的一样，此时这样的中间态版本数据将被认为是脏数据，在与新 primary 进行数据同步时被 zookeeper 丢弃。

从上面的叙述中就可以看到写的过程中保证写一个多数派的（W）节点就告知写入成功，读取的时候（同样包括Learner学习的过程在后面有介绍）读取多数派（R）个节点的数据就可以保证读取到更新的数据。W+R>N  满足Quorum机制。

Learner学习过程：
Learner：学习者。Learner 学习被批准的 value。所谓学习就是通过读取各个 Proposer 对 value
的选择结果，如果某个 value 被超过半数 Proposer 通过，则 Learner 学习到了这个 value。回忆（2.4 ）
不难理解，这里类似 Quorum 机制，某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准，从而学习者
需要至少读取 N/2+1 个 Accpetor，至多读取 N 个 Acceptor 的结果后，能学习到一个通过的 value。

4.ZooKeeper中关于paxos算法的实现


在 Zookeeper 中，始终分为两种场景：一、Leader activation，在这个场景里，系统中缺
乏 Leader（primary），通过一个类似 paxos 协议的过程完成 Leader 选举。二、Active messaging，在
这个场景里，Leader 接收客户端发送的更新操作，以一种类似两阶段提交的过程在各个 follower
（secondary）节点上进行更新操作。在 Leader activation 场景中完成 leader 选举及数据同步后，系统
转入 Active messaging 场景，在 active messaging 中 leader 异常后，系统转入 Leader activation 场景。
无论在那种场景，Zookeeper 依赖于一个全局版本号：zxid。zxid 由(epoch, count)两部分组成，
高位的 epoch 部分是选举编号，每次提议进行新的 leader 选举时 epoch 都会增加，低位的 count 部分
是 leader 为每个更新操作决定的序号。可以认为，一个 leader 对应一个唯一的 epoch，每个 leader
任期内产生的更新操作对应一个唯一的有序的 count，从而从全局的视野，一个 zxid 代表了一个更
新操作的全局序号（版本号）。
每个 zookeeper 节点都有各自最后 commit 的 zxid，表示这个 zookeeper 节点上最近成功执行的
更新操作，也代表了这个节点的数据版本。在 Leader activation 阶段，每个 zookeeper 节点都以自己
的 zxid 作为 Paxos 中的 b 参数发起 paxos 实例，设置自己作为 leader（此为 value）。每个 zookeeper
节点既是 proposer 又是 acceptor，所以，每个 zookeeper 节点只会 accpet 提案编号 b 大于自身 zxid
的提案。不难理解，通过 paxos 协议过程，某个超过 quorum 半数的节点中持有最大的 zxid 的节点
会成为新的 leader。值得注意的是，假如参与选举的每个 zookeeper 节点的 zxid 都一样，即所有的
节点都以相同的 b=zxid 发提案，那么就有可能发送类似 2.8.4 中无法选举出 leader 的情况。zookeeper
解决这个问题的办法很简单，zookeeper 要求为每个节点配置一个不同的的节点编号，记为 nodeid，
paxos 过程中以 b=(zxid, nodeid)发起提议，从而当 zxid 相同时会优先选择节点编号较大的节点成为
leader。成为新 leader 的节点首先与 follower 完成数据同步后，再次说明，数据同步过程可能会涉及
删除 follower 上的最后一条脏数据，详细分析见 2.4.6.3 。当与至少半数节点完成数据同步后，leader
更新 epoch，在各个 follower 上以(epoch + 1, 0) 为 zxid 写一条没有数据的更新操作。这个更新操作
称为 NEW_LEADER 消息，是为了在各个节点上更新 leader 信息，当收到超过半数的 follower 对
NEW_LEADER 的确认后，leader 发起对 NEW_LEADER 的 COMMIT 操作，并进入 active messaging
状态提供服务。
进入 active messaging 状态的 leader 会接收从客户端发来的更新操作，为每个更新操作生成递增
的 count，组成递增的 zxid。Leader 将更新操作以 zxid 的顺序发送给各个 follower （包括 leader 本身，
一个 leader 同时也是 follower），当收到超过半数的 follower 的确认后，Leader 发送针对该更新操作
的 COMMIT 消息给各个 follower。这个更新操作的过程很类似两阶段提交，只是 leader 永远不会对
更新操作做 abort 操作。
如果leader不能更新超过半数的follower，也说明leader失去了quorum，此时可以发起新的leader
选举，最后一条更新操作处于“中间状态”，其是否生效取决于选举出的新 leader 是否有该条更新操
作。从另一个角度，当 leader 失去 quorum 的 follower，也说明可能有一个超过半数的节点集合正在
选举新的 leader。
Zookeeper 通过 zxid 将两个场景阶段较好的结合起来，且能保证全局的强一致性。由于同一时
刻只有一个 zookeeper 节点能获得超过半数的 follower，所以同一时刻最多只存在唯一的 leader；每
个 leader 利用 FIFO 以 zxid 顺序更新各个 follower，只有成功完成前一个更新操作的才会进行下一个
更新操作，在同一个 leader 任期内，数据在全局满足 quorum 约束的强一致，即读超过半数的节点
一定可以读到最新已提交的数据；每个成功的更新操作都至少被超过半数的节点确认，使得新选举
的 leader 一定可以包括最新的已成功提交的数据。

关于ZooKeeper中的Leader Evaluator的实现可以参考如下：

ZooKeeper实现Leader Election，也就是选出一个Master Server。每台Server创建一个EPHEMERAL_SEQUENTIAL目录节点。类似于前面的集群节点。但是使用了带有顺序的临时节点。

代码如下：

void findLeader() throws Exception{
    byte[] leader=null;
    try{
        //得到leader节点数据
        leader=zk.getData(root+"/leader",true,null);
    }catch(Exception e){
        logger.error(e);
    }
    //存在leader节点，也就是leader存在
    if(leader!=null){
        following();
    }else{
        String newLeader=null;
        try{
            //leader不存在，创建leader节点，自己成为leader
            byte[] localhost=InetAddress.getLocalHost().getAddress();
            newLeader=zk.create(root+"/leader",localhost,ZooDefs.Ids.OPEN_ACL_UNSAFE,CreateMode.EPHEMERAL);
        }catch(Exception e){
            logger.error(e);
        }
        //自己成为leader
        if(newLeader!=null){
            leading();
        }else{
            mutex.wait();
        }
    }
}

5.关于paxos算法的推导以及案例，书籍中做了精彩的介绍，我就不赘述了。

6.关于我们上面提到的三种机制（lease Quorum paxos）与CAP理论的关系

上面几种分布式协议是都是在CAP 三大属性中做折中与取舍的

lease机制：
Lease 机制牺牲了部分异常情况下的 A，从而获得了完全的 C 与很好的 P。
上面这句话有点抽象，下面一一解释。首先，Lease 机制不是在任何情况下都具有可用性的，
使用 Lease 机制的协议，在发生异常时，需要等待 Lease 超时才能收回 Lease 权限。然而，Lease 的
持有者可能在 Lease 超时前就已经出现异常而不能提供服务了，直到 Lease 超时这段时间内，系统
服务的可用性都有问题。例如，如果用 lease 决定 Primary 副本的，Primary 副本节点宕机后，只有
待 Lease 超时才能选出新的 primary 副本，这段时间由于缺乏 primary 副本是没有更新服务的。再者，
Lease协议本身保证了对于Lease约定的承诺在Lease颁发者和持有者之间是始终一致的。即使Lease
持有者由于网络分化没有真正收到 Lease，Lease 颁发者也会在 Lease 时间内执行自己的承诺；而一
旦 Lease 持有者收到 Lease，则即使再出现网络分化，也无法影响双方对 Lease 承诺理解的一致性。
最后，Lease 协议引入了“时间”这一概念，使得在对抗网络分化上有其特别的优势，另外，Lease
只需由颁发者向持有者通信，即使网络是单向的也不影响 Lease 协议的正常工作。

Quorum机制：

这里仅讨论一般的 Quorum 机制，即总共有 N 个副本，成功更新 W 个副本则算成功提交，读取
时读 R 个副本。这种一般的 Quorum 机制，在 CAP 三大因素中都各做了折中，有一定的 C，有较好
的 A，也有较好的 P，是一种较为平衡的分布式协议。
首先，读取 R 个副本时，可以保证读取到成功提交的版本，但无法保证读取到最新的成功提交
的版本（2.4.4 ）。也就是说，系统具有一定的一致性，却无法真正做到强一致性。（在单纯使用 Quorum 机制时，若要确定最新的成功提交的版本，最多需要读取 R+（W-R-1）=N 个副本，当出现任一副本异常时，读最新的成功提交的版本这一功能都有可能不可用。实际工程中，应该尽量通过其他技术手段，回避通过 Quorum 机制读取最新的成功提交的版本。例如，当 quorum 机制与 primary-secondary 控制协议结合使用时，可以通过读取 primary 的方式读取到最新的已提交的数据。）再者，无论是更新 W 个副本，还是读取 R 个副本，协议可以允许部分副本异常而不影响更新或者读取服务。最后，只要能与 W 个副本通信就可以提供更新服务，能与 R 个副本通信就可以提供读服务，协议具有一定的容忍网络分化的能力。工程中，当使用 3 个副本时，可以讲三个副本部署在三个不同的机房，只有同时出现两个机房的网络都异常时才会影响服务，这种情况的概率本身已经非常低了。

 两阶段提交协议
两阶段提交系统具有完全的 C，很糟糕的 A，很糟糕的 P。
首先，两阶段提交协议保证了副本间是完全一致的，这也是协议的设计目的。再者，协议在一
个节点出现异常时，就无法更新数据，其服务可用性较低。最后，一旦协调者与参与者之间网络分
化，无法提供服务。
 Paxos 协议
同样是强一致性协议，Paxos 在 CAP 三方面较之两阶段提交协议要优秀得多。Paxos 协议具有
完全的 C，较好的 A，较好的 P。Paxos 的 A 与 P 的属性与 Quorum 机制类似，因为 Paxos 的协议本
身就具有 Quorum 机制的因素。
首先，无需赘述，Paxos 协议是一种强一致性协议。再者，Paxos 协议只有两种情况下服务不可
用：一是超过半数的 Proposer 异常，二是出现活锁  前者可以通过增加 Proposer 的个数来
降低由于 Proposer 异常影响服务的概率，后者本身发生的概率就极低。最后，只要能与超过半数的
Proposer 通信就可以完成协议流程，协议本身具有较好的容忍网络分区的能力。
7.关于日志的使用
日志的使用在数据库系统中有大量的应用。传统的数据库是遵循acid，基于事务处理，这种事务的实现很多都是基于日志实现的，比如我们使用的建立savepoint，然后出错进行回滚rollback（oracle数据库中就有相应的API实现事务处理，内部机制就是使用类似这种日志实现）。在就是最近学习的hadoop中，在hadoop1.x中关于日志的使用保证NameNode节点在崩溃后重新使用。（hadoop2.x中基于ZooKeeper建立了HA高性能模块就没有这种设置了）。在Namenode中有edits日志用于保存操作日志，fsimage文件保存已经处理好的元数据。

关于Hadoop1.x中HDFS元数据使用操作日志的过程详述：

下面我们讲解第二种节点(SecondaryNameNode SNN)  SNN不能理解为NameNode 的备份。但是可以作为NameNode一部分数据的备份。但不是实时备份。所以我们可以知道SecondaryNameNode存储的也是元数据。

 

SNN的主要功能是帮助NameNode合并edits文件。

 

因为进行文件的操作都是存储在edits中，但是HDFS不是立马进行对文件的操作，而是等一段时间之后，合并edits文件然后与fsimage进行合并的时候才进行对文件的操作。这个过程涉及到大量的I/O操作，对NameNode资源占用很大，但是NameNode的主要功能是接收客户端的读写操作，所以不能浪费大量的资源在这上面，所以我们需要单独拿出一种节点SNN帮助NameNode进行这方面的处理。

 

SNN合并结束之后会得到一个新的fsimage文件，这个文件就是完成了edits文件中记录操作的fsimage文件。这个新的fsimage会推送给NameNode然后替换掉原来的fsimage。

 

我们可以设置SNN进行合并的时机：

上面PPT中提到的

 

首先没有特殊情况下是3600s合并一次，但是如果edits文件的大小超过了64MB即使没有到达3600s也会立马进行合并。上面的都是默认设置我们可以自己通过修改PPT上面提到的两个参数进行设置。

下面就是SNN进行合并的过程。

首先进行合并的过程中，需要网络拷贝，因为可能NameNode和SNN可能不在一台机器上，甚至不在一个网段里面，所以可能会需要跨网络传输，所以采用网络拷贝将edits文件与fsimage文件拷贝到SNN上面，但是由于NameNode一直在接收客户端的读写请求，所以就可能会产生新的操作日志，这些日志不能存储在老的edits文件中，我们需要创建新的edits文件存储NameNode中的操作日志，而老的edits文件与fsimage在SNN中完成合并产生新的fsimage文件，然后新的edits文件存储在NameNode中为下一次合并做准备，产生的新的fsimage推送给NameNode，替换掉老的fsimage。

 

上面可以体现出NameNode中磁盘的数据不是实时的，但是NameNode工作的数据是使用的内存中的数据，所以是不影响工作的。

 

所以通过上面的过程中我们就可以看到，SNN只能为NameNode恢复一部分数据，但不是热备份。就是因为SNN中存储了上一次进行合并得到的fsimage，可以拷贝给NameNode进行恢复，但是后来新增加的操作，也就是edits.new 文件是永久丢失的是找不回来的。

 

 

所以我们应该将SecondaryNameNode放在与NameNode不同的机器上面，这样才不会使得这台机器down掉之后，所有数据丢失，因为在不同机器上，NameNode down掉之后，可以通过SNN恢复大部分数据。

8.了解到分布式系统中很重要的  数据分布

主要由四种方式：哈希、按数据范围分布、按数据量分布、一致性哈希
这几种方式在现在的分布式系统中都有使用，我熟知的有这几种

哈希：在MapReduce中选取Reduce使用的是哈希模的方式。
数据范围：HBase的Region就是根据Rowkey的的数据范围分成多个Region 
数据量分布：最典型的就是HDFS的分块（block）进行存储
一致性哈希暂时没有遇到。

9.其他一些杂七杂八的问题。
有时间在整理