Implement the binary tree as specified in [eip-7864](https://eips.ethereum.org/EIPS/eip-7864).
This will gradually replace verkle trees in the codebase. This is only
running the tests and will not be executed in production, but will help
me rebase some of my work, so that it doesn't bitrot as much.
---------
Signed-off-by: Guillaume Ballet
Co-authored-by: Parithosh Jayanthi <parithosh.jayanthi@ethereum.org>
Co-authored-by: rjl493456442 <garyrong0905@gmail.com>
These changes made in the PR should be highlighted here
The trie tracer is split into two distinct structs: opTracer and prevalueTracer.
The former is specific to MPT, while the latter is generic and applicable to all
trie implementations.
The original values of dirty nodes are tracked in a NodeSet. This serves
as the foundation for both full archive node implementations and the state live
tracer.
This pull request removes the node copy operation to reduce memory
allocation. Key Changes as below:
**(a) Use `decodeNodeUnsafe` for decoding nodes retrieved from the trie
node reader**
In the current implementation of the MPT, once a trie node blob is
retrieved, it is passed to `decodeNode` for decoding. However,
`decodeNode` assumes the supplied byte slice might be mutated later, so
it performs a deep copy internally before parsing the node.
Given that the node reader is implemented by the path database and the
hash database, both of which guarantee the immutability of the returned
byte slice. By restricting the node reader interface to explicitly
guarantee that the returned byte slice will not be modified, we can
safely replace `decodeNode` with `decodeNodeUnsafe`. This eliminates the
need for a redundant byte copy during each node resolution.
**(b) Modify the trie in place**
In the current implementation of the MPT, a copy of a trie node is
created before any modifications are made. These modifications include:
- Node resolution: Converting the value from a hash to the actual node.
- Node hashing: Tagging the hash into its cache.
- Node commit: Replacing the children with its hash.
- Structural changes: For example, adding a new child to a fullNode or
replacing a child of a shortNode.
This mechanism ensures that modifications only affect the live tree,
leaving all previously created copies unaffected.
Unfortunately, this property leads to a huge memory allocation
requirement. For example, if we want to modify the fullNode for n times,
the node will be copied for n times.
In this pull request, all the trie modifications are made in place. In
order to make sure all previously created copies are unaffected, the
`Copy` function now will deep-copy all the live nodes rather than the
root node itself.
With this change, while the `Copy` function becomes more expensive, it's
totally acceptable as it's not a frequently used one. For the normal
trie operations (Get, GetNode, Hash, Commit, Insert, Delete), the node
copy is not required anymore.
This change makes the trie commit operation concurrent, if the number of changes exceed 100.
Co-authored-by: stevemilk <wangpeculiar@gmail.com>
Co-authored-by: Gary Rong <garyrong0905@gmail.com>
* all: implement path-based state scheme
* all: edits from review
* core/rawdb, trie/triedb/pathdb: review changes
* core, light, trie, eth, tests: reimplement pbss history
* core, trie/triedb/pathdb: track block number in state history
* trie/triedb/pathdb: add history documentation
* core, trie/triedb/pathdb: address comments from Peter's review
Important changes to list:
- Cache trie nodes by path in clean cache
- Remove root->id mappings when history is truncated
* trie/triedb/pathdb: fallback to disk if unexpect node in clean cache
* core/rawdb: fix tests
* trie/triedb/pathdb: rename metrics, change clean cache key
* trie/triedb: manage the clean cache inside of disk layer
* trie/triedb/pathdb: move journal function
* trie/triedb/path: fix tests
* trie/triedb/pathdb: fix journal
* trie/triedb/pathdb: fix history
* trie/triedb/pathdb: try to fix tests on windows
* core, trie: address comments
* trie/triedb/pathdb: fix test issues
---------
Co-authored-by: Felix Lange <fjl@twurst.com>
Co-authored-by: Martin Holst Swende <martin@swende.se>
* trie: add node type common package
In trie/types package, a few node wrappers are defined, which will be used
in both trie package, trie/snap package, etc. Therefore, a standalone common
package is created to put these stuffs.
* trie: rename trie/types to trie/trienode
This PR contains a small portion of the full pbss PR, namely
Remove the tracer from trie (and comitter), and instead using an accessList.
Related changes to the Nodeset.
---------
Co-authored-by: Gary Rong <garyrong0905@gmail.com>
This PR fixes an error in trie commit. If the trie.root is nil, it can be two possible scenarios:
- The trie was empty, and no change happens
- The trie was non-empty and all nodes are dropped
For the latter one, we should collect the deletions and apply them into database(e.g. in PBSS).
This PR includes minor updates to comments in trie/committer that reference insertion to the db, and adds an err != nil check for the return value of preimages.commit.
Trie tracer is an auxiliary tool to capture all deleted nodes
which can't be captured by trie.Committer. The deleted nodes
can be removed from the disk later.
This change speeds up trie hashing and all other activities that require
RLP encoding of trie nodes by approximately 20%. The speedup is achieved by
avoiding reflection overhead during node encoding.
The interface type trie.node now contains a method 'encode' that works with
rlp.EncoderBuffer. Management of EncoderBuffers is left to calling code.
trie.hasher, which is pooled to avoid allocations, now maintains an
EncoderBuffer. This means memory resources related to trie node encoding
are tied to the hasher pool.
Co-authored-by: Felix Lange <fjl@twurst.com>
* trie: update tests to check commit integrity
* trie: polish committer
* trie: fix typo
* trie: remove hasvalue notion
According to the benchmarks, type assertion between the pointer and
interface is extremely fast.
BenchmarkIntmethod-12 1000000000 1.91 ns/op
BenchmarkInterface-12 1000000000 2.13 ns/op
BenchmarkTypeSwitch-12 1000000000 1.81 ns/op
BenchmarkTypeAssertion-12 2000000000 1.78 ns/op
So the overhead for asserting whether the shortnode has "valuenode"
child is super tiny. No necessary to have another field.
* trie: linter nitpicks
Co-authored-by: Martin Holst Swende <martin@swende.se>
* core, crypto: various allocation savings regarding tx handling
* core: reduce allocs for gas price comparison
This change reduces the allocations needed for comparing different transactions to each other.
A call to `tx.GasPrice()` copies the gas price as it has to be safe against modifications and
also needs to be threadsafe. For comparing and ordering different transactions we don't need
these guarantees
* core: added tx.GasPriceIntCmp for comparison without allocation
adds a method to remove unneeded allocation in comparison to tx.gasPrice
* core/types: pool legacykeccak256 objects in rlpHash
rlpHash is by far the most used function in core that allocates a legacyKeccak256 object on each call.
Since it is so widely used it makes sense to add pooling here so we relieve the GC.
On my machine these changes result in > 100 MILLION less allocations and > 30 GB less allocated memory.
* reverted some changes
* reverted some changes
* trie: use crypto.KeccakState instead of replicating code
Co-authored-by: Martin Holst Swende <martin@swende.se>
