core, core/state, trie: enterprise hand-tuned multi-level caching

1 files changed, 150 insertions, 87 deletions

diff --git a/trie/trie.go b/trie/trie.go
index cc5dcf2a6..a530e7b2a 100644
--- a/trie/trie.go
+++ b/trie/trie.go
@@ -129,7 +129,7 @@ func (t *Trie) TryGet(key []byte) ([]byte, error) {
 			tn = n.Val
 			pos += len(n.Key)
 		case fullNode:
-			tn = n[key[pos]]
+			tn = n.Children[key[pos]]
 			pos++
 		case nil:
 			return nil, nil
@@ -169,13 +169,13 @@ func (t *Trie) Update(key, value []byte) {
 func (t *Trie) TryUpdate(key, value []byte) error {
 	k := compactHexDecode(key)
 	if len(value) != 0 {
-		n, err := t.insert(t.root, nil, k, valueNode(value))
+		_, n, err := t.insert(t.root, nil, k, valueNode(value))
 		if err != nil {
 			return err
 		}
 		t.root = n
 	} else {
-		n, err := t.delete(t.root, nil, k)
+		_, n, err := t.delete(t.root, nil, k)
 		if err != nil {
 			return err
 		}
@@ -184,9 +184,12 @@ func (t *Trie) TryUpdate(key, value []byte) error {
 	return nil
 }
 
-func (t *Trie) insert(n node, prefix, key []byte, value node) (node, error) {
+func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
 	if len(key) == 0 {
-		return value, nil
+		if v, ok := n.(valueNode); ok {
+			return !bytes.Equal(v, value.(valueNode)), value, nil
+		}
+		return true, value, nil
 	}
 	switch n := n.(type) {
 	case shortNode:
@@ -194,53 +197,63 @@ func (t *Trie) insert(n node, prefix, key []byte, value node) (node, error) {
 		// If the whole key matches, keep this short node as is
 		// and only update the value.
 		if matchlen == len(n.Key) {
-			nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
+			dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
 			if err != nil {
-				return nil, err
+				return false, nil, err
+			}
+			if !dirty {
+				return false, n, nil
 			}
-			return shortNode{n.Key, nn}, nil
+			return true, shortNode{n.Key, nn, nil, true}, nil
 		}
 		// Otherwise branch out at the index where they differ.
-		var branch fullNode
+		branch := fullNode{dirty: true}
 		var err error
-		branch[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
+		_, 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 nil, err
+			return false, nil, err
 		}
-		branch[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
+		_, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
 		if err != nil {
-			return nil, err
+			return false, nil, err
 		}
 		// Replace this shortNode with the branch if it occurs at index 0.
 		if matchlen == 0 {
-			return branch, nil
+			return true, branch, nil
 		}
 		// Otherwise, replace it with a short node leading up to the branch.
-		return shortNode{key[:matchlen], branch}, nil
+		return true, shortNode{key[:matchlen], branch, nil, true}, nil
 
 	case fullNode:
-		nn, err := t.insert(n[key[0]], append(prefix, key[0]), key[1:], value)
+		dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
 		if err != nil {
-			return nil, err
+			return false, nil, err
 		}
-		n[key[0]] = nn
-		return n, nil
+		if !dirty {
+			return false, n, nil
+		}
+		n.Children[key[0]], n.hash, n.dirty = nn, nil, true
+		return true, n, nil
 
 	case nil:
-		return shortNode{key, value}, nil
+		return true, shortNode{key, value, nil, true}, nil
 
 	case hashNode:
 		// We've hit a part of the trie that isn't loaded yet. Load
 		// the node and insert into it. This leaves all child nodes on
 		// the path to the value in the trie.
-		//
-		// TODO: track whether insertion changed the value and keep
-		// n as a hash node if it didn't.
 		rn, err := t.resolveHash(n, prefix, key)
 		if err != nil {
-			return nil, err
+			return false, nil, err
+		}
+		dirty, nn, err := t.insert(rn, prefix, key, value)
+		if err != nil {
+			return false, nil, err
 		}
-		return t.insert(rn, prefix, key, value)
+		if !dirty {
+			return false, rn, nil
+		}
+		return true, nn, nil
 
 	default:
 		panic(fmt.Sprintf("%T: invalid node: %v", n, n))
@@ -258,7 +271,7 @@ func (t *Trie) Delete(key []byte) {
 // If a node was not found in the database, a MissingNodeError is returned.
 func (t *Trie) TryDelete(key []byte) error {
 	k := compactHexDecode(key)
-	n, err := t.delete(t.root, nil, k)
+	_, n, err := t.delete(t.root, nil, k)
 	if err != nil {
 		return err
 	}
@@ -269,23 +282,26 @@ func (t *Trie) TryDelete(key []byte) error {
 // delete returns the new root of the trie with key deleted.
 // It reduces the trie to minimal form by simplifying
 // nodes on the way up after deleting recursively.
-func (t *Trie) delete(n node, prefix, key []byte) (node, error) {
+func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
 	switch n := n.(type) {
 	case shortNode:
 		matchlen := prefixLen(key, n.Key)
 		if matchlen < len(n.Key) {
-			return n, nil // don't replace n on mismatch
+			return false, n, nil // don't replace n on mismatch
 		}
 		if matchlen == len(key) {
-			return nil, nil // remove n entirely for whole matches
+			return true, nil, nil // remove n entirely for whole matches
 		}
 		// The key is longer than n.Key. Remove the remaining suffix
 		// from the subtrie. Child can never be nil here since the
 		// subtrie must contain at least two other values with keys
 		// longer than n.Key.
-		child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):])
+		dirty, child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):])
 		if err != nil {
-			return nil, err
+			return false, nil, err
+		}
+		if !dirty {
+			return false, n, nil
 		}
 		switch child := child.(type) {
 		case shortNode:
@@ -295,17 +311,21 @@ func (t *Trie) delete(n node, prefix, key []byte) (node, error) {
 			// always creates a new slice) instead of append to
 			// avoid modifying n.Key since it might be shared with
 			// other nodes.
-			return shortNode{concat(n.Key, child.Key...), child.Val}, nil
+			return true, shortNode{concat(n.Key, child.Key...), child.Val, nil, true}, nil
 		default:
-			return shortNode{n.Key, child}, nil
+			return true, shortNode{n.Key, child, nil, true}, nil
 		}
 
 	case fullNode:
-		nn, err := t.delete(n[key[0]], append(prefix, key[0]), key[1:])
+		dirty, nn, err := t.delete(n.Children[key[0]], append(prefix, key[0]), key[1:])
 		if err != nil {
-			return nil, err
+			return false, nil, err
 		}
-		n[key[0]] = nn
+		if !dirty {
+			return false, n, nil
+		}
+		n.Children[key[0]], n.hash, n.dirty = nn, nil, true
+
 		// Check how many non-nil entries are left after deleting and
 		// reduce the full node to a short node if only one entry is
 		// left. Since n must've contained at least two children
@@ -316,7 +336,7 @@ func (t *Trie) delete(n node, prefix, key []byte) (node, error) {
 		// value that is left in n or -2 if n contains at least two
 		// values.
 		pos := -1
-		for i, cld := range n {
+		for i, cld := range n.Children {
 			if cld != nil {
 				if pos == -1 {
 					pos = i
@@ -334,37 +354,41 @@ func (t *Trie) delete(n node, prefix, key []byte) (node, error) {
 				// shortNode{..., shortNode{...}}.  Since the entry
 				// might not be loaded yet, resolve it just for this
 				// check.
-				cnode, err := t.resolve(n[pos], prefix, []byte{byte(pos)})
+				cnode, err := t.resolve(n.Children[pos], prefix, []byte{byte(pos)})
 				if err != nil {
-					return nil, err
+					return false, nil, err
 				}
 				if cnode, ok := cnode.(shortNode); ok {
 					k := append([]byte{byte(pos)}, cnode.Key...)
-					return shortNode{k, cnode.Val}, nil
+					return true, shortNode{k, cnode.Val, nil, true}, nil
 				}
 			}
 			// Otherwise, n is replaced by a one-nibble short node
 			// containing the child.
-			return shortNode{[]byte{byte(pos)}, n[pos]}, nil
+			return true, shortNode{[]byte{byte(pos)}, n.Children[pos], nil, true}, nil
 		}
 		// n still contains at least two values and cannot be reduced.
-		return n, nil
+		return true, n, nil
 
 	case nil:
-		return nil, nil
+		return false, nil, nil
 
 	case hashNode:
 		// We've hit a part of the trie that isn't loaded yet. Load
 		// the node and delete from it. This leaves all child nodes on
 		// the path to the value in the trie.
-		//
-		// TODO: track whether deletion actually hit a key and keep
-		// n as a hash node if it didn't.
 		rn, err := t.resolveHash(n, prefix, key)
 		if err != nil {
-			return nil, err
+			return false, nil, err
 		}
-		return t.delete(rn, prefix, key)
+		dirty, nn, err := t.delete(rn, prefix, key)
+		if err != nil {
+			return false, nil, err
+		}
+		if !dirty {
+			return false, rn, nil
+		}
+		return true, nn, nil
 
 	default:
 		panic(fmt.Sprintf("%T: invalid node: %v (%v)", n, n, key))
@@ -413,8 +437,9 @@ 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 {
-	root, _ := t.hashRoot(nil)
-	return common.BytesToHash(root.(hashNode))
+	hash, cached, _ := t.hashRoot(nil)
+	t.root = cached
+	return common.BytesToHash(hash.(hashNode))
 }
 
 // Commit writes all nodes to the trie's database.
@@ -437,17 +462,17 @@ func (t *Trie) Commit() (root common.Hash, err error) {
 // 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) {
-	n, err := t.hashRoot(db)
+	hash, cached, err := t.hashRoot(db)
 	if err != nil {
 		return (common.Hash{}), err
 	}
-	t.root = n
-	return common.BytesToHash(n.(hashNode)), nil
+	t.root = cached
+	return common.BytesToHash(hash.(hashNode)), nil
 }
 
-func (t *Trie) hashRoot(db DatabaseWriter) (node, error) {
+func (t *Trie) hashRoot(db DatabaseWriter) (node, node, error) {
 	if t.root == nil {
-		return hashNode(emptyRoot.Bytes()), nil
+		return hashNode(emptyRoot.Bytes()), nil, nil
 	}
 	if t.hasher == nil {
 		t.hasher = newHasher()
@@ -464,51 +489,87 @@ func newHasher() *hasher {
 	return &hasher{tmp: new(bytes.Buffer), sha: sha3.NewKeccak256()}
 }
 
-func (h *hasher) hash(n node, db DatabaseWriter, force bool) (node, error) {
-	hashed, err := h.replaceChildren(n, db)
+// hash collapses a node down into a hash node, also returning a copy of the
+// original node initialzied with the computed hash to replace the original one.
+func (h *hasher) hash(n node, db DatabaseWriter, force bool) (node, node, error) {
+	// If we're not storing the node, just hashing, use avaialble cached data
+	if hash, dirty := n.cache(); hash != nil && (db == nil || !dirty) {
+		return hash, n, nil
+	}
+	// Trie not processed yet or needs storage, walk the children
+	collapsed, cached, err := h.hashChildren(n, db)
 	if err != nil {
-		return hashNode{}, err
+		return hashNode{}, n, err
 	}
-	if n, err = h.store(hashed, db, force); err != nil {
-		return hashNode{}, err
+	hashed, err := h.store(collapsed, db, force)
+	if err != nil {
+		return hashNode{}, n, err
 	}
-	return n, nil
+	// Cache the hash and RLP blob of the ndoe for later reuse
+	if hash, ok := hashed.(hashNode); ok && !force {
+		switch cached := cached.(type) {
+		case shortNode:
+			cached.hash = hash
+			if db != nil {
+				cached.dirty = false
+			}
+			return hashed, cached, nil
+		case fullNode:
+			cached.hash = hash
+			if db != nil {
+				cached.dirty = false
+			}
+			return hashed, cached, nil
+		}
+	}
+	return hashed, cached, nil
 }
 
-// hashChildren replaces child nodes of n with their hashes if the encoded
-// size of the child is larger than a hash.
-func (h *hasher) replaceChildren(n node, db DatabaseWriter) (node, error) {
+// hashChildren replaces the children of a node with their hashes if the encoded
+// size of the child is larger than a hash, returning the collapsed node as well
+// as a replacement for the original node with the child hashes cached in.
+func (h *hasher) hashChildren(original node, db DatabaseWriter) (node, node, error) {
 	var err error
-	switch n := n.(type) {
+
+	switch n := original.(type) {
 	case shortNode:
+		// Hash the short node's child, caching the newly hashed subtree
+		cached := n
+		cached.Key = common.CopyBytes(cached.Key)
+
 		n.Key = compactEncode(n.Key)
 		if _, ok := n.Val.(valueNode); !ok {
-			if n.Val, err = h.hash(n.Val, db, false); err != nil {
-				return n, err
+			if n.Val, cached.Val, err = h.hash(n.Val, db, false); err != nil {
+				return n, original, err
 			}
 		}
 		if n.Val == nil {
-			// Ensure that nil children are encoded as empty strings.
-			n.Val = valueNode(nil)
+			n.Val = valueNode(nil) // Ensure that nil children are encoded as empty strings.
 		}
-		return n, nil
+		return n, cached, nil
+
 	case fullNode:
+		// Hash the full node's children, caching the newly hashed subtrees
+		cached := fullNode{dirty: n.dirty}
+
 		for i := 0; i < 16; i++ {
-			if n[i] != nil {
-				if n[i], err = h.hash(n[i], db, false); err != nil {
-					return n, err
+			if n.Children[i] != nil {
+				if n.Children[i], cached.Children[i], err = h.hash(n.Children[i], db, false); err != nil {
+					return n, original, err
 				}
 			} else {
-				// Ensure that nil children are encoded as empty strings.
-				n[i] = valueNode(nil)
+				n.Children[i] = valueNode(nil) // Ensure that nil children are encoded as empty strings.
 			}
 		}
-		if n[16] == nil {
-			n[16] = valueNode(nil)
+		cached.Children[16] = n.Children[16]
+		if n.Children[16] == nil {
+			n.Children[16] = valueNode(nil)
 		}
-		return n, nil
+		return n, cached, nil
+
 	default:
-		return n, nil
+		// Value and hash nodes don't have children so they're left as were
+		return n, original, nil
 	}
 }
 
@@ -517,21 +578,23 @@ func (h *hasher) store(n node, db DatabaseWriter, force bool) (node, error) {
 	if _, isHash := n.(hashNode); n == nil || isHash {
 		return n, nil
 	}
+	// Generate the RLP encoding of the node
 	h.tmp.Reset()
 	if err := rlp.Encode(h.tmp, n); err != nil {
 		panic("encode error: " + err.Error())
 	}
 	if h.tmp.Len() < 32 && !force {
-		// Nodes smaller than 32 bytes are stored inside their parent.
-		return n, nil
+		return n, nil // Nodes smaller than 32 bytes are stored inside their parent
 	}
 	// Larger nodes are replaced by their hash and stored in the database.
-	h.sha.Reset()
-	h.sha.Write(h.tmp.Bytes())
-	key := hashNode(h.sha.Sum(nil))
+	hash, _ := n.cache()
+	if hash == nil {
+		h.sha.Reset()
+		h.sha.Write(h.tmp.Bytes())
+		hash = hashNode(h.sha.Sum(nil))
+	}
 	if db != nil {
-		err := db.Put(key, h.tmp.Bytes())
-		return key, err
+		return hash, db.Put(hash, h.tmp.Bytes())
 	}
-	return key, nil
+	return hash, nil
 }