hiero-ledger / hiero-ledger/hiero-consensus-node
More optimal memory access for Solidity structs in EVM programs
- Dominant language
- Java
- Stars
- 406
- Forks
- 226
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 210
Description
# Problem Statement
Hiero integrates the Besu EVM with the Virtual Map for data storage. Each key and value in the EVM is a 32-byte word. Hiero maps each key as a key in the Virtual Map, and each single 32-byte value is a distinct leaf in the merkle tree. Due to the way the virtual map works, these keys and values can be anywhere among the leaves of the merkle tree, in no particular order (their order is based on the order in which mutations to the merkle tree were made, not based on anything in their data). In other words, we have no data locality.
For EVM programs, this is a big problem. Smart contracts written in Solidity frequently make use of `struct`s. A `struct` in solidity is just like one in C -- it is a simple data structure for holding data. The Solidity compiler will attempt to pack multiple fields together, if possible. But a natural datatype in solidity is `uint256` -- a single 32-byte word. And this is used all over the place for token quantities and prices. For example, a DEX might have a struct like:
```
struct MarketOrder {
uint64 orderId; // A unique, monotonically incrementing orderId that comes from the same pool as all orders
address trader; // The trader that placed the order
uint256 quantity; // The number of assetTokens to buy or sell
bool buy; // Whether this is a buy or sell market order.
bool canceled; // Whether this order has been canceled
}
```
This simple struct will require 3 storage slots -- 96 bytes. Since the EVM only works on 32-byte words, and since the `trader` and `quantity` use 32 bytes each, we need another 32 bytes to store the `orderId` and the two booleans.
Everywhere in the program where this struct is loaded and used, it will require 3 random reads on our system -- three separate key/value pairs sprinkled throughout our merkle tree. When a struct like this is placed in an array, it means that each array index read actually results in three disk reads. And since disk reads are one of the bottlenecks to performance, reading this struct is very expensive. I'd like to fix that.
# Proposed Solution
The EVM thinks of the entire 2^256 address space as existing for its memory. It doesn't actually have that much memory, of course, so instead of having a single big array of this size like a traditional computer would, it stores memory in a map with the key as the address into this space and the value as a the 256-bit word at that location.
Let's divide this address space up into `segments` of some size, say, 4K (4096 bytes). Each segment is made up of 128 32-byte words. Some disk systems use 4K as the page size, so the hope was that using a similar size would give us better utilization of the underlying system. Some other size is acceptable if found to be better for performance.
When the EVM asks for the 32-byte word at some address `A`, we would take `(int) (A / 4096)` to determine which segment the data lives within, and `A mod 4096` to discover which word within that segment maps to that address. The entire segment is the leaf in the virtual map. So once we know the segment, we know the key in the virtual map from which to get the segment data. And then once we know the offset within the segment (from the mod operation), we know the word within that segment in which the data lives and we can give it to the EVM (SLOAD) or write to it (SSTORE).
If structs are stored in an array, this would make iterating the array significantly more efficient. With a single random read we would have an entire segment of the memory space which we could then trivially iterate over.
If structs are stored in a map ("mapping" in Solidity terminology), then it is highly likely the struct will be the ONLY data in the entire segment. It is also possible (although for smaller structs, unlikely) that the struct will be split across two segments. So we would prefer to not waste bytes in that segment leaf if those bytes are not being used.
We could do this by creating a new Protobuf message:
```
syntax = "proto3";
message EvmMemorySegment {
bytes word0 = 1;
bytes word1 = 2;
bytes word2 = 3;
...
bytes word126 = 127;
bytes word127 = 128;
}
```
Any word that isn't used, will be omitted from the serialized bytes. In our case where we are only using 96 bytes (or three words), only 3, we would only have between 3 and 6 bytes of waste (depending on which fields are used -- fields 1-15 only have 1 byte of overhead, all others have 2 bytes of overhead). We could easily have a switch statement based on the offset into the `EvmMemorySegement` and read from or write to the exact correct field.
Another fact worth noting is that our struct with 96 bytes are laid out in EVM virtual memory as consecutive bytes. The offset of the start of the segment is more or less seemingly random, but the subsequent bytes are consecutive.
This would be relatively trivial to implement. The biggest challenge will be data migration.
# There Be Dragons
The primary tradeoff in this design is read performance vs. blockstream utilization. Smaller leafs require more random reads. Larger leafs leave a bigger footprint in the blockstream when any data within that leaf is changed.
Let's consider two examples.
1. A struct stored in a mapping. In this case, the position of the struct in virtual EVM address space is essentially random -- that is, while deterministic, it could be anywhere. It is extremely likely that the struct will be the *only* thing stored in the memory segment (or segments if it spans two of them). In that case, when a value in the struct is updated, the impact on the block stream is minimal since the proposed protobuf encoding would squeeze out all of the unused words.
2. An array of structs can very easily fill an entire segment. If only a single value were changed in the array, then the entire affected segment would have to be written to the block stream.
Due to 2 above, we have to determine what the right tradeoff is. Do we leave things as they are with 32-byte values (the most block-stream friendly, perhaps, but the worst for random-read performance of structs) or 4K bytes (possibly very bad for block-stream utilization, but perhaps quite good for random-read performance of structs), or something in between?
Contributor guide
Assessment
This issue has not been assessed yet.