这两天看完了zk单实例模式的大部分源码，发现分析源码有两个最重要的点：大学时软件工程导论上说的一句话：程序=算法+数据结构，当时不甚明白，在工作中的体会越来越深。
入口就在zk自带的几个shell文件里，shell里会设置环境变量，调用特定的类的main方法。
zkServer.sh对应的入口是org.apache.zookeeper.server.quorum.QuorumPeerMain
一切都要先从zk的运行时状态开始。一个程序肯定会记录运行时的状态，就会有对应的数据结构。
整个运行时状态用ZKDatabase类表示，ZKDatabase里的关键数据结构：
1， DataTree dataTree：表示当前zk的所有节点。
2，ConcurrentHashMap<Long, Integer> sessionsWithTimeouts：记录当前所有的session id及对应的超时时间。
3， FileTxnSnapLog snapLog：表示事务log和状态镜像的工厂类。
4， LinkedList<Proposal> committedLog：维护最新的500个Proposal，跟集群模式有关，稍后分析。
DataTree结构：
1，ConcurrentHashMap<String, DataNode> nodes：记录当前每一个节点的绝对路径。
2，WatchManager dataWatches：记录所有的监控create/delete/setData/setAcl的watcher
HashMap<String, HashSet<Watcher>> watchTable：记录每个绝对路径对应的watcher
HashMap<Watcher, HashSet<String>> watch2Paths：记录每个watcher监控的节点
两个map同时维护状态，方便查找。
3，WatchManager childWatches：记录所有的监控子节点增删的watcher
4， PathTrie pTrie：记录所有设置了限额的节点路径。所谓限额，就是限制一个节点及其所有后代节点的数量和数据(DataNode.data)之和占用的空间。限额值保存在/zookeeper/quota + fullpath + zookeeper_limits，当前的状态保存在/zookeeper/quota + fullpath + zookeeper_stats，每次增删节点，都要先查找祖先节点是否在PathTrie上，如果在，找到距离增删的节点路径最短的祖先，更新它在/zookeeper/quota下的状态节点的值。每次维护状态节点的数据都会检查是否超过对应的限额节点，如果超过了，只是记录一条警告log！！！
5， Map<Long, HashSet<String>> ephemerals：记录每个session id对应的瞬时节点的绝对路径的集合
6， ReferenceCountedACLCache aclCache：每个节点的acl权限列表比较占空间，且重复的比较多，所以使用了缓存，把每个acl列表跟一个索引关联。结构非常简单：
Map<Long, List<ACL>> longKeyMap：记录每个索引对应的权限列表
Map<List<ACL>, Long> aclKeyMap：记录每个权限列表对应的索引，两个map一起维护，方便查找。
Map<Long, AtomicLongWithEquals> referenceCounter：这就跟它的气质符合了，引用计数，记录每个索引被引用的次数，引用归0，从上面两个map里剔除。
DataNode结构：核心数据结构之一
1，DataNode parent：父节点
2，Set<String> children：子节点相对路径集合，这俩属性终于符合tree的气质了。
3，byte data[]：节点存储的数据
4，Long acl：aclCache中的索引
5，StatPersisted stat：节点状态，一共9个属性，时刻维护DataNode一生的状态。
long czxid; // 创建此节点时的zxid
long mzxid; // 上次修改此节点时的zxid
long ctime; // 创建此节点时的时间戳
long mtime; // 上次修改此节点时的时间戳
int version； // 数据版本号 用于setdata时乐观锁判断
int cversion; // 子节点版本号 用于创建删除子节点时乐观锁判断
int aversion; // acl权限版本号 用于setacl时乐观锁判断
long ephemeralOwner; // 瞬时节点对应的session id
long pzxid; // 添加或删除子节点时的zxid
FileTxnSnapLog表示ZKDatabase和构造ZKDatabase的所有事务log序列化到文件的形式。
1， File dataDir：配置文件中dataLogDir对应的目录，用于存放事务log
2， FilesnapDir：配置文件中dataDir对应的目录，用于存放ZKDatabase的状态镜像。
3，TxnLog txnLog：事务log序列化反序列化查找相关操作，每一条修改SnapShot的指令都会记录一条事务log，类似mysql的bin log。
4， SnapShot snapLog：状态镜像相关序列化反序列化操作，包含三部分：FileHeader(版本号，magic word之类的，可以检查文件类型) + zkdb.sessionsWithTimeouts + zkdb.dataTree。
系统启动时先从最新的镜像还原状态，系统运行过程中周期性的生成镜像文件。
数据结构说完了，该说算法了。像zk这种，分析算法的关键在于找出有多少个线程，搞清楚每个线程的任务是啥。
下面跟随zk单实例server启动的过程分析每个线程的职责：
1，单实例的入口在ZooKeeperServerMain类的main方法，解析完配置文件之后，根据配置文件设置ZooKeeperServer和ServerCnxnFactory。CountDownLatch的经典用法：化异步为同步，哈哈哈！！！
2， ServerCnxnFactory是用于处理client连接的网络层，根据类名反射获取实例，默认使用基于NIO的NIOServerCnxnFactory，可选使用netty或自定义。
简洁明了，就是把ServerSocketChannel注册到selector上，监听accept事件。maxClientCnxns表示每个ip的最大连接数，超过此数拒绝连接。可以看到此处构造了一个新线程。
NIOServerCnxnFactory自身实现了Runnable，start方法启动之前创建的IO线程，异步监听IO事件。
IO线程的run方法是非常经典的NIO demo。重点是accept之后的client连接被封装在了NIOServerCnxn之中，NIOServerCnxn中引用创建它的NIOServerCnxnFactory，对应client连接的SocketChannel，与channel关联的SelectionKey，ZooKeeperServer4个对象。还有两个非常重要的buffer：ByteBuffer incomingBuffer表示client请求数据缓存，LinkedBlockingQueue<ByteBuffer> outgoingBuffers表示响应数据缓存。从上图中可以看出，client连接read/write可用时，会调用NIOServerCnxn的doIO方法。
所有的zk请求都使用lv格式，4个直接表示长度，然后读取剩余字节，等读完之后直接反序列化。每个请求都对应一个Record记录， Record只定义了两个方法：serialize和deserialize，每个record负责序列化和反序列化自己。
每个client连接server时必须先发送ConnectRequest，包含当前client看到的最大zxid lastZxidSeen，超时时间timeOut(必须在2-10个ticktime范围内)，sessionId，如果lastZxidSeen大于当前zkdb的最大zxid，拒绝连接。然后调用submitRequest提交请求给请求处理线程建立session，开始监听client的read事件。如果时其他请求，先反序列化RequestHeader获取当前请求的类型，然后调用submitRequest提交给请求处理线程处理。
重点是touch，每次收到请求都会刷新session超时时间。
请求已经收到了，现在看看如何处理请求把。
要处理请求，必须先恢复当前zk server的状态。NIOServerCnxnFactory.startup时会先调用ZooKeeperServer.startdata。用于从状态镜像和事务log中恢复上次中断时的状态。
先从dataDir文件夹下找到最近的100个合法的镜像文件，镜像文件格式为snapshot.zxid，zxid表示保存此镜像时最大的zxid。每个镜像文件的最后5个字节为 0 0 0 1 /。
每个镜像文件校验crc，从crc通过校验的第一个文件反序列化出session和data tree。
保存镜像时需要时间的，保存过程中可能有新的事务发生。所以从镜像反序列化之后，应该从事务log中redo最新的事务。
先读取事务log文件里记录的zxid比镜像文件最大zxid大1的所有事务。
事务log文件的格式为log.zxid，zxid表示当时最大的zxid表示此文件里的最大事务id。取得的所有事务文件的所有事务记录里zxid比镜像最大zxid大的大的事务全部redo一遍。
最新状态已恢复，可以启动ZooKeeperServer处理请求了，ZooKeeperServer启动过程中会启动一个session追踪线程和两个请求处理线程。
SessionTrackerImpl有3个map维护状态：
HashMap<Long, SessionImpl> sessionsById：记录每个sessionid对应的session。
HashMap<Long, SessionSet> sessionSets：记录过期时刻相同的session。所有的过期时刻都是ticktime的倍数，每过ticktime检查一下当前时间点要过期的session。从session建立时开始，根据session timeout计算比某个过期时间检查点大的最小过期时间点(time / ticktime +1) *ticktime。加入对应的sessionSets里，如果过期之前有新的请求，刷新sessioin，重新计算过期时间点。
ConcurrentHashMap<Long, Integer> sessionsWithTimeout记录每个session对应的超时时间。
请求处理线程是一个单链表结构，有多个环节构成，firstProcessor是链表头，按顺序如下：
PrepRequestProcessor：请求预处理，关键状态LinkedBlockingQueue<Request>表示请求任务队列。IO线程读取请求之后放入此队列。然后run方法中，从队列里取任务，然后一个大的switch根据请求类型分别处理。PrepRequestProcessor只处理修改data tree和session相关的指令。处理指令时所有的变动并没有字节修改data tree和session，而是缓存在ZooKeeperServer的List<ChangeRecord> outstandingChanges中，同时会组装事务log。处理完之后，交给单链表的下一个处理环节处理。
每个指令的简要处理流程如下：
create：反序列化请求，检查acl，如果是创建序列节点，用"%010d"格式化parent节点的旧的cversion属性作为节点后缀。所以序列化节点的后缀永远单调递增，但是不一定连续。确认父节点不能是瞬时节点。如果是瞬时节点，设置请求关联的session id。修改parent的cversion。然后将parent节点和添加的节点放入outstandingChanges缓存。
delete：检查权限。确认没有子节点。节点数据版本号version乐观锁检查。此处竟然没有修改parent的cversion！！！然后将parent节点和添加的节点放入outstandingChanges缓存。
setdata：权限检查。节点数据版本号version乐观锁检查。version加1，将节点放入outstandingChanges缓存。
setacl：同上，只是乐观锁检查和增加的都是aversion。
createSession：建立session，开始追踪此session的过期时间。
closeSession：检查当前outstandingChanges缓存中与当前session关联的所有瞬时节点。将删除关联瞬时节点的请求加入outstandingChanges缓存。删除标识是ChangeRecord.stat=null。
SyncRequestProcessor：跟PrepRequestProcessor一样也有一个任务队列，处理PrepRequestProcessor放进来的任务。
SyncRequestProcessor的主要任务是保存outstandingChanges缓存中的每个记录的事务log到事务文件里，当事务log数量达到一定数量时，产生新的事务log文件，同时保存新的镜像到文件。然后交给链表的下一个环节处理。
FinalRequestProcessor：最后一个处理环节，把outstandingChanges缓存里的记录全部应用到对data tree和session的修改。
请求已经处理完啦，该返回响应了。
加入outgoingBuffers缓存，等待write事件发送，把缓存发送给client。
server启动时还会启动一个清理dataDir下的镜像和dataLogDir下的事务log的线程。
整个zk server的处理流程就完啦！！！！！！
