libsql / sqld

LibSQL with extended capabilities like HTTP protocol, replication, and more.
https://libsql.org
903 stars 38 forks source link

Bottomless: restore from chain of generations #638

Closed Horusiath closed 1 year ago

Horusiath commented 1 year ago

This PR enables bottomless to perform restore from a generation that may not have a database snapshot included. In general this is realised by introducing a new kind of an object (.dep, similar to other metadata objects like .changecounter used by snapshot backup and .meta used by WAL backup) which stores the dependency between current generation and its predecessor.

This allows us to create a chain of generations that may be necessary (in LIFO order) to be visited in order to restore database state. The algorithm is basically:

  1. Try to restore state from a snapshot in a generation we were asked for.
    • If restore from snapshot was ok, proceed to pt.3.
  2. If snapshot was not found check the .dep and try to get parent generation.
    • If parent generation was not found (current generation is first one), proceed to pt.3.
    • If parent was found try to stash current generation and try pt.1 for parent. (this works recursively up to 100 generations deep).
  3. Picking stashed generations one by one, try to find WAL log segments and apply them one by one. When reached the end of a current generation, pick the next stashed one. Rinse and repeat.

I've introduced the next step in bottomless test that verifies this behaviour.

This PR doesn't interfere with snapshots. They are still created on every new generation. It just allows us to fallback to previous generations in case when snapshot is not there - which will be useful once we want to postpone snapshot creation per every generation.

Horusiath commented 1 year ago

@psarna it's exactly as you've explained.

psarna commented 1 year ago

@Horusiath k, perfect, please rebase to get rid of some conflicts and I'll queue