Parallelize Execution

[tac0turtle]

Starting a discussion on parallelization of execution.

The Cosmos-SDK is synchronous in most to all cases. While this simplifies implementation details, there are areas that could be parallelized to increase throughput.

The first idea that comes to mind is to split bank accounts into denomination then account address. This would lend itself to one account sending multiple transfers of different denominations that could update state at the same time.

Much of the performance improvements to be had, are currently not here. Tendermint could introduce DeliverBatchTX or DeliverBlock instead of delivering each transaction individually. Also, we can't forget about IAVL and the performance increases that could be made there.

[alexanderbez]

Great use of the new discussions feature and thanks for whipping this up to get the ball rolling! As we all know, ABCI and mempool changes to Tendermint and thus the Cosmos SDK are coming right around the corner.

Specifically, DeliverBatchTX will allow us to parallelize some things, most notably signature verification in the ante handler. However, message execution might be a bit tricky and we need to think carefully about that.

We need to make sure that write operations to the underlying merkle-ized tree are not order-dependent (I don't think they are with IAVL?). Once we can safely make this assumption, we should ensure any changes we make to message handlers are done generically enough such that they still make sense and are easy to understand even if they're not executed in parallel.

[alexanderbez]

/cc'ing people here for signaling @sunnya97 @ValarDragon @cwgoes @aaronc

[hxrts]

also cc'ing @ethanfrey

[ethanfrey]

We need to make sure that write operations to the underlying merkle-ized tree are not order-dependent (I don't think they are with IAVL?).

I raised this with Jae back in 2017. The iavl hash is dependent on insert order. There is no way to change that with a btree like algorithm. The only efficient merklized data structure i know of is a Trie, as in Ethereum. That hash is stable wrt insert order. However, it doesn't support range queries unless you store the keys unhashed, allowing arbitrary depth. And the proofs are notably bigger.

If this is important, I would look at Eth 2 Sparse Merkle Trie to start.

[hxrts]

linking for visibility #7100 ++ ref ethereum/consensus-specs#1472

[robert-zaremba]

There is no way to change that with a btree like algorithm

Patricia Merke tree is a BTree. SMT is a BTree as well.

[ValarDragon]

Patricia Trees are tries, which are not BTrees. SMT's are also not BTrees. There is no rebalancing in either of those algorithms.

[robert-zaremba]

ah, the definition of a btree in my head didn't have a self-balancing property: generalization of a binary search tree (allowing for nodes with more than two children).

[aaronc]

Does this mean that lazy ledger's smt is thus a valid option for this? Would there we a reason we would favor the lazy ledger approach vs eth2?

[ethanfrey]

I think pre-processing of the tx shell could be parallelized somehow, but note that the sig verifier does modify the state for that account, and you need to ensure that the txs ante handing is sequential for the same account (this could be done with a bit of careful logic).

Following that is fee collection, which always increases the same account balance (fee collector) and I see no way of parallelizing that without a major architecture change.

[ethanfrey]

That said, I think supporting some level of optimistic parallel execution would be useful, it just must be done very carefully to work at all, and by some people with deep db knowledge to be bulletproof

[robert-zaremba]

One way to approach Parallel Execution is to use something like Solana Sealevel. In a nutshell:

• group transactions in a way, that there is no pair of transaction (tx1,tx2) such that group(tx1) =/= group(tx2) AND tx1 dependencies don't interfere with tx2 dependencies.
• execute all groups in parallel
• execute transactions in each group sequentially

[robert-zaremba]

Following @aaronc idea about KV references, I would like to propose and API for simple grouping.

Observation1:

Message object doesn't know about it's dependencies

Observation2:

Message handler usually knows about it's dependencies

Idea

1. We update MsgService to have 2 methods for every message: Exec and Plan
2. The *Exec(ctx, msg) method will execute the message in the same way we are doing now (sequential message processing).
3. *Plan(ctx, msg) method will return all dependencies for processing a given message. If it can't determine a finite and sane list of it's dependencies it must return special constant: UNKNOWN_DEPS.
4. deliverTx will first run Plan, then it will group transactions in a way described above (first bullet)
5. we execute all groups in parallel and we execute transactions in each group sequentially.
6. transactions with UNKNOWN_DEPS will run sequentially after all other groups are executed. (variation - they can run first).

API proposals.

Let's take x/bank MsgSend as an example. Instead of defining 1 RPC for Send, we will need two:

1. Send(goCtx context.Context, msg *types.MsgSend) (*types.MsgSendResponse, error)
2. SendPlan(goCtx context.Context, msg *types.MsgSend) (Dependencies, error)

Option 2:
We have one handler, but it will return two functions:

Send(goCtx context.Context, msg *types.MsgSend) (ExecFn, PlanFn, error)

[aaronc]

I think this is generally not a bad idea. It would be useful to analyze which tx's have statically known deps. For the ones that don't, there may be a subset where the known deps can be accurately computed from the begin block state... though maybe not good to rely on this because there could be nasty edge cases.

[robert-zaremba]

One more thing to analyze is a case when someone calls a msg from another message... but we can call Plan recursively.

[ValarDragon]

I'm not clear on the goal of this issue.

1. Discuss some ad-hoc parallelization addition to computationally intense parts of the SDK (e.g. parallelize signature verification, batch DB updates across txs, end blocks, hardcode some modules that can run in parallel, such as bank and governance). This class of things ought to be a non-breaking change to the state machine.
2. Open a discussion on parallel execution models, and compile/convert all existing modules into such a model. Then, we ought to be discussing / understanding changes required to adopt an existing parallel tx execution models, e.g. SeaLevel, TxVM, etc, and pick one. Then rewrite all module logic to be in a compliant form. (It could be there are simple tricks, e.g. including the txs entire memtrace SeaLevel style at tx creation, and do a pass in begin block to group things)
3. Understand how to make tx interactions less stateful / less synchronous, and leave parallel execution / scheduling abstract / up to the end app developer.

I personally view (1) as the best thing to focus on for now, and within it parallelizing auth and bank. I don't think we best know how to abstract in the style of (3) yet. (Or at least I definitely don't)

(Also its v cool that threads got added to github issues)

[tac0turtle]

Oh, this isn't an issue actually. Its github's new discussion feature, a sort of forum. How I have approached is to put ideas that will have larger conversations here and then when actionable items arise we create issues for them.

The goal of opening the thread is to begin the conversation of how to improve performance with parallelization.

1 could be opened as an issue if there is agreement as it's not large change. The goal of the discussion is oriented more towards 2. By no means are there actionable nor preferred approaches,

[ValarDragon]

Oh my bad, didn't realize this was a discussion! This makes sense then

[robert-zaremba]

BTW: Cardano has a great research on how to parallelize smart-contract execution.
https://eprint.iacr.org/2020/299

In a nutshell, they extend the UTXO model to provide more smart-contract capabilities.

[hxrts]

First step should be a profiling strategy and set of core benchmarks.

[ethanfrey]

I agree with some hard coded fixes for auth/fees so the ante handlers can prep the next tx when the previous is running.

Ideally any changes we can make that are opt in and non invasive are nice to add to the current sdk.

For a design like Solana, one should build a new sdk. It is a radically different design and you cannot force everyone using the current sdk to change to such architecture.

[ValarDragon]

I share the same view

[robert-zaremba]

Why do you think it should be a new SDK? It's a state-machine compatible change (doesn't change the state). It's a huge work on the SDK, but it's hard to say for me, how much breaking changes are on the SDK user side.

[sunnya97]

I agree with this. Building parallelization natively at the SDK will be a massively difficult undertaking.

But instead, app developers should be able to choose to intelligently run things in parallel for their modules when they want to.

In this model, if a "VM module" like CosmWasm wants to implement parallelism, it can, without needing the SDK itself doing it. An example of this happening currently, is in the AiB Dex Demo, during the end blocker, the execution engine for each orderbook pair runs in parallel in separate goroutines.

What the SDK should do however, is give the app developers the tools and ability to more easily do this.

The lowest hanging fruit is having a DeliverBlock ABCI method. This will allow app developers to add parallelism during tx execution, not just the endblocker.

Another thing that could be beneficial is having more nested merkle trees. Currently the normal way of doing things is everything is in a single global IAVL tree. But making it easier to create "sub-merkletrees" that can be written to in parallel, and then their merkle roots are in larger merkle tree (I believe multistore already does this, but would be nice to have it better documented and idk if its currently multi-layer nestable). I know @ValarDragon probably has more thoughts on this.

[alexanderbez]

Another thing that could be beneficial is having more nested merkle trees. Currently the normal way of doing things is everything is in a single global IAVL tree. But making it easier to create "sub-merkletrees" that can be written to in parallel, and then their merkle roots are in larger merkle tree (I believe multistore already does this, but would be nice to have it better documented and idk if its currently multi-layer nestable

Separate logical stores is actually how the SDK is currently designed and I'm actually not in favor of it (see #6370). I believe there should be a single logical store with proper namespaces per module/domain. If you have a single logical store that is insertion-order independent, than you still get the ability to execute writes in parallel.

[ValarDragon]

Not sure what you mean by logical store.

Theres many important use cases for different sub-tree types. E.g. if you want to incorporate a zcash-style shielded pool, or proof friendly sub-trees in general, this is a necessity. As another example, efficient key iterability could instead be a property thats pushed to a leaf node in a generalized merkle tree format. (Use a different, key iterable efficient, data store for how you compute that nodes leafhash)

In general, for efficiency, you want to be able to use a different database / vector commitments for datasets of different access structure types, and efficiency needs. Not supporting this would block both many key efficiency optimizations, and privacy applications.

I agree with you on making an insertion order independent data structure as the default (e.g. an SMT variant)

[alexanderbez]

Logical store = iavl, datastrucures, etc..
physical store = postgres, leveldb, etc..

In general, for efficiency, you want to be able to use a different database / vector commitments for datasets of different access structure types, and efficiency needs. Not supporting this would block both many key efficiency optimizations, and privacy applications.

Why? Can you elaborate on the last part? Provide examples or references. In typical applications, you have a single logical store separated by some domain namespace. This also allows you to perform atomic operations. Not to say this can't be done with multiple logical stores, but it's more difficult.

[ethanfrey]

I have seen this atomicity issue and it is a big headache.
(Agreeing with you 💯 bez)

[ValarDragon]

Different data stores differ in provability and efficiency aspects. One key capability that is blocked is not allowing for "infrequent witness updates", which is needed for many of the stateless blockchains. (e.g. ETH 2: https://ethresear.ch/t/double-batched-merkle-log-accumulator/571) Essentially you want a separate data store for history and state, with almost everything being thrown to history. And you design the history tree s.t. one part of its witness will only update once, and then not update afterwards.

You get a large host of different data structure needs as you go to start certain sub-trees in state to be efficiently provable in a SNARK. E.g. you want to use algebraic hash functions, you want simpler trees, you want to change the tree arity, you want to do hash prefixing for each layer differently to what is done now etc. These are real things, that one has to change to incorporate a zcash shielded pool.

If you want cryptographic proofs of append only-ness to a lite client, you then need a separate tree type. (Can't get an efficient append onlyness proof, and proofs of non-inclusion) This is something that is wanted in key transparency applications for instance. (E.g. the WAVE operation log https://people.eecs.berkeley.edu/~m.andersen/files/wave.pdf)

There are other components as well, like suppose I wanted a faster-in-software, worse-in-lite-client tree. Then I may increase the tree's radix, to have fewer lookup rounds and be more simd friendly.

Then there are separately questions around using alternate vector commitments than merkle trees for improved batch lite client performance.

[alexanderbez]

That honestly sounds super complicated, but I understand the use-cases. It sounds like you want two logical store types -- one for historical purposes and one for the current view of state, which I think makes sense and can be done while maintaining atomicity, ACID compliance and a clean API.

However, I do not recommend having different logical store types per unique sub-tree. That just sounds very messy and complicated.

[jackzampolin]

This is kinda what react does with the shadow DOM right?

[aaronc]

A lot of really interesting ideas here. I just want to first try to get a sense of how important it is for us to start designing this now. Are we seeing current scaling issues? Or are we looking at this from a competitive lens and seeing performant solutions like Solana and wanting to stay in the race?

If addressing this sooner rather than later is important to secure Cosmos's relevance in the space, I'm happy to start considering approaches. I wonder if someone like @zmanian or @jackzampolin might be able to comment on this a bit...

I have tended agree with @ValarDragon in that the first thing we should focus on is likely parallelizing computationally intensive parts of the SDK rather than a full on parallel execution model. Although, on the other hand, getting a parallel execution model like Sealevel right is going to require lots of design and planning, and if we're going in that direction we should consider it while we're thinking about other things like #7539 and #7459.

So anyway, please let me know your thoughts regarding priority and roadmap.

[aaronc]

Regarding a parallel execution model, I want to share my current thoughts on how a module API for that might look. There are obviously lots of things we'd need to think of in terms of the storage layer and scheduler so that everything gets run deterministically, but I think it's useful to start by thinking about what would be needed at the module level.

Synchronous R/W Scheduling

Methods would communicate a list of store keys or key prefixes which they would need synchronous R/W access to before the method is invoked. This list of keys would be the input for a batching algorithm that parallelizes methods based on non-overlapping synchronous store access. Let’s say we add a method RequestStoreAccess that does this.

So the RequestStoreAccess method for x/bank MsgSend would return all the balance/address pairs for the coins and to and from addresses. The scheduler would use this to figure out which thread this message gets executed on and ensure that no other thread could concurrently access these regions of the store. Now, there are some difficulties if we need to make inter-module queries to say the x/auth module regarding locked coins - but we could consider either of the options below for that - i.e. read the locked coins as of the last block or make an async inter-module call.

To make the dev UX a bit better, the actual MsgSend handler might be fed mutable references to all the store keys previously requested in RequestStoreAccess. I’d need to think a bit more about how this would work to make it nice…

We could add support for parallelism incrementally in that if a method doesn’t conform to the parallel API, it would get run sequentially in a separate phase from parallelizable methods.

Full Read Access for Last Block's State

Parallelizable methods would have full read access to their own state and any other module's state at the end of the last block. In some cases, this is good enough and we could define it as the expected behavior. For instance, I think it's fine to say for something like voting, that the weight is based on the stake as of the end of the last block.

Two phase inter-module calls

In this model, calls to other modules would need to be initialized in RequestStoreAccess like calls to the module's own state and then processed later so there is no resource contention.

[hxrts]

AgoricVM scheduler discussion is worth taking a quick look: Agoric/agoric-sdk#23

[robert-zaremba]

Adding parallelism on the micro level (like in the example of sending coins) would probably be more costly then doing it sequentially. Parallelism has a big runtime cost. @aaronc - probably in your PoC, each message handler will need to return a channel which will inform the deliverTx executor to run multiple messages at once, and be able to limit the total number of parallel message invocations.

In general, I think a simple realization of grouping would be the most efficient.

[aaronc]

Adding parallelism on the micro level (like in the example of sending coins) would probably be more costly then doing it sequentially. Parallelism has a big runtime cost.

That's my thought as well. There's not too much to gain by parallelizing the internals of sending coins vs parallelizing all of the send transactions in a block. A single transaction that sends multiple coins is probably exceedingly rare and I can't think of any client application I've ever seen that supports that sort of thing.

@aaronc - probably in your PoC, each message handler will need to return a channel which will inform the deliverTx executor to run multiple messages at once, and be able to limit the total number of parallel message invocations.

I'm not quite sure what you mean by returning a channel. My PoC is intended to provide the input to a grouping algorithm not parallelize things within a message handler.

In general, I think a simple realization of grouping would be the most efficient.

Agreed.

[robert-zaremba]

I'm not quite sure what you mean by returning a channel.

When we call the executor:

ctx.Exec(func(ctx ExecContext) error { 

I assume that the scheduler will call the closure. To do things in parallel - the scheduler will need to run few closures at once. So:

1. It needs to keep track of continuations which are still running
2. or manage workers which will call that continuation

In the first case, the closure will need to inform the scheduler when it's finished. In the second case a worker will take care about it. In both cases using channels is the easiest way to communicate that with a scheduler.

[aaronc]

Oh no, the idea is that those functions will be queued to run sequentially. Parallelism is only between transactions. I updated the docs to my example to make that clear. I don't think it's feasible to parallelize those Exec calls within a transaction and also make it atomic.

[robert-zaremba]

We can't parallelize transactions without any a-priori knowledge. One of the basic problems is state versioning.
If tx1 and tx2 are happening in parallel, then

• we have a race condition on the state
• if one tx fails (down the line when processing messages), then we have a problem with rollback.

I think the only reasonable way to solve it is to only allow message processing which doesn't share any resource (state).

[aaronc]

Yeah that's more or less what I'm proposing above. Let me know what you think. (I'm updating the description now to fix the inter-module call part.)

[iramiller]

We can't parallelize transactions without any a-priori knowledge

I would like to see something on the order of an execution plan attached to a new type of parallelized transaction type. When these transactions are submitted another step similar to CheckTx could run that performs the DeliverTx operation and tracks a list of all keys from KVStore Reads/Writes in a discarded state snapshot.

This extra work would be done on submission and would be parallelized. With a list of read/write state store keys processing could be performed to select non-overlapping transactions in a greedy fashion from the mempool.

• If during the evaluation step greater than [threshold number of keys] are read/write the process could abort and dispatch the TX without an execution plan.
• Techniques such as bloomfilters over the keys could possibly apply as a method for estimating that transaction is not overlapping existing operations within the block.
• Regular TX could be added to a block first followed by parallel TX that are able determine they will not overlap. Perhaps demote a parallelize TX to a regular one if it has skipped a block so it takes a normal place in line with the second attempt.
• If a DeliverTx violated its execution plan by touching keys not in the read/write set then it could be either rejected or demoted to run as a regular transaction

[mconcat]

STM might be a helpful concept here. In the delivertx, all the transactions are executed in parallel on cache wrapped state with an optimistic assumption that they will not cause a race condition. After all of the message execution is done, we commit the state change sequentially, and if any of the execution turns out to had access to a state that has previously accessed, that state change does not get committed(=rolled back). Those "failed" messages then get batched and run again(maybe sequentially).

[aaronc]

Interesting. That wouldn't change the current execution model at all really... I wonder how efficient that would be vs an explicit synchronization approach like I suggested. I guess that depends on the average overlap of transactions in blocks... which we could maybe evaluate statistically somehow for the hub, though maybe not generally...

[robert-zaremba]

I was thinking about STM in blockchain runtime a while ago. I think it won't work, because an attacker can always prepare 2 transactions which will depend and will cause an optimistic assumption to fail. So we always need to start with grouping transactions and have some a priori knowledge.

[ethanfrey]

An attcker could always design a set of transactions that cannot be parallelized and must be executed sequentially.

In fact, 50 tx signed from the same account with incrementing sequence numbers and all sending coins to different output is very hard to parallelize. Both the ante-handler (sequence check) would have to be sequential, as well as the state updates (decrementing the sender's coin balance).

Parallel approaches can only provide speed-ups in average case, never in worst-case.

Or maybe you can show me a design that uses CRDTs to allow full commutability of the state updates

[aaronc]

In fact, 50 tx signed from the same account with incrementing sequence numbers and all sending coins to different output is very hard to parallelize. Both the ante-handler (sequence check) would have to be sequential, as well as the state updates (decrementing the sender's coin balance).

I actually think that would be hard to pull off because there's a good chance they'll arrive out of order and fail in the ante handler and never reach state updates. Or is the order they'll show up in a block predictable? If that's a concern there could be a simple provision to not include tx's from the same signers in the same block, or to fail them early if they do. And even if you could pull that off in a single block, it becomes more and more costly to sustain such an attack...

I think the general point that @robert-zaremba is making relates to an attack being cheaper to pull off with STM because you only need two non-parallel transactions. I think that makes sense.

[jackzampolin]

Well if the best case before impl STM is non-parallel txs then STM would still be an improvement in the average case and could be a good optimization regardless of ease/feasibility of attacks on it.

[aaronc]

The more I think about this, the more I think that framework level parallelism is something we should be designing towards even if we don't fully implement it for a while.

Parallelism in begin and end blockers would be great of course and can be done now in specific cases if needed, but I think there is only so much parallelism we can introduce within individual transactions. For instance, when sending coins sure someone could send multiple coins in a single transaction and we could parallelize that state access, but I imagine this will be very rare. Users generally send one coin at a time not a bundle.

So I think the big gains are executing multiple transactions in parallel which requires some grouping algorithm based on a priori knowledge of state access (a synchronization or preparation phase).

It would be good to understand where the parallel execution model I described will not be feasible, but in most of the cases I've examined it seems feasible and likely desirable. And we can still at a "synchronized" phase for tx's that can't be parallelized yet or even at all.

Adding this level of parallelism at the framework level would likely be both a big competitive edge for Cosmos chains and the Hub and provide the community with greater future assurance of scalability that doesn't depend on sharding as CPUs already have 64 cores on a chip and will continue to evolve.

From my perspective, I would like to move our 1.0 roadmap and ADR 033 (#7459) to include this.

[jackzampolin]

Also seems like with SMTs being a hopefully soon type feature seems like some of the hard ground work is already laid. This would be amazing!