Multi-version concurrency control (MVCC) in non-volatile memory

1. A computer implemented method, comprising:

determining that an event occurred, wherein one or more write transactions to one or more records of a multi-version database that were pending prior to the event did not commit, and wherein the multi-version database is stored in a non-volatile memory;

identifying the one or more write transactions based on a commit value that was stored in the non-volatile memory prior to the event, wherein each of the one or more write transactions includes a commit value;

selecting a particular one of the identified uncommitted write transactions;

identifying, from the multi-version database, a first version of a record corresponding to the selected uncommitted write transaction, wherein the first version was not committed;

identifying an earlier version of the record that was committed prior to the event;

setting a visibility of the record to indicate that the earlier version of the record is visible and the first version of the record is not visible;

setting a delete timestamp corresponding to the first version of the record below a garbage collection threshold;

determining that the delete timestamp is part of an update operation;

adding a new version of the record corresponding to the first version of the record to the database; and

setting a commit timestamp for the new version of the record greater than the garbage collection threshold.

2. The method of claim 1 , wherein the setting the visibility comprises:

setting a delete timestamp corresponding to the earlier version of the record to indicate that the earlier version of the record is visible, wherein the visibility of a record to a transaction is based on the delete timestamp.

3. The method of claim 1 , wherein the garbage collection threshold is based on a minimum starting timestamp corresponding to a time when an oldest running transaction began.

4. The method of claim 1 , wherein the event corresponds to a computer system crash or reboot.

5. The method of claim 1 , wherein the selecting comprises:

determining that the identified transaction comprises a plurality of statements, wherein the multi-version database includes a statement identifier for each of the plurality of statements; and

identifying a first statement of the plurality of statements.

6. The method of claim 5 , wherein the statement identifier is based on a statement counter, and wherein a transaction identifier corresponding to the selected uncommitted write transaction corresponds to a transaction counter different from the statement counter.

7. A system, comprising:

a memory; and

at least one processor coupled to the memory and configured to:

determine that an event occurred, wherein one or more write transactions to one or more records of a multi-version database that were pending prior to the event did not commit, and wherein the multi-version database is stored in a non-volatile memory;

identify the one or more write transactions based on a commit value that was stored in the non-volatile memory prior to the event, wherein each of the one or more write transactions includes a commit value;

select a particular one of the identified uncommitted write transactions;

identify, from the multi-version database, a first version of a record corresponding to the selected uncommitted write transaction, wherein the first version was not committed;

identify an earlier version of the record that was committed prior to the event;

set a visibility of the record to indicate that the earlier version of the record is visible and the first version of the record is not visible;

set a delete timestamp corresponding to the first version of the record below a garbage collection threshold;

determine that the delete timestamp is part of an update operation;

add a new version of the record corresponding to the first version of the record to the database; and

set a commit timestamp for the new version of the record greater than the garbage collection threshold.

8. The system of claim 7 , wherein the processor that sets the visibility is configured to:

set a delete timestamp corresponding to the earlier version of the record to indicate that the earlier version of the record is visible, wherein the visibility of a record to a transaction is based on the delete timestamp.

9. The system of claim 7 , wherein the garbage collection threshold is based on a minimum starting timestamp corresponding to a time when an oldest running transaction began.

10. The system of claim 7 , wherein the event corresponds to a computer system crash or reboot.

11. The system of claim 7 , wherein the processor that selects is configured to:

determine that the identified transaction comprises a plurality of statements, wherein the multi-version database includes a statement identifier for each of the plurality of statements; and

identify a first statement of the plurality of statements.

12. The system of claim 11 , wherein the statement identifier is based on a statement counter, and wherein a transaction identifier corresponding to the selected uncommitted write transaction corresponds to a transaction counter different from the statement counter.

13. A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:

determining that an event occurred, wherein one or more write transactions to one or more records of a multi-version database that were pending prior to the event did not commit, and wherein the multi-version database is stored in a non-volatile memory;

identifying the one or more write transactions based on a commit value that was stored in the non-volatile memory prior to the event, wherein each of the one or more write transactions includes a commit value;

selecting a particular one of the identified uncommitted write transactions;

identifying, from the multi-version database, a first version of a record corresponding to the selected uncommitted write transaction, wherein the first version was not committed;

identifying an earlier version of the record that was committed prior to the event;

setting a visibility of the record to indicate that the earlier version of the record is visible and the first version of the record is not visible;

setting a delete timestamp corresponding to the first version of the record below a garbage collection threshold;

determining that the delete timestamp is part of an update operation;

adding a new version of the record corresponding to the first version of the record to the database; and

setting a commit timestamp for the new version of the record greater than the garbage collection threshold.

14. The device of claim 13 , wherein the setting the visibility comprises:

setting a delete timestamp corresponding to the earlier version of the record to indicate that the earlier version of the record is visible, wherein the visibility of a record to a transaction is based on the delete timestamp.

15. The device of claim 13 , wherein the garbage collection threshold is based on a minimum starting timestamp corresponding to a time when an oldest running transaction began.

16. The device of claim 13 , wherein the event corresponds to a computer system crash or reboot.

17. The device of claim 13 , wherein the one computing device configured to select is configured to perform operations comprising:

determining that the identified transaction comprises a plurality of statements, wherein the multi-version database includes a statement identifier for each of the plurality of statements; and

identifying a first statement of the plurality of statements, wherein the statement identifier is based on a statement counter, and wherein a transaction identifier corresponding to the selected uncommitted write transaction corresponds to a transaction counter different from the statement counter.