An article to understand the Geth client snapshot acceleration mechanism
Editor's Note: This article comes fromEthereum enthusiasts (ID: ethfans)Editor's Note: This article comes from
Ethereum enthusiasts (ID: ethfans)
Ethereum enthusiasts (ID: ethfans)
, Author: Péter Szilágyi, translation: A Jian, reprinted by Odaily with authorization.
This article is the first article in the Geth Client Answers series. You can actively ask questions about the Geth client. I will use a small article every week to answer the most voted questions. The most requested question this week is: Can you talk about the main differences between the flat database structure and the legacy structure?
State of Ethereum
Before delving into the acceleration structure (acceleration structure), let's review the concept of "state" in Ethereum and how the state is stored when it comes to different levels of abstraction.
Ethereum has two different types of state: a collection of accounts; and a collection of account slots per contract. From a completely abstract point of view, both kinds of data are key-value pairs. The account collection maps an address to that address' nonce, balance, etc. A contract's storage field maps any value (defined and used by the contract) to some value.
Unfortunately, while storing these key-value pairs as flat data can be very efficient, verifying their correctness becomes computationally difficult. Whenever the data is modified, we have to hash all the data from the bottom up.
To avoid the need to always hash the entire database, we can split the database into contiguous pieces and create a sort of tree structure! The most original and useful data is placed on the leaf nodes, and each internal node on the tree is the hash value of the content below the node. In this way, when we want to modify some value, we only need to do logarithmic number of hash operations. This kind of data structure actually has a well-known name, which is "Merkel tree".
But it's not over yet, this method is still lacking in computational complexity. Although the Merkle tree structure is very efficient when modifying existing data, if inserting and deleting data changes the boundaries of the underlying small data blocks, it will invalidate all the calculated hash values.
At this time, instead of blindly grouping the database, we can use the keys themselves to organize the data, and arrange the data into a tree-like format based on common prefixes! In this way, both insertion and deletion operations will not affect all nodes, but only the (logarithmic) nodes on the path from the root of the tree to the leaves. This data structure is called a "Patricia tree".
Combining the above two methods - the tree hierarchy of the Patricia tree and the hash algorithm of the Merkle tree - is the so-called "Merkel-Patricia tree", which is also used in practice A data structure that represents the state of Ethereum. Whether it is modification, insertion, deletion or verification, there is only logarithmic complexity! The only small exception is that some keys are hashed before insertion to balance the tries (A tiny extra is that keys are hashed before insertion to balance the tries).
Ethereum's state storage
The above explains why Ethereum uses a Merkle Patricia tree structure to store its state. Unfortunately, while the required operations are fast, each option comes with sacrifices. The logarithmic complexity of update and verify operations means that reads and storage for each individual key are logarithmic (logarithmic reads and logarithmic storage). This is because each internal node of the tree structure must be stored separately on the hard disk.
At this moment, I don't know exactly how deep the account tree is, but about a year ago, the account state filled the 7-level tree. This means that every tree operation (eg read balance, write nonce) touches at least 7-8 internal nodes and therefore does at least 7-8 persistent database accesses. LevelDB organizes data up to 7 layers, so there is an additional multiplier. The end result is that a single state access is expected to amplify to 25-50 random disk accesses. You multiply that by all the state reads and writes of all the transactions in a block, and you get a scary number.
[Of course, all client implementations try to keep the overhead as low as possible. Geth uses a larger memory area to cache several nodes; it also uses an in-memory pruning mechanism to avoid writing data to disk that will be deleted after a few blocks. But this needs another article to make it clear. ]
What's also scary is that this number is the cost of running an Ethereum node that is guaranteed to verify all states 24/7.
Can we do better?
Not all visits are created equal
The operation of Ethereum relies on cryptographic proofs of state. As long as we want to maintain the ability to verify all data, we cannot get around the problem of hard disk read and write amplification. That is, we — can and do — trust data that we have verified.
It is meaningless to repeatedly verify each state object, but if you have to verify it every time you pull data from the hard disk, you are doing such a meaningless thing. The Merkle Patricia tree structure is inherently designed for write operations, but in turn becomes a burden for read operations. We can't get rid of it, and we can't make it slim, but that doesn't mean we have to use it on every occasion.
The scenarios of Ethereum node access status can be roughly divided into the following three categories:
When importing a new block, the execution of the EVM code produces a more or less balanced number of state reads and writes. However, a block used for denial-of-service attacks may generate far more read operations than write operations.
When the node operator retrieves the state (such as calling ethcall and similar operations), the EVM code execution only generates read operations (of course there may be write operations, but the data generated by these operations will eventually be discarded and will not be persisted to inside the hard drive).
When a node is synchronizing the blockchain, the synchronizer will request the status from the remote node, and the requestee will mine the data and spread it to the synchronizer through the network.
Based on the above access patterns, many node operations can be made much faster if we can short circuit read operations without touching the state tree. This can even open up some novel access patterns (such as state iteration) that were previously too expensive to be feasible.
Of course, sacrifices are inevitable. Without removing the tree structure, any new acceleration structure will introduce additional overhead. The only question is: Does the extra overhead pay off enough to warrant a try?
please follow it
We've developed the magic Merkle Patricia tree structure to solve all our problems, and now we want to make read operations bypass it. So, what kind of acceleration structure should we use to make the read operation faster again? Obviously, if we don't need a tree structure, then we can throw all the complexity that comes with the tree structure aside, and we can go straight back to the original state.
As mentioned at the beginning of this article, in theory, the data storage method of the state of Ethereum in an ideal state should be a simple key-value pair. Without the restriction of the Merkel Patricia tree, there is nothing to stop us from To realize this ideal plan!
Not too long ago, Geth introduced the snapshot acceleration structure (not enabled by default). A snapshot is a complete view of the state of Ethereum at a given block. Abstracting away the implementation details, it simply stacks all account and contract storage slots together, represented by flat key-value pairs.
Whenever we want to access an account or a certain storage slot, we only need to pay one query operation of LevelDB, instead of querying 7-8 times on each tree. In theory, updating the snapshot is also very simple. After processing a block, we only need to do 1 additional LevelDB write operation for each storage slot to be updated.
The snapshot acceleration structure actually reduces the complexity of read operations from O(log n) to O(1) (multiplied by the overhead of LevelDB), at the cost of changing the complexity of write operations from O(log n) to O(1 + log n) (multiplied by LevelDB overhead), and increased disk storage from O(n log n) to O(n + n log n).
the devil is in the details
Maintaining the availability of Ethereum state snapshots is also not easy. As long as blocks are still being produced one after the other, stacked on top of the last block, the crude way of merging the latest changes into the snapshot will work fine. However, with even a tiny blockchain reorganization (even just one block), the snapshot mechanism breaks down because undo operations are not designed at all. For flat data representation patterns, persistent writing is a one-way operation. And to make matters worse, we have no way to access older states (for example, some dApps need to access the state of 3 blocks ago; or the state of 64 blocks in fast/snap synchronization mode) .
To overcome these limitations, the Geth client snapshot consists of two parts: a persistent hard disk layer, which is a complete snapshot of the state at the old block (for example, the top 128 blocks); and an in-memory diff layer A tree of components used to collect the most recent write operations.
When processing new blocks, we don't merge these writes directly to the hard disk layer, but just create a new in-memory diff layer that contains these changes. When the diff layers inside the memory accumulate to a high enough number of layers, the bottom one starts merging updates and pushes them to the hard disk layer. When it is necessary to read a state object, we start searching from the top diff layer and go down until we find it in the diff layer or in the hard disk layer.
This data representation is very powerful and solves many problems. Because the diff layer inside the memory forms a tree, the chain reorganization within 128 blocks only needs to take out the diff layer belonging to the parent block, and then start to build. dApps and farsyncers that require older states can access the last 128 most recent states. The overhead becomes 128 mapping lookups, but the 128 in-memory lookups are several orders of magnitude faster than the 8 hard disk reads and the 4 to 5 times amplification of Level DB.
Of course, there are still many pitfalls. I won’t go into too much depth, but simply enumerate the following list:
Self-destruct (contract self-destruct operations) (and delete operations) are particularly difficult to deal with because they require short-circuiting the descent of the diff layer.
If there is a chain reorganization deeper than the persistent hard disk layer, the current snapshot will be completely discarded and regenerated. The whole set of operations is very expensive.
When the node is shut down, the diff layer in the memory needs to be persisted to the log and loaded for backup, otherwise the snapshot will be useless after restarting.
Use the lowest diff layer as an accumulator that is only flushed to disk when it exceeds a certain memory usage. This allows deduping writes to the same slot across chunks.
A read cache should be allocated for the hard disk layer so that the hard disk will not be corrupted if the contract repeatedly accesses the same old storage slot.
Use cumulative bloom filters in the in-memory diff layer to quickly detect whether state objects are likely to exist in the diff layer, or should jump directly to disk.
The original data (account address, contract storage key) is not set as the key, but the hash value of these data is used as the key to ensure that the iteration order of the snapshot is the same as that of the Merkle Patricia tree.
The time to generate the persistent hard disk layer is much longer than the time to prune the state tree window, so even the generator needs to dynamically track the operation of the chain.
Coexistence of beauty and ugliness
Geth's snapshot acceleration structure reduces the complexity of state reading by an order of magnitude. This means that read-based DoS attacks are an order of magnitude harder to launch, and ethcall calls are also an order of magnitude faster (assuming there is no CPU bottleneck).
Of course, all this is not without cost. After the initial synchronization is completed, the nodes participating in the main network need 9 to 10 hours to construct the initial snapshot (and then maintain its availability), and an additional hard disk of more than 15 GB is required.
epilogue
Where's the bad part? It took us 6 months to build up enough confidence to release the snapshot mechanism, and it's still not a default feature, it needs to be actively enabled with the --snapshot flag, and there is still some polishing work around memory usage and crash recovery to do.
All in all, we are very proud of this improvement. There was a huge amount of work involved, and it was groping in the dark, implementing everything myself and praying it would work. Another interesting thing is that the first version of leaf sync was written two and a half years ago, but it has been blocked because we lack the necessary acceleration structure to drive it.
