乱色小说久久,一区二区九视频,久久亚洲日韩熟女精品

死磕以太坊源碼分析之MPT樹-下

文章以及資料請(qǐng)查看：https://github.com/blockchainGuide/

上篇主要介紹了以太坊中的MPT樹的原理，這篇主要會(huì)對(duì)MPT樹涉及的源碼進(jìn)行拆解分析。trie模塊主要有以下幾個(gè)文件：

|-encoding.go 主要講編碼之間的轉(zhuǎn)換
|-hasher.go 實(shí)現(xiàn)了從某個(gè)結(jié)點(diǎn)開始計(jì)算子樹的哈希的功能
|-node.go 定義了一個(gè)Trie樹中所有結(jié)點(diǎn)的類型和解析的代碼
|-sync.go 實(shí)現(xiàn)了SyncTrie對(duì)象的定義和所有方法
|-iterator.go 定義了所有枚舉相關(guān)接口和實(shí)現(xiàn)
|-secure_trie.go 實(shí)現(xiàn)了SecureTrie對(duì)象
|-proof.go 為key構(gòu)造一個(gè)merkle證明
|-trie.go Trie樹的增刪改查
|-database.go 對(duì)內(nèi)存中的trie樹節(jié)點(diǎn)進(jìn)行引用計(jì)數(shù)

實(shí)現(xiàn)概覽

encoding.go

這個(gè)主要是講三種編碼（KEYBYTES encoding、HEX encoding、COMPACT encoding）的實(shí)現(xiàn)與轉(zhuǎn)換，trie中全程都需要用到這些，該文件中主要實(shí)現(xiàn)了如下功能：

hex編碼轉(zhuǎn)換為Compact編碼：hexToCompact()
Compact編碼轉(zhuǎn)換為hex編碼：compactToHex()
keybytes編碼轉(zhuǎn)換為Hex編碼：keybytesToHex()
hex編碼轉(zhuǎn)換為keybytes編碼：hexToKeybytes()
獲取兩個(gè)字節(jié)數(shù)組的公共前綴的長度：prefixLen()

func hexToCompact(hex []byte) []byte {
    terminator := byte(0)
    if hasTerm(hex) { //檢查是否有結(jié)尾為0x10 => 16
        terminator = 1 //有結(jié)束標(biāo)記16說明是葉子節(jié)點(diǎn)
        hex = hex[:len(hex)-1] //去除尾部標(biāo)記
    }
    buf := make([]byte, len(hex)/2+1) // 字節(jié)數(shù)組
    
    buf[0] = terminator << 5 // 標(biāo)志byte為00000000或者00100000
    //如果長度為奇數(shù)，添加奇數(shù)位標(biāo)志1，并把第一個(gè)nibble字節(jié)放入buf[0]的低四位
    if len(hex)&1 == 1 {
        buf[0] |= 1 << 4 // 奇數(shù)標(biāo)志 00110000
        buf[0] |= hex[0] // 第一個(gè)nibble包含在第一個(gè)字節(jié)中 0011xxxx
        hex = hex[1:]
    }
    //將兩個(gè)nibble字節(jié)合并成一個(gè)字節(jié)
    decodeNibbles(hex, buf[1:])
    return buf

//compact編碼轉(zhuǎn)化為Hex編碼
func compactToHex(compact []byte) []byte {
    base := keybytesToHex(compact)
    base = base[:len(base)-1]
     // apply terminator flag
    // base[0]包括四種情況
    // 00000000 擴(kuò)展節(jié)點(diǎn)偶數(shù)位
    // 00000001 擴(kuò)展節(jié)點(diǎn)奇數(shù)位
    // 00000010 葉子節(jié)點(diǎn)偶數(shù)位
    // 00000011 葉子節(jié)點(diǎn)奇數(shù)位

    // apply terminator flag
    if base[0] >= 2 {
       //如果是葉子節(jié)點(diǎn)，末尾添加Hex標(biāo)志位16
        base = append(base, 16)
    }
    // apply odd flag
    //如果是偶數(shù)位，chop等于2，否則等于1
    chop := 2 - base[0]&1
    return base[chop:]
}

//compact編碼轉(zhuǎn)化為Hex編碼
func compactToHex(compact []byte) []byte {
    base := keybytesToHex(compact)
    base = base[:len(base)-1]
     // apply terminator flag
    // base[0]包括四種情況
    // 00000000 擴(kuò)展節(jié)點(diǎn)偶數(shù)位
    // 00000001 擴(kuò)展節(jié)點(diǎn)奇數(shù)位
    // 00000010 葉子節(jié)點(diǎn)偶數(shù)位
    // 00000011 葉子節(jié)點(diǎn)奇數(shù)位

    // apply terminator flag
    if base[0] >= 2 {
       //如果是葉子節(jié)點(diǎn)，末尾添加Hex標(biāo)志位16
        base = append(base, 16)
    }
    // apply odd flag
    //如果是偶數(shù)位，chop等于2，否則等于1
    chop := 2 - base[0]&1
    return base[chop:]
}

// 將十六進(jìn)制的bibbles轉(zhuǎn)成key bytes，這只能用于偶數(shù)長度的key
func hexToKeybytes(hex []byte) []byte {
    if hasTerm(hex) {
        hex = hex[:len(hex)-1]
    }
    if len(hex)&1 != 0 {
        panic("can't convert hex key of odd length")
    }
    key := make([]byte, (len(hex)+1)/2)
    decodeNibbles(hex, key)
    return key
}

// 返回a和b的公共前綴的長度
func prefixLen(a, b []byte) int {
    var i, length = 0, len(a)
    if len(b) < length {
        length = len(b)
    }
    for ; i < length; i++ {
        if a[i] != b[i] {
            break
        }
    }
    return i
}

node.go

四種節(jié)點(diǎn)

node 接口分四種實(shí)現(xiàn): fullNode，shortNode，valueNode，hashNode，其中只有 fullNode 和 shortNode 可以帶有子節(jié)點(diǎn)。

type (
    fullNode struct {
        Children [17]node // 分支節(jié)點(diǎn)
        flags    nodeFlag
    }
    shortNode struct { //擴(kuò)展節(jié)點(diǎn)
        Key   []byte
        Val   node //可能指向葉子節(jié)點(diǎn)，也可能指向分支節(jié)點(diǎn)。
        flags nodeFlag
    }
    hashNode  []byte
    valueNode []byte // 葉子節(jié)點(diǎn)值，但是該葉子節(jié)點(diǎn)最終還是會(huì)包裝在shortNode中
)

trie.go

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

iterator.go

nodeIterator提供了遍歷樹內(nèi)部所有結(jié)點(diǎn)的功能。其結(jié)構(gòu)如下：此結(jié)構(gòu)體是在trie.go定義的

type nodeIterator struct {
    trie.NodeIterator
    t   *odrTrie
    err error
}

里面包含了一個(gè)接口NodeIterator，它的實(shí)現(xiàn)則是由iterator.go來提供的，其方法如下：

func (it *nodeIterator) Next(descend bool) bool 
func (it *nodeIterator) Hash() common.Hash 
func (it *nodeIterator) Parent() common.Hash 
func (it *nodeIterator) Leaf() bool 
func (it *nodeIterator) LeafKey() []byte 
func (it *nodeIterator) LeafBlob() []byte 
func (it *nodeIterator) LeafProof() [][]byte 
func (it *nodeIterator) Path() []byte {}
func (it *nodeIterator) seek(prefix []byte) error 
func (it *nodeIterator) peek(descend bool) (*nodeIteratorState, *int, []byte, error) 
func (it *nodeIterator) nextChild(parent *nodeIteratorState, ancestor common.Hash) (*nodeIteratorState, []byte, bool) 
func (it *nodeIterator) push(state *nodeIteratorState, parentIndex *int, path []byte) 
func (it *nodeIterator) pop()

NodeIterator的核心是Next方法，每調(diào)用一次這個(gè)方法，NodeIterator對(duì)象代表的當(dāng)前節(jié)點(diǎn)就會(huì)更新至下一個(gè)節(jié)點(diǎn)，當(dāng)所有結(jié)點(diǎn)遍歷結(jié)束，Next方法返回false。

生成NodeIterator結(jié)口的方法有以下3種：

①：Trie.NodeIterator(start []byte)

通過start參數(shù)指定從哪個(gè)路徑開始遍歷，如果為nil則從頭到尾按順序遍歷。

②：NewDifferenceIterator(a, b NodeIterator)

當(dāng)調(diào)用NewDifferenceIterator(a, b NodeIterator)后，生成的NodeIterator只遍歷存在于 b 但不存在于 a 中的結(jié)點(diǎn)。

③：NewUnionIterator(iters []NodeIterator)

當(dāng)調(diào)用NewUnionIterator(its []NodeIterator)后，生成的NodeIterator遍歷的結(jié)點(diǎn)是所有傳入的結(jié)點(diǎn)的合集。

database.go

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

func NewDatabase(diskdb ethdb.KeyValueStore) *Database
func NewDatabaseWithCache(diskdb ethdb.KeyValueStore, cache int) *Database 
func (db *Database) DiskDB() ethdb.KeyValueReader
func (db *Database) InsertBlob(hash common.Hash, blob []byte)
func (db *Database) insert(hash common.Hash, blob []byte, node node)
func (db *Database) insertPreimage(hash common.Hash, preimage []byte)
func (db *Database) node(hash common.Hash) node
func (db *Database) Node(hash common.Hash) ([]byte, error)
func (db *Database) preimage(hash common.Hash) ([]byte, error)
func (db *Database) secureKey(key []byte) []byte
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) dereference(child common.Hash, parent common.Hash)
func (db *Database) Cap(limit common.StorageSize) error
func (db *Database) Commit(node common.Hash, report bool) error

security_trie.go

可以理解為加密了的trie的實(shí)現(xiàn)，ecurity_trie包裝了一下trie樹，所有的key都轉(zhuǎn)換成keccak256算法計(jì)算的hash值。同時(shí)在數(shù)據(jù)庫里面存儲(chǔ)hash值對(duì)應(yīng)的原始的key。
但是官方在代碼里也注釋了，這個(gè)代碼不穩(wěn)定，除了測試用例，別的地方并沒有使用該代碼。

proof.go

Prove()：根據(jù)給定的key，在trie中，將滿足key中最大長度前綴的路徑上的節(jié)點(diǎn)都加入到proofDb（隊(duì)列中每個(gè)元素滿足：未編碼的hash以及對(duì)應(yīng)rlp編碼后的節(jié)點(diǎn)）
VerifyProof()：驗(yàn)證proffDb中是否存在滿足輸入的hash，和對(duì)應(yīng)key的節(jié)點(diǎn)，如果滿足，則返回rlp解碼后的該節(jié)點(diǎn)。

實(shí)現(xiàn)細(xì)節(jié)

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

①：Trie樹的初始化

如果root不為空，就通過resolveHash來加載整個(gè)Trie樹，如果為空，就新建一個(gè)Trie樹。

func New(root common.Hash, db *Database) (*Trie, error) {
    if db == nil {
        panic("trie.New called without a database")
    }
    trie := &Trie{
        db: db,
    }
    if root != (common.Hash{}) && root != emptyRoot {
        rootnode, err := trie.resolveHash(root[:], nil)
        if err != nil {
            return nil, err
        }
        trie.root = rootnode
    }
    return trie, nil
}

②：Trie樹的插入

首先Trie樹的插入是個(gè)遞歸調(diào)用的過程，它會(huì)從根開始找，一直找到合適的位置插入。

func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error)

參數(shù)說明：

n: 當(dāng)前要插入的節(jié)點(diǎn)
prefix: 當(dāng)前已經(jīng)處理完的key(節(jié)點(diǎn)共有的前綴)
key: 未處理完的部分key，完整的key = prefix + key
value：需要插入的值

返回值說明：

bool : 操作是否改變了Trie樹(dirty)
Node :插入完成后的子樹的根節(jié)點(diǎn)

接下來就是分別對(duì)shortNode、fullNode、hashNode、nil 幾種情況進(jìn)行說明。

2.1：節(jié)點(diǎn)為nil

空樹直接返回shortNode，此時(shí)整顆樹的根就含有了一個(gè)shortNode節(jié)點(diǎn)。

case nil:
        return true, &shortNode{key, value, t.newFlag()}, nil

2.2 ：節(jié)點(diǎn)為shortNode

首先計(jì)算公共前綴，如果公共前綴就等于key，那么說明這兩個(gè)key是一樣的，如果value也一樣的(dirty == false)，那么返回錯(cuò)誤。
如果沒有錯(cuò)誤就更新shortNode的值然后返回
如果公共前綴不完全匹配，那么就需要把公共前綴提取出來形成一個(gè)獨(dú)立的節(jié)點(diǎn)(擴(kuò)展節(jié)點(diǎn)),擴(kuò)展節(jié)點(diǎn)后面連接一個(gè)branch節(jié)點(diǎn)，branch節(jié)點(diǎn)后面看情況連接兩個(gè)short節(jié)點(diǎn)。
首先構(gòu)建一個(gè)branch節(jié)點(diǎn)(branch := &fullNode{flags: t.newFlag()}),然后再branch節(jié)點(diǎn)的Children位置調(diào)用t.insert插入剩下的兩個(gè)short節(jié)點(diǎn)

matchlen := prefixLen(key, n.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
        }
        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
        }
        if matchlen == 0 {
            return true, branch, nil
    }
        return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil

2.3: 節(jié)點(diǎn)為fullNode

節(jié)點(diǎn)是fullNode(也就是分支節(jié)點(diǎn))，那么直接往對(duì)應(yīng)的孩子節(jié)點(diǎn)調(diào)用insert方法,然后把對(duì)應(yīng)的孩子節(jié)點(diǎn)指向新生成的節(jié)點(diǎn)。

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

2.4: 節(jié)點(diǎn)為hashnode

暫時(shí)還在數(shù)據(jù)庫中的節(jié)點(diǎn)，先調(diào)用 t.resolveHash(n, prefix)來加載到內(nèi)存，然后調(diào)用insert方法來插入。

rn, err := t.resolveHash(n, prefix)
        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

③：Trie樹查詢值

其實(shí)就是根據(jù)輸入的hash，找到對(duì)應(yīng)的葉子節(jié)點(diǎn)的數(shù)據(jù)。主要看TryGet方法。

參數(shù)：

origNode：當(dāng)前查找的起始node位置
key：輸入要查找的數(shù)據(jù)的hash
pos：當(dāng)前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: //表示當(dāng)前trie是空樹
        return nil, nil, false, nil
    case valueNode: ////這就是我們要查找的葉子節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)
        return n, n, false, nil
    case *shortNode: ////在葉子節(jié)點(diǎn)或者擴(kuò)展節(jié)點(diǎn)匹配
        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
        }
        return value, n, didResolve, err
    case *fullNode://在分支節(jié)點(diǎn)匹配
        value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1)
        if err == nil && didResolve {
            n = n.copy()
            n.Children[key[pos]] = newnode
        }
        return value, n, didResolve, err
    case hashNode: //說明當(dāng)前節(jié)點(diǎn)是輕節(jié)點(diǎn)，需要從db中獲取
        child, err := t.resolveHash(n, key[:pos])
        if err != nil {
            return nil, n, true, err
        }
        value, newnode, _, err := t.tryGet(child, key, pos)
        return value, newnode, true, err
...
}

didResolve用于判斷trie樹是否會(huì)發(fā)生變化，tryGet()只是用來獲取數(shù)據(jù)的，當(dāng)hashNode去db中獲取該node值后需要更新現(xiàn)有的trie，didResolve就會(huì)發(fā)生變化。其他就是基本的遞歸查找樹操作。

④：Trie樹更新值

更新值，其實(shí)就是調(diào)用insert方法進(jìn)行操作。

到此Trie樹的增刪改查就講解的差不多了。

將節(jié)點(diǎn)寫入到Trie的內(nèi)存數(shù)據(jù)庫

如果要把節(jié)點(diǎn)寫入到內(nèi)存數(shù)據(jù)庫，需要序列化，可以先去了解下以太坊的Rlp編碼。這部分工作由trie.Commit()完成，當(dāng)trie.Commit(nil)，會(huì)執(zhí)行序列化和緩存等操作，序列化之后是使用的Compact Encoding進(jìn)行編碼，從而達(dá)到節(jié)省空間的目的。

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
    return common.BytesToHash(hash.(hashNode)), nil
}

上述代碼大概講了這些：

每次執(zhí)行Commit()，該trie的cachegen就會(huì)加 1
Commit()方法返回的是trie.root所指向的node的hash（未編碼）
其中的hashRoot()方法目的是返回trie.root所指向的node的hash以及每個(gè)節(jié)點(diǎn)都帶有各自hash的trie樹的root。

//為每個(gè)node生成一個(gè)hash
func (t *Trie) hashRoot(db *Database, onleaf LeafCallback) (node, node, error) {
    if t.root == nil {
        return hashNode(emptyRoot.Bytes()), nil, nil
    }
    h := newHasher(onleaf)
    defer returnHasherToPool(h)
    return h.hash(t.root, db, true) //為每個(gè)節(jié)點(diǎn)生成一個(gè)未編碼的hash
}

而hashRoot的核心方法就是 h.hash，它返回了頭節(jié)點(diǎn)的hash以及每個(gè)子節(jié)點(diǎn)都帶有hash的頭節(jié)點(diǎn)（Trie.root指向它），大致做了以下幾件事：

①：如果我們不存儲(chǔ)節(jié)點(diǎn)，而只是哈希，則從緩存中獲取數(shù)據(jù)

if hash, dirty := n.cache(); hash != nil {
        if db == nil {
            return hash, n, nil
        }
        if !dirty {
            switch n.(type) {
            case *fullNode, *shortNode:
                return hash, hash, nil
            default:
                return hash, n, nil
            }
        }
    }

②：遞歸調(diào)用h.hashChildren，求出所有的子節(jié)點(diǎn)的hash值，再把原有的子節(jié)點(diǎn)替換成現(xiàn)在子節(jié)點(diǎn)的hash值

2.1:如果節(jié)點(diǎn)是shortNode

首先把collapsed.Key從Hex Encoding 替換成 Compact Encoding, 然后遞歸調(diào)用hash方法計(jì)算子節(jié)點(diǎn)的hash和cache，從而把子節(jié)點(diǎn)替換成了子節(jié)點(diǎn)的hash值

collapsed, cached := n.copy(), n.copy()
        collapsed.Key = hexToCompact(n.Key)
        cached.Key = common.CopyBytes(n.Key)

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

2.2:節(jié)點(diǎn)是fullNode

遍歷每個(gè)子節(jié)點(diǎn)，把子節(jié)點(diǎn)替換成子節(jié)點(diǎn)的Hash值，否則的化這個(gè)節(jié)點(diǎn)沒有children。直接返回。

        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
                }
            }
        }
        cached.Children[16] = n.Children[16]
        return collapsed, cached, nil

③：存儲(chǔ)節(jié)點(diǎn)n的哈希值，如果我們指定了存儲(chǔ)層，它會(huì)寫對(duì)應(yīng)的鍵/值對(duì)

store()方法主要就做了兩件事：

rlp序列化collapsed節(jié)點(diǎn)并將其插入db磁盤中
生成當(dāng)前節(jié)點(diǎn)的hash
將節(jié)點(diǎn)哈希插入db

3.1：空數(shù)據(jù)或者h(yuǎn)ashNode，則不處理

if _, isHash := n.(hashNode); n == nil || isHash {
        return n, nil
    }

3.2:生成節(jié)點(diǎn)的RLP編碼

h.tmp.Reset()                                 // 緩存初始化
    if err := rlp.Encode(&h.tmp, n); err != nil { //將當(dāng)前node序列化
        panic("encode error: " + err.Error())
    }
    if len(h.tmp) < 32 && !force {
        return n, nil // Nodes smaller than 32 bytes are stored inside their parent 編碼后的node長度小于32，若force為true，則可確保所有節(jié)點(diǎn)都被編碼
    }
//長度過大的，則都將被新計(jì)算出來的hash取代
    hash, _ := n.cache() //取出當(dāng)前節(jié)點(diǎn)的hash
    if hash == nil {
        hash = h.makeHashNode(h.tmp) //生成哈希node
    }

3.3:將Trie節(jié)點(diǎn)合并到中間內(nèi)存緩存中

hash := common.BytesToHash(hash)
        db.lock.Lock()
        db.insert(hash, h.tmp, n)
        db.lock.Unlock()
        // Track external references from account->storage trie
        //跟蹤帳戶->存儲(chǔ)Trie中的外部引用
        if h.onleaf != nil {
            switch n := n.(type) {
            case *shortNode:
                if child, ok := n.Val.(valueNode); ok {  //指向的是分支節(jié)點(diǎn)
                    h.onleaf(child, hash) //用于統(tǒng)計(jì)當(dāng)前節(jié)點(diǎn)的信息，比如當(dāng)前節(jié)點(diǎn)有幾個(gè)子節(jié)點(diǎn)，當(dāng)前有效的節(jié)點(diǎn)數(shù)
                }
            case *fullNode:
                for i := 0; i < 16; i++ {
                    if child, ok := n.Children[i].(valueNode); ok {
                        h.onleaf(child, hash)
                    }
                }
            }
        }

到此為止將節(jié)點(diǎn)寫入到Trie的內(nèi)存數(shù)據(jù)庫就已經(jīng)完成了。

如果覺得文章不錯(cuò)可以關(guān)注公眾號(hào)：區(qū)塊鏈技術(shù)棧，詳細(xì)的所有以太坊源碼分析文章內(nèi)容以及代碼資料都在其中。

Trie樹緩存機(jī)制

Trie樹的結(jié)構(gòu)里面有兩個(gè)參數(shù)，一個(gè)是cachegen,一個(gè)是cachelimit。這兩個(gè)參數(shù)就是cache控制的參數(shù)。 Trie樹每一次調(diào)用Commit方法，會(huì)導(dǎo)致當(dāng)前的cachegen增加1。

func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error) {
   ...
    t.cachegen++
   ...
}

然后在Trie樹插入的時(shí)候，會(huì)把當(dāng)前的cachegen存放到節(jié)點(diǎn)中。

func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
            ....
            return true, &shortNode{n.Key, nn, t.newFlag()}, nil
}
func (t *Trie) newFlag() nodeFlag {
    return nodeFlag{dirty: true, gen: t.cachegen}
}

如果 trie.cachegen - node.cachegen > cachelimit，就可以把節(jié)點(diǎn)從內(nèi)存里面拿掉。也就是說節(jié)點(diǎn)經(jīng)過幾次Commit，都沒有修改，那么就把節(jié)點(diǎn)從內(nèi)存里面干掉。只要trie路徑上新增或者刪除一個(gè)節(jié)點(diǎn)，整個(gè)路徑的節(jié)點(diǎn)都需要重新實(shí)例化，也就是節(jié)點(diǎn)中的nodeFlag被初始化了。都需要重新更新到db磁盤。

拿掉節(jié)點(diǎn)過程在 hasher.hash方法中，這個(gè)方法是在commit的時(shí)候調(diào)用。如果方法的canUnload方法調(diào)用返回真，那么就拿掉節(jié)點(diǎn)，如果只返回了hash節(jié)點(diǎn)，而沒有返回node節(jié)點(diǎn)，這樣節(jié)點(diǎn)就沒有引用，不久就會(huì)被gc清除掉。節(jié)點(diǎn)被拿掉之后，會(huì)用一個(gè)hashNode節(jié)點(diǎn)來表示這個(gè)節(jié)點(diǎn)以及其子節(jié)點(diǎn)。如果后續(xù)需要使用，可以通過方法把這個(gè)節(jié)點(diǎn)加載到內(nèi)存里面來。

func (h *hasher) hash(n node, db *Database, force bool) (node, node, error) {
    ....
       // 從緩存中卸載節(jié)點(diǎn)。它的所有子節(jié)點(diǎn)將具有較低或相等的緩存世代號(hào)碼。
       cacheUnloadCounter.Inc(1)
  ...
}

參考&總結(jié)

這部分重要的內(nèi)容也就上面講述的，主要集中在Trie上面，如果有不對(duì)的地方，可以及時(shí)指正哦。

https://mindcarver.cn/about/

https://github.com/blockchainGuide/blockchainguide

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

死磕以太坊源碼分析之MPT樹-下

死磕以太坊源碼分析之MPT樹-下

實(shí)現(xiàn)概覽

encoding.go

node.go

四種節(jié)點(diǎn)

trie.go

iterator.go

database.go

security_trie.go

proof.go

實(shí)現(xiàn)細(xì)節(jié)

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

將節(jié)點(diǎn)寫入到Trie的內(nèi)存數(shù)據(jù)庫

Trie樹緩存機(jī)制

參考&總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

死磕以太坊源碼分析之MPT樹-下

實(shí)現(xiàn)概覽

encoding.go

node.go

四種節(jié)點(diǎn)

trie.go

iterator.go

database.go

security_trie.go

proof.go

實(shí)現(xiàn)細(xì)節(jié)

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

將節(jié)點(diǎn)寫入到Trie的內(nèi)存數(shù)據(jù)庫

Trie樹緩存機(jī)制

參考&總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av