"Turbo-Geth - too good to be true?" - Alexey Akhunov

and uh next up we have Alexi talking about Tri and uh he'll just be covering sort of all the the latest improvements and performance updates that have been added to the trette project and uh he is uh in this room so I'll let him introduce himself and kick off with the presentation welcome Alexi hello hi caric thank you very much for the introduction and uh yeah so I will let me just start the screen share I will um sort of say a couple of words about second let me just figure it yeah so okay so first um um little bit about myself I basically um I am currently I've been the programmer for pretty much all my professional life and uh for almost last three years I was working on this particular software just called turb and what turb is is basically it started as a fork um um as a fork uh the um of the go ethereum and sort of experimental software uh with certain goals to basically make it a bit more performant if possible and uh but now it's pretty it's it's becoming more more more different and we're going to see in the in our talk how and why and the title basically is is too good to be true is addressing the the um something that I haven't thought about until very recently is that whenever we present some kind of performance numbers for TR most of the time the first question I get where's the tradeoff like what's the catch what is what what is the because people think well if we do something better then we might we have to do something worse and so basically that's what I want to address so here's the picture about the um so in the databases B I look at the first of all I look at ethereum as a database essentially it's a it's a distributed database with certain properties um uh but in the databases essentially you have usually like three points uh between which you're making tradeoffs um so update efficiency space efficiency and access efficiency and sometimes of course uh the the space efficiency helps all others and yeah yeah you can kind of move around and and trade one for another usually you might have seen those triangles as well um in different areas and so you know people normally think about moving in this little plane which is the the circle underneath um and so this is where you're going to get tradeoff like oh if I get more efficient in Access I must be losing something and some other places but what actually happens in technology all the time and if you look at it there are there's always Technologies which are strictly improving right we we have we have seen this many times for example move from SSD to HDD first of all the SSD was were more expensive but now they're so ssds for for considerable volumes they're not uh so expensive anymore and they're pretty much better at everything so nobody's asking what is a trade-off between between SSD and HDD um at least not anymore so this happens all the time uh in technology and usually the the way I see it is that the previous technology is a bit further um further um down further apart away from the from these fishing Frontier where you can do trade-offs and so usually you want to get closer to the efficient Frontier and that normally requires some kind of paradigm shift and the paradigm shift is usually also kind of goes against the uh the common intuition um so we're going to look at this so what kind of the paradigms do we did we have to shift here to uh which I basically I posit that we did get closer to efficient Frontier so there are a little bit of tradeoffs but not many so next time you know that's why every time people ask me the questions what is a trade-off I this is what I'm bringing up so so we we're going to be talking about the trade uh the paradigm shift in the data model where we replace trees with the flood data we're not going to be talking about uh history uh the data modal for history because it's another complex topic and then I'm not going to cover it today but we are going to be talking about other things like concurrency and architecture so um with the concurrency is essentially uh whether you do homogeneous concurrency essentially when you're trying to run many things at once but they're pretty similar or do you want to run like lot lots lots lots of different things at once that's what I call the heterogeneous concurrency and in terms of architecture it's the here you basically the shift is from monolithic uh system with a lot of cross cutting concerns done in the name of optimization we moving towards the modular system with the separate separate concerns which I POS it as well is more optimal um so we start with the data model and so what so kind of I thought about this for a very long time like where does this come from where does these uh data model come from what everybody's using and I some time ago I saw that it actually probably comes from the yellow paper and again it comes from the sort of common intuition that yellow paper essentially calls this particular way of storing data that most implementations do right now a sensible implementation or a reasonable implement ation and it says that it's memorizing the function C which is essentially function C is mapping the the um the nodes in that that that sort of State try into their sort of hashes or something like that um but actually it might it should probably be the inverse so although this particular paragraphs these paragraphs are not normative they already create this sort of they basically based on somebody's Intuition or some sort of common uh kind of expect and therefore everybody assumes I guess everybody assumes this is how we should implement this and this is where it goes so back in 2017 when I just started this project I started with profiling go ethereum and I bumped into this thing which was 20% of my profile and this is exactly accessing this memorized function inverse me memorized inverse of a function C so essentially given the a hash you need to figure out what is the the node um the the tree node is so basically that's the uh so in in in the previous slide we were talking about recommendation to memorize this function and here we're actually using this memorization and that was the from my point of view that was a performance bottleneck and this is where all that started so and this is the picture you probably saw many times some of you so on the left is basically is my very simplistic representation of the state TR where you have um some elements which are V1 V2 V3 so forth and they are built up into this kind of sophisticated I would say State try and the the the the point Sorry the arrows the black arrows in that the tree on the left are the um those uh function like memorization of this inverse function so given the root hash I can get this root element and so forth and can navigate through so examp for example if we wanted to find element B5 so we need to basically access this memorization one two three four times so that's the basically four access to the database if you use this me memorization as a data model and what I noticed straight away is that I couldn't parallelize this because there is a data dependency there so you don't know you cannot do the you know you can don't do the second um Arrow until you resol the first one so there is necessarily um uh data dependency and no um possible paralyzation and on the right you can see how this memorization kind of is laid out in a database if it's a key value store so yeah and so here's another point is that you're essentially the the deeper the deeper the tree the you know the the worse the problem is becoming but why why does it why do this uh you know why do we actually have to do this at all and it turns out this is all about Computing the state um State root hash which is which we need to either if you're a minor you have to place it in in in um header or if you are just a verifier of the block you have to compare what you've computed with what um you got in header so all of this complexity is simply to verify the state Ro hash and this is actually one of the interesting innovation of ethereum compared to bitcoin which essentially commits every every block we commit to the uh to the state uh to the state route and this is actually quite a good interesting feature but it has a certain cost and apparently so myosite that the the cost of implementing it in the old way is actually very high and it's unnecessary high so what does the um so now uh what does the evm think about it so if we look at it from the evm point of view um so if anybody if you looked at the like what is the evm up codes are they actually have no idea about to try so they don't actually look at to try they look at the um account addresses and they want to um Pitch balances bite codes or storage and stuff like this and also some instructions for storage loading they again they look at addresses they look at storage location there is no merization here at all so um so basically what uh the hypothesis was that okay the having everything stor having the state stored in a Radix tree as a primary structure it tries to satisfy this um sort of computation of the state route which I think is quite a minimal thing and uh but it sacrifices the efficiency of evm access as we saw before it requires the uh sequential um data dependent access so is this sacrifice worth it so essentially we sacrifice evm efficiency and to be able to compute these State root hashes quickly and that's what yellow paper calls sensible or reasonable implementation so yeah that's what I've been working on for last two years uh is that trying to figure out if this is sensible or reasonable or could it could be that this this is a false tradeoff and now I am convinced that this is a false tradeoff because it is possible to do both things efficiently Compu State Route and have efficient AVM access okay so but how do we do that how so we know how if we have a flat D structure it's I don't need to explain you how to provide deficient St access from evm because it's clear like if you if you go back to the slide if this is exactly how we start store the data evm simply accesses it in in this form so I don't need to tell you how this work but I do want to tell you how the other part works so given the flat structure how do we calculate the the state roote so yeah the if we know the structure of the tree then we can do that and you know of course you can try to build up the tree and then compute the root but obviously that is going to be quite memory intensive what you could do better is that you can start um some kind of stack and then you need to calculate the tree let's say from the left and then you um you know you you only keep the stack of one two three four five hashes and then um every time you move on you just appin like you accumulating sort of um the hashes on certain level so you can basically compute this whole thing with a very limited memory so with about five um five accumulators for hashes and so forth but that's still quite large I mean um I can tell you that for example it's say an SSD it might take you I don't know half an hour or something like this or sometimes an hour to get it be depending on the speed to essentially iterate through entire State and compute the state route so although it's sort of relatively quick but it's not as quick as you can you can't do it for every single block right uh it's too slow and so the problem then becomes is that okay what if we um we had a root calculated and we had had maybe we cached the part of that that state tree in memory but because we don't store it in database you know once we Flash the memory it's gone and then we needed to mod in our block we needed to modify this green thing and then sort of like how do we um actually calculate the new State Route how do we do that so in originally this is how I I was doing it I would essentially load the entire region of the structure the entire one in an would calculate the root and that was well that kind of worked as long as your um as my kind of cache of the state was large enough and in the beginning it was terribly slow like on a startop and uh but then it was also if start if the if the block started to hit some cold spaces cold uh spaces in the state it was quite slow um but I I sort of thought okay I'm going to solve this problem later so I was running with that I was saying okay I know that it's really crap right in the moment but I I know we're going to solve this uh because I had this idea how to solve it so this next slide shows how we're going to discard this data because we just used it to compute the state root of that little sub tree and then we discard it okay so the solution that I was thinking about all the time but I just didn't have time to implement it but now it's all implemented by the way so now it's all done and dusted so we going to store the what I call intermediate hashes um so it sort of you might think that oh but this is actually going back the direction of these um you know trees actually no because in the tree that yellow paper suggests to do uh we are mapping the hashes into the um the nodes but here the mapping is kind of opposite not opposite but slightly in Reverse so we're mapping the prefixes in the trees to the hashes so essentially the the function that this particular structure serves is simply to have those hashes and we store them in the database yeah and a storage is also um I would say that it has a nice properties because the it's got to the data locality and things like this and it's it's it's also pretty small um so now if we need to solve the exactly the same problem if we have this green thing that we modified and we don't have um you know uh the the pieces of the trees around it and our cache so we can um use this structure new structure that we introduced to help us to bridge the um Bridge the gaps and so that's how we do it we load only those uh things that I pointed out with the arrows from the database instead of the entire region and here we go and we can basically compute our new state rout so this has been implemented this year um quite recently uh I think about April or something or may um and it has been optimized multiple times so now I show you um how like what is the cost of that right and also I'm going to show you like the how our storage looks like so the the structure the in the the additional structure that I was talking about just now it's called intermediate hashes it's currently for the like recent reasonably recent state is about two um two something gigabyte so actually it's it's not a bad price to pay for this right and it is the structure which essentially stores all the intermediate hashes for all the levels of the Stree and stuff like that and so you can also notice that there are two structures for the state and that's another Innovation which we introduced quite recently so we State we store the state twice but why so first we store the state as a plane structure which is currently 9.9 Gaby 9.09 gab maybe maybe a bit more right now and then we have a hash state so some of you may know that in order to keep the kind of the the tree balanced uh we need to apply some hashes to the Keys before we put in the structure um so we separate these two things so evm actually works with the plane State and uh then in order to produce the state root again only then we use the hash state so we convert it to the hash State and then we compute the hash there and but we have managed to get rid of the there was another table here which is called pre um pre-images so because we have the two states we actually don't need pre-images and there are some other nice properties about it for example it allows us to withstand certain dose attacks easier than um other implementations so yeah um so as I said I'm not going to touch on the history storage but it's also pretty efficient um and so all in all um the efficiency in in storage actually translates uh into efficiency of access as well because um things are simply smaller and then and then they're actually more kind of standard so you can look them up quicker so now we go to the second Paradigm uh which is the the concurrency and so here is the something which kind of was discovered again this year is that on the on the top you basically can see how the the things were processed before in go ethereum and in before that time and you can see that when we download the blocks uh there are let's say some sort of stages of processing for example we do um recover um signature sorry we recover senders from the signature so forth and we do um we do certain things like run evm through it and compute some storage route or whatever it is and so usually this happens sort of in parallel with this kind of staggered uh staggered concurrency and lots and lots of things happening in parallel and so what uh we did is that we decided to split them up and like this and of course intuition would tell you that would tell you that this is actually slower if you just look at this graph diagram it's like oh no no this is definitely going to be slower actually uh it it probably was a bit slower in the beginning but then the the because we managed to split them into more homogeneous pieces we were able to actually make the individual pieces are faster and in the end everything was much faster maybe like 10 times again this is another Paradigm Shift which you go into the counterintuitive Direction and then you arrive at the at the kind of Next Level result um and so this is the stage sync so what did what basically happens here is that we are trying to process as especially when we do the initial sync we we try to process things in large batches the as large as possible so for example if I were to sync right now my first batch would be more than a mil million blocks so I first put this 11 million blocks through the first stage and then another million in the whole batch through the second stage and so forth and so because we do that and so in the red I just put here um some text is that because we're putting most of these stages are actually essentially data transformation they take the data from one table and database they do something with it and put it in another table of in database that's why I'm calling etherum a database so but with the databases that we use is that it's actually easier it's actually much more faster to um to put that stuff in the database if it's presorted so in the other words database are pretty uh you should not use them for for sorting so there are much better sorting algorithms and and so what what that basically graph means that we can use that property to uh speed up the the sync quite a lot and so but if you let's say Pro process one block at a time then the the time is not going to be so impressive uh but it would be very impressive if you start like processing Millions block million of block at a time and this also explains why our implementation actually uh could work with um um HDD sync uh which hard drives actually one is currently just on a Finishing Line right now I started almost 30 years ago sorry not years 30 days ago sorry and it's today is is finally catching up with the with the tip of the chain but when it catches up it's not going to be able to process uh every single block through the stages what it will do which I tested before is that it will so you see this intersection here it's for for example for my HDD it will be about 15 blocks it means that it cannot uh process you know one single block quicker than 13 seconds but it can process 15 blocks approximately at the same speed as these 15 blocks are produced on the main net and so this is where we find the intersection so my HD sync would be always having a lagger of about 15 blocks but for some application it's probably all right I mean but as I say that because ssds are so much easier now so much faster and then because we don't require you to have five terabytes so you can actually buy a pretty cheap SSD and run it so you don't need HDD so it's pretty much for academic purposes at the moment and I think by the time our size grows to two G two terabytes you probably be able to afford SSD at the same price as it's now for one terab or something like that so anyway so that then we go to the third part third paradigm shift is the architecture so I put a note here about cev calls in July 2020 some of you might have listened to those calls so for three calls in a row um we decided to not discuss the IPS for Berlin but talk about other issues about kind of wider issues and we talked about developer burnout we talked about development process and things like this about the client diversity and so maybe some people think it was completely useless but actually I thought it was really really good and I learned I got basically I uh I found it very informative and I made some conclusions out of it and so one thing we debated on the call is that whether the modalization and splitting things in component would actually help and so they they were opinions in the call with saying that if you start splitting things up um you know you lose the optimizations because there was assumption that optimizations have to be cross cutting and they basically like tie everything together and eventually it becomes a big spaghetti but my experience is actually the opposite and there was a one person on the co actually agreed with me and so this is where we are on the journey to make this happen and so as you can see here is that one thing is already done two things in progress one thing will be started and actually on the right here is that the stage sync is also part of that um so it's also kind of componentization so and one of the interesting things about this architecture is that it um hopefully will allow us to bring more developers into the into the project and into the core developer development in general it does actually also lead to certain sort of abdication of power from core developers but that's it's a bit larger topic and I would probably discuss it in somewhere else in kind of more long form whatever chats and podcasts and stuff like that um then the last slide which is a bit of a you probably heard about or seen me talking about 10x Improvement in ethereum so and today I just realized that oh you know why is it can't we go from one ethereum 1X to ethereum 10x um or some X maybe 2x so and so the if we if we actually take it seriously then uh there are from my point of view three main challenges here so it's a nice goal to have of course to to to do 10x on L on ler one uh but um there are three main challenges which I sort of describe here I'm probably not going to unpack all of them for you but they the Dos attacks and there are certain dos attacks we know about and some of them are because of the state AIS but some of them are computational some of them are related to precompound and that thanks to V like to point pointing out to me so we currently actually assessing those uh things U I mean I know that some groups are doing the same thing but we're assessing it in the context of turbog we are finding more attacks and we're trying to figure out how to protect against them and so we just recently started this effort and then there are other things that there are other two things that people are worry about but I think they are also solvable so on this point I think I'm going to end my presentation and I don't know if you have any time let sorry guys I think uh thank you so much Alexi we do have a few minutes for questions and we actually have a lot of questions coming in so what we'll do is I'll just kind of ask a few here and if we end up running out of time I'll just ask you to uh okay join the live chat on life. online.org and you can just answer them directly there all right so handful of clarifications a handful of uh broader breaker questions uh the first one being um does double hash in attempt to address any long-term State degradation related issues I'm not sure about double hashing but uh I don't know I'm not sure what it means uh what what is meant by double hashing to be honest sorry I think this will this common will reach the audience in about 30 seconds so I'll just have them see and clarify this but in the meantime I'll just move on to the next question and that is uh so it's I mean you kind of talked about that it's taken about three years um to kind of get where you are uh purely out of curiosity what was like the most surprising breakthrough um in that time from kind of your perspective I think the stage syc was the most surprising thing because I kind of thought I discovered very early on that data model would be beneficial it's just that with the data model essentially the reason why it took so long is because um it's sort of like in engineering you solve one problem but then you get another two problems to solve and then you solve those two and then there's another three and so I wasn't sure whether the sort of I will be able to to tie all the loose ends in the end and then I only figured out like last year that I will be able to tie all the Loose Ends and it will work but the generally I thought it would be the it would work but with a stage Sy for example or now with a competent comp compon components that was quite surprising to me that such simple things actually make such a huge uh impact um that's awesome um I guess be a follow up on that how how many people are currently kind of helping you with being a contributor to Turbo right so it's actually the team has grown quite quickly and uh so specifically this year so we currently have about 13 people who are basically working on it like 10 full-time three part time and I'm most of the time I'm losing count because I'm actually inviting people all the time and the reason I'm inviting people more all the time because I do want to test this idea that if we uh if we do things in components uh we can have U many more contributors which are sort of they're not just waiting for the pool request to be merged but they are there to develop their components maybe on multiple different implementations of the same component um and so forth so I'm I'm actually op for testing the the the theory that we could have a much wider uh cont utions no it's awesome it's a it's a wonderful a wonderful problem to have when you're uh scoring too fast and you get a track who who's fully contributing so that's that's wonderful um another question that um sort of came from the answer you just gave and that is what was the actual original intuition that sort of uh made you even try stage thinking in the first place was it just experimentation or it was essentially um yeah that's a good question because what I was so basically I was profiling to foret all the time at at some point I got to the to the place where the the right rights to the dis were the bottleneck at some point and obviously as I normally do that I started to um split um like luckily the database we had allowed us to um look at the like a right chore like I call the right chor how much data you write for each table rather than on the entire database and I noticed certain tables were were very intensive in terms of writing and so those were I I saw that those were the the ones that um they had a very sort of randomized keys so for example the transaction look up one where if you have a transaction hash you can figure out which block this transaction in and obviously the keys being a transaction hashes are pretty randomized and so we were inserting those randomized hashes with in the middle of the table and I was scratching my head thinking maybe if we try to to pre-sort them like if we if we just take the whole bunch of them like the like 900 million of them pre- sort from them by hash and insert them that way is it going to be faster and it turned out to be faster and this whole thing generated uh the essentially the stage sync uh it required a bit of a bravery because in order to push it through we had to delay the the release and we had to rip everything apart and then change the architecture entirely into about two months it was actually kind of risky thing to do because some people said no no you shouldn't do that you just like release and then change it but no no if I release I'm never going to change this I have to do it right now and I and I think it sort of paid off um absolutely no high risk High reward and uh glad that you you did um last question for today before we move on to our next talk and that is um I mean it's a pretty big core value in our space that uh people should be able to run um and and kind of individually run inv validated notes and um kind of especially from like the the Gen say block so what are you kind of thoughts on on this as a norm um and is kind of is one of the motivations behind tro to actually make this world a lot more possible or or is it purely it I mean it wasn't started for this reason I mean I simply wanted to create the better technology I don't really like I I don't know if it's going to be the norm because maybe if we do like let say e 10x maybe we will make it impossible again to essentially we improve the technology but we use it not to uh let everybody run a node on their on their Raspberry Pi but maybe we're going to use it to expand the the boundaries of the system instead right so I don't know it's not for me to uh to kind of make this sort of into ideology I think I'm just want to make a better technology and we will see how this is going to what it's going to do is it going to make people run raspberry pies or is it going to make ethereum 10 times bigger right um so no that's wonderful I think uh you're a you're taking the stance of being a technology maximalist and uh that's and that's awesome um so there's a few more questions that are in in the chat so I I'd encourage you to just kind of reply in the chat directly and I want to thank you again for uh doing this talk and answering all of our questions and uh lot excitement on the chat so thank you so much Alexi thank you byebye