polaris
polaris copied to clipboard
berachain
Problem: overhead of nested cache stores
If i understand correctly, the current implementation suffer from overhead of nested cache store a lot, similar to when we have observed before in ethermint.
Specifically, each message call in EVM contract will results in a Snapshot() call in statedb, which wraps a new layer of cache store, this could result in a deeply nested cache stores, which have a big performance penalty in both query and commit, which I've described here: https://github.com/cosmos/cosmos-sdk/issues/14377.
There's a solution to this issue here: https://github.com/cosmos/cosmos-sdk/pull/14444, which eliminate overhead of nesting completely, I guess now we have more motivations to push forward the cache store refactoring.
@yihuang we ran benchmarks with multiple implementations and found this to be the fastest: https://github.com/berachain/polaris/blob/main/x/evm/plugins/state/plugin_benchmark_test.go
If you play around with the parameters, you can see the increasing the contract call depth only results in linear increase in runtime, not exponential. Specifically the variable is numCalls https://github.com/berachain/polaris/blob/c32182f7bc42ae110773db8ca7bcc08c1a65f5e6/x/evm/plugins/state/plugin_benchmark_test.go#L34
Part of this though has to do with the fact that we use our own custom Multistore: https://github.com/berachain/polaris/blob/main/store/snapmulti/store.go
Regardless of such I agree with everything in the PRs, CacheKV v2 is definitely the move, as the nesting is not ideal.
I guess the worst case scenario is when you have a deep cache store stack, do a bunch of writes at the top, then finalize. You can give that scenario a try, as long as the performance is acceptable even when attacker exploit the worst case scenario within gas limit, it should be fine.
you can see the increasing the contract call depth only results in linear increase in runtime, not exponential
iteration on nested cache store is worse but fortunately we don't do that in EVM.
query overhead is linear to the nesting depth, but I guess the cost of finalize will increase faster than linear, because of the key sortings done in the Write of each layer.
Yeah I suppose in that embodimeant you would effectively end up with O(n^2) writes.
yeah the key sorting is bad.
For a while we had a custom CacheKv store without the sorting. It's a twice second thing to throw it back in, but we just removed it for the time being, since we're doing it at the sdk level.
In the interim it would be a rather trivial change to our SnapMulti to throw on a custom non sorting cachekv store instead of regular cachekv when Len(journal) >=1.
yeah, that's possible.probably based on some copy-on-write data structures, tidwall/btree is the only one I know that's convenient to use, although we don't need the sorting capability.
theres really no great solution other than a full CacheKV rewrite IMO
yeah, but fortunately it's not too complicated provided with existing copy-on-write data structures.
I think you do need a sorted data structure to handle the iteration in sdk native functionalities, and the iteration performance on nested cache store do matters.
The that is correct, the benefit to the implementation we have right now, is that we only wrap the cachekv's individually. So the wrap only happens if we write to it [EDIT] or read from it at any previous call in the current transaction.
If we called 10 contacts in a row, but we never had ether transfers we would never wrap the cache.
The that is correct, the benefit to the implementation we have right now, is that we only wrap the cachekv's individually. So the wrap only happens if we write to it during that specific contract call.
If we called 10 contacts in a row, but we never had ether transfers we would never wrap the cache.
I thought each message call will call Snapshot() which will add a layer of wrapping immediately, and the wrapping depth will only increase during the whole tx execution until commit at the end, no?
The design of SnapMulti makes it so the Snapshot will only do a cache wrap of KVstores if they were changed and is doing so on a store by store basis.
If you were to just call snapshot() over and over again with no changes to the underlying store, you'd effectively end up doing no-ops.
In practice this typically means you're only wrapping the "evm" store, for subsequent contract calls and then the bank and account store once at the beginning.
Ignoring precompiles for a second, it means that SnapMulti is only every wrapping. Account on contract deploys, bank on balance transfer and state on storage writes.
Opposed to caching every kvstore in the root multi every time as it does with the standard impl.
On the precompile front we are going to benchmark the overhead for adding each additional store and then charge users gas based in that, our implementation supports having dynamic gas in precompiles. (Though we are just cleaning up a bug).
https://github.com/berachain/polaris/blob/main/x/evm/plugins/precompile/plugin.go
The that is correct, the benefit to the implementation we have right now, is that we only wrap the cachekv's individually. So the wrap only happens if we write to it during that specific contract call. If we called 10 contacts in a row, but we never had ether transfers we would never wrap the cache.
I thought each message call will call Snapshot() which will add a layer of wrapping immediately, and the wrapping depth will only increase during the whole tx execution until commit at the end, no?
Correct, currently each call to Snapshot() will wrap every individual cachekv store if it has modified state in ANY of the execution before the current call. Generally the number of cachewraps grows linearly with the number of contract calls.
For example, if in the first 10 calls the "acc" (account) store is never modified, it will not have been cache-wrapped. The latest state of "acc" store is synchronized with the root store (where root is the state before the transaction). If "acc" store is modified on call 11 but never again, every subsequent call will cache wrap the "acc" store.
The design of SnapMulti makes it so the Snapshot will only do a cache wrap of KVstores if they were changed and is doing so on a store by store basis.
If you were to just call snapshot() over and over again with no changes to the underlying store, you'd effectively end up doing no-ops.
In practice this typically means you're only wrapping the "evm" store, for subsequent contract calls and then the bank and account store once at the beginning.
Ignoring precompiles for a second, it means that SnapMulti is only every wrapping. Account on contract deploys, bank on balance transfer and state on storage writes.
Correcting minor nuances here:
"The design of SnapMulti makes it so the Snapshot will only do a cache wrap of KVstores if they were changed at any time during the transaction before the current snapshot and is doing so on a store by store basis."
In practice, we are most often still wrapping all of ("evm", "acc", "bank") stores on every snapshot because they had all probably been written to/read from at some call early in the transaction.
As @itsdevbear mentioned, the SnapMulti store approach was our most performant implementation to maintaining a journal stack of cachekvstores (or more specifically mapMultiStores). We used this benchmark test to measure performance of different approaches: https://github.com/berachain/polaris/blob/main/x/evm/plugins/state/plugin_benchmark_test.go
We played around with the parameters and found that even with num_calls extremely high (~10000), our SnapMulti store is the most performant.
@yihuang to optimize writes on a Finalize, there is more caching we can do.
For example, we could make a "DuoCacheKV" store that can read from and write to 2 synchronized cachekv stores. The indivudal kv store in use during the transaction would be this DuoCacheKV, where one of the cachekvs is the head of the journal stack and the other one is the "source of truth" store.
On Snapshot, the "source of truth" store remains the same but the other store in the DuoCacheKV would be a cache wrap of the head of the journal stack. On RevertToSnapshot, all changes from the revertTo cachekv store would have to be applied to the "source of truth store". On Finalize, only the "source of truth" store must be written to its parent. The journal can be cleared.
Essentially, this approach saves a current state with all previous changes included. Iteration on the DuoCacheKV should also be faster as there is only one layer of cache wrap on the "source of truth" store.