以太坊源码解读-第3.2讲-trie模块源码解读

区块链 / ethereum / 源码解读
Word count: 7.5k   |   Reading time≈ 30 min

前言

这一部分，我们主要是讲trie源码的实现，要理解代码的实现过程，是需要先了解一下理论内容的，建议大家先看看我的上一篇文章：以太坊源码解读-第3.1讲-trie原理介绍

概述

小编根据对已有代码的了解，画了这么个trie相关一览图：

encoding.go源码解读

trie模块中，这个文件是我们首先要掌握的，这个主要是讲三种编码（KEYBYTES encoding、HEX encoding、COMPACT encoding）的实现与转换，trie中全程都需要用到这些，该文件中主要实现了如下功能：

  1. hex编码转换为Compact编码：hexToCompact()
  2. Compact编码转换为hex编码：compactToHex()
  3. keybytes编码转换为Hex编码：keybytesToHex()
  4. hex编码转换为keybytes编码：hexToKeybytes()
  5. 获取两个字节数组的公共前缀的长度：prefixLen()

但是，小编不会去讲这块的源码内容了，因为以太坊源码解读-第3.1讲-trie原理介绍这篇文章里已经穿插了很多相关的源码，重点都已经在其中解释的很详细了。
如果还有哪些地方不了解，大家可以留言或者微信与小编联系。

node.go源码解读

大家得先看懂以太坊源码解读-第3.1讲-trie原理介绍关于节点方面的内容，否则很难理解小编下面要讲的源码。

node的结构与定义

以太坊为MPT中的node定义了一套基本接口规则：

1
2
3
4
5
type node interface {
	fstring(string) string //用来打印节点信息，没别的作用
	cache() (hashNode, bool)  //保存缓存
	canUnload(cachegen, cachelimit uint16) bool  //除去缓存，cache次数的计数器
}

以太坊依据上面的规则为MTP定义了四种类型的节点，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
type (
	fullNode struct {
		Children [17]node  //对应了黄皮书里面的分支节点
		flags    nodeFlag
	}
	shortNode struct {  //对应了黄皮书里面的扩展节点
		Key   []byte
		Val   node  //可能指向叶子节点，也可能指向分支节点。
		flags nodeFlag
	}
	hashNode  []byte
	valueNode []byte  //叶子节点值，但是该叶子节点最终还是会包装在shortNode中
)

分为这四种节点：

  • fullNode
    这就是传说中的分支节点，会发现它里面定义了17个node，其中16个对应的16进制的0~9a~f，第17个还没搞清楚，后面清楚了再来讲。nodeFlag稍后再说。
  • shortNode
    它本身若是扩展节点，则它的属性Val可能指向分支节点或者叶子节点，但要知道，叶子节点本身同样是用shortNode表示的；
    它本身若是叶子节点，则Val的值为rlp编码的数据，而key则是该数据的完整hash(经过hex编码的)
  • valueNode：这是给叶子节点用的，但是要知道它不能单独使用，而是要放在shortNode中使用的，用于存放rlp编码的原始数据
  • hashNode：这个同样不能单独使用，我们在上面节点定义中发现了，会涉及到nodeFlag，先来看看定义：
1
2
3
4
5
type nodeFlag struct {
	hash  hashNode // cached hash of the node (may be nil)
	gen   uint16   // cache generation counter
	dirty bool     // whether the node has changes that must be written to the database
}

在其中发现了hashNode，这个属性是用来标记nodeFlag所属的node对象本身经过rlp编码后的hash值（该hash在hashNode中同样是经过hex编码的），若node有任何变化，则该hash就会发生变化。
nodeFlag中的gen，只要对应的node发生一次变化，计数就加一
nodeFlage中的bool，只要对应的node发生变化，它就变成true，表示要把数据重新刷新到DB中(以太坊用levelDB存储MTP信息)
小编认为，对node理解到此处就可以了，对node的具体操作，要结合MPT的具体操作来掌握，这就引出了我们的下一部分需要掌握的文件：trie.go

trie.go源码解读

我们先来了解下以太坊给trie定义的结构：

1
2
3
4
5
6
7
8
9
type Trie struct {
	db           *Database  //trei在levelDB中
	root         node  //根结点
	originalRoot common.Hash  //32位byte[],从db中恢复出完整的trie

	//cachegen表示当前trie树的版本，trie每次commit，则增加1
	//cachelimit如果当前的cache时代 - cachelimit参数 大于node的cache时代，那么node会从cache里面卸载，以便节约内存。
	cachegen, cachelimit uint16
}

具体我们来解读一下其中的每部分：

  • db
  • root 可以理解为当前root指向哪个节点，初始时候，没有内容，则root=nil，表示指向nil
  • originalRoot
  • cachegen
  • cachelimit

按小编的理解，trie中存入db本身的是各种类型的node，也就是从root指向的那个node开始存储，root本身并不存储。

想要真正掌握以太坊中的trie，小编建议还是从它的测试文件node_test.go作为入口来读取源码，这里面涉及到内容如果都看懂，那相信你对MPT了解已经非常深刻了。好，那咱们一个个来看：

一颗空树

当为一颗空树时候，也就是trie只有一个节点，且trie.root=nil。
此时使用trie.Hash()可以返回当前整个trie树的hash值。而emptyRoot是trie预先定义的一个空节点时候的hash常量，将当前trie的hash和它比较，可以校验当前trie是否为空树。具体代码如下：
注意，这些hash是真实值，从进一步的代码中，我们是可以得知，这些hash是使用hex转换回来的hash。

1
2
3
4
5
6
7
8
func TestEmptyTrie(t *testing.T) {
	var trie Trie
	res := trie.Hash() //获取当前trie的hash
	exp := emptyRoot
	if res != common.Hash(exp) {
		t.Errorf("expected %x got %x", exp, res)
	}
}

从空树中添加一个节点

添加一个节点，也就是添加叶子结点，先来看代码：

1
2
3
4
5
6
7
8
9
func TestNull(t *testing.T) {
	var trie Trie
	value := []byte("test")  //value为字节数组
	key := make([]byte, 32) //一个32位的hash，但是其中每一位都是0
	trie.Update(key, value)
	if !bytes.Equal(trie.Get(key), value) {
		t.Fatal("wrong value")
	}
}

初始时，tril.root指向的是nil。
value：要把一个字符串内容为"test"的数据存入trie中
key：应该是value对应的rlp编码后的hash值
从trie.Update()进入到trie.go的insert方法中：会发现，key和value被组成一个shortNode，表示一个叶子节点，插入到trie空树中。
然后trie.root指向这个叶子节点。
可以这么理解，此时这棵树有一个根结点和一个叶子结点。
为更好说明，上个图，大体如下：

数据库中检测一个不存在的trie根节点

小编曾说个，以太坊的MPT中，是有google的levelDB参与的，而从trie定义的结构中，我们可知通过trie中的originalRoot可以恢复出一棵levelDB中存在的MPT树。
这个案例中，我们尝试使用一个不存在的hash来判断level中的确不存在该对应的MTP树。代码如下：
ps：小编需要说明，其中涉及的levelDB以及代码中的db操作相关，属于以太坊的ethdb模块中的内容，这个将在后续的文章中讲解，本文只一笔概述不会深入去讲db内容。

1
2
3
4
5
6
7
8
9
10
11
func TestMissingRoot(t *testing.T) {
	diskdb, _ := ethdb.NewMemDatabase()
	//New()中，第一个参数是将hex编码转为原始的hash 32位byte[]
	trie, err := New(common.HexToHash("0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33"), NewDatabase(diskdb))
	if trie != nil {
		t.Error("New returned non-nil trie for invalid root")
	}
	if _, ok := err.(*MissingNodeError); !ok {
		t.Errorf("New returned wrong error: %v", err)
	}
}

代码中我们可知，我们是要从一个新建的db中去找某hash对应的trie树。呵呵，当然会找不到。但程序具体是怎么执行查找的？需要我们进入New()方法去进一步了解过程：
传入的root是一个hash，根据该hash最后是在db中查找对应的trie根的。
其中originalRoot: root, ，若最终查找出了该trie，则该root就是整个trie的hash。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func New(root common.Hash, db *Database) (*Trie, error) {
	if db == nil {
		panic("trie.New called without a database")
	}
	trie := &Trie{
		db:           db,
		originalRoot: root,  //把传入的hash保存在此处，只要能恢复了整个trie
	}
	if (root != common.Hash{}) && root != emptyRoot {
		rootnode, err := trie.resolveHash(root[:], nil) //检查是否有对应的trie
		if err != nil {
			return nil, err
		}
		trie.root = rootnode  //返回了找到的trie，按小编理解，这个rootnode应该是分支节点或叶子节点
	}
	return trie, nil
}

其中，真正进行node查找的方法是resolveHash()该方法也需要大家了解一下：

1
2
3
4
5
6
7
8
9
10
func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
	cacheMissCounter.Inc(1)  //每执行一次resolveHash()方法，计数器+1

	hash := common.BytesToHash(n)
	enc, err := t.db.Node(hash)
	if err != nil || enc == nil {
		return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
	}
	return mustDecodeNode(n, enc, t.cachegen), nil
}

主要的是那个计数器，cacheMissCounter.Inc(1)，不论从db中还原trie成功还是失败，计数器都会累加1

操作存储在内存或磁盘的trie

db中只会存放最终真正确认有效的数据块，因此trie会被分为存在db磁盘中的以及留在内存中的两大类，具体可以看测试代码，（期间会涉及到部分非重点代码，小编就不列出了）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func testMissingNode(t *testing.T, memonly bool) {
	diskdb, _ := ethdb.NewMemDatabase()  //磁盘空间
	triedb := NewDatabase(diskdb)  //生成db

	trie, _ := New(common.Hash{}, triedb) //空节点创建
	//实际使用时，Update中的 value是需要先经过rlp编码
	trie.Update([]byte("120000"), []byte("qwerqwerqwerqwerqwerqwerqwerqwer"))
	trie.Update([]byte("123456"), []byte("asdfasdfasdfasdfasdfasdfasdfasdf"))
	root, _ := trie.Commit(nil)  //trie.Commit需要了解
	if !memonly {  //根据此处来判断是否提交到db
		triedb.Commit(root, true)  //这个就是将trie提交到db了
	}

	//根据key查找某个trie是否存在
	var bts []byte
	trie, _ = New(root, triedb)
	bts, err := trie.TryGet([]byte("120000"))
	fmt.Println(bts)
	
	//添加一个node
	trie, _ = New(root, triedb)
	//本质上也是调用trie.Update()方法
	err = trie.TryUpdate([]byte("120099"), []byte("zxcvzxcvzxcvzxcvzxcvzxcvzxcvzxcv"))

	//删除一个node
	trie, _ = New(root, triedb)
	err = trie.TryDelete([]byte("123456"))
	
	hash := common.HexToHash("0xe1d943cc8f061a0c0b98162830b970395ac9315654824bf21b73b891365262f9")
	if memonly { //为true，则在内存中删除该trie
		delete(triedb.nodes, hash)
	} else {  //为false，则在磁盘中删除该trie
		diskdb.Delete(hash[:])
	}
}

会发现，trie中存这样的几对方法：Update()和TryUpdate()、Get()和TryGet()、Delete()和TryDelete()；其实是没有加Try关键字的方法进一步封装了带有Try的方法，做了异常处理。另外：

  • TryUpdate()方法：当传入的value长度大于0，则调用trie.insert()把把key和value组成节点插入trie（插入逻辑后续再说）；否则若value长度为0，则调用trie.delete()方法删除trie中key对应的节点。
  • TryGet()方法：就是从trie中调用tryGet()方法获取key对应的那一部分数据
  • TryDelete()方法：就是调用trie中delete()方法删除trie中key对应的节点。
  • triedb.Commit()方法：将数据提交给db，这个涉及到trie模块下的database.go，后面章节中单独讲
  • diskdb.Delete()方法：磁盘中删除某节点，这个属于diskdb模块内容，本文不讲解。

节点的操作本身很重要，我们知道了，真正处理数据的是trie中的insert()、delete()、tryGet()这三个方法。接下来详细介绍一下它们。
先要知道，这些操作的数据目前都是在内存中保存的。
下面操作中，除了明确标明是在操作db，其余情况都是在内存中操作，这点一定要清楚，很容易搞混。

注意！小编多个新号让大家注意：****
只要trie树上的某条路径上有节点新增或者删除，那这条路径的节点都会被重新实例化并负值，如此一来，节点的nodeFlag中的dirty也被改为true，这样就表示这条路径的所有节点都需要重新插入到db。

新增数据到trie

其实就是新增一个叶子节点到trie
前面提到过的一些文章中只是理论上讲了讲新增原理，真实情况要复杂很多。
先来上一坨代码，看看以太坊是怎么处理新增的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//该方法会被递归调用
//n表示从trie当前节点n开始插入
//prefix表示当前匹配到的key的公共前缀
//key 表示待插入数据当前key中剩余未匹配的部分
//value 待插入数据本身
func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
	if len(key) == 0 { 
		if v, ok := n.(valueNode); ok {
			return !bytes.Equal(v, value.(valueNode)), value, nil
		} //要在节点A中新增节点B，若A和B本身数据一致，则认为已经新增，则直接返回true
		return true, value, nil
	}
	switch n := n.(type) {
	case *shortNode:
		matchlen := prefixLen(key, n.Key) //n.Key是扩展节点的公共key，这是公共结点匹配
		if matchlen == len(n.Key) { 
			dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
			if !dirty || err != nil {
				return false, n, err
			}//新增返回的必是叶子结点
			return true, &shortNode{n.Key, nn, t.newFlag()}, nil //从这里可以看出，从根路径到插入数据的位置，整条路径的节点都会被重新实例化，node的dirty也被改为true，表示要重新更新
		}
		//该case中，剩余部分代码，是为了将一个扩展节点拆分为两部分
		branch := &fullNode{flags: t.newFlag()} //新建一个分支节点
		var err error
		//插入分支节点第一个数据
		_, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
		if err != nil {
			return false, nil, err
		}
		//插入分支节点第二个数据
		_, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
		if err != nil {
			return false, nil, err
		}
		//若待插入数据和trie中当前节点的前缀key一个也没匹配，则返回分支节点
		if matchlen == 0 {
			return true, branch, nil
		}
		// 否则返回扩展节点
		return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil

	case *fullNode: //分支节点插入数据
		dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
		if !dirty || err != nil 
			return false, n, err
		n = n.copy()
		n.flags = t.newFlag()
		n.Children[key[0]] = nn
		return true, n, nil

	case nil: //也就是说，在空trie中添加一个节点，就是叶子节点，返回shortNode。
		return true, &shortNode{key, value, t.newFlag()}, nil

	case hashNode: //恢复一个存储在db中的node
		rn, err := t.resolveHash(n, prefix)  //检查该node是否存在，若存在，加载在node中
		if err != nil 
			return false, nil, err
		dirty, nn, err := t.insert(rn, prefix, key, value)
		if !dirty || err != nil 
			return false, rn, err
		return true, nn, nil

	default:
		panic(fmt.Sprintf("%T: invalid node: %v", n, n))
	}
}

从代码中我们可以看出：

  • 此时，只有key被编码为hex编码，而value是经过rlp编码的字节数组。
  • insert()最终返回的node其实就是trie.root所指向的node。
  • 若trie中本身是存在key所对应的数据的，则不可被修改。也就是会说，trie本身只可增加节点，不可修改节点
  • 若节点n指向的是nil，则当前是空trie，直接在其后加一个shortNode(叶子节点)即可。
  • 若节点n指向的是shortNode，则该shortNode可能是扩展节点，也可能是叶子节点。
    • 若待插入的key剩余未匹配的部分能匹配到当前shortNode中key的全部长度，则在该shortNode之后新增分支节点，或者在shortNode之后的分支节点上新增待插入节点。
    • 若待插入的key剩余未匹配的部分不能匹配到当前shortNode中key的全部长度，则该shortNode会新增一个分支节点，将shortNode分裂成两部分。这块建议大家画图理解。
  • 若节点n指向的是分支节点fullNode，理解了上面指向shortNode的过程，那这里就容易理解了，从分支节点下进一步查找要匹配的位置
  • 若节点n指向的是hashNode，说明此时该节点属于轻节点，真实的节点数据被释放了。因此，通过hashNode去db中恢复该节点，然后进一步去插入。

从trie中获取数据

其实就是根据输入到hash，在找到对应的叶子节点的数据，一言不合，先来代码，一坨。。。：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//origNode：当前查找的起始node位置
//key：输入要查找的数据的hash
//pos：当前hash匹配到第几位
func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) {
	switch n := (origNode).(type) {
	case nil: //这表示当前trie是空树
		return nil, nil, false, nil
	case valueNode: //这就是我们要查找的叶子节点对应的数据
		return n, n, false, nil
	case *shortNode: //在叶子节点或者扩展节点匹配
		if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) 
			return nil, n, false, nil
		value, newnode, didResolve, err = t.tryGet(n.Val, key, pos+len(n.Key))
		if err == nil && didResolve {
			n = n.copy()
			n.Val = newnode
			n.flags.gen = t.cachegen
		}
		return value, n, didResolve, err
	case *fullNode:  //在分支节点匹配
		value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1)
		if err == nil && didResolve {
			n = n.copy()
			n.flags.gen = t.cachegen
			n.Children[key[pos]] = newnode
		}
		return value, n, didResolve, err
	case hashNode: //说明当前节点是轻节点，需要从db中获取
		child, err := t.resolveHash(n, key[:pos])
		if err != nil 
			return nil, n, true, err  //trie重组，因此需要返回true
		value, newnode, _, err := t.tryGet(child, key, pos)
		return value, newnode, true, err
	default:
		panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
	}
}

不说别的，先说didResolve这个东西，用于判断trie树是否会发生变化，按理tryGet()只是用来获取数据的，哪里会影响trie发生变化，但是因为有可能我们会根据hashNode去db中获取该node值，获取到后，需要更新现有的trie，didResolve就会发生变化。
其实这段查询代码里，也就只有didResolve会让人郁闷一下，其它的就只是基本的递归查找树了。小编就不详解了，代码里注释大概写了点，够用了。
补充一下，当涉及到hashNode时，我们要知道，这是通过外部输入hashNode，进磁盘DB中查找对应节点。

从trie中删除数据

也就是说删除trie中的一个叶子节点。这个过程和插入过程很相似，小编就不讲了，再讲就累死了。

节点缓存设置

当一个节点被提交次数达到指定上线时候，该节点将会被重新加载。
这个功能还是蛮有用的，提高效率。这个代码没细看，有兴趣的可以看看。
在test_trie.go中看TestCacheUnload()测试方法，在trie.go中看trie.SetCacheLimit()方法
话说这个缓存机制小编一直没看懂。。。

Trie树的序列化、缓存(轻节点)

小编相信，看懂以太坊源码解读-第2讲-rlp模块源码解读的同学，会很容易理解trie树的序列化的 。
序列化和反序列化，本就是内存和磁盘存储时候的两种转化，具体概念小编就不讲了。
当trie.Commit(nil)的时候，会执行序列化、缓存等操作，因此小编就将这两者合在一起讲了
需要注意的是，trie树序列化后，真正保存在磁盘上，是使用的Compact Encoding编码，这样会节省空间。
还有一点需要分清：node本身节点的hash和shortNode中的key要区分，从根结点到叶子节点的key衔接起来，表示的是叶子节点value数据的hash值
关于trie的缓存机制，其实就是轻节点机制的设计理念，后面小编在代码中深入介绍吧。

trie.Commit(nil)入口解析

Commit()的目的，是将trie树中的key转为Compact编码，为每个节点生成一个hash。
可以这么说，它就是为了确保后续能正常将变动的数据提交到db.
来看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error) {
	if t.db == nil 
		panic("commit called on trie with nil database")
	hash, cached, err := t.hashRoot(t.db, onleaf)  
	if err != nil 
		return common.Hash{}, err
	t.root = cached
	t.cachegen++
	return common.BytesToHash(hash.(hashNode)), nil  //返回trie.root所指向的节点的hash，注意该hash是原始的32位hash，并未编码
}

//为每个node生成一个hash
//返回的结果中，有两个node，后面文中详细解释
func (t *Trie) hashRoot(db *Database, onleaf LeafCallback) (node, node, error) {
	if t.root == nil 
		return hashNode(emptyRoot.Bytes()), nil, nil
	h := newHasher(t.cachegen, t.cachelimit, onleaf) //涉及到haser.go，后面解释
	defer returnHasherToPool(h)
	return h.hash(t.root, db, true)  //为每个节点生成一个未编码的hash，该方法后面具体会详解
}

上述代码我们了解到：

  • 每Commit()一次，该trie的cachegen就会加1
  • 最终Commit()方法返回的是trie.root所指向的node的hash（未编码）。
  • 其中的hashRoot()方法目的是返回trie.root所指向的node的hash以及每个节点都带有各自hash的trie树的root。
  • 期间会涉及到hasher.go中的操作，它维护着一个操作trie中hash相关的对象池，我们也发现，在hashRoot()中最重要的就是它的hash()方法，接下来我们就好好探索一下它的具体实现。

haser.go的hash()方法

这个方法主要就是为每个节点都生成一个hash，
来一坨代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
func (h *hasher) hash(n node, db *Database, force bool) (node, node, error) {
	if hash, dirty := n.cache(); hash != nil {
		if db == nil 
			return hash, n, nil
		if n.canUnload(h.cachegen, h.cachelimit) {
			cacheUnloadCounter.Inc(1)
			return hash, hash, nil
		}
		if !dirty 
			return hash, n, nil
	}
	collapsed, cached, err := h.hashChildren(n, db) //处理每个节点
	if err != nil 
		return hashNode{}, n, err
	hashed, err := h.store(collapsed, db, force) //将当前节点生成hash，这方法很重要，下一节讲
	if err != nil 
		return hashNode{}, n, err

	cachedHash, _ := hashed.(hashNode)
	switch cn := cached.(type) {
	case *shortNode:
		cn.flags.hash = cachedHash //将当前节点的hasn保存在flags中
		if db != nil 
			cn.flags.dirty = false
	case *fullNode:  //和上面一样操作
		cn.flags.hash = cachedHash
		if db != nil 
			cn.flags.dirty = false
	}
	return hashed, cached, nil  //返回当前节点的hash以及当前节点本身
}

//依次处理trie中的每个节点
func (h *hasher) hashChildren(original node, db *Database) (node, node, error) {
	var err error
	switch n := original.(type) {
	case *shortNode:
		collapsed, cached := n.copy(), n.copy()  //递归算下来，相当于复制了两个新的trie
		collapsed.Key = hexToCompact(n.Key) //将前缀hex转为compact，方便磁盘存储
		cached.Key = common.CopyBytes(n.Key) //将key字节数组复制给cached
		if _, ok := n.Val.(valueNode); !ok {
			collapsed.Val, cached.Val, err = h.hash(n.Val, db, false)
			if err != nil 
				return original, original, err
		}
		if collapsed.Val == nil 
			collapsed.Val = valueNode(nil) //确保不为nil
		return collapsed, cached, nil  //前者是用于磁盘存储的节点，后者是hash化的节点，可以称为轻节点

	case *fullNode:
		collapsed, cached := n.copy(), n.copy()
		for i := 0; i < 16; i++ {
			if n.Children[i] != nil { //类似，处理每个节点
				collapsed.Children[i], cached.Children[i], err = h.hash(n.Children[i], db, false)
				if err != nil 
					return original, original, err
			} else 
				collapsed.Children[i] = valueNode(nil) //确保不会出现nil
		}
		cached.Children[16] = n.Children[16]
		if collapsed.Children[16] == nil 
			collapsed.Children[16] = valueNode(nil)
		return collapsed, cached, nil

	default:
		return n, original, nil
	}
}

纠结了半天，小编觉得也没什么注释可以写的。具体的这里来解释吧：

  • hash()方法很重要，最终它返回了头节点的hash以及每个子节点都带有hash的头节点。（头节点就是为了让trie.root最终指向它）
    它主要完成了3个任务：
    • 缓存管理，检测是否要释放某节点
    • 递归调用hashChildren()处理每个节点，它返回的是两个node，具体看下面的解释。
    • 调用store()方法生成每个节点的hash，并保存在当前节点中，store()方法很重要，我们下一节单独讲
  • hashChildren()方法主要就是为了处理树中的每个节点，比如：将shortNode的前缀key转为Compact编码，将nil数据处理一下。小编认为这个方法真正最主要的目的就是将当前所在节点复制了两份（分别叫做collapsed, cached），这样此时加上原先传入的总共就有3份当前节点数据了。复制的两份，其中一份collapsed是为了将来db磁盘存储；而另一份cached会保留在内存中，回调结束后trie.root会指向这个cached，这样，原先的那一份就会被gc了（trie.root原先是指向这一份），

haser.go的store()方法（涉及缓存）

我们上面提到了hashChildren()返回的是两个node，其中一个叫做collapsed的当前node被传入了store()方法中，而它只返回了一个当前node的hash。
前面我们已经知道collapsed节点做了部分处理，它最终目的是保存在db磁盘的。当它的节点本身被rlp序列化，就可以直接传入db保存了。
store()方法就是用来rlp序列化collapsed节点并将其插入db磁盘中，当前节点的hash也是由它来生成的。
具体我们来看这样一坨代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func (h *hasher) store(n node, db *Database, force bool) (node, error) {
	if _, isHash := n.(hashNode); n == nil || isHash //空数据或者hashNode，则不处理
		return n, nil
	h.tmp.Reset() //缓存初始化
	if err := rlp.Encode(h.tmp, n); err != nil //将当前node序列化
		panic("encode error: " + err.Error())
	if h.tmp.Len() < 32 && !force 
		return n, nil //编码后的node长度小于32，若force为true，则可确保所有节点都被编码
	// 长度过大的，则都将被新计算出来的hash取代
	hash, _ := n.cache()  //取出当前节点的hash
	if hash == nil {  //如果hash
		h.sha.Reset()
		h.sha.Write(h.tmp.Bytes())  //将rlp编码的节点数据传入hash工具
		hash = hashNode(h.sha.Sum(nil))  //根据传入的节点信息，生成hash
	}
	if db != nil {
		db.lock.Lock()

		hash := common.BytesToHash(hash)
		db.insert(hash, h.tmp.Bytes()) //将其插入db

		switch n := n.(type) {
		case *shortNode:
			if child, ok := n.Val.(hashNode); ok //指向的是分支节点
				db.reference(common.BytesToHash(child), hash) //用于统计当前节点的信息，比如当前节点有几个子节点，当前有效的节点数
		case *fullNode:
			for i := 0; i < 16; i++ {
				if child, ok := n.Children[i].(hashNode); ok 
					db.reference(common.BytesToHash(child), hash)
			}
		}
		db.lock.Unlock()

		if h.onleaf != nil { //onleaf是回调时候使用的，记得trie.Commit(x)里的那个参数吧，就是它
			switch n := n.(type) {
			case *shortNode:
				if child, ok := n.Val.(valueNode); ok 
					h.onleaf(child, hash)
			case *fullNode:
				for i := 0; i < 16; i++ 
					if child, ok := n.Children[i].(valueNode); ok {
						h.onleaf(child, hash)
				}
			}
		}
	}
	return hash, nil
}

代码中重要的一点就是hash的生成，它是根据序列化后的节点生成的。
注意看db的插入，根据hash来插入rlp序列化的节点，到时候我们就能根据这个hash来还愿整个节点了。而要注意的一点是该hash是32位的原始hash，并未经过任何编码，最终该方法返回的hash也没有经过任何处理
另外stroe()方法传入的有个参数叫force，通过代码我们得知，如果设置为true，则即使长度再小的节点，也要进行rlp编码
剩下的代码，小编发现没什么要讲的。。。代码不复杂，写的都很清楚，能注释的也都注释了，

缓存机制（轻节点）

讲了半天，就剩缓存没讲了，再次回到haser.go的hash()方法，这时候再来看这个缓存机制就很容易理解了。
代码看这里
还记得Trie树的结构里面有两个参数， 一个是cachegen,一个是cachelimit。这两个参数就是cache控制的参数。 Trie树每一次调用Commit方法，会导致当前的cachegen增加1。
数据节点插入时候（代码看这里），会把当前trie的cachegen存放到该节点中。
要知道，只要trie路径上新增或者删除一个节点，整个路径的节点都需要重新实例化，也就是节点中的nodeFlag被初始化了。都需要重新更新到db磁盘。
node.go源码中有针对每种node实现的canUnload()方法，大体上是当trie.cachegen - node.cachegen > cachelimit和dirty=false（表示当前节点未发生变化）条件满足时就会返回true（说明该节点数据始终没有发生变化，自己好好悟悟这句话吧，最好拿数据实际操作一下）,此时hash()方法中，就不会返回节点数据，而是返回节点的一个hash值。

轻节点

小编在以太坊源码解读-第3.1讲-trie原理介绍中已经初步介绍了轻节点的概念，根据上述缓存机制，我们返回的只有hash节点本身。这其实就是我们所说的轻节点。。。貌似小编没有什么需要继续往下说的了。。。一路看下来这篇文章的同学，应该会很容易理解这个吧。

proof.go 源码

看了下，总共有三个方法：

  • Prove()：根据给定的key，在trie中，将满足key中最大长度前缀的路径上的节点都加入到proofDb（队列中每个元素满足：未编码的hash以及对应rlp编码后的节点）
  • VerifyProof()：验证proffDb中是否存在满足输入的hash，和对应key的节点，如果满足，则返回rlp解码后的该节点。

具体代码小编就不列了，也不复杂，有兴趣的可以看看

database.go源码

它对ethdb做了进一步封装，方便trie中节点的插入删除操作，具体代码小编等下一次讲ethdb.go的时候再来解释。现在就不说了。

iterator.go源码

以太坊提供的对trie树的遍历工具，有兴趣的看看，这里也不解释了，小编也懒得看了。

security_trie.go源码

这个可以理解为加密了的trie的实现，ecurity_trie包装了一下trie树， 所有的key都转换成keccak256算法计算的hash值。同时在数据库里面存储hash值对应的原始的key。
但是官方在代码里也注释了，这个代码不稳定，除了测试用例，别的地方并没有使用该代码。

总结

还有几个trie模块下的代码文件，小逼没有提到，不是说不重要，只是小编的精力主要集中在trie的整体逻辑。关于trie，写了两篇文章，写了将近半个月，涉及的比较多，有些地方写的不一定合理，大家可以留言指出。

Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2017-2023 Jason
  • Visitors: | Views:

谢谢打赏～

微信