Revisit LedgerDB in-memory data-structure

[edsko]

At the moment, the LedgerDB supports a "memory policy" that specifies precisely at which points we store snapshots (e.g., one at the tip, one 10 back to support short chains, and one k back, to support maximum rollback).

This strong guarantee comes with two important drawbacks however.

• Because there are gaps between these snapshots, we have to update each of them independently whenever we push a new block. Not only does this duplicate work, it also means that there can be very little sharing between them.
• We have to traverse the entire list of k elements every time we process a block. This is of no concern during normal operation, but can become a bottleneck during syncing.

Instead we should simplify the "policy" to a mere number indicating how often we want to take a snapshot, and allow snapshots to gradually get older. For example, if the state is a triple (tip, n, history) where n is a countdown to the next snapshot, the state could evolve something like

( G, 2, [])
(L1, 1, [B1])
(L2, 0, [B1, B2])
(L3, 2, [B1, B2, L3])
(L4, 1, [B1, B2, L3, B4])
(L5, 0, [B1, B2, L3, B4, B5])
(L6, 2, [B1, B2, L3, B4, B5, L6])
..

(setting the "policy" to 2). Now we get full sharing, and moreover, adding a block is just a single update to the ledger state and a single append to the history (+ a single pattern match to remove the oldest, once we reach k).

[edsko]

Closed in #1021 .