Path-based global cache

[rjl493456442]

Mulversion cache

Geth uses a tree structure to manage various state transitions, effectively addressing the frequent mini-reorganizations on the Ethereum mainnet. Each transition's position in the tree is determined by its original and resulting states. Additionally, each original state can have multiple "children," representing branches of state transitions.

Due to this tree-like architecture, data retrieval in a specific state (e.g., within the state of root x) typically involves traversing multiple state layers from the target state back to the common base state. According to our benchmark data, 50% data retrieval on the Ethereum mainnet requires approximately 7 layer iterations, while 25% data retrieval requires about 35 layer iterations.

State snapshot uses a bloom filter to bypass unnecessary layer iterations, thereby mitigating the associated overhead. @will-2012 has proposed a hash-based global cache to further reduce layer iterations.

Given that state snapshot does not use data hashes as lookup identifiers, and node hashes might be deprecated once Verkle trees are activated, hash-based global cache might be non-compatible in the future. I propose an alternative method to build this global cache.

---

In this proposal, the data path serves as the key in the global cache. Specifically, for state snapshot, the key will be either a 32-byte account identifier or a 64-byte storage slot identifier. For pathdb, the key will be the node path.

The value stored in the global cache will be a list of records. Each record includes: (a) associated layer metadata such as ID and state root; and (b) the corresponding data blob. These records are sorted in ascending order based on their layer ID.

When data retrieval happens, the global cache will be checked first. If it's hit in the cache, then the corresponding data could be resolved without traversing state layers. Specifically, we need to find the record with the highest layer ID (these records are sorted) where the layer ID is not greater than that of the target state. The corresponding data is the data that needs to be resolved.

For example, if we want to retrieve the data with path X in state C, then the record with id=2 should be located and m_2 is returned.

+---------------+          +--------------+          +--------------+          +--------------+
|               |          |              |          |              |          |              |
|  Common Base  | ------>  |    Layer A   | ------>  |    Layer B   | ------>  |    Layer C   |
|     (id=0)    |          |     (id=1)   |          |     (id=2)   |          |     (id=3)   |
+---------------+          +---- ---------+          +---- ---------+          +---- ---------+
                                                                                               
                                                                                               
+--------------+                                                                               
|              |     Path:     X                                                               
| Global Cache |     Records: [{id=0, data=m_1}, {id=2, data=m_2}]                             
|              |                                                                               
+--------------+                                                                               
                                                                                                                                                                                   

---

As previously noted, numerous state branches can result from mini-reorg. Consequently, it's possible to have multiple layers with the same ID. To manage these state branches effectively, an additional structure is necessary.

This structure primarily maps each state to all its descendants. For instance, the mappings maintained include:

A:  [B, C]
B:  [C]
C:  null
A': [B']
B': null

+---------------+          +--------------+          +--------------+          +--------------+
|               |          |              |          |              |          |              |
|  Common Base  | ------>  |    Layer A   | ------>  |    Layer B   | ------>  |    Layer C   |
|     (id=0)    |          |     (id=1)   |          |     (id=2)   |          |     (id=3)   |
+---------------+          +---- ---------+          +---- ---------+          +---- ---------+
                 \                                                                             
                  -\                                                                           
                    -\    +--------------+          +--------------+                           
                      -\  |              |          |              |                           
                        > |    Layer A'  | ------>  |    Layer B'  |                           
                          |     (id=1)   |          |     (id=2)   |                           
                          +---- ---------+          +---- ---------+                           
                                                                                               
  +--------------+                                                                             
  |              |     Path:     X                                                             
  | Global Cache |     Records: [{id=0, root=A, data=m_1}, {id=2, root=B', data=m_2}]          
  |              |                                                                             
  +--------------+                                            

Again, when retrieving data for path X in state C, the first record that satisfies the conditions is found as {id=2, root=B', data=m_2}. Subsequently, by checking additional mappings, we determine that C is not a descendant of B', so this record is filtered out. The next qualifying record is {id=0, root=A, data=m_1}, where it is confirmed that C is indeed a descendant of A. Thus, the corresponding data m_1 is returned.

Managing the extra mappings is relatively straightforward.

When a new layer is created, it may potentially interact with all existing layers if they belong to the same branch. Fortunately, this procedure can be executed concurrently with layer creation.

When an old layer is merged into the bottom disk layer (layer deletion), we just need to discard the corresponding mapping.

[will-2012]

#30073 This is the draft implementation, It is appreciated that any comments and feedback from the community.

[holiman]

I associate the term cache with with something that is essentially a leaky bucket: it may hold it, but may drop it at any point. First I thought that this was not the case here, but as long as we drop the entire list of records, and not just parts of it, that should be fine, right?

The 'slack' that you want to pick up, is the state snapshot data which resides in the non-top layers, but also not in the disklayer?

State snapshot uses a bloom filter to bypass unnecessary layer iterations,

I'm not sure about the idea here. Any/all misses will not only iterate, but obtain an even longer path-to-failure. And hits that would have been pretty fast will be slightly faster, at the cost of whatever memory size we allow it. Do you propose to remove the bloom filters?