DAPPCON 2018: Turbo-Geth: Optimising Ethereum Client(s) - Alexey Akhunov

Transcript

so basically this is the project that started late last year and it's currently supported by the grant from a Syrian foundation and I'm not going to details why I'm doing this apart from the fact that I'm actually enjoying doing this but you probably understand why we need to optimize the serum clients right so now so this is the outline hopefully that will help you decide whether you want to stay till the end or is anything interesting there that you want to hear about let's go in so I am NOT going to go into the miracle trees sorted and sorted so let's go straight into the why this slide is here so essentially my first assumption about

why the ethereal network was inefficient around for example around the time of cryptic kitties in further down my assumption was that it's something to do with the state something to do with the slow access to the state and because and that assumption was based on my profiling results from a guess is how a hosting started and I'm now started questioning the subsumption but this presentation has not reflected it yet and in order to understand the access to the state we need to understand how the state is stored in a Syrian client at the moment so let's start with the radix miracle radix tree so if you let's say that this in this example you want to store a dictionary of four values in

this kind of structure and you can clearly see where every word goes so the the path in a tree represents the key and somewhere on the leaves there there are values and the reason why it's called merkel because there's a hash in going on or every triangle is essentially concatenation and hashing and then the result of the hash is inserted up upwards so essentially in a you know end you get the roots of hash of that radix tree so in this theorem this is like how the state is essentially a dictionary of tea tree value but instead of the radix 26 as you have seen in the theory of the radix 16 so that's why they're the tree is actually

the problem with the radix trees like this is that you very often if you if your keys are randomized then on average you will get a lot of these segments which have really long segments with the branches of one without one element and this is very inefficient because you usually allocate the whole sixteen elements and you only use one so you have a like some blow up so when you store this date in memory it uses much more memory than you really want to and the solution to this is called Patricia tree which is really an acronym and the idea is that when you see these long branches of of the enoki like no unoccupied nodes you replace them with either leaves if this happens on at the

end of the like before the leaf or you are replaced them with extension and so this is how it gets transformed so that it's much more efficient in terms of storing it in memory and this is exactly what a cerium state is do it so instead of storing it in in a simply merkel redick's tree it stores it in this patricia tree it does have some disadvantages because the code to handle this tree is much more complicated than the code to handle usual red extreme because you have lots of corner cases like what happens when you got that extension what happens when you get this and that especially when you start deleting things sometimes let's say that in our example if you delete v4 right

and then that branch turns out into the branch with only one element then you have to merge the extension to the leaf and then this is kind of the corner case which is has to be handled anyway oh okay so now this is very quickly I like some people ask me like what is ROP ROP is used throughout of the cerium protocol and usually as an app developer you don't need to care about ROP but if you start looking into the serial client code you need to have an idea of what it is and essentially it's a way of encoding arbitrary data structures and it has a five different cases like a case of just one bite a case of array of

bytes short longer a bite and essentially recursive array of structures and it uses some clever encoding essentially what it allows you to do take any data structure in memory encode it into string of bytes and then decode it back and that will help us understand how the state is actually stored in most of the serum clients today so as I said before the state is stored in the memory when it's in memory it stores in a way in this Patricia tree which is on the left and then on the right is how it's stored in a database so the keys are essentially hashes of the Arab Peace realization of specific nodes and like you have as many

keys as you have nodes in Patricia tree and the values are essentially these strings of bytes which represent the ROP encoding and so now let's say that we are running out of memory for storing this current state and we decided to offload let's say elements this first stop elements with the pink and yellow ones right and we are essentially removed them from memory and they are sterilised in disk but we don't have that branch so now let's say that another transaction comes and this transaction wants to reference let's say v1 so what we need to do we need to fetch this from disk and what actually

happens is it laser okay so here look we only have the hash of that little subtree here but we also know that this hash is actually shaft free of ROP of this node so we look up we get here we get back the arrow key of this little branch node we dis realize it and now we have this bit but not this video ok so now we know the hashes of this little leaves so because we need v1 we take that hash and we do another lookup and then we get the serialization of that and then we we basically meet you realize it now so now we've got this branch in memory and now we can apply our transaction but imagine notice what

happened we actually did two lookups to database one to get this in this branch and want to get this little leaf and you cannot avoid having them sequentially because in order to do this lookup you need to know this hash but in order to know this hash we need to first do this lookup so there's a data dependency here and that data dependency means that the depth of this tree actually matters the deeper is this patricia tree there are more lookups you need to do to essentially unroll that tree and that's one of the reasons why oh that's one of the reasons why in a serial before you insert anything into that tree you have to first hash it with the this sha-3 of hash function which

serves as a randomized randomization function so that the tree becomes balanced and then it's not too deep because the maximum depth is currently 64 but an average I think that the usual depth is about 8 at the moment with the current size of the state so it doesn't have to go all the 64 deep anyway so this is how it's actually quite all because we are currently coming to the block 6 that million I think it's probably gonna happen tomorrow but this was a long time ago but still it demonstrates that the so what this picture represents here we have the levels of the Patricia tree down to the 12 there was nothing after the level 12 because of this balancing and here you

have the occupancy so this is the occupancy one which doesn't happen in Patricia tree because it's been replaced by the extension node and by the leaf nodes and so what you see here is essentially these the extension and leaf nodes and so here you get the 16 which is a fully fully saturated so essentially level up to up to 4 from 0 to 4 fully saturated which is ok and then you start having those little holes and as I said the most of the elements would live on a level 7 I think by now it's probably moved to the level 8 because there's quite a bit more state after that so but this picture basically shows us again that the depth is actually important so you can say that

on average you have to do seven look ups if you start from the top okay so now what the tuba guest is doing the turbojet is a radical departure from that storage model and it tries to say okay like I understand why people wanted to store the the they stayed the way they it was because it was very convenient to get the root hash of the state to put it in a block but what if we didn't do that what if we just store the things as the key value pairs as usual but like you usually would do in a database but then the problem is that how do you can compute the root hash and so the way you do it is that let's say again we want this thing wasn't in

memory and we wanted to materialize it what is that so essentially what we do first is we realize that this is 1 and we do range queries on the database which you can see that probably pretty simple and in the return you get this pair of key value pairs and then you apply this repetition tree fashion algorithm to derive this whole bit and then you can work with that data so that is it basically a trade off so we do more computation to recompute this parts of the patrician tree but in in return you get very nice and flat structure of the database and that dead structure allows you to let's say do RPC queries much

more efficiently because you're simply query what you want there is a little bit of complexity to that when you're we're going to look at it later when you actually have to look at historical data so this applies to the current state but the most crucial bit here is the depth does not matter in this model it doesn't matter how deep the Patricia tree is it does not affect the performance of the queries because it doesn't matter whether these elements produced the 64 bit depth deep deep sub trees or is it one level deep right so now we're going to talk about the process in architectures so if you open up the gap or probably other clients as well so what we will see there is that you get

this state in a database then you so I think whenever I click there's this flickering or maybe it's over there so this then there's a state forest and the reason I'm to the same forest and not a tree is because actually the guests at least stores let's say 128 passed patrician trees just in case that there's the reward so it quickly it can quickly go back to the previous tree and start building the fork from there because it would be expensive to try to fetch it off from disk with all these lookups so that's why I say forest and then whenever you have a new block processed there's a transient state which is basically in memory there's

like little hash map which Maps accounts to the account information and storage indices to storage information and when the block is a virtual machine does that it interrupts it interacts with this transient state and when the block is finished the the state is committed into the tree and then the tree computes the root hash and everything gets committed to the database but everything goes through a tree and when people do an RPC requests they normally also go through the tree so essentially they no go they don't let it go straight to the database they always go through the tree and let's say that if you have a query which is very often used by exchanges let's say you have a range of blocks let's say

block 10 and block 15 and you need to figure out which accounts have changed within this changed anything about them let's say nones or balanced within these blocks this query will have to unroll this big trees at the block 5 or at the block 10 and block 15 so that's actually quite slow now in turbojets it's a little bit different so the main difference here is that the RPC queries would not go through the tree but go straight into the database I have not implemented this yet but that's one of the last things to do and then the reason why I can do it as well is that I provide a common interface to

the database and the tree so I wanted to decouple it as much as possible so there that torture machine and transient state doesn't have any idea like where is the data is actually stored isn't gonna be Patricia tree or is it gonna it'll be like some other tree or it's gonna be the the database now let's go to some data so this was the actually this is already quite old but anyway so the experiment here was that to run a so it was a Google cloud the machine had the 20 60 bytes of memory one of them has says D one of them has HDD and the the I set a limit on five million five million

nodes in a patrician tree and you can see that it's inked in about twelve days right to that block 2.28 and then you see that the the HDD was actually fallen behind anyway so now this is how the memory did at that time so you can see this is the where the limit of 5 million started to kick in but you could see like there's still got something going on now I need to look at it further but yeah the memory didn't go up more than 6 gigabytes now this is another interesting thing so imagine that we have a huge amount of memory so at the moment I think you need about 70 gigabytes of memory and so you never

actually have to do this disk fetching operation for the state you only save the state but you never actually read it and then it sinks in about five days this is comparison to when we limited to 5 million loads which is quite interesting which will be relevant a little bit later I will tell you why so and in terms of memory consumption it went up to 68 gigabytes but you know it was it synced in five days versus twelve days okay so we will come to that a bit later so now let's have a look at the disk answer so this is archive mode archive node which means that it it actually preserves the total history of

off state like an unpacked so that you can always query the state at any storico point and as we can see here is that it's actually not very not too bad so for archive mode to have this because in the comparison I think the gas has more than terabyte to achieve the same thing and what we can see here is that ya on the next slide the clicker stopped working alright okay so so basically that's it I think this is really good I will try to get it even further down now

let's think about light clients in the beginning I come I completely ignored the the issue of the light clients because I think it would put too much pressure on me and now so I decided not to support fast sync because actually fast think relies on this patricia tree is always present in the memory so if we look at this protocols one of them is called east and one of old less so these are the basically the tree and FTTP protocols that are running in a serial network and one of them is supported by the let's say the usual nodes another one by light nodes and I looked at each of them and I try to figure out which

one I could support quite easily and which one I could not at the moment and the ones I could not support at the moment is this one and this one so what the get node data does get no data essentially is asking is given your hash inside the partition tree anywhere at any point in history or any point in current state and you're supposed to give it back the arrow P of that I cannot do that because it doesn't give me any information where in history T's and I cannot even if I wanted to I don't know like it doesn't tell me all that was actually for a block thousand with just a hash I don't know like I don't have all these hashes so and the get proofs is a bit be easier because when

the light clients asks for the proof it actually tells you the the block number and it tells you which account it is it's involved so actually it's easy for me to find it so I will be able to support light clients much easier than a fast sink because what I can do is that I can just simply for the purpose of supporting that I can keep a little bit of a history of the Patricia tree maybe like ten blocks in the past and hopefully the light clients will not ask for too old data and if they do then they say sorry I don't have that anymore we past that point but III will keep thinking about this so this is kind of the very recent thoughts about light

clients because I realized I would have to do that at some point now okay so now let's say this is a let's get another look at the storage requirements so at some point in in the development I decided to split up the current state from historical state it used to be that I treated the current state the sabres historical but just just with the the car latest block number as the history and then I realized that if you separate them the queries to the current state become more efficient and then what I also realized when I did this graph is that the current state isn't actually that big if you remember I needed sixty

eight gigs to stored as a Patricia tree but when I stored as a b-tree which is the how I represented database it takes less than ten gigabytes so there's basically a with seven x factor blow-up when your stored as the Patricia tree in the form that it is now so it's but it's actually possible if you score it in memory in a different format let's say it's a b-tree it's it's possible to like do 7 times compression and probably it will be slightly faster as well it's one of the things that we'll definitely try so and and then and that the reason why it's interesting because remember how the sync time goes down from 12 to 5

days so my theory is that if I implement this as the beech tree instead of Patricia tree I be able to get the sink time down at the cost of extra ten gigabytes of memory right that would be quite a interesting experiment so now another thing I don't like at the moment is this so this is the the artifact simply of Trueba yes it does not exist in get and what it is essentially for each block number it stores which keys have changed in this block number and the reason why I need this information is first of all it allows pruning very easily I haven't implemented pruning but this information will make pruning trivial because essentially if you want to prune everything up to this block you just

consult this part of the database and just prune it and just delete everything and the second reason why this information is useful is when I do reorge I look back let's say that I do 10 10 blocks back reorge I look back here which keys have changed during these 10 blocks and then I know what to undo so basically I roll back the Patricia tree 10 blocks back using this information and it works actually pretty well but in the future I want to get rid of that chunk and I will tell you how so what is the my current thinking of this although I think the RPC queries will be fast faster than in current get but not fast enough and the

reason for that is so imagine that we have the database and in a database you've got a beech tree which is the most popular structure it gives you ordering on some kind of keys and in our case it's an account so let's say that it allows you very quickly to find any specific account write this be tree in a logarithmic time but you also have another dimension which is a block number and because this particular beech tree doesn't give me two dimensions I have to basically hack around it and what I do is that I encode this block number and I append write appended to the key right it's a bit hockey thing to do it still allows me to find the

account very quickly but it doesn't allow me to do slicing on the particular block very easily because let's say that I want to retrieve history for block 3 3 9 and as you can see that the current state only includes these little blobs but there are lots of blobs in the middle which are really old state or the state they already have been deleted do you remember there was this attack on 2016 where there's lots of empty accounts been created and then subsequently cleared up by after the last furious drug and hard work and that situation created a lot of empty accounts and that would slow down my queries because there will be lots of things in between and and I had to basically walk through all of them to

just collect the current state so what I really need I need a database which allows me to do the key ordering but also temporal element into it so I started to look at the papers and I found that there are papers on it which is like the first one which I quite like this the from 1996 and I think it's probably implemented the sound products like Oracle or Terra data or Microsoft SQL Server but I haven't found open source implementations yet and probably I want and then there's other improvements on this it's like how do you do bulk updates and this multiple multi version trees so and to give you a quick idea but what is the difference

between the usual beech tree so this is a usual bee tree so the idea is that you've got these pages which are normally like four kilobytes long and they usually match the the amount of data you like that the minimum amount of data you read or write to the disk like four kilobytes even if you want one but you still operate in chunks of four kilobytes and so all the values are stored in the leaves of this tree and these keys are they work as a guides so you can know which page to descend to when you're looking for a specific key right and because they all together it gives you a very nice locality and plays very nicely with the blog devices like

disks plays very nicely with the with the hi cassia's on the cpu and in fact the interesting bit about it there used to be another tree structure called tea tree which is basically like a bee tree were but optimized for memory but then with the modern computer architecture bee tree actually outperforms that tea tree because of the locality so now the multi version bit trees are slightly different because for each key well which key or each key value you also have timestamp when it comes in and timestamp when it goes out or in the star if means that its current so my idea is essentially trying to implement

this based on that paper on the first paper I had before so I started doing this already but let's see how it goes so my hope is it's going to improve the the whole query even further and now let's say look at the status I'm really happy about this first line so finally after let's say two months of work I managed to get the turbo gift not just sync to the main net but also stay synced it basically follows the tip of the chain for the last 60 hours now without break and and now another interesting thing it does it's actually it has some slight side effect because Trueba guest does not support like a bra

it cannot like guess for example if it gets conflicting blocks it tries to execute them all just in case somebody starts building on top of those blocks so in trouble yes I cannot do that I have to decide all the time which is the current block in the canonical chain so I have to keep reworking but that means that I have to keep all the ankles in the beta base so it doesn't actually take a lot of space because all the ankles still have a proof work so it's actually hard to produce them but it gives me a nice history on all the ankles that were ever propagated around the network and what one thing I started to see in it last couple of days that there are sometimes really deep reorg slike ten blocks deep or 15 blocks deep

which is kind of surprising to me and a next thing I will do is I will look at into this ankle history and see which miner is producing those and blocks maybe they've fallen behind and another and this is where remember in the beginning I said my assumption was that the performance problem is due to the state access but now I start questioning assumption maybe the problem is not like not only that maybe the bigger problem is the the peer-to-peer networks itself is actually quite unstable maybe the peers are kicking each other all the time and disconnecting and reconnecting and maybe the the download protocols are slightly incompatible with each other and that and that that generates this big reworks and Network

kind of been really behaving really unhealthily an unco rates spiking maybe that's the reason so I'm gonna be looking at that much more closely in the next couple of weeks few weeks and but apart from that about fix or our pcs hopefully there will be much faster than that guess and then I will listen to some early adopters I will not do it to general public because simply I will not be able to provide adequate support to the general public but I will be able to provide support to some early adopters who well there are some already some organizations and people who want to do that they just want to run this node and see how it goes and then I want to

support we test test which is another which is the something which is coming out of the Syrian foundation is the we tree is working on this essentially retested is the is the you need to add like a five new RPC request to the gate to the theorem node and that allows you to run all the state tests which already exist directly on your note that because at the woman the state tests are running through cpp c++ the theorem as a proxy client and they did not directly run on the on the other implementation so supporting retested would allow me to run the state tests on der began and hopefully that will be easily portable

back to guest as well and i'm gonna look into hi i'm not very full like i looked at the code yet but not really familiar with this yes and in maybe in the version to version 3 if I ever get somewhere with MV BT which is multi version v3 I might swap the database so there will be no backwards compatibility and that's it