上文中讨论了关于Merkle DAG的一些基本概念和原理，本文将记述其具体实现。
存储结构
结合上文来看，本系列中Merkle DAG的使用方法还是更接近IPFS一些，于是我便参照IPFS的白皮书设计了一下。为了使数据具有统一的序列化标准，我使用了Protobuf。
syntax = "proto3";
message AritegObject {
// Type of this object
AritegObjectType type = 1;
// blob data content
bytes data = 2;
// list, tree and commit links
// Note: commit link has fixed name: parent, link, author
repeated AritegLink links = 3;
// commit data
AritegCommitData commit_data = 4;
}AritegObject是所有Object的超集，它具有所有Object需要的字段，并且内置了一个type用来描述该Object是何种类型：
enum AritegObjectType {
BLOB = 0;
LIST = 1;
TREE = 2;
COMMIT = 3;
}这里一共设计了4个Object，与前文介绍的IPFS中的Object类型一样。另外IPFS中还定义了加密和签名的Object，用于IPNS，由于本文的目的是一个简单的文件存储服务，所以并不考虑对存储数据的处理（签名、加密等）。即便是要加，可以简单的在程序方面增加， 而不必修改底层设计。
对于links，设计与IPFS的类似：
message AritegLink {
// name of the link
string name = 1;
// multihash of target
bytes multihash = 2;
}这里没有记录目标对象的大小，因为与IPFS不同，IPFS获取对象前无法知晓对象的大小，因此必须记录下来以供申请合适大小的缓冲区。而我们的系统将所有数据集中存储，因此给定一个目标的multihash，必定能够知道该对象的字节数目。
对于commit类型的Object，使用一个专门的域来存储某次提交的信息，结构如下：
message AritegCommitData {
// type of committed object
AritegObjectType type = 1;
// unix timestamp of this
uint64 unix_timestamp = 2;
// commit message
string message = 3;
}逻辑结构
基于上述存储结构，可以引申出4个逻辑结构，分别对应blob、list、tree和commit。
抽象类
为了适应Protobuf生成的类与四个逻辑结构能够相互转换，首先定义如下抽象类：
package info.skyblond.ariteg.objects
import info.skyblond.ariteg.AritegObject
import info.skyblond.ariteg.AritegObjectType
abstract class AbstractAritegObject {
/**
* Convert current instance to proto
* */
abstract fun toProto(): AritegObject
// If bytes are same, then they are same
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (other !is AbstractAritegObject) return false
val thisBytes = this.toProto().toByteArray()
val otherBytes = this.toProto().toByteArray()
if (!thisBytes.contentEquals(otherBytes)) return false
return true
}
// hash is the byte content
override fun hashCode(): Int {
return this.toProto().toByteArray().contentHashCode()
}
}
abstract class AbstractAritegObjectCompanion<T>(
protected val expectedType: AritegObjectType
) where T : AbstractAritegObject {
/**
* If the object is type
* */
fun isTypeOf(proto: AritegObject): Boolean {
return proto.type == AritegObjectType.BLOB
}
/**
* Generate instance from proto.
* */
fun fromProto(proto: AritegObject): T {
require(isTypeOf(proto)) { "Expect ${expectedType.name} object but ${proto.type.name} object is given" }
return toInstance(proto)
}
protected abstract fun toInstance(proto: AritegObject): T
}
AbstractAritegObject类描述了一个Object应该有哪些方法，由于里面覆盖了来自Any（Kotlin世界中的万物之父java.lang.Object）的equals和hashcode方法，统一利用其内容的字节进行比较，所以使用了抽象类。自从Java 8中给接口引入了默认方法之后，很大一部分情况下接口与抽象类在功能上可以相互替换了，但这里由于覆盖了来自其他类的方法，所以不能使用接口。由于使用Kotlin，所以Object的构造应当由静态工厂方法来担任，Object本身应当设计成不可变对象，这样之后的序列化到字节数组，以及多线程的使用会方便和安全许多。另外系统中的Object是通过其内容的哈希来索引，如果内容变了，那么内存中对该对象的引用和逻辑上哈希的引用出现了冲突，会带来额外的麻烦，所以Object本身不可变，由一个工厂方法负责构造，由一个成员方法负责将其转换为Protobuf的生成类，这样应该算得上是最优实践了。
在Kotlin中没有static关键字，一般类中的静态方法是依靠companion object来实现的，因此还得针对compainion object设计一个抽象类，即AbstractAritegObjectCompanion<T>，泛型表示该伴生对象产生的Object类型，应当是AbstractAritegObject类的子类。这里没有使用接口的原因是其拥有一个protect修饰的成员变量，该变量记录本对象接受的Protobuf对象的类型，并在转换前进行检查，这样即可复用类型检查的代码（很显然你不希望在每个具体实现中检查传入的proto是不是拥有正确的type）。
具体实现
在有了如上两个抽象类之后，我们可以开始搞具体实现了。之前说过，所有的Object类应当是不可变的，Kotlin当中的data class较为方便的提供了这个特性。
BlobObject的实现如下：
data class AritegBlobObject(
val data: ByteString
) : AbstractAritegObject() {
companion object : AbstractAritegObjectCompanion<AritegBlobObject>(AritegObjectType.BLOB) {
override fun toInstance(proto: AritegObject): AritegBlobObject {
return AritegBlobObject(proto.data)
}
}
override fun toProto(): AritegObject {
return AritegObject.newBuilder()
.setType(AritegObjectType.BLOB)
.setData(data)
.build()
}
}这里ByteString是Protobuf提供的对字节串的描述，相比字节数组，其本身具有不可变性，与String一样。AritegBlobObject自身实现了AbstractAritegObject，它只要实现toProto方法即可。其伴生对象实现了AbstractAritegObjectCompanion<AritegBlobObject>，只需要覆盖toInstance方法即可享受到转换前的自动类型检查。
使用实例
上述数据结构在代码中使用时如下图。
最顶层的AritegCommitObject表示一个commit，内部除了有本次提交的相关信息之外，还有一个AritegLink作为指针，指示本次提交的根对象。本例中是一个AritegTreeObject，其内部有一系列AritegLink，每个代表一个子对象。子对象可以是其他tree，list或blob，而list的子对象可以是其他list或blob。本例中还给出了一个blob复用的情况：如果恰好存储了具有相同哈希的blob块，那么可以直接引用已有的数据，而不必再单独存储一份。如果只存储一份可能效果不明显，如果一个文件或目录有多个版本，目前所有S3的做法都是把旧版本复制一份单独收费，而使用这种文件切块的方式，则可以复用已有的块。假如一个20GB的文件改变的范围可以有一个blob描述，那么两个版本大小加起来只有20GB+1个blob，而S3则需要40GB。这种做法可以极大的减少开销。
最顶层的对象只需要使用一个Base58编码的Multihash即可找到，便于人类查询。
哈希碰撞
由于整个系统使用数据的哈希作为索引，由于输入空间无限大（默认每个blob是256k，但不足256k的也可以单独程为要给blob，如果用户愿意，任意不同大小的blob相互组合也是合法的，这样一来扔进哈希函数的数据长度就是任意的，那么数据的内容也就是无限种情况），而输出空间只有固定大小（IPFS使用SHA256，我准备使用SHA3-512），回忆我们中学或小学时学到的抽屉原理，势必会有两个及更多个不同的输入对应同一个输出哈希，这种情况下，某一块的blob哈希重复，但内容不相同，文件势必会损坏，这种情况应该如何应对？
技术上最简单的方法就是同时使用三种不同的哈希函数，由于两个哈希函数对于同一个输入同时碰撞的几率很小，可以认为是不可能事件，所以在AritegLink中存储三个哈希函数，每次读取读出三个数据，如果三个数据都相同，那么没有碰撞，万事大吉。如果有一个不同，则发生了碰撞，另外两个相同，选相同的两个作为读取的结果。这种解决方法将数据损毁的概率直接推向了不可能，但代价是同一份数据要以三个哈希存储三遍，付出三倍的存储代价。如果数据块的复用程度比较高，这种做法还有可能带来收益，但如果复用性较低，那么只会徒增存储成本。
在IPFS社群中也有过类似的讨论。例如：「What to do in case of hash collision?」、「Hash collision/limitation in IPFS: is it possible?」、「IPFS collisions.」，以及SHA1被攻破的例子：「We have broken SHA-1 in practice.」。虽然最后一个例子很吓人——两个内容不同的PDF给出了相同的SHA-1哈希，但也只是个例。哈希碰撞在客观上确实存在，但和中彩票一样——你知晓它的存在，但很少遇见。而且就哈希函数的设计而言，一个好的哈希函数是无法预知输入与输出之间的关系，所以这种哈希碰撞完全是概率的（即，不是普遍现象）。系统中使用了Multihash存储不同哈希函数的结果，所以不同的哈希可以在系统中共存，因此在未来如果我们发现某个碰撞确实存在，那么可以简单的升级到一个更安全的哈希函数，虽然过程中可能需要重新对所有AritegLink涉及的数据重新计算哈希，但至少是可升级的，一个哈希函数的失效并不会给整个系统宣告死亡。
至于上一篇文章开头问的，块复用有这么多好处，为什么没有人用？大概原因就是如此——虽然碰撞的概率很低，但谁也不想冒着数据损坏的风险来减少成本。这也是为什么大家都能够接受S3在开启版本控制时会收取多分费用的原因。
【代码札记】基于 Merkle DAG 的文件存储服务 P2 数据结构 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。