MPT树节点类型

标签:底层链开发
发布时间:2019年03月27日 价值:20000.00 / 共识:26

参考:http://www.cocoachina.com/apple/20180921/24990.html

叶子节点:(valueNode)

  1. valueNode []byte

没有子结点,包含一个value,表示为[key,value]的一个键值对,其中key是key的一种特殊十六进制编码(HP编码)十六进制前缀编码

它其实是字节数组[]byte 的一个别名,不带子节点。在使用中,valueNode 就是所携带数据部分的 RLP 哈希值,长度 32byte,数据的 RLP 编码值作为 valueNode 的匹配项存储在数据库里。

扩展节点:(shortNode)

  1. shortNode struct {
  2. Key []byte
  3. Val node
  4. flags nodeFlag
  5. }

只有1个子结点,也是[key,value]的一个键值对,但是这里的value是其他节点的hash值,这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。

分支节点(fullNode):

  1. fullNode struct {
  2. Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
  3. flags nodeFlag
  4. }

包含16个分支,以及1个value.因为MPT树中的key被编码成一种特殊的16进制的表示,再加上最后的value,所以分支节点是一个长度为17的list,前16个元素对应着key中的16个可能的十六进制字符,如果有一个[key,value]对在这个分支节点终止,最后一个元素代表一个值,即分支节点既可以搜索路径的终止也可以是路径的中间节点。

叶子节点和扩展节点是新增加的!(对比于前缀树来说)

这三种类型覆盖了一个普通 Trie(也许是 PatriciaTrie)的所有节点需求。任何一个[k,v]类型数据被插入一个 MPT 时,会以 k 字符串为路径沿着 root 向下延伸,在此次插入结束时首先成为一个 valueNode,k 会以自顶点 root 起到到该节点止的 key path 形式存在。但之后随着其他节点的不断插入和删除,根据 MPT 结构的要求,原有节点可能会变化成其他node 实现类型,同时 MPT 中也会不断裂变或者合并出新的(父)节点。

hashNode:

  1. hashNode []byte

hashNode 跟 valueNode 一样,也是字符数组[]byte 的一个别名,同样存放 32byte 的哈希值,也没有子节点。不同的是,hashNode 是 fullNode 或者 shortNode 对象的 RLP 哈希值,所以它跟 valueNode 在使用上有着莫大的不同。

HashNode一般是放在nodeFlag这个struct中,被fullNode和shortNode间接持有。

  1. // nodeFlag contains caching-related metadata about a node.
  2. type nodeFlag struct {
  3. hash hashNode // cached hash of the node (may be nil)
  4. gen uint16 // cache generation counter
  5. dirty bool // whether the node has changes that must be written to the database
  6. }

一旦 fullNode 或 shortNode 的成员变量(包括子结构)发生任何变化,它们的 hashNode 就一定需要更新。所以在 trie.Trie 结构体的 insert(),delete()等函数实现中,可以看到除了新创建的 fullNode、shortNode,那些子结构有所改变的 fullNode、shortNode 的 nodeFlag 成员也会被重设,hashNode 会被清空。在下次 trie.Hash()调用时,整个 MPT 自底向上的遍历过程中,所有清空的 hashNode 会被重新赋值。这样trie.Hash()结束后,我们可以得到一个根节点 root 的 hashNode,它就是此时此刻这个 MPT结构的哈希值。

Header 中的成员变量 Root、TxHash、ReceiptHash 的生成,正是源于此。明显的,hashNode 体现了 MerkleTree 的特点:每个父节点的哈希值来源于所有子节点哈希值的组合,一个顶点的哈希值能够代表一整个树形结构。hashNode 加上之前的fullNode,shortNode,valueNode,构成了一个完整的 Merkle-PatriciaTrie 结构。

树的解析

节点增删查改用到的函数都定义于 trie.go。在 MPT 的查找,插入,删除过程中,如果在遍历时遇到一个 hashNode,首先需要从数据库里以这个哈希值为 k,读取出相匹配的v,然后再将 v 解码恢复成 fullNode 或 shortNode。在代码中这个过程叫 resolve。

  1. func (t *Trie) resolve(n node, prefix []byte) (node, error) {
  2. if n, ok := n.(hashNode); ok {
  3. return t.resolveHash(n, prefix)
  4. }
  5. return n, nil
  6. }
  7. func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
  8. cacheMissCounter.Inc(1)
  9. hash := common.BytesToHash(n)
  10. if node := t.db.node(hash, t.cachegen); node != nil {
  11. return node, nil
  12. }
  13. return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
  14. }
  15. // node retrieves a cached trie node from memory, or returns nil if none can be
  16. // found in the memory cache.
  17. func (db *Database) node(hash common.Hash, cachegen uint16) node {
  18. // Retrieve the node from cache if available
  19. db.lock.RLock()
  20. node := db.nodes[hash]
  21. db.lock.RUnlock()
  22. if node != nil {
  23. return node.obj(hash, cachegen)
  24. }
  25. // Content unavailable in memory, attempt to retrieve from disk
  26. enc, err := db.diskdb.Get(hash[:])
  27. if err != nil || enc == nil {
  28. return nil
  29. }
  30. return mustDecodeNode(hash[:], enc, cachegen)
  31. }
  32. func mustDecodeNode(hash, buf []byte, cachegen uint16) node {
  33. n, err := decodeNode(hash, buf, cachegen)
  34. if err != nil {
  35. panic(fmt.Sprintf("node %x: %v", hash, err))
  36. }
  37. return n
  38. }
  39. // decodeNode parses the RLP encoding of a trie node.
  40. func decodeNode(hash, buf []byte, cachegen uint16) (node, error) {
  41. if len(buf) == 0 {
  42. return nil, io.ErrUnexpectedEOF
  43. }
  44. elems, _, err := rlp.SplitList(buf)
  45. if err != nil {
  46. return nil, fmt.Errorf("decode error: %v", err)
  47. }
  48. switch c, _ := rlp.CountValues(elems); c {
  49. case 2:
  50. n, err := decodeShort(hash, elems, cachegen)
  51. return n, wrapError(err, "short")
  52. case 17:
  53. n, err := decodeFull(hash, elems, cachegen)
  54. return n, wrapError(err, "full")
  55. default:
  56. return nil, fmt.Errorf("invalid number of list elements: %v", c)
  57. }
  58. }

最后decodeNode就是根据SplitList解出来的node数量进行判断,如果是两个,则表示shortNode,如果是17个,则表示fullnode。

如果一个fullNode原本只有两个子节点,现在要删除其中一个子节点,那么这个fullNode就会退化为shortNode,同时保留的子节点如果是shortNode,还可以跟它再合并.

  • 分享 收藏
0 条评论
  • 这篇文章暂无评论,赶紧评论一下吧~