Advanced Transaction Processing:Transaction-Processing Monitors

Advanced Transaction Processing

In Chapters 15, 16, and 17, we introduced the concept of a transaction, which is a program unit that accesses—and possibly updates—various data items, and whose execution ensures the preservation of the ACID properties. We discussed in those chapters a variety of schemes for ensuring the ACID properties in an environment where failure can occur, and where the transactions may run concurrently.

In this chapter, we go beyond the basic schemes discussed previously, and cover advanced transaction-processing concepts, including transaction-processing monitors, transactional workﬂows, main-memory databases, real-time databases, long-

duration transactions, nested transactions, and multidatabase transactions.

Transaction-Processing Monitors

Transaction-processing monitors (TP monitors) are systems that were developed in the 1970s and 1980s, initially in response to a need to support a large number of remote terminals (such as airline-reservation terminals) from a single computer. The term TP monitor initially stood for teleprocessing monitor.

TP monitors have since evolved to provide the core support for distributed transaction processing, and the term TP monitor has acquired its current meaning. The CICS TP monitor from IBM was one of the earliest TP monitors, and has been very widely used. Current-generation TP monitors include Tuxedo and Top End (both now from BEA Systems), Encina (from Transarc, which is now a part of IBM), and Transaction Server (from Microsoft).

TP-Monitor Architectures

Large-scale transaction processing systems are built around a client–server architecture. One way of building such systems is to have a server process for each client; the server performs authentication, and then executes actions requested by the client.

This process-per-client model is illustrated in Figure 24.1a. This model presents several problems with respect to memory utilization and processing speed:

• Per-process memory requirements are high. Even if memory for program code is shared by all processes, each process consumes memory for local data and open ﬁle descriptors, as well as for operating-system overhead, such as page tables to support virtual memory.

• The operating system divides up available CPU time among processes by switching among them; this technique is called multitasking. Each context switch between one process and the next has considerable CPU overhead; even on today’s fast systems, a context switch can take hundreds of microseconds.

The above problems can be avoided by having a single-server process to which all remote clients connect; this model is called the single-server model, illustrated in Figure 24.1b. Remote clients send requests to the server process, which then executes those requests. This model is also used in client–server environments, where clients send requests to a single-server process. The server process handles tasks, such as user authentication, that would normally be handled by the operating system. To avoid blocking other clients when processing a long request for one client, the server process is multithreaded: The server process has a thread of control for each client, and, in effect, implements its own low-overhead multitasking. It executes code on behalf of one client for a while, then saves the internal context and switches to the code for another client. Unlike the overhead of full multitasking, the cost of switching between threads is low (typically only a few microseconds).

Systems based on the single-server model, such as the original version of the IBM CICS TP monitor and ﬁle servers such as Novel’s NetWare, successfully provided high transaction rates with limited resources. However, they had problems, especially when multiple applications accessed the same database:

• Since all the applications run as a single process, there is no protection among them. A bug in one application can affect all the other applications as well. It would be best to run each application as a separate process.

• Such systems are not suited for parallel or distributed databases, since a server process cannot execute on multiple computers at once. (However, concurrent threads within a process can be supported in a shared-memory multiprocessor system.) This is a serious drawback in large organizations, where parallel processing is critical for handling large workloads, and distributed data are becoming increasingly common.

One way to solve these problems is to run multiple application-server processes that access a common database, and to let the clients communicate with the application through a single communication process that routes requests. This model is called the many-server, single-router model, illustrated in Figure 24.1c. This model supports independent server processes for multiple applications; further, each application can have a pool of server processes, any one of which can handle a client session. The request can, for example, be routed to the most lightly loaded server in a pool. As before, each server process can itself be multithreaded, so that it can handle multiple clients concurrently. As a further generalization, the application servers can run on different sites of a parallel or distributed database, and the communication process can handle the coordination among the processes.

The above architecture is also widely used in Web servers. A Web server has a main process that receives HTTP requests, and then assigns the task of handling each request to a separate process (chosen from among a pool of processes). Each of the processes is itself multithreaded, so that it can handle multiple requests.

A more general architecture has multiple processes, rather than just one, to com- municate with clients. The client communication processes interact with one or more router processes, which route their requests to the appropriate server. Later- generation TP monitors therefore have a different architecture, called the many-server, many-router model, illustrated in Figure 24.1d. A controller process starts up the other processes, and supervises their functioning. Tandem Pathway is an example of the later-generation TP monitors that use this architecture. Very high performance Web server systems also adopt such an architecture.

The detailed structure of a TP monitor appears in Figure 24.2. A TP monitor does more than simply pass messages to application servers. When messages arrive, they may have to be queued; thus, there is a queue manager for incoming messages. The queue may be a durable queue, whose entries survive system failures. Using a

durable queue helps ensure that once received and stored in the queue, the messages will be processed eventually, regardless of system failures. Authorization and application-server management (for example, server startup, and routing of messages to servers) are further functions of a TP monitor. TP monitors often provide logging, recovery, and concurrency-control facilities, allowing application servers to implement the ACID transaction properties directly if required.

Finally, TP monitors also provide support for persistent messaging. Recall that persistent messaging (Section 19.4.3) provides a guarantee that the message will be delivered if (and only if) the transaction commits.

In addition to these facilities, many TP monitors also provided presentation facilities to create menus/forms interfaces for dumb clients such as terminals; these facilities are no longer important since dumb clients are no longer widely used.

Application Coordination Using TP monitors

Applications today often have to interact with multiple databases. They may also have to interact with legacy systems, such as special-purpose data-storage systems built directly on ﬁle systems. Finally, they may have to communicate with users or other applications at remote sites. Hence, they also have to interact with communication subsystems. It is important to be able to coordinate data accesses, and to implement ACID properties for transactions across such systems.

Modern TP monitors provide support for the construction and administration of such large applications, built up from multiple subsystems such as databases, legacy systems, and communication systems. A TP monitor treats each subsystem as a re- source manager that provides transactional access to some set of resources. The in- terface between the TP monitor and the resource manager is deﬁned by a set of trans- action primitives, such as begin transaction, commit transaction, abort transaction, and prepare to commit transaction (for two-phase commit). Of course, the resource man- ager must also provide other services, such as supplying data, to the application.

The resource-manager interface is deﬁned by the X/Open Distributed Transaction Processing standard. Many database systems support the X/Open standards, and can act as resource managers. TP monitors—as well as other products, such as SQL systems, that support the X/Open standards—can connect to the resource managers.

In addition, services provided by a TP monitor, such as persistent messaging and durable queues, act as resource managers supporting transactions. The TP monitor can act as coordinator of two-phase commit for transactions that access these services as well as database systems. For example, when a queued update transaction is executed, an output message is delivered, and the request transaction is removed from the request queue. Two-phase commit between the database and the resource managers for the durable queue and persistent messaging helps ensure that, regard- less of failures, either all these actions occur, or none occurs.

We can also use TP monitors to administer complex client–server systems consisting of multiple servers and a large number of clients. The TP monitor coordinates activities such as system checkpoints and shutdowns. It provides security and authentication of clients. It administers server pools by adding servers or removing servers without interruption of the system. Finally, it controls the scope of failures. If a server fails, the TP monitor can detect this failure, abort the transactions in progress, and restart the transactions. If a node fails, the TP monitor can migrate transactions to servers at other nodes, again backing out incomplete transactions. When failed nodes restart, the TP monitor can govern the recovery of the node’s resource managers.

TP monitors can be used to hide database failures in replicated systems; remote backup systems (Section 17.10) are an example of replicated systems. Transaction

requests are sent to the TP monitor, which relays the messages to one of the database replicas (the primary site, in case of remote backup systems). If one site fails, the TP monitor can transparently route messages to a backup site, masking the failure of the ﬁrst site.

In client–server systems, clients often interact with servers via a remote-procedure- call (RPC) mechanism, where a client invokes a procedure call, which is actually executed at the server, with the results sent back to the client. As far as the client code that invokes the RPC is concerned, the call looks like a local procedure-call invocation. TP monitor systems, such as Encina, provide a transactional RPC interface to their services. In such an interface, the RPC mechanism provides calls that can be used to enclose a series of RPC calls within a transaction. Thus, updates performed by an RPC are carried out within the scope of the transaction, and can be rolled back if there is any failure.

24.2 Transactional Workﬂows

A workﬂow is an activity in which multiple tasks are executed in a coordinated way by different processing entities. A task deﬁnes some work to be done and can be speciﬁed in a number of ways, including a textual description in a ﬁle or electronic- mail message, a form, a message, or a computer program. The processing entity that

performs the tasks may be a person or a software system (for example, a mailer, an application program, or a database-management system).

Figure 24.3 shows examples of workﬂows. A simple example is that of an electronic- mail system. The delivery of a single mail message may involve several mailer systems that receive and forward the mail message, until the message reaches its destination, where it is stored. Each mailer performs a task—forwarding the mail to the next mailer—and the tasks of multiple mailers may be required to route mail from source to destination. Other terms used in the database and related literature to refer to workﬂows include task ﬂow and multisystem applications. Workﬂow tasks are also sometimes called steps.

In general, workﬂows may involve one or more humans. For instance, consider the processing of a loan. The relevant workﬂow appears in Figure 24.4. The person who wants a loan ﬁlls out a form, which is then checked by a loan ofﬁcer. An employee who processes loan applications veriﬁes the data in the form, using sources such as credit-reference bureaus. When all the required information has been collected, the loan ofﬁcer may decide to approve the loan; that decision may then have to be approved by one or more superior ofﬁcers, after which the loan can be made.

Each human here performs a task; in a bank that has not automated the task of loan processing, the coordination of the tasks is typically carried out by passing of the loan application, with attached notes and other information, from one employee to

the next. Other examples of workﬂows include processing of expense vouchers, of purchase orders, and of credit-card transactions.

Today, all the information related to a workﬂow is more than likely to be stored in a digital form on one or more computers, and, with the growth of networking, information can be easily transferred from one computer to another. Hence, it is feasible for organizations to automate their workﬂows. For example, to automate the tasks involved in loan processing, we can store the loan application and associated information in a database. The workﬂow itself then involves handing of responsibility from one human to the next, and possibly even to programs that can automatically fetch the required information. Humans can coordinate their activities by means such as electronic mail.

We have to address two activities, in general, to automate a workﬂow. The ﬁrst is workﬂow speciﬁcation: detailing the tasks that must be carried out and deﬁning the execution requirements. The second problem is workﬂow execution, which we must do while providing the safeguards of traditional database systems related to computation correctness and data integrity and durability. For example, it is not acceptable for a loan application or a voucher to be lost, or to be processed more than once, because of a system crash. The idea behind transactional workﬂows is to use and extend the concepts of transactions to the context of workﬂows.

Both activities are complicated by the fact that many organizations use several independently managed information-processing systems that, in most cases, were developed separately to automate different functions. Workﬂow activities may re- quire interactions among several such systems, each performing a task, as well as interactions with humans.

A number of workﬂow systems have been developed in recent years. Here, we study properties of workﬂow systems at a relatively abstract level, without going into the details of any particular system.

Workﬂow Speciﬁcation

Internal aspects of a task do not need to be modeled for the purpose of speciﬁcation and management of a workﬂow. In an abstract view of a task, a task may use parameters stored in its input variables, may retrieve and update data in the local system, may store its results in its output variables, and may be queried about its execution state. At any time during the execution, the workﬂow state consists of the collection of states of the workﬂow’s constituent tasks, and the states (values) of all variables in the workﬂow speciﬁcation.

The coordination of tasks can be speciﬁed either statically or dynamically. A static speciﬁcation deﬁnes the tasks—and dependencies among them—before the execution of the workﬂow begins. For instance, the tasks in an expense-voucher workﬂow

may consist of the approvals of the voucher by a secretary, a manager, and an accountant, in that order, and ﬁnally by the delivery of a check. The dependencies among the tasks may be simple—each task has to be completed before the next begins.

A generalization of this strategy is to have a precondition for execution of each task in the workﬂow, so that all possible tasks in a workﬂow and their dependencies are known in advance, but only those tasks whose preconditions are satisﬁed are executed. The preconditions can be deﬁned through dependencies such as the following:

• Execution states of other tasks—for example, “task ti cannot start until task tj has ended,” or “task ti must abort if task tj has committed”

• Output values of other tasks—for example, “task ti can start if task tj re- turns a value greater than 25,” or “the manager-approval task can start if the secretary-approval task returns a value of OK”

• External variables modiﬁed by external events—for example, “task ti cannot be started before 9 AM,” or “task ti must be started within 24 hours of the completion of task tj ”

We can combine the dependencies by the regular logical connectors (or, and, not) to form complex scheduling preconditions.

An example of dynamic scheduling of tasks is an electronic-mail routing system. The next task to be scheduled for a given mail message depends on what the destination address of the message is, and on which intermediate routers are functioning.

Failure-Atomicity Requirements of a Workﬂow

The workﬂow designer may specify the failure-atomicity requirements of a work- ﬂow according to the semantics of the workﬂow. The traditional notion of failure atomicity would require that a failure of any task results in the failure of the work- ﬂow. However, a workﬂow can, in many cases, survive the failure of one of its tasks— for example, by executing a functionally equivalent task at another site. Therefore, we should allow the designer to deﬁne failure-atomicity requirements of a workﬂow. The system must guarantee that every execution of a workﬂow will terminate in a state that satisﬁes the failure-atomicity requirements deﬁned by the designer. We call those states acceptable termination states of a workﬂow. All other execution states of a workﬂow constitute a set of nonacceptable termination states, in which the failure- atomicity requirements may be violated.

An acceptable termination state can be designated as committed or aborted. A committed acceptable termination state is an execution state in which the objectives of a workﬂow have been achieved. In contrast, an aborted acceptable termination state is a valid termination state in which a workﬂow has failed to achieve its ob- jectives. If an aborted acceptable termination state has been reached, all undesirable effects of the partial execution of the workﬂow must be undone in accordance with that workﬂow’s failure-atomicity requirements.

A workﬂow must reach an acceptable termination state even in the presence of system failures. Thus, if a workﬂow was in a nonacceptable termination state at the time of failure, during system recovery it must be brought to an acceptable termination state (whether aborted or committed).

For example, in the loan-processing workﬂow, in the ﬁnal state, either the loan applicant is told that a loan cannot be made or the loan is disbursed. In case of failures such as a long failure of the veriﬁcation system, the loan application could be returned to the loan applicant with a suitable explanation; this outcome would constitute an aborted acceptable termination. A committed acceptable termination would be either the acceptance or the rejection of the loan.

In general, a task can commit and release its resources before the workﬂow reaches a termination state. However, if the multitask transaction later aborts, its failure atomicity may require that we undo the effects of already completed tasks (for example, committed subtransactions) by executing compensating tasks (as subtransactions). The semantics of compensation requires that a compensating transaction eventually complete its execution successfully, possibly after a number of resubmissions.

In an expense-voucher-processing workﬂow, for example, a department-budget balance may be reduced on the basis of an initial approval of a voucher by the manager. If the voucher is later rejected, whether because of failure or for other reasons, the budget may have to be restored by a compensating transaction.

Execution of Workﬂows

The execution of the tasks may be controlled by a human coordinator or by a soft- ware system called a workﬂow-management system. A workﬂow-management sys- tem consists of a scheduler, task agents, and a mechanism to query the state of the workﬂow system. A task agent controls the execution of a task by a processing entity. A scheduler is a program that processes workﬂows by submitting various tasks for execution, monitoring various events, and evaluating conditions related to inter- task dependencies. A scheduler may submit a task for execution (to a task agent), or may request that a previously submitted task be aborted. In the case of multi- database transactions, the tasks are subtransactions, and the processing entities are local database management systems. In accordance with the workﬂow speciﬁcations, the scheduler enforces the scheduling dependencies and is responsible for ensuring that tasks reach acceptable termination states.

There are three architectural approaches to the development of a workﬂow-management system. A centralized architecture has a single scheduler that schedules the tasks for all concurrently executing workﬂows. The partially distributed architecture has one scheduler instantiated for each workﬂow. When the issues of concurrent execution can be separated from the scheduling function, the latter option is a natural choice. A fully distributed architecture has no scheduler, but the task agents coordinate their execution by communicating with one another to satisfy task dependencies and other workﬂow execution requirements.

The simplest workﬂow-execution systems follow the fully distributed approach just described and are based on messaging. Messaging may be implemented by persistent messaging mechanisms, to provide guaranteed delivery. Some implementations use e-mail for messaging; such implementations provide many of the features of persistent messaging, but generally do not guarantee atomicity of message deliv- ery and transaction commit. Each site has a task agent that executes tasks received through messages. Execution may also involve presenting messages to humans, who have then to carry out some action. When a task is completed at a site, and needs to be processed at another site, the task agent dispatches a message to the next site. The message contains all relevant information about the task to be performed. Such message-based workﬂow systems are particularly useful in networks that may be disconnected for part of the time, such as dial-up networks.

The centralized approach is used in workﬂow systems where the data are stored in a central database. The scheduler notiﬁes various agents, such as humans or computer programs, that a task has to be carried out, and keeps track of task completion. It is easier to keep track of the state of a workﬂow with a centralized approach than it is with a fully distributed approach.

The scheduler must guarantee that a workﬂow will terminate in one of the spec- iﬁed acceptable termination states. Ideally, before attempting to execute a workﬂow, the scheduler should examine that workﬂow to check whether the workﬂow may terminate in a nonacceptable state. If the scheduler cannot guarantee that a workﬂow will terminate in an acceptable state, it should reject such speciﬁcations without at- tempting to execute the workﬂow. As an example, let us consider a workﬂow consist- ing of two tasks represented by subtransactions S1 and S2, with the failure-atomicity requirements indicating that either both or neither of the subtransactions should be committed. If S1 and S2 do not provide prepared-to-commit states (for a two-phase commit), and further do not have compensating transactions, then it is possible to reach a state where one subtransaction is committed and the other aborted, and there is no way to bring both to the same state. Therefore, such a workﬂow speciﬁcation is unsafe, and should be rejected.

Safety checks such as the one just described may be impossible or impractical to implement in the scheduler; it then becomes the responsibility of the person designing the workﬂow speciﬁcation to ensure that the workﬂows are safe.

Recovery of a Workﬂow

The objective of workﬂow recovery is to enforce the failure atomicity of the work- ﬂows. The recovery procedures must make sure that, if a failure occurs in any of the workﬂow-processing components (including the scheduler), the workﬂow will even- tually reach an acceptable termination state (whether aborted or committed). For ex- ample, the scheduler could continue processing after failure and recovery, as though nothing happened, thus providing forward recoverability. Otherwise, the scheduler could abort the whole workﬂow (that is, reach one of the global abort states). In ei- ther case, some subtransactions may need to be committed or even submitted for execution (for example, compensating subtransactions).

We assume that the processing entities involved in the workﬂow have their own local recovery systems and handle their local failures. To recover the execution-environment context, the failure-recovery routines need to restore the state information of the scheduler at the time of failure, including the information about the execution states of each task. Therefore, the appropriate status information must be logged on stable storage.

We also need to consider the contents of the message queues. When one agent hands off a task to another, the handoff should be carried out exactly once: If the handoff happens twice a task may get executed twice; if the handoff does not occur, the task may get lost. Persistent messaging (Section 19.4.3) provides exactly thefeatures to ensure positive, single handoff.

Workﬂow Management Systems

Workﬂows are often hand coded as part of application systems. For instance, enterprise resource planning (ERP) systems, which help coordinate activities across an entire enterprise, have numerous workﬂows built into them.

The goal of workﬂow management systems is to simplify the construction of work- ﬂows and make them more reliable, by permitting them to be speciﬁed in a high-level manner and executed in accordance with the speciﬁcation. There are a large number of commercial workﬂow management systems; some, like Flow Mark from IBM, are general-purpose workﬂow management systems, while others are speciﬁc to particular workﬂows, such as order processing or bug/failure reporting systems.

In today’s world of interconnected organizations, it is not sufﬁcient to manage workﬂows only within an organization. Workﬂows that cross organizational boundaries are becoming increasingly common. For instance, consider an order placed by an organization and communicated to another organization that fulﬁlls the order. In each organization there may be a workﬂow associated with the order, and it is important that the workﬂows be able to interoperate, in order to minimize human intervention.

The Workﬂow Management Coalition has developed standards for interoperation between workﬂow systems. Current standardization efforts use XML as the under- lying language for communicating information about the workﬂow. See the biblio- graphical notes for more information.

Search This Blog

Database Management System course