Tiered Storage

[RodrigoVillar]

Terminology:

• MState: fast state available in memory
• SState: slow state assumed to require a disk read
• ReadFromMState: a state key permission that allows reads from MState
• ReadFromSState : a state key permission that allows reads from MState and SState

Goals

• Long-Term: we want to expand the existing five-dimension pricing structure to accommodate for n dimensions
  • By implementing this, we could add an additional dimension to differentiate reads from MState vs reads from SState (n=6)
• Medium Term: we want to differentiate pricing between reads from MState and reads from SState
• Short Term: we want to introduce a version of tiered storage which allows us to differentiate reads from MState and reads from SState

Idea

We want to implement a version of MState such that, for any state-transition function, reads are first queried against MState before querying into SState. Furthermore, if we have a cache miss, we want to load the missed KV-pair into MState and have it be persistent between blocks/transactions.

Originally, one way for implementing this was to add an additional field to vm called mState ; state transition functions would first query vm.mState prior to querying the view of the parent block. However, this introduces additional complexity such as making sure that vm.mState is synced with views and making sure that the size of vm.mState was managed. Instead of directly implementing MState ourselves, we can make the following assumptions:

• Data that was recently fetched from SState is highly likely to be kept in memory
• MState can therefore just be an abstraction of the cache/memory of the running node

With the assumptions above, the question shifts from how we can implement our own version of MState to how we can track of which data was loaded into MState. The most straightforward way to keep track of this is to etch this into values themselves. For any value, we would add a suffix representing the last time the KV-pair was loaded into MState; this suffix could be the most recent accepted block number which touched the KV-pair. This suffix would be used the following to ways:

• Permission Validation: let $b_{i}$ represent the height of the block which is touching key $k$ and let $b_j$ represent the height of the last block which touched the $k$. Let $\epsilon$ represent the maximum number of blocks we guarantee a KV-pair will be kept in MState for. If we have the following:

  $b_i - b_j \leq \epsilon$

  then this means that $k$ is still in memory and so a permission like ReadFromMState is sufficient enough here. However, if we have the following:

  $b_i - b_j > \epsilon$

  Then $k$ is not guaranteed to be in MState and so we need a permission like ReadFromSState

• Suffix Updates: for accepted blocks and for each key that we’ve read/written to, we would set the suffix of the value to the height of the accepted block

Implementation Details

Currently, logic similar to an implementation of tracking MState values can be found in the following:

• Fetcher: for a given set of transactions, f stores KV-pairs that have been loaded from persistent storage
• chain.BuildBlock(): this function also stores KV-pairs that have been loaded from persistent storage

However, these solutions are persistent only within a block; furthermore, these solutions treat ReadMState operations the same as ReadSState operations and so the fetching models described above are merely a performance optimization and do not benefit the user. In the case of Fetcher, we would ideally like to do the following:

• We would update tasks so that instead of holding database keys, tasks would hold state keys (i.e. database keys and their permissions)
• When f.runWorker() is called, we still get the KV-pair from storage. However, we then add the additional step of validating the permission specified in the state key. If the permission is sufficient, then we call f.set(). Otherwise, we return an error.

With the above, when we now call tx.preExecute() and tx.Execute() in processor, the view being passed in (tsv ) will only have the KV-pairs which tx gave permission for. To handle updating the suffixes of the values touched by $b_i$, we could query the cache of f after all transactions are executed and then update the suffixes of any values in the cache.

Side Note: Permission Piggybacking

One thing that we would need to handle is permission piggybacking; that is, in the following case:

• We have transactions $t_1, t_2$
• Both $t_1, t_2$ access some key $k$
• We have that permission(t_1, k) = ReadFromSState, permission(t_2, k) = ReadFromMState

We don’t want a case where, in either pre-execution or execution, that $t_2$ has access to k as this would imply that $t_2$ has access to data that it did not pay for.

Testing

Ideally, we would start by defining the coverage which new Fetcher unit tests should cover:

• Transactions with the correct read permissions should have full access to their requested data
• Transactions with insufficient read permissions should fail as a result of ErrNotFound

Next, we could define the additional cases that Processor unit tests would need to cover:

• For any state keys that were touched by b, their suffixes are updated to match the height of b

cc: @aaronbuchwald @darioush @tsachiherman

[aaronbuchwald]

Another alternative is to use state rent rather than recent access to determine which key-value pairs are part of MState.

[RodrigoVillar]

After a couple of passes trying to implement the writeup, one thing that can be refactored is the permission verification step.

Currently, Fetcher is responsible for one thing: grabbing KV-pairs from persistent storage/it's local cache and returning it to the caller. While we do pass in stateKeys when fetching values, Fetcher doesn't utilize any state key permissions and instead, solely works off of the database key. Therefore, making Fetcher do the permission validation logic outlined in the writeup seems like an anti-pattern as now, both Fetcher and TStateView are checking for permissions. We should instead add the permission validation logic inside TStateView.

[aaronbuchwald]

Could the Fetcher change its function signature for Fetch from Fetch(ctx context.Context, txID ids.ID, stateKeys state.Keys) error to Fetch(ctx context.Context, txID ids.ID, keys []string) error ?