2023-07-12 23:03:14 +00:00
|
|
|
# nimbus-eth1
|
2024-02-01 21:27:48 +00:00
|
|
|
# Copyright (c) 2023-2024 Status Research & Development GmbH
|
2023-07-12 23:03:14 +00:00
|
|
|
# Licensed under either of
|
|
|
|
|
# * Apache License, version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or
|
|
|
|
|
# http://www.apache.org/licenses/LICENSE-2.0)
|
|
|
|
|
# * MIT license ([LICENSE-MIT](LICENSE-MIT) or
|
|
|
|
|
# http://opensource.org/licenses/MIT)
|
|
|
|
|
# at your option. This file may not be copied, modified, or distributed
|
|
|
|
|
# except according to those terms.
|
|
|
|
|
|
|
|
|
|
## Aristo DB -- Handy Helpers
|
|
|
|
|
## ==========================
|
|
|
|
|
##
|
|
|
|
|
{.push raises: [].}
|
|
|
|
|
|
|
|
|
|
import
|
2024-06-22 20:33:37 +00:00
|
|
|
eth/common,
|
2023-07-12 23:03:14 +00:00
|
|
|
results,
|
Store keys together with node data (#2849)
Currently, computed hash keys are stored in a separate column family
with respect to the MPT data they're generated from - this has several
disadvantages:
* A lot of space is wasted because the lookup key (`RootedVertexID`) is
repeated in both tables - this is 30% of the `AriKey` content!
* rocksdb must maintain in-memory bloom filters and LRU caches for said
keys, doubling its "minimal efficient cache size"
* An extra disk traversal must be made to check for existence of cached
hash key
* Doubles the amount of files on disk due to each column family being
its own set of files
Here, the two CFs are joined such that both key and data is stored in
`AriVtx`. This means:
* we save ~30% disk space on repeated lookup keys
* we save ~2gb of memory overhead that can be used to cache data instead
of indices
* we can skip storing hash keys for MPT leaf nodes - these are trivial
to compute and waste a lot of space - previously they had to present in
the `AriKey` CF to avoid having to look in two tables on the happy path.
* There is a small increase in write amplification because when a hash
value is updated for a branch node, we must write both key and branch
data - previously we would write only the key
* There's a small shift in CPU usage - instead of performing lookups in
the database, hashes for leaf nodes are (re)-computed on the fly
* We can return to slightly smaller on-disk SST files since there's
fewer of them, which should reduce disk traffic a bit
Internally, there are also other advantages:
* when clearing keys, we no longer have to store a zero hash in memory -
instead, we deduce staleness of the cached key from the presence of an
updated VertexRef - this saves ~1gb of mem overhead during import
* hash key cache becomes dedicated to branch keys since leaf keys are no
longer stored in memory, reducing churn
* key computation is a lot faster thanks to the skipped second disk
traversal - a key computation for mainnet can be completed in 11 hours
instead of ~2 days (!) thanks to better cache usage and less read
amplification - with additional improvements to the on-disk format, we
can probably get rid of the initial full traversal method of seeding the
key cache on first start after import
All in all, this PR reduces the size of a mainnet database from 160gb to
110gb and the peak memory footprint during import by ~1-2gb.
2024-11-20 08:56:27 +00:00
|
|
|
"."/[aristo_desc, aristo_compute]
|
2023-07-12 23:03:14 +00:00
|
|
|
|
|
|
|
|
# ------------------------------------------------------------------------------
|
|
|
|
|
# Public functions, converters
|
|
|
|
|
# ------------------------------------------------------------------------------
|
|
|
|
|
|
|
|
|
|
proc toNode*(
|
|
|
|
|
vtx: VertexRef; # Vertex to convert
|
No ext update (#2494)
* Imported/rebase from `no-ext`, PR #2485
Store extension nodes together with the branch
Extension nodes must be followed by a branch - as such, it makes sense
to store the two together both in the database and in memory:
* fewer reads, writes and updates to traverse the tree
* simpler logic for maintaining the node structure
* less space used, both memory and storage, because there are fewer
nodes overall
There is also a downside: hashes can no longer be cached for an
extension - instead, only the extension+branch hash can be cached - this
seems like a fine tradeoff since computing it should be fast.
TODO: fix commented code
* Fix merge functions and `toNode()`
* Update `merkleSignCommit()` prototype
why:
Result is always a 32bit hash
* Update short Merkle hash key generation
details:
Ethereum reference MPTs use Keccak hashes as node links if the size of
an RLP encoded node is at least 32 bytes. Otherwise, the RLP encoded
node value is used as a pseudo node link (rather than a hash.) This is
specified in the yellow paper, appendix D.
Different to the `Aristo` implementation, the reference MPT would not
store such a node on the key-value database. Rather the RLP encoded node value is stored instead of a node link in a parent node
is stored as a node link on the parent database.
Only for the root hash, the top level node is always referred to by the
hash.
* Fix/update `Extension` sections
why:
Were commented out after removal of a dedicated `Extension` type which
left the system disfunctional.
* Clean up unused error codes
* Update unit tests
* Update docu
---------
Co-authored-by: Jacek Sieka <jacek@status.im>
2024-07-16 19:47:59 +00:00
|
|
|
root: VertexID; # Sub-tree root the `vtx` belongs to
|
|
|
|
|
db: AristoDbRef; # Database
|
2023-07-12 23:03:14 +00:00
|
|
|
): Result[NodeRef,seq[VertexID]] =
|
|
|
|
|
## Convert argument the vertex `vtx` to a node type. Missing Merkle hash
|
|
|
|
|
## keys are searched for on the argument database `db`.
|
|
|
|
|
##
|
|
|
|
|
## On error, at least the vertex ID of the first missing Merkle hash key is
|
|
|
|
|
## returned. If the argument `stopEarly` is set `false`, all missing Merkle
|
|
|
|
|
## hash keys are returned.
|
|
|
|
|
##
|
2023-12-04 20:39:26 +00:00
|
|
|
## In the argument `beKeyOk` is set `false`, keys for node links are accepted
|
|
|
|
|
## only from the cache layer. This does not affect a link key for a payload
|
|
|
|
|
## storage root.
|
|
|
|
|
##
|
|
|
|
|
|
2023-07-12 23:03:14 +00:00
|
|
|
case vtx.vType:
|
|
|
|
|
of Leaf:
|
2024-09-13 16:55:17 +00:00
|
|
|
let node = NodeRef(vtx: vtx.dup())
|
2023-07-12 23:03:14 +00:00
|
|
|
# Need to resolve storage root for account leaf
|
|
|
|
|
if vtx.lData.pType == AccountData:
|
2024-08-07 13:28:01 +00:00
|
|
|
let stoID = vtx.lData.stoID
|
|
|
|
|
if stoID.isValid:
|
Store keys together with node data (#2849)
Currently, computed hash keys are stored in a separate column family
with respect to the MPT data they're generated from - this has several
disadvantages:
* A lot of space is wasted because the lookup key (`RootedVertexID`) is
repeated in both tables - this is 30% of the `AriKey` content!
* rocksdb must maintain in-memory bloom filters and LRU caches for said
keys, doubling its "minimal efficient cache size"
* An extra disk traversal must be made to check for existence of cached
hash key
* Doubles the amount of files on disk due to each column family being
its own set of files
Here, the two CFs are joined such that both key and data is stored in
`AriVtx`. This means:
* we save ~30% disk space on repeated lookup keys
* we save ~2gb of memory overhead that can be used to cache data instead
of indices
* we can skip storing hash keys for MPT leaf nodes - these are trivial
to compute and waste a lot of space - previously they had to present in
the `AriKey` CF to avoid having to look in two tables on the happy path.
* There is a small increase in write amplification because when a hash
value is updated for a branch node, we must write both key and branch
data - previously we would write only the key
* There's a small shift in CPU usage - instead of performing lookups in
the database, hashes for leaf nodes are (re)-computed on the fly
* We can return to slightly smaller on-disk SST files since there's
fewer of them, which should reduce disk traffic a bit
Internally, there are also other advantages:
* when clearing keys, we no longer have to store a zero hash in memory -
instead, we deduce staleness of the cached key from the presence of an
updated VertexRef - this saves ~1gb of mem overhead during import
* hash key cache becomes dedicated to branch keys since leaf keys are no
longer stored in memory, reducing churn
* key computation is a lot faster thanks to the skipped second disk
traversal - a key computation for mainnet can be completed in 11 hours
instead of ~2 days (!) thanks to better cache usage and less read
amplification - with additional improvements to the on-disk format, we
can probably get rid of the initial full traversal method of seeding the
key cache on first start after import
All in all, this PR reduces the size of a mainnet database from 160gb to
110gb and the peak memory footprint during import by ~1-2gb.
2024-11-20 08:56:27 +00:00
|
|
|
let key = db.computeKey((stoID.vid, stoID.vid)).valueOr:
|
2024-08-07 13:28:01 +00:00
|
|
|
return err(@[stoID.vid])
|
Store keys together with node data (#2849)
Currently, computed hash keys are stored in a separate column family
with respect to the MPT data they're generated from - this has several
disadvantages:
* A lot of space is wasted because the lookup key (`RootedVertexID`) is
repeated in both tables - this is 30% of the `AriKey` content!
* rocksdb must maintain in-memory bloom filters and LRU caches for said
keys, doubling its "minimal efficient cache size"
* An extra disk traversal must be made to check for existence of cached
hash key
* Doubles the amount of files on disk due to each column family being
its own set of files
Here, the two CFs are joined such that both key and data is stored in
`AriVtx`. This means:
* we save ~30% disk space on repeated lookup keys
* we save ~2gb of memory overhead that can be used to cache data instead
of indices
* we can skip storing hash keys for MPT leaf nodes - these are trivial
to compute and waste a lot of space - previously they had to present in
the `AriKey` CF to avoid having to look in two tables on the happy path.
* There is a small increase in write amplification because when a hash
value is updated for a branch node, we must write both key and branch
data - previously we would write only the key
* There's a small shift in CPU usage - instead of performing lookups in
the database, hashes for leaf nodes are (re)-computed on the fly
* We can return to slightly smaller on-disk SST files since there's
fewer of them, which should reduce disk traffic a bit
Internally, there are also other advantages:
* when clearing keys, we no longer have to store a zero hash in memory -
instead, we deduce staleness of the cached key from the presence of an
updated VertexRef - this saves ~1gb of mem overhead during import
* hash key cache becomes dedicated to branch keys since leaf keys are no
longer stored in memory, reducing churn
* key computation is a lot faster thanks to the skipped second disk
traversal - a key computation for mainnet can be completed in 11 hours
instead of ~2 days (!) thanks to better cache usage and less read
amplification - with additional improvements to the on-disk format, we
can probably get rid of the initial full traversal method of seeding the
key cache on first start after import
All in all, this PR reduces the size of a mainnet database from 160gb to
110gb and the peak memory footprint during import by ~1-2gb.
2024-11-20 08:56:27 +00:00
|
|
|
|
2023-07-12 23:03:14 +00:00
|
|
|
node.key[0] = key
|
|
|
|
|
return ok node
|
2023-11-08 12:18:32 +00:00
|
|
|
|
2023-07-12 23:03:14 +00:00
|
|
|
of Branch:
|
2024-09-13 16:55:17 +00:00
|
|
|
let node = NodeRef(vtx: vtx.dup())
|
Pre-allocate vids for branches (#2882)
Each branch node may have up to 16 sub-items - currently, these are
given VertexID based when they are first needed leading to a
mostly-random order of vertexid for each subitem.
Here, we pre-allocate all 16 vertex ids such that when a branch subitem
is filled, it already has a vertexid waiting for it. This brings several
important benefits:
* subitems are sorted and "close" in their id sequencing - this means
that when rocksdb stores them, they are likely to end up in the same
data block thus improving read efficiency
* because the ids are consequtive, we can store just the starting id and
a bitmap representing which subitems are in use - this reduces disk
space usage for branches allowing more of them fit into a single disk
read, further improving disk read and caching performance - disk usage
at block 18M is down from 84 to 78gb!
* the in-memory footprint of VertexRef reduced allowing more instances
to fit into caches and less memory to be used overall.
Because of the increased locality of reference, it turns out that we no
longer need to iterate over the entire database to efficiently generate
the hash key database because the normal computation is now faster -
this significantly benefits "live" chain processing as well where each
dirtied key must be accompanied by a read of all branch subitems next to
it - most of the performance benefit in this branch comes from this
locality-of-reference improvement.
On a sample resync, there's already ~20% improvement with later blocks
seeing increasing benefit (because the trie is deeper in later blocks
leading to more benefit from branch read perf improvements)
```
blocks: 18729664, baseline: 190h43m49s, contender: 153h59m0s
Time (total): -36h44m48s, -19.27%
```
Note: clients need to be resynced as the PR changes the on-disk format
R.I.P. little bloom filter - your life in the repo was short but
valuable
2024-12-04 10:42:04 +00:00
|
|
|
for n, subvid in vtx.pairs():
|
|
|
|
|
let key = db.computeKey((root, subvid)).valueOr:
|
|
|
|
|
return err(@[subvid])
|
|
|
|
|
node.key[n] = key
|
2023-07-12 23:03:14 +00:00
|
|
|
return ok node
|
2023-11-08 12:18:32 +00:00
|
|
|
|
2024-07-01 12:07:39 +00:00
|
|
|
iterator subVids*(vtx: VertexRef): VertexID =
|
2024-02-01 21:27:48 +00:00
|
|
|
## Returns the list of all sub-vertex IDs for the argument `vtx`.
|
2023-12-04 20:39:26 +00:00
|
|
|
case vtx.vType:
|
|
|
|
|
of Leaf:
|
2024-02-01 21:27:48 +00:00
|
|
|
if vtx.lData.pType == AccountData:
|
2024-08-07 13:28:01 +00:00
|
|
|
let stoID = vtx.lData.stoID
|
|
|
|
|
if stoID.isValid:
|
|
|
|
|
yield stoID.vid
|
2023-12-04 20:39:26 +00:00
|
|
|
of Branch:
|
Pre-allocate vids for branches (#2882)
Each branch node may have up to 16 sub-items - currently, these are
given VertexID based when they are first needed leading to a
mostly-random order of vertexid for each subitem.
Here, we pre-allocate all 16 vertex ids such that when a branch subitem
is filled, it already has a vertexid waiting for it. This brings several
important benefits:
* subitems are sorted and "close" in their id sequencing - this means
that when rocksdb stores them, they are likely to end up in the same
data block thus improving read efficiency
* because the ids are consequtive, we can store just the starting id and
a bitmap representing which subitems are in use - this reduces disk
space usage for branches allowing more of them fit into a single disk
read, further improving disk read and caching performance - disk usage
at block 18M is down from 84 to 78gb!
* the in-memory footprint of VertexRef reduced allowing more instances
to fit into caches and less memory to be used overall.
Because of the increased locality of reference, it turns out that we no
longer need to iterate over the entire database to efficiently generate
the hash key database because the normal computation is now faster -
this significantly benefits "live" chain processing as well where each
dirtied key must be accompanied by a read of all branch subitems next to
it - most of the performance benefit in this branch comes from this
locality-of-reference improvement.
On a sample resync, there's already ~20% improvement with later blocks
seeing increasing benefit (because the trie is deeper in later blocks
leading to more benefit from branch read perf improvements)
```
blocks: 18729664, baseline: 190h43m49s, contender: 153h59m0s
Time (total): -36h44m48s, -19.27%
```
Note: clients need to be resynced as the PR changes the on-disk format
R.I.P. little bloom filter - your life in the repo was short but
valuable
2024-12-04 10:42:04 +00:00
|
|
|
for _, subvid in vtx.pairs():
|
|
|
|
|
yield subvid
|
2023-12-04 20:39:26 +00:00
|
|
|
|
2024-07-29 20:15:17 +00:00
|
|
|
iterator subVidKeys*(node: NodeRef): (VertexID,HashKey) =
|
|
|
|
|
## Simolar to `subVids()` but for nodes
|
2024-09-13 16:55:17 +00:00
|
|
|
case node.vtx.vType:
|
2024-07-29 20:15:17 +00:00
|
|
|
of Leaf:
|
2024-09-13 16:55:17 +00:00
|
|
|
if node.vtx.lData.pType == AccountData:
|
|
|
|
|
let stoID = node.vtx.lData.stoID
|
2024-08-07 13:28:01 +00:00
|
|
|
if stoID.isValid:
|
|
|
|
|
yield (stoID.vid, node.key[0])
|
2024-07-29 20:15:17 +00:00
|
|
|
of Branch:
|
Pre-allocate vids for branches (#2882)
Each branch node may have up to 16 sub-items - currently, these are
given VertexID based when they are first needed leading to a
mostly-random order of vertexid for each subitem.
Here, we pre-allocate all 16 vertex ids such that when a branch subitem
is filled, it already has a vertexid waiting for it. This brings several
important benefits:
* subitems are sorted and "close" in their id sequencing - this means
that when rocksdb stores them, they are likely to end up in the same
data block thus improving read efficiency
* because the ids are consequtive, we can store just the starting id and
a bitmap representing which subitems are in use - this reduces disk
space usage for branches allowing more of them fit into a single disk
read, further improving disk read and caching performance - disk usage
at block 18M is down from 84 to 78gb!
* the in-memory footprint of VertexRef reduced allowing more instances
to fit into caches and less memory to be used overall.
Because of the increased locality of reference, it turns out that we no
longer need to iterate over the entire database to efficiently generate
the hash key database because the normal computation is now faster -
this significantly benefits "live" chain processing as well where each
dirtied key must be accompanied by a read of all branch subitems next to
it - most of the performance benefit in this branch comes from this
locality-of-reference improvement.
On a sample resync, there's already ~20% improvement with later blocks
seeing increasing benefit (because the trie is deeper in later blocks
leading to more benefit from branch read perf improvements)
```
blocks: 18729664, baseline: 190h43m49s, contender: 153h59m0s
Time (total): -36h44m48s, -19.27%
```
Note: clients need to be resynced as the PR changes the on-disk format
R.I.P. little bloom filter - your life in the repo was short but
valuable
2024-12-04 10:42:04 +00:00
|
|
|
for n, subvid in node.vtx.pairs():
|
|
|
|
|
yield (subvid,node.key[n])
|
2024-07-29 20:15:17 +00:00
|
|
|
|
2023-07-12 23:03:14 +00:00
|
|
|
# ------------------------------------------------------------------------------
|
|
|
|
|
# End
|
|
|
|
|
# ------------------------------------------------------------------------------
|