我目前正在尝试在 Go 中实现默克尔树数据结构。基本上,我的最终目标是存储一小组结构化数据(最大 10MB),并允许该“数据库”轻松与分布在网络上的其他节点同步(请参阅相关资料)。
我已经在 Node 中相当有效地实现了这一点,因为没有类型检查。这就是 Go 的问题,我想利用 Go 的编译时类型检查,尽管我也希望拥有一个可以与任何提供的树一起使用的库。
简而言之,我想使用结构作为默克尔节点,并且我想要一个Merkle.Update()
嵌入在所有类型中的方法。我试图避免写一个Update()
对于每个结构(尽管我知道这可能是唯一/最好的方法)。
我的想法是使用嵌入类型:
//library
type Merkle struct {
Initialised bool
Container interface{} //in example this references foo
Fields []reflect.Type
//... other merkle state
}
//Merkle methods... Update()... etc...
//userland
type Foo struct {
Merkle
A int
B bool
C string
D map[string]*Bazz
E []*Bar
}
type Bazz struct {
Merkle
S int
T int
U int
}
type Bar struct {
Merkle
X int
Y int
Z int
}
在这个例子中,Foo
将是根,其中将包含Bazz
s and Bar
s。这种关系可以通过反映类型来推断。问题是用法:
foo := &Foo{
A: 42,
B: true,
C: "foo",
D: map[string]*Bazz{
"b1": &Bazz{},
"b2": &Bazz{},
},
E: []*Bar{
&Bar{},
&Bar{},
&Bar{},
},
}
merkle.Init(foo)
foo.Hash //Initial hash => abc...
foo.A = 35
foo.E = append(foo.E, &Bar{})
foo.Update()
foo.Hash //Updated hash => def...
我认为我们需要merkle.Init(foo)
since foo.Init()
实际上会是foo.Merkle.Init()
并且无法反思foo
。未初始化的Bar
s and Bazz
s 可以被父级检测到并初始化foo.Update()
。一些反思是可以接受的,因为目前正确性比性能更重要。
另一个问题是,当我们Update()
一个节点,所有结构字段(子节点)都需要Update()
d 以及(重新整理),因为我们不确定发生了什么变化。我们可以做foo.SetInt("A", 35)
实现自动更新,但这样我们就失去了编译时类型检查。
这会被认为是惯用的 Go 语言吗?如果没有,如何改进?谁能想到一种替代方法来将数据集存储在内存中(用于快速读取)并进行简洁的数据集比较(用于通过网络进行高效的增量传输)?
编辑:还有一个元问题:问这类问题的最佳地点在哪里,StackOverflow、Reddit 还是 go-nuts?最初发布于reddit http://www.reddit.com/r/golang/comments/2eibc0/implementing_a_merkletree_data_structure_in_go/没有答案:(