1 volatile 的应用

1.1 volatile 的定义与实现原理

volatile 变量修饰的共享变量进行写操作的时候，会引发两件事情：

将当前处理器缓存行（ cache line ）的数据写回到系统内存。
这个写回内存的操作会使其它 CPU 里缓存了该内存地址的数据无效。
为了提高处理速度，处理器不直接和内存进行通信，而是先将系统内存的数据读到内部缓存（L1，L2或其它，即一级缓存、二级缓存等）后再进行操作， 但操作完全不知道何时会真正写到内存。而声明了 volatile 的变量进行写操作， JVM 就会向处理器发送一条 Lock 前缀的指令， 将这个变量所在缓存行的数据写回到系统内存。但是，就算写回到内存，如果其它处理器缓存的值还是旧的，再执行计算操作就会有问题。所以， 在多处理器下，为了保证各个处理器的缓存是一致的，就会实现缓存一致性协议，每个处理器通过嗅探在总线上传播的数据来检查自己缓存的值是不是过期了， 当处理器发现自己缓存行对应的内存地址被修改，就会将当前处理器的缓存行设置成无效状态，当处理器对这个数据进行修改操作的时候， 会重新从系统内存中把数据读到处理器缓存里。

1.2 volatile 的使用优化

在 JDK 1.7 中的 LinkedTransferQueue 使用 volatile 变量时，用一种追加字节的方式来优化队列出队和入队的性能，即将共享变量追加到 64 字节。 一个对象的引用占用 4 个字节，追加 15 个变量（共占 60 个字节），一共 64 个字节。这样 CPU 中缓存行中，最多只有一个队列， 而不会导致有两个队列，操作其中一个队列的时候由于和另一个队列在同一个缓存行中锁住了另一个队列。但是有两种场景下不应该使用这种方式：

缓存行非 64 字节宽的处理。
共享变量不会被频繁的写。
但是在 java7 中，它会淘汰或重新排列无用字段，因此需要使用其它追加字节的方式。

2 synchronized 的实现原理与应用

作为一个重量级锁，它是存在 Java 对象头里的。并在 Java SE 1.6 对 synchronized 进行了各种优化。
Java 中的每一个对象都可以作为锁：

对于普通同步方法，锁是当前实例对象。
对于静态同步方法，锁是当前类的 Class 对象。
对于同步方法块，锁是 Synchronized 括号里配置的对象。
JVM 基于进入和退出 Monitor 对象来实现方法同步和代码块同步，但两者的实现细节不同。
代码块同步是使用 monitorenter 和 monitorexit 指令实现的，而方法同步使用另外一种方法实现，细节在 JVM 规范里并没有详细说明。但是， 方法的同步同样可以使用这两个指令来实现。

2.1 锁的升级与对比

Java SE 1.6 为了减少获得锁和释放锁带来的性能消耗，引入了“偏向锁”和“轻量级锁”，在 Java SE 1.6 中，锁一共有 4 种状态，级别从低到高依次是：

无锁状态
偏向锁状态
轻量级锁状态
重量级锁状态
这几种状态随着竞争情况逐渐升级。锁可以升级但不能降级，这是为了提高获得锁和释放锁的效率，下文会详细分析。

2.1.1 偏向锁

HotSpot 的作者经过研究发现，大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。
当一个线程访问同步块并获取锁时，会在当前同步块的对象头和栈帧中的锁记录里存储锁偏向的线程 ID ，以后该线程再进入和退出同步块时不需要进行 CAS 操作来加锁和解锁， 只需要简单地测试一下对象头里的 Mark Word 里是否存储着指向当前线程的偏向锁。如果测试成功，表示当前线程已经获得了锁。如果测试失败，则需要再测试一下对象头中偏向锁的标识是否设置成1 （标识当前是偏向锁）：如果没有设置，则使用 CAS 竞争锁；如果设置了，则尝试使用 CAS 将对象头的偏向锁指向当前线程。

1) 偏向锁的撤销
偏向锁使用了一种等到竞争出现才释放锁的机制，所以当其它线程尝试竞争偏向锁时，持有偏向锁的线程才会释放锁。偏向锁的撤销，需要等待全局安全点 （在这个时间点上没有正在执行的字节码，GC 可以在这个点进行暂停所有线程进行暂停回收操作）。它会首先暂停拥有偏向锁的线程， 然后检查持有偏向锁的线程是否活着，如果线程不处于活动状态，则将对象头设置成无锁状态；如果线程仍然活着，拥有偏向锁的栈会被执行，遍历偏向对象的锁记录， 栈中的锁记录和对象头，要么重新偏向于其它线程，要么恢复到无锁或者标记对象不适合作为偏向锁，最后唤醒暂停的线程。

2) 关闭偏向锁
偏向锁在 Java 6 和 Java 7 里是默认启用的，但是它在应用程序启动几秒钟之后才激活，可以使用 -XX:BiasedLockingStartupDelay=0 。 如果你确定应用程序里所有的锁通常情况下处理竞争状态，可以通过 -XX:UseBiasedLocking=false 关闭偏向锁，那么程序默认会进入轻量级锁状态。

2.1.2 轻量级锁

1) 轻量级锁加锁
线程在执行同步块之前， JVM 会先在当前线程的栈帧中创建用于存储锁记录的空间，并将对象头中的Mark Word 复制到锁记录中，官方称为 Displaced Mark Word 。 然后线程尝试使用 CAS 将对象头中的 Mark Word 替换为指向锁记录的指针。如果成功，当前线程获得锁，如果失败，表示其它线程竞争锁，当前线程便尝试使用自旋来获取锁。

2) 轻量级锁解锁
使用 CAS 操作将 Displaced Mark Word 替换回到对象头，如果成功，则表示没有竞争发生。如果失败，表示当前锁存在竞争，锁就会膨胀成重量级锁。
当锁处于这个状态下，其它线程试图获取锁时，都会被阻塞住，当持有锁的线程释放锁之后会唤醒这些线程，被唤醒的线程就会进行新一轮的夺锁之争。

3) 锁的优缺点对比

3 原子操作的实现原理

3.1 处理器使用总线锁保证原子性

如果多个处理器同时对共享变量进行读改写操作（i++ 就是经典的读改写操作），那么共享变量就会被多个处理器同时进行操作，这样读改写操作就不是原子的， 操作完之后共享变量的值会和期望的不一致。例如：如果 i=1 ,我们进行两次 i++ 操作，期望结果是 3 ，但是有可能结果是 2 。如下图：

可能是多个处理器同时从各自的缓存中读取变量 i ，分别进行加 1 操作，然后分别写入系统内存中。那么，想要保证读改写共享变量的操作是原子的， 就必须保证 CPU1 读改写共享变量的时候， CPU2 不能操作缓存了该共享变量内存地址的缓存。

处理器使用总线锁来解决这个问题，即使用处理器提供的一个 LOCK# 信号，当一个处理器在总线上输出此信号时，其它处理器的请求将被阻塞住， 那么该处理器就可以独占共享内存，而其它处理器会直接废弃掉该信号的值，从内存中取，再缓存。

3.2 处理器使用缓存锁保证原子性

在同一时刻，我们只需要保证对某个内存地址的操作是原子性即可，但总线锁定把 CPU 和内存之间的通信锁住了，这使得锁定期间，其它处理器不能操作其它内存地址的户数， 所以总线锁定的开销比较大，在某些场合下可以使用缓存锁定代替总线锁定进行优化。

频繁使用的内存会缓存在处理器的 L1、L2 和 L3 高级缓存里，那么原子操作就可以直接在处理器内部缓存中进行，并不需要声明总线锁。所谓“缓存锁定” 是指内存区域如果被缓存在处理器的缓存行中，并且在 Lock 操作期间被锁定，那么当它执行锁操作回写到内存时，处理器不在总线上声明 LOCK# 信号， 而是膝盖内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改两个以上处理器缓存的内存区域数据， 当其它处理器回写已被锁定的缓存行的数据时，会使缓存行无效。如上图的例子，当 CPU1 修改缓存行中的 i 时使用了缓存锁定，那么 CPU2 就不能同时缓存 i 和缓存行。

但是有两种情况下处理器不会使用缓存锁定：
1：当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行，则处理器会调用总线锁定。
2：处理器本身不支持缓存锁定。

4 Java 如何实现原子操作

4.1 使用循环 CAS 实现原子操作

使用 JDK 1.5 之后的并发包，里面有一些类来支持原子操作，如 AtomicBoolean 、 AtomicInteger 、 AtomicLong ，还有一些工具了， 如以原子额方式将当前值自增 1 和自减 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

public class Counter {
    private AtomicInteger atomicI = new AtomicInteger(0);
    private int i = 0;
    public static void main(String[] args) {
        final Counter cas = new Counter();
        List<Thread> ts = new ArrayList<>(600);
        long start = System.currentTimeMillis();
        for (int j = 0; j < 100; j++) {
            Thread t = new Thread(new Runnable() {
                @Override public void run() {
                    for (int i = 0; i < 10000; i++) {
                        cas.count();
                        cas.safeCount();
                    }
                }
            });
            ts.add(t);
        }
        for (Thread t : ts) {
            t.start();
        }
        // 等待所有线程执行完成
        for (Thread t : ts) {
            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println(cas.i);
        System.out.println(cas.atomicI.get());
        System.out.println(System.currentTimeMillis() - start);
    }
    /**
     * 使用 CAS 实现线程安全计数器
     */
    private void safeCount() {
        for (;;) {
            int i = atomicI.get();
            boolean suc = atomicI.compareAndSet(i, ++i);
            if (suc) {
                break;
            }
        }
    }
    /**
     * 非线程安全计数器
     */
    private void count() {
        i++;
    }
}

4.2 CAS 实现原子操作的三大问题

4.2.1 ABA 问题

如果一个值原来是 A ，变成了 B ，又变成了 A ，那么使用 CAS 进行检查时会发现它的值没有变化，但是实际却变化了。
解决思路就是使用版本号，即 A->B->A 变成 1A->2B->3A 。 Atomic 包提供了类 AtomicStampedReference 来解决 ABA 问题。

4.2.2 循环时间开销大

自旋 CAS 如果长时间不成功，会给 CPU 带来非常大的执行开销。

4.2.3 只能保证一个共享变量的原子操作

对多个共享变量操作时，循环 CAS 就无法保证操作的原子性，这个时候就可以用锁。还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作， 例如，有两个共享变量 i=2 ，j=a ，合并以下 ij=2a ，然后用 CAS 来操作 ij 。 JDK 1.5 之后提供了 AtomicReference 类来保证引用对象之间的原子性， 就可以把多个变量放在一个对象里来进行 CAS 操作。

4.3 使用锁机制实现原子操作

JVM 内部实现了很多种锁机制，有偏向锁、轻量级锁和互斥锁。有意思的是除了偏向锁， JVM 实现锁的方式都用了循环 CAS ，即当一个线程想进入同步块的时候使用循环 CAS 的方式来获取锁， 当它退出同步块的时候使用循环 CAS 释放锁。

5 本章小结

volatile 的实现原理，从处理器到 JVM 讲解。
synchronized 的实现原理以及三种锁对象以及 JDK 1.6 之后的四种状态锁。
原子操作的实现原理，即 CAS 。
Java 中的大部分容器和框架都依赖于本章介绍的 volatile 和原子操作的实现原理，了解这些原理对我们进行并发编程会更有帮助。

1 上下文切换

并发是单核处理器支持多线程执行代码。则 CPU 通过给每个线程分配时间片来实现，线程任务执行的切换，由于在切换 前要保存当前任务的状态，因此从保存再到加载的过程就是一次上下文切换。

1.1 多线程一定快吗？

以下为对比：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class ConcurrencyTest {
    private static final long count = 100000001;
    public static void main(String[] args) throws InterruptedException {
        concurrenct();
        serial();
    }
    private static void concurrenct() throws InterruptedException {
        long start = System.currentTimeMillis();
        Thread thread = new Thread(new Runnable() {
            @Override public void run() {
                int a = 0;
                for (long i = 0; i < count; i++) {
                    a += 5;
                }
            }
        });
        thread.start();
        int b = 0;
        for (long i = 0; i < count; i++) {
            b--;
        }
        long time = System.currentTimeMillis() - start;
        thread.join();
        System.out.println("concurrency: " + time + "ms, b = " + b);
    }
    private static void serial() {
        long start = System.currentTimeMillis();
        int a = 0;
        for (long i = 0; i < count; i++) {
            a += 5;
        }
        int b = 0;
        for (long i = 0; i < count; i++) {
            b--;
        }
        long time = System.currentTimeMillis() - start;
        System.out.println("serial: " + time + "ms, b = " + b);
    }
}

1.2 如何减少上下文切换

无锁并发编程：多线程竞争锁时，会引起上下文切换。因此 Hash 算法通过取模分段，不同的线程处理不同段的数据。
CAS 算法： Atomic 包使用 CAS 算法来更新数据，而不需要加锁。
协程：在单线程里实现多任务的调度，并在单线程里维持多个任务间的切换。

2. 死锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class DeadLockDemo {
    private static String A = "A";
    private static String B = "B";
    public static void main(String[] args) {
        new DeadLockDemo().deadLock();
    }
    private void deadLock() {
        Thread t1 = new Thread(new Runnable() {
            @Override public void run() {
                synchronized (A) {
                    try {
                        Thread.currentThread().sleep(2000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    synchronized (B) {
                        System.out.println("1");
                    }
                }
            }
        });
        Thread t2 = new Thread(new Runnable() {
            @Override public void run() {
                synchronized (B) {
                    synchronized (A) {
                        System.out.println("2");
                    }
                }
            }
        });
        t1.start();
        t2.start();
    }
}

这段代码的死锁在于，t1拿到锁之后，因为一些异常没有释放锁（或者死循环）。又或者是t1拿到一个数据库锁，释放锁的时候抛出了异常，没有释放掉。 导致t2一直等待t1释放锁。
而避免死锁常见方法有：

避免一个线程同时获取多个锁。
避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源。
尝试使用定时锁，使用 lock.tryLock(timeout) 来替代使用内部锁机制。
对于数据库锁，加锁和解锁必须在一个数据库连接里，否则会出现解锁失败的情况。

3 资源限制的挑战

3.1 什么是资源限制

资源限制是指，程序的执行速度受限于计算机硬件资源或软件资源。例如，服务器的宽带只有 2MB/s ，某个资源的下载速度是 1MB/s ， 系统启动 10 个线程下载资源，下载速度会不会变成 10MB/s ，所以在进行并发编程时，要考虑资源的限制。而硬件资源限制有带宽的上传/下载速度、 硬盘读写速度和 CPU 的处理速度，软件资源限制有数据库的连接数和 socket 连接数等。

3.2 资源限制引发的问题

在并发编程中，将代码执行速度加快的原则是将代码中串行执行的部分编程并发执行，但是受限于资源，仍然在串行执行，这时候执行的会更慢， 因为增加了上下文切换和资源调度的时间。例如，之前看到一段程序使用多线程在办公网并发的下载和处理数据，导致 CPU 使用率达到 100% ， 几个小时都不能运行完成任务，后来修改成单线程，一个小时就执行完成了。

3.3 如何解决资源限制的问题

对于硬件资源限制，可以考虑使用集群并行执行程序。既然单机的资源有限制，那么就让程序在多机运行。不同的机器处理不同的数据。

对于软件资源限制，可以考虑使用资源池将资源复用。例如使用连接池数据库和 Socket 连接复用，或者在调用对方 webservice 接口获取数据时， 只建立一个连接。

4 本章小结

本章的并发程序不够严谨，但是够入门，笔者建议多实用 JDK 并发包提供的并发容器和工具类来解决并发问题，因为这些类都已经通过了充分的测试和优化。

1 数据发布/订阅

数据发布/订阅（Pulish/Subscribe）系统，即所谓的配置中心，顾名思义就是发布者将数据发布到ZooKeeper的一个或一系列节点上，供订阅者进行数据订阅， 进而达到动态获取数据的目的，实现配置信息的集中式管理和数据的动态更新。

发布/订阅系统一般有两种设计模式，分别是推（Push）模式和拉（Pull）模式。在推模式中，服务端主动将数据更新发送给所有订阅的客户端；而拉模式则是由 客户端主动发起请求获取最新数据，通常客户端都采用定时进行轮询拉取的方式。ZooKeeper采用的是推拉结合的方式：客户端向服务端注册自己需要关注的 节点，一旦该节点的数据发生变更，那么服务端就会向相应的客户端发送Watcher事件通知，客户端接收到这个消息通知之后，需要主动到服务端获取最新的数据。

如果将配置信息存放到ZooKeeper上进行集中管理，那么通常情况下，应用在启动的时候都会主动到ZooKeeper服务端上进行一次配置信息的获取，同时， 在指定节点上注册一个Watcher监听，这样一来，但凡配置信息发生变更，服务端都会实时通知到所有订阅的客户端，从而达到实时获取最新配置信息的目的。

实例：在我们平常的应用系统开发中，经常会碰到这样的需求：系统中需要使用一些通用的配置信息，例如机器列表信息、运行时的开关配置、数据库配置信息等。 这些全局配置信息通畅具备以下3个特性：

数据量通常比较小。
数据内容在运行时会发生动态变化。
集群中各机器共享，配置一致。
对于这类配置信息，一般的做法通常可以选择将其存储在本地配置文件或是内存变量中。本地配置可以采用JMX方式来实时对系统运行时内存变量的更新。

但是一旦机器规模变大，且配置信息变更频繁后，就需要寻找一种更为分布式化的解决方案。

下面以“数据库切换”的应用场景展开，看看如何使用ZooKeeper实现配置管理。

1.1 配置存储

进行配置之前，首先初始化配置存储到ZooKeeper上去，例如/app1/databse_config/（以下简称“配置节点”），写入数据节点中：

1
2
3
4
5
6
7
8

dbcp.driverClassName=com.mysql.jdbc.Driver
dbcp.dbJDBCUrl=jdbc:mysql://localhost:3306/taokeeper
dbcp.characterEncoding=GBK
dbcp.username=admin
dbcp.password=root
dbcp.maxActive=30
dbcp.maxIdle=10
dbcp.maxWait=10000

1.2 配置获取

集群中每台机器在启动初始化阶段，首先会从上面提到的ZooKeeper配置节点上读取数据库信息，同时，客户端还需要在该配置节点上注册一个数据变更的 Water监听，一旦发生节点数据变更，所有订阅的客户端都能够获取到数据变更通知。

1.3 配置变更

在系统运行过程中，可能会出现需要机型数据库切换的情况，借助ZooKeeper的Watcher机制，帮我们将数据变更的通知发送到各个客户端，每个客户端在 接收到这个变更通知后，就可以重新进行最新数据的获取。

2 负载均衡

根据维基百科上的定义，负载均衡（Load Balance）是一种相当常见的计算机网络技术，用来对多个计算机（计算机集群）、网络连接、CPU、磁盘驱动器或是 其它资源进行分配负载，以达到优化资源使用、最大化吞吐率、最小化响应时间和避免过载的目的。通常负载均衡可以分为硬件和软件负载均衡两种，本节 主要探讨的是ZooKeeper在“软”负载均衡中的应用场景。

在分布式系统中，负载均衡更是一种普遍的技术，基本上每一个分布式系统都需要使用负载均衡。在本书第一章讲解分布式系统特征的时候，我们提到，分布式系统具有 对等性，为了保证系统的高可用性，通常采用副本的方式来对数据和服务进行部署。而对于消费者而言，则需要在这些对等的服务提供方中选择一个来执行相关的业务 逻辑，其中比较典型的就是DNS服务。在本节中，我们将详细介绍如何使用ZooKeeper来解决负载均衡问题（请看深入分析Java_Web技术的第一章）。

2.1 一种动态的DNS服务

DNS是域名系统（Domain Name System）的缩写。DNS系统可以看作是一个超大规模的分布式映射表，用于将域名和IP地址进行一一映射，进而方便人们 通过域名来访问互联网站点。

通常情况下，我们可以向域名注册服务商申请域名注册，但是这种方式最大的缺陷在于只能注册有限的域名：

日常开发过程中，经常会碰到这样的情况，在一个Company1公司内部，需要给一个App1应用的服务器集群机器配置一个域名解析。相信有过一线开发 经验的读者一定知道，这个时候通常需要由类似于app1.company1.com的一个域名，其对应的就是一个服务器地址。如果系统数量不多，那么通过 这种传统的DNS配置方式还可以应付，但是，一旦公司规模变大，各类应用层出不穷，那么就很难再通过这种方式来进行统一的管理了。

因此，在实际开发中，往往使用本地HOST绑定来实现域名解析的工作。具体如何进行本地HOST绑定，因为不是本书的重点，并且互联网上有大量额资料， 因此这里不再多说明。使用本地HOST绑定的方法，可以很容易解决域名紧张的问题，基本上每一个系统都可以自行确定系统的域名与目标IO地址。大大提高了 开发调试效率。（就是修改HOST文件，让域名与IP直接映射，减去解析时间）然而，这种看上去完美的方案，也有其致命的缺陷：

当应用的机器规模在一定范围内，并且域名的变更不是特别频繁时，本地HOST绑定是非常高效且简单的方式。然而一旦机器规模变大后，就常常 会碰到这样的情况：我们在应用上线的时候，需要在应用的每台机器上去绑定域名，但是在机器规模相当庞大的情况下，这种做法就相当不方便。 另外，如果想要临时更新域名，还需要到每个机器上去逐个进行变更，更消耗大量时间，因此完全无法保证实时性。

现在，我们来介绍一种基于ZoKeeper实现的动态DNS方案（简称“DDNS”，Dynamic DNS）。

2.2 域名配置

首先需要在ZooKeeper上创建一个节点来进行域名配置。

这样，在/DDNS/app1的节点上，将自己的域名配置上去，并支持多个IP

2.3 域名解析

在传统的DNS解析中，我们都不需要关系域名的解析过程，所有这些工作都交给了操作系统的域名和IP地址映射机制（本地HOST绑定）或是专门的域名解析 服务器（由域名注册服务商提供）。因此，在这点上，DDNS方案和传统的域名解析有很大的区别————在DDNS中，域名的解析过程都是由每一个应用自己负责的。 通常应用都会首先从域名节点中获取一份IP地址和端口的配置，进行自行解析。同时，每个应用还会在域名节点上注册一个数据变更Watcher监听，以便及时 收到域名变更的通知。

2.4 域名变更

在运行过程中，难免会碰上域名对应的IP地址或是端口变更，这个时候就需要进行域名变更操作。在DDNS中，我们只需要对指定的域名节点进行更新操作， ZooKeeper就会向订阅的客户端发送这个事件通知，应用在接收到这个事件通知后，就会再次进行域名配置的获取。

上面我们介绍了如何使用ZooKeeper来实现一种动态的DNS系统。通过ZooKeeper来实现动态DNS服务，一方面，可以避免域名数量无限增长带来的集中式维护 的成本；另一方面，在域名变更的情况下，也能够避免因逐台机器更新本地HOST而带来的繁琐工作。

2.5 自动化的DNS服务

根据上面的讲解，相信读者基本上已经能够使用ZooKeeper来实现一个动态的DNS服务了。但是我们仔细看一下上面的实现就会发现，在域名变更环节中，当 域名对应的I地址发生变更的时候，我们还是需要人为地介入去修改域名节点上的IP地址和端口。接下来我们看看下面这种使用ZooKeeper实现的更为自动化 的DNS服务。自动化的DNS服务系统主要是为了实现服务的自动化定位。

首先来介绍整个动态DNS系统的架构体系中比较重要的组件及其职责。

• Register Cluster：负责域名的动态注册。
• Dispatcher Cluster：负责域名解析。
• Scanner Cluster：负责检测以及维护服务状态（探测服务的可用性、屏蔽异常服务节点等）。
• SDK：提供各种语言的系统接入协议，提供服务注册以及查询接口。
• Monitor：负责收集服务信息以及对DDNS自身状态的监控。
• Controller：后台管理的Console，负责授权管理、流量控制、静态配置服务和手动屏蔽服务等功能，运维人员在上面管理Register、Dispatcher和Scanner等Cluster。

整个系统的核心当然是ZooKeeper集群，负责数据的存储以及一系列分布式协调。下面我们再来详细地看下整个系统是如何运行的。在这个架构模型中，我们 将那些目标IP地址和端口抽象为服务的提供者，而那些需要使用域名解析的客户端则被抽象成服务的消费者。

2.5.1 域名注册

域名注册主要是针对服务提供者来说的。域名注册过程可以简单地概括为：每个服务提供者在启动的过程中，都会把自己的域名信息注册到Register Cluster中去。

服务提供者通过SDK提供的API接口，将域名、IP地址和端口发送给Register Cluster。例如，A机器用于提供serverA.xxx.com，于是它就向Register 发送一个“域名->IP:PORT”的映射：“serverA.xxx.com->192.168.0.1:8080”。
Register获取到域名、IP地址和端口配置后，根据域名将信息写入相对应的ZooKeeper域名节点中。

2.5.2 域名解析

域名解析是针对服务消费者来说的，正好和域名注册过程相反：服务消费者在使用域名的时候，会向Dispatcher发出域名解析请求。Dispatcher收到请求后， 会从ZooKeeper上的指定域名节点读取相应的IP:PORT列表，通过一定的策略选取其中一个返回给前端应用。

2.5.3 域名探测

域名探测是指DDNS系统需要对域名下所有注册的IP地址和端口的可用性进行检测，俗称“健康度检测”。健康度检测一般有两种方式，第一种是服务端主动发起健康度心跳 检测，这种方式一般需要在服务端和客户端之间建立起一个TCP长链接；第二种则是客户端主动向服务端发起健康度心跳检测。在DDNS架构中的域名探测，使用 的是服务提供者都会定时向Scanner进行状态汇报（即第二种健康度检测方式）的模式，即每个服务提供者后都会定时向Scanner汇报自己的状态。

Scanner会负责记录每个服务提供者最近一次的状态汇报时间，一旦超过5秒没有收到状态汇报，那么就认为该IP地址和端口已经不可用，于是开始进行域名 清理过程。在域名清理过程中，Scanner会在ZooKeeper中找到该域名对应的域名节点，然后将该IP地址和端口配置从节点内容中移除。

3 命名服务

命名服务（Name Service）也是分布式系统中比较常见的一类场景。在分布式系统中，被命名的实体通常可以是集群中的机器、提供的服务地址或远程对象等———— 这些我们都可以统称它们为名字（Name），其中较为常见的就是一些分布式服务框架（如RPC、RMI）中的服务地址列表，通过使用命名服务， 客户端应用能够根据指定名字来获取资源的实体、服务地址和提供者的信息等。

Java语言中的JNDI便是一种典型的命名服务。JNDI是Java命名与目录接口（Java Naming and Directory Interface）的缩写，是J2EE体系中重要的规范之一， 标准的J2EE容器都提供了对JNDI规范的实现。因此，在实际开发中，开发人员常常使用应用服务器自带的JNDI实现来数据源的配置与管理————使用JNDI方式后， 开发人员可以完成不需要关心与数据库相关的任何信息，包括数据库类型、JDBC驱动类型以及数据库账号等。

ZooKeeper提供的命名服务功能与JNDI技术有相似的地方，都能够帮助应用系统通过一个资源引用的方式来实现对资源的定位与使用。另外，广义上命名服务 的资源定位都不是真正意义的实体资源————在分布式环境中，上层应用仅仅需要一个全局唯一的名字，类似于数据库中的唯一主键。下面我们来看看如何使用 ZooKeeper来实现一套分布式全局唯一ID的分配机制。

所谓ID，就是一个能够唯一标识某个对象的标识符。在我们熟悉的关系型数据库中，各个表都需要一个主键来唯一标识每条数据库记录，这个主键就是这样的唯一ID。 在过去的单库单表型系统中，通常可以使用数据库字段自带的auto_increment属性来自动为每条数据库记录生成一个唯一的ID，数据库会保证生成的这个ID 在全局唯一。但是随着数据库数据规模的不断增大，分库分表随之出现，而auto_increment属性仅能针对单一表中的记录自动生成ID，因此在这种情况下， 就无法再依靠数据库的auto_increment属性来唯一标识一条记录了。于是，我们必须寻求一种能够在分布式环境下生成全局唯一ID的方法。

一说起全局唯一ID，相信读者都会联想到UUID。没错，UUID是通用唯一识别码（Universally Unique Identifier）的简称，是一种在分布式系统中广泛 使用的用于唯一标识元素的标准，最典型的实现是GUID（Globally Unique Identifier，全局唯一标识符），主流ORM框架Hibernate有对UUID的直接支持。

确实，UUID是一个非常不错的全局唯一ID生成方式，能够非常简便地保证分布式环境中的唯一性。一个标准的UUID是一个包含32位字符和4个短线的字符串， 例如“asd321a-sd-sdwds321d5w4a2-w5e4w51d”。UUID的优势自然不必多说，我们重点来看看它的缺陷。

长度过长：与数据库中的INT类型相比，存储一个UUID需要花费更多得空空间。
含义不明：影响问题排查和开发调试的效率。
接下来，我们结合一个分布式任务调度系统来看看如何使用ZooKeeper来实现这类全局唯一ID的生成。

通过ZooKeeper节点创建的API接口可以创建一个顺序节点，并且在API返回值中会返回这个节点的完整名字。利用这个特性，我们就可以借助ZooKeeper来生成全局唯一的ID了。

所有客户端都会根据自己的任务类型，在指定类型的任务下面通过调用create()接口创建一个顺序节点，例如创建“job-”节点。
节点创建完毕后，create()接口会返回一个完整的节点名，例如“job-0000000003”。
客户端拿到这个返回值后，拼接上type类型，例如“type2-job-0000000003”，这就可以作为一个全局唯一的ID了。
在ZooKeeper中，每一个数据节点都能够维护一份子节点的顺序顺列，当客户单对其创建一个顺序子节点的时候ZooKeeper会自动以后缀的形式在其子节点上 添加一个序号，在这个场景中就是利用了ZooKeeper的这个特性。以下为博主测试：

另外如果子节点过多，导致连接读取超时，可以适当提高配置中的initLimit以及syncLimit的数值（10倍也是可以的）。

4 分布式协调/通知

分布式协调/通知服务是分布系统不可缺少的环节，是将不同的分布式组件有机结合起来的关键所在。对于一个在多台机器上部署运行的应用而言，通常 需要一个协调者（Coordinator）来控制整个系统的运行流程，例如分布式事务的处理、机器间的互相协调等。同时，引入这样一个协调者，便于将分布式协调的职责从 应用中分离出来，从而可以大大减少系统之间的耦合性，而且能够显著提高系统的可扩展性。

ZooKeeper中特有的Watcher注册与异步通知机制，能够很好地实现分布式环境下不同机器，甚至是不同系统之间的协调与通知，从而实现对数据变更的实时处理。 基于ZooKeeper实现分布式协调与通知功能，通常的做法是不同的客户端都对ZooKeeper上同一个数据节点进行Watcher注册，监听数据节点的变化（包括 数据节点本身及其子节点），如果数据节点发生变化，那么所有订阅的客户端都能够接收到相应的Watcher通知，并做出相应的处理。

4.1 MySQL数据复制总线：MySQL_Replicator

MySQL数据复制总线（以下简称“复制总线”）是一个实时数据复制框架，用于在不同的MySQL数据库实例之间进行异步数据复制和数据变化通知。整个系统是一个由 MySQL数据库集群、消息队列系统、任务管理监控平台以及ZooKeeper集群等组件共同构成的一个包含数据生产者、复制管道和数据消息者等部分的数据总线系统。

在该系统中，ZooKeeper主要负责进行一系列的分布式协调工作，在具体的实现上，根据功能将数据复制组件划分为三个核心子模块：Core、Server和Monitor， 每个模块分别为一个单独的进程，通过ZooKeeper进行数据交换。

Core实现了数据复制的核心逻辑，其将数据复制封装成管道，并抽象出生产者和消费者两个概念，其中生产者通常是MySQL数据库的Binlog日志。
Server负责启动和停止复制任务。
Monitor负责监控任务的运行状态，如果在数据复制期间发生异常或出现故障会进行告警。
三个子模块之间的关系如下图：

每个模块作为独立的进程运行在服务端，运行时的数据和配置信息均保存在ZooKeeper上，Web控制台通过ZooKeeper上的数据获取到后台进程的数据，同时发布控制信息。

4.2 任务注册

Core进程启动的时候，首先会向/mysql_replicator/tasks节点（以下简称“任务列表节点”）注册任务。例如，对于一个“复制热门商品”的任务，Task 所在机器在启动的时候，会首先在任务列表节点上创建一个子节点，例如/mysql_replicator/tasks/copy_hot_time（以下简称“任务节点”），如下图：

如果在注册过程中发现该子节点已经存在，说明已经有其他Task机器注册了该任务，因此自己不需要再创建该节点了。

4.3 任务热备份

为了应对复制任务故障或者复制任务所在主机故障，复制组件采用“热备份”的容灾方式，即将同一个复制任务部署在不同的主机上，我们称这样的机器为“任务机器”， 主、备任务机器通过ZooKeeper互相检测运行健康状况。

为了实现上述热备方案，无论在第一步中是否创建了任务节点，每台任务机器都需要在/mysql_replicator/tasks/copy_hot_item/instances节点上 将自己的主机名注册上去。注意，这里注册的节点类型很特殊，是一个临时的顺序节点。在注册完这个子节点后，通常一个完整的节点名如下： /mysql_replicator/tasks/copy_hot_item/instances/[Hostname]-1，其中最后的序列号就是临时顺序节点的精华所在。

在完成该子节点的创建后，每台任务机器都可以获取到自己创建的节点的完成节点名以及所有子节点的列表，然后通过对比判断自己是否是所有子节点中序号最小的。 如果自己是序号最小的子节点，那么就将自己的运行状态设置为RUNNING，其余的任务机器则将自己设置为STANDBY————我们将这样的热备份策略称为“小序号优先”策略。

4.4 热备切换

完成运行状态的标识后，任务的客户端机器就能够正常工作了，其中标记为RUNNING的客户端机器进行正常的数据复制，而标记为STANDBY的客户端机器则进入待命状态。 这里所谓待命状态，就是说一旦标记为RUNNING的机器出现故障停止了任务执行，那么就需要在所有标记为STANDBY的客户端机器再次按照“小序号优先”策略来 选出RUNNING机器来执行，具体的做法就是标记为STANDBY的机器都需要在/mysql_replicator/tasks/copy_hot_item/instances节点上注册一个 “子节点列表变更”的Watcher监听，用来订阅所有任务执行机器的变化情况————一旦RUNNING机器宕机与ZooKeeper断开连接后，对应的节点就会消失， 于是其他机器也就接收到了这个变更通知，从而开始新一轮的RUNNING选举。

4.5 记录执行状态

既然使用了热备份，那么RUNNING任务机器就需要将运行时的上下文状态保留给STANDBY任务机器。在这个场景中，最主要的上下文状态就是数据复制过程中的 一些进度信息，例如Binlog日志的消费位点，因此需要将这些信息保存到ZooKeeper上以便共享。在Mysql_Replicator的设计中，选择了 /mysql_replicator/tasks/copy_hot_item/lastCommit作为Binlog日志消费位点的存储节点，RUNNING任务机器会定时向这个节点写入当前的Binlog日志消费位点。

4.6 控制台协调

在上文中我们主要讲解了Core组件是如何进行分布式任务协调的，接下来我们再看看Server是如何来管理Core组件的。在Mysql_Replicator中，Server主要的 工作就是进行任务的控制，通过ZooKeeper来对不同的任务进行控制与协调。Server会将每个复制任务对应生产者的元数据，即库名、表名、用户名与密码等数据库信息以及 消费者的相关信息以配置的形式写入任务节点/mysql_replicator/tasks/copy_hot_item中去的，以便该任务的所有任务机器都能够共享该复制任务的配置。

4.7 冷备切换

到目前为止我们已经基本了解了Mysql_Replicator的工作原理，现在再回过头来看上面提到的热备份。在该热备份方案中，针对一个任务，都会至少分配两台 任务机器来进行热备份，但是在一定规模的大型互联网公司中，往往有许多MySQL实例需要进行数据复制，每个数据库实例都会对应一个复制任务， 如果每个任务都进行双机热备份的话，那么显然需要消耗太多的机器。

因此我们同时设计了一种冷备份，它和热备份方案的不同点在于，对所有任务进行分组，如下：

和热备份中比较大的区别在于，Core进程被配置了所属Group（组）。举个例子来说，假如一个Core进程被标记了group1，那么在Core进程启动后，会到对应 的ZooKeeper group1节点下面获取所有的Task列表，假如找到了任务“copy_hot_item”之后，就会遍历这个Task列表的instances节点，但凡还没有子节点的， 则会创建一个临时的顺序节点：/mysql_replicator/task-groups/group1/copy_hot_item/instances/[Hostname]-1————当然，在这个过程中，其它 Core进程也会在这个instances节点下创建类似的子节点。和热备份中的“小序号优先”策略一样，顺序小的Core进程将自己标记为RUNNING，不同之处在于，其它Core 进程则会自动将自己创建的子节点删除，然后继续遍历下一个Task节点————我们将这样的过程称为“冷备份扫描”。就这样，所有Core进程在一个扫描周期内不断地对相应 的Group下面的Task进行冷备份扫描。整个过程如下图：

4.8 冷热备份对比

从上面的讲解中，我们基本对热备份和冷备份两种运行方式都有了一定的了解，现在再来对比下这两种运行方式。在热备份方案中，针对一个任务使用了两台机器进行 热备份，借助ZooKeeper的Watcher通知机制和临时顺序节点的特性，能够非常实时地进行互相协调，但缺陷就是机器资源消耗比较大。而在冷备份方案中，采用了扫描机制， 虽然降低了任务协调的实时性，但是节省了机器资源。（博主总结冷备份与热备份的区别在于，热备份一个运行多个等待，冷备份在于一个运行，系统轮询判断是否有一个 在运行，只要有一个在运行就遍历下个任务，如果一个都没有在运行这个任务就让自己运行）。 ，

4.9 一种通用的分布式系统机器间通信方式

在绝大部分的分布式系统中，系统机器间的通信无外乎心跳检测、工作进度汇报和系统调度这三种类型。接下来，我们将围绕这三种类型的机器通信讲解 如何基于ZooKeeper去实现一种分布式系统间的通信方式。

4.9.1 心跳监测

机器间的心跳检测机制是指在分布式环境中，不同机器之间需要检测到彼此是否在正常运行，例如A机器需要知道B机器是否正常运行。在传统的开发中，我们 通常是通过主机之间是否可以互相PING通来判断，更复杂一点的话，则会通过在机器之间建立长连接，通过TCP连接固有的心跳检测机制来实现上层机器的心跳检测， 这些确实都是一些非常常见的心跳检测方法。而ZooKeeper基于ZooKeeper的临时节点特性，可以让不同的机器都在ZooKeeper的一个指定节点下创建临时子节点，不同的机器 之间可以根据这个临时节点来判断对应的客户端机器是否存活。通过这种方式，检测系统和被检测系统之间并不需要直接相关联，而是通过ZooKeeper上的 某个节点进行关联，大大减少了系统耦合。

4.9.2 工作进度汇报

在一个常见的任务分发系统中，通常任务被分发到不同的机器上执行后，需要实时地将自己的任务执行进度汇报给分发系统。这个时候就可以通过ZooKeeper来实现。 在ZooKeeper上选择一个节点，每个任务客户端都在这个节点下面创建临时子节点，这样便可以实现两个功能：

通过判断临时节点是否存在来确定任务机器是否存活；
各个任务机器会实时地将自己的任务执行进度写到这个临时节点上去，以便中心系统能够实时地获取到任务的执行进度。

4.9.3 系统调度

使用ZooKeeper，能够实现另一种调度模式：一个分布式系统由控制台和一些客户端系统两部分组成，控制台的职责就是需要将一些指令信息发送给所有的 客户端，以控制它们进行相应的业务逻辑。后台管理人员在控制台上做的一些操作，实际上就是修改了ZooKeeper上某些节点的数据，而ZooKeeper进一步 把这些数据变更以事件通知的形式发送给了对应的订阅客户端。

总之，使用ZooKeeper来实现分布式系统机器间的通信，不仅能省去大量底层网络通信和协议设计上重复的工作，更为重要的一点是大大降低了系统之间的耦合， 能够非常方便地实现异构系统之间的灵活通信。

5 集群管理

随着分布式系统规模的日益扩大，集群中的机器规模也随之变大，因此，如何更好地进行集群管理也显得越来越重要了。

所谓集群管理，包括集群监控与集群控制两大块、前者侧重对集群运行时状态的收集，后者则是对集群进行操作与控制。在日常开发和运维过程中，我们经常会有 类似于如下的需求。

希望知道当前集群中究竟有多少机器在工作。
对集群中每台机器的运行时状态进行数据收集。
对集群中机器进行上下线操作。
在传统的基于Agent的分布式集群管理体系中，都是通过在集群中的每台机器上部署一个Agent，由这个Agent负责主动向指定的一个监控中心系统（监控中心 系统负责将所有数据进行集中处理，形成一系列报表，并负责实时报警，以下简称“监控中心”）汇报自己所在机器的状态。在集群规模适中的场景下，这确实 是一种在生产实践中广泛使用的解决方案，能够快速有效地实现分布式环境集群监控，但是一旦系统的业务场景增多，集群规模变大，该解决方案的弊端也就显现出来了:

大规模升级困难：以客户端形式存在的Agent，在大规模使用后，一旦遇到需要大规模升级的情况，就非常麻烦，在升级成本和升级进度的控制上面临巨大的挑战。
统一的Agent无法满足多样的需求：对于机器的CPU使用率、负载（Load）、内存使用率、网络吞吐以及磁盘容量等机器基本的物理状态，使用统一的Agent 来进行监控或许都可以满足。但是，如果需要深入应用内部，对一些业务状态进行监控，例如，在一个分布式消息中间件中，希望监控到每个消费者对消息的消费状态； 或者在一个分布式任务调度系统中，需要对每个机器上任务的执行情况进行监控。很显然，对于这些业务耦合紧密的监控需求，不适合由一个统一的Agent来提供。
编程语言多样性：随着越来越多编程语言的出现，各种异构系统层出不穷。如果使用传统的Agent方式，那么需要提供各种语言的Agent客户端。另一方面， “监控中心”在对异构系统的数据进行整合上面临巨大挑战。
ZooKeeper具有以下两大特性：

客户端如果对ZooKeeper的一个数据节点注册Watcher监听，那么当该数据节点的内容或是其子节点列表发生变更时，ZooKeeper服务器就会向订阅的 客户端发送变更通知。
对在ZooKeeper上创建的临时节点，一旦客户端与服务器之间的会话失效，那么该临时节点也就被自动清除。
利用ZooKeeper的这两大特性，就可以实现另一种集群机器存活性监控的系统。例如，监控系统在/clusterServers节点上注册一个Watcher监听， 那么但凡进行动态添加机器的操作，就会在/clusterServers节点下创建一个临时节点/clusterServers/[Hostname]。这样一来监控系统就能够实时 检测到机器的变动情况，至于后续处理就是监控系统的业务了。下面我们就通过分布式日志收集系统和在线云主机管理这两个典型例子来看看如何使用ZooKeeper 实现集群管理。

5.1 分布式日志收集系统

分布式日志收集系统的核心工作就是收集分布在不同机器上的系统日志，在这里我们重点来看分布式日志系统的收集器模块。

在一个典型的日志系统的架构设计中，整个日志系统会把所有需要收集的日志机器（下文以“日志源机器”代表此类机器）分为多个组别，每个组别对应一个收集器， 这个收集器其实就是一个后台机器（下文以“收集器机器”代表此类机器），用于收集日志。对于大规模的分布式日志收集系统场景，通常需要解决如下两个问题。

变化的日志源机器：在生产环境中，伴随着机器的变动，每个应用的机器几乎每天都是在变化的（机器硬件问题、扩容、机房迁移或是网络问题都会导致一个应用的机器变化）， 也就是说每个组别中的日志源机器通常是在不断变化的。
变化的收集器机器：日志收集系统自身也会有机器的变更或扩容，于是会出现新的收集器加入或是老的收集器机器退出的情况。
上面两个问题，无论是日志源机器还是收集器机器的变更，最终都归结为一点：如何快速、合理、动态地为每个收集器分配对应的日志源机器，这也成为了整个 日志系统正确稳定运转的前提，也是日志收集过程中最大的技术挑战。在这种情况下，引入ZooKeeper是个不错的选择，下面我们来看ZooKeeper在这个 场景中的使用。

5.1.1 注册收集器机器

使用ZooKeeper来进行日志系统收集器的注册、典型做法是在ZooKeeper上创建一个节点作为收集器的根节点，例如/logs/collector（下文我们以“收集器 节点”代表该数据节点），每个收集器机器在启动的时候，都会在收集器节点下创建自己的节点，例如logs/collector/[Hostname]。

5.1.2 任务分发

待所有收集器机器都创建好自己对应的节点后，系统根据收集器节点下子节点的个数，将所有日志源机器分成对应的若干组，然后将分组后的机器列表分别写到 这些收集器机器创建的子节点（例如/logs/collector/host1）上去。这样一来，每个收集器机器都能够从自己对应的收集器节点获取日志源机器列表， 进而开始进行日志收集工作。

5.1.3 状态汇报

完成收集器机器的注册以及任务分发后，我们还要考虑到这些机器随时都有挂掉的可能。因此，针对这个问题，我们需要有一个收集器的状态汇报机制： 每个收集器机器在创建完自己的专属节点后，还需要在对应的子节点上创建一个状态子节点，例如/logs/collector/host1/status，每个收集器都需要定期向 该节点写入自己的状态信息。我们可以把这种策略看作是一种检测机制，通常收集器机器都会在这个节点写入日志收集进度信息。日志系统根据该状态子节点的最后更新时间 来判断对应的收集器机器是否存活。

5.1.4 动态分配

如果收集器机器挂掉或是扩容了，就需要动态地进行收集任务的分配。在运行过程中，日志系统始终关注着/logs/collector这个节点下所有子节点的变更， 一旦检测到有收集器机器停止汇报或是有新的收集器机器加入，就要开始进行任务的重新分配。无论是针对收集器机器停止汇报还是新机器加入的情况， 日志系统都需要将之前分配给该收集器的所有任务转移。为了解决这个问题，通常有两种做法。

5.1.4.1 全局动态分配

这是一种简单粗暴的做法，在出现收集器机器挂掉或是新机器加入的时候，日志系统需要根据新的收集器机器列表，立即对所有的日志源机器重新进行一次分组， 然后将其分配给剩下的收集器机器。

5.1.4.2 局部动态分配

全局动态分配方式虽然策略简单，但是存在一个问题：一个或部分收集器机器的变更，就会导致全局动态任务的分配，影响面比较大，因此风险也就比较大。 所谓局部动态分配，顾名思义就是在小范围内进行任务的动态分配。在这种策略中，每个收集器机器在汇报自己日志收集状态的同时，也会把自己的负载汇报上去。 请注意，这里提到的负载并不仅仅只是简单地指机器CPU负载（Load），而是一个对当前收集器任务执行的综合评估。

在这种策略中，如果一个收集器机器挂了，那么日志系统就会把之前分配给这个机器的任务重新分配到那些负载较低的机器上去。同样，如果有新的收集器机器加入， 会从那些负载高的机器上转移部分任务给这个新加入的机器。

5.1.5 注意事项

5.1.5.1 节点类型

首先看/logs/collector这个节点下面子节点的节点类型。这个节点下面的所有子节点都代表了每个收集器机器，那么初步认为这些子节点必须选择临时节点， 原因是日志系统可以根据这些临时节点来判断收集器机器的存活性。但是，同时还需要注意的一点是：在分布式日志收集这个场景中，收集器节点上还会存放所有 已经分配给该收集器机器的日志源机器列表，如果只是简单地依靠ZooKeeper自身的临时节点机制，那么当一个收集器挂掉或是当这个收集器机器中断“心跳汇报” 的时候，待该收集器节点的会话失效后，ZooKeeper就会立即删除该节点，于是，记录在该节点上的所有日志源机器列表也就随之被清除掉了。

从上面的描述中可以知道，临时节点显然无法满足这里的业务需求，所以我们选择了使用持久节点来标识每一个收集器机器，同时在这个持久节点下面分别创建 /logs/collector/[Hostname]/status节点来表征每一个收集器机器的状态。这样一来，既能实现日志系统对所有收集器的监控，同时在收集器机器挂掉 后，依然能够准确地将分配于其中的任务还原。

5.1.5.2 日志系统节点监听

在实际生产运行过程中，每一个收集器机器更改自己状态节点的频率可能非常高（如每秒1次或更短），而且收集器的数量可能非常大，如果日志系统监听所有 这些节点变化，那么通知的消息量可能会非常大。另一方面，在收集器机器正常工作的情况下，日志系统没有必要去实时地接收每次节点状态变更，因此大部分 这些变更通知都是无用的。因此我们考虑放弃监听设置，而是采用日志系统主动轮询收集器节点的策略，这样就节省了不少网卡流量，唯一的缺陷就是有 一定的延时（考虑到分布式日志收集系统的定位，这个延时是可以接受的）。

5.2 在线云主机管理

在线云主机管理通常出现在那些虚拟主机提供商的应用场景中。在这类集群管理中，有很重要的一块就是集群机器的监控。这个场景通常对于集群中的机器状态， 尤其是机器在线率的统计有较高的要求，同时需要能够快速地对集群中机器的变更做出响应。

在传统的实现方案中，监控系统通过某种手段（比如检测主机的指定端口）来对每台机器进行定时检测，或者每台机器自己定时向监控系统汇报“我还活着”。 但是这种方式需要每个业务系统的开发人员自己来处理网络通信、协议设计、调度和容灾等诸多琐碎的问题。下面来看看使用ZooKeeper实现的另一种集群机器 存活性监控系统。针对这个系统，我们的需求点通常如下。

如何快速地统计当前生产环境一共有多少台机器？
如何快速地获取到机器上/下线的情况？
如何实时监控集群中每台主机的运行时状态？

5.2.1 机器上/下线

为了实现自动化的线上运维，我们必须对机器的上/下线情况有一个全局的监控。通常在新增机器的时候，需要首先将指定的Agent部署到这些机器上去。 Agent部署启动之后，会首先向ZooKeeper的指定节点进行注册，具体的做法就是在机器列表节点下面创建一个临时子节点，例如/XAE/machine/[Hostname] （下文以“主机节点”代表这个节点），如下图：

当Agent在ZooKeeper上创建完这个临时子节点后，对/XAE/machines节点关注的监控中心就会接收到“子节点变更”事件，即上线通知，于是就可以对这个 新加入的机器开启相应的后台管理逻辑。另一方面，监控中心同样可以获取到机器下线的通知，这样便实现了对机器上/下线的检测，同时能够很容易地获取 到在线的机器列表，对于大规模的扩容和容量评估都有很大的帮助。

5.2.2 机器监控

对于一个在线云主机系统，不仅要对机器的在线状态进行检测，还需要对机器的运行时状态进行监控。在运行的过程中，Agent会定时将主机的运行状态信息 写入ZooKeeper上的主机节点，监控中心通过订阅这些节点的数据变更通知来间接地获取主机的运行时信息。

随着分布式系统规模变得越来越庞大，对集群机器的监控和管理显得越来越重要。上面提到的这种借助ZooKeeper来实现的方式，不仅能够实时地检测到集群 中机器的上/下线情况，而且能够实时地获取到主机的运行时信息，从而能够构建出一个大规模集群的主机图谱。

6 Master选举

Master选举是一个在分布式系统中非常常见的应用场景。分布式最核心的特性就是能够将具有独立计算能力的系统单元部署在不同的机器上，构成一个完整的 分布式系统。而与此同时，实际场景中往往也需要在这些分布在不同机器上的独立系统单元中选出一个所谓的“老大”，在计算机科学中，我们称之为“Master”。

在分布式系统中，Master往往用来协调集群中其他系统单元，具有对分布式系统状态变更的决定权。例如，在一些读写分离的应用场景中，客户端的写请求往往 是由Master来处理的；而在另一些场景中，Master则常常负责处理一些复杂的逻辑，并将处理结果同步给集群中其它系统单元。Master选举可以说是ZooKeeper 最典型的应用场景了，在本节中，我们就结合“一种海量数据处理与共享模型”这个具体例子来看看ZooKeeper在集群Master选举中的应用场景。

在分布式环境中，经常会碰到这样的应用场景：集群中的所有系统单元需要对前端业务提供数据，比如一个商品ID，或者是一个网站轮播广告的广告ID（通常 出现在一些广告投放系统中）等，而这些商品ID或是广告ID往往需要从一系列的海量数据处理中计算得到————这通常是一个非常耗费I/O和CPU资源的过程。 鉴于该计算过程的复杂性，如果让集群中的所有机器都执行这个计算逻辑的话，那么将耗费非常多的资源。一种比较好的方法就是只让集群中的部分，甚至只 让其中的一台机器去处理数据计算，一旦计算出数据结果，就可以共享给整个集群中的其他所有客户端机器，这样可以大大减少重复劳动，提升性能。

这里我们以一个简单的广告投放系统后台场景为例来讲解这个模型。整个系统大体上可以分成客户端集群、分布式缓存系统、海量数据处理总线和ZooKeeper 四个部分，如下图：

Client集群每天定时会通过ZooKeeper来实现Master选举。选举产生Master客户端之后，这个Master就会负责进行一系列的海量数据处理，最终计算得到 一个数据结果，并将其放置在一个内存/数据库中。同时，Master还需要通知集群中其它所有的客户端从这个内存/数据库中共享计算结果。

接下去，我们将重点来看Master选举的过程，首先来明确下Master选举的需求：在集群的所有机器中选举出一台机器作为Master。针对这个需求，通常情况 下，我们可以选择常见的关系型数据库中的主键特性来实现：集群中的所有机器都向数据库中插入一条相同主键ID的记录，数据库会帮助我们自动进行主键冲突 检查，也就是说，所有进行插入操作的客户端机器中，只有一台机器能够成功————那么，我们就认为向数据库中成功插入数据的客户端机器成为Master。

乍一看，这个方案确实可行，依靠关系型数据库的主键特性能够很好地保证在集群中选举出唯一的一个Master。但是我们需要考虑的另一个问题是，如果当前 选举出的Master挂了，那么该如何处理？谁来告诉我Master挂了呢？显然，关系型数据库没法通知我们这个事件。

ZooKeeper的强一致性，能够很好地保证在分布式高并发情况下节点的创建一定能够保证全局唯一性，即ZooKeeper将会保证客户端无法重复创建一个已经存在 的数据节点。也就是说，如果同时有多个客户端请求创建同一个节点，那么最终一定只有一个客户端请求能够创建成功。利用这个特性，就能很容易地在分布式 环境中进行Master选举了。

在这个系统中，首先会在ZooKeeper上创建一个日期节点，如下图：

客户端集群每天都会定时往ZooKeeper上创建一个临时节点，例如/master_election/2017-09-03/binding。在这个过程中，只有一个客户端能够成功 创建这个节点，那么这个客户端所在机器就称为了Master。同时，其他没有在ZooKeeper上成功创建节点的客户端，都会在节点/master_ecection/2017-09-03 上注册一个子节点变更的Watcher，用于监控当前的Master机器是否存活，一旦发现当前的Master挂了，那么其余的客户端将会重新进行Master选举。

从上面的讲解中，我们可以看到，如果仅仅只是想实现Master选举的话，那么其实只需要有一个能够保证唯一性的组件即可，例如关系型数据库的主键模型 就是不错的选择。但是，如果希望能够快速地进行集群Master动态选举，那么基于ZooKeeper来实现是一个不错的新思路。

7 分布式锁

分布式锁是控制分布式系统之间同步访问共享资源的一种方式。如果不同的系统或是同一个系统的不同主机之间共享了一个或一组资源，那么访问这些资源的 时候，往往需要通过一些互斥手段来防止彼此之间的干扰，以保证一致性，在这种情况下，就需要使用分布式锁了。

在平时的实际项目开发中，我们往往很少会去在意分布式锁，而是依赖于关系型数据库固有的排他性来实现不同进程之间的互斥。这确实是一种非常简便且被 广泛使用的分布式锁实现方式。然而有一个不争的事实是，目前绝大多数大型分布式系统的性能瓶颈都集中在数据库操作上。因此，如果上层业务再给数据库 添加一些额外的锁，例如行锁、表锁甚至是繁重的事务处理，那么是不是会让数据库更加不堪重负呢？下面我们来看看使用ZooKeeper如何实现分布式锁， 这里主要讲解排他锁和共享锁两类分布式锁。

7.1 排他锁

排他锁（Exclusive Locks，简称X锁），又称为写锁或独占锁，是一种基本的锁类型。如果事务T1对数据对象O1加上了排他锁，那么在整个加锁期间，只允许 事务T1对O1进行读取和更新操作，其他任何事务都不能再对这个数据对象进行任何类型的操作————直到T1释放了排他锁。

从上面讲解的排他锁的基本概念中，我们可以看到，排他锁的核心是如何保证当前有且仅有一个事务获得锁，并且锁被释放后，所有正在等待获取锁的事务都 能够被通知到。下面我们就看看如何借助ZooKeeper实现排他锁。

7.1.1 定义锁

有两种常见的方式可以用来定义锁，分别是synchronized机制和JDK5提供的ReentrantLock。然而，在ZooKeeper中，没有类似于这样的API可以直接使用， 而是通过ZooKeeper上的数据节点来表示一个锁，例如/exclusive_lock/lock节点就可以被定义为一个锁，如下图：

7.1.2 获取锁

在需要获取排他锁时，所有的客户端都会试图通过调用create()接口，在/exclusive_lock节点下创建临时子节点/exclusive_lock/lock。而ZooKeeper 会保证在所有的客户端中，最终只有一个客户端能够创建成功，那么就可以认为该客户端获取了锁。同时，所有没有获取到锁的客户端就需要到/exclusive_lock 节点上注册一个子节点变更的Watcher监听，以便实时监听到lock节点的变更情况。

7.1.3 释放锁

由于是临时节点，有下面两种情况，可能释放锁：

• 当前获取锁的客户端机器发生宕机
• 正常执行完业务逻辑后，客户端主动将临时节点删除。
  无论在上面情况下移除了lock节点，ZooKeeper都会通知所有在/exclusive_lock节点上注册了子节点变更Watcher监听的客户端。这些客户端在接收到通知后， 再次重新发起分布式锁获取，即重复“获取锁”过程。如下图：

7.2 共享锁

共享锁（Shared Locks，简称S锁），又称读锁，同样是一种基本的锁类型。如果事务T1对数据对象O1加上了共享锁，那么当前事务只能对O1进行读取操作， 其他事务也只能对这个数据对象加共享锁————直到该数据对象上的所有共享锁都被释放。

共享锁和排他锁最根本的区别在于，加上排他锁后，数据对象只对一个事务可见，而加上共享锁后，数据对所有事务都可见。

7.2.1 定义锁

和排他锁一样，同样是通过ZooKeeper上的数据节点来表示一个锁，是一个类似于/shared_lock/[Hostname]-请求类型-序号的临时顺序节点，例如 /shared_lock/192.168.0.1-R-0000000001，那么，这个节点就代表了一个共享锁，如下图：

7.2.2 获取锁

在需要获取共享锁时，所有客户端都会到/shared_lock这个节点下面创建一个临时顺序节点，如果当前是读请求，那么就创建例如/shared_lock/192.168.0.1-R-000000001/ 的节点；如果是写请求，那么就创建例如/shared_lock/192.168.0.1-W-000000001的节点。

7.2.3 判断读写顺序

根据共享锁的定义，不同的事务都可以同时对同一数据对象进行读取操作，而更新操作必须在当前没有任何事务进行读写操作的情况下进行。基于这个原则， 我们来看看如何通过ZooKeeper的节点来确定分布式读写顺序，大致可以分为如下4个步骤。

创建完节点后，获取/shared_lock节点下的所有子节点，并对该节点注册子节点变更的Watcher监听。
确定自己的节点序号在所有子节点中的顺序。
如果当前节点业务为读请求：如果没有比自己序号小的子节点，或是所有比自己序号小的子节点都是读请求，那么表明自己已经成功获取到了共享锁，同时 开始执行读取逻辑。如果比自己序号小的子节点有写请求，那么就需要进入等待。
如果当前节点业务为写请求：如果自己不是序号最小的子节点， 那么就需要进入等待。
接收到Watcher通知后，重复步骤1。

7.2.4 释放锁

释放锁的逻辑和排他锁是一致的。

7.2.5 羊群效应

上面讲解的这个共享锁实现，大体上能够满足一般的分布式集群竞争锁的需求，并且性能都还可以————这里说的一般场景是指集群规模不是特别大，一般是在 10台机器以内。但是如果机器规模扩大之后，会有什么问题呢？我们着重来看上面“判断读写顺序”过程的步骤3，如下图，看看实际运行中的情况。

192.168.0.1这台机器首先进行读操作，完成读操作后将节点/192.168.0.1-R-000000001删除。
余下的4台机器均收到了这个节点被移除的通知，然后重新从/shared_lock/节点上获取一份新的子节点列表。
每个机器判断自己的读写顺序。其中192.168.0.2这台机器检测到自己已经是序号最小的机器了，于是开始进行写操作，而余下的其他机器发现没有轮到 自己进行读取或更新操作，于是继续等待。
继续……
上面这个过程就是共享锁在实际运行中最主要的步骤了，我们着重看下上面步骤3中提到的：“而余下的其他机器发现没有轮到自己进行读取或更新操作，于是继续等待。” 很明显，我们看到，192.168.0.1这个客户端在移除自己的共享锁后，ZooKeeper发送了子节点变更Watcher通知给所有机器，然而这个通知除了给192.168.0.2 这台机器产生实际影响外，对于余下的其他所有机器都没有任何作用。

相信读者也已经意思到了，在这整个分布式锁的竞争过程中，大量的“Watcher通知”和“子节点列表获取”两个操作重复运行，并且绝大多数的运行结果都是 判断出自己并非是序号最小的节点，从而继续等待下一次通知————这个看起来显然不怎么科学。客户端无端地接收到过多和自己并不相关的事件通知，如果在集群 规模比较大的情况下，不仅会对ZooKeeper服务器造成巨大的性能影响和网络冲击，更为严重的是，如果同一时间有多个节点对应的客户端完成事务或是事务 中断引起节点消息，ZooKeeper服务器就会在短时间内向其余客户端发送大量的事件通知————这就是所谓的羊群效应。

上面这个ZooKeeper分布式共享锁实现中出现羊群效应的根源在于，没有找准客户端真正的关注点。我们再来回顾一下上面的分布式锁竞争过程，它和核心 逻辑在于：判断自己是否是所有子节点中序号最小的。于是，很容易可以联想到，每个节点对应的客户端只需要关注比自己序号小的那个相关节点的变更情况 就可以了————而不需要关注全局的子列表变更情况。

7.2.6 改进后的分布式锁实现

现在我们来看看如何改进上面的分布式锁实现。首先，我们需要肯定的一点是，上面提到的共享锁实现，从整体思路上来说完全正确。这里主要的改动在于： 每个锁竞争者，只需要关注/shared_lock/节点下序号比自己小的那个节点是否存在即可，具体实现如下：

1. 客户端调用create()方法创建一个类似于/shared_lock/[Hostname]-请求类型-序号的临时顺序节点。
2. 客户端调用getChildren()接口来获取所有已经创建的子节点列表，注意，这里不注册任何Watcher。
3. 如果无法获取共享锁，那么就调用exist()来对比自己小的那个节点注册Watcher。注意，这里“比自己小的节点”只是一个笼统的说法，具体对于读请求和写请求不一样。
   读请求：向比自己序号小的最后一个写请求节点注册Watcher监听。
   写请求：向比自己序号小的最后一个节点注册Watcher监听。
4. 等待Watcher通知，继续进入步骤2。
   流程图如下：

7.2.7 注意

看到这里，相信很多读者都会觉得改进后的分布式锁实现相对来说比较麻烦。确实如此，如同在多线程并发编程实践中，我们会去尽量缩小锁的范围————对于 分布式锁实现的改进其实也是同样的思路。那么对于开发人员来说，是否必须按照改进后的思路来设计实现自己的分布式锁呢？答案是否定的。在具体的实际开发 过程中，我们提倡根据具体的业务场景和集群规模来选择适合自己的分布式锁实现：在集群规模不大、网络资源丰富的情况下，第一种分布式锁实现方式是 简单实用的选择；而如果集群规模达到一定程度，并且希望能够精细化地控制分布式锁机制，那么不妨试试改进版的分布式锁实现。

8 分布式队列

业界有不少分布式队列产品，不过绝大多数都是类似于ActiveMQ、Kafka等的消息中间件。在本节中，我们主要介绍基于ZooKeeper实现的分布式队列。 分布式队列，简单地讲分为两大类，一种是常规的先入先出队列，另一种则是要等到队列元素集聚之后才统一安排执行的Barrier模型。

8.1 FIFO:先进先出

使用ZooKeeper实现FIFO队列，和共享锁的实现非常类似。FIFO队列就类似于一个全写的共享锁模型，大体的设计思想其实非常简单：所有客户端都会到 /queue_fifo这个节点下面创建一个临时顺序节点，例如/queue_fifo/192.168.0.1-0000000001，如下图：

创建完节点之后，根据如下4个步骤来确定执行顺序。

通过调用getChildren()接口来获取/queue_fifo节点下的所有子节点，即获取队列中所有的元素。
确定自己的节点序号在所有子节点中的顺序。
如果自己不是序号最小的子节点，那么就需要进入等待，同时向比自己序号小的最后一个节点注册Watcher监听。
接收到Watcher通知到，重复步骤1。
整个FIFO队列的工作流程，如下图：

8.2 Barrier:分布式屏障

Barrier原意是指障碍物、屏障，而在分布式系统中，特指系统之间的一个协调条件，规定了一个队列的元素必须都集聚后才能统一进行安排，否则一直等待。 这往往出现在那些大规模分布式并行计算的应用场景了：最终的合并计算需要基于很多并行计算的子结果来进行。这些队列其实是FIFO队列的基础上进行了 增强，大致的设计思想如下：开始时，/queue_barrier节点是一个已经存在的默认节点，并且将其节点的数据内容赋值为一个数字n来代表Barrier值， 例如n=10表示只有当/queue_barrier节点下的子节点个数达到10后，才会打开Barrier。之后，所有的客户端都会到/queue_barrier节点下创建一个 临时节点，例如/queue_barrier/192.168.0.1，如下图：

创建完节点之后，根据如下5个步骤来确定执行顺序。

1. 通过调用getDate()接口获取/queue_barrier节点的数据内容：10。
2. 通过调用getChildren()接口获取/queue_barrier节点下的所有子节点，即获取队列中所有元素，同时注册对子节点列表变更的Watcher监听。
3. 统计子节点的个数。
4. 如果子节点个数还不足10个，那么就需要进入等待。
   
5. 接收到Watcher通知后，重复步骤2。

博主理解为，如果在很少的时间内，同时超过了10个以上的业务机创建了临时节点，那么业务处理的速度并不是恒定的，因为有可能这个业务被11个机器处理， 下一个被12个业务机处理？

9 小结

数据发布/订阅（配置中心）、负载均衡（DNS解析）、命名服务（顺序节点特性）、分布式协调/通知（Watcher机制），集群管理（子节点）、Master选举 （同时创建节点）、分布式锁（同时创建节点）、分布式队列（创建顺序节点）

本章概要：
首先对ZooKeeper进行一个整体上的介绍，包括ZooKeeper的设计目标、由来以及它的基本概念，然后将会重点介绍ZAB这一ZooKeeper中非常重要的一致性协议。

1. 初识ZooKeeper

1.1 ZooKeeper介绍

ZooKeeper由雅虎创建，是Chubby的开源实现。设计目标是将那些复杂且容易出错的分布式一致性服务封装起来，构成一个高效可靠的原语集，并以一系列简单易用的接口提供给用户使用。

1.1.1 ZooKeeper是什么

ZooKeeper是一个典型的分布式数据一致性的解决方案，分布式应用程序可以基于它实现诸如数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master选举 、分布式锁和分布式队列等功能。ZooKeeper可以保证如下分布式一致性特性。

.1 顺序一致性

从同一个客户端发起的事务请求，最终将会严格地按照其发起顺序被应用到ZooKeeper中去。

.2 原子性

所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的，也就是说，要么整个集群所有机器都成功应用了某一个事务，要么都没有应用，一定 不会出现集群中部分机器应用了该事务，而另外一部分没有应用的情况。

.3 单一视图（Single System Image）

无论客户端连接的是哪ZooKeeper服务器，其看到的服务端数据模型都是一致性。

.4 可靠性

一旦服务端成功地应用了一个事务，并完成对客户端的响应，那么该事务所引起的服务端状态变更将会被一直保留下来，除非有另一个事务又对其进行了变更。

.5 实时性

通常人们看到实时性的第一反应是，一旦一个事务被成功应用，那么客户端能够立即从服务端上读取到这个事务变更后的最新数据状态。这里需要注意的是， ZooKeeper仅仅保证在一定额时间段内，客户端最终一定能够从服务端上读取到最新的数据状态。

1.1.2 ZooKeeper的设计目标

ZooKeeper致力于提供一个高性能、高可用，且具有严格的顺序访问控制能力（主要是写操作的严格顺序性）的分布式协调服务。高性能使得ZooKeeper能够应用于 那些对系统吞吐有明确要求的大型分布式系统中，高可用使得分布式的单点问题得到了很好的解决，而严格的顺序访问控制使得客户端能够基于ZooKeeper实现 一些复杂的同步原语。下面我们来具体看一下ZooKeeper的四个设计目标。

.1 目标一：简单的数据模型

ZooKeeper使得分布式程序能够通过一个共享的、树型结构的名字空间来进行相互协调。

这里所说的树型结构的名字空间，是指ZooKeeper服务器内存中的一个数据模型，其由一系列被称为ZNode的数据节点组成，总的来说，其数据模型类似于一个文件系统， 而ZNode之间的层级关系，就像文件系统的目录结构一样。不过和传统的磁盘文件系统不同的是，ZooKeeper将全量数据存储在内存中，以此来实现提高 服务器吞吐、减少延迟的目的。

.2 目标二：可以构建集群

一个ZooKeeper集群通常由一组机器组成，一般3~5台机器就可以组成一个可用的ZooKeeper集群了（2n+1）。

组成ZooKeeper集群的每台机器都会在内存中维护当前的服务器状态，并且每台机器之间都互相保持着通信。值得一提的，只要集群中存在超过一半的机器 能够正常工作，那么整个集群就能够正常对外服务。

ZooKeeper的客户端程序会选择和集群中任意一台机器共同来创建一个TCP连接，而一旦客户端和某台ZooKeeper服务器之间的连接断开后，客户端会自动连接 到集群中的其他机器。

.3 顺序访问

对于来自客户端的每个更新请求，ZooKeeper都会分配一个全局唯一的递增编号，这个编号反映了所有事务操作的先后顺序，应用程序可以使用ZooKeeper 的这个特性来实现更高层次的同步原语。

.4 高性能

由于ZooKeeper将全量数据存储在内存中，并直接服务于客户端的所有非事务请求，因此它尤其适用于以读操作为主的应用场景。

1.2 ZooKeeper从何而来

ZooKeeper最早起源于雅虎研究院的一个研究小组。在当时，研究人员发现，在雅虎内部很多大型系统基本都需要依赖一个类似的系统来进行分布式协调，但是 这些系统往往都存在分布式单点问题。所以雅虎的开发人员就试图开发一个通用的无单点问题的分布式协调框架，以便让开发人眼将精力集中在处理业务逻辑上。

关于“ZooKeeper”这个项目的名字，其实也有一段趣闻。在立项初期，考虑到之前内部很多项目都是使用动物的名字来命名的（例如著名的Pig项目），雅虎 的工程师希望给合格项目也取一个动物的名字，大家纷纷表示就叫动物园管理员吧————因为各个以动物命名的分布式组件放在一起，雅虎的整个分布式系统看 上去就像一个大型的动物园了，而ZooKeeper正好要用来进行分布式环境的协调————于是，ZooKeeper的名字也就由此诞生了。

1.3 ZooKeeper的基本概念

1.3.1 集群角色

通常在分布式系统中，构成一个集群的每一台机器都有自己的角色，最典型的集群模式就是Master/Slave模式（主备模式）。在这种模式下，我们把能够处理所有 写操作的机器称为Master机器，把所有通过异步复制方式获取最新数据，并提供读服务的机器称为Slave机器。

而在ZooKeeper中，这些概念被颠覆了。它没有沿用传统的Master/Slave概念，而是引入了Leader、Follower和Observer三种角色。ZooKeeper集群中的所有 机器通过一个Leader选举过程来选定一台被称为“Leader”的机器，Leader服务器为客户端提供读和写服务。除Leader外，其他机器包括Follower和Observer。 Follower和Observer都能够提供读服务，唯一的区别在于，Observer机器不参与Leader选举过程，也不参与写操作的“过半写成功”策略，因此Observer可以 在不影响写性能的情况下提升集群的读性能。

1.3.2 会话（Session）

Session是指客户端会话，在讲解会话之前，我们首先来了解一下客户端连接。在ZooKeeper中，一个客户端连接是指客户端和服务器之间的一个TCP长连接。 ZooKeeper对外的服务端口默认是2181，客户端启动的时候，首先会服务器建立一个TCP连接，从第一次连接建立开始，客户端会话的生命周期也开始了， 通过这个连接，客户端能够通过心跳检测与服务器保持有效的会话，也能够向ZooKeeper服务器发送请求并接受响应，同时还能够通过该连接接收来自服务器的Watch事件通知。 Session的sessionTimeout值用来设置一个客户端会话的超时时间。当由于服务器压力太大、网络故障或是客户端主动断开连接等各种原因导致客户端连接断开时， 只要在sessionTimeout规定的时间内能够重新连接上集群中任意一台服务器，那么之前创建的会话仍然有效。

1.3.3 数据节点（Znode）

在谈到分布式的时候，我们通常说的“节点”是指组成集群的每一台机器。然后，在ZooKeeper中，“节点”分为两类，第一类同样是指构成集群的机器，我们称之为机器节点； 第二类则是指数据模型中的数据单元，我们称之为数据几点————Znode。ZooKeeper将所有数据存储在内存中，数据模型是一棵树（Znode Tree），由/进行分割 的路径，就是一个Znode，例如/foo/path1。每个Znode上都会保存自己的数据内容，同时还会保存一系列属性信息。

在ZooKeeper中，Znode可以分为持久节点和临时节点两类。所谓持久节点是指一旦这个Znode被创建了，除非主动进行Znode的移除操作，否则这个Znode将一直保存在ZooKeeper 上。临时节点生命周期和客户端会话绑定，一旦客户端会话失效，那么这个客户端创建的所有临时节点都会被移除。另外，ZooKeeper还允许用户为每个节点 添加一个特殊的属性：SEQUENTIAL。一旦节点被标注上这个属性，那么在这个节点被创建的时候，ZooKeeper会自动在其节点名后面追上一个整型数字，这个 整型数字是一个由父节点维护的自增数字。

1.3.4 版本

在前面我们已经提到，ZooKeeper的每个Znode上都会存储数据，对应于每个Znode，ZooKeeper都会为其维护一个叫作Stat的数据结构，Stat中记录了这个Znode 的三个数据版本，分别是version（当前Znode的版本）、cversion（当前Znode字节点的版本）、aversion（当前Znode的ACL版本）。

1.3.5 Watcher

Watcher（事件监听器），是ZooKeeper中得意一个很重要的特性。ZooKeeper允许用户在指定节点上注册一些Watcher，并且在一些特定事件触发的时候，ZooKeeper服务端 会将事件通知到感兴趣的客户端上去，该机制是ZooKeeper实现分布式协调服务的重要特性。

1.3.6 ACL

ZooKeeper采用ACL（Access Control Lists）策略来进行权限控制。

• CREATE：创建子节点的权限。
• READ：获取节点数据和子节点列表的权限。
• WRITE：更新节点数据的权限。
• DELETE：删除子节点的权限。
• ADMIN：设置节点ACL的权限。

其中尤其需要注意的是，CREATE和DELETE这两种权限都是针对子节点的权限控制。

1.4 为什么选择ZooKeeper

在解决分布式数据一致性上，除了ZooKeeper之外，目前还没有一个成熟稳定且被大规模应用的解决方案。ZooKeeper无论从性能、易用性还是稳定性上来说， 都已经达到了一个工业级产品的标准。并且开发源码、免费。

2 ZooKeeper的ZAB协议

2.1 ZAB协议

事实上，ZooKeeper并没有完全采用Paxos算法，而是使用了一种称为ZooKeeper Atomic Broadcast（ZAB，ZooKeeper原子消息广播协议）的协议作为其数据一致性的核心算法。

ZAB协议是为分布式协调服务ZooKeeper专门设计的一种支持崩溃恢复的原子广播协议。ZAB协议的开发设计人员在协议设计之初并没有要求其具有很好的扩展性， 最初只是为雅虎公司内部那些高吞吐量、低延迟、健壮、简单的分布式系统场景设计的。在ZooKeeper的官方文档也指出，ZAB协议不像Paxos算法那样，是一种 通用的分布式一致性算法，它是一种特别为ZooKeeper设计的崩溃可恢复的原子消息广播算法。

在ZooKeeper中，主要依赖ZAB协议来实现分布式数据一致性，基于该协议，ZooKeeper实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。具体的， ZooKeeper使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用ZAB的原子广播协议，将服务器数据的状态变更以事务Proposal的形式广播到所有的副本进程上去。 ZAB协议的这个主备模型架构保增乐同一时刻集群中只能够有一个主进程来广播服务器的状态变更，因此能够很好地处理客户端大量的并发请求。另一方面，考虑到在分布式环境中， 顺序执行的一些状态变更其前后会存在一定的依赖关系，有些状态变更必须依赖于比它早生成的那些状态变更，例如变更C需要依赖变更A和变更B。这样的依赖关系 也对ZAB协议提出了一个要求：ZAB协议必须能够保证一个全局的变更序列被顺序应用，也就是说，ZAB协议需要保证如果一个状态变更已经被处理了，那么所有其 依赖的状态变更都应该已经被提前处理掉了。最后，考虑到主进程在任何时候都有可能出现崩溃退出或重启现象。因此，ZAB协议还需要做到在当前主进程出现上述异常情况的时候，依旧能够正常工作。

ZAB协议的核心是定义了哪些会改变ZooKeeper服务器数据状态的事务请求的处理方式，即：

所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的其他服务器则成为Follower服务器。 Leader服务器负责将一个客户端事务请求转换成一个事务Proposal（提议），并将该Proposal分发给集群中所有的Follower服务器。之后Leader 服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower 服务器分发Commit消息，要求其将前一个Proposal进行提交。

2.2 协议介绍

ZAB协议包括两种基本的模式，分别是崩溃恢复和消息广播。当整个服务框架在启动过程中，或是当Leader服务器出现网络中断、崩溃退出与重启等异常情况时， ZAB协议就会进入恢复模式并选举产生新的Leader服务器。当选举产生了新的Leader服务器，同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后， ZAB协议就会退出恢复模式。其中，所谓的状态同步是指数据同步，用来保证集群中存在过半的机器能够和Leader服务器的数据状态保持一致。

当集群中已经有过半的Follower服务器完成了和Leader服务器的状态同步，那么整个服务框架就可以进入消息广播模式了。当一台同样遵守ZAB协议的服务器启动后加入到 集群中时，如果此时集群中已经存在一个Leader服务器在负责进行消息广播，那么新加入的服务器就会自觉地进入数据恢复模式：找到Leader所在的服务器， 并与其进行数据同步，然后一起参与到消息广播流程中区。正如上文介绍所说的，ZooKeeper设计成只允许唯一的一个Leader服务器来进行事务请求和处理。 Leader服务器在接收到客户端的事务请求后，会生成对应的事务提案并发起一轮广播协议；而如果集群中的其他机器接收到客户端的事务请求， 那么这些非Leader服务器首先将这个事务请求转发给Leader服务器。

当Leader服务器出现崩溃退出或机器重启，亦或是集群中已经不存在过半的服务器与该Leader服务器保持正常通信时，那么在重新开始新一轮的原子广播事务操作之前， 所有进程首先会使用崩溃恢复协议来使彼此达到一个一致的状态，于是整个ZAB流程就会从消息广播模式进入到崩溃恢复模式。

一个机器要称为新的Leader，必须获得过半进程的支持，同时由于每个进程都有可能会崩溃，因此，在ZAB协议运行过程中，前后会出现多个Leader，并且每个进程也有可能 会多次成为Leader。进入崩溃恢复模式后，只要集群中存在过半的服务器能够彼此进行正常通信，那么就可以产生一个新的Leader并再次进入消息广播模式。 举个例子来说，一个由3台机器组成的AZB服务，通常由1个Leader、2个Follower服务器组成。某一时刻，加入其中一个Follower服务器挂了，整个ZAB是 不会中断服务的，这是因为Leader服务器依然能够获得过半机器（包括Leader自己）的支持。

2.2.1 消息广播

ZAB协议的消息广播过程使用的是一个原子广播协议，类似于一个二阶段提交过程。针对客户端的事务请求，Leader服务器会为其生成对应的事务Proposal，并 将其发送给集群中其余所有的机器，然后再分别收集各自的选票，最后进行事务提交。

在ZAB协议的二阶段提交过程中，移除了中断逻辑，所有的Follower服务器要么正常反馈Leader提出的事务Proposal，要么就抛弃Leader服务器。同时，ZAB协议将二阶段 提交中的中断逻辑移除意味着我们可以在过半的Follower服务器已经反馈Ack之后就开始提交事务Proposal了，而不需要等待集群中所有的Follower服务器都 反馈响应。当然，在这种简化了的二阶段提交模型下，是无法处理Leader服务器崩溃退出而带来的数据不一致问题，因此在ZAB协议中添加了另一个模式， 即采用崩溃恢复模式来解决这个问题。另外，整个消息广播协议是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易地保证消息广播过程中 消息接收与发送的顺序性。

在整个消息广播过程中，Leader服务器会为每个事务请求对应的Proposal来进行广播，并且在广播事务Proposal之前，Leader服务器会首先为这个事务Proposal分配一个 全局单调递增的唯一ID，我们称之为事务ID（即ZXID）。由于ZAB协议需要保证每一个消息严格的因果关系，因此必须将每一个事务Proposal按照其ZXID的 先后顺序来进行排序与处理。

具体的，在消息广播过程中，Leader服务器会为每一个Follower服务器都各自分配一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列中，并且根据FIFO 策略进行消息发送。每一个Follower服务器在接收到这个事务Proposal之后，都会首先将其以事务日志的形式写入到本地磁盘中去，并且在成功写入后反馈给Leader 服务器一个Ack响应。当Leader服务器接收到超过半数Follower的Ack响应后，就会广播一个Comit消息给所有的Follower服务器以通知其进行事务提交，同时Leader自身 也会完成对事务的提交，而每一个Follower服务器在接收到Commit消息后，也会完成对事务的提交。

2.2.2 崩溃恢复

一旦Leader服务器出现奔溃，或者说由于网络原因导致Leader服务器失去了与过半Follower的联系，那么就会进入崩溃恢复模式。在ZAB协议中，为了保证程序的正确运行， 整个恢复过程后需要选举出一个新的Leader服务器。因此，AZB协议需要一个高效且可靠的Leader选举算法，从而确保能够快速地选举出新的Leader。同时， Leader选举算法不仅仅需要让Leader自己知道其自身已经被选举为Leader，同时还需要让集群中的所有其他机器也能够快速地感知到选举产生的新的Leader服务器。

.1 基本特性

ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功，那么应该在所有的机器上都被处理成功，哪怕机器出现故障崩溃。接下来我们看看在崩溃恢复过程中， 可能会出现的两个数据不一致性的隐患及针对这些情况ZAB协议所需要保证的特性。

ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交。

假设一个事务在Leader服务器上被提交了，并且已经得到过半Follower服务器的Ack反馈，但是它将Commit消息发送给所有Follower机器之前，Leader服务器挂了。 例如，在集群正常运行过程中的某一个时刻，Server1是Leader服务器，其先后广播了消息P1、P2、C1、P3、C2，其中，当Leader服务器将消息C2（Commit Of Proposal2） 发出后就立即崩溃退出了。针对这种情况，ZAB协议就需要确保事务Proposal2最终能够在所有的服务器上都被提交成功，否则将出现不一致。

ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务。

假设初始的Leader服务器Server1在提出了一个事务Proposal3之后就崩溃退出了，从而导致集群中的其它服务器都没有收到这个事务Proposal。于是，当Server1 恢复过来再次加入到集群中的时候，ZAB协议需要确保丢弃Proposal3这个事务。

结合上面的这两个崩溃恢复过程中需要处理的特殊情况，就决定了ZAB协议必须设计这样一个Leader选举算法：能够确保提交已经被Leader提交的事务Proposal， 同时丢弃已经被跳过的事务Proposal。针对这个要求，如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高编号（即ZXID）的事务 Proposal，那么就可以保证这个新选举出来的Leader一定具有所有已经提交的提案。更为重要的是，如果让具有最高编号事务Proposal的机器来成为Leader，就 可以省去Leader服务器检查Proposal提交和丢弃工作的这一步操作了。

.2 数据同步

完成Leader选举之后，在正式开始工作（即接收客户端的事务请求，然后提出新的提案）之前，Leader服务器会首先确认事务日志中的所有Proposal是否都已经 被集群中过半的机器提交了，即是否完成数据同步。下面我们就来看看ZAB协议的数据同步过程。

所有正常运行的服务器，要么称为Leader，要么称为Follower并和Leader保持同步。Leader服务器需要确保所有的Follower服务器能够接收每一条事务Proposal， 并且能够正确地将所有已经提交了的事务Proposal应用到内存数据中去。具体的，Leader服务器会为每一个Follower服务器都准备一个队列，并将那些没有被 各Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器，并在每一个Proposal消息后面紧接着再发送一个Commit消息，以表示该事务 已经被提交。等到Follower服务器将所有其尚未同步的事务Proposal都从Loeader服务器上同步过来并成功应用到本地数据库中后，Leader服务器就会将 Follower服务器加入到真正的可用Follower列表中，并开始之后的其它流程。

上面讲到的是正常情况下的数据同步逻辑，下面来看ZAB协议是如何处理那些需要被丢弃的事务Proposal的。在ZAB协议的事务编号ZXID设计中，ZID是一个64位的数字， 其中低32位可以看作是一个简单的单调递增的计数器，针对客户端的每一个事务请求，Leader服务器在产生一个新的事务Proposal的时候，都会对该计数器进行加1操作； 而高32位则代表了Leader周期epoch的编号，每当选举产生一个新的Leader服务器，就会从这个Leader服务器上取出本地日志中最大事务Proposal的ZXID，并从 该ZXID中解析出对应的epoch值，然后再对其进行加1操作，之后就会以此编号作为新的epoch，并将低32位置0来开始生成新的ZXID。ZAB协议中的这一通过epoch编号 来区分Leader周期变化的策略，能够有效地避免不同的Leader服务器错误地使用相同的ZXID编号提出不一样的事务Proposal的异常情况，这对于识别在Leader崩溃恢复前后 生成的Proposal非常有帮助，大大简化和提升了数据恢复流程。

基于这样的策略，当一个包含了上一个Leader周期尚无提交过的事务Proposal的服务器启动时，其肯定无法成为Leader，原因很简单，因为当前集群中一定包含一个Quorum集合， 该集合中的机器一定包含了更好epoch的事务Proposal，因此这台机器的事务Proposal肯定不是最高，也就无法成为Leader了。当这台机器加入到集群中，以 Follower角色连接上Leader服务器之后，Leader服务器会根据自己服务器上最后被提交的Proposal来和Follower服务器的Proposal进行比对，比对的结果 当然是Leader会要求Follower进行一个回退操作————回退到一个确实已经被集群中过半机器提交的最新的事务Proposal。（ZXID的高32位是纪元，当已经挂了 的Leader重新恢复变成Leader时，其纪元一定小于当前一直在运行的服务器，因此老的Leader就算恢复了也不会成为Leader。大清亡了，新的时代，）

2.3 ZAB与Paxos算法的联系

ZAB协议并不是Paxos算法的一个典型实现，在讲解ZAB和Paxos之间的区别之前，我们首先来看下两者的联系。

两者都存在一个类似于Leader进程的角色，由其负责协调多个Follower进程的运行。
Leader进程都会等待超过半数的Follower做出正确的反馈后，才会将一个提案进行提交。
在ZAB协议中，每个Proposal中都包含了一个epoch值，用来代表当前的Leader周期，在Paxos算法中，同样存在这样的一个标识，只是名字变成了Ballot。
在Paxos算法中，一个新选举产生的主进程会进行两个阶段的工作。第一阶段被称为读阶段，在这个阶段中，这个新的主进程会通过和所有其它进程进程通信的方式来收集上一个主进程提出 的提案，并将它们提交。第二阶段被称为写阶段，在这个阶段，当前主进程开始提出它自己的提案。在Paxos算法设计的基础上，ZAB协议额外添加了一个同步阶段。 在同步阶段之前，ZAB协议也存在一个和Paxos算法中的读阶段非常类似的过程，称为发现（Discovery）阶段。在同步阶段中，新的Leader会确保存在 过半的Follower已经提交了之前Leader周期中的所有事务Proposal。这一同步阶段的引入，能够有效地保证Leader在新的周期中提出事务Proposal之前，所有的 进程都已经完成了对之前所有事务Proposal的提交。一旦完成同步阶段后，那么ZAB就会执行和Paxos算法类似的写阶段。

总的来说，ZAB协议和Paxos算法的本质区别在于，两者的设计目标不太一样。ZAB协议主要用于构建一个高可用的分布式数据主备系统，例如ZooKeeper， 而Paxos算法则是用于构建一个分布式的一致性状态机系统。

3 小结

ZooKeeper的设计目标、由来以及基本概念。另外还有它的一致性协议————ZAB，并将其与Paxos算法进行了比对。

ZooKeeper为了保证状态的一致性，提出了两个安全属性：

• 全序（消息a和消息b发送的顺序Client和Server看的都是一样的），通过TCP协议的FIFO队列特性实现。
• 因果顺序（消息a先于消息b发送，则消息a先于消息b执行）。通过Leader消息先到先执行。

前章提要：
主要从理论上讲解了Paxos算法，如何在保证数据一致性的情况下兼顾稳定性和性能也是一个巨大的挑战。从本章开始，我们将结合实际工程实际中的Paxos实现， 来讲解如何真正地使用Paxos算法来解决分布式一致性问题。

1. Chubby

Google Chubby是一个大名鼎鼎的分布式锁服务，GFS和Big Table等大型系统多用它来解决分布式协作、元数据存储和Master选举等一系列与分布式锁服务相关的问题。 Chubby的底层一致性实现就是以Paxos算法为基础的，这给Paxos算法的学习者提供了一个理论联系的范例，从而可以了解到Paxos算法是如何在实际工程中得到应用的。

1.1 概述

Chubby是一个面向松耦合分布式系统的锁服务，通常用于为一个由大量小型计算机构成的松耦合分布式系统提供高可用的分布式锁服务。一个分布式锁服务的目的是 允许它的客户端进程同步彼此的操作，并对当前所处环境的基本状态信息达成一致。针对这个目的，Chubby提供了粗粒度的分布式锁服务，开发人员不需要使用复杂的同步协议。 而是直接调用Chubby的锁服务接口即可实现分布式系统中多个进程之间粗粒度的同步控制，从而保证分布式数据的一致性。

Chubby的客户端接口设计非常类似于UNIX文件系统结构，应用程序通过Chubby的客户端接口，不仅能够对Chubby服务器上的整个文件进行读写操作，还能够添加对文件节点的锁控制， 并且能够订阅Chubby服务端发出的一些列文件变动的事件通知。

1.2 应用场景

在Chubby的众多应用场景中，最为典型的就是集群中服务器的Master选举。例如在Google文件系统（Google File System，GFS）中使用Chubby锁服务来实现对 GFS Master服务器的选举。而在BigTable（用于结构化数据存储与管理的大型分布式存储系统）中，同样被用于Master选举，并且借助Chubby， Master能够非常方便地的感知到其所控制的那些服务器。同时，通过Chubby，BigTable的哭护短还能够方便地定位到当前BitTable集群的Master服务器。 此外，在GFS和BigTable中，都使用Chubby来进行系统运行时元数据的存储。

1.3 设计目标

对于Chubby的设计，有的开发人员觉得作为Paxos算法的实现者，Chubby应该构建成一个包含Paxos算法的协议库，从而使应用程序能够便捷地使用Paxos算法。 但是，Chubby的最初设计者并没有选择这么做，而是将Chubby设计成一个需要访问中心化节点的分布式锁服务。

Chubby之所以设计成这样一个完整的分布式锁服务，是因为锁服务具有以下4个传统算法库所不具有的优点。

1. 对上层应用程序的侵入性更小

对于应用程序开发初期，开发人员都是从一个只需要支撑较小的负载，并且只需要保证大体可用的原型开始的，往往并没有在代码层面为分布式一致性协议的实现留有余地。 于是，集群中副本复制和Master选举等一系列提高分布式系统可用性的措施，就通过一个封装了分布式一致性协议的客户端来完成，但相比之下， 使用一个分布式锁服务的接口方式对上层应用程序的侵入性会更小。

2. 便于提供数据的发布与订阅

几乎在所有使用Chubby进行Master选举的应用场景中，都需要一种广播结果的机制，用来向所有的客户端公布当前的Master服务器。这就意味着Chubby应该 允许其客户端在服务器上进行少量数据的存储与读取————也就是对小文件的读写操作。虽然这个特性也能够通过分布式命名服务来实现，但是根据实际的经验来看， 分布式锁服务本身也非常适合提供这个功能，这一方面能够大大减少客户端依赖的外部服务，另一方面，数据的发布与订阅功能和锁服务在分布式一致性特性上是想通的。

3. 开发人员对基于锁的接口更为熟悉

对于绝大部分的开发人员来说，Chubby为其提供了一套近乎和单机锁机制一致的分布式锁服务接口，比提供一个一致性协议的库来得更为友好。

4. 更便捷地构建更可靠的服务

通常一个分布式一致性算法都需要使用Quorum机制来进行数据项值的选定。Quorum机制是分布式系统中实现数据一致性的一个比较特殊的策略，它指的是在 一个由若干个机器组成的急群众，在一个数据项值的选定过程中，要求急群众存在过半的机器达成一致，因此Quorum机制也被称作“过半机制”。 在Chubby中通常使用5台服务器来组成一个集群单元，根据Quorum机制，只要整个急群众有3台服务器是正常运行的，那么整个集群就可以对外提供正常的服务。 相反的，如果仅提供一个分布式一致性协议的客户端库，那么这些高可用性的系统部署都将交给开发人员自己来处理，提高了成本。

因此，Chubby被设计成了一个需要访问中心化节点的分布式锁服务。同时，在Chubby的设计过程中，提出了以下几个设计目标。

1. 提供一个完整的、独立的分布式锁服务，而非仅仅是一个一致性协议的客户端库：
   例如，对于Master选举同时将Master信息登记并广播的场景，应用程序只需要向Chubby请求一个锁，并且在获得锁之后向相应的锁文件写入Master信息即可， 其余的客户端就可以通过读取这个锁文件来获取Master信息。

2. 提供粗粒度的锁服务
   Chubby锁服务针对的应用场景是客户端获得锁之后会进行长时间的持有（数小时或数天），而非用于短暂获取锁的场景。针对这种应用场景，当锁服务短暂失效时 （例如服务器宕机），Chubby需要保持所有锁的持有状态，以避免持有锁的客户端出现问题。这和细粒度锁的设计方式有很大的区别，细粒度锁通常设计为锁 服务一旦失效就释放所有锁，因为细粒度锁的持有时间很短，相比而言放弃锁带来的代价较小。

3. 在提供锁服务的同时提供对小文件的读写功能
   Chubby提供对小文件的读写服务，以使得被选举出来的Master可以在不依赖额外服务的情况下，非常方便地向所有客户端发布自己的状态信息。具体的， 当一个客户端成功获取到一个Chubby文件锁而成为Master之后，就可以继续向这个文件里写入Master信息，其他客户端就可以通过读取这个文件得知当前的Master信息。

4. 高可用、高可靠
   在Chubby的架构设计中，允许运维人员通过部署多台机器（一般是5台机器）来组成一个Chubby集群，从而保证集群的高可用，基于Paxos算法的实现， 只要保证在3台正常运行的机器，整个集群对外服务就能保持可用。

5. 提供事件通知机制
   Chubby客户单需要实时地感知到Master的变化情况，当然这可以通过让客户端反复轮询来实现，但是在客户端规模不断增大的情况下，客户端主动轮询的实时性效果并不理想， 且对服务器性能和网络带宽压力都非常大。因此，Chubby需要由能力将服务端的数据变化情况（如文件内容变更）以事件的形式通知到所有订阅的客户端。

1.4 Chubby技术架构

1.4.1 系统结构

Chubby的整个系统结构主要由服务端和客户端两部分组成，客户端通过RPC调用与服务端进行通信

一个典型的Chubby集群，或称为Chubby cell，通常由5台服务器组成。这些副本服务器采用Paxos协议，通过投票的方式来选举产生一个获得过半投票的 服务器作为Master。一旦某台服务器成为了Master，Chubby就会保证在一段时期内不会再有其他服务器成为Master————这段时期称为Master租期（Master lease）。 在运行过程中，Master服务器会通过不断续租的方式来延长Master租期，而如果Master服务器出现故障，那么余下的服务器就会进行新一轮的Master选举， 最终产生新的Master服务器，开始新的Master租期。

集群中的每个服务器都维护着一份服务端数据库的副本，但在实际运行过程中，只有Master服务器才能对数据库进行写操作，而其它服务器都是使用Paxos协议从 Master服务器上同步数据库数据的更新。

现在，我们再来看下Chubby的客户端是如何定位到Master服务器的。Chubby客户端通过向记录有Chubby服务端机器列表的DNS来请求获取所有的Chubby服务器列表， 然后逐个发起请求询问该服务器是否是Master。在这个询问过程中，那些非Master的服务器，则会将当前Master所在的服务器标识反馈给客户端，这样 客户端就能够非常快速地定位到Master服务器了。

一旦客户端定位到Master服务器之后，只要该Master正常运行，那么客户端就会将所有的请求都发送到该Master服务器上。针对写请求，Chubby Master 会采用一致性协议将其广播给集群中所有的副本服务器，并且在过半的服务器接受了该写请求之后，再响应给客户端正确的应答。而对于读请求， 则不需要在集群内部进行广播处理，直接由Master服务器单独处理即可。

在Chubby运行过程中，服务器难免会发生故障。如果当前的Master服务器崩溃了，那么集群中的其他服务器会在Master租期到期后，重新开启新一轮的Master 选举。通常，进行一次Master选举大概需要花费几秒钟的时间。而如果是集群中任意一台非Master服务器崩溃，那么整个集群是不会停止工作的， 这个崩溃的服务器会在恢复之后自动加入到Chubby集群中去。新加入的服务器首先需要同步Chubby最新的数据库数据，完成数据同步之后，新的服务器就可以 加入到正常的Paxos运作流程中与其它服务器副本一起协同工作。

如果集群中的一个服务器发生崩溃并在几个小时后仍无法恢复正常，那么就需要加入新的机器，并同时更新DNS列表。Chubby服务器的更换方式非常简单， 只需要启动Chubby服务端程序，然后更新DNS上的机器列表（即使用新机器的IP地址替换老机器的IP地址）即可。在Chubby运行过程中， Master服务器会周期性地轮询DNS列表因此其很快就会感知服务器地址列表的变更，然后Master就会将集群数据库中的地址列表做相应的变更， 集群内部的其他副本服务器通过复制方式就可以获取到最新的服务器地址列表了。

1.4.2 目录与文件

Chubby对外提供了一套与Unix文件系统非常相近但是更简单的访问接口。Chubby的数据结构可以看作是一个由文件和目录组成的树，其中每一个节点都可以表示为一个 使用斜杠分割的字符串，典型的节点路径表示如下：

/ls/foo/wombat/pouch
其中，ls是所有Chubby节点所共有的前缀，代表着锁服务，是Lock Service的缩写；foo则指定了Chubby集群的名字，从DNS可以查询到由一个或多个 服务器组成该Chubby集群；剩余部分的路径wombat/pouch则是一个真正包含业务含义的节点名字，由Chubby服务器内部解析并定位到数据节点。

Chubby的命名空间，包括文件和目录，我们称之为节点（nodes，在本书后面的内容中，我们以数据节点来泛指Chubby的文件或目录）。在同一个Chubby 集群数据库中，每一个节点都是全局唯一的。和Unix系统一样，每个目录都可以包含一系列的子文件和子目录列表，而每个文件中则会包含文件内容。当然， Chubby并非模拟一个完整的文件系统，因此没有符号链接和硬连接的概念。

由于Chubby的命名结构组成了一个近似标准文件系统的视图，因此Chubby的客户端应用程序也可以通过自定义的文件系统访问接口来访问Chubby服务端数据， 比如可以使用GFS的文件系统访问接口，这就大大减少了用户使用Chubby的成本。

Chubby上的每个数据节点都分为持久节点和临时节点两大类，其中持久节点需要显式地调用接口API来进行删除，而临时节点则会在其对应的客户端会话失效后被自动删除。 （zk中的EPHEMERAL）也就是说，临时节点的生命周期和客户端会话绑定，如果该临时节点对应的文件没有被任何客户端打开的话，那么它就会被删除掉。 因此，临时节点通常可以用来进行客户端会话有效性的判断依据。

另外，Chubby上的每个数据节点都包含了少量的元数据信息，其中包括用于权限控制的访问控制列表（ACL）信息。同时，每个节点的元数据中还包括4个单调 递增的64编号，分别如下。

实例编号：实例编号用于标识Chubby创建该数据节点的顺序，节点的创建顺序不同，其实例编号也不同，因此，通过实例编号，即使针对两个名字相同的数据节点， 客户端也能够非常方便地识别出是否是同一个数据节点————因此创建时间晚的数据节点，其实例编号必定大于任意先前创建的同名节点。
文件内容编号（只针对文件）：文件内容编号用于标识文件内容的变化情况，该编号会在文件内容被写入时增加。
锁编号：锁编号用于标识节点锁状态变更情况，该编号会在节点锁从自由（free）状态转换到被持有（held）状态时增加。
ACL编号：ACL编号用于标识节点的ACL信息变更情况，该编号会在节点的ACL配置信息被写入时增加。
同时，Chubby还会标识一个64位的文件内容校验码，以便客户端能够识别出文件是否变更。

1.4.3 锁与锁序列器

在分布式系统中，锁是一个非常复杂的问题，由于网络通信的不确定性，导致在分布式系统中锁机制变得非常复杂，消息的延迟或是乱序都有可能会引起锁的失效。 一个典型的分布式锁错乱案例是，一个客户端C1获取到了互斥锁L，并且在锁L的保护下发出请求R，但请求R迟迟没有到达服务端（可能出现网络延时或 反复重发等），这时应用程序会认为该客户端进程已经失败，于是便会为另一个客户端C2分配锁L，然后再重新发起之前的请求R，并成功地应用到了服务器 上。此时，不幸的事情发生了，客户端C1发起的请求R在经过一波三折之后也到达了服务端，此时，它有可能会在不受任何锁控制的情况下被服务端处理， 从而覆盖了客户端C2的操作，于是导致系统数据出现不一致。当然，诸如此类消息接收顺序紊乱引起的数据不一致问题已经在人们对分布式计算的长期 研究过程中得到了很好的解决，典型的解决方案包括虚拟时间和虚拟同步。

在Chubby中，任意一个数据节点都可以充当一个读写锁来使用：一种是单个客户端以排他（写）模式持有这个锁，另一种则是任意数目的客户端以共享（读）模式 持有这个锁。同时，在Chubby的锁机制中需要注意的一点是，Chubby舍弃了严格的强制锁，客户端可以在没有获取任何锁的情况下访问Chubby的文件，也就是说， 持有锁F既不是访问文件F的必要条件，也不会阻止其它客户端访问文件F。

.1 锁延迟

在Chubby中，主要采用锁延迟和锁序列器两种策略来解决上面我们提到的由于消息延迟和重排序引起的分布式锁问题。其中锁延迟是一种比较简单的策略， 使用Chubby的应用几乎不需要进行任何的代码修改。具体的，如果一个客户端以正常的方式主动释放了一个锁，那么Chubby服务端将会允许其它客户端能够 立即获得该锁。而如果一个锁是因为客户端的异常情况（如客户端无响应）而被释放的话，那么Chubby服务器会为该锁保留一定的时间，我们称之为“锁延迟”（lock-delay） 在这段时间内，其它客户端无法获取这个锁。锁延迟措施能够很好地防止一些客户端由于网络闪断等原因而与服务器暂时断开的场景出现。总的来说， 该方案尽管不完美，但是锁延时能够有效地保护在出现消息延时情况下发生的数据不一致现象。

.2 锁序列器

Chubby提供的另一种方式是使用锁序列器，当然该策略需要Chubby的上层应用配合在代码中加入相应的修改逻辑。任何时候，锁的持有者都可以向Chubby请求一个锁 序列器，其包括锁的名字、锁模式（排他或共享模式），以及锁序号。当客户端应用程序在进行一些需要锁机制保护的操作时，可以将该锁序列器一并发送给服务端。 Chubby服务端接收到这样的请求后，会首先检测该序列器是否有效，以及检查客户端是否处于恰当的锁模式；如果没有通过检查，那么服务端就会拒绝该客户端请求。

1.4.4 Chubby中的事件通知机制

为了避免大量客户端轮询Chubby服务端状态所带来的压力，Chubby提供了事件通知机制。Chubby的客户端可以向服务端注册事件通知，当触发这些事件的时候， 服务端就会向客户端发送对应的事件通知。在Chubby的事件通知机制中，消息通知都是通过异步的方式发送给客户端的，常见的Chubby事件如下。

.1 文件内容变更

例如，BigTable集群使用Chubby锁来确定集群中的哪台BitTable机器是Master；获得锁的BitTable Master会将自身信息写入Chubby上对应的文件中。 BitTable集群中的其他客户端可以通过监视这个Chubby文件的变化来确定新的BitTable Master机器。

.2 节点删除

当Chubby上指定节点被删除的时候，会产生“节点删除”事件，这通常在临时节点中比较常见，可以利用该特性来间接判断该临时节点对应的客户端会话是否有效。

.3 子节点新增、删除

当Chubby上指定的节点的子节点新增或是删除时，会产生“子节点新增、删除”事件。（还有更新）

.4 Master服务器转移

当Chubby服务器发生Master转移时，会以事件的形式通知客户端。

1.4.5 Chubby中的缓存

为了提高Chubby的性能，同时也是为了减少客户端和服务端之间频繁的读请求对服务端的压力，Chubby除了提供事件通知机制之外，还在客户端中实现了缓存， 会在客户端对文件内容和元数据信息进行缓存。使用缓存机制在提高系统整体性能的同时，也为系统带来了一定的复杂性，其中最主要的问题就是应该如何保证缓存的一致性。 在Chubby中，通过租期机制来保证缓存的一致性。

Chubby缓存的生命周期和Master租期机制紧密相关，Master会维护每个客户端的数据缓存情况，并通过向客户端发送过期信息的方式来保证客户端数据的一致性。 在这种机制下，Chubby就能够保证客户端要么能够从缓存中访问到一致的数据，要么访问出错，而一定不会访问到不一致的数据。具体的，每个客户端的缓存 都有一个租期，一旦该租期到期，客户端就需要向服务端续订租期以继续维持缓存的有效性。当文件数据或元数据被修改时，Chubby服务端首先会阻塞该修改操作， 然后由Master向所有可能缓存了该数据的客户端发送缓存过期信号，以使其缓存失效，等到Master在接收到所有相关客户端针对该过期信息的应答（应答包括两类， 一类是客户端明确要求更新缓存，另一类则是客户端允许缓存租期过期）后，再继续进行之前的修改操作。

通过上面这个缓存机制的介绍，相信读者都已经明白了，Chubby的缓存数据保证了强一致性。尽管要保证严格的数据一致性对于性能的开销和系统的吞吐影响很大， 但由于弱一致性模式在实际使用过程中极容易出现问题，因此Chubby在设计之初就决定了强一致性模型。

1.4.6 会话和会话激活（KeepAlive）

Chubby客户端和服务端之间通过创建一个TCP连接来进行所有的网络通信操作，我们将这一连接称为会话（Session）。会话是有生命周期的，存在一个超时时间， 在超时时间内，Chubby客户端和服务端之间可以通过心跳检测来保持会话的活性，以使会话周期得到延续，我们将这个过程称为KeepAlive（会话激活）。如果 能够成功地通过KeepAlive过程将Chubby会话一直延续下去，那么客户端创建的句柄（引用）、锁和缓存数据等都依然有效。

1.4.7 KeepAlive请求

下面我们就重点来看看Chubby Master是如何处理客户端的KeepAlive请求的。Master在接收到客户端的KeepAlive请求时，首先会将该请求阻塞住，并等到 该客户端的当前会话租期即将过期时，才为其续租该客户端的会话租期，之后再向客户端响应这个KeepAlive请求，并同时将最新的会话租期超时时间反馈给客户端。 Master对于会话续租时间的设置，默认是12秒，但这不是一个固定的值，Chubby会根据实际的运行情况，自行调节该周期的长短。举个例子来说， 如果当前Master处于高负载运行状态的话，那么Master会适当地延长会话租期的长度，以减少客户端KeepAlive请求的发送频率。客户端在接收到来自Master的续租 响应后，会立即发起一个新的KeepAlive请求，再由Master进行阻塞。因此我们可以看出，在正常运行过程中，每一个Chubby客户端总是会有一个KeepAlive 请求阻塞在Master服务器上。

除了为客户端进行会话续租外，Master还将通过KeepAlive响应来传递Chubby事件通知和缓存过期通知给客户端。具体的，如果Master发现服务端已经触发了 针对该客户端的事件通知或缓存过期通知，那么会提前将KeepAlive响应反馈给客户端。

1.4.8 会话超时

谈到会话租期，Chubby的客户端也会维持一个和Master端近似相同的会话租期。为什么是近似相同呢？这是因为客户端必须考虑两方面的因素：一方面，KeepAlive 响应在网络传输过程中会花费一定的时间；另一方面，Master服务端和Chubby客户端存在时钟不一致性现象。因此在Chubby会话中，存在Master端会话租期和客户端本地 会话租期。

如果Chubby客户端在运行过程中，按照本地的会话租期超时时间，检测到期会话租期已经过期却尚未接收到Master的KeepAlive响应，那么这个时候，它将无法确定Master 服务端是否已经中止了当前会话，我们称这个时候客户端处于“危险状态”。此时，Chubby客户端会清空其本地缓存，并将其标记为不可用。同时，客户端还会等待一个被 称作“宽限期”的时间周期，这个宽限期默认是45秒。如果在宽限期到期前，客户端和服务端成功地进行了KeepAlive，那么客户端就会再次开启本地缓存，否则，客户端就会 认为当前会话已经过期了，从而中止本次会话。

我们再着重来看看上面提到的“危险状态”。当客户端进入上述提到的危险状态时，Chubby的客户端库会通过一个“jeopardy”事件来通知上层应用程序。如果 恢复正常，客户端同样会以一个“safe”事件来通知应用程序可以继续正常运行了。但如果客户端最终没能从危险状态中恢复过来，那么客户端会以一个“expired” 事件来通知应用程序当前Chubby会话已经超时。Chubby通过这些不同的事件类型通知，能够很好地辅助上层应用程序在不明确Chubby会话状态的情况下， 根据不同的事件类型来做出不同的处理：等待或重启。有了这样的机制保证之后，对于那些在短时间内Chubby服务不可用的场景下，客户端应用程序可以选择等待，而不是重启， 这对于那些重启整个应用程序需要花费较大代价的系统来说非常有帮助。

1.4.9 Chubby Master故障恢复

Chubby的Master服务器上运行着会话租期计时器，用来管理所有会话的生命周期。如果在运行过程中Master出现了故障，那么该计时器会停止，直到新的Master选举 产生后，计时器才会继续计时，也就是说，从旧的Master崩溃到新的Master选举产生所花费的时间将不计入会话超时的计算中，这等价于延长了客户端的会话租期。 如果新的Master在短时间内就选举产生了，那么客户端就可以在本地会话租期过期前与其创建连接。而如果Master的选举花费了较长的时间，就会导致客户端只能情况本地的缓存， 并进入宽限期进行等待。从这里我们可以看出，由于宽限期的存在，使得会话能够很好地在服务端Master转换额过程中得到维持。整个Chubby Master故障恢复过程中 服务端和客户端的交互情况：

展示了一个完整的Chubby服务端Master故障恢复过程中所触发的所有事件序列。在这整个故障恢复过程中，客户端必须使用宽限期来保证在Master转换过程完成之后， 其会话依然有效。

一开始在旧的Master服务器上维持了会话租期“lease M1”，在客户端上维持了对应的“lease C1”，同时客户端的KeepAlive请求1一直被Master阻塞着。在一段时间之后， Master向客户端反馈了KeepAlive响应2，同时开始了新的会话租期“lease M2”，而客户端在接收到该KeepAlive响应之后，立即发送了新的KeepAlive请求3，并 同时也开始了新的会话租期“lease C2”。至此，客户端和服务吨Master之间的所有交互都是正常的。但是随后，Master发生了故障，从而无法反馈客户端的KeepAlive 请求3。在这个过程中，客户端检测到会话租期“lease C2”已经过期，它会清空本地缓存，并进入宽限期。在这顿时间内，客户端无法确定Master上的会话周期 是否也已经过期，因此，它不会销毁它的本地会话，而是将所有应用程序对它的API调用都阻塞主，以避免在这个期间进行的API调用导致数据不一致现象。 同时，在客户端宽限期开始时，Chubby客户端会向上层应用程序发送一个“jeopardy”事件。一段时间后，CHubby服务端选举产生了新的Master，并为该客户端初始化 了新的会话租期“lease M3”。当客户端向新的Master发送KeepAlive请求4时，Master检测到该客户端的Master周期号已经过期，因此会在KeepAlive响应5 中拒绝这个客户端请求，并将最新的Master周期号发送给客户端。之后，客户端会携带上新的Master周期号，再次发送KeepAlive请求6给Master，最终，整个 客户端和服务端之间的会话就会再次恢复正常。

通过上面的详细介绍，不难看出，在Master转换的这段时间内，只要客户端的宽限期是够长的，那么客户端应用程序可以在没有任何察觉的情况下，实现Chubby的故障恢复， 但如果客户端的宽限期设置得比较短，那么Chubby客户端就会丢弃当前会话，并将这个异常情况通知给上层应用程序。

一旦客户端与新的Master建立上连接之后，客户端和Master之间会通过互相配合来实现对故障的平滑恢复。新的Master会设法将上一个Master服务器的内存状态构造出来。 具体的，由于本地数据库记录了每个客户端的会话信息，以及其持有的锁和临时文件等信息，因此Chubby会通过读取本地磁盘上的数据来恢复一部分状态。 总的来讲，一个新的Chubby Master服务器选举产之后，会进行如下几个主要处理。

.1 确定Master周期

Master周期用来唯一标识一个Chubby集群的Master统治轮次，以便区分不同的Master。一旦新的Master周期确定下来之后，Master就会拒绝所有携带其他Master 周期编号的客户端请求，同时告知其最新的Master周期编号，例如上述提到的KeepAlive请求4。需要注意的一点是，只要发生Master重新选举，就一定会产生新的 Master周期，即使是在选举前后Master都是同一台机器的情况下也是如此。

.2 新Master能够立即对客户端的Master寻址请求进行响应，但是不会立即开始处理客户端会话相关的请求操作。

.3 Master根据本地数据库中存储的会话和锁信息，来构建服务器的内存状态。

.4 到现在为止，Master已经能够处理客户端的KeepAlive请求了，但依然无法处理其他会话相关的操作。

.5 Master会发送一个“Master故障切换”事件给每一个会话。

客户端接收到这个事件后，会清空它的本地缓存，并警告上层应用程序可能已经丢失了别的事件，之后再向Master反馈应答。

.6 此时，Master会一直等待客户端的应答，知道每一个会话都应答了这个切换事件。

.7 在Master接收到了所有客户端的应答之后，就能够开始处理所有的请求操作了。

.8 如果客户端使用了一个在故障切换之前创建的引用，Master会重新为其创建这个引用的内存对象，并执行调用。

而如果该引用在之前的Master周期中已经被关闭了，那么它聚不能在这个Master周期内再次被重建了————这一机制就确保了即使由于网络原因使得Master接收到那些延迟或重发的网络数据包， 也不会错误地重建一个已经关闭的引用。

1.5 Paxos协议实现

Chubby服务端的基本架构大致分为三层：

最底层是容错日志系统（Fault-Tolerant Log），通过Paxos算法能够保证集群中所有机器上的日志完全一致，同时具有较好的容错性。
日志层之上是Key-value类型的容错数据库（Fault-Tolerant DB），其通过下层的日志来保证一致性和容错性。
存储层之上就是Chubby对外提供的分布式锁服务和小文件存储服务。

Paxos算法的作用就在于保证集群内各个副本节点的日志能够保持一致。Chubby事务日志中的每一个Value对应Paxos算法中的一个Instance，由于Chubby需要对外提供 不间断的服务，因此事务日志无限增长，于是在整个Chubby巡行过程中，会存在多个Paxos Instance。同时，Chubby会为每一个Paxos Instance都按序分配一个全局唯一 的Instance编号，并将其顺序写入到事务日志中去。
在多Paxos Instance的模式下，为了提升算法执行的性能，就必须选举出一个副本节点作为Paxos算法的主节点，以避免因为每一个Paxos Instance都提出提案而陷入多个Paxos Round 并存的情况。同时，Paxos会保证在Master重启或出现故障而进行切换的时候，允许出现短暂的多个Master共存却不影响副本之间的一致性。

在Paxos中，每一个Paxos Instance都需要进行一轮或多轮“Prepare->Promise->Propose->Accept”这样完整的二阶段请求过程来完成对一个提案值的选定， 而多个Instance之间是完全独立的，每个Instance可以自己决定每一个Round的序号，仅仅只需要保证在Instance内部不会出现序号重复即可。为了在保证正确性的前提下尽可能 地的提高算法运行性能，可以让多个Instance共用一套序号分配机制，并将“Prepare->Promise”合并为一个阶段，具体做法如下。

当某个副本节点通过选举成为Master后，就会使用新分配的编号N来广播一个Prepare消息，该Prepare消息会被所有未达成一致的Instance和目前还未开始的Instance共用。
当Acceptor接收到Prepare消息后，必须对多个Instance同时做出回应，这通常可以通过将反馈信息封装在一个数据包中来实现。假设最多允许K个Instance同时进行提案值的选定，那么：

当前至多存在K个未达成一致的Instance，将这些未决的Instance各自最后接收的提案值（若该提案尚未接收任何值。则使用null来代替）封装进一个数据包，并作为Promise消息返回。 同时，判断N是否大于当前Acceptor的highestPromisedNum值（当前已经接受的最大提案编号值），如果大于该值的话，那么就标记这些未决Instance和 所有未来的Instance的highestPromisedNum值为N————这样，这些未决Instance和所有未来Instance都不能再接受任何编号小于N的提案。

然后Master就可以对所有未决Instance和所有未来Instance分别执行“Propose->Accept”阶段的处理。值得注意的是，如果当前Master能够一直稳定运行的话， 那么在接下来的算法运行过程中，就不再需要进行“Prepare->Promise”的处理了。但是，一但Master发现Acceptor返回了一个Reject消息，说明集群中存在另一个Master， 并且试图使用更大的编号发送了Prepare消息。碰到这种情况，当前Master就需要重新分配新的提案编号，并再次进行“Prepare->Promise”阶段的逻辑处理。

利用上述改进的Paxos算法，在Master稳定运行的情况下，只需要使用同一个编号来依次执行每一个Instance的“Promise->Accept”阶段逻辑处理。在每个Instance 的运行过程中，一旦接收到多数派的Accept反馈后，就可以将对应的提案值写入本地事务日志并广播COMMIT消息给集群中的其他副本节点，其他副本节点在接收到这个COMMIT消息之后也会 将提案值写入到事务日志中。如果某个副本节点因为宕机或者网络原因没有接收到COMMIT消息，可以主动向集群中的其他副本节点进行查询。因此，我们可以看到，在Chubby的Paxos 算法的实现中，只要维持集群中存在多数派的机器能够正常运行，即使其他机器在任意时刻发生宕机，也能保证已经提交的提案的安全性。

至此，我们已经实现了一套满足一致性的日志副本，在此基础上就可以在上层实现一个一致的状态机副本，即容错数据库层。初期，使用Berkeley DB作为容错数据库， 这个数据库底层实现了B树数据结构，即存储大量数据的HashMap，将每一个数据节点的节点路径名作为键，同时按照节点路径名进行排序，这就能够使得兄弟节点在排序顺序中相邻， 方便对数据节点的检索。

后来，Chubby自己实现了一套更为简单的、基于日志预写和数据快照技术的底层数据复制组件。

数据快照和事务日志回放机制：集群中的某台机器在宕机重启以后，为了恢复状态机的状态，最简单的方法就是将已经记录的所有事务日志重新执行一遍。但这 会有一个明显的问题，就是如果机器上的事务日志已经积累了很多，那么恢复的时间就会非常长，因此需要定期对状态机数据做一个数据快照并将其存入磁盘， 然后就可以将数据快照点之前的事务日志清除。

通常副本节点在进行宕机后的恢复过程中，会出现磁盘未损坏和损坏两种情况。前者最为常见，一般通过磁盘上保存的数据库快照和事务日志就可以恢复到之前某个时间点的状态， 之后再向集群中其他正常运行的副本节点索取宕机后缺失的部分数据变更记录，这样即可实现宕机后的数据恢复。另外一种则是磁盘损坏，无法直接从本地数据恢复的情况， 需要从其它副本节点索取全部的状态数据。

副本节点在完成宕机重启之后，为了安全起见，不会立即参与Paxos Instance流程，而是需要等待检测到K个Paxos Instance流程陈宫完成之后才能开始参与————这样就能够保证 新分配的提案编号不会和自己以前发过的重复。

最后，为了提高整个集群的性能，还有一个改进之处在于：得益于Paxos算法的容错机制，只要任意时刻保证多数派的机器能够正常运行，那么在宕机瞬间未能真正写入到 磁盘上（只有当真正调用操作系统Flush接口后，数据才能被真正写入物理磁盘中）的那一小部分事务日志也可以通过从其它正常运行的副本上复制来进行获取，因此 不需要实时地进行事务日志的Flush操作，这可以极大地提高事务写入的效率。

1.6 Hypertable

1.6.1 概述

使用C++开发的开源、高性能、可伸缩的数据库。只支持增删改查，不支持事务。

支持对大量并发请求的处理。
支持对海量数据的管理。
扩展性良好，在保证可用性的前提下，能够通过随意添加集群中的机器来实现水平扩容。
可用性极高，具有非常好的容错性，任何节点的失效，既不会造成系统瘫痪也不会影响数据的完整性。

1.6.2 算法实现

选举Master是根据所有服务器上事务日志的更新时间来确定哪个服务器的数据最新，那么被选举的可能性就越大。

3 小结

列举了使用Paxos算法的工业实践应用，更好的理解Paxos算法。

前章提要：
上章我们讲到分布式往往会在系统可用性和数据一致性之间反复权衡，于是就产生了一系列的一致性协议（为什么没有可用性协议？博主认为，数据才是王道）。

1. 2PC和3PC

在分布式系统总，每一个机器节点虽然都能够明确地知道自己在进行事务操作过程中的结果是成功或失败，但却无法直接获取到其他分布式节点的操作结果。 因此，当一个事务操作需要跨越多个分布式节点的时候，为了保持事务处理的ACID特性（某个节点为单位），就需要引入一个称为“协调者（Coordinator）” 的组件来统一调度所有分布式节点的执行逻辑，这些被调度的分布式节点被称为“参与者（Participant）”。

Coordinator负责调度Participant的行为，并最终决定这些Participant是否要把事务真正的提交。基于这个思想，衍生除了二阶段提交和三阶段提交两种协议， 在本节中，我们将重点对这两种分布式事务中涉及的一致性协议进行讲解。

1.1 2PC

2PC是Two-Phase Commit的缩写，即二阶段提交，是计算机网络尤其是在数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务处理过程中能保持 原子性和一致性而设计的算法。

1.1.1 阶段一：提交事务请求

事务询问：协调者向所有的参与者发送事务内容，询问是否可以执行事务提交曹组，并开始等待各参与者的响应。
执行事务：各参与者节点执行事务操作，并将Undo和Redo信息记入事务日志中。
各参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作，那么反馈给协调者Yes响应，表示事务可以执行；如果参与者没有成功执行事务， 那么就反馈给协调者No响应，表示事务不可以执行。
由于上面讲述的内容在形式上近似是协调者组织各参与者对一次事务操作的投票表态过程，因此二阶段提交协议的阶段一页被称为“投票阶段”，即各参与者投票 表明是否要继续执行接下去的事务提交操作。

1.1.2 阶段二：执行事务提交

正常情况，包含以下两种可能：

.1 可能一：执行事务提交：假如协调者从所有的参与者的反馈都是Yes响应，那么就会执行事务提交。

.1.1 发送提交请求：协调者向所有参与者发出Commit请求。

.1.2 事务提交：参与者接收到Commit请求后，会正式执行事务提交操作，并在完成提交之后释放整个事务执行期间占用的事务资源。

.1.3 反馈事务提交结果：参与者在完成事务提交之后，向协调者发送Ack消息。

.1.4 完成事务：协调者接收到所有参与者反馈的Ack消息后，完成事务。

.2 可能二：执行事务中断：假如任何一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。

.2.1 发送回滚请求：协调者向所有参与者节点发出Rollback请求。

.2.2 事务回滚：参与者接收到Rollback请求后，会利用其在阶段一记录的Undo信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。

.2.3 反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送Ack消息。

.2.4 中断事务：协调者接收到所有参与者反馈的Ack消息后，完成事务中断。

以上就是二阶段提交过程中，前后两个阶段分别进行的处理逻辑。简单地讲，二阶段提交将一个事务的处理分成了投票和执行两个阶段，其核心是对每个事务 都采用了先尝试后提交的处理方式，因此也可以将二阶段提交看作一个强一致性的算法。

1.1.3 优缺点

原理简单，实现方便；但是同步阻塞、单点问题、数据不一致、太过保守。

.1 同步阻塞：在事务的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，也就是说，各个参与者在登台其他参与者响应的过程中，

将无法进行其他任何操作。

.2 单点问题：一旦协调者出现问题，整个二阶段提交流程将无法运转，更为严重的是，如果协调者是在阶段二中出现问题的话，

那么其他参与者将会一直处于锁定事务资源的状态中，而无法继续完成事务操作。

.3 数据不一致：当协调者向所有参与者发送Commit请求之后，发生了协调者在尚未发送完Commit请求之前自身发生了崩溃，

导致最终只有部分参与者收到了Commit请求。于是，其他没有收到Commit请求的参与者没有进行事务提交，而收到Commit请求的参与者会进行事务提交，最终数据不一致。

.4 太过保守：任何一个节点的失败都会导致整个事务的失败。

1.2 3PC

研究者在二阶段提交协议的基础上进行了改进，提出了三阶段提交协议。
3PC是Three-Phase Commit的缩写，将二阶段提交协议的“提交事务请求”过程分为两个，形成了CanCommit、PreCommit和DoCommit。

1.2.1 阶段一：CanCommit

.1 事务询问：协调者向所有的参与者发送一个包含事务内容的CanCommit请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应。

.2 各参与者向协调者反馈响应：如果自身可以顺序执行事务，反馈Yes响应，并进入预备状态，否则反馈No响应。

1.2.2 阶段二：PreCommit

.1 执行事务预提交：假如协调者从所有参与者获得的反馈都是Yes响应。

.1.1 发送预提交请求：协调者向所有参与者节点发出PreCommit的请求，并进入Prepared阶段。

.1.2 事务预提交：参与者接收到PreCommit请求后，会执行事务操作，并将Undo和Redo信息记录到事务日志中。

.1.3 各参与者向协调者反馈事务执行的响应：如果参与者成功执行了事务操作，那么就会反馈给协调者Ack响应，同时等待最终的指令：提交（commit）或中止（abort）。

.2 中断事务：假如任何一个参与者向协调者反馈了No响应，或等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。

.2.1 发送中断请求：协调者向所有参与者节点发出abort请求。

.2.2 中断事务：无论是收到来自协调者的abort请求，或者是在等待协调者请求过程中出现超时时，参与者都会中断事务。

1.2.3 阶段三：DoCommit

.1 可能一：执行提交

.1.1 发送提交请求：协调者从“预提交”状态转换到“提交”状态，并向所有的参与者发送DoCommit请求。

.1.2 事务提交：参与者接收到DoCommit请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。

.1.3 反馈事务提交结果：参与者在完成事务提交之后，向协调者发送Ack消息。

.1.4 完成事务：协调者接收到所有参与者反馈的Ack消息后，完成事务。

.2 可能二：中断事务

.2.1 发送中断请求：协调者向所有参与者节点发送abort请求。

.2.2 事务回滚：参与者接收到abort请求后，利用Undo信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。

#####.2.3 反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送Ack消息。

#####.2.4 中断事务：协调者接收到所有参与者反馈的Ack消息后，中断事务。

需要注意的是，一旦进入阶段三，可能会存在以下两种故障：

协调者出现问题。
协调者和参与者之间的网络出现故障。 无论出现哪种情况，参与者都会在等待超时之后，继续进行事务提交。即，默认为允许提交。

1.2.3 优缺点

降低参与者的阻塞范围，出现单点故障后继续达成一致；但是在参与者接收到PreCommit消息后，如果协调者所在的节点和参与者无法正常通信， 该参与者仍然会进行事务的提交，这必然出现数据不一致性。

2. Paxos算法

我们将重点讲解另一种非常重要的分布式一致性协议：Paxos。Paxos算法是一种基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式 一致性问题最有效的算法之一。

我们现在已经知道，在常见的分布式系统中，总会发生诸如机器宕机或网络异常等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中， 快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常都不会破坏整个系统的一致性。

2.1 追本溯源

1982年，Lamport与另两人提出了一种计算容错理论。在理论描述过程中，为了将要所描述的问题形象的表达出来，Lamport设想出了下面这样一个场景：

拜占庭帝国有许多支军队，不同军队的将军之间必须制定一个统一的行动计划，从而做出进攻或者撤退的决定，同时，各个将军在地理上都是被 分割开来的，只能依靠军队的通讯员来进行通讯。然而，在所有的通讯员中可能会存在叛徒，这些叛徒可以任意篡改消息，从而达到欺骗将军的目的。

这就是著名的“拜占庭将军问题”。从理论上来说，在分布式计算领域，试图在异步系统和不可靠的通道上来达到一致性状态是不可能的，因此在堆一致性的研究 过程中，都往往假设信道是可靠地。而事实上，大多数系统都是部署在同一个局域网中的，因此消息被篡改的情况非常罕见，另一方面，由于硬件和网络原因而 造成的消息不完整问题，只需一套简单的校验算法即可避免——因此，在实际工程实践中，可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被 篡改的。那么，在这种情况下需要什么样的算法来保证一致性呢？

Lamport在1990年提出了一个理论上的一致性解决方案，同时给出了严格的数学证明。鉴于之前采用故事类比的方式成功的阐述了“拜占庭将军问题”，因此这次Lamport 同样用新娘库地设想除了一个场景来描述这种一致性算法需要解决的问题，及其具体的解决过程：

在古希腊有一个叫Paxos的小岛，岛上采用议会的形式来通过法令，议会中的议员通过信使进行消息的传递。值得注意的是，议员和信使都是兼职的， 他们随时有可能会离开议会厅，并且信使可能会重复的传递消息，也可能一去不复返。因此，议会协议要保证在这种情况下法令仍然能够正确的产生， 并且不会出现冲突。

这就是兼职议会，而Paxos算法名称的由来也是取自提到的Paxos小岛。

2.2 Paxos算法详解

Paxos作为一种提高分布式系统容错性的一致性算法，一直以来总是被很多人抱怨其算法理论太难理解。

2.2.1 问题描述：

假设有一组可以提出提案的进程集合，那么对于一个一致性算法来说需要保证以下几点：

在这些被提出的提案中，只有一个会被选中。
如果没有提案被提出，那么就不会有被选定的提案。
当一个提案被选定后，进程应该可以获取被选定的提案信息。

对于一致性来说，安全性需求如下：

只有被提出的提案才能被选定。
只能由一个值被选定。
如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个。

在对Paxos算法的讲解过程中，我们不去精确地定义其活性需求，从整体上来说，Paxos算法的目标就是要保证最终有一个提案会被选定，当提案被选定后， 进程最终也能获取到被选定的提案。

在该一致性算法中，有三种参与角色，我们用Proposer、Acceptor、Learner来表示，在具体的实现中，一个进程可能充当不止一种角色，在这里我们并 不关心进程如何映射到各种角色。假设不同参与者之间可以通过收发消息来进行通信，那么：

每个参与者以任意的速度执行，可能会因为出错而停止，也可能会重启。同时，即使一个提案被选定后，所有的参与者也都有可能失败或重启，因此除非 哪些失败或重启的参与者可以记录某些信息，否则将无法确定最终的值。
消息在传输过程中可能会出现不可预知的延迟，也可能会重复或丢失，但是消息不会被损坏。

2.2.2 提案的选定

要选定一个唯一提案的最简单方式莫过于只允许一个Accpetor存在，这样的话，Proposer只能发送提案给该Accpetor，Acceptor会选择它接收到的第一个 提案作为被选定的提案。这种解决方式尽管实现起来非常简单，但是却很难让人满意，因为一旦这个Accpetor出现问题，那么整个系统就无法工作了。
因此，应该寻找一种更好的解决方式，例如可以使用多个Acceptor来避免Accpetor的单点问题。现在我们就来看看，在存在多个Acceptor的情况下，如何 进行提案的选取：Proposer向一个Acceptor集合发送提案，同样，集合中的每个Acceptor都可能会批准该提案，当有足够多的Acceptor批准这个提案的时候， 我们就可以认为该提案被选定了。那么，什么是足够多呢？我们假定足够多的Acceptor是整个Acceptor集合的一个子集，并且让这个集合大得可以包含Acceptor 集合中的大多数成员，因为任意炼哥包含大多数Acceptor的子集至少有一个公共成员。另外我们再规定，每一个Acceptor最多只能批准一个提案，那么就能 保证只有一个提案被选定了。

2.2.3 推导过程

在没有失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案，这就暗示了如下的需求。

P1：一个Acceptor必须批准它收到的第一个提案。

上面这个需求就引出了另外一个问题：如果有多个提案被不同的Proposer同时提出，这可能会导致虽然每个Acceptor都批准了它收到的第一个提案，但是没有一个 提案是由多数人批准的。可能会现以下两种情况

Acceptor接收的提案数量相同，此时无法选定最终的提案了。
因此，在P1的基础上，需要再加上一个提案被选定需要由半数以上的Acceptor批准的需求暗示着一个Acceptor必须能够批准不止一个提案。在这里，我们使用一个全局的编号 （这种全局唯一编号的生成并不是Paxos算法需要关注的地方，就算法本身而言，其假设当前已经具备这样的外部组件能够生成一个全局唯一的编号）来标识每一个 被Acceptor批准的提案，当一个具有某Value值的提案被半数以上的Acceptor批准后，我们就认为该Value被选定了，此时我们也认为该提案被选定了。需要注意的是， 此处讲到的提案和Value不是同一个概念了，提案变成了由编号和Value组成的组合体，因此我们以“[编号，Value]”来表示一个提案。（编号多少的提案被选中了，其中value是多少） 根据上面讲到的内容，我们虽然允许多个提案被选定，但同时必须保证所有被选定的提案都具有相同的Value值——这是一个关于提案Value的约定，结合提案 的编号，该约定可以定义如下：

P2：如果编号为M0、Value值为V0的提案（即[M0、V0]）被选定了，那么所有比编号M0更高的，且被选定的提案，其Value值必须也是V0。

因为提案的编号是全序的，条件P2就保证了只有一个Value值被选定这一关键安全性属性。同时，一个提案要被选定，其首先必须至少一个Acceptor批准，因此 我们可以通过满足如下条件来满足P2。

P2a：如果编号为M0、Value值为V0的提案（即[M0、V0]）被选定了，那么所有比编号M0更高的，且被Acceptor批准的提案，其Value值必须也是V0。

至此，我们仍然需要P1来保证提案会被选定，但是因为通信是异步的，一个提案可能在某个Acceptor还未收到任何提案时就被选定了。

如上图，在Acceptor1没有接收到任何提案的情况下，其他4个Acceptor已经批准了来自Proposer2的提案[M0,V1]，而此时，Proposer1产生了一个具有其他Value值的、 编号更高的提案[M1,V2]，并发送给了Acceptor1。根据P1，就需要Acceptor1批准该提案，但是这与P2a矛盾，因此如果要同时满足P1和P2a，需要对P2a进行如下强化：

P2b：如果一个提案[M0,V0]被选定后，那么之后任何Proposer产生的编号的提案，其Value值都为V0。

因为一个提案必须在被Proposer提出后才能被Acceptor批准，因此P2b包含了P2a，进而包含了P2。于是，接下去的重点就是论证P2b成立即可：

假设某个提案[M0,V0]已经被选定了，证明任何编号Mn > M0的提案，其Value值都是V0。

2.2.4 数学归纳法证明

略过。

2.2.5 Proposer生成提案

对于一个Proposer来说，获取哪些已经被通过的提案远比预测未来可能会被通过的提案来得简单。因此，Proposer在产生一个编号为Mn的提案时， 必须要知道当前某一个将要或已经被半数以上Acceptor批准的、编号小于Mn但为最大编号的提案。并且，Proposer会要求所有的Acceptor都不要 再批准任何编号小于Mn的提案——这就引出了如下的提案生成算法。

.1 Proposer选择一个新的提案编号Mn，然后向某个Acceptor集合的成员发送请求，要求该集合中的Acceptor做出如下回应。
向Proposer承诺，保证不再批准任何编号小于Mn的提案。
如果Acceptor已经批准过任何提案，那么其就向Proposer反馈当前该Acceptor已经批准的编号小于Mn但为最大编号的那个提案的值。
我们将该请求称为编号为Mn的提案的Prepare请求。

.2 如果Proposer收到了来自半数以上的Acceptor的响应结果，那么它就可以产生编号为Mn、Value值的Vn的提案，这里的Vn是所有响应中编号最大的提案的Value值。
当然还存在另一种情况，就是半数以上的Acceptor都没有批准过任何提案，即响应不包含任何的提案，那么此时Vn值就可以 由Proposer任意选择。

在确定提案之后，Proposer就会将该提案再次发送给某个Acceptor集合，并期望获得它们的批准，我们称此请求为Accept请求。需要注意的一点是， 此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合——这点相信读者也能够明白，任意两个半数以上的Acceptor集合，必定 包含至少一个公共Acceptor。

2.2.6 Acceptor批准提案

在上文中，我们已经讲解了Paxos算法中Proposer的处理逻辑，下面我们来看看Acceptor是如何批准提案的。

根据上面的内容，一个Acceptor可能会收到来自Proposer的两种请求，分别是Prepare请求和Accept请求，对这两类请求做出相应的条件分别如下。

Prepare请求：Acceptor可以在任何时候响应一个Prepare请求。
Accept请求：在不违背Accept现有承诺的前提下，可以任意响应Accept请求。因此，对Acceptor逻辑处理的约束条件，大体可以定义如下。
P1a：一个Acceptor只要尚未响应过任何编号大于Mn的prepare请求，那么它就可以接受这个编号为Mn的提案。

从上面这个约束条件中，我们可以看出，P1a包含了P1。同时，值得一提的是，Paxos算法允许Acceptor忽略任何请求而不用担心破坏其算法的安全性。

2.2.7 算法优化

在上面的内容中，我们分别从Proposer和Acceptor对提案的生成和批准两方面来讲解了Paxos算法在提案选定过程中的算法细节，同时也在提案的编号全局唯一 的前提下，获得了一个满足安全性需求的提案选定算法，接下来我们再对这个初步算法做一个小优化。尽可能地忽略Prepare请求：

假设一个Acceptor收到了一个编号为Mn的prepare请求，但此时该Acceptor已经对编号大于Mn的prepare请求做出了响应，因此它肯定不会再批准 任何新的编号为Mn的提案，那么狠显然，Acceptor就没有必要对这个Prepare请求做出响应，于是Acceptor可以炫册忽略这样的Prepare请求。同时 Acceptor也可以忽略掉那些它已经批准过的提案的Prepare请求。

通过这个优化，每个Acceptor只需要记住它已经批准的提案的最大编号以及它已经做出Prepare请求响应的提案的最大编号，以便在出现故障或节点重启的情况下， 也能保证P2c的不变性。而对于Proposer来说，只要它可以保证不会产生具有相同编号的提案，那么就可以丢弃任意的提案以及它所有的运行时状态信息。

2.2.8 算法陈述

.1 阶段一：

Proposer选择一个提案编号Mn，然后向Acceptor的某个超过半数的子集成员发送编号为Mn的Prepare请求。
如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应的所有Prepare请求的编号，那么它就会将它已经批准过的最大编号的提案 作为响应反馈给Proposer，同时Acceptor会承诺不会再批准任何编号小于Mn的提案。
举个例子来说，假定一个Acceptor已经响应过的所有Prepare请求对应的提案编号分别为1、2、…、5和7，那么该Acceptor在接收到一个编号为8的 Prepare请求后，就会将编号为7的提案作为响应反馈给Proposer。

.2 阶段二：

如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个针对[Mn，Vn]提案的Accept请求给Acceptor。 注意，Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值。
如果Acceptor收到这个针对[Mn，Vn]提案的Accep请求，只要改Acceptor尚未对编号大于Mn的Prepare请求做出响应，它就可以通过这个提案。
当然，在实际运行过程中，每一个Proposer都有可能会产生多个提案，但只要每个Proposer都遵循如上所述的算法运行，就一定能够保证算法执行的正确性。 值得一提的是，每个Proposer都可以在任意时刻丢弃一个提案，哪怕针对该提案的请求和响应在提案被丢弃后会到达，但根据Paxos算法的一系列规约，依然可以保证 其在提案选定上的正确性，事实上，如果某个Proposer已经在试图 生成编号更大的提案，那么丢弃一些旧的提案未尝不是一个好的选择。 因此，如果一个Acceptor因为已经收到过更大编号的Prepare请求而忽略某个编号更小的Prepare或者Accept请求，那么它也应当通知其对应的Proposer， 以便该Proposer也能够将该提案进行丢弃——这和上面“算法优化”部分中提到的提案丢弃是一致的。

2.2.9 提案的获取

在上文中，我们已经介绍了如何来选定一个提案，下面我们再来看看如何让Learner获取提案，大体可以有以下几种方案。

.1 方案一：

Learner获取一个已经被选定的提案的前提是，该提案已经被半数以上的Acceptor批准。因此，最简单的做法就是一旦Acceptor批准了一个提案，就将该 提案发送给所有的Learner。
很显然，这种做法虽然可以让Learner尽快地获取被选定的提案，但是却需要让每个Acceptor与所有的Learner逐个进行一次通信，通信的次数至少为二者个数的乘积。

.2 方案二：

另一种可行的方案是，我们可以让所有的Acceptor将它们对提案的批准情况，统一发送给一个特定的Learner（下文中我们将这样的Learner称为“主Learner”）， 在不考虑拜占庭奖金问题的前提下，我们假定Learner之间可以通过消息通信来互相感知提案的选定情况。基于这样的前提，当主learner被通知一个提案 已经被选定时，它会负责通知其它的Learner。

在这种方案中，Acceptor首先会将得到批准的提案发送给主Learner，再由其同步给其他Learner，因此较方案一而言，方案二虽然需要多一个步骤才能将 提案通知到所有的Learner，但其通信次数却大大减少了，通常只是Acceptor和Learner的个数总和。但同时，该方案引入了一个新的不稳定因素：主Learner随时可能出现故障。

.3 方案三：

在讲解方案二的时候，我们提到，方案二最大的问题在于主Learner存在单点问题，即主Learner随时可能出现故障。因此，对方案二进行改进，可以将主Learner的范围扩大， 即Acceptor可以将批准的提案发送给一个特定的Learner集合，该集合中的每个Learner都可以在一个提案被选定后通知所有其他的Learner。 这个Learner集合中的Learner个数越多，可靠性就越好，但同时网络通信的复杂度也就越高。

2.2.10 通过选取主Proposer保证算法的活性

根据前面的内容坚决，我们已经基本了解Paxos算法的核心逻辑，下面我们再来看看Paxos算法在实际运作过程中的一些细节。假设存在这样一种极端情况， 有两个Proposer依次提出了一系列编号递增的议案，但是最终都无法被选定，具体流程如下：

Proposer P1提出了一个编号为M1的提案，并完成了上述阶段一的流程。但与此同时，另外一个Propoesr P2提出了一个编号为M2的提案，同样也完成了 阶段一的流程，于是Acceptor已经承诺不再批准编号小于M2的提案了。因此，当P1进入阶段二的时候，其发出的Accept请求将被Acceptor忽略， 于是P1再次进入阶段一并提出了一个编号为M3的提案，而这又导致P2在第二阶段的Accept请求被忽略，以此类推，提案的选定过程将陷入死循环。

为了保证Paxos算法流程的可持续性，以避免陷入上述提到的“死循环”，就必须选择一个主Proposer，并规定只有主Proposer才能提出议案。这样一来， 只要主Proposer和过半的Acceptor能够正常进行网络通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准。当然，如果Proposer发现当前 算法流程中已经有一个编号更大的提案被提出或正在接受批准，那么它会丢弃当前这个编号较小的提案，并最终能够选出一个编号足够大的提案。因此， 如果系统中有足够多的组件（包括Propsoer、Acceptor和其他网络通信组件）能够正常工作，那么通过选择一个主Proposer，整套Paxos算法流程就能够保持活性。

3 小结

2PC和3PC：

1. 牧师分别问新郎和新娘：你是否愿意……不管生老病死……（投票阶段）。
2. 当新郎和新娘都回答愿意后（锁定一生的资源，只要有一个没有反应，这场结婚就失败）。（投票阶段）
3. 牧师就会说：我宣布你们……（执行阶段）。

存在的问题：

1. 阻塞问题：如果新郎回答原意，新娘没反应，则整个结婚就阻塞。（投票阶段之后增加眼神交流阶段（3PC的额外阶段），之后才真正承诺一生一世不分离即锁定资源）。
2. 单点问题：如果牧师没反应，整个结婚就失败。（3PC的超时机制，给牧师5秒反应时间）

主要从协议设计和原理实现角度详细讲解了二阶段提交协议、三阶段提交协议和Paxos这三种典型的一致性算法。其中二阶段提交协议解决了分布式事务的原子性问题， 保证了分布式事务的多个参与者要么都执行成功，要么都执行失败。但是，在二阶段解决部分分布式事务问题的同时，依然存在一些难以解决的诸如同步阻塞、 无限期等待问题。三阶段提交协议则是在二阶段提交协议的基础上，添加了PreCommit过程，从而避免了二阶段提交协议中的无限期等待问题。而Paxos算法支持 分布式节点角色之间的轮换，这极大地避免了分布式单点的出现，因此Paxos算法既解决了无限期等待问题，是目前来说最优秀的分布式一致性协议之一。

1. 从集中式到分布式

1.1 集中式的特点

所谓的集中式系统就是指由一台或多台主计算机组成中心节点，数据集中存储于这个中心节点，并且整个系统的所有业务单元都部署在这个中心节点上， 系统的所有功能均由其集中处理。也就是说，在集中式系统中，每个终端或客户端机器仅仅负责数据的录入和输出，而数据的存储与控制处理完全 交由主机来完成。

最大的特点就是部署结构简单。由于集中式系统往往基于底层性能卓越的大型主机，因此无须考虑如何对服务进行多个节点的部署，也就不用考虑多个 节点之间的分布式协作问题。

1.2 分布式的特点

分布式系统是一个硬件或者软件组成分布在不同的网络计算上，彼此之间仅仅通过消息传递进行通信和协调的系统。

一个标准的分布式系统在没有任何特定业务逻辑约束的情况下，都会有如下几个特征：

分布性：分布式系统中的多台计算机在空间上随意分布。
对等性：分布式系统中的计算机没有主/从之分，既没有控制整个系统的主机，也没有被控制的从机，组成分布式系统的所有计算机节点都是对等的。 副本（Replica）是分布式系统最常见的概念之一，指的是分布式系统对数据和服务提供一种冗余方式。在常见的分布式系统中，为了对外提供高可用的服务， 我们往往会对数据和服务进行副本处理。不同的节点上持久化同一份数据，当某一个节点上存储的数据丢失时，可以从副本上读取到该数据，另一类副本是 服务副本，指多个节点提供同样的服务，每个节点都有能力接收来自外部的请求并进行相应的处理。
并发性：同一个分布式系统中的多个节点，可能会并发地操作一些共享的资源，诸如数据库或分布式存储等，如何准确并高效地协调分布式并发操作也成为了分布式 系统架构与设计中最大的挑战之一。
缺乏全局时钟：一个典型的分布式系统是由一系列在空间上随意分布的多个进程组成的，具有明显的分布性，这些进程之间通过交换下次来进行相互通信。 因此，在分布式系统中，很难定义两个时间的顺序，原因就是因为分布式系统缺乏一个全局的时钟序列控制。
故障总是会发生：组成分布式系统的所有计算机，都有可能发生任何形式的故障。任何在设计阶段考虑到的异常情况，一定会在系统实际运行中发生！

##1.3 分布式环境的各种问题

1.3.1 通信异常

分布式引入了网络因素，而由于网络本身的不可靠性，因此每次网络通信都会伴随网络不可用的风险，网络光纤、路由器和DNS等。因此消息丢失和消息延迟变得非常普遍。

1.3.2 网络分区

当网络由于发生异常情况，导致分布式系统中部分节点之间的网络延时不断增大，最终导致组成分布式系统的所有节点中，只有部分节点之间能够正常通信， 而另一些节点则不能——我们将这个现象称为网络分区。网络分区出现时，分布式系统会出现局部小集群，在极端情况下，这些局部小集群会独立完成原本 需要整个分布式系统才能完成的功能，包括对数据的事务处理，这就对分布式一致性提出了非常大的挑战（某个复杂业务原本需要多个机器完成，现在被一个机器 执行）。

1.3.3 三态

分布式系统的每一次请求与响应，存在特有的“三态”概念，即成功、失败与超时。超时的现象，通常有以下两种情况：

由于网络原因，请求并没有被成功地发送到接收方，在发送过程就发生了消息丢失现象。
请求成功的被接收方接收后，并进行了处理，但是在将响应反馈给发送方的过程中，发生了消息丢失现象。（rabitMQ的解决方案是，消费者（接收方）开始处理消息前发送响应A， 消费者（接收方）处理完成消息后发送响应B，生产者（发送方）必须得到AB两个响应才能确定消息成功被处理了）

2. 从ACID到CAP/BASE

2.1 ACID

事务（Transaction）是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元（Unit）。

2.1.1 原子性（Atomicity）

要么全部成功执行，要么全部不执行。

2.1.2 一致性（Consistency）

事务的运行被迫中断时，这些未完成的事务对数据库所做的修改有一部分已写入物理数据库，这时数据库就处于不一致的状态。

2.1.3 隔离性（Isolation）

并发的事务是相互隔离的，一个事务的执行不能被其他事务干扰。SQL规范定义了4个事务隔离级别：

1. 读未提交（Read Uncommitted）：A事务更新过程中，从1更新到10，B事务能获取过程中间值，获取到2，3等值。（脏读）
2. 读已提交（Read Committed）：A事务更新过程中，从1更新到10，B事务只能获取最终的值10。
3. 可重复读（Repeatable Read）：A事务更新过程中，从1更新到10，B事务先获取了1，后来B事务中有个操作重新获取了一次值为10。（幻影读）
4. 串行化（Serializable）：事务只能串行执行，不能并发。

2.1.4 持久性（Durability）

事务一旦提交，对数据库对应数据的状态变更就应该被永久保存下来。

2.1 分布式事务

设想一个最典型的分布式事务场景：一个跨银行的转账操作涉及调用两个异地的银行服务，其中一个是本地银行提供的取款服务，另一个则是目标银行提供的存款 服务，这两个服务本身是无状态并且是互相独立的，共同构成了一个完整的分布式事务。如果从本地银行取款成功，但是因为某种原因存款服务失败了，那么 就必须回滚到取款前的状态，否则用户可能会发现自己的钱不翼而飞了。

我们可以看到，一个分布式事务可以看作是由多个分布式的操作序列组成的，例如上面例子中的取款服务和存款服务，通常可以把这一系列分布式的操作序列称为 子事务。因为，分布式事务也可以被定义为一种嵌套型的事务，同时也就具有了ACID事务特性。但由于在分布式事务中，各个子事务的执行时分布式的， 因此要实现一种能够保证ACID特性的分布式事务处理系统就显得格外复杂。

2.3 CAP和BASE理论

ACID是属于单机系统的理论，分布式有属于自己的理论，即CAP和BASE。

2.3.1 CAP定理

一个分布式系统不可能同时满足一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）这三个基本需求，最多只能同时 满足其中的两项。

.1 Consistency

在分布式环境下，数据在多个副本之间是否能够保持一致性，当某个副本执行更新操作后，应该保证系统的数据仍然处于一致的状态。如果做到一个数据项的更新 操作执行成功后，所有的用户都可以读取到最新的值，那么这样的系统就被认为具有强一致性。

.2 Availability

对于用户的每一个操作请求总是能够在有限的时间内返回结果。划重点：有限的时间内、返回结果。

有限的时间内：对于用户的一个艹做请求，系统必须能够在指定的时间内返回对应的处理结果，如果超过了这个时间范围，那么系统就被认为是不可用的。 比如，对于一个在线搜索引擎来说，通常在0.5秒内需要给出用户搜索关键词对应的检索结果，而对于一个面向HIVE的海量数据查询平台来说，正常一次数据 检索时间可能在20秒，这是正常的，系统必须存在一个合理的响应时间。
返回结果：要求系统在完成堆用户请求的处理后，返回一个正常的结果，而不是返回系统错误。

.3 Partition tolerance

分布式系统在遇到任何网络分区故障的时候（节点间的故障），仍然需要保证对外提供满足一致性和可用性的服务，除非整个网络环境发生了故障。

.4 总结

• AC：所有的数据都放在一个分布式节点上。（谈什么分布式？）
• PC：系统正在维修，请等待。（要么可用，要么直接不能访问）
• AP：放弃数据的强一致性，保留数据额最终一致性。（双11xx商品正在被5126人浏览，可能每个人看到的数字都不一样，但是系统最终会让所有人看到一样的数字）

2.3.2 BASE理论

基于CAP定理结合实际演化而来，即Basically Available（基本可用）、Soft state（软状态）、Eventually consistency（最终一致性）。

.1 Basically Available

分布式在出现不可预知故障的时候，允许损失部分可用性：

响应时间上的损失：搜索正常是0.5秒返回用户，出现故障变成2秒。
功能上的损失：网上购物在双11时选择购买可能会跳转到排队页面。

.2 Soft state

允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

.3 Eventually consistency

强调数据最终数据能够达到一致，而不需要实时保证系统数据的强一致性。 在实际工程实践中，最终一致性存在以下五类主要变种。

.3.1 因果一致性（Causal consistency）

进程A更新完某个数据项后通知了进程B，那么进程B之后对该数据的访问都应该能够获取到进程A更新后的最新纸，并且如果进程B要对该数据项进行更新操作的话， 务必基于进程A更新后的最新值。而进程C的数据访问则没有这样的限制。

.3.2 读己之所写（Read your writes）

进程A更新了一个数据项，它自己总是能够访问到更新过的最新值。特殊的因果一致性（A进程通知了A进程）。

.3.3 会话一致性（Session consistency）

系统能保证在同一个有效的会话中实现“读己之所写”的一致性，即客户端能够在同一绘画中始终读取到该数据项的最新值。

.3.4 单调读一致性（Monotonic read consistency）

如果一个进程从系统读取出一个数据项的某个值后，那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。

.3.5 单调写一致性（Monotonic write consistency）

系统保证来自同一个进程的写操作被顺序地执行。

.3.6 总结

最终一致性并不是只有那些大型分布式系统才涉及的特性，许多关系型数据库都采用了最终一致性模型，采用同步和异步方式来实现主备数据复制技术。

在同步方式中，数据的复制过程通常是更新事务的一部分，因此在书屋完成后，主备数据库的数据就会达到一致。
在异步方式中，备库的更新往往会存在延时，这取决于事务日志在主备数据库之间传输的时间长达，如果传输时间过长或者甚至在日志传输过程中出现异常导致 无法及时将事务应用到备库上，那么很显然，从备库读取的数据将是旧的，就出现了数据不一致的情况。
但是，无论采用重试、人为修正，关系型数据库还是能够保证最终数据达到一致性——这就是系统提供最终一致性保证的经典案例。

总的来说，BASE理论面向大型高可用可扩展的分布式系统，和传统事务的ACID特性是相反的，不同于ACID的强一致性模型，而是通过强一致性和高可用性的 平衡，最终达到一致性。因此在具体的分布式系统架构设计过程中，ACID和BASE理论往往会结合一起使用用来面对不同的业务场景的要求。

3. 小结

分布式架构发展过程中的ACID->CAP->BASE等分布式事务与一致性方面的经典理论。