《设计模式：可复用面向对象软件的基础》一书中提出了 24 中经典的设计模式，这些设计模式被广泛地运用于项目实战之中。这篇博客的重点并不在于讲解这些设计模式以及使用，而主要列举了在 Java Core Libraries 中间所用到的设计模式。Java Core Libraries 中的 API 设计基本涵盖了 GOF 书中所提到的绝大部分设计模式，可以说是 API 设计的典范，非常值得借鉴和学习。

创建型模式

这些设计模式提供了一种在创建对象的同时隐藏创建逻辑的方式，而不是使用 new 运算符直接实例化对象。这使得程序在判断针对某个给定实例需要创建哪些对象时更加灵活。

工厂模式（Factory Pattern）

• java.util.Calendar#getInstance()
• java.util.ResourceBundle#getBundle()
• java.text.NumberFormat#getInstance()
• java.nio.charset.Charset#forName()
• java.net.URLStreamHandlerFactory#createURLStreamHandler(String) (Returns singleton object per protocol)
• java.util.EnumSet#of()
• javax.xml.bind.JAXBContext#createMarshaller() and other similar methods

抽象工厂模式（Abstract Factory Pattern）

• javax.xml.parsers.DocumentBuilderFactory#newInstance()
• javax.xml.transform.TransformerFactory#newInstance()
• javax.xml.xpath.XPathFactory#newInstance()

单例模式（Singleton Pattern）

• java.lang.Runtime#getRuntime()
• java.awt.Desktop#getDesktop()
• java.lang.System#getSecurityManager()

建造者模式（Builder Pattern）

• java.lang.StringBuilder#append() (unsynchronized)
• java.lang.StringBuffer#append() (synchronized)
• java.nio.ByteBuffer#put() (also on CharBuffer, ShortBuffer, IntBuffer, LongBuffer, FloatBuffer and DoubleBuffer)
• javax.swing.GroupLayout.Group#addComponent()

原型模式（Prototype Pattern）

• java.lang.Object#clone()

结构型模式

这些设计模式关注类和对象的组合。继承的概念被用来组合接口和定义组合对象获得新功能的方式

适配器模式（Adapter Pattern）

• java.util.Arrays#asList()
• java.util.Collections#list()
• java.util.Collections#enumeration()
• java.io.InputStreamReader(InputStream) (returns a Reader)
• java.io.OutputStreamWriter(OutputStream) (returns a Writer)
• javax.xml.bind.annotation.adapters.XmlAdapter#marshal() and

桥接模式（Bridge Pattern）

TODO

过滤器模式（Filter、Criteria Pattern）

组合模式（Composite Pattern）

• java.awt.Container#add(Component)
• javax.faces.component.UIComponent#getChildren()

装饰器模式（Decorator Pattern）

• All subclasses of java.io.InputStream, OutputStream, Reader and Writer have a constructor taking an instance of same type.
• java.util.Collections, the checkedXXX(), synchronizedXXX() and unmodifiableXXX() methods.
• javax.servlet.http.HttpServletRequestWrapper and HttpServletResponseWrapper

外观模式（Facade Pattern）

• javax.faces.context.FacesContext, it internally uses among others the abstract/interface types LifeCycle, ViewHandler, NavigationHandler and many more without that the enduser has to worry about it (which are however overrideable by injection).
• javax.faces.context.ExternalContext, which internally uses ServletContext, HttpSession, HttpServletRequest, HttpServletResponse, etc.

享元模式（Flyweight Pattern）

• java.lang.Integer#valueOf(int) (also on Boolean, Byte, Character, Short, Longand BigDecimal)

代理模式（Proxy Pattern）

• java.lang.reflect.Proxy
• java.rmi.*
• javax.ejb.EJB (explanation here)
• javax.inject.Inject (explanation here)
• javax.persistence.PersistenceContext

行为型模式

责任链模式（Chain of Responsibility Pattern）

• java.util.logging.Logger#log()
• javax.servlet.Filter#doFilter()

命令模式（Command Pattern）

• All implementations of java.lang.Runnable
• All implementations of javax.swing.Action

解释器模式（Interpreter Pattern）

• java.util.Pattern
• java.text.Normalizer
• All subclasses of java.text.Format
• All subclasses of javax.el.ELResolver

迭代器模式（Iterator Pattern）

• All implementations of java.util.Iterator (thus among others also java.util.Scanner!).
• All implementations of java.util.Enumeration

中介者模式（Mediator Pattern）

• java.util.Timer (all scheduleXXX() methods)
• java.util.concurrent.Executor#execute()
• java.util.concurrent.ExecutorService (the invokeXXX() and submit() methods)
• java.util.concurrent.ScheduledExecutorService (all scheduleXXX() methods)
• java.lang.reflect.Method#invoke()

备忘录模式（Memento Pattern）

• java.util.Date (the setter methods do that, Date is internally represented by a longvalue)
• All implementations of java.io.Serializable
• All implementations of javax.faces.component.StateHolder

观察者模式（Observer Pattern）

• java.util.Observer/java.util.Observable (rarely used in real world though)*
• All implementations of java.util.EventListener (practically all over Swing thus)
• javax.servlet.http.HttpSessionBindingListener
• javax.servlet.http.HttpSessionAttributeListener
• javax.faces.event.PhaseListener

状态模式（State Pattern）

• javax.faces.lifecycle.LifeCycle#execute() (controlled by FacesServlet, the behaviour is dependent on current phase (state) of JSF lifecycle)

空对象模式（Null Object Pattern）

TODO

策略模式（Strategy Pattern）

• java.util.Comparator#compare(), executed by among others Collections#sort().
• javax.servlet.http.HttpServlet, the service() and all doXXX() methods take HttpServletRequest and HttpServletResponse and the implementor has to process them (and not to get hold of them as instance variables!).
• javax.servlet.Filter#doFilter()

模板模式（Template Pattern）

• All non-abstract methods of java.io.InputStream, java.io.OutputStream, java.io.Reader and java.io.Writer.
• All non-abstract methods of java.util.AbstractList, java.util.AbstractSet and java.util.AbstractMap. javax.servlet.http.HttpServlet, all the doXXX() methods by default sends a HTTP 405 "Method Not Allowed" error to the response. You're free to implement none or any of them.

访问者模式（Visitor Pattern）

• javax.lang.model.element.AnnotationValue and AnnotationValueVisitor
• javax.lang.model.element.Element and ElementVisitor
• javax.lang.model.type.TypeMirror and TypeVisitor
• java.nio.file.FileVisitor and SimpleFileVisitor
• javax.faces.component.visit.VisitContext and VisitCallback

参考资料

• http://www.runoob.com/design-pattern/design-pattern-intro.html
• https://stackoverflow.com/questions/1673841/examples-of-gof-design-patterns-in-javas-core-libraries

什么是 ClassLoader

一个 Java 程序是由若干个 class 文件组成。当程序在运行时，即会调用该程序的一个入口函数来调用系统的相关功能，而这些功能都被封装在不同的 class 文件当中，所以经常要从这个 class 文件中要调用另外一个 class 文件中的方法，如果另外一个 class 文件不存在的，则会引发 ClassNotFoundException。

程序在启动的时候，并不会一次性加载程序所要用的所有 class 文件，而是根据程序的需要，通过 Java 的类加载机制（ClassLoader）来动态加载某个 class 文件到内存当中的，从而只有 class 文件被载入到了内存之后，才能被其它 class 所引用。所以 ClassLoader 就是用来动态加载 class 文件到内存当中用的。

Java ClassLoader 的体系结构

现在先看下 ClassLoader 的体系结构：

Bootstrap ClassLoader

BootStrap ClassLoader：称为启动类加载器，是 Java 类加载层次中最顶层的类加载器，负责加载 JDK 中的核心类库，如：rt.jar、resources.jar、charsets.jar 等。

可以通过如下程序获得该 classloader 所加载的 jar

System.out.println(System.getProperty("sun.boot.class.path"));

程序输出：

/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/sunrsasign.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/classes

如果是 scala 会在 java 的基础上额外加载几个 jar。

scala> println(System.getProperty("sun.boot.class.path"))
/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/sunrsasign.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_60.jdk/Contents/Home/jre/classes:/Users/zhenlong/DevTools/scala/lib/akka-actor_2.11-2.3.10.jar:/Users/zhenlong/DevTools/scala/lib/config-1.2.1.jar:/Users/zhenlong/DevTools/scala/lib/jline-2.12.1.jar:/Users/zhenlong/DevTools/scala/lib/scala-actors-2.11.0.jar:/Users/zhenlong/DevTools/scala/lib/scala-actors-migration_2.11-1.1.0.jar:/Users/zhenlong/DevTools/scala/lib/scala-compiler.jar:/Users/zhenlong/DevTools/scala/lib/scala-continuations-library_2.11-1.0.2.jar:/Users/zhenlong/DevTools/scala/lib/scala-continuations-plugin_2.11.7-1.0.2.jar:/Users/zhenlong/DevTools/scala/lib/scala-library.jar:/Users/zhenlong/DevTools/scala/lib/scala-parser-combinators_2.11-1.0.4.jar:/Users/zhenlong/DevTools/scala/lib/scala-reflect.jar:/Users/zhenlong/DevTools/scala/lib/scala-swing_2.11-1.0.2.jar:/Users/zhenlong/DevTools/scala/lib/scala-xml_2.11-1.0.4.jar:/Users/zhenlong/DevTools/scala/lib/scalap-2.11.7.jar

Extension ClassLoader

Extension ClassLoader：称为扩展类加载器，负责加载 Java 的扩展类库，默认加载 JAVA_HOME/jre/lib/ext/目下的所有 jar。该类在 sun.misc.launcher 包中。

App ClassLoader

App ClassLoader：称为应用类加载器，也称为 System ClassLoaer，负责加载应用程序 CLASSPATH 下的所有 jar 和 class 文件。该类也在 sun.misc.launcher 包中。

User-Defined ClassLoader

用户还可以根据需要定义自已的 ClassLoader，而这些自定义的 ClassLoader 都必须继承自 java.lang.ClassLoader 类.

所有的 ClassLoader 都必须继承自 java.lang.ClassLoader，而 Bootstrap ClassLoader 却不是。它不是一个普通的 Java 类，底层由 C++编写，已嵌入到了 JVM 内核当中，当 JVM 启动后，Bootstrap ClassLoader 也随着启动，负责加载完核心类库后，并构造 Extension ClassLoader 和 App ClassLoader 类加载器。

ClassLoader 加载原理

ClassLoader 使用的是双亲委托模型来搜索类的，每个 ClassLoader 实例都包含(而不是继承)一个父类加载器的引用。虚拟机内置的类加载器（Bootstrap ClassLoader）本身没有父类加载器，但可以用作其它 ClassLoader 实例的的父类加载器。

采用双亲委托机制加载类的时候采用如下的几个步骤：

1. 当前 ClassLoader 首先从自己已经加载的类中查询是否此类已经加载，如果已经加载则直接返回原来已经加载的类；
2. 当前 classLoader 的缓存中没有找到被加载的类的时候，委托父类加载器去加载，父类加载器采用同样的策略，首先查看自己的缓存，然后委托父类的父类去加载，一直到 bootstrp ClassLoader.
3. 当所有的父类加载器都没有加载的时候，再由当前的类加载器加载，并将其放入它自己的缓存中，以便下次有加载请求的时候直接返回。
4. 如果它们都没有加载到这个类时，则抛出 ClassNotFoundException 异常。否则（找到），将为这个类生成一个类的定义，并将它加载到内存当中，最后返回这个类在内存中的 Class 实例对象；

总之，class 的加载顺序为：cache -> parent classloader -> self.

使用双亲委托模型的好处：

1. 避免重复加载。当父亲已经加载了该类的时候，就没有必要子 ClassLoader 再加载一次。
2. 提高安全性。如果不使用这种委托模式，那我们就可以随时使用自定义的 String 来动态替代 java 核心 api 中定义的类型，这样会存在非常大的安全隐患，而双亲委托的方式，就可以避免这种情况，因为 String 已经在启动时就被引导类加载器（Bootstrcp ClassLoader）加载，所以用户自定义的 ClassLoader 永远也无法加载一个自己写的 String，除非你改变 JDK 中 ClassLoader 搜索类的默认算法。

在 JVM 在搜索类的时候，又是如何判定两个 class 是相同的呢？JVM 在判定两个 class 是否相同时，不仅要判断两个类名是否相同，而且要判断是否由同一个类加载器实例加载的。只有两者同时满足的情况下，JVM 才认为这两个 class 是相同的。就算两个 class 是同一份 class 字节码，如果被两个不同的 ClassLoader 实例所加载，JVM 也会认为它们是两个不同 class。比如有一个 Java 类 SimpleClass.java，javac 编译之后生成字节码文件 SimpleClass.class，ClassLoaderA 和 ClassLoaderB 这两个类加载器并读取了 SimpleClass.class 文件，并分别定义出了 java.lang.Class 实例来表示这个类，对于 JVM 来说，它们是两个不同的实例对象，但它们确实是同一份字节码文件，如果试图将这个 Class 实例生成具体的对象进行转换时，就会抛运行时异常 java.lang.ClassCaseException，提示这是两个不同的类型。

如何自定义 ClassLoader

何时需要自己定制 ClassLoader？

1. 需要加载外部的 class 而这些 class，默认的类加载器是加载不到的。例如，文件系统比较特殊或者需要从网络中加载一个 class 字节流等。
2. 需要实现 class 的隔离性。常用的 web 服务器，如 weblogic、tomcat、jetty 等都实现这样的类加载器。这些类加载器主要做到： 1）实现加载 Web 应用指定目录下的 jar 和 class。 2）实现部署在容器中的 Web 应用程共同使用的类库的共享。 3）实现部署在容器中各个 Web 应用程序自己私有类库的相互隔离。

如何自定义 ClassLoader

1. 继承 java.lang.ClassLoader
2. 覆盖 findClass()方法

下面是一个自定义 ClassLoader 的例子：

public class MyClassLoader extends ClassLoader {
    @Override
    protected Class<?> findClass(String name) throws ClassNotFoundException {
        Class clazz = this.findLoadedClass(name);  // optional
        if (clazz == null) {
            byte[] classData = loadClassData(name);
            if (classData == null) {
                throw new ClassNotFoundException();
            }
            clazz = defineClass(name, classData, 0, classData.length);
        }
        return clazz;
    }

    private byte[] loadClassData(String name) {
        // TODO: load class data.
        return null;
    }
}

Sublime Text是一个十分强大的文本编辑器，它支持Windows，Linux和Mac。Sublime Text在默认情况下就支持Markdown格式，本文想介绍的是如何增强Sublime Text使其更好的Markdown写作。

Package Control

想必大多数SublimeText的用户已经安装了Package Control这个神器了。如未安装，请参考：https://packagecontrol.io/installation

Markdown Preview

markdown preview这个插件可以使用户在浏览器中预览Markdown文件。

按下键Ctrl+Shift+p调出命令面板，找到Package Control: install Pakage这一项。搜索markdown preview，点击安装。

关于快捷键设置，可以在Preferences->Key Binding User中，加入

{ 
	"keys": ["alt+m"],
	"command": "markdown_preview",
	"args": 
	{ 
		"target": "browser"
		
	} 
}

语法高亮

默认SublimeText带的语法高亮对Markdown确实太少了，可以装一个Monokai Extended插件进行增强。在Package Control中搜索Monokai Extended并安装，然后在Preferences->Color Scheme中进行设置。

Octopress是一个基于Jekyll静态页面生成器，多数用于Github Pages的生成。本文主要介绍Octopress在Windows以及Linux平台下的安装，本文的安装步骤基于Window 7以及Ubuntu 14.04。

Git安装

Git下载地址：http://git-scm.com/downloads

Ubuntu用户也可执行下面命令：

sudo apt-get install git

Ruby安装

Ruby下载地址:http://rubyinstaller.org/downloads/。这里需要注意，所选择的版本应为Ruby1.9.3或者更高，本文使用的是Ruby1.9.3。

Windows用户还需额外安装RubyDevKit，下载地址:http://rubyinstaller.org/downloads/

cd C:/RubyDevKit
ruby dk.rb init
ruby dk.rb install

安装后使用ruby --version命令确认所安装的Ruby版本。

Octopress安装

克隆Octopress源码，安装依赖。

git clone git://github.com/imathis/octopress.git octopress
cd octopress
gem install bundler
bundle install

安装Octopress默认主题。

rake install

到目前为止，Octopress已经安装完成，可以使用rake generate命令尝试生成静态页面。使用rake preview命令到http://localhost:4000进行预览。

Troubleshooting

Windows用户，在执行rake generate命令的过程中，可能会出现类似

warning: cannot close fd before spawn

的警告信息，导致静态页面生成失败。这是主要是由于pygments的版本与Windows不兼容导致的。可以尝试执行以下步骤进行修复：

gem uninstall pygments.rb --version ">0.5.0"
gem install pygments.rb --version "=0.5.0"

在项目文件夹下修改Gemfile.lock文件

pygments.rb (0.6.0) => pygments.rb (0.5.0)

Zookeeper 使用了一种称为 Zab（Zookeeper Atomic Broadcast）的协议作为其一致性的核心。Zab 协议是 Paxos 协议的一种变形，下面将展示一些协议的核心内容。

考虑到 Zookeeper 的主要操作数据状态，为了保证一致性，Zookeeper 提出了两个安全属性：

• 全序（Total Order）：如果消息 A 在消息 B 之前发送，则所有 Server 应该看到相同结果。
• 因果顺序（Causal Order）：如果消息 A 在消息 B 之前发生（A 导致了 B），并且一起发送，则消息 A 始终在消息 B 之前被执行。

为了保证上述两个安全属性，Zookeeper 使用了 TCP 协议和 Leader。通过使用 TCP 协议保证了消息的全序的特性（先发先到），通过 Leader 解决了因果顺序(先到 Leader 先执行)。因为有了 Leader，Zookeeper 的架构就变成为：Master-Slave 模式，但在该模式中 Master（Leader）会 Crash，因此，Zookeeper 引入 Leader 选举算法，以保证系统的健壮性。

当 Zookeeper Server 收到写操作，Follower 会将其转发给 Leader，由 Leader 执行操作。Client 可以直接从 Follower 上读取数据，如果需要读取最新数据，则需要从 Leader 节点读取，Zookeeper 设计的读写比大致为 2：1。

Leader 执行写操作可以简化为一个两段式提交的 transaction：

1. Leader 发送 proposal 给所有的 Follower。
2. 收到 proposal 后，Follower 回复 ACK 给 Leader，接受 Leader 的 proposal.
3. 当 Leader 收到大多数的 Follower 的 ACK 后，将 commit 其 proposal。

在这个过程中，proposal 的确认不需要所有节点都同意，如果有 2n+1 个节点，那么只要有 n 个节点同意即可，也就是说 Zookeeper 允许 n 个节点 down 掉。任何两个多数派必然有交集，在 Leader 切换（Leader down）时，这些交集依然保持着最新的系统状态。如果集群节点个数少于 n+1 个时，Zookeeper 将无法进行同步，也就无法继续工作。

Zab 与 Paxos

Zab 的作者认为 Zab 与 paxos 并不相同，只所以没有采用 Paxos 是因为 Paxos 保证不了全序顺序：

Because multiple leaders can propose a value for a given instance two problems arise. First, proposals can conflict. Paxos uses ballots to detect and resolve conflicting proposals. Second, it is not enough to know that a given instance number has been committed, processes must also be able to figure out which value has been committed.

举个例子。假设一开始 Paxos 系统中的 Leader 是 P1，他发起了两个事务{t1, v1}（表示序号为 t1 的事务要写的值是 v1）和{t2, v2}，过程中 Leader 挂了。新来个 Leader 是 P2，他发起了事务{t1, v1'}。而后又来个新 Leader 是 P3，他汇总了一下，得出最终的执行序列{t1, v1'}和{t2, v2}。

这样的序列为什么不能满足 ZooKeeper 的需求呢？ZooKeeper 是一个树形结构，很多操作都要先检查才能确定能不能执行，比如 P1 的事务 t1 可能是创建节点“/a”，t2 可能是创建节点“/a/aa”，只有先创建了父节点“/a”，才能创建子节点“/a/aa”。而 P2 所发起的事务 t1 可能变成了创建“/b”。这样 P3 汇总后的序列是先创建“/b”再创建“/a/aa”，由于“/a”还没建，创建“a/aa”就搞不定了。

为了保证这一点，ZAB 要保证同一个 leader 的发起的事务要按顺序被 apply，同时还要保证只有先前的 leader 的所有事务都被 apply 之后，新选的 leader 才能在发起事务。

当 Leader 崩溃或者 Leader 失去大多数的 Follower，这时候 zk 进入恢复模式，恢复模式需要重新选举出一个新的 Leader，让所有的 Server 都恢复到一个正确的状态。Zookeeper 中 Leader 的选举采用了三种算法：

• LeaderElection
• FastLeaderElection
• AuthFastLeaderElection

并且在配置文件中是可配置的，对应的配置项为 electionAlg。

背景知识

Zookeeper Server 的状态可分为四种：

• LOOKING：寻找 Leader
• LEADING：Leader 状态，对应的节点为 Leader。
• FOLLOWING：Follower 状态，对应的节点为 Follower。
• OBSERVING：Observer 状态，对应节点为 Observer，该节点不参与 Leader 选举。

成为 Leader 的必要条件： Leader 要具有最高的 zxid；当集群的规模是 n 时，集群中大多数的机器（至少 n/2+1）得到响应并 follow 选出的 Leader。

心跳机制：Leader 与 Follower 利用 PING 来感知对方的是否存活，当 Leader 无法相应 PING 时，将重新发起 Leader 选举。

术语

zxid：zookeeper transaction id, 每个改变 Zookeeper 状态的操作都会形成一个对应的 zxid，并记录到 transaction log 中。 这个值越大，表示更新越新。

electionEpoch/logicalclock：逻辑时钟，用来判断是否为同一次选举。每调用一次选举函数，logicalclock 自增 1，并且在选举过程中如果遇到 election 比当前 logicalclock 大的值，就更新本地 logicalclock 的值。

peerEpoch: 表示节点的 Epoch。

LeaderElection 选举算法

LeaderElection 是 Fast Paxos 最简单的一种实现，每个 Server 启动以后都询问其它的 Server 它要投票给谁，收到所有 Server 回复以后，就计算出 zxid 最大的哪个 Server，并将这个 Server 相关信息设置成下一次要投票的 Server。该算法于 Zookeeper 3.4 以后的版本废弃。

选举算法流程如下：

1. 选举线程首先向所有 Server 发起一次询问(包括自己)；
2. 选举线程收到回复后，验证是否是自己发起的询问(验证 xid 是否一致)，然后获取对方的 id(myid)，并存储到当前询问对象列表中，最后获取对方提议的 leader 相关信息(id,zxid)，并将这些信息存储到当次选举的投票记录表中；
3. 收到所有 Server 回复以后，就计算出 zxid 最大的那个 Server，并将这个 Server 相关信息设置成下一次要投票的 Server；
4. 线程将当前 zxid 最大的 Server 设置为当前 Server 要推荐的 Leader，如果此时获胜的 Server 获得多数 Server 票数， 设置当前推荐的 leader 为获胜的 Server，将根据获胜的 Server 相关信息设置自己的状态，否则，继续这个过程，直到 leader 被选举出来。

通过流程分析我们可以得出：要使 Leader 获得多数 Server 的支持，则 Server 总数必须是奇数 2n+1，且存活的 Server 的数目不得少于 n+1.

异常问题的处理：

1. 选举过程中，Server 的加入
   当一个 Server 启动时它都会发起一次选举，此时由选举线程发起相关流程，那么每个 Serve r 都会获得当前 zxi d 最大的哪个 Serve r 是谁，如果当次最大的 Serve r 没有获得 n/2+1 个票数，那么下一次投票时，他将向 zxid 最大的 Server 投票，重复以上流程，最后一定能选举出一个 Leader。
2. 选举过程中，Server 的退出
   只要保证 n/2+1 个 Server 存活就没有任何问题，如果少于 n/2+1 个 Server 存活就没办法选出 Leader。
3. 选举过程中，Leader 死亡
   当选举出 Leader 以后，此时每个 Server 应该是什么状态(FLLOWING)都已经确定，此时由于 Leader 已经死亡我们就不管它，其它的 Fllower 按正常的流程继续下去，当完成这个流程以后，所有的 Fllower 都会向 Leader 发送 Ping 消息，如果无法 ping 通，就改变自己的状为(FLLOWING ==> LOOKING)，发起新的一轮选举。
4. 选举完成以后，Leader 死亡
   处理过程同上。
5. 双主问题
   Leader 的选举是保证只产生一个公认的 Leader 的，而且 Follower 重新选举与旧 Leader 恢复并退出基本上是同时发生的，当 Follower 无法 ping 同 Leader 是就认为 Leader 已经出问题开始重新选举，Leader 收到 Follower 的 ping 没有达到半数以上则要退出 Leader 重新选举。

FastLeaderElection 选举算法

由于 LeaderElection 收敛速度较慢，所以 Zookeeper 引入了 FastLeaderElection 选举算法，FastLeaderElection 也成了 Zookeeper 默认的 Leader 选举算法。

FastLeaderElection 是标准的 Fast Paxos 的实现，它首先向所有 Server 提议自己要成为 leader，当其它 Server 收到提议以后，解决 epoch 和 zxid 的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息。FastLeaderElection 算法通过异步的通信方式来收集其它节点的选票，同时在分析选票时又根据投票者的当前状态来作不同的处理，以加快 Leader 的选举进程。

算法流程

数据恢复阶段

每个 ZooKeeper Server 读取当前磁盘的数据（transaction log），获取最大的 zxid。

发送选票

每个参与投票的 ZooKeeper Server 向其他 Server 发送自己所推荐的 Leader，这个协议中包括几部分数据：

• 所推举的 Leader id。在初始阶段，第一次投票所有 Server 都推举自己为 Leader。
• 本机的最大 zxid 值。这个值越大，说明该 Server 的数据越新。
• logicalclock。这个值从 0 开始递增，每次选举对应一个值，即在同一次选举中，这个值是一致的。这个值越大说明选举进程越新。
• 本机的所处状态。包括 LOOKING，FOLLOWING，OBSERVING，LEADING。

处理选票

每台 Server 将自己的数据发送给其他 Server 之后，同样也要接受其他 Server 的选票，并做一下处理。

如果 Sender 的状态是 LOOKING

• 如果发送过来的 logicalclock 大于目前的 logicalclock。说明这是更新的一次选举，需要更新本机的 logicalclock，同事清空已经收集到的选票，因为这些数据已经不再有效。然后判断是否需要更新自己的选举情况。首先判断 zxid，zxid 大者胜出；如果相同比较 leader id，大者胜出。
• 如果发送过来的 logicalclock 小于于目前的 logicalclock。说明对方处于一个比较早的选举进程，只需要将本机的数据发送过去即可。
• 如果发送过来的 logicalclock 等于目前的 logicalclock。根据收到的 zxid 和 leader id 更新选票，然后广播出去。

当 Server 处理完选票后，可能需要对 Server 的状态进行更新：

• 判断服务器是否已经收集到所有的服务器的选举状态。如果是根据选举结果设置自己的角色（FOLLOWING or LEADER），然后退出选举。
• 如果没有收到没有所有服务器的选举状态，也可以判断一下根据以上过程之后更新的选举 Leader 是不是得到了超过半数以上服务器的支持。如果是，那么尝试在 200ms 内接收下数据，如果没有心数据到来说明大家已经认同这个结果。这时，设置角色然后退出选举。

如果 Sender 的状态是 FOLLOWING 或者 LEADER

• 如果 LogicalClock 相同，将数据保存早 recvset，如果 Sender 宣称自己是 Leader，那么判断是不是半数以上的服务器都选举它，如果是设置角色并退出选举。
• 否则，这是一条与当前 LogicalClock 不符合的消息，说明在另一个选举过程中已经有了选举结果，于是将该选举结果加入到 OutOfElection 集合中，根据 OutOfElection 来判断是否可以结束选举，如果可以也是保存 LogicalClock，更新角色，退出选举。

具体实现

数据结构

本地消息结构：

static public class Notification {
long leader;  //所推荐的Server id

long zxid;      //所推荐的Server的zxid(zookeeper transtion id)

long epoch;   //描述leader是否变化(每一个Server启动时都有一个logicalclock，初始值为0)

QuorumPeer.ServerState state;   //发送者当前的状态
InetSocketAddress addr;            //发送者的ip地址
}

网络消息结构：

static public class ToSend {

int type;        //消息类型
long leader;  //Server id
long zxid;     //Server的zxid
long epoch;  //Server的epoch
QuorumPeer.ServerState state; //Server的state
long tag;      //消息编号

InetSocketAddress addr;

}

线程处理

每个 Server 都一个接收线程池和一个发送线程池, 在没有发起选举时，这两个线程池处于阻塞状态，直到有消息到来时才解除阻塞并处理消息，同时每个 Server 都有一个选举线程(可以发起选举的线程担任)。

• 接收线程的处理
  notification: 首先检测当前 Server 上所被推荐的 zxid,epoch 是否合法(currentServer.epoch <= currentMsg.epoch && (currentMsg.zxid > currentServer.zxid || (currentMsg.zxid == currentServer.zxid && currentMsg.id > currentServer.id))) 如果不合法就用消息中的 zxid,epoch,id 更新当前 Server 所被推荐的值，此时将收到的消息转换成 Notification 消息放入接收队列中，将向对方发送 ack 消息。
  ack: 将消息编号放入 ack 队列中，检测对方的状态是否是 LOOKING 状态，如果不是说明此时已经有 Leader 已经被选出来，将接收到的消息转发成 Notification 消息放入接收对队列

• 发送线程池的处理
  notification: 将要发送的消息由 Notification 消息转换成 ToSend 消息，然后发送对方，并等待对方的回复,如果在等待结束没有收到对方法回复，重做三次,如果重做次还是没有收到对方的回复时检测当前的选举(epoch)是否已经改变，如果没有改变，将消息再次放入发送队列中，一直重复直到有 Leader 选出或者收到对方回复为止。
  ack: 主要将自己相关信息发送给对方

• 选举线程的处理
  首先自己的 epoch 加 1，然后生成 notification 消息,并将消息放入发送队列中，系统中配置有几个 Server 就生成几条消息，保证每个 Server 都能收到此消息,如果当前 Server 的状态是 LOOKING 就一直循环检查接收队列是否有消息，如果有消息，根据消息中对方的状态进行相应的处理。

AuthFastLeaderElection 选举算法

AuthFastLeaderElection 算法同 FastLeaderElection 算法基本一致，只是在消息中加入了认证信息，该算法在最新的 Zookeeper 中也建议弃用。

Example

下面看一个 Leader 选举的例子以加深对 Leader 选举算法的理解。

1. 服务器 1 启动,此时只有它一台服务器启动了,它发出去的报没有任何响应,所以它的选举状态一直是 LOOKING 状态.
2. 服务器 2 启动,它与最开始启动的服务器 1 进行通信,互相交换自己的选举结果,由于两者都没有历史数据,所以 id 值较大的服务器 2 胜出,但是由于没有达到超过半数以上的服务器都同意选举它(这个例子中的半数以上是 3),所以服务器 1,2 还是继续保持 LOOKING 状态.
3. 服务器 3 启动,根据前面的理论分析,服务器 3 成为服务器 1,2,3 中的 Leader,而与上面不同的是,此时有三台服务器选举了它,所以它成为了这次选举的 Leader.
4. 服务器 4 启动,根据前面的分析,理论上服务器 4 应该是服务器 1,2,3,4 中最大的,但是由于前面已经有半数以上的服务器选举了服务器 3,所以它只能是 Follower.
5. 服务器 5 启动,同 4 一样,Follower.

参考资料

http://blog.csdn.net/xhh198781/article/details/10949697

http://blog.cnsolomo.com/ld/liunx/nginx/264.html

http://blog.sina.com.cn/s/blog_3fe961ae01012jod.html

http://blog.csdn.net/xhh198781/article/details/6619203

http://csrd.aliapp.com/?p=162

http://codemacro.com/2014/10/19/zk-fastleaderelection/

在 Zookeeper 集群中，主要分为三者角色，而每一个节点同时只能扮演一种角色，这三种角色分别是：

• Leader：接受所有 Follower 的提案请求并统一协调发起提案的投票，负责与所有的 Follower 进行内部的数据交换(同步);
• Follower：直接为客户端服务并参与提案的投票，同时与 Leader 进行数据交换(同步);
• Observer：直接为客户端服务但并不参与提案的投票，同时也与 Leader 进行数据交换(同步);

Follower 与 Observer 并称为 Learner。

Leader

在 Zookeeper 集群中，只有一个 Leader 节点，其主要职责：

• 恢复数据；
• 维持与 Learner 的心跳，接收 Learner 请求并判断 Learner 的请求消息类型；

Leader 的工作流程简图如下所示，在实际实现中，流程要比下图复杂得多，启动了三个线程来实现功能。

PING：Learner 的心跳。
REQUEST：Follower 发送的提议信息，包括写请求及同步请求。
ACK：Follower 的对提议的回复，超过半数的 Follower 通过，则 commit 该提议。
REVALIDATE：用来延长 SESSION 有效时间。

Follower

在 Zookeeper 集群中，follower 可以为多个，其主要职责：

• 向 Leader 发送请求；
• 接收 Leader 的消息并进行处理；
• 接收 Zookeeper Client 的请求，如果为写清求，转发给 Leader 进行处理

Follower 的工作流程简图如下所示，在实际实现中，Follower 是通过 5 个线程来实现功能的。

PING：心跳消息。
PROPOSAL：Leader 发起的提案，要求 Follower 投票。
COMMIT：服务器端最新一次提案的信息。
UPTODATE：表明同步完成。
REVALIDATE：根据 Leader 的 REVALIDATE 结果，关闭待 revalidate 的 session 还是允许其接受消息。
SYNC：返回 SYNC 结果到客户端，这个消息最初由客户端发起，用来强制得到最新的更新。

Observer

此处 Observer 就不再分析，其与 follower 基本相同，唯一不同就在于 Observer 不参与投票。

Zookeeper Server 的启动入口为 org.apache.zookeeper.server.quorum.QuorumPeerMain。Zookeeper 的启动模式分为两种：一种为 standalone mode；另一种为 cluster mode。

• Standalone 模式：当配置文件中仅配置了一台 server 时，Zookeeper 将以 standalone 模式启动，启动类为 ZooKeeperServerMain，此处不作详细分析。
• Cluster 模式：当配置文件中配置了多台 server，构建 cluster，启动类为 QuorumPeer#start()。

public synchronized void start() {
        loadDataBase();
        cnxnFactory.start();
        startLeaderElection();
        super.start();
    }

清理 DataDir

在 Server 启动时，根据启动的配置参数启动一个 TimeTask 用于清理 DataDir 中的 snapshot 及对应的 transactionlog。由于 Zookeeper 的任何一个写操作都将在 transaction log 中留下记录，当写操作达到一定量或者一定时间间隔，Zookeeper 将 transaction log 合并为 snapshot。所以随着运行时间的增长生成的 transaction log 和 snapshot 将越来越多，所以定期清理是必要的。在 DatadirCleanupManager 中有两个参数：

• snapRetainCount：清理后保留的 snapshot 的个数，该参数至少要大于 3。
• purgeInterval：定期清理的时间间隔，以小时为单位。

// Start and schedule the the purge task
       DatadirCleanupManager purgeMgr = new DatadirCleanupManager(config
               .getDataDir(), config.getDataLogDir(), config
               .getSnapRetainCount(), config.getPurgeInterval());
       purgeMgr.start();

加载 ZKDatabase

1.从 snapshot 和 transaction log 中恢复 ZKDatabase，并将其载入内存。

zkDb.loadDataBase();

2.载入 currentEpoch 和 acceptedEpoch

首先要明白什么是 epoch，官方给出的解释是:

The zxid has two parts: the epoch and a counter. In our implementation the zxid is a 64-bit number. We use the high order 32-bits for the epoch and the low order 32-bits for the counter. Because it has two parts represent the zxid both as a number and as a pair of integers, (epoch, count). The epoch number represents a change in leadership. Each time a new leader comes into power it will have its own epoch number.

从 currentEpoch 文件中读取 current epoch；若 currentEpoch 文件不存在，Zookeeper 将从 lastProcessedZxid 中获取 epoch 作为 current epoch，写入 currentEpoch 文件。

try {
           	currentEpoch = readLongFromFile(CURRENT_EPOCH_FILENAME);
               if (epochOfZxid > currentEpoch && updating.exists()) {
                   LOG.info("{} found. The server was terminated after " +
                            "taking a snapshot but before updating current " +
                            "epoch. Setting current epoch to {}.",
                            UPDATING_EPOCH_FILENAME, epochOfZxid);
                   setCurrentEpoch(epochOfZxid);
                   if (!updating.delete()) {
                       throw new IOException("Failed to delete " +
                                             updating.toString());
                   }
               }
           } catch(FileNotFoundException e) {
           	// pick a reasonable epoch number
           	// this should only happen once when moving to a
           	// new code version
           	currentEpoch = epochOfZxid;
           	LOG.info(CURRENT_EPOCH_FILENAME
           	        + " not found! Creating with a reasonable default of {}. This should only happen when you are upgrading your installation",
           	        currentEpoch);
           	writeLongToFile(CURRENT_EPOCH_FILENAME, currentEpoch);
           }

同理，获取 accepted epoch。

try {
           	acceptedEpoch = readLongFromFile(ACCEPTED_EPOCH_FILENAME);
           } catch(FileNotFoundException e) {
           	// pick a reasonable epoch number
           	// this should only happen once when moving to a
           	// new code version
           	acceptedEpoch = epochOfZxid;
           	LOG.info(ACCEPTED_EPOCH_FILENAME
           	        + " not found! Creating with a reasonable default of {}. This should only happen when you are upgrading your installation",
           	        acceptedEpoch);
           	writeLongToFile(ACCEPTED_EPOCH_FILENAME, acceptedEpoch);
           }

启动 ServerCnxnFactory 线程

ServerCnxnFacotry 是管理 ServerCnxn 处理类的工厂,它负责对 connection 上数据处理的调度,以及 server 级别的一些处理,例如关闭指定 session 等。有关 ServerCnxnFactory 的实现类，可分为三种情况：

• NIO 模式。这是 Zookeeper 默认的 ServerCnxnFactory 实现，其实现类为 NIOServerCnxnFactory。
• Netty 模式。在 Zookeeper 3.4 以后引入了 Netty 作为 Server 端连接处理的可选实现。Netty 是一套非常高效的异步通信框架。可以通过 JVM 参数 zookeeper.serverCnxnFactory 进行配置。
• 自定义模型。Zookeeper 还支持自定类来实现通信，同样可以通过 JVM 参数 zookeeper.serverCnxnFactory 进行配置。

Static public ServerCnxnFactory createFactory() throws IOException {
        String serverCnxnFactoryName =
            System.getProperty(ZOOKEEPER_SERVER_CNXN_FACTORY);
        if (serverCnxnFactoryName == null) {
            serverCnxnFactoryName = NIOServerCnxnFactory.class.getName();
        }
        try {
            return (ServerCnxnFactory) Class.forName(serverCnxnFactoryName)
                                                .newInstance();
        } catch (Exception e) {
            IOException ioe = new IOException("Couldn't instantiate "
                    + serverCnxnFactoryName);
            ioe.initCause(e);
            throw ioe;
        }
    }

ServerCnxnFactory 的主要职责：

1. 在单机模式下，引导完成 Zookeeper Server 的实例化。
2. 异步接收 Client 的 IO 连接，并维护连接的 IO 操作，这是 ServerCnxnFactory 的核心功能。ServerCnxnFacotry 本身被设计成一个 Thread，在完成初始化工作之后，就开始启动自身线程，在线程 run 方法中，采用 NIO 的方式 Accept 客户端连接，创建一个 NIOServerCnxn 实例，此实例和普通的 NIO 设计思路一样，它持有当前连接的 Channel 句柄和 Buffer 队列，最终将此 NIOServerCnxn 放入 Factory 内部的一个 set 中，以便此后对链接信息进行查询和操作(比如关闭操作,IO 中 read 和 write 操作等)。

Leader 选举

Leader 的选举算法有三种：

• LeaderElection：LeaderElection 采用的是 fast paxos 算法的一种简单实现，目前该算法在 3.4 以后已经建议弃用。
• FastLeaderElection：FastLeaderElection 是标准的 fast paxos 的实现，这是目前 Zookeeper 默认的 Leader 选举算法。
• AuthFastLeaderElection：AuthFastLeaderElection 算法同 FastLeaderElection 算法基本一致，只是在消息中加入了认证信息，该算法在最新的 Zookeeper 中也建议弃用。

Leader 选举算法分析详见：Zookeeper 源码分析-Zookeeper Leader 选举算法

QuorumPeer 启动

完成 DataDir，ZKDatabase 加载以及 Leader 选举动作后，QuorumPeer 完成初始化及启动工作。

参考资料

http://zookeeper.apache.org/doc/r3.4.6/zookeeperInternals.html

http://shift-alt-ctrl.iteye.com/blog/1846507

本文主要介绍 Zookeeper 的数据模型，包括 Zookeeper 的数据视图，节点类型以及节点所包含的信息。

节点

Zookeeper 的数据视图采用的是类似 Unix 的数据视图，但是并没有引入文件系统的相关概念：目录和文件，而是引入了节点的概念，称为 Znode。它是 Zookeeper 最小的组成单元，每个 Znode 包含三部分组成：

• data：表示节点所存储的数据，单个节点存储数据不能超过 1M。
• stat：表示节点的信息，例如节点创建时间，节点的版本，节点的权限等信息。
• children:表是所包含的子节点。

节点类型

Zookeeper 中的节点类型可以分为三种：

• 持久节点（Perisient Node），这类节点在创建之后将一直存在，知道有客户端对它进行显示删除，也就是说它不会因为创建其的 client 的关闭而消失。
• 临时节点（Ephemeral Node），这类节点的生命周期与创建它们的 client 绑定。也就是说当 client 的 session 关闭时，其所创建的临时节点也将被删除。这里有一点需要注意的是 session 关闭，而不是 connection loss。因为 zookeeper 的 client 支持 session 转移，也就是当所连接的 server 出现网络连接断开或者 server down 掉的情况，client 将自动选择 zookeeper 集群中的其他节点进行连接，同时将 session 转移到其他节点上。这种情况只能算 connection loss，而不会造成 session 关闭。除非，该 client 无法连接所有的节点，支持 session timeout。
• 时序节点（Sequential Node）,这类节点在创建节点的时候，zookeeper 会自动为其添加一个数字后缀%10d，例如/test-0000000001。不过这类节点是不能单独存在的，需要同持久节点或临时节点组合使用形成：
  • Perisient Sequential Node
  • Ephemeral Sequential Node

节点信息

Znode 的信息包含下面一些字段：

Note:zxid = znode transaction id

查看节点信息，可以使用 zkCli 中的 get 命令。

[zk: localhost:2181(CONNECTED) 15] get /zk_test
my_data
cZxid = 0x8
ctime = Sun Sep 14 14:43:56 CST 2014
mZxid = 0x8
mtime = Sun Sep 14 14:43:56 CST 2014
pZxid = 0x10
cversion = 2
dataVersion = 0
aclVersion = 0
ephemeralOwner = 0x0
dataLength = 7
numChildren = 2

源码下载

git clone https://github.com/apache/zookeeper.git

源码编译

Zookeeper 的代码构建采用的是，所以可以直接使用 ant 命令进行编译。

ant

Unit Tests

ant -Djavac.args="-Xlint -Xmaxwarns 1000" clean test tar

Troubleshooting

1.在运行 unit test 的时候出现

create-cppunit-configure:
 [exec] configure.ac:37: warning: macro 'AM_PATH_CPPUNIT' not found in library
 [exec] configure.ac:37: error: possibly undefined macro: AM_PATH_CPPUNIT
 [exec] If this token and others are legitimate, please use m4_pattern_allow.
 [exec] See the Autoconf documentation.
 [exec] configure.ac:57: error: possibly undefined macro: AC_PROG_LIBTOOL
 [exec] autoreconf: /usr/bin/autoconf failed with exit status: 1

解决方法：

sudo apt-get install libtool

2.在运行 unit test 的时候出现

create-cppunit-configure:
 [mkdir] Created dir: /home/killua/Workspace/zookeeper/build/test/test-cppunit
 [exec] checking for doxygen... no
 [exec] checking for perl... /usr/bin/perl
 [exec] checking for dot... no
 [exec] configure: error: cannot find install-sh, install.sh, or shtool in "/home/killua/Workspace/zookeeper/src/c" "/home/killua/Workspace/zookeeper/src/c/.." "/home/killua/Workspace/zookeeper/src/c/../.."

解决方法：

sudo apt-get install doxygen
sudo apt-get install perl
sudo apt-get install shtool
sudo apt-get install graphviz
sudo apt-get install libcppunit-dev