package tezos-store

Persistent and cached generic block store

The store instantiate a cemented block store and multiple floating block stores. The floating stores serve as buffers until enough blocks have arrived. Then it performs a "cementing" (also called a "merge"). Under normal circumstances, there are two different kinds (Floating_block_store.floating_kind) of floating stores instances: a RO(read-only) and a RW(read-write). Newly arrived blocks are always pushed in the RW instance. The block lookup is first tried in RW, then RO and finally in the cement blocks.

This store also instantiates a LRU block cache to reduce the number of I/O operations. This cache is updated whenever a block is read or stored.

When a merge occurs, the RW instance is promoted as another RO' and a new RW' instance replaces it. This allows retrieving the new cycle to be cemented from RO and RO' (former RW) asynchronously and thus allowing new blocks to be stored in the newly instantiated RW store without pausing. This asynchronous merging thread, while retrieving the cycle to cement, also combines RO and RO' into a new RO'' without the cemented cycle. When the merging thread is done, the former RO and RO' instances are deleted from the disk and the new RO'' replaces them. A merging thread has to wait for the previous one to finish.

Retrieving the new cycle from RO and RO' from blocks B_start and B_end means that we must retrieve the set of blocks between them but also trim potential branches that have roots in this set. To achieve that, we iterate over RO and RO' linearly. This means that every block's predecessor in floating stores must be previously known. Either we previously encountered it in the same floating store file, either in RO if the block is in RO' or in the cemented store (see invariants below). This invariant is required to ensure minimal memory usage. The iterations done to retrieve the cycle and merge the floating stores works similarly to a stop and copy GC algorithm. It works as follows:

• We retrieve the blocks from B_end to B_start by sequentially reading predecessors.

• We instantiate a set of encountered block hashes with B_end's hash as initial value.

• We iterate sequentially over RO and RO' blocks and copy them only if their predecessors is present in the visited set, adding their hash in the process.

The result is a correct, in order and trimmed new RO floating store. A visual example of merging is given below.

The merging thread will also trigger a garbage-collection of the cemented block store w.r.t. the given history mode.

Invariants

This store is expected to respect the following invariants:

• If no merging thread is pending, two floating stores are present: a RO and a RW.

• If a merging thread is pending, there are three floating stores present: a RO, a RO' and a RW.

• Blocks may be stored twice in floating stores but only when a merging occurs (as RO'' is a subset of RO+RO'). However, blocks can be present in both the cemented and the floating store (after importing a storage snapshot as the floating block store consist in a checkpoint associated with its `max_op_ttl` blocks which were already cemented).

• For every stored block in floating stores, its predecessor is either already stored in the same floating store file, in a previous floating store file or in the cemented store.

• A merging thread does not start until the previous one has completed.

Merging example

           RO          RW

                 | C' - D' - E'   G'
              /  |               /
         A - B - | C - D - E - F - G
                 |  \
                 |    D'' - E''
                 |     \
                 |       E'''

For instance, a merging from A to C will first retrieve blocks C, B and A. Then, iterate over all the blocks in both the RO and RW files: reading first in RO, then in RW. By construction, blocks are stored after their predecessors. For example, [ A ; B ; C ; C'; D'' ; D'; D ; E ; E'' ; F ; E''' ; G' ; G ] is a valid storing sequence.

The algorithm starts iterating over this sequence and will only copy blocks for which predecessors are present in the set S of hash (initially S = { hash(C) }). Thus, for the given sequence, D'' will first be considered, S will be updated to { hash(C), hash(D) } and so on, until RO and RW are fully read.

The new RO will then be:

                G'
               /
    - D - E - F - G

    - D'' - E''
       \
        E'''

where its storing order will be correct with regards to the invariant.