摘要:是以太坊中存儲(chǔ)區(qū)塊數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu),它和融合一個(gè)樹形結(jié)構(gòu),理解結(jié)構(gòu)對(duì)之后學(xué)習(xí)以太坊區(qū)塊以及智能合約狀態(tài)存儲(chǔ)結(jié)構(gòu)的模塊源碼很有幫助。
MPT(Merkle Patricia Tries)是以太坊中存儲(chǔ)區(qū)塊數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu),它Merkle Tree和Patricia Tree融合一個(gè)樹形結(jié)構(gòu),理解MPT結(jié)構(gòu)對(duì)之后學(xué)習(xí)以太坊區(qū)塊header以及智能合約狀態(tài)存儲(chǔ)結(jié)構(gòu)的模塊源碼很有幫助。
首先來看下Merkle樹:
它的葉子是數(shù)據(jù)塊的hash,從圖中可以看出非葉子節(jié)點(diǎn)是其子節(jié)點(diǎn)串聯(lián)字符串的hash,底層數(shù)據(jù)的任何變動(dòng)都會(huì)影響父節(jié)點(diǎn),這棵樹的Merkle Root代表對(duì)底層所有數(shù)據(jù)的“摘要”。
這樣的樹有一個(gè)很大的好處,比如我們把交易信息寫入這樣的樹形結(jié)構(gòu),當(dāng)需要證明一個(gè)交易是否存在這顆樹中的時(shí)候,就不需要重新計(jì)算所有交易的hash值。比如證明圖中Hash 1-1,我們可以借助Hash 1-0重新計(jì)算出Hash 1,然后再借助Hash 0重新計(jì)算出Top Hash,這樣就可以根據(jù)算出來的Top Hash和原來的Top Hash是否一樣,如果一樣的話那么Hash 1-1就屬于這棵樹。
所以想象一下,我們將這個(gè)Top Hash儲(chǔ)存在區(qū)塊頭中,那么有了區(qū)塊頭就可以對(duì)區(qū)塊信息進(jìn)行驗(yàn)證了。同時(shí) Hash 計(jì)算的過程可以十分快速,預(yù)處理可以在短時(shí)間內(nèi)完成。利用Merkle樹結(jié)構(gòu)能帶來巨大的比較性能提升。
從它的名字壓縮前綴樹再結(jié)合上圖就可以猜出來Patricia樹的特點(diǎn)了,這種樹形結(jié)構(gòu)比將每一個(gè)字符作為一個(gè)節(jié)點(diǎn)的普通trie樹形結(jié)構(gòu),它的鍵值可以使用多個(gè)字符,降低了樹的高度,也節(jié)省了空間,再看個(gè)例子:
圖中可以很容易看出數(shù)中所存儲(chǔ)的鍵值對(duì):
6c0a5c71ec20bq3w => 5
6c0a5c71ec20CX7j => 27
6c0a5c71781a1FXq => 18
6c0a5c71781a9Dog => 64
6c0a8f743b95zUfe => 30
6c0a8f743b95jx5R => 2
6c0a8f740d16y03G => 43
6c0a8f740d16vcc1 => 48
以太坊中的MPT:在以太坊中MPT的節(jié)點(diǎn)的規(guī)格主要有一下幾個(gè):
NULL 空節(jié)點(diǎn),簡(jiǎn)單的表示空,在代碼中是一個(gè)空串
Nibble 它是key的基本單元,是一個(gè)四元組(四個(gè)bit位的組合例如二進(jìn)制表達(dá)的0010就是一個(gè)四元組)
Extension 擴(kuò)展節(jié)點(diǎn)有兩個(gè)元素,一個(gè)是key值,還有一個(gè)是hash值,這個(gè)hash值指向下一個(gè)節(jié)點(diǎn)
Branch 分支節(jié)點(diǎn)有17個(gè)元素,回到Nibble,四元組是key的基本單元,四元組最多有16個(gè)值。所以前16個(gè)必將落入到在其遍歷中的鍵的十六個(gè)可能的半字節(jié)值中的每一個(gè)。第17個(gè)是存儲(chǔ)那些在當(dāng)前結(jié)點(diǎn)結(jié)束了的節(jié)點(diǎn)(例如, 有三個(gè)key,分別是 (abc ,abd, ab) 第17個(gè)字段儲(chǔ)存了ab節(jié)點(diǎn)的值)
Leaf 葉子節(jié)點(diǎn)只有兩個(gè)元素,分別為key和value
這里還有一些知識(shí)點(diǎn)需要了解的,為了將MPT樹存儲(chǔ)到數(shù)據(jù)庫(kù)中,同時(shí)還可以把MPT樹從數(shù)據(jù)庫(kù)中恢復(fù)出來,對(duì)于Extension和Leaf的節(jié)點(diǎn)類型做了特殊的定義:如果是一個(gè)擴(kuò)展節(jié)點(diǎn),那么前綴為0,這個(gè)0加在key前面。如果是一個(gè)葉子節(jié)點(diǎn),那么前綴就是1。同時(shí)對(duì)key的長(zhǎng)度就奇偶類型也做了設(shè)定,如果是奇數(shù)長(zhǎng)度則標(biāo)示1,如果是偶數(shù)長(zhǎng)度則標(biāo)示0。
以太坊中主要有一下幾個(gè)地方用了MPT樹形結(jié)構(gòu):
State Trie 區(qū)塊頭中的狀態(tài)樹
key => sha3(以太坊賬戶地址address)
value => rlp(賬號(hào)內(nèi)容信息account)
Transactions Trie 區(qū)塊頭中的交易樹
key => rlp(交易的偏移量 transaction index)
每個(gè)塊都有各自的交易樹,且不可更改
Receipts Trie 區(qū)塊頭中的收據(jù)樹
key = rlp(交易的偏移量 transaction index)
每個(gè)塊都有各自的交易樹,且不可更改
Storage Trie 存儲(chǔ)樹
存儲(chǔ)只能合約狀態(tài)
每個(gè)賬號(hào)有自己的Storage Trie
這兩個(gè)區(qū)塊頭中,state root,tx root receipt root分別存儲(chǔ)了這三棵樹的樹根,第二個(gè)區(qū)塊顯示了當(dāng)賬號(hào)175的數(shù)據(jù)變更(27 -> 45)的時(shí)候,只需要存儲(chǔ)跟這個(gè)賬號(hào)相關(guān)的部分?jǐn)?shù)據(jù),而且老的區(qū)塊中的數(shù)據(jù)還是可以正常訪問。
MPT樹種還有一個(gè)重要的概念一個(gè)特殊的十六進(jìn)制前綴(hex-prefix, HP)編碼來對(duì)key編碼,我們先來了解一下編碼定義規(guī)則,源碼實(shí)現(xiàn)后面再分析:
RAW 原始編碼,對(duì)輸入不做任何變更
HEX 十六進(jìn)制編碼
RAW編碼輸入的每個(gè)字符分解為高4位和低4位
如果是葉子節(jié)點(diǎn),則在最后加上Hex值0x10表示結(jié)束
如果是分支節(jié)點(diǎn)不附加任何Hex值
比如key=>"bob",b的ASCII十六進(jìn)制編碼為0x62,o的ASCII十六進(jìn)制編碼為0x6f,分解成高四位和第四位,16表示終結(jié) 0x10,最終編碼結(jié)果為[6 2 6 15 6 2 16],
HEX-Prefix 十六進(jìn)制前綴編碼
輸入key結(jié)尾為0x10,則去掉這個(gè)終止符
key之前補(bǔ)一個(gè)四元組這個(gè)Byte第0位區(qū)分奇偶信息,第1位區(qū)分節(jié)點(diǎn)類型
如果輸入key的長(zhǎng)度是偶數(shù),則再添加一個(gè)四元組0x0在flag四元組后
將原來的key內(nèi)容壓縮,將分離的兩個(gè)byte以高四位低四位進(jìn)行合并
十六進(jìn)制前綴編碼相當(dāng)于一個(gè)逆向的過程,比如輸入的是[6 2 6 15 6 2 16],根據(jù)第一個(gè)規(guī)則去掉終止符16。根據(jù)第二個(gè)規(guī)則key前補(bǔ)一個(gè)四元組,從右往左第一位為1表示葉子節(jié)點(diǎn),從右往左第0位如果后面key的長(zhǎng)度為偶數(shù)設(shè)置為0,奇數(shù)長(zhǎng)度設(shè)置為1,那么四元組0010就是2。根據(jù)第三個(gè)規(guī)則,添加一個(gè)全0的補(bǔ)在后面,那么就是20.根據(jù)第三個(gè)規(guī)則內(nèi)容壓縮合并,那么結(jié)果就是[0x20 0x62 0x6f 0x62]
官方有一個(gè)詳細(xì)的結(jié)構(gòu)的示例:
下面再用一個(gè)圖像化的示例來加深一下對(duì)上面的MPT規(guī)則的理解
key的16進(jìn)制 | key | value |
---|---|---|
<64 6f> | do | verb |
<64 6f 67> | dog | puppy |
<64 6f 67 65> | doge | coin |
<68 6f 72 73 65> | horse | stallion |
Compact就是上面說的HEX-Prefix,keybytes為按完整字節(jié)(8bit)存儲(chǔ)的正常信息,hex為按照半字節(jié)nibble(4bit)儲(chǔ)存信息的格式。
go-ethereum/trie/encoding:
package trie 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 //如果長(zhǎng)度為奇數(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:] } // 將keybytes 轉(zhuǎn)成十六進(jìn)制 func keybytesToHex(str []byte) []byte { l := len(str)*2 + 1 //將一個(gè)keybyte轉(zhuǎn)化成兩個(gè)字節(jié) var nibbles = make([]byte, l) for i, b := range str { nibbles[i*2] = b / 16 nibbles[i*2+1] = b % 16 } //末尾加入Hex標(biāo)志位16 nibbles[l-1] = 16 return nibbles } // 將十六進(jìn)制的bibbles轉(zhuǎn)成key bytes,這只能用于偶數(shù)長(zhǎng)度的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 } func decodeNibbles(nibbles []byte, bytes []byte) { for bi, ni := 0, 0; ni < len(nibbles); bi, ni = bi+1, ni+2 { bytes[bi] = nibbles[ni]<<4 | nibbles[ni+1] } } // 返回a和b的公共前綴的長(zhǎng)度 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 } // 十六進(jìn)制key是否有結(jié)束標(biāo)志符 func hasTerm(s []byte) bool { return len(s) > 0 && s[len(s)-1] == 16 }以太坊中MTP數(shù)據(jù)結(jié)構(gòu)
上面已經(jīng)分析了以太坊的key的編碼方式,接下來我們來看以太坊中MPT樹的數(shù)據(jù)結(jié)構(gòu),在分析trie的數(shù)據(jù)結(jié)構(gòu)前,我們先來了解一下node的定義:
trie/node.go
type node interface { fstring(string) string cache() (hashNode, bool) canUnload(cachegen, cachelimit uint16) bool } type ( fullNode struct { //分支節(jié)點(diǎn) Children [17]node // Actual trie node data to encode/decode (needs custom encoder) flags nodeFlag } shortNode struct { Key []byte Val node flags nodeFlag } hashNode []byte valueNode []byte )
上面代碼中定義了四個(gè)struct,就是node的四種類型:
fullNode -> 分支節(jié)點(diǎn),它有一個(gè)容量為17的node數(shù)組成員變量Children,數(shù)組中前16個(gè)空位分別對(duì)應(yīng)16進(jìn)制(hex)下的0-9a-f,這樣對(duì)于每個(gè)子節(jié)點(diǎn),根據(jù)其key值16進(jìn)制形式下的第一位的值,就可掛載到Children數(shù)組的某個(gè)位置,fullNode本身不再需要額外key變量;Children數(shù)組的第17位,留給該fullNode的數(shù)據(jù)部分。這和我們上面說的Branch 分支節(jié)點(diǎn)的規(guī)格一致的。
shortNode,key是一個(gè)任意長(zhǎng)度的字符串(字節(jié)數(shù)組[]byte),體現(xiàn)了PatriciaTrie的特點(diǎn),通過合并只有一個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)和其子節(jié)點(diǎn)來縮短trie的深度,結(jié)果就是有些節(jié)點(diǎn)會(huì)有長(zhǎng)度更長(zhǎng)的key。
-> 擴(kuò)展節(jié)點(diǎn),Val指向分支節(jié)點(diǎn)或者葉子節(jié)點(diǎn)
-> 葉子節(jié)點(diǎn),Val為rlp編碼數(shù)據(jù),key為該數(shù)據(jù)的hash
valueNode -> MPT的葉子節(jié)點(diǎn)。字節(jié)數(shù)組[]byte的一個(gè)別名,不帶子節(jié)點(diǎn)。使用中valueNode就是所攜帶數(shù)據(jù)部分的RLP哈希值,長(zhǎng)度32byte,數(shù)據(jù)的RLP編碼值作為valueNode的匹配項(xiàng)存儲(chǔ)在數(shù)據(jù)庫(kù)里。
hashNode -> 字符數(shù)組[]byte的一個(gè)別名,存放32byte的哈希值,他是fullNode或者shortNode對(duì)象的RLP哈希值
來看下trie的結(jié)構(gòu)以及對(duì)trie的操作可能對(duì)上面各個(gè)node的類型使用可能會(huì)更清晰一點(diǎn),我們來接著看下trie的結(jié)構(gòu)定義
trie/trie.go:
type Trie struct { db *Database // 用levelDB做KV存儲(chǔ) root node //當(dāng)前根節(jié)點(diǎn) originalRoot common.Hash //啟動(dòng)加載時(shí)候的hash,可以從db中恢復(fù)出整個(gè)trie cachegen, cachelimit uint16 // cachegen 緩存生成值,每次Commit會(huì)+1 }
這里的cachegen緩存生成值會(huì)被附加在node節(jié)點(diǎn)上面,如果當(dāng)前的cachegen-cachelimit參數(shù)大于node的緩存生成,那么node會(huì)從cache里面卸載,以便節(jié)約內(nèi)存。一個(gè)緩存多久沒被時(shí)候用就會(huì)被從緩存中移除,看起來和redis等一些LRU算法的cache db很像。
Trie的初始化:
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, } if (root != common.Hash{}) && root != emptyRoot { // 如果hash不是空值,從數(shù)據(jù)庫(kù)中加載一個(gè)已經(jīng)存在的樹 rootnode, err := trie.resolveHash(root[:], nil) if err != nil { return nil, err } trie.root = rootnode //根節(jié)點(diǎn)為找到的trie } //否則返回新建一個(gè)樹 return trie, nil }
這里的trie.resolveHash就是加載整課樹的方法,還有傳入的root common.Hash hash是一個(gè)將hex編碼轉(zhuǎn)為原始hash的32位byte[] (common.HexToHash()),來看下如何通過這個(gè)hash來找到整個(gè)trie的:
func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) { cacheMissCounter.Inc(1) //沒執(zhí)行一次計(jì)數(shù)器+1 //上面說過了,n是一個(gè)32位byte[] hash := common.BytesToHash(n) //通過hash從db中取出node的RLP編碼內(nèi)容 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 }
mustDecodeNode中調(diào)用了decodeNode,這個(gè)方法通過RLP的list長(zhǎng)度來判斷該編碼內(nèi)容屬于上面節(jié)點(diǎn),如果是兩個(gè)字段則為shortNode,如果是17個(gè)字段則為fullNode,然后再調(diào)用各自的decode解析函數(shù)
func decodeNode(hash, buf []byte, cachegen uint16) (node, error) { if len(buf) == 0 { return nil, io.ErrUnexpectedEOF } elems, _, err := rlp.SplitList(buf) //將buf拆分為列表的內(nèi)容以及列表后的任何剩余字節(jié)。 if err != nil { return nil, fmt.Errorf("decode error: %v", err) } switch c, _ := rlp.CountValues(elems); c { case 2: n, err := decodeShort(hash, elems, cachegen) //decode shortNode return n, wrapError(err, "short") case 17: n, err := decodeFull(hash, elems, cachegen) //decode fullNode return n, wrapError(err, "full") default: return nil, fmt.Errorf("invalid number of list elements: %v", c) } }
decodeShort函數(shù)中通過key是否含有結(jié)束標(biāo)識(shí)符來判斷是葉子節(jié)點(diǎn)還是擴(kuò)展節(jié)點(diǎn),這個(gè)我們?cè)谏厦娴木幋a部分已經(jīng)講過,有結(jié)束標(biāo)示符則是葉子節(jié)點(diǎn),再通過rlp.SplitString解析出val生成一個(gè)葉子節(jié)點(diǎn)shortNode返回。沒有結(jié)束標(biāo)志符則為擴(kuò)展節(jié)點(diǎn),通過decodeRef解析并生成一個(gè)shortNode返回。
func decodeShort(hash, elems []byte, cachegen uint16) (node, error) { kbuf, rest, err := rlp.SplitString(elems) //將elems填入RLP字符串的內(nèi)容以及字符串后的任何剩余字節(jié)。 if err != nil { return nil, err } flag := nodeFlag{hash: hash, gen: cachegen} key := compactToHex(kbuf) if hasTerm(key) { // value node val, _, err := rlp.SplitString(rest) if err != nil { return nil, fmt.Errorf("invalid value node: %v", err) } return &shortNode{key, append(valueNode{}, val...), flag}, nil } r, _, err := decodeRef(rest, cachegen) if err != nil { return nil, wrapError(err, "val") } return &shortNode{key, r, flag}, nil }
繼續(xù)看下decodeRef主要做了啥操作:
func decodeRef(buf []byte, cachegen uint16) (node, []byte, error) { kind, val, rest, err := rlp.Split(buf) if err != nil { return nil, buf, err } switch { case kind == rlp.List: // "embedded" node reference. The encoding must be smaller // than a hash in order to be valid. if size := len(buf) - len(rest); size > hashLen { err := fmt.Errorf("oversized embedded node (size is %d bytes, want size < %d)", size, hashLen) return nil, buf, err } n, err := decodeNode(nil, buf, cachegen) return n, rest, err case kind == rlp.String && len(val) == 0: // empty node return nil, rest, nil case kind == rlp.String && len(val) == 32: return append(hashNode{}, val...), rest, nil default: return nil, nil, fmt.Errorf("invalid RLP string size %d (want 0 or 32)", len(val)) } }
這段代碼比較清晰,通過rlp.Split后返回的類型做不同的處理,如果是list,調(diào)用decodeNode解析,如果是空節(jié)點(diǎn)返回空,如果是一個(gè)32位hash值返回hashNode,decodeFull:
func decodeFull(hash, elems []byte, cachegen uint16) (*fullNode, error) { n := &fullNode{flags: nodeFlag{hash: hash, gen: cachegen}} for i := 0; i < 16; i++ { cld, rest, err := decodeRef(elems, cachegen) if err != nil { return n, wrapError(err, fmt.Sprintf("[%d]", i)) } n.Children[i], elems = cld, rest } val, _, err := rlp.SplitString(elems) if err != nil { return n, err } if len(val) > 0 { n.Children[16] = append(valueNode{}, val...) } return n, nil }
再回到Trie結(jié)構(gòu)體中的cachegen, cachelimit,Trie樹每次Commit時(shí)cachegen都會(huì)+1,這兩個(gè)參數(shù)是cache的控制參數(shù),為了弄清楚Trie的緩存機(jī)制,我們來看下Commit具體是干嘛的:
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 //返回所指向的node的未編碼的hash } //返回trie.root所指向的node的hash以及每個(gè)節(jié)點(diǎn)都帶有各自hash的trie樹的root。 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) defer returnHasherToPool(h) return h.hash(t.root, db, true)//為每個(gè)節(jié)點(diǎn)生成一個(gè)未編碼的hash }
Commit目的,是將trie樹中的key轉(zhuǎn)為Compact編碼,為每個(gè)節(jié)點(diǎn)生成一個(gè)hash,它就是為了確保后續(xù)能正常將變動(dòng)的數(shù)據(jù)提交到db.
那么這個(gè)cachegen是怎么放到該節(jié)點(diǎn)中的,當(dāng)trie樹在節(jié)點(diǎn)插入的時(shí)候,會(huì)把當(dāng)前trie的cachegen放入到該節(jié)點(diǎn)中,看下trie的insert方法:
//n -> trie當(dāng)前插入節(jié)點(diǎn) //prefix -> 當(dāng)前匹配到的key的公共前綴 //key -> 待插入數(shù)據(jù)當(dāng)前key中剩余未匹配的部分,完整的key=prefix+key //value -> 待插入數(shù)據(jù)本身 //返回 -> 是否改變樹,插入完成后子樹根節(jié)點(diǎn),error 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 } //如果key長(zhǎng)度為0,那么說明當(dāng)前節(jié)點(diǎn)中新增加的節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)數(shù)據(jù)一樣,認(rèn)為已經(jīng)新增過了就直接返回 return true, value, nil } switch n := n.(type) { case *shortNode: matchlen := prefixLen(key, n.Key) // 返回公共前綴長(zhǎng)度 if matchlen == len(n.Key) { //如果整個(gè)key匹配,請(qǐng)按原樣保留此節(jié)點(diǎn),并僅更新該值。 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 } //如果它在索引0處出現(xiàn)則用該branch替換shortNode if matchlen == 0 { return true, branch, nil } // Otherwise, replace it with a short node leading up to the branch. 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中添加一個(gè)節(jié)點(diǎn),就是葉子節(jié)點(diǎn),返回shortNode。 return true, &shortNode{key, value, t.newFlag()}, nil case hashNode: rn, err := t.resolveHash(n, prefix)//恢復(fù)一個(gè)存儲(chǔ)在db中的node if err != nil { return false, nil, err } dirty, nn, err := t.insert(rn, prefix, key, value) //遞歸調(diào)用 if !dirty || err != nil { return false, rn, err } return true, nn, nil default: panic(fmt.Sprintf("%T: invalid node: %v", n, n)) }
Trie樹的插入,這是一個(gè)遞歸調(diào)用的方法,從根節(jié)點(diǎn)開始,一直往下找,直到找到可以插入的點(diǎn),進(jìn)行插入操作。
如果當(dāng)前的根節(jié)點(diǎn)葉子節(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)。這里有個(gè)小細(xì)節(jié),key的編碼是HEX encoding,而且末尾帶了一個(gè)終結(jié)符??紤]我們的根節(jié)點(diǎn)的key是abc0x16,我們插入的節(jié)點(diǎn)的key是ab0x16。下面的branch.Children[key[matchlen]]才可以正常運(yùn)行,0x16剛好指向了branch節(jié)點(diǎn)的第17個(gè)孩子。如果匹配的長(zhǎng)度是0,那么直接返回這個(gè)branch節(jié)點(diǎn),否則返回shortNode節(jié)點(diǎn)作為前綴節(jié)點(diǎn)。
如果節(jié)點(diǎn)類型是nil(一顆全新的Trie樹的節(jié)點(diǎn)就是nil的),這個(gè)時(shí)候整顆樹是空的,直接返回shortNode{key, value, t.newFlag()}, 這個(gè)時(shí)候整顆樹的跟就含有了一個(gè)shortNode節(jié)點(diǎn)。
如果當(dāng)前的節(jié)點(diǎn)是fullNode(也就是branch節(jié)點(diǎn)),那么直接往對(duì)應(yīng)的孩子節(jié)點(diǎn)調(diào)用insert方法,然后把對(duì)應(yīng)的孩子節(jié)點(diǎn)指向新生成的節(jié)點(diǎn)。
如果當(dāng)前節(jié)點(diǎn)是hashNode, hashNode的意思是當(dāng)前節(jié)點(diǎn)還沒有加載到內(nèi)存里面來,還是存放在數(shù)據(jù)庫(kù)里面,那么首先調(diào)用 t.resolveHash(n, prefix)來加載到內(nèi)存,然后對(duì)加載出來的節(jié)點(diǎn)調(diào)用insert方法來進(jìn)行插入。
接下來看如何遍歷Trie樹從Trie中獲取數(shù)據(jù),根據(jù)key獲取的value過程:
func (t *Trie) TryGet(key []byte) ([]byte, error) { key = keybytesToHex(key) value, newroot, didResolve, err := t.tryGet(t.root, key, 0) if err == nil && didResolve { t.root = newroot } return value, err } func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) { switch n := (origNode).(type) { case nil: // 空樹 return nil, nil, false, nil case valueNode: // 就是要查找的葉子節(jié)點(diǎn)數(shù)據(jù) return n, n, false, nil case *shortNode: if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) { // key在trie中不存在 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: // hashNodes時(shí)候需要去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 default: panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode)) } }
tryGet(origNode node, key []byte, pos int)方法提供三個(gè)參數(shù),起始的node,hash key,還有當(dāng)前hash匹配的位置,didResolve用來判斷trie樹是否發(fā)生變化,根據(jù)hashNode去db中獲取該node值,獲取到后,需要更新現(xiàn)有的trie,didResolve就會(huì)發(fā)生變化。
關(guān)于Trie的Update和Delete就不分析了,在trie包中還有其他的功能,我們來大略看下主要是干嘛的不做詳細(xì)解讀了:
databases.go trie數(shù)據(jù)結(jié)構(gòu)和磁盤數(shù)據(jù)庫(kù)之間的一個(gè)寫入層,方便trie中節(jié)點(diǎn)的插入刪除操作
iterator.go 遍歷Trie的鍵值迭代器
proof.go Trie樹的默克爾證明,Prove方法獲取指定Key的proof證明, proof證明是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有節(jié)點(diǎn)的hash值列表。 VerifyProof方法,接受一個(gè)roothash值和proof證明和key來驗(yàn)證key是否存在。
security_trie.go 加密了的trie實(shí)現(xiàn)
轉(zhuǎn)載請(qǐng)注明: 轉(zhuǎn)載自Ryan是菜鳥 | LNMP技術(shù)棧筆記
如果覺得本篇文章對(duì)您十分有益,何不 打賞一下
本文鏈接地址: 以太坊源碼分析--MPT 樹
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/24200.html
摘要:前言以太坊是一個(gè)巨大的狀態(tài)機(jī),在網(wǎng)絡(luò)中,每一個(gè)全節(jié)點(diǎn)都保存著以太坊狀態(tài)機(jī)的全部歷史,只要愿意,我們可以查詢到任何時(shí)刻的狀態(tài)黃皮書中,而賬戶狀態(tài)便是其中的狀態(tài),這部分功能由主要由代碼中的包提供基本概念賬戶地址在以太坊中,無論是外部賬戶還是合約 前言 以太坊是一個(gè)巨大的狀態(tài)機(jī),在網(wǎng)絡(luò)中,每一個(gè)全節(jié)點(diǎn)都保存著以太坊狀態(tài)機(jī)的全部歷史,只要愿意,我們可以查詢到任何時(shí)刻的狀態(tài)(黃皮書中World ...
摘要:是以太坊存儲(chǔ)數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu),它是由和結(jié)合的一種樹形結(jié)構(gòu),理解有助于我們更好的理解以太坊的數(shù)據(jù)存儲(chǔ)。所以就有了樹壓縮前綴樹,后面會(huì)介紹到,也被稱為,中文名稱默克爾樹,主要用于數(shù)據(jù)集較大時(shí)的文件校驗(yàn)。 ??MPT(Merkle Patricia Tries)是以太坊存儲(chǔ)數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu),它是由Merkle Tree和Patricia Tree結(jié)合的一種樹形結(jié)構(gòu),理解MPT有助于我們更...
摘要:加密經(jīng)濟(jì)網(wǎng)絡(luò)中的底層公鏈?zhǔn)潜缺忍貛鸥癖忍貛诺膬r(jià)值存儲(chǔ)平臺(tái)。這一點(diǎn)將會(huì)在經(jīng)濟(jì)模型設(shè)計(jì)中講到,敬請(qǐng)期待在技術(shù)實(shí)現(xiàn)上,我們也充分對(duì)比了比特幣模型和以太坊模型的優(yōu)劣,從中繼承了比特幣協(xié)議對(duì)狀態(tài)為核心的優(yōu)秀架構(gòu)。 Nervos 加密經(jīng)濟(jì)網(wǎng)絡(luò)中的底層公鏈 CKB 是比比特幣更像比特幣的價(jià)值存儲(chǔ)平臺(tái)。(這一點(diǎn)將會(huì)在經(jīng)濟(jì)模型設(shè)計(jì)中講到,敬請(qǐng)期待~)在技術(shù)實(shí)現(xiàn)上,我們也充分對(duì)比了比特幣 UTXO 模型...
摘要:引言給迷失在如何學(xué)習(xí)區(qū)塊鏈技術(shù)的同學(xué)一個(gè)指引,區(qū)塊鏈技術(shù)是隨比特幣誕生,因此要搞明白區(qū)塊鏈技術(shù),應(yīng)該先了解下比特幣。但區(qū)塊鏈技術(shù)不單應(yīng)用于比特幣,還有非常多的現(xiàn)實(shí)應(yīng)用場(chǎng)景,想做區(qū)塊鏈應(yīng)用開發(fā),可進(jìn)一步閱讀以太坊系列。 本文始發(fā)于深入淺出區(qū)塊鏈社區(qū), 原文:區(qū)塊鏈技術(shù)學(xué)習(xí)指引 原文已更新,請(qǐng)讀者前往原文閱讀 本章的文章越來越多,本文是一個(gè)索引帖,方便找到自己感興趣的文章,你也可以使用左側(cè)...
摘要:前言是以太坊封定義的一個(gè)接口,它的功能可以分為類驗(yàn)證區(qū)塊類,主要用在將區(qū)塊加入到區(qū)塊鏈前,對(duì)區(qū)塊進(jìn)行共識(shí)驗(yàn)證。輔助類生成以太坊共識(shí)相關(guān)的。被使用,是以太坊狀態(tài)管理服務(wù),當(dāng)報(bào)告數(shù)據(jù)的時(shí)候,需要獲取區(qū)塊的信息。 前言 engine是以太坊封定義的一個(gè)接口,它的功能可以分為3類: 驗(yàn)證區(qū)塊類,主要用在將區(qū)塊加入到區(qū)塊鏈前,對(duì)區(qū)塊進(jìn)行共識(shí)驗(yàn)證。 產(chǎn)生區(qū)塊類,主要用在挖礦時(shí)。 輔助類。 接下...
閱讀 1711·2021-11-11 10:58
閱讀 4184·2021-09-09 09:33
閱讀 1257·2021-08-18 10:23
閱讀 1548·2019-08-30 15:52
閱讀 1624·2019-08-30 11:06
閱讀 1867·2019-08-29 14:03
閱讀 1507·2019-08-26 14:06
閱讀 2943·2019-08-26 10:39