Automatic Checkpointing and Partial Rollback in Software Transaction Memory

• US 20110029490A1
• Filed: 07/28/2009
• Published: 02/03/2011
• Est. Priority Date: 07/28/2009
• Status: Active Grant

• Current Assignee: Maplebear Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Agarwal, Shivali, Kallikote, Shyamasundar Rudrapatna, Gupta, Monika
• Granted Patent: US 9,569,254 B2
• Time in Patent Office: Days
• US Class Current: 707/684
• CPC Class Codes: G06F 11/141 for bus or memory accesses
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

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.

Claims

1. A method comprising:

while speculatively executing a given one of a plurality of transactions concurrently executing on a computer;

carrying out write operations in a local data block;

automatically creating an entry in a checkpoint log when reading from a shared memory;

continuously conflict checking during read and tentative commit operations; and

carrying out a partial rollback upon detection of a conflict in the conflict checking step, the partial rollback being based upon the checkpoint log.

2. The method of claim 1, further comprising, if 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; and

otherwise reading the data to be read from the shared memory.

3. The method of claim 1, wherein the partial rollback comprises:

identifying, in the checkpoint log, a safest checkpoint to roll back to;

applying a continuation of the safest checkpoint;

resetting a status flag of the given one of the transactions to a green condition; and

proceeding with the speculative execution at a rolled back transaction program location.

4. The method of claim 3, wherein the safest checkpoint is identified by searching the checkpoint log to locate a first log entry pertaining to a pertinent victim shared object in a write set of the conflict, and taking the first log entry pertaining to the pertinent victim shared object as the safest checkpoint to roll back to.

5. The method of claim 1, further comprising, in the tentative commit operation, if no conflict is detected:

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; and

removing the given one of the transactions from a global active transactions list.

6. The method of claim 1, further comprising:

if 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; and

otherwise reading the data to be read from the shared memory;

in the tentative commit operation, if no conflict is detected;

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; and

removing the given one of the transactions from a global active transactions list;

wherein the partial rollback comprises;

identifying, in the checkpoint log, a safest checkpoint to roll back to, by searching the checkpoint log to locate a first log entry pertaining to a pertinent victim shared object in a write set of the conflict, and taking the first log entry pertaining to the pertinent victim shared object as the safest checkpoint to roll back to;

applying a continuation of the safest checkpoint;

resetting a status flag of the given one of the transactions to a green condition; and

proceeding with the speculative execution at a rolled back transaction program location.

7. The method of claim 1, wherein the automatic creation of the entry in the checkpoint log is delayed until a predetermined number of operations can be saved by checkpoint creation.

8. The method of claim 1, wherein the automatic creation of the entry in the checkpoint log is not carried out when a conflict probability with a given shared object is less than a threshold value.

9. The method of claim 1, further comprising providing a system, wherein the system comprises distinct software modules, each of the distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the distinct software modules comprise a transaction handler module, a rollback handler module, a checkpoint generator module, and a commit handler module;

wherein;

the carrying out of the write operations is implemented by the transaction handler module executing on at least one hardware processor;

the creation of the entry in the check point log is implemented by the checkpoint generator module executing on the at least one hardware processor;

the conflict checking during the read operation is implemented by the transaction handler module executing on the at least one hardware processor;

the conflict checking during the tentative commit operation is implemented by the commit handler module executing on the at least one hardware processor;

the partial rollback is implemented by the rollback handler module executing on the at least one hardware processor.

10. A computer program product comprising a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:

computer readable program code configured to carry out write operations in a local data block, while speculatively executing a given one of a plurality of transactions concurrently executing on a computer;

computer readable program code configured to automatically create an entry in a checkpoint log when reading from a shared memory, while speculatively executing the given one of the plurality of transactions concurrently executing on the computer;

computer readable program code configured to continuously conflict check during read and tentative commit operations, while speculatively executing the given one of the plurality of transactions concurrently executing on the computer; and

computer readable program code configured to carry out a partial rollback upon detection of a conflict in the conflict checking step, while speculatively executing the given one of the plurality of transactions concurrently executing on the computer, the partial rollback being based upon the checkpoint log.

11. The computer program product of claim 10, further comprising:

computer readable program code configured to read locally if data to be read is in the local data block and no conflict is detected in the read operation;

computer readable program code configured to, if the data to be read is not in the local data block, read 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, if no conflict is detected in the read operation; and

computer readable program code configured to otherwise read the data to be read from the shared memory, if no conflict is detected in the read operation.

12. The computer program product of claim 10, wherein the partial rollback is implemented by:

computer readable program code configured to identify, in the checkpoint log, a safest checkpoint to roll back to;

computer readable program code configured to apply a continuation of the safest checkpoint;

computer readable program code configured to reset a status flag of the given one of the transactions to a green condition; and

computer readable program code configured to proceed with the speculative execution at a rolled back transaction program location.

13. The computer program product of claim 12, wherein the safest checkpoint is identified by computer readable program code configured to search the checkpoint log to locate a first log entry pertaining to a pertinent victim shared object in a write set of the conflict, and computer readable program code configured to take the first log entry pertaining to the pertinent victim shared object as the safest checkpoint to roll back to.

14. The computer program product of claim 10, further comprising distinct software modules, each of the distinct software modules being embodied on the computer-readable storage medium, the distinct software modules comprising a transaction handler module, a rollback handler module, a checkpoint generator module, and a commit handler module;

wherein;

the transaction handler module comprises the computer readable program code configured to continuously conflict check during the read operations; and

the checkpoint generator module comprises the computer readable program code configured to automatically create the entry in the checkpoint log

the commit handler module comprises the computer readable program code configured to continuously conflict check during the tentative commit operations; and

the rollback handler module comprises the computer readable program code configured to carry out the partial rollback upon detection of the conflict.

15. An apparatus comprising:

a memory; and

at least one processor, coupled to the memory, and operative to, 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;

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 in the conflict checking step, the partial rollback being based upon the checkpoint log.

16. The apparatus of claim 15, wherein the at least one processor is further operative, if no conflict is detected in the read operation, to:

read 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, read 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; and

otherwise read the data to be read from the shared memory.

17. The apparatus of claim 15, wherein the at least one processor is further operative to partially roll back by:

identifying, in the checkpoint log, a safest checkpoint to roll back to;

applying a continuation of the safest checkpoint;

resetting a status flag of the given one of the transactions to a green condition; and

proceeding with the speculative execution at a rolled back transaction program location.

18. The apparatus of claim 17, wherein the at least one processor is further operative to identify the safest checkpoint by searching the checkpoint log to locate a first log entry pertaining to a pertinent victim shared object in a write set of the conflict, and taking the first log entry pertaining to the pertinent victim shared object as the safest checkpoint to roll back to

19. The apparatus of claim 15, further comprising a computer-readable storage medium having distinct software modules embodied thereon, wherein the distinct software modules comprise a transaction handler module, a rollback handler module, a checkpoint generator module, and a commit handler module;

wherein;

the at least one processor is operative to carry out the write operations by executing the transaction handler module;

the at least one processor is operative to automatically create the entry in the checkpoint log by executing the checkpoint generator module;

the at least one processor is operative to continuously conflict check during the read and the tentative commit operations by executing the transaction handler module and the commit handler module; and

the at least one processor is operative to carry out the partial rollback by executing the rollback handler module.

20. An apparatus comprising:

means for carrying out write operations in a local data block while speculatively executing a given one of a plurality of transactions concurrently executing on a computer;

means for automatically creating an entry in a checkpoint log when reading from a shared memory, while speculatively executing the given one of the plurality of transactions concurrently executing on the computer;

means for continuously conflict checking during read and tentative commit operations, while speculatively executing the given one of the plurality of transactions concurrently executing on the computer; and

means for carrying out a partial rollback upon detection of a conflict in the conflict checking step, while speculatively executing the given one of the plurality of transactions concurrently executing on the computer, the partial rollback being based upon the checkpoint log.