aboutsummaryrefslogtreecommitdiffstats
path: root/trie/trie.go
diff options
context:
space:
mode:
authorPéter Szilágyi <peterke@gmail.com>2018-02-06 00:40:32 +0800
committerFelix Lange <fjl@users.noreply.github.com>2018-02-06 00:40:32 +0800
commit55599ee95d4151a2502465e0afc7c47bd1acba77 (patch)
tree4165e73ae852db4f025a5ed57f0bc499e87cb8b9 /trie/trie.go
parent59336283c0dbeb1d0a74ff7a8b717b2b3bb0cf40 (diff)
downloadgo-tangerine-55599ee95d4151a2502465e0afc7c47bd1acba77.tar
go-tangerine-55599ee95d4151a2502465e0afc7c47bd1acba77.tar.gz
go-tangerine-55599ee95d4151a2502465e0afc7c47bd1acba77.tar.bz2
go-tangerine-55599ee95d4151a2502465e0afc7c47bd1acba77.tar.lz
go-tangerine-55599ee95d4151a2502465e0afc7c47bd1acba77.tar.xz
go-tangerine-55599ee95d4151a2502465e0afc7c47bd1acba77.tar.zst
go-tangerine-55599ee95d4151a2502465e0afc7c47bd1acba77.zip
core, trie: intermediate mempool between trie and database (#15857)
This commit reduces database I/O by not writing every state trie to disk.
Diffstat (limited to 'trie/trie.go')
-rw-r--r--trie/trie.go90
1 files changed, 31 insertions, 59 deletions
diff --git a/trie/trie.go b/trie/trie.go
index 8fe98d835..e37a1ae10 100644
--- a/trie/trie.go
+++ b/trie/trie.go
@@ -22,16 +22,17 @@ import (
"fmt"
"github.com/ethereum/go-ethereum/common"
- "github.com/ethereum/go-ethereum/crypto/sha3"
+ "github.com/ethereum/go-ethereum/crypto"
"github.com/ethereum/go-ethereum/log"
"github.com/rcrowley/go-metrics"
)
var (
- // This is the known root hash of an empty trie.
+ // emptyRoot is the known root hash of an empty trie.
emptyRoot = common.HexToHash("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421")
- // This is the known hash of an empty state trie entry.
- emptyState common.Hash
+
+ // emptyState is the known hash of an empty state trie entry.
+ emptyState = crypto.Keccak256Hash(nil)
)
var (
@@ -53,29 +54,10 @@ func CacheUnloads() int64 {
return cacheUnloadCounter.Count()
}
-func init() {
- sha3.NewKeccak256().Sum(emptyState[:0])
-}
-
-// Database must be implemented by backing stores for the trie.
-type Database interface {
- DatabaseReader
- DatabaseWriter
-}
-
-// DatabaseReader wraps the Get method of a backing store for the trie.
-type DatabaseReader interface {
- Get(key []byte) (value []byte, err error)
- Has(key []byte) (bool, error)
-}
-
-// DatabaseWriter wraps the Put method of a backing store for the trie.
-type DatabaseWriter interface {
- // Put stores the mapping key->value in the database.
- // Implementations must not hold onto the value bytes, the trie
- // will reuse the slice across calls to Put.
- Put(key, value []byte) error
-}
+// LeafCallback is a callback type invoked when a trie operation reaches a leaf
+// node. It's used by state sync and commit to allow handling external references
+// between account and storage tries.
+type LeafCallback func(leaf []byte, parent common.Hash) error
// Trie is a Merkle Patricia Trie.
// The zero value is an empty trie with no database.
@@ -83,8 +65,8 @@ type DatabaseWriter interface {
//
// Trie is not safe for concurrent use.
type Trie struct {
+ db *Database
root node
- db Database
originalRoot common.Hash
// Cache generation values.
@@ -111,12 +93,15 @@ func (t *Trie) newFlag() nodeFlag {
// trie is initially empty and does not require a database. Otherwise,
// New will panic if db is nil and returns a MissingNodeError if root does
// not exist in the database. Accessing the trie loads nodes from db on demand.
-func New(root common.Hash, db Database) (*Trie, error) {
- trie := &Trie{db: db, originalRoot: root}
+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 {
- if db == nil {
- panic("trie.New: cannot use existing root without a database")
- }
rootnode, err := trie.resolveHash(root[:], nil)
if err != nil {
return nil, err
@@ -447,12 +432,13 @@ func (t *Trie) resolve(n node, prefix []byte) (node, error) {
func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
cacheMissCounter.Inc(1)
- enc, err := t.db.Get(n)
+ hash := common.BytesToHash(n)
+
+ enc, err := t.db.Node(hash)
if err != nil || enc == nil {
- return nil, &MissingNodeError{NodeHash: common.BytesToHash(n), Path: prefix}
+ return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
}
- dec := mustDecodeNode(n, enc, t.cachegen)
- return dec, nil
+ return mustDecodeNode(n, enc, t.cachegen), nil
}
// Root returns the root hash of the trie.
@@ -462,32 +448,18 @@ func (t *Trie) Root() []byte { return t.Hash().Bytes() }
// Hash returns the root hash of the trie. It does not write to the
// database and can be used even if the trie doesn't have one.
func (t *Trie) Hash() common.Hash {
- hash, cached, _ := t.hashRoot(nil)
+ hash, cached, _ := t.hashRoot(nil, nil)
t.root = cached
return common.BytesToHash(hash.(hashNode))
}
-// Commit writes all nodes to the trie's database.
-// Nodes are stored with their sha3 hash as the key.
-//
-// Committing flushes nodes from memory.
-// Subsequent Get calls will load nodes from the database.
-func (t *Trie) Commit() (root common.Hash, err error) {
+// Commit writes all nodes to the trie's memory database, tracking the internal
+// and external (for account tries) references.
+func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error) {
if t.db == nil {
- panic("Commit called on trie with nil database")
+ panic("commit called on trie with nil database")
}
- return t.CommitTo(t.db)
-}
-
-// CommitTo writes all nodes to the given database.
-// Nodes are stored with their sha3 hash as the key.
-//
-// Committing flushes nodes from memory. Subsequent Get calls will
-// load nodes from the trie's database. Calling code must ensure that
-// the changes made to db are written back to the trie's attached
-// database before using the trie.
-func (t *Trie) CommitTo(db DatabaseWriter) (root common.Hash, err error) {
- hash, cached, err := t.hashRoot(db)
+ hash, cached, err := t.hashRoot(t.db, onleaf)
if err != nil {
return common.Hash{}, err
}
@@ -496,11 +468,11 @@ func (t *Trie) CommitTo(db DatabaseWriter) (root common.Hash, err error) {
return common.BytesToHash(hash.(hashNode)), nil
}
-func (t *Trie) hashRoot(db DatabaseWriter) (node, node, error) {
+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)
+ h := newHasher(t.cachegen, t.cachelimit, onleaf)
defer returnHasherToPool(h)
return h.hash(t.root, db, true)
}