Parallelizing EVM Transaction Processing | Gary Schulte - Besu

[Music] hello eth Denver welcome to the second half of the Basu hour over here at the captain ethereum stage uh my name is Gary schy I'm a blockchain engineer with consensus I've been working on Basu since 2021 um my talk is on evm transaction parallelization not on layer 2 not on a special blockchain we're talking about layer one transaction parallelization today uh it's a it's a deep topic uh but it's fairly accessible um in the interest of time though I'm just going to get on with it so uh ethereum is scaling uh layer one's scaling Layer Two is scaling uh we're seeing asks for um more block gas uh there's New cryptographic Primitives coming on online with pios with verl uh pretty soon now with pectra um the tldr here is that we're asking more and more out of our execution clients and they need to get things done as quickly and efficiently as possible so as I said my talk is on execution specifically um in any 12C ethereum slot four of those seconds are dedicated to block execution um if we can use as little as possible of those 4 seconds we can yield that time back to our consensus client uh we get better attestation times we get more time to propagate we get better financial performance um the network is happier overall everybody's happy when we can execute as quickly as possible so if we want to eat as little into that 4 second window as possible what are we typically doing during those 4 seconds um there's a couple of things that take most the time the first is we're executing transactions in the evm I mean fundamentally that's what's going on when we execute a block uh the next thing that we're doing that takes time is we take the results of those transactions and we apply them to State and we calculate a root hash and we do all of that work um this talk is focusing on the former just the transaction execution and specifically doing that in parallel on multiple cores so that we can get that done as quickly as possible so a quick history lesson um ethereum pretium what what does pretium ethereum have to say about transaction execution well uh the white paper specifies that we have a shared Global State and transactions should be executed against that shared Global state in the order that they were packed into the block that ensures that all the different clients arrive at the same answer have the same end state by executing the transactions serially uh originally there was actually a kind of hard requirement to execute transaction serially um the transaction receipt for each transaction needed to include an intermediate state route that means that you execute the transaction you apply the results of that transaction to State you recalculate your state route and you include that new intermediate state route along with the transaction receipt and you do this for every transaction until you get to the end of the block um as you can imagine that's not as efficient as it could be that creates right amplification um and it just makes things run a bit slower than needed so in banum um EIP 98 and 658 relaxed that requirement so that we don't have to include intermediate State routes we just instead include a Boolean to say yes the transaction action succeeded or the transaction failed um now that was a good unlock in terms of being able to aggregate the results of all of these transactions and applying all of that state change at the same time we get rid of that right amplification and everything when you do it in batch is faster so that was a good unlock but in terms of how that applies to parallel execution now that we don't have to calculate that intermediate State Route we can execute the transactions in any order we want and in parallel the only thing that we have to worry about is when these transactions are touching or mutating the same shared Global State um so with that in mind what kind of parallel execution strategies might you implement in order to be able to leverage multiple cores well the simplest strategy is just don't parallelize you know it's safe you know that it's protocol specified you know you're going to get the right result um incidentally you're also going to end up with the worst case block execution and that sounds bad but it's actually useful because we don't have any guarantee about a rate of conflict in any particular block we don't have any guarantees about what performance we're going to gain from executing things in parallel because it's kind of trivial to create a block that has 100% conflict so when we're setting gas targets when we're trying to think about our worst case we need to consider all the transactions executing serly so that strategy is probably not going away anytime soon if only because it informs our worst case so if you do though want to take advantage of multiple cores and try to get execution running faster some strategies you might think to implement would be like pessimistic lock based uh synchronization there's been some presentations here I think archology maybe aptose um they're talking about locking State uh moving State uh all these things that allow you to do some intelligent scheduling of transactions that might otherwise conflict um the ethereum protocol the core L1 layer one protocol it doesn't have those Primitives it's not just just a non-starter so that leaves us really with just optimistic execution optimistic execution would just see us execute all the transactions in parallel against our shared State and try to detect and handle these conflicts so what strategies what optimistic execution strategies might work um one is a somewhat naive and that is to just assume everything's in Conflict you run all your transactions against your shared State and you just presume that everything's in conflict and you throw all the results away and reexecute that we block again serially and it that might seem kind of strange like why would you bother to execute something in parallel just to reexecute it again serially well there's some benefits you can gain there one is that when you're executing transactions in parallel you're able to load everything from state that you need in order to execute your transactions and any expensive compute operations you can cash those and hang on to them so that when you get rid of your parallel results and you re reexecute in a Serial fashion there's minimal IO weight there's minimal CPU weight you're running that block in seral as fast as is possible um incidentally this is the basis for nether mes uh pre-warming feature nethermind implements a ketak hash cache where they keep all of the recent uh results of hashing values and a uh pre-compile cache where expensive pre-compile computations are cached uh and also a storage cache so that when nether mine re-executes its Block in Cal it's got all the advantages of everything sitting there waiting for it another strategy might be to try to detect and handle these conflicts instead of throwing away the results you somehow try to detect in what way they're conflicted and resolve that conflict um so like the prior strategy you would execute everything thing in parallel against your head World State and then you would try to aggregate all of those results in the order that the result that the transactions were packed into the block at the time that you do that aggregation that's where you do your conflict detection and when you find conflicts you reexecute against a state that has already had its prior transactions merged into it uh the core of this strategy what makes it possible is that conflict detection and this is the strategy that Basu implements and I work on Basu so I'm going to talk about it so a quick recap on Bonsai Bonsai is a storage format the default storage format for Basu um where Bonsai is relevant to parallel transaction processing is in that it provides a few key features that allow us to do this um Bonsai provides a single semantic worldview there's only a single state tree a single flat database stored on disk at any time that's how we save on storage we have a small storage footprint that's kind of the the primary value that Bonsai has been bringing um but also uh any diff to that world State any prior block any future block or whatever is stored as a diff to that state so you can think of a Bonsai World State as like a git repository that you can roll back and forth to any particular particular commit so one of the features that make parallel execution possible is inmemory World State overlays Bonsai what it does is it provides an inmemory overlay for that semantic World state so that you can read it you can write it you can mutate it you can roll it back and forth and you can persist it to dis as a diff but what's great about that is that you can also clone it you can create 20 copies of the head World State you can create a 100 copies of the world State you can create a thousand copies of the head World State and it's just a map in memory that is an overlay on top of it this is how we can duplicate this head World State and allow all of our transactions to run in parallel against their own uh segregated I guess uh World State the uh the next feature that Bonsai gives us that makes this possible is the accumulator the accumulator data structure is specific to any particular World state every World state has its own accumulator and the accumulator is tracking any reads or any writs or any updates to that world state so that gives us kind of a summary of what happened when we execute a transaction against this isolated World State get it lets us know anything that happened anything that we touched read right or mutated during that block during that transaction specifically so this this is the basis for our conflict detection that accumulate our data structure so Bonsai basally is using Bonsai as a type of software transactional memory uh software transactional memory is a class of concurrency control that allows you to do optimistic parallel execution against shared memory in this case that shared memory is our head World State and we take multiple copies of this head World State as I said before and we give each transaction its own private copy and we kick off all of those transactions in parallel against all of the cores that we have available to us once all of those transactions are complete their accumulator has the summary of all the changes all the touches all the mutates and we can merge them into a single World State a single intermediate World State and as we merge those we check for conflict using the accumulator so for example transaction one completes we merge its accumulator into our intermediate State and that's fine there's nothing I can conflict with it's the first transaction the second transaction we merge its accumulator in and the first thing we do is we say has anything in here been modified in this intermediate state if it is we we kick it out say this this has a conflict we need to reexecute this against this intermediate State and if not we just merge it so we do this for all of the accumulators and at the end of that block we have a resulting World state that has been parallel executed or at least as much as possible has been parallel executed so this is all core um depending on detecting conflict and detecting conflict has a couple properties it needs to do it needs to be fast and it needs to be correct um it's kind of pointless if you parallel execute a to block and the conflict detection algorithm is so expensive that it's more expensive to run a block in parallel than it is to run that block serially so what we've done is we've ordered these checks to be as cheap as possible and the cheapest first we want to fail fast so we don't waste time with expensive checks uh the first thing that we're doing is account level checks if an account that's modified or touched by a transaction has a non or a balance or code has or whatever that's already been changed in the intermediate World State we're trying to merge into we market for conflict if not we move on to contract storage if a transaction modifies contract storage uh transactions can modify a lot of contract storage there's um several things in contract storage we might need to in in elements you might think that we could potentially change so we save this check for the last because uh it's just a more expensive check to make we look at all of the elements in contract storage that have been either read or updated by this transaction and we make sure that they haven't been modified already in that intermediate World state if it has it's conflicted check it out reexecute if not we merge that in we do this for all of the transactions in the block and the resulting World state has all of the changes from all of the transactions now we take all of those changes and we merge them into the state tree and then we recalculate the state route and we take that state route and compare it to the state route that was advertised in the block header if it matches we're good we just parallel executed a block if it doesn't match something went wrong either that block was invalid to begin with OR that something happened during the parallelization a race condition or maybe a false negative for conflict detection so and basically we add a fall back to uh serial execution if we detect a state route mismatch we want to be certain that it really is a bad block before we report to the consensus layer that it is a bad block um not to put too fine a point on it how well do ethereum blocks even parallelize if we try to run things in parallel what might we actually see um there's a couple of things that play into that each block is different as I mentioned before there's no Guaranteed Rate of conflict or or parallelism so the contents of the block kind of Define this High Watermark of what might be parallel uh then it comes to the hardware itself since we're using multiple cores we're running all of these things in parallel we're trying to get all of these parallel transactions completed in time to merge them into the block uh at the time we're trying to uh do block processing so if those parallel transactions haven't finished maybe the hardware is underprovision maybe it's like a 2017 era Nook or something like that it just doesn't have the horsepower to get there in time in that case we at the at merge time run that run that transaction in serial so if you look at the chart here this is a sample this is uh you know this is my own personal Nook it's the solo Staker special uh just an Intel processor like a $600 computer and you can see that on Basu on that type of hard Ware on commodity Hardware we're achieving moving average roughly 60 to 65% of our transactions on Main net are successfully running in parallel we're considering that a pretty good result um The Ref team did a an analysis uh of historical ethereum transactions and they determined that roughly maybe 80% of transactions might be parallelizable so when we're in real time uh getting 60 to 65% we're pretty happy with that so what's the net performance um on that same Nook um we're seeing for that 24-hour period on average 160 to 170 megag gas per second that's 160 to 170 million gas per second um again this is blocks subjective blocks that are full achieve a higher throughput than blocks that are empty uh on not all operations cost the same and again it comes to Hardware so whoops missed a slide what are our recommendations um the takeaway should be that parallelization isn't a slam dunk you don't always want to enable it because it is Hardware dependent and it is block dependent and use case dependent so conflict detection itself is a cost it's strictly a cost and the Heap memory pressure from these additional World states that we're using for parallel transactions that is a cost uh um the resource consumption using all these extra cores that might cause some contention for inter or intra processes you might see some things shift around um the takeaway is the tldr is if you are interested in high performance execution if you want good validator performance if you're running on an L2 using basis Basu as your execution client you should seriously consider enabling this feature um we're finding the best uh TR off is right around eight cores maybe four cores if you've got hyperthreading and you've got you know logically eight cores on a four core machine that's pretty good that's we recommend going that route we want you to try it out that's what we're trying to get here today um Basu has had this feature since 2471 it's been marked as experimental while we iterate on conflict detection and as we improve the conflict detection to reduce our false positives um the Basu 253 release is going to have the best best of breed of this probably final form of conflict detection so we want to get that out there and get people using it and testing it and if you want to try it out on your own Basu node uh there's it's still marked as experimental but probably soon going GA um that is the long and the short of it give it a try um I've got you know questions comments or feedback let me know you can hop in to the Basu uh main net Discord on the consensus Discord or the Basu channel on lfd thanks very much