在Go中实现Merkle-tree数据结构

我目前正在尝试在Go中实现Merkle-

tree数据结构。基本上,我的最终目标是存储一小组结构化数据(最大10MB),并使该“数据库”可以轻松地与网络上分布的其他节点同步(请参阅参考资料)。由于没有类型检查,因此我已经在Node中有效地实现了这一点。这就是Go的问题,我想利用Go的编译时类型检查,尽管我也想拥有一个可以与任何提供的树一起使用的库。

简而言之,我想将结构用作merkle节点,并且希望有一种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将是根,其中将包含Bazzs和Bars。可以通过思考类型来推断这种关系。问题是用法:

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。未初始化的Bars和Bazzs可以由父级检测并初始化foo.Update()。可以接受一些反思,因为当前的正确性比性能更重要。另一个问题是,当我们Update()成为一个节点时,Update()由于我们不确定要更改的内容,因此所有结构字段(子节点)也都需要被删除(重新映射)。我们可以foo.SetInt("A",

35)实现自动更新,尽管那样我们会丢失编译时的类型检查。

会认为这是惯用的Go吗?如果没有,如何改善?谁能想到一种简洁的数据集比较(用于通过网络进行有效增量传输)将数据集存储在内存中(用于快速读取)的替代方法吗?编辑:还有一个元问题:问此类问题的最佳地点是StackOverflow,Reddit或螺母?最初发布在reddit上没有答案:(

回答:

一些目标看起来像:

  • 散列任何内容 -通过散列开箱即用的东西来使其易于使用
  • 缓存哈希 -使更新只是重新 哈希 他们需要的内容
  • 习惯用法 -与其他Go代码完美匹配

我认为您可以使用类似于内置encoding/gobencoding/jsondo之类的序列化工具的方式大致上对哈希进行攻击,这是三管齐下的:如果类型实现了(对于JSON而言MarshalJSON),则使用特殊方法;对于基本类型使用类型开关,然后使用反射回退到令人讨厌的默认情况。这是一个API草图,它提供了哈希缓存的帮助器,并允许类型实现Hash或不实现:

package merkle

type 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

回到顶部