DEEP DIVE: DAG

DAG（有向无环图）详解：既非链条也非树，而是表达因果的结构

Git 的提交历史、IPFS 用来捆绑内容的 Merkle DAG，还有试图把区块链从「一条链」拓展成「一张网」的 Tangle、GHOSTDAG 之类的账本，归根结底都建立在同一种结构之上，即 DAG（Directed Acyclic Graph，有向无环图）。「沿着边走下去，永远不会回到出发点」这一条简单的约束，为什么恰好成了表达分布式系统中因果关系的自然语言？本文从定义到具体案例逐一详解。

DAG 是什么：定义与拓扑排序

DAG（有向无环图）顾名思义由两部分构成：它是一个有向图（节点之间的边带有方向），同时又是无环的（无论沿着边走多远，都不存在一条路径能回到出发的那个节点）。「顺着某节点的后代一路走下去，最终又绕回这个节点本身」这种情况绝不会发生，这正是「无环」的含义，也正因如此，DAG 中的每条边在某种意义上都只能「从前指向后」。

它与树的区别，关键在于一个节点能否拥有多个父节点。在树中，每个节点恰好有一个父节点（根节点为零个），路径可以分叉，但绝不会再次汇合。DAG 解除了这一限制，允许多条路径汇聚（converge）到同一个节点。可以说树只是 DAG 的一种特例，反过来讲，DAG 是比树表达能力更强的结构。

拓扑排序必然存在：一个有向图存在拓扑排序（即把所有节点排成一列，使每条边都从靠前的节点指向靠后的节点）当且仅当该图是无环的。因此任意 DAG 至少存在一种拓扑排序。
可达性构成一个半序（partial order）：若沿着边可以从节点 A 到达节点 B，就定义「A ≤ B」，这一关系满足自反性、反对称性与传递性，构成一个半序。正因为无环，反对称性（若 A ≤ B 且 B ≤ A，则 A = B）才得以成立。
为什么是「半」序：与全序不同，半序并不要求任意两个节点都可比较。彼此之间不存在祖先与后代的关系的两个节点被称为「并发（concurrent）」，谁先谁后无从谈起。
拓扑排序并不唯一：同一个 DAG 可能存在多种合法的拓扑排序。若某个场景需要「唯一正确的顺序」，就必须在 DAG 之外另行引入一套排序规则。

分布式系统为何需要 DAG：因果关系构成的半序

分布式系统中不存在一个所有节点共享的物理全局时钟，因此原则上无法在没有外部观察者的情况下，为「所有事件究竟按什么顺序发生」这一问题确定一个唯一的全序。但可以确定的是，某个事件是否有可能是另一个事件的原因，也就是因果关系。Leslie Lamport 在 1978 年的论文《Time, Clocks, and the Ordering of Events in a Distributed System》中，将这一关系形式化为happened-before 关系（记作 →）。它是一个半序而非全序：若 A 与 B 之间互不构成 happened-before 关系，二者便是并发（concurrent）的。

真正用来计算 happened-before 关系的机制是向量时钟（vector clock）（Fidge 与 Mattern 于 1988 年各自独立提出）。每个节点维护一个向量，记录「自己观察到的其他各节点事件的数量」，并在每次收发消息时更新。这套机制在暗中构建出的，恰恰就是一张以事件为节点、以直接因果依赖为边的 DAG。换句话说，DAG 并非为表达分布式系统中的因果关系而专门发明的工具，它不过是 happened-before 关系本身所具有的数学结构的直观呈现。

不强行串行化本无关联的操作：若强制要求全序，本来互不相关的操作也要相互等待，网络分区发生时更会陷入停滞。DAG 只对确实存在依赖的部分排序，让相互独立的部分保持并发。
与流言协议天然契合：在流言协议的异步信息传播中，每个节点可以直接按照自己收到更新的顺序拼出因果图，无需等待所有内容排成一条全序队列。

DAG 的实际案例

Git：提交 DAG

每一次提交都持有指向父提交哈希的指针。通常只有一个父节点，但合并提交（merge commit）会拥有两个（或更多）父节点，把分头演进的多条分支历史汇合成一个节点。「分支」这一概念本身并非独立的结构，只是指向某个具体提交的可变指针（ref）而已。git log --graph 展示的正是这张提交 DAG 的可视化结果。

IPFS 的 Merkle DAG

正如Merkle 树详解中所述，IPFS 把内容切分成若干块，并通过「以哈希指向子节点」的链接方式把它们捆绑起来。这种链接方式从原理上就杜绝了成环的可能：节点 B 要成为节点 A 的子节点，B 的哈希必须在构建 A 的那一刻就已经确定，B 不可能在之后反过来指向 A、形成一个环。由于内容相同的数据块始终具有相同的哈希，把结构设计成允许多个父节点的 DAG 而非树，也就自然而然地实现了去重（deduplication）。

DAG 型账本：把区块链从「链」拓展为「网」

单链结构的区块链在某一时刻若同时出现多个候选区块，最终会通过最长链之类的分叉选择规则只保留其中一条，其余的则被丢弃。DAG 型账本反其道而行之：不丢弃并发提出的多个区块或交易，而是把它们全部纳入图中，再另行制定一套排序规则，来决定其中哪一部分才算作正式历史。

IOTA 的 Tangle：新交易在发布时需要验证并「批准」此前两笔交易。不以区块为单位打包，而是每笔交易都直接连入 DAG，目的是让处理能力随参与者增多而提升。
GHOSTDAG（Kaspa）：由 Yonatan Sompolinsky 与 Aviv Zohar 提出的协议，把工作量证明并发产生的多个区块（blockDAG）全部纳入而非丢弃，并给出一套排序规则，从区块间的关系中递归地选出「主链」。其目标是在保留 Nakamoto 式工作量证明安全模型的同时缩短出块间隔、提升吞吐量。
Hashgraph：由 Leemon Baird 设计的方案，通过「流言的流言（gossip about gossip）」把事件的传播历史本身构建成一张 DAG，再仅凭这张 DAG 结构虚拟地重现投票过程（virtual voting），从而达成 aBFT（异步拜占庭容错）共识。

这些方案追求的主要是吞吐量的提升，让原本要在单链上排队等待的部分得以并行处理。但代价是共识本身也随之复杂化。判定「哪一部分子图才算正式历史」的排序规则，其安全性分析要比简单的最长链规则复杂得多，也进一步抬高了分布式共识在设计与验证上的难度。

CRDT 与操作的因果 DAG

在支持多人离线协同编辑的系统（CRDT，Conflict-free Replicated Data Type，无冲突复制数据类型）中，每一次编辑操作都会连同「它发生在哪次操作之后」这一因果依赖关系一并记录下来，并将其视作一张 DAG。所谓合并，就是把两个副本各自持有的操作 DAG 取并集，对于彼此不存在祖先与后代的关系（即并发）的操作，再用一套确定性的优先规则来化解冲突。高效比对这张因果 DAG 的副本同步机制，往往与流言协议的 anti-entropy 机制结合实现。去中心化社交协议 AT Protocol（Bluesky）的仓库结构同样呈现出 DAG 式的历史：每次提交都指向父提交的哈希，形成一条链式历史，并与存放具体记录的 Merkle Search Tree 结合在一起。

DAG 并不只局限于分布式账本或协同编辑。make、Bazel 之类的构建系统把任务之间的依赖关系表示成 DAG，用拓扑排序来决定构建顺序；npm、apt 之类的包管理器同样把依赖包之间的关系当作 DAG 来求解，一旦检测到循环依赖便会拒绝安装。DAG 其实就活在许多日常之处。

链、树、DAG 的结构对比

维度	链（区块链）	树（Merkle Tree）	DAG
节点的父节点数量	始终为 1（单一路径）	始终为 1（向上收敛至根）	可以有多个父节点（允许汇合）
结构	线性的全序	层级化的半序（从根到叶）	一般化的半序（可能存在多种拓扑排序）
如何处理分叉	按最长链等规则只保留一条，其余丢弃	结构是静态的，通常不存在「分叉」这一概念	不丢弃分叉，全部纳入，再靠排序规则解决
擅长的事情	简单的共识（确定一个全序）	对固定数据集进行高效的包含证明	表达因果关系、容忍并发更新、提升吞吐量
代表案例	Bitcoin 的区块链	Merkle Tree、Git 的 tree 对象	Git 的提交历史、IPFS 的 Merkle DAG、Tangle、GHOSTDAG

常见误解与注意事项

「DAG 总是优于区块链」是误解：DAG 在吞吐量与并发性上确有优势，但判定「哪一部分子图算作正式历史」的共识规则，其安全性分析往往比单一链条更复杂。事实上，早期部分 DAG 型账本一度依赖中心化机制来保障安全性。
「用了 DAG 就意味着无法篡改」也是误解：防篡改能力并非来自图本身的形状，而是由哈希函数的抗碰撞性、签名机制，以及分布式共识或最终性（finality）机制共同保障的。DAG 只是表达因果关系的容器，本身并不能保证任何安全属性。
「拓扑排序是唯一确定的」也是误解：同一张 DAG 可能存在多种合法的拓扑排序。凡是需要「唯一正史」的场景，都必须在 DAG 之外另行补充一套排序规则，例如 GHOSTDAG 的排序规则。
「Merkle DAG」与「DAG 型账本」并非一回事：像 IPFS、Git 那样用哈希把数据捆绑起来的 Merkle DAG（作为一种数据结构使用），与 Tangle、GHOSTDAG 那样的 DAG 型账本（作为一种共识架构使用），虽然都借用了同一个图论概念，但目的与设计截然不同，不应混为一谈。