Acid transaction for distributed, versioned key-value databases

1. A database management system comprising:

one or more computing nodes, comprising one or more processors;

one or more storage devices; and

one or more memories comprising computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

transmit, in response to initiating a first transaction, a first identifier of the first transaction, the first identifier based at least in part on a first start time for the first transaction, wherein the system defers storage of a record of initiating the first transaction until a first request to modify a data element in a context of the first transaction has been received;

receive the first request to modify the data element, the first request comprising the first identifier, the first identifier indicating that the first request is associated with the first transaction;

in response to receiving the first request to modify the data element, store the record of initiating the first transaction on the one or more storage devices and add a first version of the data element to a plurality of versions of the data element stored on the one or more storage devices, the plurality of versions comprising a second version of the data element, the second version in a committed state;

receive a second request to read the data element, the second request comprising information indicative of a second start time of a second transaction; and

identify the second version of the data element, in the plurality of versions of the data element, for responding to the second request, the second version of the data element identified based at least in part on the second request being associated with a time prior to the first start time and on the second version of the data element being associated with the committed state.

2. The system of claim 1 , further comprising one or more memories comprising computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

maintain an index comprising a plurality of transaction start times, stored within version information entries, including the second start time and information indicative of the second version of the data element; and

identify the second version of the data element based at least in part on the index.

3. The system of claim 1 , further comprising one or more memories comprising computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

determine to update the first version of the data element with information indicative of a pending commit state, the determination based at least in part on an assurance that a client of the first transaction will, in response to a failed write, rollback the first transaction or retry the failed write.

4. The system of claim 1 , wherein the plurality of versions of the data element is stored on the one or more storage devices and comprises any additional versions of the data element that are known to the system.

5. The system of claim 1 , further comprising one or more memories comprising computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to:

in response to receiving information indicative of committing the first transaction, store data indicative of the first version of the data element being in a pending commit state; and

identify a conflict between a third request to read the data element, the conflict identified based at least in part on the third request being associated with a third transaction initiated subsequent to the start time of the first transaction and on the pending commit state associated with the first version of the data element.

6. A computer-implemented method comprising:

transmitting a first identifier of a first transaction, the first identifier indicative of the first transaction and comprising information based on a first time, wherein information indicative of an initiated state of the first transaction is not persisted in response to initiating the first transaction;

storing, in response to receiving a first request to modify the data element in a context of the first transaction, a first version of the data element with the information indicative of an initiated state of the first transaction, including information indicative of the first time and information indicative of an uncommitted state in the first transaction of the first version of the data element, wherein the first version of the data element is stored with a second version of the data element, the second version being in a committed state; and

processing a second request to read the data element, the second request comprising information indicative of a second transaction and a second time, wherein processing the second request comprises identifying the second version of the data element based at least in part on the second time being prior to the first time and on the second version of the data element being in the committed state.

7. The computer-implemented method of claim 6 , further comprising:

maintaining an index of a plurality of transaction start times, stored within version information entries, including the second time; and

identifying the second version of the data element based at least in part on the index.

8. The computer-implemented method of claim 6 , wherein commit time is essentially constant with respect to number of data elements modified in association with the first transaction.

9. The computer-implemented method of claim 6 , wherein the first version of the data element and the second version of the data element are stored with plurality of versions of the data element, the plurality of versions comprising any additional versions of the data element.

10. The computer-implement method of claim 9 , wherein the plurality of versions are maintained in a table structure.

11. The computer-implemented method of claim 6 , further comprising:

storing, in response to receiving information indicative of committing the first transaction, data indicative of the first version of the data element being in a pending commit state; and

identifying a conflict between a third request to read the data element, the conflict identified based at least in part on the third request being associated with a third transaction initiated subsequent to the first time and on the pending commit state associated with the first version of the data element.

12. The computer-implemented method of claim 6 , further comprising:

determining a timeout period for the first transaction, the timeout period proportional to a number of data elements modified in association with the first transaction.

13. The computer-implemented method of claim 6 , further comprising:

identifying a conflict between a third request to modify the data element, based at least in part on the first version of the data element being in the uncommitted state.

14. Anon-transitory computer-readable storage medium comprising instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to:

transmit, in response to initiating a first transaction, a first identifier of a first transaction, the first identifier indicative of the first transaction and a first time, wherein a record comprising information indicative of the first transaction having been initiated is not stored in response to initiating the first transaction;

store, in response to receiving a first request to modify the data element in a context of the first transaction, the record, and a first version of the data element with information indicative of the first time and information indicative of an uncommitted state in the first transaction of the first version of the data element, wherein the first version of the data element is stored with a second version of the data element, the second version being in a committed state; and

process a second request to read the data element, the second request comprising information indicative of a second transaction and a second time, wherein processing the second request comprises identifying the second version of the data element based at least in part on the second time being prior to the first time and on the second version of the data element being in the committed state.

15. The non-transitory computer-readable storage medium of claim 14 , comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

maintain an index of a plurality of transaction start times, stored within version information entries, including the second time; and

identify the second version of the data element based at least in part on the index.

16. The non-transitory computer-readable storage medium of claim 14 , comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

determine to update the first version of the data element with information indicative of a pending commit state, the determination based at least in part on information indicative of an assurance that a client of the first transaction will, in response to a failed write, rollback the first transaction or retry the failed write.

17. The non-transitory computer-readable storage medium of claim 14 , wherein the first version of the data element and the second version of the data element are stored with plurality of versions of the data element, the plurality of versions comprising any additional versions of the data element.

18. The non-transitory computer-readable storage medium of claim 14 , comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

store, in response to receiving information indicative of committing the first transaction, data indicative of the first version of the data element being in a pending commit state; and

identify a conflict between a third request to read the data element, the conflict identified based at least in part on the third request being associated with a third transaction initiated subsequent to the first time and on the pending commit state associated with the first version of the data element.

19. The non-transitory computer-readable storage medium of claim 14 , comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

determine a timeout period for the first transaction, the timeout period proportional to a number of data elements modified in association with the first transaction.

20. The non-transitory computer-readable storage medium of claim 14 , comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

identify a conflict between a third request to modify the data element, based at least in part on the first version of the data element being in the uncommitted state.