IndexedDB-based Fedimint Database Implementation

[elsirion]

Unfortunately IndexedDB's transaction abstraction is absolutely unusable for our purposes. The core problem is that IndexedDB transactions cannot span across await points. We can atomically write multiple values, but these writes cannot be intertwined with e.g. network requests, which Fedimint often does. This means, if we want an efficient DB for the web runtime we need to implement a transaction overlay.

Fedimint requires snapshot isolation with optimistic transactions, one possible design I wrote about elsewhere:

I think a possible way of implementing our level of isolation (I think it was snapshot isolation that we expect?) by:

• Saving each value together with its "generation". The global DB generation is defined as the max of all value generations.
• Having an index of all ongoing transactions and their start DB generation
• On commit of transactions with writes written KV pairs are updated and their generation set to DB generation + 1. If there are other transactions active the old KV pairs are written to a generation cache (together with their original generation).
• Whenever a transaction finishes (commit/abort) the generation cache is cleaned of all entries older than the minimum generation of all ongoing transactions
• When reading from a key in a transaction:
  1. Check the local transaction log for writes to the key
  2. Check the generation cache
  3. Read directly from the IndexedDB
• Commits are conflict-free if:
  • All reads before the last write read values with a generation at commit time <= the transaction generation
  • All writes write to values with a generation at commit time <= the transaction generation (deleted item generations have to be kept I guess to notice conflicts)
• Commits can use IndexedDB transactions for atomicity since the reads/writes all happen without other tasks in between.

[elsirion]

Closed by #33. It's not the same, but good enough for now.

[elsirion]

Re-opening since MemDatabase is quite broken fedimint/fedimint#3988