JOTM 2 Documentation

See:
Description

JOTM 2 Core API

org.objectweb.jotm.core.conflict	Specifies JOTM 2 conflict management API
org.objectweb.jotm.core.delegation
org.objectweb.jotm.core.dependency
org.objectweb.jotm.core.events	Specifies JOTM 2 event model API
org.objectweb.jotm.core.log	Specifies JOTM 2 log management API
org.objectweb.jotm.core.recovery
org.objectweb.jotm.core.transaction	Specifies JOTM 2 transaction management API

JOTM 2 Core Implementation

org.objectweb.jotm.impl.core.conflict	Provides some implementations of the org.objectweb.jotm.core.conflict interfaces
org.objectweb.jotm.impl.core.log	Provides some implementations of the org.objectweb.jotm.core.log interfaces
org.objectweb.jotm.impl.core.transaction	Provides some implementations of the org.objectweb.jotm.core.transaction interfaces

Other Packages

org.objectweb.jotm.examples	Provides some JOTM 2 examples
org.objectweb.jotm.impl.ots	Provides an OTS personality implementation
org.objectweb.jotm.util	Provides some utilities

Table of Contents

1 Transaction Manager
2 Conflict Manager
3 Dependency Manager
4 Delegation Manager
5 Log Manager
6 Recovery Manager
7 Communication Manager
8 OTS personality prototype
9 Examples

1 Transaction Manager

(org.objectweb.jotm.core.transaction package)

Transaction Manager is a two-phase commit engine that is able to start and finish (i.e., commit or abort) transactions as well as register transaction participants.

A transaction participant is an object that implements the EventListener interface. Events are implementations of the TransactionalEvent interface. Transactional event listeners register to a transactional EventSource. Here is an example how it works:

    BasicTransaction tx = tm.getTransaction("twoPhaseCommit");
    EventListener a = new ResourceParticipant( );
    EventListener b = new SynchronizationParticipant();
    tx.begin();
    tx.addListener(TwoPhaseCommitEvent.TYPE_PREPARE 
                   | TwoPhaseCommitEvent.TYPE_COMMIT
                   | TwoPhaseCommitEvent.TYPE_ABORT
                   | TwoPhaseCommitEvent.TYPE_ONE_PHASE_COMMIT, a)
    tx.addListener(TwoPhaseCommitEvent.TYPE_BEFORE_COMPLETION
		   | TwoPhaseCommitEvent.TYPE_AFTER_COMPLETION, b);
    try {
      tx.commit();
    } catch (TransactionAbortedException e) { 
      // Listener: TransactionAbortedException!
    }
    

An EventListener implementation looks like this:

public class ListenerImpl implements EventListener {
      public void handleEvent(Event event) {
        BasicTransaction tx = ((TransactionalEvent)event).getTransaction();
        System.out.println("Listener: got event from " + tx.getName());
        if (event instanceof CommitEvent)
          commit( );                     // private method
        else if (event instanceof OnePhaseCommitEvent)
          one_phase_commit( );           // private method
        else if (event instanceof AbortEvent)
          abort( );                      // private method
        else if (event instanceof PrepareEvent)
          prepare((PrepareEvent)event);  // private method
        else if (event instanceof AfterCompletionEvent) {
          acEvent = (AfterCompletionEvent)event;
          before_completion(acEvent.getCompletionStatus());  // private method
        else
          System.out.println("Wrong Event received!");
       }
     

In the example above, you can see that a particular TransactionalEvent implementation can provide a listener with additional data, e.g. the AfterCompletionEvent class allows to get the transaction completion status.

This way it is easily possible to implement both OTS Resource objects, OTS Synchronization objects, etc.

An example of (very simple) OTS Resource and Synchronization implementations is on the org.objectweb.jotm.impl.ots package. E.g., ResourceParticipant is an implementation of OTS Resource participant. A client passes an OTS Resource object to a transaction implementation that registers listener of the corresponding transactional events (PrepareEvent, CommitEvent, OnePhaseCommitEvent, and AbortEvent). The registered participants employ the Resource object.

A transaction is represented by the following interfaces:

• Demarcable - allows to start and commit transaction,
• Interrogable - allows to determine the status, timeout, and other transaction information,
• Suspendable - allows to suspend and resume a transaction,
• EventSource - allows to register transaction participants through listeners of transactional events.

Note that it is not necessary that every transaction implementation implements all of these interfaces. The BasicTransaction interface then represents a demarcable, interrogable and suspendable transaction, which is able to register transaction participants. A simple implementation of such interface is the CoreTransaction class, which is used by all examples in the org.objectweb.jotm.examples package.

2 Conflict Manager

(org.objectweb.jotm.core.conflict package)

The basic mean for the Conflict Manager is a conflict table. A conflict table is a table that for every two object operations specifies whether they are conflicting or not (together with implied dependency and event handler). A conflict table is not necessarilly symmetric.

Another mean is an ignore-conflict relationship between two transactions. A transaction t1 can mark two oeprations on an object obj as non-conflicting for another transaction t2.

For the moment, JOTM 2 defines just lock management service based on the user-defined conflict tables.

Introduction

When implementing transactional locking, we considered the three criteria as follows:

1. When a lock is requested, we need an efficient way of checking whether a conflicting lock is already held by another transaction.
2. When a lock is released, transactions that requested conflicting locks earlier and have therefore been suspended should now be considered for being resumed.
3. When a transaction terminates, all locks (still) held on behalf of the transaction are released at once.

There are also other points to consider:

• FIFO: requests are satisfied in the order they arrived (if possible)
• No starvation: To prevent exclusive locks starvation, a shared lock request shouldn't be allowed to pass a previously issued exclusive lock request that is already waiting for one or more shared locks to be released.
• Lock conversion: if the same transaction which holds a lock asks for another lock, then 1) the original lock can be converted or 2) a transaction can have multiple locks acquired on the same item.

The read/write model

In the read/write model (r/w for short), we consider the read and write operations only, and therefore we need just two lock modes with the following conflict table:

       R  W
    R  -  +           "-" there is no conflict between locks
    W  +  +           "+" the locks are conflicting

Two transactions can share a r/w lock by having it acquired in non-conflicting modes (two reads). If a lock is acquired by a transaction in the write mode, if another transaction is going to acquire a lock in the read or write (both are conflicting with write) modes, it suspended until the conflicting write lock is released.

As for supended waiting requests, a single queue of suspended lock requests is sufficient. However, it is also possible to have separate R and W queues as in MySQL:

The locking method MySQL uses for WRITE locks works as follows:

• If there are no locks on the table, put a write lock on it.
• Otherwise, put the lock request in the write lock queue.

The locking method MySQL uses for READ locks works as follows:

• If there are no write locks on the table, put a read lock on it.
• Otherwise, put the lock request in the read lock queue.

When a lock is released, the lock is made available to the threads in the write lock queue, then to the threads in the read lock queue. This means that

• if you have many updates on a table, SELECT statements will wait until there are no more updates,
• since there are two queues, there can be write lock starvation problem

The r/w model often considers other locks related to read and write operations. This includes:

• Update locks: Use of this lock mode prevents deadlocks in case that multiple transactions are reading some data, decide which data to update, and then update selected data. In this case, transaction share the data thanks to sharing the read lock acquired, but they are deadlocked when waiting for the write (exclusive) lock since the other read locks have to be released. Update lock solve this problem thanks to it is not conflicting with read, but it is conflicting with itself and also read is conflicting with it. Therefore, there can be only one transaction that acquired the lock in the update mode, which prevents new update or read locks acquired. Before going to write (to convert the update mode to the write mode), the transaction just has to wait for reads acquired before.
• Intention locks: These locks are used in locking with different granularity. E.g., in relatinal databases, we can lock a single record or whole table. To indicate that it is not possible to lock a table in the write mode when there is one of its records locked in the read (or write) mode, we lock the table by the intention-read (intention-write mode). An equivalent of the update lock is the read-intention-write mode.

Note that even in the r/w model with the update lock mode as an extension, the conflict table is not symmetric

Model with semantically rich operations

Let us more generalize the points of the r/w model. JOTM 2 is going to be used for components. Components have multiple interfaces with multiple methods. Instead of marking each method as "read" or "write", it is better to stem from the semantic difference of methods and allow to use different locks with multiple lock modes and corresponding conflict tables.

Key principles

A lock can be acquired in multiple lock modes that are specified in the conflict table , which also defines the conflict relation for all lock modes. An entity in name of which a lock can be acquired is an implementation of the org.objectweb.jotm.core.conflict.Locker interface. This interface only requires that the equals method is implemented. For more details see the org.objectweb.jotm.core.conflict.Lock and org.objectweb.jotm.core.conflict.ConflictTable interfaces. A single locker can acquire a lock only once; if it asks for to acquire a lock in a specified mode and it has already acquired the lock before, then the original lock mode is converted to a new mode that covers both the original and newly asked modes.

Basic implementation of locks

A basic implementation of the Lock interface is BasicLock. A basic implementation that uses the transaction associated with the current thread as the locker is TransactionalLock. A basic conflict table implementation is BasicConflictTable.

Here is an example of a conflict table construction:

    String[] ops =     {"balance", "deposit", "withdraw"};
    boolean[][] cTable =
    /* balance */     {{ false,     false,    false,},
    /* deposit */      { false,     false,    true, },
    /* withdraw */     { true,      true,     true  }};

    ConflictTable tab = new BasicConflictTable(ops, cTable);

In this example, e.g., "balance" is not conflicting with any acquired lock mode, while "withdraw" is conflicting with all of them.

A conflict table is passed to the BasicLock or TransactionalLock constructor, and the created instance then uses the conflict table to test conflict between lock modes.

Waiting queues implementation

More queues of suspended lock requests are necessary since two requests can be suspended due to different locks acquired. Consider an example where we have three different lock modes o, p, q, r and conflict relation ~ such that

• q ~ r (q, r are acquired lock modes, therefore the are not conflicting)
• o !~ q (o is suspended because of q)
• p ~ q (p is not suspended because of q)
• p !~ r (p is suspended because of r)

To decide how to implement an effective algorithm of suspending and activiating transactions, we have to consider which properties our conflict relation does have. In the example above, the conflict relation is not transitive nor symmetric! Even we have transitive ~, if it is not symmetric, there can be multiple request queues:

• p ~ q, q !~ p
• r !~ p, r !~ q
• q is acquired, then p is acquired
• r is suspended by q
• another q is suspended by p

If there is transitivity and symmetry of ~, then there are several lock mode groups, where all lock modes do not conflict with each other and each lock mode conflicts with a lock mode from another group.

Since ~ can not be symmetric (e.g. for the broadly-used UPDATE lock), we have to keep in mind that there can be requests suspended by different acquired lock modes.

BasicLock uses one queue of suspended waiting request per each lock mode, i.e., there are as many waiting queues as lock modes.

• When acquiring a lock in a lock mode is requested, it is discovered whether a conflicting lock mode have been acquired before by another locker. If not, the request is fulfilled, the lock is acquired in requested mode, and the current thread continues its execution. If a conflicting acquired lock mode is found, then the request is put to the waiting queue of the specific lock mode and the current thread is suspended.
• When a lock mode is released by a locker, if there is a suspended request in queue of waiting requests of a conflicting mode, then the request is woken up and conflicts with all other active acquirements have to be provided.

The implementation is therefore for with respect to the order of requests of the same lock mode. How to prevent lock starvation and what about lock conversion is described below.

Lock starvation implementation

As for locks starvation, the problem is to prvent the following situation:

• p !~ q
• q is acquired, p is suspended
• another q can be acquired since q ~ q
• p is waiting for no q acquired

Since our implementation is not limited by the existence of predefined lock modes, there is a very simple solution. If the author of the conflict table would like to prevent lock starvation of some lock mode p due to existnce of a less restrictive lock mode q, it has to:

• add another lock mode r, r ~ q, q !~ r
• to prevent q to be acquired, lock in r mode
• no q can be now acquired since q !~ r
• acquired q can be just released
• then p can be acquired (r ~ p, p ~ r)

Lock conversion implementation

In the r/w model, we have a lock conversion lattice. If a tx has a lock mode l acquired and is asking for a lock mode k, then the supremum of l and k lock mode is acquired when possible. This approach is also applicable in the model with semantically rich operations. However, the lattice have to be computed when the compatibility table is passed to the lock manager. In JOTM 2, the lock conversion lattice is implemented by the LockConversionTable class. The lock conversion table is calculated from a conflict table passed to the constructor. In general, the calculated table does not have to represent lattice, since the conflict table can in general define two operations that do not have supremum.

If a request arrives to BasicLock and the lock has been before acquired by the same locker, then:

• If the two lock modes are equal, then nothing is done.
• If the two lock modes are different, then the supremum of the two modes is calculated.
• If the supremum equals the old lock mode, nothing is done.
• If the supremum differs from the old lock mode, then the process of acquiring a lock mode is executed as described above and the old lock mode is released at the same time when the new lock mode is acquired.
• If there is no supremem of the two lock modes, LockConflictException is thrown

A couple of words on deadlocks

Deadlocks are not detected. This is due to the fact that the locker can be e.g. multithreaded transaction, and what we consider as a "deadlock" can be after an amount of time cancelled by another thread releasing one of the existing locks in the name of the locker. If there is a class that wraps BasicLock and uses it for thread-aware locking (by getting currentThread and using it as the locker), then the wrapper class has to implement a kind of deadlock detection.

3 Dependency Manager

(org.objectweb.jotm.core.dependency package)

Dependencies are binary relations among transactions. We distinguish causal, order, and weak-causal dependency types (interface DependencyType). JOTM is able to distinguish between rejectable, delayable, and forcable dependencies, as well as conflicting dependencies.

4 Delegation Manager

(org.objectweb.jotm.core.delegation package)

A transaction t1 is able to delegate an object obj to another transaction t2, which means that t2 becomes responsible for committing or aborting effects having been provided by t1 and all locks on obj become owned by t2. We call t1 a delegator and t2 a delegatee.

In principle, it would be possible to delegate locks instead of obejcts, but we have no identification of locks in JOTM. The delegation granularity level is therefore set to objects: together with an object obj all locks held by a delegator t1 are moved to be owned by a delegatee t2.

5 Log Manager

(org.objectweb.jotm.core.log package)

Log Manager is responsible for logging all event of the transaction lifecycle.

6 Recovery Manager

(org.objectweb.jotm.core.recovery package)

Recovery Manager is responsible for recovery after a JOTM crash.

7 Communication Manager

Support for transaction context-aware communication

8 OTS personality

A very simple prototype implementation of the OTS two-phase commit is in org.objectweb.jotm.ots

• TransactionImpl is a very simple OTS Current-like class that allows to register OTS Resource and Synchronization objects. It employs the ResourceParticipant andSynchronizationParticipant objects that implements the mapping between JOTM 2 and OTS participants.
• ResourceParticipant is a class that implements TwoPhaseCommit event handler for the PREPARE, COMMIT, ONE_PHASE_COMMIT, and ABORT events. Upon the received events, the corresponding OTS Resource methods are invoked.
• SynchronizationParticipant is a class that implements TwoPhaseCommit event handler for the BEFORE_COMPLETION and AFTER_COMPLETION events. Upon the received events, the corresponding OTS Synchronization methods are invoked.

9 Examples

Very simple examples are in org.objectweb.jotm.examples:

Example

(org.objectweb.jotm.examples.Example)
ant example

An example with pure JOTM 2 that comprises three scenarios:

• One-phase commit: registration of a single TwoPhaseCommit.TYPE_TWO_PHASE_COMMIT participant.
• Two-phase commit: registration of two single TwoPhaseCommit.TYPE_TWO_PHASE_COMMIT participants.
• Late registration: registration of a single TwoPhaseCommit.TYPE_TWO_PHASE_COMMIT and a single TwoPhaseCommit.TYPE_BEFORE_COMPLETION participants with a demonstration of an unsuccessfull registration of an TwoPhaseCommit.TYPE_AFTER_COMPLETION participant in the BEFORE_COMPLETION event handler.

Files:

• Example.java - main class, creation of a transaction, registration of transaction participants, transaction commit
• ListenerImpl.java - a class that implements event handlers

OTS Example

(org.objectweb.jotm.examples.OtsExample)
ant otsexample

An example of OTS commitment, which comprises two scenarios:

• One-phase commit: registration of a single OTS Resource and single OTS Synchronization objects.
• Two-phase commit: registration of several OTS Resource and single OTS Synchronization objects.

Files:

• OtsExample.java - main class, creation of a transaction, registration of transaction participants, transaction commit
• Component.java - a class that implements OTS Resource and Synchronization interfaces
  

Log Example

(org.objectweb.jotm.examples.LogExample)
ant logexample

An example of simple logging. In fact, logging is enabled for CoreTransaction, so this example currently does not make sense, since logging works in all examples. Currently, Log Manager just writes "begin" and "commit" events to a log file created in the root directory of the JOTM2 distribution. The Log Manager keeps a single file for every transaction (the prefix of the file is the name of the transaction). Currently, the file is not deleted when transaction finishes.

Files:

• LogExample.java - main class, creation of a transaction, transaction commit

Lock Example

(org.objectweb.jotm.examples.LockExample)
ant lockexample

An example of how to use JOTM 2 locking. The example creates two transactions in two different threads. Each transaction registers the AccountImpl transaction participant and invokes its balance, deposit, and withdraw methods. AccountImpl uses a single transaction-aware lock with the balance, deposit, and withdraw modes. When one of its business methods is invoked, the corresponding lock mode is acquired. At commit, the lock is released.

Files:

• Account.java - a simple bank account interface
• AccountImpl.java - a simple bank account implementation
• LockExample.java - main class, thread creation, transaction creation, registration of a AccountImpl instance to transactions and invocation of its methods.

Lock Test

(org.objectweb.jotm.examples.LockTest)
ant locktest

The test creates 1000 transactions in 1000 different threads. Each transaction registers the AccountImpl transaction participant and invokes either its balance or withdraw method. AccountImpl uses a single transaction-aware lock with the balance, deposit, and withdraw modes. When one of its business methods is invoked, the corresponding lock mode is acquired. At commit, the lock is released and the number of all requested locks and all obtained locks is printed.

Files:

• Account.java - a simple bank account interface
• AccountImpl.java - a simple bank account implementation
• LockTest.java - main class, thread creation, transaction creation, registration of a AccountImpl instance to transactions and invocation of its methods.