本系列将记述使用Merkle DAG实现一个文件存储服务。这个想法并非本人原创，在本文之前，以太坊、IPFS等去中心实现中都用到了类似的想法，但令人惊奇的是，竟然没有纯粹的将这个想法作为文件存储来实现的代码。可能是意义不大吧。
本文作为整个系列的铺垫，将阐述这个需求的意义以及一些基本概念。
Merkle DAG
所谓Merkle DAG，其实分为两个部分：Merkle和DAG。DAG无需多说，是有向无环图的英文缩写。而Merkle是个人名，早年间他给这个东西注册了专利，所以才叫Merkle DAG或者Merkle tree。从技术上讲，Hash tree或者Hash DAG更直观一些。因为在这种有向无环图中使用了Hash来索引节点。最直观的理解就是把传统的DAG或者树中的指针全部替换成Hash。
对于指针，它建立了节点（Node）与成员域（Field）之间的联系，即通过域中记录的指针（内存地址）可以找到一个节点，进而对该节点进行访问。但是指针中记录的内存地址与被指向的节点不具有唯一的对应关系，原则上同一个内存地址可以是任何节点，也可以不是节点。而Hash则具有相对唯一的对应关系，某个节点的Hash由其自身的内容决定，并且微小的改变都会使得Hash的计算结果与原来大相径庭（所谓的「雪崩效应」）。
一个Merkle DAG节点可以抽象的标识成如下两种格式：
public class MerkleNode<T> {
final T data;
final List<Hash> links;
}public class MerkleNode<T> {
final T data;
final Set<Hash> links;
}这两个区别是使用List存储Hash允许节点间维持相对顺序，而Set则不保证顺序。前者适用于表示大块数据（IPFS），后者适用于组织零碎节点（ETH）。其中links存储的是子节点的Hash。
基于节点的定义，显而易见，Merkle DAG有三个特点。
首先是整个DAG构建完成后即不可变，因为任何节点的改变，都导致自身Hash的变化，进而导致父节点内容改变，从而导致父节点的Hash变化，如此传播下去，最顶层的根节点的Hash也一定会改变（假定不会撞Hash）。
第二个特点就是构造时必须自底向上构造，因为父节点要存储子节点的Hash，而子节点的Hash来源于自身的内容。因此构造时只有叶节点可以被最先计算Hash，然后逐级构造。
第三个特点就是允许复用。这并非Merkle DAG的特点，一般的DAG也可以通过共享指针来复用节点，但基于Hash的复用允许我们更直接更自信的复用节点——相同的内容产生相同的Hash，考虑到撞Hash的可能性极小（或许压根儿不需要担心碰撞），我们完全可以认为Hash相同即内容相同。这也是基于内容寻址的核心想法。
以上是Merkle DAG的原理，以下将利用IPFS和智能合约作为例子说明他们是如何使用这种DAG的。
智能合约
以太坊最近（一直）比较热门，它与比特币具有本质上的不同。比特币的核心是去中心分布式的账本，它使用节点度为1的Merkle DAG，实际上就退化成了使用Hash寻址的链表（这里省略了比特币的UTXO模型和挖矿的原理）。而以太坊除了要支持传统的交易之外，还希望引入能够根据条件自动执行的代码，即智能合约。简单回忆一下计算机组成原理，冯诺依曼结构的五大组成要素是：运算器、控制器、存储器、输入、输出。
对于区块链来说，运算器和控制器由区块链虚拟机提供，存储器有区块链提供，表现为合约的存储区，该存储区为合约专属，本质上是区块链中的一块数据，表示合约的状态。输入输出则表现为调用合约时传入的参数，以及合约正常返回时的返回值。这样我们就可以实现一个简单的支持智能合约的区块链的。
在以太坊中，运算器和控制器由EVM提供，即执行时以太坊节点根据实现约定的指令和行为对编译好的合约进行模拟执行（因为合约并不编译为x86或其他机器指令，而是EVM自定义的指令集），在调用合约时提供的参数作为输入，调用前的合约状态（合约存储区）作为存储器，用于存储持久化的数据（比如账户余额等），而合约结束后的返回值则作为输出发送给调用者。对于区块链节点来说，这个过程它只关心两个东西：调用前的合约状态和调用后的合约状态。要保证交易的可验证性，任何节点只要用同样的输入和同样的合约状态执行同样的合约代码，一定会得到同样的调用后的合约状态（假设其中不涉及预言机，Oracle，不是甲骨文）。而调用后的合约状态将在未来作为输入去验证后续的交易，至于输出，区块链节点并不关心。所以以太坊需要一种可靠并高效的机制来记录每个区块中所有合约的状态。
于是就该轮到Merkle DAG出场了。在一个区块中，Merkle DAG表现为一个树，即每一个节点表示一个合约的存储区，这些存储区使用Hash寻址，组织成一棵树。但是有些合约不见得每个块都要变，于是利用DAG复用节点的原理，如果一个合约的存储区没有变，那就不要每个块都复制一遍，不如就直接用之前的状态。由于节点间不需要维护相对顺序，所以使用Set<Hash>就可以完成任务，并且在节点数量巨大的情况下，为了提高查找效率，还可以引入前缀树等优化手段。
值得注意的是这里所说的并不完全是以太坊的工作机制，以太坊的每个区块中有三棵树，分别记录了世界状态、收据和交易。其中的数据结构根据实际需求有所变动，这里只是从解决需求和介绍Merkle DAG的角度泛泛而谈。下面有关IPFS的部分也一样，如果想要了解以太坊或IPFS的具体设计，不妨直接去阅读他们的白皮书。
IPFS
IPFS全称星际文件系统，旨在创建持久且分布式存储和共享文件的网络传输协议。它在文件存储的核心部分就是Merkle DAG。
在IPFS中，最小的数据单位是Object：
public class IPFSObject {
final IPFSLink[] links;
final byte[] data;
}
public class IPFSLink {
final String name;
final Multihash hash;
final int size;
}这是一种抽象的表示方法，可以看出这里的links和上面的List<Hash>类似，用以维护节点之前的相对顺序（毕竟数据块之前的顺序乱了，文件也有要不了了）。取决于各自的作用，Object有许多种分型。
充当DAG中叶结点的是blob，它的特点是links为空，data是要存储的数据。在存储文件时，默认的切块大小是256KB，即每个blob的data域长度为256KB。将多个blob连起来，就变成了list，它所表示的数据即将其内部的blob和list按顺序拼接起来。它的data域指明了links中对应Object的类型（blob或list），links不具有name（因为没有意义）。默认情况下，一个list最多具有176个子节点。
以上通过blob和list的组合可以实现存储任意大小的文件，对于文件夹，则可以使用tree。与list类似，data域存储Object类型，文件夹中的类型可以是blob（小于256KB的文件）、list（大于256KB的文件）和tree（子文件夹）。并且tree的links中的name即文件名或目录名。
为了支持版本管理，IPFS还有一个commit类型的Object，由于Merkle DAG是不可变的，因此通过在commit中指向一个DAG的根节点，就相当于对这个DAG拍了个快照，之后无论数据怎么变动，commit永远指向这个快照所表示的状态，因此使用IPFS来实现Git也是有可能的。
IPFS通过将上述不同种类的Object组织成Merkle Tree来灵活的表示任意大小的文件和文件夹，同时还具备版本控制功能。另外得益于基于内容寻址（也就是使用Hash索引节点），如果不同文件的某些切块重复，那么可以直接复用，从而节省空间。
文件存储
所以说回文章一开始的问题，为什么要用Merkle DAG（像IPFS一样）存储文件？文件存储对于IPFS来说并不是核心，它所要解决的问题是文件交换的效率。而我希望的是能够以这种方式存储/归档文件。
谈起这种需求，大概还得从IBM Cloud说起。大约8月26日前后，我的IBM Cloud账号毫无征兆的被封了，于是痛失900GB数据，联系IBM Cloud无果（SoftLayer的客服就是逊），和其他人聊了聊，发现导致封号的原因可能是在他们家的云对象存储上存了大量的版权视频，因为我用那东西做备份来着，数据存放在美国，所以适用于美国的法律。现在我转到了AWS S3，因为他们家是最早一个做云服务的，所以我比较相信AWS的客服质量，只要封号之前告诉我一声就行了。
但是为了避免发生类似的事情，同时希望能够借复用机制减少一些使用量（从价格上来说，我只用Glacier Deep Archive，其他的太贵），所以提出了这样的构想。
在下一篇中我将介绍本项目的一些基本组件和相关数据结构。
-全文完-
【代码札记】基于Merkle DAG的文件存储服务 P1 铺垫 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。