我们都知道 zookeeper 使用了树状结构来管理它的 ZNode, 无数中间件使用 zookeeper 的 ZNode 组织并管理了具有层次关系的数据结构;
本文将探究 zookeeper ZNode 树状结构的实现方式及原理;

在 ZooKeeper 中，ZNode 是数据存储的基本单元，每个 ZNode 可以存储数据并关联一组子节点; ZNode 的具体数据结构设计得非常简洁，但功能强大，能够支持 ZooKeeper 的核心功能，如数据存储、事件通知和分布式协调;

ZNode 的数据结构

ZNode 的数据结构主要包括以下字段：

data

  • 类型：byte[]（字节数组）
  • 作用：存储 ZNode 的实际数据。
  • 说明：ZooKeeper 不限制数据的格式，用户可以存储任意二进制数据。

acl

  • 类型：List<ACL>（访问控制列表）
  • 作用：定义 ZNode 的访问权限。
  • 说明：ACL 包含权限（如读、写、创建、删除等）和授权对象（如用户、IP 地址等）。

stat

  • 类型：Stat（状态信息）
  • 作用：存储 ZNode 的元数据信息。
  • 说明：Stat 结构包含以下字段：
    • czxid：创建该 ZNode 的事务 ID（ZXID）
    • mzxid：最后一次修改该 ZNode 的事务 ID（ZXID）
    • pzxid：最后一次修改子节点的事务 ID（ZXID）
    • ctime：ZNode 的创建时间（毫秒）。
    • mtime：ZNode 的最后修改时间（毫秒）。
    • version：ZNode 的数据版本号（每次数据更新时递增）。
    • cversion：ZNode 的子节点版本号（每次子节点变化时递增）。
    • aversion：ZNode 的 ACL 版本号（每次 ACL 更新时递增）。
    • ephemeralOwner：如果 ZNode 是临时节点，存储其所有者的会话 ID；否则为 0。
    • dataLength：ZNode 数据的长度。
    • numChildren：ZNode 的子节点数量。

children

  • 类型：Set<String>（子节点集合）
  • 作用：存储 ZNode 的子节点名称;
  • 说明：ZNode 可以包含多个子节点，形成树状结构;

 
假设有一个 ZNode /app/config，其数据结构可能如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
data: "key=value" (二进制数据)
acl: [{"perms": 31, "id": {"scheme": "world", "id": "anyone"}}] (允许所有用户读写)
stat: {
  czxid: 0x100000001,
  mzxid: 0x100000002,
  pzxid: 0x100000001,
  ctime: 1698765432000,
  mtime: 1698765433000,
  version: 1,
  cversion: 0,
  aversion: 1,
  ephemeralOwner: 0,
  dataLength: 9,
  numChildren: 0
}
children: ["/app/config/boot", "/app/config/runtime"]

ZNode 的索引机制

DataTree

ZooKeeper 使用对象 DataTree 来存储所有的 ZNode:

  • Map<String, DataNode>:
    • String 是 ZNode 的路径（如 /app/config）;
    • DataNode 是 ZNode 的实际数据;

假设 DataTree 中有以下 ZNode:

1
2
3
4
5
6
7
/
  /app
    /app/config
    /app/logs
  /users
    /users/alice
    /users/bob

DataTree 的内部存储如下：

1
2
3
4
5
6
7
8
Map<String, DataNode>:
  "/" -> DataNode {data: null, children: ["/app", "/users"]}
  "/app" -> DataNode {data: null, children: ["/app/config", "/app/logs"]}
  "/app/config" -> DataNode {data: "key=value", children: []}
  "/app/logs" -> DataNode {data: null, children: []}
  "/users" -> DataNode {data: null, children: ["/users/alice", "/users/bob"]}
  "/users/alice" -> DataNode {data: "role=admin", children: []}
  "/users/bob" -> DataNode {data: "role=user", children: []}

如需遍历整个 ZNode 树, 只需递归获取 children 后再次从 DataTree 查询即可;

临时节点管理

  • Map<Long, Set<String>>:
    • Long 是客户端会话 ID。
    • Set<String> 是该会话创建的所有临时节点的路径。
  • 特点：
    • 用于管理临时节点，当会话结束时自动删除相关临时节点。

Watcher 管理

  • Map<String, Set<Watcher>>:
    • String 是 ZNode 的路径。
    • Set<Watcher> 是监听该 ZNode 的所有 Watcher。
  • 特点：
    • 用于实现事件通知机制，当 ZNode 发生变化时触发 Watcher。

举例如下:

  1. 客户端变更
    • 客户端调用 create(“/app/config”, data);
    • zk 在 /app 下创建子节点 /app/config;
  2. DataTree 更新
    • ZooKeeper 更新 /app 的以下字段:
      • cversion：递增;
      • pzxid：更新为当前事务的 ZXID;
      • children：将 /app/config 添加到子节点集合中;
  3. Watcher 触发
    • 根据路径 /app/config 解析出其父节点为 /app;
    • 如果客户端注册了监听 /app 的 children 变更的 Watcher, ZooKeeper 会执行以下步骤:
      • 从 Watcher 管理 Map 中查找 /app 对应的 Watcher 集合;
      • 遍历 Watcher 集合, 依次触发每个 Watcher 的 process(WatchedEvent event) 方法, 其中事件类型为 EventType.NodeChildrenChanged;