Batch-optimization

[ScottyPoi]

Continues work on optimizations described by @holgerd77 in #3293

trie.batch()

1. Externalized to trie/batch.ts

trie.batch() will now call an externalized function called batch, imported from batch.ts. batch.ts also contains helper functions and modified trie operations related to batch.

2. Return updated stack

trie._updateNode and trie._createInitialNode have been modified to return the stack of nodes after updating. This will be utilized in the batch optimization.

3. orderBatch()

orderBatch() is a helper function which sorts a batch of trie operations by key nibbles. This sorting will allow for an optimized approach to updating trie nodes.

4. custom _put and _del functions

modified version of trie operations _put and _del were added to batch.ts. These functions accept additional path parameters, and return the modified stack of nodes following a trie update. This will allow for caching of recently visited nodes within the batch operation, which reduces the amount of trie walking (findPath() calls) necessary for updates.

5. batchPut

batchPut is a modified version of trie.put which acts as an intermediary between the batch method, and the modified _put and _del methods.

6. batch

Refactored batch method keeps the same parameters. No batch calls need to be modified elsewhere in the codebase.

stackPathCache: Map<string, TrieNode>

• _batch will keep track of traversed node paths and nodes. with each trie update, the updated path from the new root to the new leaf will be stored in a map by their path nibbles.
• This cached path will contain most or all of the nodes involved in the following update, due to the presorted keys.
• Rather than walk the trie again from each new root, this cache allows the next update to use the partial path already traversed the previous update.
• _batch will call batchPut for each op with the added parameter of the cached stack nodes, and the nibble remainder of the next key.

Benchmarks:

This refactored batch process completes 33% faster than before!

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 95.45455% with 4 lines in your changes are missing coverage. Please review.

Project coverage is 86.91%. Comparing base (48e6a30) to head (e075991).

Additional details and impacted files

Flag	Coverage Δ
block	88.43% <ø> (ø)
blockchain	91.61% <ø> (ø)
client	84.85% <ø> (ø)
common	98.43% <ø> (ø)
devp2p	82.12% <ø> (ø)
ethash	∅ <ø> (∅)
evm	74.10% <ø> (ø)
genesis	99.98% <ø> (ø)
rlp	∅ <ø> (?)
statemanager	77.08% <ø> (ø)
trie	89.42% <95.45%> (+0.09%)	:arrow_up:
tx	95.08% <ø> (ø)
util	89.34% <ø> (ø)
vm	79.90% <ø> (ø)
wallet	88.35% <ø> (ø)

Flags with carried forward coverage won't be shown. Click here to find out more.

[holgerd77]

That sounds really promising, also this looks super-clean already! 🤩 Is this already ready for review or are you doing continued work here?

[ScottyPoi]

Not quite yet! I wrote more tests that try it with different trie settings, and not all are passing yet. close!

[ScottyPoi]

OK ready for review! :+1:

[holgerd77]

This already looks a lot better respectively „more compact“, let me know when this should get another look! 🙂

[ScottyPoi]

@holgerd77

• reduced this down to +88 / -17 lines of code (not including the test)
• Removed new file created in PR

If this feels small enough to you, then it is ready for another review

[holgerd77]

Rebased this via UI

[ScottyPoi]

I think any user with a bit of dyslexia will get dizzy trying to decipher skipKeyTransformOrOptsDict?: boolean | BatchOpts
:rofl:

[ScottyPoi]

Thinking out loud here about the cache memory overload issue

• The cache can be thought of like an in-memory slice of a Trie database

• Difference is that Trie Nodes are stored by their current path in the trie at each iteration

  • *instead of by node_hash like trie.db
  • `"[ ]" is the key for the root node
  • Children of the root node will have a key-path like: "[ a ]"
  • Nodes further down will have key-path like: "[ a, 0, b, c, e]"

• With each batch operation, updated nodes are insterted via their path in the updated trie.

  • "[ ]" will point to the new rootnode, etc.

• To me this means that the maximum size of the cache is equal to the total number of updated nodes in the final trie

• Nodes are individually only about 500 bytes. So i think that even a large batch would not build a promlematically large memory cache.

[ScottyPoi]

if there is first a put for a key and then a delete for the same key this is obviously different then having this the other way around

The way we currently do the sorting, multiple batch ops for the same key would remain the original order relative to each other. So the order of multiple put or del for the same key should not be affected, and the end result should be the same

[holgerd77]

I think any user with a bit of dyslexia will get dizzy trying to decipher skipKeyTransformOrOptsDict?: boolean | BatchOpts 🤣

This would for sure only be temporary until the next breaking releases (maybe autumn or so?), then we would remove the skipKeyTransform part. 🙂

This would have the advantage though that people then could already "go" into the new API and would not need to adjust again along breaking releases, so I think I would still be a fan of taking this version. 🙂

(we can also pick these things up on the call)

[holgerd77]

Thinking out loud here about the cache memory overload issue

* The cache can be thought of like an in-memory slice of a `Trie` database

* Difference is that Trie Nodes are stored by their current **path** in the trie at each iteration
  
  * *instead of by **node_hash** like `trie.db`
  * `"[ ]" is the key for the root node
  * Children of the root node will have a key-path like: `"[ a ]"`
  * Nodes further down will have key-path like: `"[ a, 0, b, c, e]"`

* With each batch operation, updated nodes are insterted via their path in the updated trie.
  
  * `"[ ]"` will point to the new rootnode, etc.

* To me this means that the maximum size of the cache is equal to the total number of updated nodes **in the final trie**

* Nodes are individually only about `500 bytes`.  So i think that even a large batch would not build a promlematically large memory cache.

I am unsure TBH. But might very well be that it's a non-issue. I would be ok with trying and eventually - if things doesn't hold for users in certain scenarios - push another release with an additional flag.

[holgerd77]

if there is first a put for a key and then a delete for the same key this is obviously different then having this the other way around

The way we currently do the sorting, multiple batch ops for the same key would remain the original order relative to each other. So the order of multiple put or del for the same key should not be affected, and the end result should be the same

Haven't looked at the sorting algorithm yet, but my imagination goes short atm to imagine a sorting algorithm that is so non-deterministic (in some sense, maybe "dynamic" might be a better word) that not one of the cases A, B and B, A is sorted in a way that behavior is changed. 🤔

Not sure, maybe I'll have some additional time for a closer look at the algorithm later on.

[holgerd77]

Can this then please get an update, or otherwise please let me know where we still need to clarify things! 🙂

So, I would assume we now do:

1. Use async batch(ops: BatchDBOp[], skipKeyTransformOrOptsDict?: boolean | BatchOpts) as signature
2. Add a new BatchOpts type
3. Keep the cache without an extra option
4. Add sortOperations: boolean to BatchOpts defaulting to false

Let me know if there is further need to discuss certain points, eventually you can independently also push the things which are unambiguous.