MPT树的编码

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

参考:https://ethfans.org/posts/588

key值编码

1.RAW编码(原生编码)

Raw编码就是原生的key值,不做任何改变。这种编码方式的key,是MPT对外提供接口的默认编码方式。

例如一条key为“cat”,value为“dog”的数据项,其Raw编码就是[‘c’, ‘a’, ‘t’],换成ASCII表示方式就是[63, 61, 74]

代码举例:

  1. trie, _ = New(root, triedb)
  2. _, err := trie.TryGet([]byte("120000"))

这个[]byte(“120000”)就是原生编码。

2.Hex编码(扩展的16进制编码)

我们在上篇文章介绍fullNode的时候,fullNode有个字段Children是17个node类型的数组。这样设计的目的是为了减少分支节点(fullNode)孩子(Children)的个数。因为一个原生编码中一个字节是8位,取值范围是[0-127),所以以太坊使用了一个新的单位叫nibble(4位)。取值范围是(0-15),这样一个分支节点的孩子至多只有16个。以太坊通过这种方式,减小了每个分支节点的容量,但是在一定程度上增加了树高。最后一个元素用来存储自身的内容。

这个转换的函数在encoding.go中。

  1. func keybytesToHex(str []byte) []byte {
  2. l := len(str)*2 + 1
  3. var nibbles = make([]byte, l)
  4. for i, b := range str {
  5. nibbles[i*2] = b / 16
  6. nibbles[i*2+1] = b % 16
  7. }
  8. nibbles[l-1] = 16
  9. return nibbles
  10. }

现在我们简单介绍下转换规则:

  • 将Raw编码的每个字符,根据高4位低4位拆成两个字节;
  • 若该Key对应的节点存储的是真实的数据项内容(即该节点是叶子节点),则在末位添加一个ASCII值为16的字符作为终止标志符;
  • 若该key对应的节点存储的是另外一个节点的哈希索引(即该节点是扩展节点),则不加任何字符;

key为“cat”, value为“dog”的数据项,其Hex编码为[3, 15, 3, 13, 4, 10, 16]

3.HP编码(Hex-Prefix编码)

这个编码方式的目的是用于在磁盘存储的时候用的。通过上面Hex编码我们可以看到使用nibble方式的key的字节数比原生key多出了一倍。所以如果在数据库中使用这种编码就会浪费很多的空间。
我们看下encoding.go中的源码:

  1. func hexToCompact(hex []byte) []byte {
  2. terminator := byte(0)
  3. if hasTerm(hex) {
  4. terminator = 1
  5. hex = hex[:len(hex)-1]
  6. }
  7. buf := make([]byte, len(hex)/2+1)
  8. buf[0] = terminator << 5 // the flag byte
  9. if len(hex)&1 == 1 {
  10. buf[0] |= 1 << 4 // odd flag
  11. buf[0] |= hex[0] // first nibble is contained in the first byte
  12. hex = hex[1:]
  13. }
  14. decodeNibbles(hex, buf[1:])
  15. return buf
  16. }
  17. // hasTerm returns whether a hex key has the terminator flag.
  18. func hasTerm(s []byte) bool {
  19. return len(s) > 0 && s[len(s)-1] == 16
  20. }
  21. func decodeNibbles(nibbles []byte, bytes []byte) {
  22. for bi, ni := 0, 0; ni < len(nibbles); bi, ni = bi+1, ni+2 {
  23. bytes[bi] = nibbles[ni]<<4 | nibbles[ni+1]
  24. }
  25. }

对着代码我们再介绍下HP编码规则:

  • 若原key的末尾字节的值为16(即该节点是叶子节点),去掉该字节;(hasTerm)
  • 在key之前增加一个半字节,其中最低位用来编码原本key长度的奇偶信息,key长度为奇数,则该位为1;低2位中编码一个特殊的终止标记符,若该节点为叶子节点,则该位为1;(buf[0] = terminator << 5)
  • 若原本key的长度为奇数,则在key之前再增加一个值为0x0的半字节;
  • 将原本key的内容作压缩,即将两个字符以高4位低4位进行划分,存储在一个字节中(Hex扩展的逆过程)(decodeNibbles);

若Hex编码为[3, 15, 3, 13, 4, 10, 16],则HP编码的值为[32, 63, 61, 74]

三种编码之间的关系

现在我们知道了三种编码方式,那他们三种方式的关系是怎样的呢?我们用一张图来表示:
转换关系

上面这张图很好的反映了三种编码之间的关系:

  • RAW编码: 原生的key编码,是MPT对外提供接口中使用的编码方式,当数据项被插入到树中时,Raw编码被转换成Hex编码;
  • Hex编码:16进制扩展编码,用于对内存中树节点key进行编码,当树节点被持久化到数据库时,Hex编码被转换成HP编码;
  • HP编码:16进制前缀编码,用于对数据库中树节点key进行编码,当树节点被加载到内存时,HP编码被转换成Hex编码;
  • 分享 收藏
2 条评论
  • black energer elastos

    @梓寒(冰心)
    我的邮箱:ttzhangbin@sina.com

    2019-04-02 12:26
  • 梓寒(冰心) 互联网行业猎头 TAG

    同学,我对您写的文章方向很感兴趣哈,方便留个邮箱或者微信交流下么

    2019-03-31 15:26