本篇文章分析的源碼地址為：https://github.com/ethereum/go-ethereum
分支：master
commit id: 257bfff316e4efb8952fbeb67c91f86af579cb0a

引言

在上篇文章中凳寺，我們講解了以太坊中Trie的主要原理。在這篇文章里，我們通過(guò)探索源代碼來(lái)進(jìn)一步了解以太坊trie模塊揉忘。

以太坊trie模塊位于項(xiàng)目目錄下的trie目錄吮便。下面我們先學(xué)習(xí)下模塊導(dǎo)出的功能和用法画舌，然后結(jié)合源代碼介紹一下目錄的組織結(jié)構(gòu)和框架。

trie模塊使用方法

trie模塊提供了四個(gè)主要的對(duì)象和接口：Trie欢伏、SecureTrie主慰、NodeIterator嚣州、TrieSync、Database共螺。下面分別介紹该肴。

Trie

Trie對(duì)象實(shí)現(xiàn)了Merkle Patricia Tree的全部功能，包括(key, value)對(duì)的增刪改查藐不、計(jì)算默克爾哈希匀哄，以及將整個(gè)樹寫入數(shù)據(jù)庫(kù)中。

你可以使用trie.New或trie.NewTrieWithPrefix來(lái)創(chuàng)建或打開(kāi)一個(gè)Trie對(duì)象佳吞。trie.NewTrieWithPrefix相對(duì)于trie.New的不同之處在于拱雏，你需要提供一個(gè)前綴串，每次查詢或?qū)懭?key, value)對(duì)時(shí)底扳，都會(huì)自動(dòng)將這個(gè)前綴串加到key的前面铸抑，然后再執(zhí)行相應(yīng)操作。

Trie對(duì)象提供的方法名都很簡(jiǎn)潔易懂衷模，幾乎所有方法都可以根據(jù)名字知道其功能鹊汛。這里我們只是簡(jiǎn)單羅列一下蒲赂，不一一詳細(xì)說(shuō)明。

func (t *Trie) NodeIterator(start []byte) NodeIterator
func (t *Trie) PrefixIterator(prefix []byte) NodeIterator
func (t *Trie) Get(key []byte) []byte
func (t *Trie) TryGet(key []byte) ([]byte, error)
func (t *Trie) Update(key, value []byte)
func (t *Trie) TryUpdate(key, value []byte)
func (t *Trie) Delete(key []byte)
func (t *Trie) TryDelete(key []byte) error
func (t *Trie) Root() []byte
func (t *Trie) Hash() common.Hash
func (t *Trie) Commit() (root common.Hash, err error)
func (t *Trie) CommitTo(db DatabaseWriter) (root common.Hash, err error)
func (t *Trie) SetCacheLimit(l uint16)
func (t *Trie) Prove(key []byte, fromLevel uint, proofDb DatabaseWriter) error

SecureTrie

SecureTrie對(duì)象實(shí)現(xiàn)了Trie相同的功能刁憋，實(shí)際上它內(nèi)部幾乎都是調(diào)用Trie對(duì)象的方法實(shí)現(xiàn)的滥嘴。唯一不同的是，SecureTrie中的所有方法會(huì)將傳入的key計(jì)算一個(gè)哈希至耻，然后把這個(gè)哈希當(dāng)作key進(jìn)行操作若皱。因此你無(wú)法通過(guò)根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上的信息拼湊出key的內(nèi)容，這也是它叫作"Secure"的原因尘颓。

SecureTrie提供的方法與Trie類似走触，這里不再細(xì)說(shuō)。唯一需要注意的是疤苹，對(duì)SecureTrie節(jié)點(diǎn)進(jìn)行枚舉時(shí)互广，想要獲取原始的key值，需要多調(diào)用一步SecureTrie.GetKey卧土。因?yàn)?code>NodeIterator.LeafKey和Iterator.Key得到的是加密后的key惫皱，需要調(diào)用SecureTrie.GetKey得到原始key。

NodeIterator

NodeIterator是一個(gè)接口尤莺，如名字所示旅敷，它提供了遍歷樹內(nèi)部所有結(jié)點(diǎn)的功能。它提供的方法如下：

func (it NodeIterator) Next(bool) bool
func (it NodeIterator) Error() error
func (it NodeIterator) Hash() common.Hash
func (it NodeIterator) Parent() common.Hash
func (it NodeIterator) Path() []byte
func (it NodeIterator) Leaf() bool
func (it NodeIterator) LeafBlob() []byte
func (it NodeIterator) LeafKey() []byte

NodeIterator的核心是Next方法缝裁，每調(diào)用一次這個(gè)方法扫皱，NodeIterator對(duì)象當(dāng)前代表的結(jié)點(diǎn)就會(huì)更新至下一個(gè)結(jié)點(diǎn)，此時(shí)你可以調(diào)用其它方法獲取這個(gè)結(jié)點(diǎn)的信息捷绑。當(dāng)所有結(jié)點(diǎn)遍歷結(jié)束，Next方法返回false氢妈。所以使用NodeIterator接口的代碼一般形式都像這樣：

for it.Next(true) {
  ... // 現(xiàn)在it代表一了一個(gè)新的結(jié)點(diǎn)粹污，你可以調(diào)用其它方法如it.Hash等，獲取這個(gè)結(jié)點(diǎn)的信息
}

需要注意的是首量，NodeIterator接口對(duì)結(jié)點(diǎn)的遍歷是有序的壮吩。其實(shí)Trie就是一棵有序樹，而遍歷的內(nèi)部實(shí)現(xiàn)就是按照Key從短到長(zhǎng)加缘、從小到大的順序進(jìn)行的鸭叙。（然而貌似并沒(méi)有文檔寫明并保證遍歷是有序的）

生成NodeIterator結(jié)口的方法有3種。我們分別說(shuō)明一下拣宏。

1.調(diào)用和Trie.NodeIterator或Trie.PrefixIterator
如果你想遍歷某個(gè)Trie對(duì)象的所有結(jié)點(diǎn)沈贝，可以調(diào)用Trie對(duì)象的方法NodeIterator()或PrefixIterator()，這倆個(gè)方法都返回一個(gè)NodeIterator接口用來(lái)進(jìn)行遍歷勋乾。NodeIterator()的start參數(shù)可以讓你有選擇的指定從哪個(gè)路徑開(kāi)始遍歷宋下，如果為nil則從頭到尾按順序遍歷嗡善。PrefixIterator()方法能過(guò)參數(shù)指定前綴后，其返回的NodeIterator接口只會(huì)遍歷路徑中包含了你指定前綴的結(jié)點(diǎn)学歧。

2.調(diào)用NewDifferenceIterator
NewDifferenceIterator函數(shù)的功能如名字所示罩引，只遍歷不同的部分。當(dāng)你調(diào)用NewDifferenceIterator(a, b NodeIterator)后枝笨，生成的NodeIterator只遍歷存在于b但不存在于a中的結(jié)點(diǎn)袁铐。

3.調(diào)用NewUnionIterator
NewUnionIterator也如名字所示，會(huì)把多個(gè)NodeIterator當(dāng)成一個(gè)合集進(jìn)行遍歷横浑。當(dāng)你調(diào)用NewUnionIterator(its []NodeIterator)后昭躺，生成的NodeIterator遍歷的結(jié)點(diǎn)是所有傳入的結(jié)點(diǎn)的合集。

另外我們不得不強(qiáng)調(diào)一下NewIterator函數(shù)伪嫁，因?yàn)槲矣X(jué)得這個(gè)函數(shù)更常用到领炫。這個(gè)函數(shù)用來(lái)枚舉樹中的所有(key, value)對(duì)，而不是每個(gè)結(jié)點(diǎn)（多數(shù)情況下我們并不關(guān)心中間結(jié)點(diǎn)的數(shù)據(jù)）张咳。這個(gè)函數(shù)聲明如下：

func NewIterator(it NodeIterator) *Iterator

它并不返回NodeIterator帝洪，而是返回Iterator指針對(duì)象。Iterator是一個(gè)結(jié)構(gòu)體脚猾，只有一個(gè)方法葱峡。定義如下：

type Iterator struct {
  nodeIt NodeIterator

  Key   []byte // Current data key on which the iterator is positioned on
  Value []byte // Current data value on which the iterator is positioned on
  Err   error
}

//Iteartor的Next方法
func (it *Iterator) Next() bool

可以看到Iterator結(jié)構(gòu)體導(dǎo)出了Key、Value龙助、Err三個(gè)字段砰奕。每調(diào)用一次Next方法，Key提鸟、Value和Err字段就會(huì)被更新军援。以下是一段使用NewIterator的示例：

//假設(shè)tr是一個(gè)Trie變量，并且包含了("hi", "lili"), ("hello", "world"), ("good", "morning")三對(duì)數(shù)據(jù)
it := trie.NewIterator(tr.NodeIterator(nil))
for it.Next {
  if it.Err != nil {
    fmt.Println(it.Err)
    continue
  }
  fmt.Println(it.Key, it.Value)
}

//輸出：
//good morning
//hello world
//hi lili

注意上面例子的三個(gè)輸出是按Key從小到大排序的称勋，這并非偶然胸哥。剛才已經(jīng)說(shuō)過(guò)NodeIterator的遍歷是有序的，因此這里的輸出也肯定是有序的赡鲜。

TrieSync

TrieSync不是trie模塊的主要功能空厌，應(yīng)用得也比較少，只在以太坊的downloader模塊中用來(lái)輔助同步代表State的trie對(duì)象银酬。與TrieSync有關(guān)的有以下幾個(gè)方法：

func NewTrieSync(root common.Hash, database DatabaseReader, callback TrieSyncLeafCallback) *TrieSync
func (s *TrieSync) AddSubTrie(root common.Hash, depth int, parent common.Hash, callback TrieSyncLeafCallback)
func (s *TrieSync) AddRawEntry(hash common.Hash, depth int, parent common.Hash)
func (s *TrieSync) Missing(max int) []common.Hash
func (s *TrieSync) Process(results []SyncResult) (bool, int, error)
func (s *TrieSync) Commit(dbw DatabaseWriter) (int, error)
func (s *TrieSync) Pending() int

其中NewTrieSync用來(lái)生成一個(gè)新的TrieSync對(duì)象并調(diào)用AddSubTrie方法為同步root結(jié)點(diǎn)作準(zhǔn)備嘲更。Peinding用來(lái)獲取當(dāng)前的Trie對(duì)象有幾個(gè)結(jié)點(diǎn)待同步；而Missing則返回待同步結(jié)點(diǎn)的哈希揩瞪。當(dāng)調(diào)用者通過(guò)網(wǎng)絡(luò)獲取到這些結(jié)點(diǎn)的數(shù)據(jù)時(shí)赋朦，它會(huì)調(diào)用Process進(jìn)行處理。在Process內(nèi)部會(huì)解析并記錄這些結(jié)點(diǎn)，如果解析結(jié)果表示它們還有子結(jié)點(diǎn)北发，則加入missing和pending隊(duì)列里纹因。當(dāng)調(diào)用者再次調(diào)用Missing方法時(shí)，就會(huì)獲取到這些缺失的子結(jié)點(diǎn)的哈希琳拨。這樣不斷循環(huán)瞭恰，直到Pending隊(duì)列為空，表示所有結(jié)點(diǎn)同步完成狱庇。整個(gè)過(guò)程的示意代碼如下：

trSync := trie.NewTrieSync(root, db, callback)
for trSync.Pending() != 0 {
  missHashs := trSync.Missing(0)

  results := downloadTrieNode(missHashs)

  trSync.Process(results)
}

trSync.Commit(db)

我們可以看到TrieSync并不具備同步的功能惊畏，它只是對(duì)結(jié)點(diǎn)的解析和組裝。所以我覺(jué)得這個(gè)名字起得很有迷惑性密任，如果是我颜启，我會(huì)把它叫做TrieBuilder。

Database

Database是trie模塊對(duì)真正數(shù)據(jù)庫(kù)的緩存層浪讳，其目的是對(duì)緩存的節(jié)點(diǎn)進(jìn)行引用計(jì)數(shù)缰盏，從而實(shí)現(xiàn)區(qū)塊的修剪功能。Database對(duì)外提供的方法有：

func NewDatabase(diskdb ethdb.Database) *Database
func NewDatabaseWithCache(diskdb ethdb.Database, cache int) *Database
func (db *Database) DiskDB() DatabaseReader
func (db *Database) InsertBlob(hash common.Hash, blob []byte)
func (db *Database) Node(hash common.Hash) ([]byte, error)
func (db *Database) Nodes() []common.Hash
func (db *Database) Reference(child common.Hash, parent common.Hash)
func (db *Database) Dereference(root common.Hash)
func (db *Database) Cap(limit common.StorageSize) error
func (db *Database) Commit(node common.Hash, report bool) error
func (db *Database) Size() (common.StorageSize, common.StorageSize)

其中NewDatabase或NewDatabaseWithCache用來(lái)創(chuàng)建一個(gè)Database對(duì)象淹遵，其參數(shù)diskdb是一個(gè)數(shù)據(jù)庫(kù)接口口猜。

在以太坊早期的trie模塊中是沒(méi)有Database對(duì)象的，加上這個(gè)就是為了增加節(jié)點(diǎn)引用計(jì)數(shù)功能透揣，實(shí)現(xiàn)區(qū)塊的修剪济炎。詳細(xì)信息我們后面再進(jìn)行介紹。

目錄結(jié)構(gòu)

trie模塊功能的實(shí)現(xiàn)代碼全部位于以太坊項(xiàng)目的trie目錄中辐真，且沒(méi)有子目錄须尚。下面我們對(duì)主要的源代碼文件作簡(jiǎn)單的說(shuō)明。

• encoding.go
  在上篇文章中我們提到過(guò)在Trie內(nèi)部key的最小單位是nibble而不是byte侍咱，以及key在從數(shù)據(jù)庫(kù)存取的時(shí)候是如何編碼的耐床。這個(gè)文件里的幾個(gè)函數(shù)實(shí)現(xiàn)了這兩大塊功能。（nibble就是將一個(gè)byte的高4位和低4位拆成倆字節(jié)得到的值放坏，比如將0xab拆成[0xa 0xb]咙咽，具體請(qǐng)參看trie上篇）

• hasher.go
  hasher.go中的代碼實(shí)現(xiàn)了從某個(gè)結(jié)點(diǎn)開(kāi)始計(jì)算子樹的哈希的功能∮倌辏可以說(shuō)這個(gè)文件里的代碼實(shí)現(xiàn)了以太坊的Trie的默克爾樹特性。

• node.go
  在上篇文章中我們介紹過(guò)為了縮短無(wú)分支路徑上的結(jié)點(diǎn)數(shù)量蜡豹，以太坊使用了不同的結(jié)點(diǎn)類型和結(jié)構(gòu)麸粮。這個(gè)文件里的代碼就是定義了一個(gè)Trie樹中所有結(jié)點(diǎn)的類型和解析的代碼。

• sync.go
  sync.go中的代碼實(shí)現(xiàn)了前面說(shuō)的SyncTrie對(duì)象的定義和所有方法镜廉。

• iterator.go
  iterator.go中的代碼定義了所有枚舉相關(guān)接口和實(shí)現(xiàn)弄诲。

• secure_trie.go
  secure_trie.go中的代碼實(shí)現(xiàn)了SecureTrie對(duì)象。

• errors.go
  errors.go中只定義了一個(gè)結(jié)構(gòu)體：MissingNodeError。當(dāng)找不到相應(yīng)的結(jié)點(diǎn)時(shí)齐遵，就會(huì)返回這個(gè)錯(cuò)誤寂玲。

• proof.go
  proof.go中只包含了Prove和VerifyProof兩個(gè)函數(shù)，它們只在輕量級(jí)以太坊子協(xié)議（LES）中被使用梗摇。這兩個(gè)函數(shù)被用來(lái)提供自己擁有某一對(duì)(key, value)的證明數(shù)據(jù)拓哟，和對(duì)數(shù)據(jù)進(jìn)行驗(yàn)證。

• trie.go
  trie.go實(shí)現(xiàn)了Trie對(duì)象的主要邏輯功能伶授。

• database.go
  database.go實(shí)現(xiàn)了Database對(duì)象的主要邏輯功能断序。

實(shí)現(xiàn)框架

前面我們說(shuō)過(guò)，以太坊的trie模塊提供了4個(gè)主要的對(duì)象和接口：Trie糜烹、SecureTrie违诗、SyncTrie和NodeIterator。然而trie模塊的核心功能是Trie對(duì)象疮蹦，所以我們這里僅針對(duì)Trie作介紹（SecureTrie與Trie是類似的诸迟，實(shí)際上SecureTrie基本上是調(diào)用了Trie的方法）。

Trie對(duì)象的功能總得來(lái)看可以分成兩部分：(key,value)的增刪改查和Hash與Commit功能愕乎。下面我們分別對(duì)其介紹阵苇。

Trie對(duì)象的增刪改查

Trie對(duì)象的Get、Update妆毕、Delete等方法實(shí)現(xiàn)了其增刪改查的功能（當(dāng)然也包含TryXXX等幾個(gè)類似的方法）慎玖。其實(shí)Trie對(duì)象本質(zhì)上是一棵樹，對(duì)于樹的增刪改查操作笛粘，也就是對(duì)樹的某一路徑上所有結(jié)點(diǎn)的訪問(wèn)趁怔。所以在Get/Delete等方法的實(shí)現(xiàn)代碼里，主體結(jié)構(gòu)就是對(duì)節(jié)點(diǎn)類型的type switch薪前，并根據(jù)不同的節(jié)點(diǎn)類型和目的（新增或刪除）對(duì)節(jié)點(diǎn)進(jìn)行操作润努。我對(duì)這一過(guò)程進(jìn)行了一下規(guī)納，如下圖：

從圖中可以看出示括，在key的驅(qū)動(dòng)下铺浇，我們循環(huán)獲取當(dāng)前部分key所對(duì)應(yīng)的結(jié)點(diǎn)（不斷的“查字典”），并根據(jù)節(jié)點(diǎn)類型的不同使用不同的方式獲取下一個(gè)結(jié)點(diǎn)垛膝。具體來(lái)說(shuō)鳍侣，如果是shortNode，則其value存儲(chǔ)的是下一個(gè)結(jié)點(diǎn)吼拥；如果是fullNode倚聚，則Children數(shù)組中存儲(chǔ)的是下一個(gè)節(jié)點(diǎn)------你需要根據(jù)key的值來(lái)確定到底是數(shù)組中的哪個(gè)元素；如果是hashNode凿可，則說(shuō)明這個(gè)結(jié)點(diǎn)還沒(méi)有被從數(shù)據(jù)庫(kù)中加載惑折，只是存了一個(gè)結(jié)點(diǎn)哈希而已，因此要先載入并解析，再進(jìn)行處理惨驶；如果是valueNode白热，則說(shuō)明找到了key對(duì)應(yīng)的value值，停止查找粗卜。

從以上的流程中也可以看出屋确，要理解Trie以太坊中Trie的實(shí)現(xiàn)，關(guān)鍵要理解這4個(gè)結(jié)點(diǎn)類型以及它們是如何被使用的休建。在上篇中我們已經(jīng)詳細(xì)介紹過(guò)shortNode和fullNode的設(shè)計(jì)原理乍恐，這里我們?cè)俳Y(jié)合代碼，詳細(xì)地介紹一下這四個(gè)節(jié)點(diǎn)以及它們?cè)诖a中的用法测砂。

在介紹4個(gè)結(jié)點(diǎn)類型之前茵烈，我們必須先說(shuō)明一下node類型。這是一個(gè)接口類型砌些，是4個(gè)結(jié)點(diǎn)類型的抽象（上面提到的type switch就是針對(duì)這個(gè)node接口類型進(jìn)行的）呜投。在shortNode和fullNode中，使用node接口代表其子結(jié)點(diǎn)存璃，而不管子結(jié)點(diǎn)是什么類型仑荐。

fullNode

我們首先來(lái)看fullNode的定義：

// code in node.go
fullNode struct {
  Children [17]node
  flags    nodeFlag
}

結(jié)構(gòu)體中flags字段記錄了一些結(jié)點(diǎn)的其它信息，可以忽略不看纵东，我們重點(diǎn)關(guān)注Children字段粘招。上篇中我們提到過(guò)根據(jù)數(shù)據(jù)的元素個(gè)數(shù)來(lái)區(qū)分fullNode和shortNode類型，這里可以看到Children字段恰好就是一個(gè)17個(gè)元素的數(shù)據(jù)（是的偎球，寫入數(shù)據(jù)庫(kù)時(shí)只寫入Children洒扎，而不寫入flags字段）。

相信你現(xiàn)在已經(jīng)可以很好地理解對(duì)fullNode的相關(guān)操作了衰絮。當(dāng)遇到一個(gè)fullNode時(shí)袍冷，我們將key[pos]作為索引，從Children數(shù)組中取出下一個(gè)結(jié)點(diǎn)猫牡。這里不得不提一下key[pos]的值為16的情況胡诗。上篇中我們提到過(guò)兩個(gè)情況：一是[]byte類型的key在Trie內(nèi)部會(huì)被轉(zhuǎn)換成nibble數(shù)組，并在nibble數(shù)組最后添加一個(gè)值16代表key已到達(dá)結(jié)尾（參考keybytesToHex函數(shù)）;二是fullNode的17個(gè)元素中最后一個(gè)元素代表的是value而不是子結(jié)點(diǎn)淌友。因此這里如果key[pos]的值是16煌恢，則取到的是Children數(shù)組的最后一個(gè)元素，也就是value震庭。相信到這里症虑，你可以完全理解為什么要在key尾部加一個(gè)值，以及為什么這個(gè)值是16而不是17或18等其它值归薛。

shortNode

shortNode的定義如下：

//code in node.go
shortNode struct {
  Key   []byte
  Val   node
  flags nodeFlag
}

同樣的我們忽略flags字段。可以看到shortNode有兩個(gè)元素：Key和Val主籍，這與我們之前介紹的一致（17個(gè)元素的是fullNode习贫，2個(gè)元素的是shortNode）。

當(dāng)遇到一個(gè)shortNode時(shí)千元，首先要對(duì)比key是否有shortNode.Key保存的前綴苫昌，如果是則Val字段代表了下一個(gè)結(jié)點(diǎn)，如果不是幸海，則代表樹中根本存在key這條路徑祟身。

shortNode稍微特殊一點(diǎn)的處理是新加分支。比如一個(gè)shortNode的Key保存的是"hello"物独，現(xiàn)在要新增一個(gè)key為"held"袜硫，那么就要把shortNode一分為二，中間插入一個(gè)fullNode挡篓。這個(gè)過(guò)程雖然麻煩一些但不難理解婉陷，我們這里就不詳細(xì)展開(kāi)了。

hashNode

hashNode的定義如下：

type hashNode []byte

hashNode就是一個(gè)簡(jiǎn)單的byte slice官研，它的內(nèi)容就是某個(gè)結(jié)點(diǎn)的哈希（所以才叫做hashNode）秽澳。為什么會(huì)有這個(gè)結(jié)點(diǎn)類型呢？

這個(gè)類型的存在是由結(jié)點(diǎn)從數(shù)據(jù)庫(kù)中延遲加載的機(jī)制造成的戏羽。之前我們說(shuō)過(guò)担神，Trie的數(shù)據(jù)是存儲(chǔ)在數(shù)據(jù)庫(kù)中的。當(dāng)我們使用某個(gè)root哈希創(chuàng)建一個(gè)新的Trie對(duì)象時(shí)始花，不會(huì)將所有子結(jié)點(diǎn)都一下子加載到內(nèi)存中妄讯，而是用到再去加載。例如當(dāng)我們創(chuàng)建新的Trie對(duì)象時(shí)衙荐，會(huì)根據(jù)root哈希從數(shù)據(jù)庫(kù)中加載根結(jié)點(diǎn)捞挥。假設(shè)根結(jié)點(diǎn)是一個(gè)fullNode，那我們接下來(lái)是否要繼續(xù)將它的16個(gè)子結(jié)點(diǎn)加載到內(nèi)存中呢忧吟？答案是不需要的砌函，我們只需要讓根結(jié)點(diǎn)的Children數(shù)組保存子結(jié)點(diǎn)的哈希（其類型當(dāng)然是hashNode），在需要時(shí)使用這個(gè)哈希從數(shù)據(jù)庫(kù)中加載溜族，并替換掉原來(lái)的哈希讹俊。其它結(jié)點(diǎn)的處理方法也是這樣。這就是hashNode的意義煌抒。

valueNode

valueNode的定義如下：

type valueNode []byte

與hashNode類似仍劈，valueNode也是一個(gè)byte slice。它的意義是代表value數(shù)據(jù)寡壮，而不再是一個(gè)結(jié)點(diǎn)了（雖然名字里仍有node這個(gè)詞）贩疙。如果在訪問(wèn)結(jié)點(diǎn)時(shí)遇到這個(gè)類型的結(jié)點(diǎn)讹弯，說(shuō)明已經(jīng)找到了key所對(duì)應(yīng)的value。

Trie的Hash與Commit

Trie的另一個(gè)非常有特色的地方在于这溅，它可以做永久性存儲(chǔ)组民，也可以像默克爾樹那樣，獲取根結(jié)點(diǎn)的哈希悲靴。這一小節(jié)里我們對(duì)這兩個(gè)特性做個(gè)簡(jiǎn)單的介紹臭胜。

其實(shí)的樹類數(shù)據(jù)結(jié)構(gòu)想要做永久性存儲(chǔ)，面臨的問(wèn)題都差不多癞尚。我覺(jué)得一個(gè)最主要的問(wèn)題是耸三，在數(shù)據(jù)庫(kù)中沒(méi)有了內(nèi)存指針，如何對(duì)子結(jié)點(diǎn)進(jìn)行引用浇揩。解決這個(gè)問(wèn)題的方法有多種仪壮，比如為每個(gè)結(jié)點(diǎn)編號(hào)且存儲(chǔ)時(shí)將指針改為編號(hào)；或者像以太坊這樣使用結(jié)點(diǎn)哈希引用結(jié)點(diǎn)临燃。這些方法的道理都是類似的睛驳。

之所以將這兩個(gè)功能放在一起講，也是因?yàn)樗鼈儍?nèi)部的實(shí)現(xiàn)實(shí)際上用的是同一段代碼膜廊。Trie.Hash和Trie.Commit方法最終都會(huì)調(diào)用內(nèi)部方法Trie.hashRoot（Trie對(duì)象中還有兩個(gè)方法Trie.Root和Trie.CommitTo乏沸，但與Trie.Hash、Trie.Commit都是一樣的代碼）爪瓜。在hashRoot方法中蹬跃，會(huì)調(diào)用內(nèi)部對(duì)象hasher的hash方法。這個(gè)方法的就是遍歷當(dāng)前樹在內(nèi)存中每一個(gè)結(jié)點(diǎn)铆铆，將所有shortNode和fullNode結(jié)點(diǎn)變成hashNode（代碼中叫壓縮蝶缀，collapsed）。直接看代碼會(huì)更容易理解這個(gè)過(guò)程（下面的代碼都是經(jīng)過(guò)簡(jiǎn)化的薄货，目的是為了更清晰的描述計(jì)算Trie的Hash和寫入數(shù)據(jù)庫(kù)的方法）

Trie.Hash

func (t *Trie) Hash() common.Hash {
  //注意hashRoot的參數(shù)為nil翁都，即只計(jì)算哈希不保存到數(shù)據(jù)庫(kù)中
  hash, cached, _ := t.hashRoot(nil)
  t.root = cached
  return hash
}

Trie.Commit

func (t *Trie) Commit() (root common.Hash, err error) {
  hash, cached, err := t.hashRoot(db)
  t.root = cached
  return hash
}

Trie.hashRoot

func (t *Trie) hashRoot(db DatabaseWriter) (node, node, error) {
  h := newHasher()
  return h.hash(t.root, db, true)
}

hasher.hash及相關(guān)代碼：

//hash返回的第一個(gè)node為hashNode，第二個(gè)node為傳入?yún)?shù)n的緩存（其實(shí)也可以理解成拷貝）
//collapsed為「壓縮的」樹谅猾，即它的所有子孫結(jié)點(diǎn)都是 hashNode柄慰。
func (h *hasher) hash(n node, db DatabaseWriter, force bool) (node, node, error) {
  collapsed, cached, err := h.hashChildren(n, db)

  hashed, err := h.store(collapsed, db, force)
  return hashed, cached, err
}

//hashChildren 以給定的結(jié)點(diǎn)為根，將這個(gè)子樹「壓縮」税娜。
//所謂「壓縮」坐搔，就是將所有子孫結(jié)點(diǎn)變成 hashNode 類型（并將原始節(jié)點(diǎn)存儲(chǔ)到數(shù)據(jù)庫(kù)中）。
//hashChildren 的第一個(gè)返回值正是「壓縮」樹的根敬矩；第二個(gè)node為傳入?yún)?shù)original的緩存
func (h *hasher) hashChildren(original node, db DatabaseWriter) (node, node, error) {
  switch n := original.(type) {
  case *shortNode:
    collapsed := n.copy()
    collapsed.Key = hexToCompact(n.Key)

    cached := n.copy()
    cached.Key = common.CopyBytes(n.Key)

    if _, ok := n.Val.(valueNode); !ok {
      collapsed.Val, cached.Val, err = h.hash(n.Val, db, false)
    }
    return collapsed, cached, nil

  case *fullNode:
    // Hash the full node's children, caching the newly hashed subtrees
    collapsed, cached := n.copy(), n.copy()

    for i := 0; i < 16; i++ {
      collapsed.Children[i], cached.Children[i], err = h.hash(n.Children[i], db, false)
    }
    cached.Children[16] = n.Children[16]
    return collapsed, cached, nil

  default:
    // Value and hash nodes don't have children so they're left as were
    return n, original, nil
  }
}


//h.store計(jì)算collapsed結(jié)點(diǎn)的哈希概行；如果db不為nil，則將collapsed結(jié)點(diǎn)保存到db中弧岳。
//Trie.Hash和Trie.Commit的區(qū)別也僅僅體現(xiàn)在這里凳忙。將普通結(jié)點(diǎn)變?yōu)閔ashNode這一操作也是
//發(fā)生在這里
func (h *hasher) store(n node, db DatabaseWriter, force bool) (node, error) {
  h.tmp.Reset()
  if err := rlp.Encode(h.tmp, n); err != nil {
    panic("encode error: " + err.Error())
  }

  h.sha.Reset()
  h.sha.Write(h.tmp.Bytes())
  hash = hashNode(h.sha.Sum(nil)) //將普通結(jié)點(diǎn)轉(zhuǎn)變成對(duì)應(yīng)的hashNode

  if db != nil {
    return hash, db.Put(hash, h.tmp.Bytes())
  }
  return hash, nil
}

注意上面hasher.hash和hasher.hashChildren的實(shí)現(xiàn)业踏。這兩個(gè)方法通過(guò)相互的遞歸調(diào)用，從葉子結(jié)點(diǎn)開(kāi)始逐步地將所有結(jié)點(diǎn)變成hashNode消略。

hasher.hash 始終維護(hù)著兩棵樹堡称，它的前兩個(gè)返回值分別為這兩棵樹的根。第一棵樹的所有結(jié)點(diǎn)都是 hashNode 類型艺演，包括根結(jié)點(diǎn)，因此使用這棵樹可以很快的獲得整棵樹的哈希桐臊；第二棵樹是原始的樹胎撤，其結(jié)點(diǎn)可能是 fullNode 或 shortNode（當(dāng)然也可能是其它類型）。使用這棵樹可以防止每次調(diào)用 Trie.Hash 或 Trie.Commit 后断凶，所有結(jié)點(diǎn)都被變成了 hashNode伤提，后續(xù)再次調(diào)用 Trie.Get 等方法時(shí)又得從數(shù)據(jù)庫(kù)中重新加載。

hasher.hashChildren 用來(lái)將某個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)變成 hashNode 類型认烁。作為 hasher.hash 的輔助方法肿男，hasher.hashChildren 也維護(hù)了兩棵樹，不同的是它的第一棵樹的根（也就是第一個(gè)返回值）并不是 hashNode 類型却嗡，只是這個(gè)根的所有子孫結(jié)點(diǎn)是 hashNode 類型而已舶沛。

Database

前面我們說(shuō)過(guò)，在早期的以太坊trie版本中是沒(méi)有Database對(duì)象的窗价，后來(lái)加上這個(gè)對(duì)象就是用來(lái)實(shí)現(xiàn)區(qū)塊的修剪功能（關(guān)于區(qū)塊的修剪可以參看這里）如庭。那么Database是怎么實(shí)現(xiàn)的呢？那就是對(duì)內(nèi)存中的trie樹節(jié)點(diǎn)進(jìn)行引用計(jì)數(shù)撼港，當(dāng)引用計(jì)數(shù)為時(shí)坪它，從內(nèi)存中刪除此節(jié)點(diǎn)。

在Database結(jié)構(gòu)體中帝牡，對(duì)trie樹節(jié)點(diǎn)實(shí)現(xiàn)引用計(jì)數(shù)功能的字段是dirties往毡，它的類型是map[common.Hash]*cachedNode。其中cachedNode代表的是一個(gè)有引用計(jì)數(shù)的節(jié)點(diǎn)靶溜，它的定義如下：

type cachedNode struct {
  node node   // node接口
  size uint16

  parents  uint32                 // 引用當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量
  children map[common.Hash]uint16 // 當(dāng)前節(jié)點(diǎn)的子結(jié)點(diǎn)的引用計(jì)數(shù)

  flushPrev common.Hash // flush-list列表的字段
  flushNext common.Hash
}

在這個(gè)結(jié)構(gòu)體中开瞭，parents和children實(shí)現(xiàn)了引用計(jì)數(shù)功能。而flushPrev和flushNext將當(dāng)前節(jié)點(diǎn)加入到了flush-list鏈表中墨技。

insert

我們先看看寫入節(jié)點(diǎn)時(shí)會(huì)發(fā)生什么惩阶。當(dāng)調(diào)用trie的Commit方法時(shí)，最終會(huì)調(diào)用Database.insert方法扣汪，且Database.InsertBlob其實(shí)也是調(diào)用insert方法断楷，因此我們從這個(gè)方法看起：

func (db *Database) insert(hash common.Hash, blob []byte, node node) {
  //已存在立即返回
  if _, ok := db.dirties[hash]; ok {
    return
  }
  //構(gòu)造cacheNode
  entry := &cachedNode{
    node:      simplifyNode(node),
    size:      uint16(len(blob)),
    flushPrev: db.newest,
  }
  //引用子節(jié)點(diǎn)，將所有子節(jié)點(diǎn)的parents加1
  for _, child := range entry.childs() {
    if c := db.dirties[child]; c != nil {
      c.parents++
    }
  }
  db.dirties[hash] = entry

  //加入flush-list鏈表
  if db.oldest == (common.Hash{}) {
    db.oldest, db.newest = hash, hash
  } else {
    db.dirties[db.newest].flushNext, db.newest = hash, hash
  }
  db.dirtiesSize += common.StorageSize(common.HashLength + entry.size)
}

Database.insert的主要邏輯非常簡(jiǎn)單崭别，就是構(gòu)造一個(gè)新加入的cacheNode節(jié)點(diǎn)冬筒，然后增加所有子節(jié)點(diǎn)的引用計(jì)數(shù)（parents字段）恐锣。注意這里并沒(méi)有增加新節(jié)點(diǎn)自身的parents計(jì)數(shù)，因?yàn)檫@里只是往數(shù)據(jù)庫(kù)里加入一個(gè)新節(jié)點(diǎn)舞痰，沒(méi)有證據(jù)顯示有人引用了這個(gè)節(jié)點(diǎn)土榴。

reference

以太坊在進(jìn)行區(qū)塊的修剪時(shí)會(huì)調(diào)用Database.Reference和Database.Dereference兩個(gè)方法。為了分析的完整一些响牛，我們先來(lái)看看修剪時(shí)的調(diào)用：

func (bc *BlockChain) writeBlockWithState(block *types.Block, receipts []*types.Receipt, state *state.StateDB) (status WriteStatus, err error) {
  ......
  if bc.cacheConfig.Disabled {
    ......  
  } else {
    triedb.Reference(root, common.Hash{}) // metadata reference to keep trie alive
    ......

      for !bc.triegc.Empty() {
        ......
        triedb.Dereference(root.(common.Hash))
      }
  }
}

這里先引用一整棵樹玷禽，經(jīng)過(guò)一些判斷和處理，再找合適機(jī)會(huì)解引用這棵樹（詳細(xì)分析請(qǐng)參看這里）呀打。

對(duì)節(jié)點(diǎn)進(jìn)行引用的功能主要在Database.reference中實(shí)現(xiàn)矢赁，我們來(lái)看看這個(gè)方法：

func (db *Database) reference(child common.Hash, parent common.Hash) {
  //如果child節(jié)點(diǎn)不在緩存中，立即返回
  node, ok := db.dirties[child]
  if !ok {
    return
  }
  //如果children字段不存在則構(gòu)造并繼續(xù)后面的執(zhí)行贬丛。
  //如果children已存在說(shuō)明已經(jīng)引用過(guò)子節(jié)點(diǎn)了撩银，那么如果child變量代表的不是根節(jié)點(diǎn)，就直接返回
  if db.dirties[parent].children == nil {
    db.dirties[parent].children = make(map[common.Hash]uint16)
  } else if _, ok = db.dirties[parent].children[child]; ok && parent != (common.Hash{}) {
    return
  }

  //增加引用計(jì)數(shù)
  node.parents++
  db.dirties[parent].children[child]++
}

這個(gè)方法就是增加child和parent節(jié)點(diǎn)的各自的引用計(jì)數(shù)豺憔。但這里有一個(gè)特殊的地方额获，就是如果child已經(jīng)被parent引用過(guò)了，且child代表的不是一個(gè)根節(jié)點(diǎn)恭应，那么就不繼續(xù)增加parent對(duì)child的引用了抄邀；如果child代表一個(gè)根節(jié)點(diǎn)，還是要繼續(xù)增加parent對(duì)child的引用暮屡。

這個(gè)處理有些難以理解撤摸，我們多解釋一下。當(dāng)父節(jié)點(diǎn)已經(jīng)引用過(guò)某個(gè)子節(jié)點(diǎn)時(shí)褒纲，不再增加對(duì)子節(jié)點(diǎn)的引用是合理的准夷，因?yàn)橐粋€(gè)父節(jié)點(diǎn)只能引用 某個(gè)特定的子節(jié)點(diǎn) 一次，不存在引用多次的情況莺掠。但為什么parent為common.Hash{}時(shí)衫嵌，還要繼續(xù)引用呢？

這是因?yàn)樵谡{(diào)用Database.Reference時(shí)彻秆，如果child參數(shù)是一個(gè)根節(jié)點(diǎn)楔绞，那么parent的值肯定是common.Hash{}，也即common.Hash{}是任一trie樹的根節(jié)點(diǎn)的父節(jié)點(diǎn)唇兑；所以這里判斷parent是否是common.Hash{}极谊，也就是在判斷child參數(shù)是否是一個(gè)根節(jié)點(diǎn)黄娘。對(duì)根節(jié)點(diǎn)的引用與對(duì)普通節(jié)點(diǎn)引用的不同之處在于，普通節(jié)點(diǎn)的引用發(fā)生在trie樹的內(nèi)部，因此剛才說(shuō)了王带，一個(gè)父節(jié)點(diǎn)只能引用 某個(gè)特定的子節(jié)點(diǎn) 一次砂竖；而根節(jié)點(diǎn)是可以被trie樹以外的地方引用的，比如在miner模塊中引用了某個(gè)trie樹的根節(jié)點(diǎn)，然后blockchain模塊又對(duì)這個(gè)根節(jié)點(diǎn)引用了一次图甜。所以這種情況不存在common.Hash{}只能引用某個(gè)根節(jié)點(diǎn)一次的情況。

deference

下面我們?cè)賮?lái)看看解引用的代碼鳖眼。解引用主要在Database.dereference中實(shí)現(xiàn)：

func (db *Database) dereference(child common.Hash, parent common.Hash) {
  // Dereference the parent-child
  node := db.dirties[parent]

  //首先解除父節(jié)點(diǎn)對(duì)子節(jié)點(diǎn)的引用
  if node.children != nil && node.children[child] > 0 {
    node.children[child]--
    if node.children[child] == 0 {
      delete(node.children, child)
    }
  }

  //如果child不存在黑毅，立即返回
  node, ok := db.dirties[child]
  if !ok {
    return
  }

  //減小對(duì)child參數(shù)代表的節(jié)點(diǎn)的引用
  if node.parents > 0 {
    node.parents--
  }

  //如果沒(méi)人再引用這個(gè)節(jié)點(diǎn)，則刪除它
  if node.parents == 0 {
    //將這個(gè)節(jié)點(diǎn)從flush-list中刪除
    switch child {
      ......
    }

    //解除對(duì)所有子節(jié)點(diǎn)的引用钦讳，然后刪除節(jié)點(diǎn)
    for _, hash := range node.childs() {
      db.dereference(hash, child)
    }
    delete(db.dirties, child)
    db.dirtiesSize -= common.StorageSize(common.HashLength + int(node.size))
  }
}

這段代碼邏輯也比較簡(jiǎn)單矿瘦，已經(jīng)用中文注釋進(jìn)行了說(shuō)明，這里就不再贅述了蜂厅。但需要多說(shuō)一點(diǎn)的時(shí)匪凡，只有某個(gè)節(jié)點(diǎn)將要被刪除時(shí)，才會(huì)解引用所有子節(jié)點(diǎn)掘猿，而不是解引用某個(gè)節(jié)點(diǎn)的同時(shí)也解引用所有子節(jié)點(diǎn)。想象一下存在一個(gè)引用計(jì)數(shù)為2的節(jié)點(diǎn)A唇跨，它有一個(gè)引用計(jì)數(shù)為1的節(jié)點(diǎn)B（也即B只被A引用了）稠通。當(dāng)我們對(duì)A進(jìn)行解引用時(shí)，A的計(jì)數(shù)變成了1买猖，如果我們此時(shí)同時(shí)解引用A的子節(jié)點(diǎn)改橘，那么B的計(jì)數(shù)將變成0從而被刪除，但A仍然需要這么節(jié)點(diǎn)玉控。因此只有當(dāng)A的引用計(jì)數(shù)變?yōu)?將要被刪除時(shí)飞主，才應(yīng)該解引用它的所有子節(jié)點(diǎn)。

flush-list

前面我們多次提到"flush-list"這個(gè)概念高诺，現(xiàn)在我們就來(lái)看看它是什么碌识。要了解flush-list，首先要了解Database.Cap的功能虱而。這個(gè)方法將緩存中的數(shù)據(jù)刷到真實(shí)的數(shù)據(jù)庫(kù)中筏餐，直到緩存占用的內(nèi)存量達(dá)到參數(shù)的要求。flush-list就是決定在刷新緩存時(shí)牡拇，先刷哪個(gè)節(jié)點(diǎn)魁瞪、最后刷哪個(gè)節(jié)點(diǎn)的一個(gè)雙向鏈表。Database.oldest和Database.newest定義了這個(gè)鏈表的頭和尾惠呼，鏈表的元素是cachedNode导俘，而將cacheNode加入到這個(gè)鏈表中的字段就是cacheNode.flushNext和cacheNode.flushPrev。

我們直接看一下Database.Cap是如何使用這個(gè)鏈表的：

func (db *Database) Cap(limit common.StorageSize) error {
  ......

  oldest := db.oldest
  for size > limit && oldest != (common.Hash{}) {
    // Fetch the oldest referenced node and push into the batch
    node := db.dirties[oldest]
    if err := batch.Put(oldest[:], node.rlp()); err != nil {
      db.lock.RUnlock()
      return err
    }

    ......

    size -= common.StorageSize(3*common.HashLength + int(node.size))
    oldest = node.flushNext
  }

  ......
}

可以看到這是一個(gè)典型的鏈表的遍歷剔蹋。至于其它對(duì)flush-list插入和刪除的代碼旅薄，相信在了解了它的功能以后，會(huì)很容易看懂滩租，因此這里就不再詳細(xì)說(shuō)明了赋秀。

總結(jié)

在這篇文章中利朵，我們結(jié)合源代碼，介紹了以太坊中trie模塊的功能與實(shí)現(xiàn)猎莲。trie模塊的代碼組織還是非常工整的绍弟，主要文件有trie.go、node.go著洼、hasher.go樟遣、encoding.go和iterator.go。

trie模塊的主要對(duì)象就是Trie身笤。想要理解Trie的實(shí)現(xiàn)原理豹悬，關(guān)鍵是弄明白代碼中的4種node類型，以及key的編碼規(guī)則（encoding.go）液荸。

唯一我覺(jué)得不太好的是瞻佛，在trie.go及其它源文件中，到處都是關(guān)于node的type switch娇钱。我覺(jué)得這幾乎完全可以放到一個(gè)函數(shù)中去做伤柄，至少可以不像現(xiàn)在這樣，在Get/Upate/Delete等方法中都有一套type switch文搂。

以上我是對(duì)以太坊的trie模塊的分析适刀，如有不對(duì)的地方還望不吝指正。

本文最先發(fā)表于我的博客煤蹭，歡迎評(píng)論和轉(zhuǎn)載笔喉。