Implementing clairvoyant caching

[adiabat]

From last semester, it looks like not only does clairvoyant caching have a much lower leaf miss rate than using TTLs alone, but actually that not using TTLs, and ejecting old leaves after a threshold is better than using TTLs. So we really don't want to keep using TTLs for look-ahead caching; look-behind is slightly better and doesn't need the TTL generation step, and clairvoyant is much better but with some added complexity. This thread is about how to implement that complexity!

conceptual flow

Here are the steps:

1. Go through the blockchain sequentially and build TTL data for every txo. (int for each txo)
2. Go through the TTL data sequentially and build a clairvoyant schedule (bool for each txo)
3. When serving blocks to clients during their IBD, give them the clairvoyant schedule for each txo created.
4. Reduce network traffic by omitting proofs for all cached nodes.

We've already got code for 1 and 2. 2 is currently in a separate package/binary, so a good first step is to integrate that into the rest of the code. It's a bit trickier than it sounds, as we can't do it all in one pass; we need all the TTL data before we can start to build the schedule data.

3 Seems easy enough; once we have the schedule file, when serving a block, read the correct section of the schedule file and send that over. It will be pretty small, at a few hundred bytes per block (1 bit per txo). But 3 on it's own isn't helpful; we need to get to 4, and that's harder. It's not enough to just send clients the schedule; we need to also not send them proofs for all the nodes they already know because of that schedule. There are a few ways I can think of to do this.

• Interactive: The server doesn't send any proofs when they send a block. The client must request the proof locations it needs.
• Proof schedule:
• Server side client state:

(IN PROGRESS saving this for now, will edit later)