Reconsider ImmutableDB caching and iterator prefetch

## Context

When reading a single block or streaming blocks from the ImmutableDB, we first read from the primary index to see whether the slot is filled or not, and at which offset in the secondary index we can find the information about the block in that slot. Next, we read the corresponding *entry* from the secondary index to find out at what offset in the chunk file we can find the block. The secondary index entry also contains the hash, the header offset, the header size, the checksum of the block, ... After getting the offset and size of the block in the chunk file, we can finally read the block from disk.

When opening an iterator, we first need to check whether the bounds (two `Point`s) are correct, i.e., do the blocks in those slots have the expected hashes? After that, we read all secondary index entries starting from the lower bound up to the last secondary index entry of the chunk or up to the upper bound, whichever comes first, into memory and use them as the state of the iterator. This makes advancing the iterator cheap, just get the first entry from the in-memory list, read the block from the chunk file at the offset in the entry, and replace the list with the tail. When the end of the list is reached and we haven't reached the upper bound yet, we read the entire next secondary index (up to the upper bound if it's in that chunk). With a secondary index entry being 56 bytes, this means an iterator stores at most ~1 MiB (21,600 * 56 bytes) in memory at once.

An iterator constantly keeps one file handle open, the handle to the chunk file it's currently streaming from. When advancing to the next chunk, two extra handles are needed (not at the same time, but sequentially): to read the next chunk's primary index and the next chunk's secondary index.

During the opening of an iterator, we read twice or even three times from the secondary index:
* To check whether the lower bound's hash is correct
* When the upper bound is in the same chunk: to check whether its hash is correct
* When reading the secondary index entries into a list that the iterator can then use for streaming

To optimise this situation, we introduced a cache of the primary and secondary indices. Whenever an index file is read, we first check whether it's in the in-memory cache, otherwise we read the requested index in its entirety and store that in the cache. This means that even if we request a single entry from a secondary index, we read and parse it in its entirety. The main reason for doing it like this is to simplify the cache: either the chunk's primary and secondary index are in memory or they're not. There are no partial indices in memory.

The current chunk's indices are always kept in memory, other chunk's indices are removed using LRU when the limit (250 chunks at the moment) is reached. Chunks that are unused for 1 minute are also removed by a background thread. Note that 250 was picked at the time so that all chunks could remain in memory, avoiding constantly having to re-read indices in worst case. However, at the moment mainnet already has 336 chunks. With each chunk taking roughly 1 MiB, the cache will take up at most 250 MiB.

The advantage of the cache is that opening an iterator with both bounds in the cache is cheap, no indices need to be read from disk. Since the `BlockFetchServer` often opens iterators within the same chunk, the cache is often hit. When a client is bulk syncing from scratch, the server will have just one cache miss per chunk. The cache is also shared across all threads, so multiple clients streaming from the same chunk will hit the cache most of the time.

### Concerns

1. **Memory usage of the cache**: the cache can take up to 250 MiB, but this does not account for fragmentation and other GHC heap overhead. I believe that you at least have to account for twice the size (because of the copying GC). So let's say 500 MiB, which is significant.
2. **Resource accounting**: the goal is to have clear resource (file handles, memory, threads) requirements per connection, see input-output-hk/ouroboros-consensus#735 and input-output-hk/ouroboros-consensus#736. The cache makes this harder:
+ A single client can potentially populate the entire cache, but many of the cached chunks will be used by other clients. How do you account for those? You could treat the entire cache as a fixed cost, but then you have to subtract its worst case memory usage from your available memory, even if only a fraction of it is used in practice.
+ If 100 clients connect at the same time, they might all request the same chunk, requiring that chunk's indices to be read, but they might also request all different chunks, requiring many more open file handles at the same time.
+ As already mentioned, each iterator keeps the secondary index entries to stream in memory (at most ~1 MiB). When these are also in the cache, they're shared, but when they have been evicted from the cache, many slow iterators might keep memory usage higher than desired. I don't think this is noticeable in practice, as we have time limits for protocols, but it does make accounting of memory usage harder.
3. **Performance**:
1. When opening an iterator with its bounds not in the cache (worst case: the bounds are in different chunks), the entire primary and secondary indices have to be read and parsed. This is significantly more work than the minimum that needs to be done before we can start streaming.
2. To *improve sync speed, what matters most is that `iteratorNext` is as fast as possible*. When receiving the request to send the next block or header, the iterator should have the bytes ready so that we can send them across the wire immediately. Currently, when the request comes in, we still have to read the block or header from disk, after which we also advance the iterator to the next entry in the list (very cheap unless switching to the next chunk and not hitting the cache for its indices). Next is making opening an iterator faster (see the previous point), so that we can serve the first request faster.
3. To improve ledger replay on startup, which also uses ImmutableDB iterators, the same insight applies: `iteratorNext` must be ready to return the decoded block so that the replay process can apply it immediately. Currently, we interleave the reading and decoding of blocks with reapplying them. Instead, we should pipeline them.

Note that it is not necessary to optimise the block reading and decoding process by, e.g., reading all blocks in the chunk at once instead of block per block, or pipelining the block reading and decoding. As long as `iteratorNext` can immediately return the block, there is not much to gain in making the other things more efficient. It might reduce the CPU load on the system, but since ledger replay is single-threaded and the node is configured to run with at least `-N2`, we shouldn't have to worry about this.

## Proposal

1. Remove the global cache of the ImmutableDB indices entirely. This solves concern 1 and 2 (partially?).
2. Instead of letting an iterator keep the list of secondary index entries to stream in memory, let it keep a handle open to the chunk's secondary index file (like it does for the chunk file already). When requesting the next block(component) with `iteratorNext`, first read the next entry from the secondary index file and then use the information in it to read the block from the chunk file.

This solves concern 2: the memory usage of an iterator is predictable and low. An iterator will have 2 file handles (chunk file and secondary index) open at all times, and a third one from time to time, when reading from the primary index.

This worsens the situation for concern 3, for a solution, see the next point.

3. To address 3.i, worsened by the above point, do some local caching when opening the iterator: when reading the lower bound's entry from the secondary chunk file, keep it in memory and use it to be able to quickly stream the first block (also see the next point).

*UPDATE:* this is caching in the sense that the entry is returned by the function checking the boundary so that we don't have to read/parse it when the iterator needs to return its first value. So just passing a value around. We could also explore adding a buffer to the file handle so that we don't have to read the same bytes again, but that is probably not needed.

Optionally: the cache can be longer-lived than the opening phase of the iterator. I.e., it can be shared across the opening of multiple iterators. This can be done similarly to how the `ResourceRegistry` is created in the `BlockFetchServer` and passed for each iterator it opens.

4. To address 3.ii and 3.iii, we can prefetch the next result of `iteratorNext`. The simplest approach is something like the following sketch:

```haskell
prefetchingIterator ::
forall m blk b.
ResourceRegistry m
-> ImmutableDB.Iterator m blk b
-> m (ImmutableDB.Iterator m blk b)
prefetchingIterator rr it = do
lookahead <- newEmptyTMVarM
prefetchThread <- forkLinkedThread rr "prefetchingIterator" $ prefetch lookahead
return ImmutableDB.Iterator {
ImmutableDB.iteratorNext = atomically $ takeTMVar lookahead
, ImmutableDB.iteratorHasNext = error "TODO"
, ImmutableDB.iteratorClose = do
-- Both operations are idempotent
cancelThread prefetchThread
ImmutableDB.iteratorClose it
}
where
prefetch :: StrictTMVar m (ImmutableDB.IteratorResult b) -> m ()
prefetch lookahead = do
next <- ImmutableDB.iteratorNext it
case next of
ImmutableDB.IteratorResult !_ -> do
atomically $ putTMVar lookahead next
prefetch lookahead
ImmutableDB.IteratorExhausted -> do
atomically $ putTMVar lookahead next
ImmutableDB.iteratorClose it
```
This can be used both for serving blocks with low latency across the network and to do some form of pipelining during ledger replay. As long as reading and decoding a block takes less time than reapplying it to the ledger or the time between incoming block requests, a `TMVar` will do. Otherwise, this can be extended to a `TBQueue` (`iteratorHasNext` will need something like `peekTBQueue`, though).

*UPDATE:* Duncan says that this won't help for serving blocks across the network. Waiting for IO blocks the capability, so we can't read the next block at the same time as sending it across the network. For ledger replay, it can help, because it happens on startup and the other capabilities are not occupied (`-N2>=`). Moreover, the parsing of the block does not involve IO. So we should only use `prefetchingIterator` for ledger replay.

Note that this means that an entire block could be kept in memory (or multiple in case of a `TBQueue`). This is still smaller than an entire secondary index and can easily be accounted for.

*UPDATE:* Duncan advised to use a `TBQueue` and to read blocks one-by-one but add them in larger batches, to reduce contention.

The nice thing about this approach is that it doesn't require any changes to the implementation of iterators in the ImmutableDB, they are still single-threaded and read entry-per-entry and block-per-block. We can even prefetch a different number of blocks for serving over the network vs. ledger replay.

If we don't want to keep the actual blocks in memory, but still want to prefetch from the secondary index, we would have to change the iterator implementation in the ImmutableDB to do the prefetching of the secondary index asynchronously. Hence my preference to just prefetch the entire block.

Final remark: we should wait until input-output-hk/ouroboros-network#2534 is merged before starting work on this.