Support ACID transactions

[kevinswiber]

Depends on #18, snapshot support.

[kevinswiber]

Potential logic flow.

1. Begin transaction.
2. Create a snapshot to use in the transaction context.
3. Allow get, put, and remove operations to occur on snapshot.
4. Track puts/removes.
5. Commit/Abort
   1. On commit, execute all puts/removes on the data files
   2. On abort, go to 7.
6. fs.fsync data files.
7. Remove snapshot.
8. End transaction.

[kesla]

For the medeadown-usecase I'm only interested in either reading data in a snapshot or putting them in one batch.

Having support for transactions would be one way to get that, but it would also mean that I'd create a snapshot everytime I'm creating a batch - even though I won't do any reads and the snapshot would be discarded directly after the batch is done.

If we were to first implement #20 and #22, together maybe they could be the base for support for full transactions?

[kevinswiber]

@kesla

Having support for transactions would be one way to get that, but it would also mean that I'd create a snapshot everytime I'm creating a batch - even though I won't do any reads and the snapshot would be discarded directly after the batch is done.

Yes. Depending on the number of entries in the keydir, this could be very little overhead. I can start mocking up the transaction API. Perhaps there can be an options object that specifies what operations are allowed on the transaction. If reads aren't allowed, we don't have to snapshot.

If we were to first implement #20 and #22, together maybe they could be the base for support for full transactions?

Yes, indeed!

[kevinswiber]

Snapshots and write batches are now in. However, I think transaction concurrency is still a barrier to ACID compliance. Might back burner this for a bit.

[kevinswiber]

Specifically, we will need write-write conflict detection. Having timestamps on keydir entries helps, but not for concurrent, overlapping writes.

When committing a transaction, we can match snapshot timestamps to keydir counterparts when running put or remove operations to ensure the key's value hasn't changed since the transaction started. However, all disk writes are asynchronous. It's possible to commit two transactions updating the same key at once. In that scenario, both transactions will have a positive match on timestamp comparison, and both will update concurrently.

We would need to track a keydir entry as dirty, indicating a write attempt is in process. Subsequent transactions with a write operation for that key can return a write conflict.

Possible tracking data structures:

[
  {
    transaction: T1,
    keys: [k1, k2, k3, k4]
  }
]

[kevinswiber]

We'll save this for post-v1.0.0 (#44).