Info on State Prefetching

[jon-chuang]

Dear Geth Team,

I am currently looking into some optimisations to Geth related to parallelism, state fetching and snapshots as part of my work on the downstream celo-blockchain.

Although it is not a priority, I think there is a chance that some work done could end up being merged upstream. Even if not, I think it is still a good idea to start a conversation.

I have a number of questions:

1. Is it correct to say as of now no actual optimisations exist based on the Berlin activated AccessList in terms of Trie (i.e. DB warming) or even snapshot object prefetching? What are the team’s plans for such things going forward? More generally, is there some sort of roadmap capturing planned features or are these only captured ephemerally in discussions/issues?
2. Somewhat relatedly, is it correct to say that the core/state_prefetcher.go code is outdated in the sense that one would not like to call TransitionDB in advance to warm the state, as it is costly, what’s more, in parallel? What is the (future) purpose of this code since it’s currently not invoked anywhere as far as I can tell? Is the future for this code to morph into DB prefetching based on AccessList? If so, what would be a good entry point to spawning the prefetching?
3. Why is it that the TriePrefetcher that lives in the StateDB uses one go worker per state root to walk the Trie? This seems inefficient to me, and in my mind, one should spawn as many goroutines as there are trie.TryGets to be walked. In my mind, one ought to maintain a hashmap of Tries and pop tasks off a global task list and spawn as many goroutines as there are tasks. The global prefetcher loop will then respond to stop commands.. This way, one can leverage concurrency for Trie prefetching even within a single contract’s state Trie. Since disk fetch >> goroutine context switch, I think this is a reasonable change. Since this is a relatively isolated change, I guess I could submit a PR here to familiarise with the contribution process on geth. I guess I’ll make an issue first. One question is whether it is preferable to maintain copies of Tries per thread (since this is rather lightweight - just a pointer to a global? Database and the root node). Further, if the intention is to warm the underlying DB, there is not much reason (apart, perhaps, for convenience) to continue to maintain the Tries in memory, is there? In essence, one can request for the Tries anew from the Database from a separate location after deleting the corresponding prefetcher Trie object in memory, as long as one is maintaining a single global Database object.

Cheers,
Jon

[holiman]

Is it correct to say as of now no actual optimisations exist based on the Berlin activated AccessList in terms of Trie (i.e. DB warming) or even snapshot object prefetching? What are the team’s plans for such things going forward? More generally, is there some sort of roadmap capturing planned features or are these only captured ephemerally in discussions/issues?

There are currently no such optimizations, correct. I also don't think anyone is working on adding such optimizations -- note, the access lists are not expected to be used by 'mainstream' users anytime soon. If that changes, and they start becoming more common, then it might be worth looking into properly.

Somewhat relatedly, is it correct to say that the core/state_prefetcher.go code is outdated

Yes, I'd say so. That prefetcher is only active when you are catchiing up, and have future blocks already downloaded. We've discussed removing it several times, it may just cause problems due to high IO.

The core/state/trie_prefetcher is a better approach, where we resolve the trie based on what we're going to write. It works in all modes of operation, not just when catching up. Look into that for more details on how it works -- you can also read up some more info here: #21047

Why is it that the TriePrefetcher that lives in the StateDB uses one go worker per state root to walk the Trie?

IIUC, you mean that we would load tries into one trie concurrently? AFAIK the trie is not safe to be used like this. The trie is concurrency-safe in the sense that any time it resolves something, it creates new nodes "on the way up" and you get a new root element. But your idea would be, as I understand it, to insert two things at the same time into the trie, which I don't think will work.

I guess one could build a new trie structure. At one point, I PR:ed a 'batch-mode' for the trie, in which I just updated the nodes in place without replacing them. That would make it possible to insert several things at once, as long as they operated on different subpaths in the trie. Maybe. It's not a trivial problem, feel free to see if you can sketch something up.

Further, if the intention is to warm the underlying DB, there is not much reason (apart, perhaps, for convenience) to continue to maintain the Tries in memory, is there?

No, the idea is not to just warm the db, but to actually hand out a fully expanded trie to the caller.

[jon-chuang]

Hi @holiman , thank for the very detailed and quick reply!

Some replies and more questions:

1. Am I right to say that as of now, all Tries one expects to encounter are in fact SecureTries?

2. TryGet mutates state iff trie.root.(type) == HashNode or n.Children[key[pos]] = newnode. However, in the former, this branch is defensive programming and is never invoked since core/state/database.OpenTrie -> trie.NewSecure -> trie.New sets Trie.root to a resolved node.

3. No, the idea is not to just warm the db, but to actually hand out a fully expanded trie to the caller.

Ok, I agree here. trie.Database actually has a lot of state. Nonetheless, Trie and SecureTrie themselves are essentially stateless wrappers (apart from some key hash cacheing and ...metrics - on number of leaf inserts, not relevant to our read-only use-case). Furthermore, in the comment description of trie.Database

// Note, the trie Database is **not** thread safe in its mutations, but it **is**
// thread safe in providing individual, independent node access.

So calling Trie.TryGet concurrently, the only method called in triePrefetcher ought not to be a problem. One maintains a reference in each goroutine worker to a given Trie living in a map that lives in the global TriePrefetcher and calls TryGet from it concurrently.

EDIT: So I think the comment is false. If one mutates the in-memory Trie by modifying the children, then a race condition occurs wherein only the fetches made by the last of n threads to pop off node objects off its call stack and clone and modify them in the event of didResolve would persist in memory, while the other "branch" would wither and be GCed. What I don't understand is why the modification cannot be performed in place (this would avoid the copy race condition issues by having multiple threads always mutate separate fields). The copy itself solves no problems. We merely need to edit the function to distinguish when the child node is a HashNode, and when the entire call didResolve (actually, we never need to propagate this all the way upwards, seems like a mistake).

However, this still does not make it "safe" because if we ever modify a node by having two threads write to the same location, they are writing two different pieces of data, that being two nodes in memory possibly resolved separately. Notice barring this, TryGets of two separate Trie keys will always result in nonoverlapping updates to children pointers in a single FullNode. This indicates that to solve this problem, one merely needs to ensure that the call stack of every thread references the same nodes in memory. The problem is that currently, walking from the root would result in "stale" parents who don't yet know that a child HashNode has been resolved.

The solution to the problem is to lock the parent node's pointer to the child node, whenever a child is a HashNode. Then, once ResolveHash has been resolved, secondary threads waiting for a parent node would gain access to the in-memory child node.

EDIT: Ok, so I finally understood your point.

4. Some "obvious" optimisations:
   a. parallelise core/state/statedb.IntermediateRoot: both StateObject.UpdateRoot -> Trie.TryUpdate/TryDelete and StateObject.CommitTrie(s.db) write to memory via commiting to the expanded Trie and writing the updated Trie to the in-memory trie.Database respectively, and these can each be parallelised, I think. This ought to improve commit (as seen to be non-trivial - 14.5ms avg v.s. execution with lion's share of ~38.5ms - in a bench in the PR you linked) depending on available cores. However, I have some questions about the benchmarks. What do commit, account-commit and storage-commit refer to specifically?

As for parallelising account commits, I have a TODO: identify possible parallelism/batching when writing to trie.Database.

5. From what I understand, trie.Database flushes to disk based on a memory cap? However, I can't seem to find where trie.Database.Cap is actually called.

[jon-chuang]

So, in case I was a little too slow in understanding your comment, my main question now, @holiman is whether you think adding a mutex to NodeFlag would be acceptable. Possibly this could lead to concurrent Trie updates too. But unclear to me how useful this is.

Instead of handling the HashNode case via recursion, we check while in the parent node if the child has type HashNode (trivial), if so, lock the parent and resolve the HashNode, and immediately modify the child pointer, atomically. So we never have to call tryGet with first arg of type HashNode.

Alternatively, the mutex would be in HashNode, and we check if it has been locked. If so, we wait until it unlocks, at which point the child pointer would now be pointing to the resolved node. The latter solution is a minimal solution that is limited to hash resolution.

An alternate lock-free way of solving this particular problem is to develop a concurrent HashResolver service. The service spawns goroutines to run trie.Database.node and maintains a map[Hash] node for resolved nodes and map[Hash] struct {} for nodes it is looking for. A worker running tryGet queries the global HashResolver for a node. If it is not available, it goes to sleep. This way, we ensure a single global state as managed via the HashMap. If we ensure that no nodes are copied and that all nodes are spawned via the HashResolver, then there is a single source of truth for the state of the nodes. Unlike the above solution using mutex, however, we can't ensure that state can be mutated concurrently, only that there is a single resolution of every hash to an object in memory.

My rationale for exploring the Trie-level prefetch concurrency is if txs are dominated by a single contract like an ERC-20 (and also to better prefetch the account Trie). Since this is as far as I can tell not the situation for ETH TXs, it's unclear how much the bench that I linked above reflects the lack of a need for such a workload.