在Go中实现Merkle-tree数据结构
我目前正在尝试在Go中实现Merkle-
tree数据结构。基本上,我的最终目标是存储一小组结构化数据(最大10MB),并使该“数据库”可以轻松地与网络上分布的其他节点同步(请参阅参考资料)。由于没有类型检查,因此我已经在Node中有效地实现了这一点。这就是Go的问题,我想利用Go的编译时类型检查,尽管我也想拥有一个可以与任何提供的树一起使用的库。
简而言之,我想将结构用作merkle节点,并且希望有一种Merkle.Update()
嵌入到所有类型中的方法。我试图避免Update()
为每个结构编写一个(尽管我知道这可能是唯一/最好的方法)。
我的想法是使用嵌入式类型:
//librarytype 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和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)
因为foo.Init()
实际上是foo.Merkle.Init()
,现在将无法反思foo
。未初始化的Bar
s和Bazz
s可以由父级检测并初始化foo.Update()
。可以接受一些反思,因为当前的正确性比性能更重要。另一个问题是,当我们Update()
成为一个节点时,Update()
由于我们不确定要更改的内容,因此所有结构字段(子节点)也都需要被删除(重新映射)。我们可以foo.SetInt("A",
35)实现自动更新,尽管那样我们会丢失编译时的类型检查。
会认为这是惯用的Go吗?如果没有,如何改善?谁能想到一种简洁的数据集比较(用于通过网络进行有效增量传输)将数据集存储在内存中(用于快速读取)的替代方法吗?编辑:还有一个元问题:问此类问题的最佳地点是StackOverflow,Reddit或螺母?最初发布在reddit上没有答案:(
回答:
一些目标看起来像:
- 散列任何内容 -通过散列开箱即用的东西来使其易于使用
- 缓存哈希 -使更新只是重新 哈希 他们需要的内容
- 习惯用法 -与其他Go代码完美匹配
我认为您可以使用类似于内置encoding/gob
或encoding/json
do之类的序列化工具的方式大致上对哈希进行攻击,这是三管齐下的:如果类型实现了(对于JSON而言MarshalJSON
),则使用特殊方法;对于基本类型使用类型开关,然后使用反射回退到令人讨厌的默认情况。这是一个API草图,它提供了哈希缓存的帮助器,并允许类型实现Hash
或不实现:
package merkletype HashVal uint64
const MissingHash HashVal = 0
// Hasher provides a custom hash implementation for a type. Not
// everything needs to implement it, but doing so can speed
// updates.
type Hasher interface {
Hash() HashVal
}
// HashCacher is the interface for items that cache a hash value.
// Normally implemented by embedding HashCache.
type HashCacher interface {
CachedHash() *HashVal
}
// HashCache implements HashCacher; it's meant to be embedded in your
// structs to make updating hash trees more efficient.
type HashCache struct {
h HashVal
}
// CachedHash implements HashCacher.
func (h *HashCache) CachedHash() *HashVal {
return &h.h
}
// Hash returns something's hash, using a cached hash or Hash() method if
// available.
func Hash(i interface{}) HashVal {
if hashCacher, ok := i.(HashCacher); ok {
if cached := *hashCacher.CachedHash(); cached != MissingHash {
return cached
}
}
switch i := i.(type) {
case Hasher:
return i.Hash()
case uint64:
return HashVal(i * 8675309) // or, you know, use a real hash
case []byte:
// CRC the bytes, say
return 0xdeadbeef
default:
return 0xdeadbeef
// terrible slow recursive case using reflection
// like: iterate fields using reflect, then hash each
}
// instead of panic()ing here, you could live a little
// dangerously and declare that changes to unhashable
// types don't invalidate the tree
panic("unhashable type passed to Hash()")
}
// Item is a node in the Merkle tree, which must know how to find its
// parent Item (the root node should return nil) and should usually
// embed HashCache for efficient updates. To avoid using reflection,
// Items might benefit from being Hashers as well.
type Item interface {
Parent() Item
HashCacher
}
// Update updates the chain of items between i and the root, given the
// leaf node that may have been changed.
func Update(i Item) {
for i != nil {
cached := i.CachedHash()
*cached = MissingHash // invalidate
*cached = Hash(i)
i = i.Parent()
}
}
以上是 在Go中实现Merkle-tree数据结构 的全部内容, 来源链接: utcz.com/qa/423654.html