Preload state trie node #4737

matkt · 2022-11-25T09:34:35Z

Signed-off-by: Karim TAAM karim.t2am@gmail.com
Co-authored-by: Ameziane H ameziane.hamlat@consensys.net

PR description

The idea behind this PR is to preload asynchronously account nodes and storage nodes from the database during the transaction processing to use these nodes during the calculate root hash step.
We've created two caches, one for account nodes and one for storage nodes. The size of these caches is 100k for accounts and 200k for storage. We've tested other values but this configuration is the one that works better.
We also exporter cache metrics as Prometheus metrics to check cache efficiency.

We didn't see any impact on GC activity even on 4 GiB Heaps (-Xmx4g).

The results

We did our tests on different AWS EC instances, here're the results.

M6a.xlarge (4 vCPU, 16 GiB)
Block processing time is 34% better for median values and 41% better for 95th percentile.

M5.xlarge (4 vCPU, 16 GiB)
Block processing time is 28% better for median values and 95th percentile.

I3.2xlarge (8 vCPU, 61 GiB)
Block processing time is 21% better for median values and 95th percentile.

Cache Efficiency
We can see in the screenshots below that these two caches are very efficient (>99%) and increasing storage cache size more than 200k is not necessary.

Account cache size = 100k and Storage cache size = 200k

Account cache size = 100k and Storage cache size = 1 million

Fixed Issue(s)

Documentation

I thought about documentation and added the doc-change-required label to this PR if
updates are required.

Changelog

I thought about the changelog and included a changelog update if required.

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

…Prometheus. Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/BonsaiInMemoryWorldState.java

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/BonsaiLayeredWorldState.java

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/BonsaiWorldStateArchive.java

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/BonsaiWorldStateUpdater.java

gezero · 2022-11-30T10:34:37Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/OptimizedMerkleTrieLoader.java

+  private final Cache<Bytes, Bytes> storageNodes;
+
+  public OptimizedMerkleTrieLoader(final ObservableMetricsSystem metricsSystem) {
+    accountsNodes = CacheBuilder.newBuilder().recordStats().maximumSize(ACCOUNT_CACHE_SIZE).build();


Please avoid running complicated logic in a constructor. Maybe extract it into a factory method.

gezero · 2022-11-30T10:40:32Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/OptimizedMerkleTrieLoader.java

+      final BonsaiWorldStateKeyValueStorage worldStateStorage,
+      final Hash worldStateRootHash,
+      final Address account) {
+    CompletableFuture.runAsync(


It feels to me weird that nobody handles the future when it is done. Maybe you can have the Optional that you were preloading to be a return value of the future and when the future completes, update your accountsNodes. That would also prevent the need of modifying a field in the middle of a function. Functions in functional programming should preferably not have side effects, so this might help.

Good point, the idea was to execute asynchronously as much work as possible to fill the cache. These completable futures doesn't return any result, but I totally agree that it should be more clean to control the execution of the completable future.
This is a first version, and this can be improved in a future PR. The control of completable futures' executions will introduce a lot of changes that can be done in the future PR. We can for example stop all the futures when we start reading from the cache, this is not done in this current PR.

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/OptimizedMerkleTrieLoader.java

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/CachedMerkleTrieLoader.java

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

ahamlat

LGTM

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

gezero

LGTM

garyschulte · 2022-12-01T19:53:26Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/BonsaiPersistedWorldState.java

@@ -116,7 +126,10 @@ protected Hash calculateRootHash(
    // next walk the account trie
    final StoredMerklePatriciaTrie<Bytes, Bytes> accountTrie =
        new StoredMerklePatriciaTrie<>(
-            this::getAccountStateTrieNode,
+            (location, hash) ->


it appears that Optional<Bytes> getAccountStateTrieNode() is no longer used anywhere

garyschulte · 2022-12-01T19:56:37Z

besu/src/main/java/org/hyperledger/besu/controller/BesuControllerBuilder.java

@@ -300,8 +301,10 @@ public BesuController build() {
            reorgLoggingThreshold,
            dataDirectory.toString());

+    final CachedMerkleTrieLoader cachedMerkleTrieLoader = new CachedMerkleTrieLoader(metricsSystem);


this feels like a worldstateArchive concern that is leaking. Non-blocking, but I think we could benefit from a builder and/or pass metricsSystem instead

garyschulte · 2022-12-01T20:11:59Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/BonsaiWorldStateUpdater.java

 import org.apache.tuweni.bytes.Bytes;
 import org.apache.tuweni.bytes.Bytes32;
 import org.apache.tuweni.units.bigints.UInt256;
+import org.jetbrains.annotations.NotNull;


I think only intellij is going to use this annotation. Findbugs uses NonNull and would probably be a better choice.

garyschulte · 2022-12-01T20:33:00Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/CachedMerkleTrieLoader.java

+  }
+
+  @VisibleForTesting
+  public void cacheAccountNodes(


can be default visibility rather than public

garyschulte · 2022-12-01T20:33:25Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/CachedMerkleTrieLoader.java

+    }
+  }
+
+  public void preLoadStorageSlot(


can be default viz

garyschulte

Non-blocking feedback, can be addressed in a subsequent PR.

garyschulte · 2022-12-01T20:38:32Z

ethereum/core/src/test-support/java/org/hyperledger/besu/ethereum/core/TrieGenerator.java


 import org.apache.tuweni.bytes.Bytes;
 import org.apache.tuweni.bytes.Bytes32;
 import org.apache.tuweni.units.bigints.UInt256;

 public class TrieGenerator {

-  public static MerklePatriciaTrie<Bytes32, Bytes> generateTrie(
+  public static MerklePatriciaTrie<Bytes, Bytes> generateTrie(


why the change from Bytes32 to Bytes for the MPTs ?

because the keys are not necessarily only hashes. storage flat db has longer keys

garyschulte · 2022-12-01T20:55:24Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/CachedMerkleTrieLoader.java

+              worldStateRootHash,
+              Function.identity(),
+              Function.identity());
+      accountTrie.get(Hash.hash(account));


we should comment that loading the cache is a side effect of calling get

garyschulte · 2022-12-01T20:58:17Z

ethereum/core/src/main/java/org/hyperledger/besu/ethereum/bonsai/CachedMerkleTrieLoader.java

+      final StoredMerklePatriciaTrie<Bytes, Bytes> accountTrie =
+          new StoredMerklePatriciaTrie<>(
+              (location, hash) -> {
+                Optional<Bytes> node = worldStateStorage.getAccountStateTrieNode(location, hash);


any reason we are doing the ifPresent check inside the MPT rather than before we create it, like we do in cacheStorageNodes ?

Not sure I understand the comment. The if is different in this case unless I didn't understand what you mean 😄

matkt · 2022-12-01T21:11:48Z

I merge and I will fix in a next PR. Thank you for your reviews

The idea behind this commit is to preload asynchronously account nodes and storage nodes from the database during the transaction processing to use these nodes during the calculate root hash step. We've created two caches, one for account nodes and one for storage nodes. The size of these caches is 100k for accounts and 200k for storage. We've tested other values but this configuration is the one that works better. We also use exporter cache metrics as Prometheus metrics to check cache efficiency. Signed-off-by: Karim TAAM <karim.t2am@gmail.com> Co-authored-by: Ameziane H <ameziane.hamlat@consensys.net> Signed-off-by: Gabriel-Trintinalia <gabriel.trintinalia@consensys.net>

The idea behind this commit is to preload asynchronously account nodes and storage nodes from the database during the transaction processing to use these nodes during the calculate root hash step. We've created two caches, one for account nodes and one for storage nodes. The size of these caches is 100k for accounts and 200k for storage. We've tested other values but this configuration is the one that works better. We also use exporter cache metrics as Prometheus metrics to check cache efficiency. Signed-off-by: Karim TAAM <karim.t2am@gmail.com> Co-authored-by: Ameziane H <ameziane.hamlat@consensys.net> Signed-off-by: Sally MacFarlane <macfarla.github@gmail.com>

The idea behind this commit is to preload asynchronously account nodes and storage nodes from the database during the transaction processing to use these nodes during the calculate root hash step. We've created two caches, one for account nodes and one for storage nodes. The size of these caches is 100k for accounts and 200k for storage. We've tested other values but this configuration is the one that works better. We also use exporter cache metrics as Prometheus metrics to check cache efficiency. Signed-off-by: Karim TAAM <karim.t2am@gmail.com> Co-authored-by: Ameziane H <ameziane.hamlat@consensys.net>

matkt added 3 commits November 24, 2022 15:15

add cache for account state trie

a187d77

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

update code

12ce007

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

fix build

00e2333

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

matkt changed the title ~~[POW-PERF] Preload state trie node~~ [POC-PERF] Preload state trie node Nov 25, 2022

matkt changed the title ~~[POC-PERF] Preload state trie node~~ Preload state trie node Nov 25, 2022

matkt changed the title ~~Preload state trie node~~ [WORK IN PROGRESS] Preload state trie node Nov 25, 2022

matkt force-pushed the feature/cached-state-node branch from 3766ea2 to bed1a9a Compare November 25, 2022 13:26

remove logs

461ce45

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

matkt force-pushed the feature/cached-state-node branch from bed1a9a to 461ce45 Compare November 25, 2022 13:36

matkt added 2 commits November 25, 2022 22:47

more robust implementation

b72dbf0

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

update cache implementation

8d9b80c

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

matkt force-pushed the feature/cached-state-node branch from e97d142 to 8d9b80c Compare November 26, 2022 11:21

ahamlat and others added 8 commits November 27, 2022 20:11

Add Account and Storage nodes cache metrics. Export those metrics to …

06b0404

…Prometheus. Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

Add Account and Storage nodes cache metrics. Export those metrics to …

60ed397

…Prometheus. Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

Fix unit tests errors.

c69c1b3

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

Enable cache statistics on account nodes

bc8a0a3

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

Modify storage cache size to compare cache metrics

8aac45e

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

optimize fallback for flat database

588ce0f

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

Undo storage cache size modification to the previous value

d51924e

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

Merge branch 'main' into feature/cached-state-node

11ee78c

gezero reviewed Nov 30, 2022

View reviewed changes

matkt force-pushed the feature/cached-state-node branch 2 times, most recently from 0315742 to 1562550 Compare November 30, 2022 16:18

github-advanced-security bot found potential problems Nov 30, 2022

View reviewed changes

matkt force-pushed the feature/cached-state-node branch 2 times, most recently from 3b97e76 to 24b47be Compare November 30, 2022 16:52

fix review

24a792c

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

matkt force-pushed the feature/cached-state-node branch from 24b47be to 24a792c Compare November 30, 2022 16:53

add missing class

eb01df4

Signed-off-by: Karim TAAM <karim.t2am@gmail.com>

matkt force-pushed the feature/cached-state-node branch from a953258 to eb01df4 Compare November 30, 2022 16:56

Merge branch 'main' into feature/cached-state-node

c7d09e3

matkt marked this pull request as ready for review November 30, 2022 20:50

matkt changed the title ~~[WORK IN PROGRESS] Preload state trie node~~ Preload state trie node Nov 30, 2022

matkt requested review from garyschulte, gezero and ahamlat December 1, 2022 09:12

ahamlat approved these changes Dec 1, 2022

View reviewed changes

matkt and others added 2 commits December 1, 2022 15:30

Merge branch 'main' into feature/cached-state-node

a544ec5

Add changelog

1a11130

Signed-off-by: Ameziane H <ameziane.hamlat@consensys.net>

gezero reviewed Dec 1, 2022

View reviewed changes

matkt added the TeamChupa GH issues worked on by Chupacabara Team label Dec 1, 2022

garyschulte reviewed Dec 1, 2022

View reviewed changes

garyschulte approved these changes Dec 1, 2022

View reviewed changes

matkt merged commit fae615f into hyperledger:main Dec 1, 2022

non-fungible-nelson mentioned this pull request Jan 26, 2023

Blocked threads after more than a month of uninterrupted uptime #4904

Closed

matkt deleted the feature/cached-state-node branch August 17, 2023 07:27

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Preload state trie node #4737

Preload state trie node #4737

matkt commented Nov 25, 2022 •

edited

gezero Nov 30, 2022

gezero Nov 30, 2022

ahamlat Nov 30, 2022

ahamlat left a comment

gezero left a comment

garyschulte Dec 1, 2022

garyschulte Dec 1, 2022

garyschulte Dec 1, 2022

garyschulte Dec 1, 2022

garyschulte Dec 1, 2022

garyschulte left a comment

garyschulte Dec 1, 2022

matkt Dec 1, 2022

garyschulte Dec 1, 2022

garyschulte Dec 1, 2022

matkt Dec 1, 2022

matkt commented Dec 1, 2022

Preload state trie node #4737

Preload state trie node #4737

Conversation

matkt commented Nov 25, 2022 • edited

PR description

The results

Fixed Issue(s)

Documentation

Changelog

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ahamlat left a comment

Choose a reason for hiding this comment

gezero left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

garyschulte left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

matkt commented Dec 1, 2022

matkt commented Nov 25, 2022 •

edited