A DbChangelog is the component of the LedgerDB implementation that responsible for:

• Maintaining the last $k$ in-memory ledger states without on-disk parks.
• Holding the in-memory ledger state that a snapshot would write to the disk.
• Providing sequences of differences from said state to any requested state in the last $k$ ledger states, which combined with the values in the BackingStore, can provide LedgerTables at any of those ledger states.

A DbChangelog is said to be anchored at a BackingStore when the slot of the values in the backing store is the predecesor of the slots in the sequence of differences, with the overall sequence of slots being defined by the blocks on the chain.

This design is based on the technical report "Storing the Cardano ledger state on disk: API design concepts" by Duncan Coutts and Douglas Wilson.

Implementation details

The DbChangelog is in fact a pure data structure, of which the LedgerDB will carry a value in some mutable state, see LedgerDBState.

Carrying states

The DbChangelog contains an instantiation of the AnchoredSeq data type to hold the last $k$ in-memory ledger states. This data type is impemented using the finger tree data structure and has the following time complexities:

• Appending a new ledger state to the end in constant time.
• Rolling back to a previous ledger state in logarithmic time.
• Looking up a past ledger state by its point in logarithmic time.

One can think of AnchoredSeq as a Seq from Data.Sequence with a custom finger tree measure allowing for efficient lookups by point, combined with an anchor. When fully saturated, the sequence will contain $k$ ledger states. In case of a complete rollback of all $k$ blocks and thus ledger states, the sequence will become empty. A ledger state is still needed, i.e., one corresponding to the most recent immutable block that cannot be rolled back. The ledger state at the anchor plays this role.

Appending in-memory states

When a new ledger state is appended to a fully saturated DbChangelog (i.e. that contains $k$ states), the ledger state at the anchor is dropped and the oldest element in the sequence becomes the new anchor, as it has become immutable. Note that we only refer here to the in-memory states, as the diffs from the anchor will remain in the DbChangelog until flushing happens. This maintains the invariant that only the last $k$ in-memory ledger states are stored, excluding the ledger state at the anchor. This means that in practice, $k + 1$ ledger states will be kept in memory. When the DbChangelog contains fewer than $k$ elements, new ones are appended without shifting the anchor until it is saturated.

Getting and appending differences

For the differences, the DbChangelog contains a SeqDiffMK (see Ouroboros.Consensus.Storage.LedgerDB.V1.DiffSeq) which in turn is just an instantiation of a root-measured finger tree (see fingertree-rm) which is a specialization of the finger trees that carries a root-measure which is the monoidal sum of all the measures of all the elements.

This allows us to very efficiently lookup the combined difference of the whole DbChangelog, while still having a good complexity when splitting this tree.

When a block is to be applied to a ledger state (which must be in the DbChangelog or application would directly fail), applying the root-measure of the sub-sequence of differences from the backing store slot up to the requested slot to the values read from the backing store will provide the LedgerTables needed for applying the block.

Once a new ledger state is appended to the DbChangelog, said ledger state will carry DiffMK tables (obtained by diffing the input and output ledger tables when calling the Ledger rules). Adding those differences to the DbChangelog is just a matter of extending the carried SeqDiffMK.

Only when flushing, the SeqDiffMK is pruned, by extracting the differences in between the last flushed state and the current immutable tip.

Applying blocks to the DbChangelog will extend it if the result is successful.

In order to do so, we first need to find the particular block, then prepare the ledger tables by hydrating the ledger state and then finally call the ledger, which might throw errors.

When trying to get tables at a specific ledger state, we must follow a process we call hydrating the ledger state. This process consists of 3 steps:

1. Rewind the requested keys to the beginning of the DbChangelog. For UTxO entries this just means that we record at which slot the db changelog was when rewinding.
2. Query the BackingStore for the actual values for the requested keys.
3. Forward those values by applying the differences in the DbChangelog up to the requested point.