Escrow-locking multithreaded process-pair resource manager dictionary
First Claim
1. A multiple transaction processing system, comprising:
- an escrow-locking multithreaded process-pair resource manager (PPRM) dictionary responsive to multiple concurrent transactions, the dictionary including;
a dictionary resource;
a concurrent aspect for concurrently servicing the multiple concurrent transactions, the concurrent aspect having an instance of the escrow-locking dictionary; and
a serial aspect for serializing the multiple concurrent transactions, the serial aspect having an instance of the escrow-locking dictionary;
wherein the escrow-locking dictionary allows multiple concurrent transactions of the concurrent aspect and serial transactions of the serial aspect to share the dictionary resource and to perform operations on behalf of the multiple concurrent transactions without compromising the atomic, consistent, isolated and durable (ACID) transaction properties.
4 Assignments
0 Petitions
Accused Products
Abstract
A dictionary in a distributed transaction processing system. The dictionary is implemented as an escrow-locking multithreaded process-pair resource manager (PPRM) dictionary which is produced as an escrow-locking object implemented in the context of a PPRM and inheriting its functionality. A process pair in the PPRM is responsive to multiple concurrent transactions and including a concurrent aspect, a serial aspect and an escrow-locking dictionary. The concurrent aspect is a front-end multithreaded process of the process pair for concurrently servicing the multiple concurrent transactions. The serial aspect is a single-threaded process of the process pair for serializing the multiple concurrent transaction. Each of the concurrent aspect and the serial aspect includes an instance of the escrow-locking dictionary. That is, each of the concurrent aspect and the serial aspect has it own copy of the escrow-locking dictionary and, combined, the two copies maintains an appearance of a single virtual dictionary. The escrow-locking dictionary has a dictionary resource and uses escrow-locking for allowing the multiple concurrent transactions to share the dictionary resource. As a result, the dictionary performs operations on behalf of the multiple concurrent transactions without compromising their atomic, consistent, isolated and durable (ACID) properties. Additionally, a method and a computer program product, including a computer useable medium having computer readable code embodied therein, are for providing access to the dictionary in the data processing system.
44 Citations
65 Claims
-
1. A multiple transaction processing system, comprising:
-
an escrow-locking multithreaded process-pair resource manager (PPRM) dictionary responsive to multiple concurrent transactions, the dictionary including;
a dictionary resource;
a concurrent aspect for concurrently servicing the multiple concurrent transactions, the concurrent aspect having an instance of the escrow-locking dictionary; and
a serial aspect for serializing the multiple concurrent transactions, the serial aspect having an instance of the escrow-locking dictionary;
wherein the escrow-locking dictionary allows multiple concurrent transactions of the concurrent aspect and serial transactions of the serial aspect to share the dictionary resource and to perform operations on behalf of the multiple concurrent transactions without compromising the atomic, consistent, isolated and durable (ACID) transaction properties. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
a transaction record log for holding an ordered sequence of per-transaction records for transactions that have been voted to commit, wherein the transaction record log is shared by more than one PPRM dictionary.
-
-
11. A system according to claim 1, wherein the escrow-locking multithreaded PPRM dictionary further includes:
a passivated serial aspect for maintaining a snap-shot of a state of the serial aspect between transactions, the passivated aspect being periodically updated and used for recovery.
-
12. A system according to claim 1, in which the concurrent aspect participates in each transaction to which the process pair is responsive and is configured to construct for each such transaction a per-transaction record, each per-transaction record including a time-sequenced set of input messages, output messages and determining factors, the input messages being recorded in the order in which they were received by the concurrent aspect, the output messages and determining factors being recorded in the order of being generated in response to the respective input messages.
-
13. A system according to claim 12, wherein, by retrieving the determining factors, the serial aspect is able to deterministically forward-play each of the respective transactions which, originally, were performed non-deterministically by the concurrent aspect.
-
14. A system according to claim 1, wherein the serial aspect includes a transaction record into which the serial aspect loads a per-transaction record created by the concurrent aspect for each transaction to which the process pair is responsive, the serial aspect using the per-transaction record as an input to deterministically forward-play each such transactions.
-
15. A system according to claim 1, wherein the escrow-locking produces exclusive and shared locks via methods in the escrow-locking dictionary including get-exclusive-lock, get-shared-lock, release-exclusive-lock and release-shared-lock.
-
16. A system according to claim 1, wherein the escrow-locking dictionary further includes methods and a set of exclusive and shared locked mapping connection points and of shared locked mapping connection points'"'"' dependent transactions, the methods for performing application-level operations and for providing the escrow-locking.
-
17. A system according to claim 16, wherein the methods for performing the application-level operations include lookup, insert and delete, and wherein the methods for providing the escrow-locking include methods for providing the exclusive and shared locks.
-
18. A system according to claim 1, wherein the dictionary resource includes a dictionary organizing structure, mapping connection points and dictionary entries, the mapping connection points providing a relationship between the dictionary organizing structure and the dictionary entries.
-
19. A system according to claim 18, wherein the dictionary organizing structure is formed as one of a binary tree of keys and a hash table of keys.
-
20. A system according to claim 18, wherein the dictionary entries are included in the dictionary organizing structure so that the mapping connection points are unnecessary to provide the relationship.
-
21. A system according to claim 18, wherein each of the mapping connection points includes a ‘
- before’
field and an ‘
after’
field for maintaining entry values representing dictionary entries before and after the transaction, respectively.
- before’
-
22. A data processing system for providing access to a dictionary, the data processing system operating within the framework of distributed transaction processing, the data processing system comprising:
-
one or more application programs;
at least one resource manager (RM) receiving and responding to requests from the applications, the at least one RM including as a transaction-protected resource the dictionary which is a special RM implemented as an escrow-locking multithreaded process pair resource manager (PPRM) dictionary, a process pair in the PPRM being responsive to multiple concurrent transactions and including;
a concurrent aspect which is a front-end multi threaded process of the process pair for concurrently servicing the multiple concurrent transactions;
a serial aspect which is a single-threaded process of the process pair for serializing the multiple concurrent transaction; and
an escrow-locking, dictionary, each of the concurrent aspect and the serial aspect having its own copy of the escrow-locking dictionary, the escrow-locking dictionary having a dictionary resource and using escrow-locking for allowing the multiple concurrent transactions to share the dictionary resource, the dictionary performing operations on behalf of the multiple concurrent transactions without compromising their atomic, consistent, isolated and durable (ACID) properties;
a process monitor monitoring the at least one RM, the process monitor restarting any of the at least one RM if it stops for any reason;
a transaction manager orchestrating transactions operations in response to begin transaction messages from the application programs, the transaction manager assigning a unique transaction identification to each transaction and tracking which of the at least one RM participates in each transaction; and
a log manager interacting with the transaction manager for recording transaction messages and outcomes. - View Dependent Claims (23, 24)
a processor;
an input device interacting with the processor;
an output device interacting with the processor;
a durable storage device interacting with the processor for maintaining durable data including a transaction log received via the log manager; and
a memory device interacting with the processor for performing the distributed transaction processing.
-
-
25. A method for providing access to a dictionary in a data processing system operating in a distributed transaction processing framework, the method comprising:
-
providing the dictionary in the data processing system;
providing in the dictionary exclusive and shared locking in response to access request messages;
using in the dictionary a distributed transaction processing two-phased protocol to process the access request messages;
keeping track in the dictionary of operations performed in response to the access request messages on behalf of each of one or more concurrent transactions; and
keeping track in the dictionary of dictionary entries being accessed so that conflicting operations may be blocked until a transaction that perform these operations has completed them, the escrow-locking multithreaded PPRM dictionary servicing each of the multiple concurrent transactions without compromising their atomic, consistent, isolated and durable (ACID) properties.
-
-
26. A method for providing access to a dictionary in a data processing system operating in a distributed transaction processing framework, the method comprising:
-
providing the dictionary in the data processing system, the dictionary including a concurrent aspect, a serial aspect and an escrow-locking dictionary in each of the concurrent aspect and the serial aspect;
providing in the dictionary exclusive and shared locking in response to access request messages;
using in the dictionary a distributed transaction processing two-phased commit protocol to process the access request messages;
keeping track in the dictionary of the operations performed in response of the access request messages on behalf of each of one or multiple concurrent transactions, the access request messages prompting a recording of the operations and reply messages in a per-transaction record in the order in which they are addressed by the concurrent aspect;
providing the per-transaction record for each transaction to the serial aspect, the serial aspect serializing and replaying the multiple concurrent transactions to which the concurrent aspect is responsive using as an input their respective per-transaction records; and
keeping track in the dictionary of dictionary entries being accessed so that conflicting operations may be blocked until a transaction that perform these operations has completed them, the dictionary servicing each of the multiple concurrent transactions without compromising their atomic, consistent, isolated and durable (ACID) properties. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35)
determining if a mapping connection point is exclusively locked;
determining, if it is determined that the mapping connection point is exclusively locked, whether the identified transaction owns the exclusively locked mapping connection point;
waiting for one of a time-out or a release by a different transaction of the exclusively locked mapping connection point if the exclusively locked mapping connection point is not owned by the identified transaction;
determining if the mapping connection point is shared locked;
waiting for one of a time-out or a release by a different transaction of the mapping connection point if the mapping connection point is shared locked but is not owned by the identified transaction;
asserting exclusive ownership of the mapping connection point by the identified transaction if the mapping connection point is not locked or if the mapping connection point is shared locked but the identified transaction alone is in the mapping connection point'"'"'s dependent transactions set; and
adding the mapping connection point to a set of exclusively locked mapping connection points if the mapping connection point is not locked or if the mapping connection point is shared locked but the identified transaction alone is in the mapping connection point'"'"'s dependent transactions set.
-
-
29. A method in accordance with claim 27, wherein the get-shared-lock is for providing ownership of a shared lock to an identified transaction, the get-shared-lock including:
-
determining if a mapping connection point is exclusively locked;
determining, if it is determined that the mapping connection point is exclusively locked, whether the identified transaction owns the exclusively locked mapping connection point;
waiting for one of a time-out or a release by a different transaction of the exclusively locked mapping connection point if the exclusively locked mapping connection point is not owned by the identified transaction;
adding the mapping connection point to a set of shared locked mapping connection points if the mapping connection point is not exclusively locked; and
adding the identified transaction to a mapping connection point'"'"'s dependent transactions set.
-
-
30. A method in accordance with claim 27, wherein the release-exclusive-lock is for releasing ownership of an exclusive lock by an identified transaction, the release-exclusive-lock including:
-
negating an indication of exclusive ownership by the identified transaction; and
removing the mapping connection point from the set of exclusively locked mapping connection points.
-
-
31. A method in accordance with claim 27, wherein the release-shared-lock is for releasing ownership of a shared lock by an identified transaction, the release-shared-lock including the steps of:
-
removing identified transaction from a mapping connection point'"'"'s dependent transactions set; and
removing the mapping connection point from the set of shared locked mapping connection points.
-
-
32. A method in accordance with claim 26, wherein the escrow-locking multithreaded PPRM dictionary includes an escrow-locking dictionary, the escrow-locking dictionary including a dictionary resource having a dictionary organizing structure and dictionary entries, and wherein access request messages are processed via escrow-locking dictionary methods including ‘
- lookup’
, ‘
insert’
, and ‘
delete’
.
- lookup’
-
33. A method in accordance with claim 32, wherein the ‘
- lookup’
includes;determining if an identified key is present in a dictionary organizing structure;
adding the identified key to the dictionary organizing structure if the key is not present there;
determining whether the escrow-locking PPRM dictionary is performing a transaction replay;
invoking get-shared-lock if the escrow-locking PPRM dictionary is not performing the transaction replay;
setting an entry parameter to an entry value of a dictionary entry; and
returning one of a ‘
found’ and
‘
not found’
result based on whether the dictionary entry is found or not found.
- lookup’
-
34. A method in accordance with claim 32, wherein the ‘
- insert’
includes the steps of;determining if an identified key is present in a dictionary organizing structure;
adding the identified key to the dictionary organizing structure if the key is not present there;
determining whether the escrow-locking PPRM dictionary is performing a transaction replay;
invoking get-exclusive-lock if the escrow-locking PPRM dictionary is not performing the transaction replay;
setting a ‘
before’
field of a mapping connection point to an ‘
after’
field value of the mapping connection point if the mapping connection point'"'"'s ‘
before’
field is not already set to the ‘
after’
field value of the mapping connection point; and
setting the mapping point ‘
after’
field value to an entry value of a dictionary entry being inserted.
- insert’
-
35. A method in accordance with claim 32, wherein the ‘
- delete’
includes setting a mapping connection point identified by a key to ‘
null’
.
- delete’
-
36. A method for providing access to a dictionary in a data processing system operating in a distributed transaction processing framework, the dictionary containing a plurality of dictionary entries, the method comprising:
-
providing the dictionary in the data processing system, the dictionary having a concurrent aspect and a serial aspect as a process pair;
using exclusive and shared locking in the dictionary;
keeping track in the dictionary of dictionary entries being accessed so that conflicting operations may be blocked until a transaction that perform these operations has completed them; and
executing in the dictionary a distributed transaction processing two-phased commit protocol, including;
beginning a transaction in response to a begin transaction message sent by an application to a transaction manager;
assigning a transaction-identification unique to the transaction, the transaction being thereafter identified thereby;
sending a join request message from the concurrent aspect to the transaction manager in response to a dictionary access request message received by the concurrent aspect from the application;
servicing the dictionary access request message by providing escrow-locking and creating a per-transaction record for the identified transaction;
repeating the servicing if during the identified transaction the application sends additional dictionary access request messages to the concurrent aspect;
sending from the concurrent aspect a prepare message to the serial aspect and a log request message to a log manager in response to a commit message from the application;
replaying in the serial aspect the entire identified transaction using as an input its respective per-transaction record;
sending a vote to commit message from the serial aspect to the concurrent aspect;
sending from the concurrent aspect to the transaction manager a vote to commit in response to the serial aspect'"'"'s vote to commit message;
sending a committed message from the transaction manager to the application in response to the vote to commit message from the concurrent aspect;
releasing any exclusive and shared lock associated with the identified transaction; and
committing the transaction, the identified transaction has been executed as a unit of work whose ACID (atomic, consistent, isolated and durable) properties have not been compromised while, at the same time, fulfilling the requirements of the distributed transaction processing two-phase commit protocol.
-
-
37. A computer program product having computer readable code embodied therein, configured to provide a dictionary in a data processing system operating in a distributed processing framework, comprising:
-
computer readable program code configured to provide the dictionary in the data processing system;
computer readable program code configured to provide the dictionary exclusive and shared locking in response to access request messages;
computer readable program code configured to use in the dictionary a distributed transaction processing two-phased protocol to process the access request messages;
computer readable program code configured to keep track in the dictionary of operations performed in response to the access request messages on behalf of each of one or more concurrent transactions; and
computer readable program code configured to keep track in the dictionary of dictionary entries being accessed so that conflicting operations may be blocked until a transaction that perform these operations has completed them, the escrow-locking multithreaded PPRM dictionary servicing each of the multiple concurrent transactions without compromising their atomic, consistent, isolated and durable (ACID) properties.
-
-
38. A computer program product having computer readable code embodied therein, configured to provide a dictionary in a data processing system operating in a distributed processing framework, comprising:
-
computer readable program code configured to provide the dictionary in the data processing system;
computer readable program code configured to provide in the dictionary exclusive and shared locking in response to access request messages;
computer readable program code configured to use in the dictionary a distributed transaction processing two-phased commit protocol to process the access request messages;
computer readable program code configured to provide in the dictionary a per-transaction record for each transaction to a concurrent aspect of the escrow-locking multithreaded PPRM dictionary in the dictionary, of operation and reply messages, according to the access request messages on behalf of each of one or multiple concurrent transactions in the order addressed;
computer readable program code configured to provide a per-transaction record for each transaction to a serial aspect of the escrow-locking multithreaded PPRM dictionary, the serial aspect serializing and replaying the multiple concurrent transactions to which the concurrent aspect is responsive using the per-transaction record for the concurrent transactions as an input; and
computer readable program code configured to keep track in the dictionary of dictionary entries being accessed so that conflicting operations may be blocked until a transaction that perform these operations has completed them, the dictionary servicing each of the multiple concurrent transactions without compromising their atomic, consistent, isolated and durable (ACID) properties.
-
-
39. An apparatus comprising:
-
a dictionary data structure stored on a computer readable medium, the dictionary data structure comprising a plurality of keys, a plurality of entries, and a plurality of mapping points, each key associated with one of the plurality of mapping points to provide a relationship between the key and a corresponding entry; and
a multiple transaction processing system to hold a given mapping point in an escrow-lock for a given transaction, to perform dictionary operations for multiple transactions simultaneously, and to maintain one or more transactional ACID properties of the multiple transactions. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50)
a shared state escrow-lock associated with the transaction to prevent other transactions from changing the mapping point and to allow other transactions to hold the locked mapping point; - and
a record of transactions that hold the shared state escrow-lock for the mapping point.
-
-
41. The apparatus of claim 39 wherein the escrow-lock further comprises
an exclusive state escrow-lock associated with the transaction to provide the transaction with exclusive access to the mapping point. -
42. The apparatus of claim 39, wherein the multiple transaction processing system is configured to track operations of each transaction so that conflicting operations are prevented, and so that reverse operations of each transaction can be performed during a roll-back.
-
43. The apparatus of claim 40, wherein the multiple transaction processing system is configured to track operations by tracking the mapping points that have been locked in an exclusive state by the transaction, and by tracking the mapping points that have been locked in a shared state by the transaction.
-
44. The apparatus of claim 39 wherein the multiple transaction processing system is further configured to commit changes made by the operations of a given transaction so that the changes are recorded on a durable computer readable medium.
-
45. The apparatus of claim 39 wherein the multiple transaction processing system is further configured to roll-back changes made by the operations of a given transaction so that changes made by the transaction are removed from the dictionary data structure.
-
46. The apparatus of claim 39 wherein the multiple transaction processing system is configured to process the multiple transactions in a pair of processes including
a concurrent process to process the transactions concurrently; - and
a serial process to process the transactions serially.
- and
-
47. The apparatus of claim 39 wherein one of the transactional properties comprises
an atomic property of implementing either all changes made by a given transaction, or implementing none of the changes made by the given transaction. -
48. The apparatus of claim 39 wherein one of the transactional properties comprises
a consistent property of evaluating integrity constraints and committing only if all of the integrity constraints are met. -
49. The apparatus of claim 39 wherein one of the transactional properties comprises
an isolated property to detach other transactions from changes made by a given transaction until the given transaction commits. -
50. The apparatus of claim 39 wherein one of the transactional properties comprises
a durable property to preserve a change made by a transaction.
-
51. A method of performing operations on a dictionary data structure stored on a computer readable medium, the dictionary data structure comprising a plurality of keys, a plurality of entries, and a plurality of mapping points, each key associated with one of the plurality of mapping points so that the associated mapping point provides a relationship between the key and an entry of the plurality of entries;
- the method comprising;
holding a given mapping point in an escrow-lock for a given transaction;
performing dictionary operations for multiple transactions simultaneously; and
maintaining the ACID properties of the multiple transactions. - View Dependent Claims (52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65)
associating a shared state escrow-lock with the transaction and the mapping point; preventing other transactions from changing the mapping point;
allowing other transactions to hold the locked mapping point; and
recording transactions that hold the shared state escrow-lock for the mapping point.
- the method comprising;
-
53. The method of claim 51 wherein holding further comprises
associating an exclusive state escrow-lock with the transaction and the mapping point; - and
providing the transaction with exclusive access to the mapping point.
- and
-
54. The method of claim 51 further comprising
tracking operations of each transaction; - and
preventing conflicting operations.
- and
-
55. The method of claim 54 further comprising
performing reverse operations of each transaction during a roll-back. -
56. The method of claim 51 further comprising
tracking the mapping points that have been locked in an exclusive state by the transaction; - and
tracking the mapping points that have been locked in a shared state by the transaction.
- and
-
57. The method of claim 51 further comprising
committing changes made by the operations of a given transaction so that the changes are recorded on a durable computer readable medium. -
58. The method of claim 51 further comprising
rolling-back changes made by the operations of a given transaction so that changes made by the transaction are removed. -
59. The method of claim 51 further comprising
processing the transactions concurrently; - and
processing the transactions serially.
- and
-
60. The method of claim 51 wherein one of the transactional properties comprises
an atomic property of implementing either all changes made by a given transaction, or implementing none of the changes made by the given transaction. -
61. The method of claim 51 wherein one of the transactional properties comprises
a consistent property of evaluating integrity constraints and committing only if all of the integrity constraints are met. -
62. The method of claim 51 wherein one of the transactional properties comprises
an isolated property to detach other transactions from changes made by a given transaction until the given transaction commits. -
63. The method of claim 51 wherein one of the transactional properties comprises
a durable property to preserve a change made by a transaction. -
64. The method of claim 52, wherein holding further comprises
determining that a mapping point is not exclusively locked by other transactions; -
holding the transaction in a shared state for the transaction, and adding the transaction to the record of transactions that hold the shared state for the mapping point.
-
-
65. The method of claim 53, wherein holding further comprises
determining that the mapping point is not exclusively locked; -
determining that the mapping point is not held in a shared state by other transactions; and
holding the mapping point in an exclusive lock for the transaction.
-
Specification