Methods and apparatus to implement parallel transactions

• US 7,669,015 B2
• Filed: 06/27/2006
• Issued: 02/23/2010
• Est. Priority Date: 02/22/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Shavit, Nir N., Dice, David, Shalev, Ori
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): DARE, RYAN A
• Application Number:
  US11/475,814
• Publication Number:
  US 20070198519A1
• Time in Patent Office: 1,337 Days
• Field of Search: 711/152
• US Class Current: 711/152
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The present disclosure describes a unique way for each of multiple processes to operate in parallel using (e.g., reading, modifying, and writing to) the same shared data without causing corruption to the shared data. For example, each of multiple processes utilizes current and past data values associated with a global counter or clock for purposes of determining whether any shared variables used to produce a respective transaction outcome were modified (by another process) when executing a respective transaction. If a respective process detects that shared data used by respective process was modified during a transaction, the process can abort and retry the transaction rather than cause data corruption by storing locally maintained results associated with the transaction to a globally shared data space.

Claims

1. A method comprising:

at one or more computers,

maintaining a set of shared data utilized by multiple processes executing in parallel,

providing a globally accessible version information variable that changes over time,

for each of at least two variables stored in the set of shared data, maintaining a corresponding location to store a respective instantaneous data value associated with the globally accessible version information variable,

receiving a first query for a current data value associated with the globally accessible version information variable around a respective start time of a transaction executed by a given process of the multiple processes,

providing the current data value associated with the globally accessible version information variable to the given process,

after receiving the first query and after the start time of the transaction, receiving a second query associated with the transaction for respective version information associated with a corresponding variable read from the shared data and used to produce a respective transaction outcome associated with the transaction, the respective version information set to a respective value of the globally accessible version information variable at a time when the corresponding variable was last written to by one of the multiple processes, and

forwarding the respective version information associated with the corresponding variable enabling the given process to abort the transaction if the respective version information indicates that the corresponding variable in the set of shared data was modified by another one of the multiple processes after the respective start time of the transaction.

2. A method as in claim 1, wherein maintaining the corresponding location to store the data value associated with the globally accessible version information variable enables each of the multiple processes to identify a relative time when a corresponding variable in the set of shared data was modified.

3. A method as in claim 1 further comprising:

enabling each of the multiple processes to access a current data value of the globally accessible version information variable and write the current data value of the globally accessible version information variable to a corresponding location associated with a respective variable in the set of shared at a time when the respective variable is modified.

4. A method as in claim 1 further comprising:

enabling the multiple processes to increment the globally accessible version information variable at a commit time when a respective one of the multiple processes attempts to modify contents of shared data utilized by the multiple processes.

5. A method as in claim 1 further comprising:

for each of the at least two variables stored in the set of shared data, maintaining a corresponding location to store respective lock information indicating whether a given one of the multiple processes currently has a lock on a respective data variable in the set of shared data, presence of the lock preventing other processes from accessing the respective data variable.

6. A method as in claim 1 further comprising:

for each of at least two variables stored in the set of shared data, maintaining a corresponding location to store respective version information representing an absolute version of a respective data variable in the set of shared data.

7. A method as in claim 1 further comprising:

for each of the at least two variables stored in the set of shared data;

i) maintaining a corresponding first location to store respective lock information indicating whether a given one of the multiple processes currently has a lock on a respective data variable in the set of shared data, presence of the lock preventing other processes from accessing the respective data variable,

ii) maintaining a corresponding second location to store respective version information representing an absolute version of a respective data variable in the set of shared data, and

iii) maintaining the first corresponding location and the second corresponding location in a same word accessible by each of the multiple processes.

8. A method as in claim 1 further comprising:

enabling the multiple processes to compete and secure an exclusive lock with respect to at least one portion of the shared data to prevent other processes from modifying the at least one portion of the shared data.

9. A method as in claim 1, wherein providing the globally accessible version information variable includes enabling modification of the globally accessible version information variable each time one of the multiple processes modifies contents of the shared data.

10. A method as in claim 1 further comprising:

receiving a first query for a current data value associated with the globally accessible version information variable at a respective start time of a transaction executed by a given process of the multiple processes;

providing the current data value associated with the globally accessible version information variable to the given process around the start time of the transaction;

during a respective commit phase in which the shared data is modified after completion of the transaction by the given process, enabling the given process to;

i) obtain locks associated with each of multiple portions of the shared data;

ii) verify that version information, as recorded based on respective data values associated with the globally accessible version information variable, associated with a group of variables read from the shared data during execution of the transaction indicate that such variables were not modified by other processes during execution of the transaction by the given process.

11. A method as in claim 10 further comprising:

enabling the given process to modify the globally accessible version information variable some time after obtaining the locks associated with each of the multiple portions of shared data to notify the other processes of a respective modification to the shared data.

17. A computer system as in claim 1, wherein maintaining the corresponding location to store the data value associated with the globally accessible version information variable enables each of the multiple processes to identify a relative time when a corresponding variable in the set of shared data was modified.

12. A computer environment including a global space accessible by multiple processes, the computer environment comprising:

one or more computers configured to

maintain a set of shared data utilized by multiple processes executing in parallel,

maintain a globally accessible version information variable that changes over time,

for each of at least two variables stored in the set of shared data, maintain a corresponding location to store a respective instantaneous data value associated with the globally accessible version information variable,

receive a first query for a current data value associated with the globally accessible version information variable around a respective start time of a transaction executed by a given process of the multiple processes,

provide the current data value associated with the globally accessible version information variable to the given process,

after receiving the first query and after the start time of the transaction, receive a second query associated with the transaction for respective version information associated with a corresponding variable read from the shared data and used to produce a respective transaction outcome associated with the transaction, the respective version information set to a respective value of the globally accessible version information variable at a time when the corresponding variable was last written to by one of the multiple processes, and

forward the respective version information associated with the corresponding variable enabling the given process to abort the transaction if the respective version information indicates that the corresponding variable in the set of shared data was modified by another one of the multiple processes after the respective start time of the transaction.

13. A computer environment as in claim 12 wherein the one or more computers are further configured to:

enable each of the multiple processes to access a current data value of the globally accessible version information variable and write the current data value of the globally accessible version information variable to a corresponding location associated with a respective variable in the set of shared at a time when the respective variable is modified.

14. A computer environment as in claim 12 wherein the one or more computers are further configured to:

enable the multiple processes to increment the globally accessible version information variable at a commit time when a respective one of the multiple processes attempts to modify contents of shared data utilized by the multiple processes.

15. A computer environment as in claim 12 wherein the one or more computers are further configured to:

receive a first query for a current data value associated with the globally accessible version information variable at a respective start time of a transaction executed by a given process of the multiple processes;

provide the current data value associated with the globally accessible version information variable to the given process around the start time of the transaction;

during a respective commit phase in which the shared data is modified after completion of the transaction by the given process, enable the given process to;

i) obtain locks associated with each of multiple portions of the shared data;

ii) verify that version information, as recorded based on respective data values associated with the globally accessible version information variable, associated with a group of variables read from the shared data during execution of the transaction indicate that such variables were not modified by other processes during execution of the transaction by the given process.

16. A computer system comprising:

a processor;

a memory unit that stores instructions associated with an application executed by the processor; and

an interconnect coupling the processor and the memory unit, enabling the computer system to execute the application and perform operations of;

maintaining a set of shared data utilized by multiple processes executing in parallel,

providing a globally accessible version information variable that changes over time,

for each of at least two variables stored in the set of shared data, maintaining a corresponding location to store a respective instantaneous data value associated with the globally accessible version information variable,

receiving a first query for a current data value associated with the globally accessible version information variable around a respective start time of a transaction executed by a given process of the multiple processes,

providing the current data value associated with the globally accessible version information variable to the given process,

after receiving the first query and after the start time of the transaction, receiving a second query associated with the transaction for respective version information associated with a corresponding variable read from the shared data and used to produce a respective transaction outcome associated with the transaction, the respective version information set to a respective value of the globally accessible version information variable at a time when the corresponding variable was last written to by one of the multiple processes, and

forwarding the respective version information associated with the corresponding variable enabling the given process to abort the transaction if the respective version information indicates that the corresponding variable in the set of shared data was modified by another one of the multiple processes after the respective start time of the transaction.

18. A computer system as in claim 16 further supporting operations of:

for each of the at least two variables stored in the set of shared data;

i) maintaining a corresponding first location to store respective lock information indicating whether a given one of the multiple processes currently has a lock on a respective data variable in the set of shared data, presence of the lock preventing other processes from accessing the respective data variable,

ii) maintaining a corresponding second location to store respective version information representing an absolute version of a respective data variable in the set of shared data, and

iii) maintaining the first corresponding location and the second corresponding location in a same word accessible by each of the multiple processes.