Allowing entries containing transactions with conflicting accounts in Banking stage

[talalim]

Problem

TPU has to make entries using only “disjoint” transactions because TVU makes some overly strict assumptions, i.e:

• That assumption seems to be that the TVU will break up a batch and execute individual transactions in parallel. In reality, this is not the case.
• Actually the TVU tries to execute multiple entries/batches in parallel using Rayon hence each transaction of a batch is executed sequentially in the scope of that batch
• This scheduling assumption severely limits any innovation in scheduling strategies

Proposed Solution

We've figured out that if we allow transactions with conflicting accounts in an entry for a flexible scheduling of transactions by changing the locking function in a way that it allows transactions with conflicting accounts in an entry, It doesn't break the execution of transactions on replay side. As it parallelize entries for execution and not individual transactions in an entry.
It looks like the way locking is implemented in execution the assumption is that the replay side will execute individual transactions in parallel, which doesn't seem to be the case.
The only thing that can break from our exploration is the rebatching logic in TVU, which can also be fixed by changing it a little e.g acquiring locks after rebatching is done.
We think if this overstrict requirement of making disjoint entries can be changed to allow entries with transactions of conflicting accounts, the performance of the banking stage can be improved by scheduling the transactions in a way that CPU utilization can be improved.

Do you guys have anything else in mind which can be affected by allowing entries with conflicting transactions

@steviez @apfitzge @jstarry @buffalu

[steviez]

Thanks for posting the issue @talalim; much less likely to get lost here. This week is a little busy with Breakpoint going on, but I will try to refresh myself on the matter and give an answer next week

[talalim]

thanks @steviez
Looking forward to your feedback.

[apfitzge]

@talalim, thanks for creating an issue. This is something that has been on the map for a while, but held back by other work.
As some of the scheduler work is beginning to wind down, this is one of the things I am hoping to begin work on.
Although I doubt we'll get much pushback, in my view since this is a base protocol change, it should be going through the SIMD process, even if as a formality.

WRT to actual implementation, I don't think it's as simple as described here.

That assumption seems to be that the TVU will break up a batch and execute individual transactions in parallel. In reality, this is not the case.

We currently do re-batching on the entries we are processing. If we removed the re-batching and used entries directly, we can guarantee that we are processing the entries (potentially self-conflicting, but not conflicting with eachother) and there are no issues with parallel access.
However, part of the reason we do re-batching is to help mitigate an attack vector where the leader maliciously creates entries that take a long time to process. So I'm not convinced we will want to just remove that immediately.

Other than that, it's just simply re-working the current implementation. The current batch processing of transactions does not simply loop over transactions, but does sections of work for all transactions. This requires some re-writing of code, since we can no longer load all our accounts up front, since for some shared writable account the state may have changed.

All that's not to say this shouldn't be done; it should. Just giving an overview of how I've viewed the problem, and why it hasn't been done yet.

[apfitzge]

Created a SIMD here: solana-foundation/solana-improvement-documents#83
In terms of priority, I think it sits behind 0082; but these are very much changes that could be done in parallel

[talalim]

Hey @apfitzge
We looked at the SIMD and its exactly what we're talking about that the constraint on entries should be relaxed.
We implemented and tested the required changes to enable self conflicting entries in our lab setup and this improves the performance alot depending on how you schedule the transactions on every execution thread.
The changes include:

• changing account locking function
• carrying temporary account state within the execution with every transaction in an entry

We can make a PR for these changes which allows all of this for community to review this.

[Huzaifa696]

please add me huzaifa.rehman#2212 and talal.irfan#3032 to proj-tx-scheduler as we are actively working on this problem and have obtained some exciting results

[Huzaifa696]

TVU handles two distinct scenarios in process_entries()(Link):

Flow 1: Re-batching Conditions
When re-batching conditions are met, original batches/entries are broken down into smaller ones and an updated vector of batches is prepared for submission to Rayon threads for execution.
Flow 2: Non-Rebatching Conditions
If re-batching conditions aren’t met, original mutually disjoint batches are not modified and the vector of batches is submitted to Rayon threads as is.

After either of the above mentioned paths, each batch is allocated to an individual Rayon thread [link]. Subsequent to this allocation, every transaction within an entry is executed sequentially within its assigned Rayon thread.

The challenge arises when self-conflicting batches occur within the first flow. Breaking them into smaller batches shuffles the order and prevents their parallel execution within Rayon threads.

Another challenge for entries with conflicting txns arises in execution as account state is not carried and updated from txn to txn. This needs to be done for the duration of execution of an entry in temp state to ensure correct execution (balances manitained correctly) until the entry is committed.

To address this, the PR [link] introduces some straightforward changes to the rebatching logic and account state logic during execution. These modifications aim to allow for the parallel execution of self-conflicting batches within Rayon threads.

I have tested this with a multi-node test by enabling batches containing conflicting txns from the TPU side and setting up bench_tps to create conflicitng/interdependent txns.

@apfitzge @talalim @steviez

[steviez]

@Huzaifa696 - Thanks for your continued interest / efforts on this problem! As mentioned in this comment:
solana-foundation/solana-improvement-documents#83 (comment)

The order we'll follow is SIMD approval ==> Feature Gate Issue ==> PR with SIMD implementation behind feature gate. So, I think we need to get agreement on the SIMD across the ecosystem before we jump in with the implementation. As such, I am going to wait on looking at the code in the PR you linked until we get the SIMD approved. Hopefully we are able to reach agreement on the SIMD, and your code can accelerate getting that feature implemented and eventually deployed!

Chatting with Andrew, he pointed out that there could be some changes made that don't necessarily impact consensus / require a feature gate, but if we're going to potentially update this piece, I think it makes sense to reach agreement first and then plan the agreed upon changes accordingly