Transcript TMs and ORBs - Microsoft Research

TP Monitors And ORBs
9:00
11:00
13:30
15:30
18:00
Aug. 2
Intro &
terminology
Reliability
Fault
tolerance
Transaction
models
Reception
Aug. 3
Aug. 4
Aug. 5
Aug. 6
TP mons
Logging &
Files &
Structured
& ORBs
res. Mgr.
Buffer Mgr.
files
Locking Res. Mgr. &
COM+
Access paths
theory
Trans. Mgr.
Locking
CICS & TP
CORBA/
Groupware
techniques & Internet
EJB + TP
Queueing
Advanced
Replication Performance
Trans. Mgr.
& TPC
Workflow Cyberbricks
Party
FREE
Chapter 5

Application
Transaction
Processing
Services
(TRAPS)
Transaction
Processing
Operating
System
(TPOS)
Basic
Operating
System
(BOS)
Hardware
© Jim Gray, Andreas Reuter
operator
interface
configuration
load control
databases (SQL)
disaster recovery
prog.environ.
resource managers
flow control
TRANSIDs
server class
request scheduling
resource mgr. i/f.
authentication
transaction manager
log, context
durable queue
transactional file
archive
process / thread
repository
address space
scheduling
IPC
local naming
protection
file system
directory
extents
blocks
processors
memory
file security
Transaction Processing - Concepts and Techniques
distributed name
binding
server invocation
protected user
interface

transactional RPC
transactional
session
RPC
IPC
simple
sessions
(open/close,
write/read)
naming
authentication
wires, fibers,
switches
WICS August 2 - 6, 1999
2
The Resource Manager Interface
rmCall(...)
response
res. manager's own service interface
To and from
TP-monitor and
other system
resource
managers
(used for
transaction
control)
© Jim Gray, Andreas Reuter
functions
invocation
administrative functions
and callbacks for
installing, starting, and
scheduling a resource
manager

rmCall(...)
transaction Resource other
management Manager resource
managers
(depends on application)
callbacks
callbacks
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
3
Some Terminology




TP-Monitor: This term denotes an operating system extension that
understands transactions.
Resource Manager: This is a system component that offers useful
services to certain user groups and that protects its resources by
transactions. An example of a very important resource manager is a
database system.
rmCall: This is used as a generic call to any kind of resource manager.
The call specifies the name of the resource manager, the operation that
should be executed, and the parameters for the operation. If there is a
database containing course information, such a call could look like this:
rmCall (“CourseDB”, “select Course-No, Ctitle from Courses,
Offerings where Term = “Summer 1999” and ….”, ...)

Callback: When a module calls some other module and that module in
turn invokes the module that called it, the technical term for that
mechanism is: callback.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
4
Some Interface Definitions
typedef struct
{
/* handle for identifying the specific instantiation
*/
/* of a resource manager
*/
NODEID nodeid;
/* node where process lives
*/
PID
pid; /* process request is bound to
*/
TIMESTAMP
birthdate; /* time of server creation */
} rmInstance;
/* identifies a specific server */
typedef struct
{
Ulong
char
} rmParams;
/* resource manager parameters
CB_length; /* number of bytes in CB
CB_bytes [CB_length]; /* byte string
Boolean rmCall(RMNAME,
/*inv. of RM named RMNAME
Bindld* BoundTo,
/* expl. with bind mechanism
rmParams * InParams,
/* params to the server
rmParams * OutResults); /* results from server
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques

*/
*/
*/
*/
*/
*/
*/
WICS August 2 - 6, 1999
5
RM Callbacks for the TM
Boolean rm_Prepare();
Boolean rm_Rollback_Savepoint(Savepoint);
Boolean rm_Commit(Boolean);
Boolean rm_Savepoint();
(void) rm_UNDO(&buffer);
(void) rm_Abort();
(void) rm_REDO(&buffer);
(void) rm_Checkpoint();
(void) TM_Startup(lsn);
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

6
Control Flow in Transactional RPCs
thread 1
thread 2
resource manager
address space
transaction manager
address space
rmCall(.....)
main portion of the
resource
manager
return(success);
rm_Prepare()
logic for
commit phase 1
Commit_Work(...)

two-phase commit
protocol
return (decision);
Abort_Work()
thread 2
abort logic
return;
return(vote);
thread 3
rm_UNDO(*log_data)
thread 3
undo logic
return;
other callback entries
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
7
RM Calls vs. RM Sessions

Independent invocations: A server of class S can be
called arbitrarily often, and the outcome of each call is
independent of whether or not the server has been
called before. Moreover, each server instance can
forget about the transaction by the time it returns the
result. Since the server keeps no state about the call,
there is nothing in the future fate of the transaction
that could influence the server’s commit decision.
Upon return, the server declares its consent to the
transaction’s commit, should that point ever be
reached.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

8
RM Calls vs. RM Sessions

Invocation sequence: The client wants to issue service requests
that explicitly refer to earlier service requests; for example, “Give
me the next 10 records.” The requirement for such service
requests arises with SQL cursors. First, there is the OPEN
CURSOR call, which causes the SELECT statement to be
executed and all the context information in the database system to
be built up. As was shown, this results in an rmCall to the sql
server. After that, the FETCH CURSOR statement can be called
arbitrarily often, until the result set is exhausted. If it was an update
cursor, then the server cannot vote on commit before the last
operation in the sequence has been executed; that is, the server
must be called at its rm_Prepare() callback entry, and the outcome
of this depends on the result of the previous service call.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

9
RM Calls vs. RM Sessions

Complex interaction: The server class must remember the
results of all invocations by client C until commit, because only
then can it be decided whether certain deferred consistency
constraints are fulfilled. Think of a mail server. The server creates
the mail header during the first interaction, the mail body during
the next interaction, and so on. The mail server stores the
various parts of a message in a database. All these interactions
are independent; the client might as well create the body first,
and the header next. However, the mail server maintains a
consistency constraint that says that no mail must be accepted
without at least a header, a body, and a trailer. Since this
constraint cannot be determined until commit, there must be
some way of relating all the updates done on behalf of the client
when the server is called (back) at rm_Prepare.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

10
Context Management - I
client
Begin_Work
S(.....);
S(.....);
S(.....);
Commit_Work
S1
S2
S3
server class S
a) each call to S is independent of
previous calls to S
client
Begin_Work
S(.....);
S(.....);
S(.....);
Commit_Work
client
Begin_Work
S(.....);
S(.....);
S(.....);
Commit_Work
result of
invocation
of S1
S2
result of
invocation
S3
of S2
result of
invocation
S4
of S3
server class S
b) the result of each call depends on the
result of the previous call
S1
S2
S1

results of
all invocations
needed for
S4 commit decision
S3
server class S
c) each call to S is independent - except for some global
integrity constraints that cannot be checked until commit
and that may depend on the results of all previous invocations
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
11
Context Management - II
request
session
server
client request S1
context resp.
context
client
response context
context
kept
loc.
request context
a) Context is maintained by a
communication session that makes
sure that each subsequent request
goes to the same server instance as
the previous one.
client request
context resp.
server
S1
server
S2
read/
write
context
DB
c) The servers write context
information to a database. This
might be a private database to the
server class or a context database
provided by the TP-monitor.
© Jim Gray, Andreas Reuter
response context
server
S1
server
S2
b) Context is passed back and
forth explicitly between client
and server upon each request and
reply.

server
S1
client request
context
context resp.
server
S2
d) All servers of the same class
share a segment of read/write
memory in which invocation
context is kept. Synchronization on
this memory is done by the servers.
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
12
Types of Context Information

Client-oriented context: The solutions presented so far implicitly
assume that this is the type of context to be managed. Typical
examples are cursor positions, authenticated userids, etc.

Transaction-oriented context: Consider the following example:
Client C invokes server S1, which in turn invokes server S3—all
within T. After return from the service call, C invokes S2 (a different
server class), which also invokes S3, but needs the context
established by the earlier call to S3 from S1. The point here is that
the context needed by S3 is not bound to any of the previous clientserver interactions, but it is bound to the transaction as such. This
leads back to the argument about the similarities between sessions
and transactions in terms of context management. Examples of
transaction-oriented context are deferred consistency constraints
and locks.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

13
Managing Context


Session management: If context maintenance is
handled through communication sessions, then theTP
monitor is responsible for binding a server process to
one client for the duration of a stateful invocation.
Process management: Even if the TP monitor has no
active responsibility for context management, it may
use information about the number of existing sessions
per server for load balancing. The rationale is that an
established session is an indicator for more work in the
future.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

14
More Interfaces
typedef struct
{rmInstance EndA;
rmInstance EndB;
Uint
SeqNo;
} BindId;
/* one end of stateful interaction
/* other end of stateful interaction
/* sequence no. to distinguish
/* between stateful interactions
/* among the same servers.
/* handle for a stateful interaction
*/
*/
*/
*/
*/
*/
BindId rmBind(rmInstance);
/* passes the id of client to which */
/* a session has to be established. */
/* gets a handle for the interaction */
/* among this server and this client. */
/* returns null if binding fails.
*/
Boolean rmUnbind(BindId);
/* inverse to rmBind.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques

*/
WICS August 2 - 6, 1999
15
More Interfaces
PID MyProcid();
TRID
RMID
RMID
PCB
MyTrid();
MYRMID();
ClientRMID();
MyProc();
TransCB MyTrans();
RMCB MyRM();
RMCB ClientRM();
© Jim Gray, Andreas Reuter
/* returns ID of process the caller is running in*/
/* this is actually a call to the basic os
*/
/* returns the TA ID the caller is executing in */
/* returns RMID of the RM that has called
*/
/* returns the RMID of the caller’s client
*/
/* returns a copy of the process control block */
/* descr. the process the caller is running in */
/* returns copy of the transaction ctl. block. */
/* describing the TA the caller is working for */
/* returns copy of the resource mgr. control */
/* block desc. the RM that issued the call
*/
/* like MyRM, but for the caller’s client
*/
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

16
Schema of the Transactional Objects
which transaction
uses a session at
the moment
1
active
transactions
1
n
transactions a
resource manager
is involved in
m
n
resource
managers
resource managers
participating in a
transaction
1

which transaction for each resource
is process working manager there is
for at the moment one server class
sessions
n
each session has
two processes as
its end-points
2
n
processes/
threads
processes in a
server class
1
n
1
m
n
server
classes
address spaces a process
can switch to
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
17
Name Binding for rmCalls
<RMNAME, EntryName>
Step 1:
RM locally
available ?
RMTable
Step 2
(yes):
Bind to
that
RMID
ResMgrName
rmid
RMactive
RMup
...
RMPR_chain
rm_entry[]
...
rm_Savepoint
rm_Prepare
rm_Commit
...
Step 4:
Find entry
point address
Step 2 (no):
Find a node
in the name
server;
send request
via RP C; do
local
binding at
that node
ProcessIx
busy
NextP rocess
name server
RMNAME
mailer
DebitCredit
DebitCredit
order entry
order entry
order entry
sqldb
DebitCredit
DebitCredit
sqldb
address
interface ptype
farnode.mailserver
***
NearNode.1
***
NearNode.2
***
snode1.prod
***
snode2.prod
***
snode3.prod
***
database.server
***
NearNode.1
***
NearNode.2
***
database.server
***
RPC to other node;
there it will be local
binding
Step 3:
Find an idle
process

cached
part
of name
server
Step 5: activate process at entry point address
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
18
The CORBA-Way of Saying It

© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
19
OTS: The BIG Picture
3
TA
client
2
TA
object
3
rec.
object
4
7
Sub-TA
res.

Recoverable server
TA server
1
resource
Object Transaction Service
6
5
TA context
Object Request Broker (ORB)
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
20
OTS Interfaces
1 A transactional client requests begin or end of
transaction. If upon a begin request, a TA
already exists, a sub-TA is started.
2 The client invokes operations from a
transactional object. Such an object has no
persistent state.
3 Requests can also be made at recoverable
objects.
4 Registers a resource object with the OTS for
commit coordi-nation; may initiate rollback.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

21
OTS Interfaces
5 A resource understanding sub-TAs implements
what is needed for completing a sub-TA,
passing the locks to the parent, etc.
6 A resource participates in the 2PC, makes
changes to persistent state durable, performs
recovery if needed, etc.
7 A transactional object may initiate rollback.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

22
Transaction Context




OTS maintains a transaction context for each
active TA. It is associated with all transactional
operations.
The TA context is an implicit parameter for all
invocations of TA operations.
The context can also be passed as an explicit
parameter.
This is required in environments where both the
OTS style and the procedural (X/Open DTP)
style of transactions are used in parallel.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

23
The Transaction´s New Clothes
Boolean Debit (Amount amountRequested) {
Account
theAccount;
Branch
theBranch;
Teller
theTeller;
History
GlobalHistory;

Current
theCurrentTransaction;
theCurrentTransaction.begin();
Amount balance = theAccount.query();
if (balance >= amountRequested)
{ theAccount.withdraw(amountRequested);
theBranch.withdraw(amountRequested);
theTeller.withdraw(amountRequested);
GlobalHistory.remember(amountRequested);
theTeller.dispense(amountRequested);
theCurrentTransaction.commit();
return True;
else ...
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
24
OTS Interfaces



Current denotes a pseudo object, the methods of which
are executed within OTS and ORB.
Invoking begin on an object of class current creates a
transaction context that is managed by the ORB until
the TA either commits or aborts.
As a result of begin, the newly created context is
associated with the client´s “thread of control”, which
typically translates into “process”. Multiple threads (in
different execution environments) can be associated
with the same context at the same time.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

25
Why Use Queues?




Load control: In case of temporary overload put requests into a
queue for the server class rather than flood the system with new
processes.
End-user control: Queue can maintain the output of
asynchronous transactions for delivery until the user explicitly
acknowledgs receipt.
Recoverable data entry: Requests put on server’s queue. Server
application processes requests as fast as it can.
Multi-transaction requests (Workflow): Requests are processed
by a server which passes results on to another server for further
processing. This can go on for many steps. If none of the steps
interacts with a user, they can all be executed asynchronously.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

26
Workflow Management Using Queues
output queue of
client A /
input queue of
server 1
ClientA
output queue of
server 1 /
input queue of
server 2
output queue
of server 2 /
input queue of
server 3
Server1
Server2
Server4
Server3

might be
identical
ClientB
output queue
of server 4 /
response queue
of client B
© Jim Gray, Andreas Reuter
output queue
of server 3 /
input queue of
server 4
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
27
Durable Queues for Asynchronous
Transactions
1. transaction
2. transaction
send request
receive
request
client

server
receive
response
send
response
3. transaction
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
28
Queued Transaction Processing



Request-reply matching: The system guarantees that for each
request there is a reply—even if all the reply says is that the
request could not be processed.
ACID request handling: Each request is executed exactly
once. Storing the response is part of the ACID transaction.
At-least-once response handling: The client is guaranteed to
receive each response at least once. As explained previously,
there are situations where it might be necessary to present a
response repeatedly to the client. This means the client must
prepare itself for properly dealing with duplicate responses. The
important thing about the at-least-once guarantee, though, is the
fact that no responses will be lost.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999

29
Queuing Interfaces
Boolean
send(
REQUEST DoThis,
RQID rqid,
QUID ToQueue,
QUID RespQueue);

receive(QUID RespQueue,
RESPONSE KeepThat);
RESPONSE
reReceive(QUID RespQueue);
Registering a client with a queue establishes a recoverable
session between the client and the queue resource manager. This
is another example of the stateful interaction between a client and
a server. The queue resource manager remembers theRQIDs it
has processed, and the client knows whether it can send a request
to the server queue, or whether it has to wait for a response from
its input queue.
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
30
A Sample Queue Manager
Boolean send(QAttrPtr);
{
/* RM interface for enqueueing a request */
/* for simplicity no checking if the requesting */
/* rm is in session with the designated queue*/
/* insert the parameters passed into relation */
exec sql
insert into sys_queues
values (:(QAttrPtr->quid), :(QAttrPtr->q_type),
:(QAttrPtr->from_rmid),
:(QAttrPtr->to_rmid),
CURRENT,:(QAttrPtr->rqid),
:(QAttrPtr->keepthat),
:(QAttrPtr->request_response),
0, NULL); /
return(sqlcode == 0);

};
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
31
A Sample Queue Manager
Boolean
receive(QUID from_there, QAttrPtr);
{ exec sql
declare cursor dequ on
/* def scan over Q
select * FROM sys_queues where quid = :from_there
and delete_flag = NULL
order by rqid ascending
for update <some isolation clauses>;
while (TRUE)
/* try until entry is found
{ exec sql open dequ;
exec sql fetch dequ into :(QAttrPtr->QAttr);
if ( sqlcode == 0 )
/* found an entry
{ exec sql update where current of cursor dequ
set delete_flag = ‘D’;
exec sql close dequ; return(TRUE); };
exec sql CLOSE dequ;
wait(1);
};
};
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
*/

*/
*/
WICS August 2 - 6, 1999
32
Load Balancing
3
2.8
2.6
2.4
2.2
2
1.8
1.6
1.4
1.2
1
Response Time
T1 = 0.8

R = 0.9
c = 0.02
response time threshold
0
© Jim Gray, Andreas Reuter
5
10
15
20
25
30
35
40
45
50
Number of Server Processes (Concurrent Transactions)
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
33
Thrashing
Throughput
thrashing threshold

normal mode
thrashing mode
Response Time
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
WICS August 2 - 6, 1999
34
Data Affinity
request
Node
server
1
class A
scheduling
by
TP
monitor
server
class B
server
class A
server
class B
database
RPC back
server
to
disk
node 1
server
because
data reside
in partition A
database
server
disk
server
data
partition
A
© Jim Gray, Andreas Reuter
Transaction Processing - Concepts and Techniques
Node
2

scheduling
by
TP
monitor
data
partition
B
WICS August 2 - 6, 1999
35
The Authentication Problem
mail
server
SQLdatabase

userid: myself
presentation
service
click browse
function on behalf process A
authid:
of : myself
localadm
mail server
process B
authid: mailguy
request readmail
on behalf of localadm
on behalf of myself
© Jim Gray, Andreas Reuter
database system
Transaction Processing - Concepts and Techniques
process C
authid:
DBadmin
select <attribute list>
from <database> ...
on behalf of mailguy
on behalf of localadm
on behalf of myself
WICS August 2 - 6, 1999
36