Implement True Snapshot Isolation for LevelDB

[CMCDragonkai]

Is your feature request related to a problem? Please describe.

Proper MVCC transactions make use of a snapshot that represent the state of the database. As mutations (put & delete) build up, they apply to the snapshot. This makes it easier to build up a transaction by composing procedures/functions that mutate a transaction object. It means you get read-after-write consistency within the snapshot. Where you may have an operation that depends on the state of the database. Like let's say a counter increment. But if the prior mutation to the transaction already incremented the same counter, it would be incoherent for the subsequent mutation to plus 1 to the counter thinking the counter hasn't already been incremented.

Right now leveldb already supports snapshots natively. However it's not exposed via the JS wrapper. There are pre-existing issues.

If we could have snapshot isolated transactions, it would simplify some of our algorithms here for inodes especially since we have counter increment operations that result from linking and unlinking the inodes.

Describe the solution you'd like

Have a snapshot ability for the leveldb that we can expose through our DB abstraction. Similar to the python library of leveldb: https://plyvel.readthedocs.io/en/latest/api.html#snapshot

Note that a snapshot by itself is not sufficient to provide snapshot-isolated transactions. A combination of a "mutating" snapshot and the batching object which can overlay changes on top of the leveldb database can produce snapshot-isolated transactions.

This would mean an API like:

# it's very similar to https://github.com/Level/level#dbbatch-chained-form
const t = await this.db.transaction();
t.put(...);
t.get(...); // get will get the actual value determined by the snapshot (with overlayed in-memory values)
t.del(...);
t.commit();

In fact I suspect it would be possible to just extend the Batch object to have this.

Additional context

• Snapshots Level/leveldown#486 (comment)
• http://www.bailis.org/blog/linearizability-versus-serializability/ - linearizable operations vs serializable transactions

[CMCDragonkai]

We often have dual operations one that is doX and doXOps.

The reason is that currently doXOps can be composed to batch up an atomic commit.

However with this transaction concept, it may be possible to do doX(t) where you pass a transaction in.

async function doX (t?: Transaction) {
  const f = async (t) => {
    t.put();
    t.del();
  };
  if (t == null) {
    const t = await this.db.transaction();
    f(t);
    await t.commit();
  } else {
    f(t);
  }
}

async function transact (t, f) {
  if (t == null) {
    const t = await this.db.transaction();
    const r = f(t);
    await t.commit();
    return r;
  } else {
    return f(t);
  }
}

async function doY (a: number, b: number, t?: Transaction) {
  await this.transact(t, async () => {
    // ... do stuff with t
  });
}

This should mean if you pass a transaction, it applies the operations against the transaction.

If you don't it creates its own transaction and commits to the database.

You may need to use try catch above.

This would again cut down on the number of code we have and simplify it quite a bit.

[CMCDragonkai]

So you'd need to:

1. Have a snapshot system - expose it from C++ leveldown codebase
2. An in-memory overlay layer of leveldb that satisfies the abstract-leveldown interface (something like memdown) also see: https://github.com/Level/awesome#layers (you'd have to use it like a cache, where if entries don't exist on it it fetches it from the underlying db, and you only look up put/del entries, this may be simpler if we just record key locations and make use of an ES6 Map)
3. Enable batching of operations by using the array form or the Batch class

The first one is the toughest to eventually merge into leveldown. It would be a fork of leveldown supporting this feature, and we would have to create our own "forked" bundle that bundles the forked leveldown supporting snapshots.

[CMCDragonkai]

A proper MVCC system would also include lock management centralised at the DB class which would then coordinate multiple transactions together. This would be similar to how we are currently using async-mutex to synchronise operations. You then have concurrency control introduced.

It would generalise the entire special casing of async mutexes that we are dealing with right now.

[CMCDragonkai]

In the process of solving #47 we have created our own makeshift transaction/snapshot system. It operates with read-committed isolation level.

The Transaction object doesn't maintain locks by itself, and it doesn't check locking for keys. But instead relies on the user to specify the relevant locks in the db.transaction method. So it's an "advisory transaction with read-committed snapshot isolation". I'm probably mixing up concepts to create a syncretic practical solution for our current situation.

• https://en.wikipedia.org/wiki/Isolation_(database_systems)
• https://en.wikipedia.org/wiki/Snapshot_isolation

However as a further extension, it may be possible to also incorporate:

• https://github.com/substack/level-cowdown
• https://github.com/u8sand/level-mount
• https://github.com/Level/memdown

To create an in-memory snapshot.

[CMCDragonkai]

This issue is more relevant to js-db now instead of EFS. EFS makes use of DB transactions.

[CMCDragonkai]

Issue moved to MatrixAI/js-db #4 via ZenHub