Optimise state storage with long-term freezer database

[michaelsproul]

Description

As raised in #484 we need to do something about the duplication of state in the database. This RFC proposes to solve the problem by storing state efficiently before the last finalized checkpoint, in tables similar to those used in #484 (sequential DB keys, multiple values per key).

Design Details

This is more of a quick idea dump before I start prototyping:

• Separate "hot" and "cold" databases. Provide an abstraction that makes the distinction transparent to the user (maybe with an optional flag to say "hot only" or "cold only"). We can implement the Store trait for the abstraction wrapper, so that the hot-cold DB can be swapped in and out with the existing DB implementation.
• The wrapper over the hot and cold databases needs to keep track of the finalized checkpoint at which the database splits, so that it knows which database to check for a given state root/block root/slot.
• We don't want to "stop the world" each time we want to move things from the hot database to the cold. I think we can avoid this by running the migration in its own thread, using an algorithm something like:
  1. Copy all of the state from hot to cold, taking only temporary per-entry read/write locks on the database (allows the main thread to interleave reads)
  2. Atomically update the finalized checkpoint in the database wrapper, so that it starts to direct queries for the recently copied states to the cold database.
  3. Delete the copied entries one by one from the hot database using short-lived write locks.
     AFAICT this should prevent the main thread from observing a partial migration (which would be difficult to handle).

TODO

A few issues require a bit more thought:

• What if a finalized checkpoint is reverted, by 1/3 of validators getting slashed? If we have the wrong chain in our DB and we've deleted the other chain then we're a bit screwed. A pragmatic solution might be to lag protocol finalization by a little bit... i.e. only migrate the database once a checkpoint has other finalized checkpoints after it (but that would seem to defeat the point!)
• Exactly how do we find all the short-lived forks that can be garbage-collected once the main chain is finalized? We likely want to hook into the fork choice code, but I haven't thought about this in-depth or formulated an exact plan yet.

[paulhauner]

Sounds good! I've been thinking about this a bit and I'm totally on board!

Here's some points I've been considering:

• Having some overlap between hot/cold might be nice too (e.g., a few epochs).
  • This works well with a background process that's working over time to migrate values from hot
• Using an arbitrary, user configurable hot/cold boundary range would be useful (e.g., not just always finalized epoch).
  • User can decide if they care more about speed or disk size (e.g., a server may not care about disk size, but want fast reads).
  • Being able to move this on the fly would be appealing but only if it's low-hanging fruit, IMO.
    to cold -- it allows the process some room to lag during temporary periods of heavy-resource use.
• We do a lot of "does this block hash exist in the database" calls during block processing
  • A fairly simple solution would be to check hot, then check cold. If neither have the block, it's not there.
  • We could do better if we can pass block.slot along with block.tree_hash_root() (this is possible in block processing). In this case, we could (sometimes) know that the block is too old/young to be in the hot/cold database and do just one read.

[michaelsproul]

Yeah I'm on-board with all your points!

I think the configurable boundary point is a particularly good idea, I'll make sure the code is generic over that.

Being able to move this on the fly would be appealing but only if it's low-hanging fruit, IMO.

You mean you ask the node to switch more data into the hot/cold database while it's running? I can see how that would be useful, and doing the cold -> hot transfer could probably mirror the hot -> cold transfer quite easily.

[paulhauner]

You mean you ask the node to switch more data into the hot/cold database while it's running?

Correct! I didn't consider that we'd need to go cold -> hot. If that turns out to be complicated, I think just getting a non-dynamic system running would be a very significant improvement alone!

[michaelsproul]

I'm prototyping, so far so good...

[paulhauner]

I just had a thought, when we start syncing from some mid-chain finalized state (e.g., weak subjectivity bounary) we'll want to be able to drop blocks/state directly into the freezer (without touching the hot db).

[michaelsproul]

Yeah, with the way things are shaping up, I think syncing "middle out" from some finalized block should work well

[paulhauner]

Resolved by #508