DAG——有向无环图

维基百科定义:

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图。

如下图:

DAG - 新型数据结构

其实就是指一个没有回路的有向图。

因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。

说起DAG就不得不说区块链，两者的目的都是为了形成可以信任的数据库。

目前币圈很多的分布式数据库的记账方式都在区块链和DAG之间选择。

我们下来利用DAG和链式结构的区别来更好的理解DAG。

DAG与链式结构的本质区别在于异步与同步通讯。区块链的链式结构的本质等同于数据库事务日志，而出块操作则为检查点操作，那么链式结构体系可以看做是定期同步检查点的数据库事务同步机制。

而DAG则通过将事务操作进行异步处理来增加网络吞吐量，采用谣言传播算法（类似谣言在人类社区中的传播方式）在节点间发送操作日志，并通过某种机制（IOTA每次验证前两条交易，并计算一个PoW代表权重）将一个权重赋给该操作。

相比起同步操作的链式结构，DAG结构与任何异步机制一样，能够带来的提升在于吞吐量，但是可能产生的问题则在于无法有效预测交易被确认的时间与周期，并且操作之间的顺序无法最终在多个节点间确认保持一致。

局限

由于当前市面上DAG的实现相对较新，暂时还存在一些理论上未突破的局限性，包括：

在对历史交易验证时采用随机方式，而没有任何先后规则，那么有可能产生某些交易在极端情况下没有任何其他节点对其验证，从而永远不会被确认。这个问题在IOTA中通过多次重试的方式解决，但是是否存在更好的一次性确认机制能更有效地解决该问题值得探讨；

为了追踪每一笔交易与之前交易的关系，整个DAG图谱需要被随时检索和访问。在一个较大规模的系统中其交易图谱溯源会非常复杂，同时几乎不可能被全部保存在内存中以进行实时更新。而如果将这些数据保存在磁盘上，那么实时刷新每个Tangle的权重会造成大量随机I/O（也许可以通过大量部署SSD解决），因此从工程实现上来看优化难度较大；

由于DAG的操作记录写入顺序不存在“区块”或“日志”这类检查点机制，因此每个节点各自为政，对于全局顺序无法得到保障。在这种情况下，在非等阶操作时可能存在不一致的问题（例如对同一条记录，在两个不同的节点同时执行转账（加减法）和计息（乘法）操作，两个节点得到的操作顺序有区别，导致账户余额最终结果不一致）。

如今从DAG衍生出一些其他数据结构（例如哈希树等），基本上只是从存储方式上有一些特定的优化，但是整体上与DAG所带来的问题保持一致。

展望

笔者认为，DAG的异步数据分发思路完全可以与链式结构相辅相成。

IOTA的DAG结构其中一部分就论述到如何确认一笔交易的可信度（通过累加权重），因此DAG除了是一种数据结构、网络拓扑模型和谣言传播算法以外，也是通过累加权重来实现共识的一种方式。

MIXIN采用了TEE可信执行环境下的BFT——DAG，我会持续跟踪。

欢迎留言探讨DAG。