Lock-free transactional support for large-scale storage systems

摘要

Described is a reliable and efficient design for a transactional status oracle (“ReTSO”), which supports large-scale storage systems. ReTSO uses a centralized scheme and implements snapshot isolation, a property that guarantees that read operations read a consistent snapshot of the data store. The centralized scheme of ReTSO enables a lock-free commit algorithm that prevents unreleased locks of a failed transaction from blocking other transactions. Each transaction submits the identifiers of modified rows to the ReTSO, the transaction is committed only if none of the modified rows is committed by a concurrent transaction, and a log of the committed transaction is cached. To recover from failures, before a client is notified of a change, the change cached is first persisted into a write-ahead log, such that the memory state can be fully reconstructed by reading from the write-ahead log. Furthermore, ReTSO implements a lazy, auto-garbage collector hash map that reduces the number of memory accesses per request.

主权项

1. A method comprising:
maintaining a set of recent commit database rows, each comprising a commit timestamp of a committed transaction, a row identifier that identifies a row in a persistent database table, and a version identifier for the row affected by the committed transaction; receiving a first request for a starting timestamp to read a set of rows; in response to receiving the first request, generating a started timestamp; receiving a second request to commit an updated version of the set of rows; in response to receiving the second request:
for each row in the set of rows:
determining a particular row identifier for the row;if the particular row identifier is equal to a row identifier of an entry in the set of recent commit database rows, then determining whether the started timestamp is after the commit timestamp of the entry;generating a committed timestamp; andreturning the committed timestamp; wherein the method is performed by one or more computing devices.