諺
Zookeeper-内部树的实现
2016-09-26 / modified at 2022-04-04 / 1.7k words / 6 mins
️This article has been over 2 years since the last update.

本文首先介绍了Zookeeper的应用、接着叙述了zk的端到端流程，最后讲解了Zookeeper中数据结构DataTree的实现方法。

本文读者：对分布式应用框架Zookeeper有兴趣了解的开发者。

本文环境：

  • Zookeeper版本：3.5.2
  • 运行模式：Standalone，无鉴权
  • 工具：Clion/Ant/Intellij Idea

下载完源码后，在当前目录下运行ant -p build.xml，它将列举所有的任务。执行你想要的命令，比如ant eclipse，它将自动生成.project等文件，这时你就可以用Idea等工具导入项目了。

Ant下载速度非常慢，你可能需要cow作为ant的前置代理工具

1. Zookeeper的介绍

Zookeeper(以下简称zk)是一款分布式协同工作集中管理的服务。看起来有点拗口，也难以理解，其实你可以把它当成Windows上的注册表就简单了——Zookeeper的名词本身就有这个含义：让动物园里的各种动物景然有序。如果你曾经在Windows优化大师的时代折腾过注册表，那么你对zk的理解将更加容易。

Windows 的“配置”，全都记录在一个中央数据库（注册表）里面，这样程序的配置得到大大的简化。虽然在 Win95 的年代，注册表貌似老是惹麻烦，但现在基本上没有什么问题了。相反，Unix 的配置，全都记录在各种稀奇古怪的配置文件里面，分布在系统的各个地方。你搞不清楚哪个配置文件记录了你想要的信息。每个配置文件连语法都不一样！这就是为什么用 Unix 的公司总是需要一个“系统管理员”，因为软件工程师们才懒得记这些麻烦的东西。——王垠《谈 Linux，Windows 和 Mac》

举个例子，下面是zk维护的数据结构：

1
2
3
4
5
6
7
8
／
----／ChildPath
--------/Node1
--------/Node2
------------/Node3
----／ChildPath2
--------/ChildPath3
------------/Node3

说了这么多，那么zk有什么用呢？

  • Naming service：通过基于树的命名服务，支持发布、订阅，并能够与Spring集成实现微服务。具体点就是可以将接口与实现类注册发布，约定好传输语法(HTTP、私有Socket、反射调用等)与抽象语法（比如SDL、SOAP、或者自己编写的DSL），就可以实现跨进程路由与通信，比如分布式计算、分布式数据库等。
  • Configuration management：用来集成配置(properties)属性，这样可以实现代码与配置分离，避免硬编码或者读取文件。
  • Message Queue：实现了消息队列，比如Apache Kafka就通过利用zk的通知功能进行主动消费，这里有更详细的介绍。

因为本文只分析单机版，主要分析内部数据结构，关于zk高级特性比如集群选举之类的晚点再开文章写。

2. Zookeeper的端到端流程

2.1. 客户端流程:

  1. 接收用户来自Terminal的标准输入请求，比如“ls /”，并跳转到相应的处理函数中

  2. 创建Socket报文，将命令序列化，包括Header与Body

    1
    2
    3
    4
    5
    //serialize "xid" "type"
    //xid: 事件
    rc = serialize_RequestHeader(oa, "header", &h);
    //serialize "path" "watch"
    rc = rc < 0 ? rc : serialize_GetChildrenRequest(oa, "req", &req);

  3. 将请求发入队列，这里使用了poll的机制去轮询寻找POLLOUT，也就是可写入的socket

  4. 通过系统调用send发送到服务端

以上分析的基于C的ClientAPI，当然还有Java版、Node版的API，都是一个套路，这里就不分析了。

2.2. 服务端流程：

当用户启动./zkServer.sh start时，实际启动的是下面的文件

1
org.apache.zookeeper.server.quorum.QuorumPeerMain /usr/local/etc/zookeeper/zoo.cfg

最终调用栈调用的是NIOServerCnxnFactory的Ruunable接口，即run方法，它将在2181端口通过Select系统调用轮询并处理Socket请求。

当客户端发送ls /等常规请求后，将调用这里的函数进行处理

1
2
3
4
private void readRequest() throws IOException {
  	//处理数据报文
    zkServer.processPacket(this, incomingBuffer);
}

Zookeeper将会把请求进入队列LinkedBlockingQueue中，即先进先出，最终先后在PrepRequestProcessor与FinalRequestProcessor中对数据进行实际的业务处理。

▶︎ 在zk中，通过Apache Jute (Hadoop Record Compiler) 作为通信类（比如ls,create等）的元数据，它定义内部序列化与反序列化的实现，并能够通过元数据编译器生成Java对象。这里就不详细说了。如果你对它有兴趣，可以用它来做一个Wireshark的zookeeper协议解码插件。

▶︎ 你可以在FinalRequestProcessor的switch (request.type)位置打断点，进而了解它的操作流程

3. Zookeeper内部数据结构的维护

Zookeeper中通过ZKDatabase实现数据管理，它在内存中维护着一个DataTree，内部通过Hash对Tree进行索引。看清楚了这里是Hash而不是当初数据结构书中那样通过链表层层嵌套指针来实现树。

下图展现了Zookeeper日常存储的方法，图左为key，图右为value

1
2
3
4
"/" => Node1
"/zookeeper" => Node2
"/zookeeper/child" => Node3
"/zookeeper/child2" => Node4

当你在cli端调用 get /zookeeper/child时，它将会在后台通过key-value的形式，即查询map.get("/zookeeper/child")并返回DataNode数据

具体的结构如下

1
2
3
4
5
6
7
8
public class DataTree {
    /**
     * This hashtable provides a fast lookup to the datanodes. The tree is the
     * source of truth and is where all the locking occurs
     */
    private final ConcurrentHashMap<String, DataNode> nodes =
        new ConcurrentHashMap<String, DataNode>();
}

ConcurrentHashMap的put操作中没有对class或者method加锁，而是只对桶(BLOCK)加了锁，粒度非常低，进而提高并发性能。这个在JDK8改动很大，是个难点。

DataNode作为Map的Value，是保存数据的节点，如下图这样构造

1
2
3
4
5
6
7
8
9
public class DataNode implements Record {
    DataNode parent;
  	//当你调用`create /zookeeper/test testdata`时，这里的
    //data[]就保留你的"testdata"字符串
    byte data[];
    Long acl;
    public StatPersisted stat;
    private Set<String> children = null;
}

因此，用户在cli端进行get ${path}, create ${pata} $data之类的操作时，实际上就是在远程操作一个HashMap，Zookeeper内部并没有像想象中使用红黑树等高大上的结构，而是使用最简单的Hash表来实现。

通过Hash表进行索引自然有它的好处，程序的get/set时间复杂度降低到了常数级别，但是它牺牲了空间——你可以看出，上图的树根/zookeeper字符串在每个节点中都有冗余。

4. TODO

晚点将继续写：

  • zookeeper的watcher机制
  • zookeeper的多机场景下的选举与缓存一致的实现
  • ConcurrentHashMap的内部put/get实现

5. REFFERENCE

  1. http://www.tutorialspoint.com/zookeeper/zookeeper_cli.htm
  2. 《ZooKeeper:分布式过程协同技术详解》