This draft adds a persistent storage trait that can be used to store transaction logs and read the log for recovery purposes. Work in heavy progress, because ideally the design should also allow reading versions from the storage, so that data can be spilled from memory to disk if there's not enough RAM available.

Fixes #3

The commit_tx() function needs to write to a transaction log and wait for it to persist on stable storage. Let's add a transaction log trait that mvcc-rs users can provide.

The paper has a typo, which I have confirmed with one of the authors. Since the code closely follows the paper and the bug has crept in here.

Let me explain with a diagram, following the same conventions as the paper:

1. At time 60, we observe our initial state, where the value of Larry is 170. This is a committed row.
2. At time 75, a transaction is started and is in Active state. It wants to update the value to 150, so it appended row 2
3. At time 80, another new transaction, Tx80 is started, and it wants to read the value of Larry. Both Tx75 and Tx80 are in Active state.

What is the value Tx80 going to read?

Tx80 can't see row 2 because of Table 1 rules. If Tx75 is in Active state, only Tx75 can see row 2. This makes sense because row 2 is fresh, and Tx75 might drop the changes later. We don't want any other transactions to see this row.

But can Tx80 see row 1? The rules from the paper contradict that since Tx75 is in Active state:

This is a typo, and Tx80 should be able to see row 1 since it is a committed row.

Code

This is the line which causes this bug - https://github.com/penberg/mvcc-rs/blob/44df6c/database/src/database.rs#L438

We can reproduce this error:

1. Lets first insert a new row and commit it
2. Start a new transaction te, updating this row. Let te be in active state
3. Start one more transaction tx. Let this be in the active state too. According to the code, tx won't see the committed value.

Fix

• tx should be able to see this row
• te should not see this, instead the version it is updating (e.g. row2 from the previous diagram)
• usual rules about the time ranges apply

Many database management systems implement "branching", which allows users to create a copy-on-write clones of a database. With a row manager (#20), we can make a copy of the in-memory index and bump the reference counts. This essentially gives us copy-on-write semantics with MVCC because updates create a new version rather than modify the rows in-place.

For example, let's say we have a database A and we make a clone B. Initially, they both point to the same set of rows. If either one of them updates a row, the other one will not be affected because the updating clone just marks the shared row version as deleted, but the actual row is unchanged.

As a future optimization, we could also use a copy-on-write hash table to even share the index between clones.

Implement a row manager to decouple the in-memory index represented by Database and the actual stored rows. For example, let's use a log structured memory allocator to allocate records and make RowVersion point to the LSA-backed row. With reference counting, we can now return rows from the index using zero-copy.

The current code uses a mutex to essentially make commit() and rollback() and other operations atomic. Let's switch to lockless data structures like Hekaton.