The Stanford Rapide Project

X/Open Architecture Rapide Code

Architectures

Local Instance Architecture

A particular instance of the X/Open architecture, which X/Open calls a local instance architecture, consists of one application program (AP), one transaction manager (TM), and one or more resource managers (RMs) connected together as shown in the above figure. The boxes indicate the generic component interfaces, and the lines indicate the communication between them.

This architecture is coded in Rapide as:

architecture LIA(NumRMS : Integer) for DTP is
- connect
  - AP.TX to TM.TX;
  - for i : Integer in 1..NumRMs generate
    - TM.XAs(i) to RMs[i].XA;
    - RMs[i].AX to TM[i].AX;
    - AP.AR(i) to RMs[i].AR;
  - end generate;
end architecture LIA;

Component Interfaces

Application Program Interface

The interface of an AP component includes two services: a native RM service(s) through which the AP communicates with the RMs and a TX (transaction demarcation) service through which the AP communicates with a TM.

type Application_Program(NumRMS : Integer) is
- interface
  - service
    - AR(1..NumRMs) : dual AR_Interface;
    - TX : dual TX_Interface;
end interface Application_Program;

Transaction Manager Interface

The interface of a TM component includes NumRMs XA services, one for each RM the TM may call, an AX service that ll the RMs may call, and a TX service that the AP may call.

type Transaction_Manager is
- interface
  - service
    - XAs(1..NumRMs) : dual XA_Interface;
    - AX : AX_Interface;
    - TX : TX_Interface;
end interface Transaction_Manager;

Resource Manager Interface

The interface of a RM component includes a native service for the AP and a XA service and an AX service through which the RM communicates with a TM.

type Resource_Manager is
- interface
  - service
    - AR : AR_Interface;
    - XA : XA_Interface;
    - AX : dual AX_Interface;
end interface Resource_Manager;

Services

TX (Transaction Demarcation) Interface

TX is the name of the service shared by the AP and the TM. The TX functions are provided by TMs and are called by APs. APs demarcate global transactions via the TX interface and perform recoverable operations via RMs' native interfaces.

type TX_Interface is
- interface
  - provides
    - function tx_begin (x : Xid_t) return TX_Return_Code;
    - function tx_close (x : Xid_t) return TX_Return_Code;
    - function tx_commit (x : Xid_t) return TX_Return_Code;
    - function tx_info (x : Xid_t; info : ref(TXInfo)) return TX_Return_Code;
    - function tx_open (x : Xid_t) return TX_Return_Code;
    - function tx_rollback (x : Xid_t) return TX_Return_Code;
    - function tx_set_commit_return (x : Xid_t; when_return : Commit_Return) return TX_Return_Code;
    - function tx_set_transaction_control (x : Xid_t; control : Transaction_Control) return TX_Return_Code;
    - function tx_set_transaction_timeout (x : Xid_t; timeout : Transaction_Timeout) return TX_Return_Code;
end interface TX_Interface;

Transaction Characteristics

The state of an application thread of control includes several characteristics. The AP specifies these by calling tx_set_*() functions.

Commit Return Characteristic

The commit_return characteristic determines the stage in the commitment protocol at which the tx_commit() call returns to the AP.

type Commit_Return is
- enum
  - TX_COMMIT_COMPLETED, -- tx_commit() returns when the two-phase commit procedure is completed.
  - TX_COMMIT_DECISION_LOGGED -- tx_commit() returns at the point when the decision to commit is logged but prior to completing the second phase.
end enum Commit_Return;

Transaction Control Characteristic

The transaction_control characteristic determines whether the completion of one transaction automatically begins a new transaction (called chained mode).

type Transaction_Control is
- enum
  - TX_CHAINED, -- completion begins a new transaction
  - TX_UNCHAINED -- completion does not begin a new transaction
end enum Commit_Return;

Transaction Timeout Characteristic

The transaction_timeout characteristic specifies the time period in which the transaction must complete before becoming susceptible to transaction timeout. The interval is expressed as a number of seconds.

type Transaction_Timeout is Integer;

Transaction Information

The TXInfo record is used to return information about the thread state, including the state of all characteristics, the thread's association, if any, to a global transaction, and transaction state information.

type TXInfo is
- record
  - xid : ref(Xid_t);
  - when_return : ref(Commit_Return);
  - control : ref(Transaction_Control);
  - timeout : ref(Transaction_Timeout);
  - state : ref(Transaction_State);
end enum TXInfo;

Transaction State

The AP may call tx_info() to obtain information regarding the state of the transaction it is in; that is, to determine whether the transaction is alive, has timed-out (and been marked rollback-only), or has beeen marked rollback-only (for a reason other than transaction timeout).

type Transaction_State is
- enum
  - TX_ACTIVE,
  - TX_TIMEOUT_ROLLBACK_ONLY,
  - TX_ROLLBACK_ONLY
end enum Transaction_State;

Return Codes

type TX_Return_Code is
- enum
  - TX_NOT_SUPPORTED, -- option not supported
  - TX_OK, -- normal execution
  - TX_OUTSIDE, -- application is in an RM local transaction
  - TX_ROLLBACK, -- transaction was rolled back
  - TX_MIXED, -- transaction was partially committed and partially rolled back
  - TX_HAZARD, -- transaction may have been partially committed and partially rolled back
  - TX_PROTOCOL_ERROR, -- routine invoked in an improper context
  - TX_ERROR, -- transient error
  - TX_FAIL, -- fatal error
  - TX_EINVAL, -- invalid arguments were given
  - TX_COMMITTED, -- transaction has heuristically committed
  - TX_NO_BEGIN, -- transaction committed plus new transaction could not be started
  - TX_ROLLBACK_NO_BEGIN, -- transaction rollback plus new transaction could not be started
  - TX_MIXED_NO_BEGIN, -- mixed plus new transaction could not be started
  - TX_HAZARD_NO_BEGIN, -- hazard plus new transaction could not be started
  - TX_COMMITTED_NO_BEGIN -- heuristically committed plus new transaction could not be started
end enum TX_Return_Code;

XA Interface

XA is the name of the services shared by the TM and the RM. XA consists of two services, ax and xa. The xa services are provided by RMs and are called by TMs, while the ax services are provided by TMs and are called by RMs.

XA Service

Each RM provides a XA_Service that gives the TM access to the RM's xa_ routines.

RMNAMESZ : Integer is 32;
type XA_Service is
- interface
  - provides
    - Name : String;
    - Flags : ref(set(RM_Flag));
    - Version : Integer;
    - function xa_close (thread : Pid_t; xa_info : Info_Type); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_commit (thread : Pid_t; xid : ref(Xid_t); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_complete (thread : Pid_t; handle, retval : Integer; rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_end (thread : Pid_t; xid : ref(Xid_t); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_forget (thread : Pid_t; xid : ref(Xid_t); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_open (thread : Pid_t; xa_info : Info_Type); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_prepare (thread : Pid_t; xid : ref(Xid_t); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_recover (thread : Pid_t; xids : set(Xid_t); count : Integer; rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_rollback (thread : Pid_t; xid : ref(Xid_t); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
    - function xa_start (thread : Pid_t; xid : ref(Xid_t); rmid : RMid_t; flags : set(XA_Flag)) return XA_Return_Code;
  - axiom
    - Name.length() <= RMNAMESZ;
    - Version = 0;
end interface XA_Service;

RM Flags

type RM_Flag is
- enum
  - TMNOFLAGS, -- no other flag being used
  - TMREGISTER, -- resource manager dynamically registers
  - TMNOMIGRATE, -- resource manager does not support association migration
  - TMUSEASYNC -- resource manager supports asynchronous operations
end enum RM_Flag;

Info_Type

MAXINFOSIZE : Integer; -- maximum size in bytes of xa_info strings, including the null terminator
type Info_Type is
- interface
  - include String;
- axiom
  - Length() <= MAXINFOSIZE;
end interface Info_Type;

Resource Manager Identifier

type RMid_t is Integer;

XA Flags

type XA_Flag is
- enum
  - TMNOFLAGS, -- no other flag being used
  - TMASYNC, -- perform routines asynchronously
  - TMONEPHASE, -- caller is using one--phase commit optimization
  - TMFAIL, -- dissociates caller and marks transaction branch rollback--only
  - TMNOWAIT, -- return if blocking condition exists
  - TMRESUME, -- caller is resuming association with suspended transaction branch
  - TMSUCCESS, -- dissocate caller from transaction branch
  - TMSUSPEND, -- caller is suspending, not ending, association
  - TMSTARTRSCAN, -- start a recovery scan
  - TMENDRSCAN, -- end a recovery scan
  - TMMULTIPLE, -- wait for any asynchhronous operation
  - TMJOIN, -- caller is joining existing transaction branch
  - TMMIGRATE -- caller intends to perform migration
end enum XA_Flag;

XA Interface Return Codes

type XA_Return_Code is
- enum
  - /* XA_RBBASE, */ -- the inclusive lower bound of the rollback codes
  - XA_RBROLLBACK, -- the rollback was caused by an unspecified reason
  - XA_RBCOMMFAIL, -- the rollback was caused by a communication failure
  - XA_RBDEADLOCK, -- a deadlock was detected
  - XA_RBINTEGRITY, -- a condition that violates the integrity of the resources was detected
  - XA_RBOTHER, -- the resource manager rolled back the transaction branch for a reason not on this list
  - XA_RBPROTO, -- a protocol error occurred in the resource manager
  - XA_RBTIMEOUT, -- a transaction branch took too long
  - XA_RBTRANSIENT, -- may retry the transaction branch
  - /* XA_RBEND, */ -- the inclusive upper bound of the rollback codes
  - XA_NOMIGRATE, -- resumption must occur where suspension occurred
  - XA_HEURHAZ, -- the transaction branch may have been heuristically completed
  - XA_HEURCOM, -- the transaction branch has been heuristically completed
  - XA_HEURRB, -- the transaction branch has been heuristically rolled back
  - XA_HEURMIX, -- the transaction branch has been heuristically committed and rolled back
  - XA_RETRY, -- routine returned with no effect and may be reissued
  - XA_RDONLY, -- the transaction branch was read--only and has been committed
  - XA_OK, -- normal execution
  - XAER_ASYNC, -- asynchronous operation already outstanding
  - XAER_RMERR, -- a resource manager error occurred in the transaction branch
  - XAER_NOTA, -- the XID is not valid
  - XAER_INVAL, -- invalid arguments were given
  - XAER_PROTO, -- routine invoked in an improper context
  - XAER_RMFAIL, -- resource manager unavailable
  - XAER_DUPID, -- the XID already exists
  - XAER_OUTSIDE -- resource manager doing work outside global transaction
end enum XA_Return_Code;

AX Service

The TM provides an AX_Service that gives the RMs access to the TM's ax_ routines. All TMs must provide these routines. These routines let a RM dynamicall control its participation in a transaction branch.

type AX_Service is
- interface
  - provides
    - -- Register an RM with a TM.
    - function ax_reg (thread : Pid_t; rmid : RMid_t; xid : ref(Xid_t); flags:set(XA_Flag)) return AX_Return_Code;
    - -- Unregister an RM with a TM.
    - function ax_unreg (thread : Pid_t; rmid : RMid_t; flags : set(XA_Flag)) return AX_Return_Code;
- constraint
  - -- The flags argument of ax_reg() and ax_unreg() is reserved for future use and must be set to TMNOFLAGS.
  - never (?t in Pid_t, ?rmid in RMid_t, ?xid in ref(Xid_t), ?flags in set(XA_Flag), ?ret in AX_Return_Code)
  - ( ax_reg'Call(?t,?rmid,?xid,?flags)
  - or ax_reg'Return(?t,?rmid,?xid,?flags,?ret)
  - or ax_unreg'Call(?t,?rmid,?flags)
  - or ax_unreg'Return(?t,?rmid,?flags,?ret) )
  - where ?flags.Cardinality() /= 0;
end interface AX_Service;

AX Routine's Return Codes

type AX_Return_Code is
- enum
  - TM_JOIN, -- caller is joining existing transaction branch
  - TM_RESUME, -- caller is resuming association with suspended transaction branch
  - TM_OK, -- normal execution
  - TMER_TMERR, -- an error occurred in the transaction manager
  - TMER_INVAL, -- invalid arguments were given
  - TMER_PROTO -- routine invoked in an improper context
end enum AX_Return_Code;

Native Application to Resource Manager Interface

type AR_Interface is
- interface
  - action
    - in Request(thread : Pid_t);
    - out Results(thread : Pid_t);
end interface AR_Interface;

Global Types

Thread of Control (Pid_t)

A thread of control (or a thread) is the entity, with all its context, that is currently in control of a processor. A thread of control is an operating system process: an address space and single thread of control that executes within that address space, and its required system resources.

type Pid_t is Integer;
type Operating_System is
- interface
  - provides
    - -- returns a new thread identifier
    - Create_Thread : function() return Pid_t;
end interface Pid_t;

There are several constraints associated with threads.

Transaction Branch Identifier (Xid_t)

The X/Open standard uses transaction branch identifiers (or xids) to associate individual operations with a global transaction. An xid is a string that identifies a global transaction and als identifies a specific transaction branch which is the set of operations between the TM and one RM. Each xid is generated by the TM and given to a RM. The RM may use this information to optimize its use of shared resources and locks.

The xid structure is specified in the Xid_t interface (see the Rapide code below). The xid contains a format identifier, two length fields and a data field. The data field comprises at most two contiguous components: a global transaction identifier (gtrid) and a branch qualifier (bqual). The gtrid_length field specifies the number of bytes that constitute gtrid. The bqual_length field specifies the number of bytes that constitute bqual. A value of -1 in FormatID means that the xid is null.

XIDDATASIZE : Integer is 128; -- size in bytes
MAXGTRIDSIZE : Integer is 64; -- maximum size in bytes of gtrid
MAXBQUALSIZE : Integer is 64; -- maximum size in bytes of bqual
type Xid_t is
- record
  - formatID, -- format identifier
  - gtrid_length,
  - bqual_length : ref(Integer);
  - data : String;
- axiom
  - -- The value in formatID should be greater than or equal to -1.
  - (formatID>= -1);
  - -- A value of -1 in FormatID means that the XID is null.
  - (formatID = -1) -> ( gtrid_length = 0 and bqual_length = 0 );
  - (formatID> -1) ->
    - ( 1 <= gtrid_length and gtrid_length <= MAXGTRIDSIZE and
    - 1 <= bqual_length and bqual_length <= MAXBQUALSIZE );
  - data.length() <= XIDDATASIZE;
  - data.length() = gtrid_length + bqual_length;;
end record Xid_t;

Commentary: The X/Open documents discuss the passing of pointers to xids, since many of the functions pass them. These pointers are valid only for the duration of the call. If the xid is needed after it is returned from the call, a local copy must be made before returning. In the reference architecture, the passing of references to xids has the same restriction.

Selected Constraints

Thread of Control Constraints

One property of threads is that all events generated by a thread are causally ordered.

match (?e in Event(thread : Pid_t); ?thread in Pid_t)
( ?e(?thread)^(-> *))^(~ *);

The thread concept is central to the TM's coordination of RMs. APs call RMs to request work, while TMs call RMs to delineate transaction branches. The way the RM knows that a given work request pertains to a given branch is that the AP and the TM both call it from the same thread.

This protocol can be expressed in Rapide as the following constraint:

match (?thread in Pid_t)
- ( AP.TX.tx_begin(?thread)
- -> TM.XA.xa_start(?thread)^(-> *) -> AP.AR.Request(?thread)^(-> *) ->
- ( AP.TX.tx_commit(?thread) or AP.TX.tx_rollback(?thread)))^(~ *);

Atomicity Constraint

Transactions are not guaranteed to execute to completion, but instead are insured to a weaker but still sufficient property. Transactions are performed entirely or not at all; they cannot be only partially done at termination.

The following Rapide constraint expresses that a global transaction identifier (i.e., a process identifier) should never be the argument of a commit event for one RM and an abort event for another RM. As a consequence, any transaction is either committed by all RM's or none.

never(
- ?thread1, ?thread2 in Pid_t;
- ?x in Xid_t;
- ?rm1, ?rm2 in RMid_t;
- ?flags1, ?flags2 in set(XA_Flag)))
( Resource_Manager::XA.xa_commit'return (?thread1,?x,?rm1,?flags1,xa_ok)
~ Resource_Manager::XA.xa_rollback'return (?thread2,?x,?rm2,?flags2,xa_ok));

Coordination Constraint

The following Rapide constraint expresses that all commit call events from the TM to the RMs must depend upon all the prepare returns from the RMs.

never
- ?thread1, ?thread2 in Pid_t;
- ?x in Xid_t;
- ?rm1, ?rm2 in RMid_t;
- ?flags1, ?flags2 in set(XA_Flag)))
( Resource_Manager::XA.xa_prepare'return (?thread1,?x,?rm1,?flags1,xa_ok)
|| Resource_Manager::XA.xa_commit'call (?thread2,?x,?rm2,?flags2));

Selected Behaviors

Transaction Manager

The transaction manager's primary purpose is to ensure atomicity. The most common approach to achieving atomicity is the two phase commit protocol. It is so called, because the commitment protocol is divided into two phases. Commitment refers to whether the transaction can end successfully, i.e., can do what it was requested to do.

In Phase 1, the polling phase, the manager for each resource is asked whether it can commit its part of the transaction, if it is requested to do so. If a resource manager can commit its work, it replies affirmatively. This positive response is a promise, guaranteeing that if asked to commit, it will. A negative reply reports failure for any reason. Thus, the poll is asking whether the resource can commit its transaction branch, and if so, prepare the branch for commitment.

When all the resource managers have responded, the decision phase, Phase 2, is entered. If all resource managers responded affirmatively, then all of the resource managers are requested to commit (otherwise they are all requested to undo their parts of the transaction thereby restoring the database to a consistent state. Thus, the entire transaction is ensured of being either atomically committed or undone.

(?x : Xid_t) AP.commit_call(?x)
- => (!i : Integer in 1..NumRMs ~) XAs(!i).prepare_call(?x);;
(?x : Xid_t)((!i : Integer in 1..NumRMs ~) XAs(!i).prepare_retn(?x,True))
- => (!i : Integer in 1..NumRMs ~) XAs(!i).commit_call(?x);;
(?x : Xid_t)((prepare_ret(?x)^(~ *) ~ prepare_retn(?x, False))
<-> ((!i : Integer in 1..NumRMs ~) XAs(!i).prepare_retn(?x)))
- => (!i : Integer in 1..NumRMs ~) XAs(!i).rollback_call(?x);;
(?x : Xid_t)((!i : Integer in 1..NumRMs ~) XAs(!i).commit_retn(?x, True))
- => AP.commit_retn(?xid, committed);;
(?x : Xid_t)((!i : Integer in 1..NumRMs ~) XAs(i).rollback_retn(?x, rollback))
- => AP.commit_retn(?xid, rolledback);;

Exemplary Execution

The independent, and possibly concurrent execution of the two resource managers is explicitly visible by the two sides of the poset. Width in a poset expresses independence. Dependencies between the two sides indicate synchronization or coordination between the components occurred. The executions of the resource managers was synchronized two times in the execution. First, when the application decided to attempt to commit the transaction. This decision was based upon the good work results of both resource managers. Presumably, if either of the transaction branches' work was not favorable, the decision would have been made to abort the transaction.

The second time the execution of the resouce managers was synchronized occurred when the application program made the decision to actually commit the transaction. This is easily visible in the poset where the dependencies criss cross near the bottom of the poset. This criss crossing is quite typical of the two phase commit protocol, and is an indication of a complex coordination between the resource managers.

8/5/97/lp