DAG（有向无环图）其实是一种数据结构，该结构以前经常用于描述分布式计算任务，直到2013年被希伯来大学的学者引入到区块链中，用于描述交易之间的关系。
除非是专业人员，不然在听到DAG图的时候，大概都没什么概念。今天就大胆尝试一把，冒着被喷的风险，用小故事来帮助大家理解DAG图，并分析DAG图在PalletOne中的使用
1、啥是DAG？
先来点专业的解释来撑撑门面，所谓DAG是Directed Acyclic Graph的首字母缩写，一般翻译为有向无环图，这里有三个关键词：有向、无环、图。
在计算机的数据结构中，把由顶点和边组成的数据结构称之为图，如果顶点与顶点之间存在前后关系，则称之为有向，如果在顶点与顶点之间按照前后关系进行遍历时，不存在环路，则称之为无环。
为了清楚，咱们还是先看个图吧，下图就是有向无环图和有向有环图的区别，是不是很直观呀？这种图可以用来描述一个关系，下面咱们就用一个例子来说明有向无环图的性能和一致性问题。
问题：某高中门卫张大爷今天上班的时候睡着了，所以他不清楚今天来了多少学生，于是安排王校长去清点一下整个学校的学生人数。
为了给王大爷点清人数，王校长通知了各级部主任和班主任来开会，并打算通过以下方式来进行人数的查点。
方式一：王校长带着所有级部主任和班主任，从高一（1班~27班），高二（1班~25班），高三（1班~26班）挨个班级数一遍，当超过一定数量的老师数出该班级的人数相同时，则该班级人数确定，并累加到总人数上。（类似区块链的单链，把每个班级实到人数看成交易数据，则只能一个一个确认），如下图所示：
方式二：由各班主任分别统计各班人数，各级部主任负责验证和统计各班主任的数据，校长负责验证和统计各级部主任的数据。（类似DAG结构的多链，把每个班级实到人数看成是交易数据，则可以并行确认，但有前后关系），如下图所示：
不论是方式一，还是方式二，验证完人数以后，就可以把最后的结果告知门卫张大爷了。不过从图中也可以看出，方式一明显比方式二要花费更多的时间，但也更有安全性。这就是区块链中的不可能三角啦！区块链在即可扩展性、去中心化、安全性这三者之间只能权衡，不能同时满足。
2、PalletOne中的DAG
PalletOne中的DAG图是采用上面方式二所示的图型结构，图中的每个节点都是一个交易单元，这些交易单元包括以下几种：
（1）创世单元，也称为G单元，该单元由创世交易构建，该单元没有父单元，是DAG图遍历的起点，所有后续单元都可以回溯到该单元。
（2）父单元和子单元，是一种相对的关系，从单元A出发可直接到达单元B，则称B为A的父单元，也可称A为B的子单元。
（3）顶端单元，不具有任何子单元的单元，也可称为未经验证的单元。
在PalletOne中新单元形成的过程中是可以选择父单元的，而咱们举得清点人数的例子中，父子节点间的关系是固定的。在PalletOne中的父单元选择主要分两种情况：
（1）认证单元的父单元是直接引用被认证的交易单元。
（2）非认证单元（例如：普通交易单元、合约模板部署单元和合约创建单元等等）的父单元是采用就近原则，根据单元哈希排序，然后尽可能选择较小的单元为父单元，其目的是为了将DAG进行收敛，最后可以形成一条链。
3、写在最后
使用DAG类的拓扑结构来存储区块链中的交易数据，可以有效解决区块链的效率问题。传统的区块链只有一条单链，所有的打包和出块只能单步完成，无法并发执行。
PalletOne旨在打造高性能的跨链平台，其采用的DAG网状拓扑可以在保证安全性的前提下并发写入，在打包时间不变的情况下，网络可以并行打包多个交易，从而使得处理效率也提高多倍。
举生活中的例子是一种简化的表达方式，在真实系统的应用中要复杂很多，只是为了方便大家对技术有一个直观的认识，有什么不对的地方，欢迎大佬们批评指正哈！
网友评论