Background

1. The entire execution world state for Flow can be represented by a map: map[RegisterID]RegisterValue , where RegisterID is composed with Account/Key, such as “account_a/public_storage”; and RegisterValue are encoded byte slice used by FVM.
2. The transactions in each block read and write the execution world state, and executing them produces register updates.
3. In order to create a hash of the world state, all the registers are added to a mtrie, where register values are stored on leaf nodes, interim nodes are created for hashing different branches, and the hash of the root node is the hash of the world state, which act as a proof for the world state.
4. Since mtrie stores register values on leaf nodes in memory, the memory usage grows linearly to the total size of register values, which creates a scaling bottleneck.

Storehouse benefit

1. The idea of storehouse is to store register values onto disk, so that memory usage will grow much slower since only interim nodes will be stored in memory for proof generation.
2. Another benefit is that since register values are separated from the trie, reading register values will become faster, especially for hot registers. That’s because reading registers from the trie will have to traverse the trie with the hash of the register, whereas registers can be indexed in the storehouse, and querying it hit at most 1 DB query.

Storehouse Design

1. RegisterStore + RegisterlessTrie
   • The existing mtrie can be broken into two parts: RegisterStore and RegisterlessTrie.
   • RegisterStore stores all the registers and their historical values at different heights on disk.
   • RegisterlessTrie stores payload hash (register hash) only on leaf nodes in memory, which can be used to derive the same root hash as the existing mtrie that stores full register value on leaf nodes.
   • Executing transactions doesn’t need the trie. The trie is only needed for generating the proof.
2. Finalized blocks and UnFinalized Forks
   • Execution nodes have to execute blocks that have been validated even if they have not been finalized.
   • For finalized blocks, it forms a chain of blocks, for unfinalized blocks, it forms a tree of blocks, it means it contains multiple forks.
   • When indexing registers in RegisterStore, for finalized blocks, the register values can be indexed by register id and the height, and stored on disk. However, it’s hard to index register values by height for unfinalized blocks, so they have to be stored in memory.
   • In other words, RegisterStore contains two models:
     • OnDiskRegisterStore for reading register values at finalized blocks
     • InMemoryRegisterStore for reading register values at unfinalized blocks

Correctness requirement

1. Atomicity
   • Committing register values for a given block to RegisterStore should be done in a transaction, meaning either all registers are added and indexed, or nothing is added.
2. Consistency
   • Data in RegisterStore and RegisterlessTrie should be consistent
   • If RegisterStore has stored register updates for block A, then getting all registers for block A from RegisterStore, and adding them into an empty trie should produce a trie with the same root hash as the trie stored in PayloadlessStore for block A.
3. Isolation
   • Since unfinalized blocks on different forks can be executed concurrently, historical register values from conflicting forks should be isolated.
4. Durability
   • After a restart, RegisterStore should contain committed register values for finalized blocks. And RegisterlessStore contains the trie for the same block.

Write-ahead-log Design