Realistic maximum size of merkle trie

[faustbrian]

So I'm planning to use the merkle-patricia-tree package with the CheckpointTrie to mutate and commit the state of my application. There will be millions of accounts, each which will be somewhere around 5kb large if all information is filled out and stored.

My question is if there are any limitations other than memory usage, like reaching N records or X size and the mutations then becoming slow even if they haven't been committed yet. I also assume that copying the root from one tree to another will require available memory in the size of the root?

[jochem-brouwer]

I'm not entirely sure if I understand the question but this might help:

The tree will get slower and slower over time once the tree gets bigger. The reason for this is that on an empty trie, you can immediately write a key/value. This only hits the disk once. However, if the tree grows bigger, then more disk reads/writes have to be done. Assuming you are using 32 bytes for keys, the max depth of the tree will be 64, so this means that once you are writing these accounts, then the disk has to be read/written 64 times.

If you have two trees with a different root, and the MPT points to the same DB, then "copying" the root from one tree to the other is a single operation: you can immediately switch to the other database by just setting the root. So this does not need much memory at all.

You might want to give this a read to get a deeper technical understanding: https://eth.wiki/fundamentals/patricia-tree

[faustbrian]

I guess my question is up to which point or amount of data it is feasible to rely on a single MPT as the primary storage for your application. I know that Ethereum has a state MPT in which it stores all account states and it has a storageRoot on each account which is the root of another MPT but what's stored in that other MPT? Does each account have its own MPT and on-disk file to avoid that the global state MPT becomes insanely large?

[jochem-brouwer]

storageRoot is a trie which contains the storage slots and values of the contract. For instance, your ERC20 token balance is stored there. Each account has its own storage trie. But, if the storage tries are equal (the root is the same) then it is only saved once on disk. To read these storages you thus have a MPT which points to the same DB and you set the root to the storage root in order to read it.

[holgerd77]

Just to phrase this differently, not sure if it became already clear: so when the Trie changes - e.g. by a block being run in the VM and then persisted by a commit trigger - all the nodes who are affected get updated and safed to disk. At this point you basically have two versions of this trie in the one database. The one before the commit and the one after. You then switch between these two tries by just setting to the state root which corresponds to either Trie 1 or Trie 2. Nothing else. All the relevant nodes are then derived from the respective state roots by following down the paths to the Trie leafs.

This goes on and on, so at some point you have got several (a lot) of Tries (Trie versions) in the same database. Of course the DB is therefore also growing accordingly.

We do not have completely tested the limits I guess how long this is feasible within our current tech setup/framing. Jochem and Gajinder are working on a snap sync implementation for the client, see #1848. This will bring us a lot closer to a mainnet run/test, we'll see what our Trie implementation will do under "mainnet conditions", so with a full-grown mainnet trie state. 🙂

[faustbrian]

Is the plan to test before the breaking change releases to make any necessary changes in terms of performance if needed?

[holgerd77]

No, no plans on that. We haven't done any structural changes on the Trie library (apart from your refactor, but that shouldn't impact performance along LevelDB usage I would very much assume). So no need to dedicatedly test here (what wouldn't mean that it is very welcome to improve Trie performance over time, just not related with the breaking release round).

Also to clarify: we are very late in the process, so we have - basically - a feature freeze now. Your changes were more or less the last (new ones, there is some stuff which is still WIP) which still made it in.