Automatic checkpointing and partial rollback in software transaction memory

摘要

While speculatively executing a given one of a plurality of transactions concurrently executing on a computer, carry out write operations in a local data block, and automatically create an entry in a checkpoint log when reading from a shared memory. Continuously conflict check during read and tentative commit operations, and carry out a partial rollback upon detection of a conflict. The partial rollback is based upon the checkpoint log.

主权项

1. A method comprising:
while speculatively executing a given one of a plurality of transactions concurrently executing on a computer, wherein the plurality of transactions share multiple objects:
carrying out write operations for the given transaction in a local data block of the given transaction;automatically creating an entry in a checkpoint log at a given time stamp upon a determination that a conflict probability with a given shared object is greater than a threshold value, and cancelling an automatic creation of the entry in the checkpoint log upon a determination that the conflict probability with the given shared object is less than the threshold value, wherein said automatically creating the entry comprises:
determining whether the given one of the multiple shared objects exists in the local data block of the given transaction at the given time stamp;reading the value of the given shared object from a shared memory associated with the plurality of transactions if the given shared object does not exist in the local data block of the given transaction at the given time stamp;writing the value of the given shared object at the local data block of the given transaction at the given time stamp; andcreating the entry in the checkpoint log to identify (i) the given shared object and (ii) the local data block of the given transaction at the given time stamp;continuously conflict checking during read and tentative commit operations;upon a determination that no conflict is detected in the read operation:
reading locally if data to be read is in the local data block,if the data to be read is not in the local data block, reading from a shared object store if the data to be read is in the shared object store and is in sync with the shared memory; andotherwise reading the data to be read from the shared memory;upon a determination that no conflict is detected in the tentative commit operation:
writing appropriate shared objects to the shared memory to obtain updated shared objects;creating a new entry in a conflict events store;subsequent to the writing of the appropriate shared objects, for each transaction in an active reader list of the updated shared objects, setting status flags to a red condition and redirecting conflict pointers to the new entry in the conflict events store; andremoving the given one of the transactions from a global active transactions list;carrying out a partial rollback upon detection of a conflict event in the conflict checking step, the partial rollback being based upon the checkpoint log, wherein carrying out a partial rollback comprises:
identifying, in the checkpoint log, a safest checkpoint to roll back to wherein the safest checkpoint is an earliest log entry pertaining to a given one of the multiple shared objects in a write set of the conflict event;applying a continuation of the safest checkpoint;resetting a status flag of the given one of the transactions to a green condition; andproceeding with speculatively executing the given one of a plurality of transactions concurrently executing on a computer from the safest checkpoint.