MENU

【代码札记】基于 Merkle DAG 的文件存储服务 P2 数据结构

September 20, 2021 • Read: 131 • 瞎折腾

上文中讨论了关于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个逻辑结构,分别对应bloblisttreecommit

抽象类

为了适应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)的equalshashcode方法,统一利用其内容的字节进行比较,所以使用了抽象类。自从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方法即可享受到转换前的自动类型检查。

使用实例

上述数据结构在代码中使用时如下图。

photo_2021-09-20_13-35-42.jpg

最顶层的AritegCommitObject表示一个commit,内部除了有本次提交的相关信息之外,还有一个AritegLink作为指针,指示本次提交的根对象。本例中是一个AritegTreeObject,其内部有一系列AritegLink,每个代表一个子对象。子对象可以是其他treelistblob,而list的子对象可以是其他listblob。本例中还给出了一个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://www.skyblond.info/about.html 处获得。

Archives QR Code Tip
QR Code for this page
Tipping QR Code