6.3.1.1 Defining the System Control Blocks

To keep things manageable, it helps to have one starting point from which all data structures can be tracked down, rather than a bundle of unrelated structures that can be located only via their names in a program. Thus, above all there is an anchor data structure providing access to the other global data structures. Its declare looks like this:

Of course, a real system anchor contains more than what is shown in the example. The TPOS_Anchor is one well-defined point in the TPOS, from which all the system data structures can be reached (provided the requestor has the required access privileges). Each resource manager is assumed to have its own local anchor, where this resource manager’s data structures are rooted. Keeping the pointers to these anchors in the TPOS_Anchor ensures that addressability can be established in an orderly manner upon system startup; this is necessary, because the TPOS comes up before any of the resource managers is activated. Note that although all the data structures to be introduced are global TPOS data structures (in that they are required for all activities of the TPOS), each one is “owned” by one of the system resource managers, which tries to hide them (that is, their physical organization) from the other components of the TPOS. The degree to which this can be done depends on the flexibility of domain protection offered by the underlying operating system.

The declaration in our example assumes five system resource managers: the TP monitor, the transaction manager, the log manager, the lock manager, and the communication manager. This is a basic set; real systems might have more.

The anchor of a system resource manager has no fixed layout; it is declared by each resource manager for itself. The TP monitor’s anchor might have the following structure:

The resource manager control blocks and the others rooted at TPAnchor need more than just declarative treatment; accordingly, they are introduced immediately following the description of the global data structures. Figure 6.7 gives an overview of which data structures the TPOS keeps in its different components and how they are related. To be precise: only the global data structures entertained by the TP monitor and the transaction manager are fully shown, because these are the ones needed for handling TRPCs. For the remaining system resource managers, Figure 6.7 shows the anchor structure but none of the global data structures managed by these components.

The flags attached to the control blocks in Figure 6.7 serve as metaphors for a special data type that has not yet been introduced: the semaphore. As explained in Chapter 8, semaphores are used to control the access of concurrent processes to data structures in shared memory. It is important to understand that the control blocks shown in Figure 6.7 will be heavily accessed, because the TPOS executes on behalf of virtually every process in the system. Since the control blocks are threaded together through different types of linked lists, it is important that update operations on these link structures be consistent. Consistency can be lost if different processes access the same control block simultaneously, applying contradictory updates to it. Again, exactly how this can happen is a subject of Chapter 8; for the the moment, just accept that the little flags called semaphores help to make sure that a process can operate on these central data structures without being disturbed by other processes.

The small control blocks in the lower part of Figure 6.7 are used to establish fast cross-references from one type of control block to the other; they are explained in Subsection 6.3.2. Before we come to that, let us introduce the access functions to the TPOS’s major control blocks.

6.3.1.2 Accessing the Central Data Structures of the TPOS

There is one system resource manager that is responsible for and encapsulates each type of control block in the central data structures. For example, the TP monitor is responsible for the resource manager control blocks, the process control blocks, and the session control blocks. The transaction manager is responsible for the transaction control blocks, and so on. The cross-reference control blocks are maintained by the resource manager at whose control block they are rooted.

Whenever a component of the TPOS executes one of its functions, the characteristics of transactional remote procedure calls require the TPOS to know:

In many cases, it also important to get the resource manager ID of the client that called upon the system resource manager. Based on such an identifier, the routine might request detailed information about the process, transaction, or resource manager. Of course, such data could be passed along with each TRPC, as is the case with remote invocations. But for local invocations, it is much more efficient to use the central control blocks where all this environmental information is kept.

For the purposes of this and the following chapters, we define a set of functions that allow controlled access of the TPOS’s data structures. Here is the list of function prototype definitions:

These functions can be called from any process running in the transaction system. The three types of identifiers returned are accessible to anybody involved in the processing and thus need no additional privilege for reading them. The next group of functions is not as public; their use is restricted to system resource managers that form core parts of the TPOS. The ways of enforcing these access restrictions are not discussed here; just keep in mind that an arbitrary application is not allowed to call the functions declared in the following example code.

The data structures that are returned by these functions will be explained as we go along. Processes that are entitled to call, say, MyTrans will get a copy of all descriptive data for their current transaction, but no linkage information from there to other control blocks. Access to that kind of data is reserved to those who are allowed to invoke MyTransP.

6.3.2.1 Declaring the Control Blocks

To start with, there must be a data structure for each of the entity types shown in Figure 6.8, and there must be an efficient way of maintaining the relationships among them. The following declarations are not meant to represent an actual implementation; rather, they contain a number of simplifications that keep the descriptions of the algorithms simple.

The first simplification is to assume a linked list of control blocks for the instances of each entity type, as is shown in the declares that follow. We could have as easily declared them as relations and used SQL to get to the required entries—this would have gone well with the explanations of the principles underlying the implementation of a TP monitor.

The first group of declares contains everything the TP monitor needs to know at run time about the resource managers installed at that node. The declares for the semaphores in Figure 6.7 have been left out to avoid confusion; but, of course, in a real system they have to be there. Note there is no control block for server classes. But, as Figure 6.8 indicates, at each node there is a 1:1 relationship between resource managers and server classes, so both entity types are represented by just one type of control block.

This is but the skeleton of a resource manager control block; for a complete system, more entries would be needed. However, the ones shown here are sufficient for the explanations of the TP monitor algorithms in the next sections. Note also that in a system that makes use of the address space/protection domain facility described in Chapter 2, there would not be just one central resource manager control block. Rather, the TP monitor would have one control block with the entries it needs, the transaction manager would have another one, the log manager would keep resource manager control blocks, and so on. (This aspect is ignored during the following presentations.)

The process control block is simple in comparison to the resource manager control block:

The third group of objects for which the TP monitor is responsible is the sessions among clients and servers. There is not very much to remember about them from the TP monitor’s point of view. Note, however, that in case one end of the session is at a remote site, communication will travel along a communication session, for which the communication manager is responsible. These sessions typically are not established and released on a pertransaction basis; the cost for that would be prohibitively high. Rather, sessions are maintained between processes in different nodes over longer periods of time (in much the same spirit as the Bind/Unbind mechanism); but since they can at any point in time be used by only one transaction, it is possible to recover the state of each session in accord with the ACID paradigm. The communications manager must, of course, behave like a transactional resource manager and keep enough information about the activities of each session to able to roll back in case of a transaction failure. This is described in some detail in Chapter 12. The communications manager must also keep track of which transactions are associated with which sessions (via their processes), since it might receive messages from the network saying that a certain session is broken because of a link failure, or because the other node crashed. Those messages must then be translated into an abort message for the affected local transaction.

Now that the data structures for the entity types have been established, we need the control blocks for the cross-references among the entity types. Let us start with the control block for the m:n relationship between resource managers and transactions. Since this chapter is on the TP monitor, these control blocks are rooted in the RMCB; they might as well be rooted in the TACB, or in both.

The interesting thing about this data structure is the variable DatalNeed. It allows a resource manager (not a particular process from its server class) to maintain context for a transaction. This is a simple version of the context management techniques depicted in Figure 6.5. The way it is declared here is a mixture of keeping context data in the database and of putting it into shared memory.

Another type of control block rooted at RMCB is needed to implement volatile queues. These queues have to be kept in cases where there are more TRPCs for a resource manager than the server class has processes—and where the TP monitor for some reason decides not to create new processes. (See Section 6.4 for details.)

The entries ClientType and Clientlnst are provided to support detection of deadlocks that are caused by suspended TRPCs.

Two lists relate processes to server classes, as shown in Figure 6.8. The first one lists all the processes that may switch to a server class (i.e., to its address space), and it holds a flag saying if this is one of the processes that has been allocated for that server class. Note that the same information is also kept in the PCB entry InstanceOf.

The second list starting at PCB contains the RMIDs whose code a process is allowed to execute. That is, it can switch to the address space of the corresponding server class.

The other reference data structures mentioned in Figure 6.7 are organized in exactly the same way and therefore need not be spelled out explicitly. The transaction control block and the data structures that go with it are introduced in Chapter 11, Section 11.2.

When describing the algorithms for handling TRPCs, it will be convenient to have routines that access the control blocks declared above (such as RMCB, PCB) via their primary keys. Of course, these routines can be used only inside the components owning the respective control block. From the outside, the more restricted retrieval operations introduced at the beginning of this subsection are available.

The ancillary routines perform the following function: given the identifier of the object type, they return the pointer to the corresponding control block upon lookup, or they return the pointer to a newly allocated control block upon insert. The following prototype declaration illustrates this for the RMCB:

The operation is INSERT if a new control block is required for the given RMID, in which case there must be no existing entry with that RMID. The function returns the pointer to the control block that has been allocated for the new resource manager. If the operation is LOOKUP, the function returns the pointer to the control block belonging to the given RMID. In either case, the function returns NULL if something goes wrong. Note that access is defined via the RMID; one can easily imagine an equivalent function for accessing RMCB via RMNAME. Similar functions are assumed for the process and the session control block.

6.3.3.1 Local Call Processing

A TRPC comes from an application or resource manager running in some process. Whether it is the process’s own resource manager calling or not makes no difference at all. We assume the do-it-yourself format of the call introduced in Subsection 6.2.1, and now look at the corresponding entry in the TRPC stub. As pointed out repeatedly, this is part of each address space, so it is just a subroutine call to rmCall. This routine starts out checking what kind of request has been issued. It should be easy to get this information by following the (pseudo-) code for the first part of rmCall.

As can be seen, the stub code is mostly concerned with figuring out where to send the request. If the request is local, the stub code authorizes the client; the methods for that are presented in Section 6.5. It then decides whether it can hold on to the client’s process and just do a domain switch, or if it has to find another process that is authorized to execute the callee’s code. For the first case, we assume a procedure DomainSwitch that hides all the operating system-specific aspects involved. Finding a process is the task of the TP monitor’s scheduler. The considerations going into that decision are also described in Section 6.5. The scheduler comes up with one out of three possible decisions: first, if too much is going on locally, then send the request to another node, even though the service is locally available. Thus, we have to continue at the point where outgoing requests are handled, represented by the routine RemoteRMC. The second possible decision is to put the requesting process on a waiting queue in front of the resource manager to which the TRPC is going. This problem is discussed in Section 6.4. The third possibility is to pick an idle process and send the request to it; this is done using the routine SendIPC.

In the event the TRPC flows along a preestablished session, the TP monitor has only to forward the request to the other end point of the session, which is completely identified in the rmlnstance that serves as a handle for that session.

The problem of binding the resource manager name to a server class is slightly simplified in the program just given. Strictly speaking, a TRPC name consists of a tuple 〈resource manager name, entry name〉. Thus, name binding of a resource manager at one of its entry points requires the name resolution and address binding of both components of the tuple.

Binding an RMNAME to an RMID is done through the repository, which holds the information about each RMNAME in the (distributed) system as to where the service is available, and under which RMID. The TP monitor caches these binding data as far as possible; we will not discuss that in detail. If you look closely at the declarations of the RMCB and its related data structures, you will find that they are designed to cache binding information.

Binding the entry name is straightforward. It is assumed that a resource manager, at the moment it is installed by the TP monitor, declares all its service and callback entries. Since the TP monitor loads the code for the resource managers into the address spaces it has allocated for them, and since all processes in one server class have identical structures, the addresses of all the entries are known to the TP monitor. In some implementations of TP systems, the code of resource managers may have to be relocated in their address spaces at run time, but this complication is ignored here.

Figure 6.10 summarizes the name binding to be done by the TP monitor.

6.3.3.2 Preparing Outgoing Calls

If a request has to be sent to a distant node, the major work is done by the communication manager, which is responsible for setting up and maintaining the communication sessions among processes. First, the TRPC stub in the TP monitor formats the message to be sent; this is almost identical to what a standard RPC stub does, except for the TRID that is appended to the message. If the request goes along a predefined session, the handle provided by the communication manager is put in the message header as an indication for the communication manager to use that session. The handle is kept by the TP monitor in the SECB.

The communication manager takes the message and checks if it has seen this transaction going out on that session before. It does so by checking the entry UsedBy in the SECB. If this is the first time, it stores req_trid in UsedBy and calls the transaction manager to inform it that this transaction is leaving the node on an outgoing session. As will be seen in Chapter 11, the transaction manager needs to know this for two reasons: first, it must include the remote resource managers in the commit decision, and because it cannot invoke them directly, it must go through the communication manager. Second, the session itself needs to be transaction protected, so that the communication manager becomes another local participant in this transaction. (This is also discussed in Chapter 10.)

6.3.3.3 Incoming Call Processing

This description can be kept short. As a request arrives from the network, it is delivered to the communication manager first. The communication manager goes through a logic similar to that of the rmCall in the case of local call processing:

If the incoming request travels along a preestablished session, then there is already a process allocated to it. Actually, this process has been suspended in its TRPC stub while waiting for the next request via this session. Thus, all the communication manager has to do is unpack the message (the inverse of what has been described for the preparation of outgoing calls) and then wake up the other end of the session; this means routing the call to the “right” resource manager process.

If there is no preestablished session, a process must be scheduled to handle the request. The option of just switching address spaces must be ruled out in this case, because the communication manager wants to hold on to its process in order to be able to handle other incoming and outgoing messages. Therefore, the scheduler of the TP monitor has to find a process that can execute in the address space of the requested server class. The process control block is then set up just as for local call processing.

There is one situation that has not yet been considered: assume the request comes in and there is no session on the receiving side for it, but the requestor’s side sends a handle along, thus indicating that a session should be established (see the description of the rmBind function in Section 6.2). In this case, the communication manager has to go through its logic for establishing a session (authenticate the requestor, for example). After that is done, it has to create a new SECB for that session and have the TP monitor allocate a process for it, which is from then on bound to that session. Of course, the Bindld, which is the application-level identifier of the session, is passed on to the server so that it knows it is in session with the client.

In accord with the logic of outgoing calls, the communication manager calls the transaction manager to inform it about the arrival of a new transaction on a session from the network. This also has to do with commit processing, although the role of the local transaction manager is different than in the previous case.

6.3.3.4 Call Delivery

Assume that a domain switch has been performed. The process executing the TRPC now continues in the TRPC stub of the callee’s address space at the location where incoming calls from local processes are received. There is not much left to do before the resource manager can start working on the request. The first step is optional: the resource manager might want to do some additional authorization of the client’s request, which for security reasons has to be performed in its own protection domain rather than outside.

The second step is strictly related to the logic of transactional RPC. The TP monitor has to check if the resource manager has already checked in with the transaction manager for the current transaction. Sophisticated resource managers could do that themselves, but simple resource managers cannot, and so it is good idea to have the TP monitor do it for them. This is the logic (we assume the same variable names and declarations as in the discussion of local call processing):

The effects of Join_Work are described in Chapter 10. Note that in case the incoming request has no TRID—which is quite possible if it is a message from a dumb terminal—the TP monitor cannot check in the resource manager with the transaction manager. What will happen (most likely) is that the resource manager will call Begin_Work, and as a consequence of that, the transaction manager will automatically register the resource manager as a participant of that new transaction. Once all this is done, the resource manager can start unpacking the message and act on it.

6.3.3.5 Call Return

The logic of call return handling is essentially the same, no matter which way the TRPC went. There are slight variations, though, with respect to the clean-up work in the global data structures. A TRPC returning within the same process (coming back from a domain switch) is like a return from a subroutine call. The only thing the TP monitor has to do is restore the entries Runsln and ClientID in the process control block. A return from an outgoing call looks just like a return from a local call with a process switch involved, because the response message is first received by the communication manager, who sends it (via IPC) to the caller’s process. In either case, the caller’s process is suspended in the TRPC stub, waiting to be woken up again with a response message.

We can restrict the description to the case of a local return from a TRPC handled by another process. The administrative work on the TP monitor’s part consists of two things: first, the process control block of the returning process must be reset; second, requests must be checked to see if there are any waiting in front of the resource manager that just completed, so that the process can immediately be scheduled for one of them. This is the logic:

If no unserviced requests are waiting, the process enters the wait state by invoking an operating system service called “wait,” which is described in Chapter 8. For convenience, our code here is written as though it were executed in the process of the original caller, which it is not. Given all the previous arguments, the reader should be able to figure out which process actually activates the process waiting in the resource manager’s request queue.

6.4.2.1 The Client’s View of Queued Processing

Queues in the sense described here allow such questions to be asked. They maintain durable information about the association between different resource managers. Remember that in our “favorite” model of transaction systems, each end point (workstation) will be represented in the system by at least one resource manager that manages the local context and presentation services. Since each request, as well as each response, is recorded durably in a queue, there is a history of resource manager interactions that makes it possible to determine specifically what happened last between a certain client and its server. Put another way, if the client has crashed and later restarts, the client can go back to its response queue and check which response was last delivered to it before the crash. The behavior of such queue-oriented client-server interactions can be characterized by three properties.

Figure 6.14 shows the corresponding state diagram for the behavior of the client with respect to one request. The client has to be connected to the queueing system in order to issue requests. It then can switch back and forth between sending requests to servers and receiving responses from them. Finally, it can disconnect from the queueing system, but only after having received all responses it has asked for.

To achieve the guarantees just listed, a mechanism for relating requests to responses must be in place. The obvious way to determine which request corresponds to which response is to have a unique identifier for each request (RQID), supplied by the client, which is returned with the response. There is no need for these identifiers to be contiguous. The requests they are attached to are manipulated inside ACID transactions; consequently, there can be no holes due to lost messages or anything like that. For convenience, let us assume the TRID of the transaction issuing the request is used as the RQID.

6.4.2.2 The Client Interface to the Queueing System

With these preparations, we can now define the client’s interface to the queueing system of the TPOS. Each queue is identified in much the same way resource managers are identified; in fact, the queueing system can best be thought of as a special resource manager that handles request and response queues. Thus, each queue has a globally unique name and a locally unique queue identifier, which is reflected in the following declares:

Before describing the functions for connecting to the queueing system, let us consider the operations that can be invoked once connection has been established. For our simple processing model, three operations are sufficient:

Registering a client with a queue establishes a recoverable session between the client and the queue resource manager. This is another example of a stateful interaction between a client and a server. The queue resource manager remembers the RQIDs 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. The session is recoverable in that after a crash of either side, it can be resumed with all state information reestablished as of the last successful transaction that updated the queue. The function prototypes for opening and closing a session with a queue are as follows:

The key point is that a session between a client and a queue can only be closed if there are no responses that have not yet been received by the client. By calling disconnect, the client explicitly states that it has properly processed all replies and waives all rights of future inquiries into the state of that session. In case of a failure, however, the session is kept up by the system (or is recovered if the entire node fails), and the client has to call connect after restart. The client then gets back the state of the session as declared above. This state is characterized by the RQID of the last request entered in the queue and by the RQID of the last response received by the client (more precisely, the RQID of the request that triggered this response). Excluding special error conditions, there are two cases to consider:

6.4.2.3 Implementation of the Queue Resource Manager

Queues have to maintain durable, transaction-protected state. As later chapters will show, it is hard to implement something like this with only a simple (non-transactional) file system underneath. A much simpler approach—and the one taken here—is to offload all the problems related to durable state to somebody else and just focus on the queue-specific aspects. In addition to greatly simplifying the discussion, that approach has the advantage of demonstrating the power of the resource manager architecture that is the leitmotif of this book. In order to turn a simple queue manager into a regular resource manager, we only have to support the resource manager interfaces described earlier and provide the callback entries for the various transaction-specific events. The SQL resource manager takes care of the durable storage, and the TPOS, with all its transaction-oriented services, makes sure that the interaction among all components involved comes out as an ACID transaction.

To keep things simple, assume that all queues are maintained in a single relation that has been created by the following statement:

It is assumed that the binding of quid to the corresponding quname is done in the repository. All the attributes have been discussed before, with three exceptions:

The sessions between “other” resource managers and the queue resource manager are stored in a separate relation that has the following schema:

The attribute role denotes whether the rmid participates in the session as a client or as a server.

The functions provided by the queue resource manager either establish sessions between a queue and a resource manager, or they act on entries of a single queue object; that is, on entries pertaining to one quid. This is important to note, because the client interface to the queue resource manager we have described permits referencing more than one queue object per call; see the description of the send function earlier in this section.

The first function is the send which appends an entry to a specified queue. Here is the implementation:

At first glance, one might wonder why the insert pays no attention to any queueing discipline; in particular, there are no provisions for making sure that the new entry is appended at the end of the queue. That is because of the decision to use relations as the implementation vehicle for the queues. Tuples in relations have no system-maintained order whatsoever. If the user wants them ordered, he has to specify a sort order based on the attributes in the relation when retrieving them. In other words, the effective queueing discipline depends on how the tuples are selected when deciding which one to remove from the queue. This is part of the second operation provided by the queue resource manager, the receive function.

These are the two service interfaces of the queue resource manager. It calls the database manager using embedded SQL but so far makes no references to other (system) resource managers. What about its callback entries for transaction handling? Some careful thought to this matter shows that there is actually nothing to do. For example, at startup the queue manager has neither control blocks to initialize nor anything else like that. Its callback entry therefore looks like this:

The queue resource manager’s logic during commit processing is not sophisticated, either; whenever it is asked about the outcome of a transaction, it votes Yes:

The other callback entries look exactly the same. Neither has the queue manager any updates to undo (SQL does that), nor is there any savepoint state to write to the log, and so on. Joining the queue manager to a transaction is done automatically by the TP monitor, as described previously.

The result of these considerations, then, is that the code for the transactional queue resource manager is strikingly simple. There is really nothing else to do. And although it looks like a straightforward sequential program, the queue resource manager runs in a multiuser environment and maintains its objects under the protection of ACID transactions. This little example shows that writing resource managers in a transaction processing system is simple—provided they do not keep their own state. Keep this in mind as a general rule for dealing with such systems: whenever possible, have a transactional database system that is able to act as a resource manager to take care of your data; don’t mess around with files.

Of course, this is not a comprehensive implementation of a queue resource manager. The coding is not defensive at all, and except for the functions to establish a session between a resource manager and a queue, further administrative functions are required for a complete queueing system. For example, there must be a way for the client to retract requests it no longer wants to be executed, or requests that have turned out to be invalid for other reasons (see Subsection 6.4.2.4). However, adding all this would not change the basic simplicity of the queue resource manager; it would only be more of the same.

6.4.2.4 Some Details of Implementing Transactional Queues

Two interesting details about transactional queues can be observed in the code for the dequeue function. The cryptic remark in our program about “some isolation clauses” refers to the same problem that has already been discussed for the volatile queues: since many server processes can operate on the same queue concurrently, they must protect themselves against each other. For the in-memory queues maintained by the TP monitor, critical sections are the appropriate solution. Durable queues implemented as SQL relations require a slightly different approach.

As we will see in the next two chapters, SQL database systems have a whole set of mechanisms for coordinating the operations of concurrent transactions on shared data. Without using concepts that have not yet been introduced, let us briefly consider the queue-specific problems. Dequeueing an element from a queue is part of a transaction; that is, if the transaction fails, the element must remain in the queue. Now if some transaction T_a has dequeued the first element E₁ no other transaction can take it (exactly-once semantics). On the other hand, E₁ is still the “first element”—the one with the lowest RQID. Thus, each concurrent access asking for the first element will be directed to E₁. And, of course, one cannot say it is no longer there; if T_a aborts, E₁ will remain in the queue as the first element. The only solution preserving FIFO processing in a strict sense would require all other transactions to wait until the fate of T_a is known. If T_a commits, then there is a new “first element”; if it aborts, another transaction will pick up E₁. This, however, is not acceptable from a performance perspective. The following, then, is what the SQL clause not spelled out in the code example says: scan the tuples in the selected queue in their RQID order, but if you find one that is currently being worked on by another transaction, skip it and try the next tuple.

The second remark has to do with a fairly subtle detail of queued transaction processing. If something goes wrong in a direct transaction, the transaction is rolled back, and the user can decide how to react to that. With queued transactions, the first step consists of putting the request into a server queue. Now assume the request is invalid in some way, causing the server transaction to abort. What will happen?

A server process receives the faulty request as part of its processing transaction and sooner or later has to invoke Rollback_Work. As a result, the request reappears in the queue, only to be picked up by the next server process, which also aborts its transaction, and so forth. Given a thoroughly corrupted request, this could go on forever. It is therefore a good idea to have a counter that contains the number of rollbacks caused by the request associated with each queue entry—this is what the attribute no_dequeues is there for. It is set to zero when the tuple is stored, and the plan is to increase it by one each time a transaction having received this entry aborts. The question, though, is how to do that. It basically requires that an aborting transaction produce a durable update—which, by definition, it can’t. There are three obvious approaches to solving this problem:

No aborts. One could rule out the use of transaction abort for the server, forcing it to masquerade all failed transactions as successful ones. In this scenario, if something goes wrong, the server calls rollback to savepoint 1, which is the state of the transaction right after executing Begin_Work. It then updates the tuple in the sys_queues relation, setting the delete_flag back to NULL and increasing no_dequeues. After that, it calls Commit_Work.

Unprotected updates. If the update of the queue entry increasing the attribute no_dequeues is made an unprotected action, then it is not affected by the server transaction’s rollback. If the queue resource manager were implemented on top of the basic file system, this would be an option. However, because we have chosen SQL as the implementation vehicle for queues, there is no such thing as an unprotected SQL operation.

Nested top-level transaction. One can try to employ the idea that was used for the Bartlett server in Chapter 5; that is, the updates that have to be detached from the scope of a rollback operation are wrapped into a separate top-level transaction. In contrast to the quotation server, this must happen only in case the server transaction aborts; thus, the logic goes into the routine associated with the rm_Abort callback entry. This is illustrated in the following piece of code:

Readers familiar with the problems of executing concurrent transactions on shared data may point out that the above solution does not work for the following reason: the new transaction tries to modify a tuple that has also been modified by the old transaction. When that happens, the old transaction is not completely over—the transactions manager is just going through the abort sequence—meaning that the old transaction still protects this tuple from other transactions. The queue manager, on the other hand, starts a new transaction to update the tuple. If the old transaction still holds on to it, the new transaction will wait for that transaction to finish. Given the logic, though, the old transaction will not finish before the new one has updated the tuple; in other words, nothing moves.

Those who came to that assessment are fundamentally right, but not entirely. Note that the piece of code for the nested top-level transaction is not part of the “mainline” implementation of the queue manager’s services; rather, it is part of a callback that gets invoked by the transaction manager at a well-defined point in time, namely at the end of the abort phase, after all undo work has been done. Chapters 10 and 11 explain that the order in which the resource managers participating in a transaction are invoked during commit (or during abort, for that matter) can be specified according to their particular needs. If in our example the queue resource manager is invoked at its rm_Abort entry after the database system, then the logic described works correctly.

6.5.1.1 Local Process Scheduling

The operating system bases its scheduling decisions on a small set of parameters, both static and dynamic, that describe the resource requirements of a process. These are the most important ones:

The TP monitor, operating at a higher level of abstraction, has more information than the BOS about the requestors and the resource requirements that come with a request. Whereas the operating system often treats processes as black boxes—that is, rather than looking at the program running in a process, it observes its behavior from the outside—the TP monitor knows which server classes it creates a process for. It also keeps statistics about that server class utilization. However, this wealth of additional information may as well lead to “paralysis by analysis.” Exploiting the performance characteristics for each single resource request is particularly infeasible, because it violates the requirement that each load balancing measure should save more resources than it consumes. As a consequence, there must be a mix of static decisions implemented at startup time and dynamic decisions that must be very fast, based on just a few parameters, mostly heuristic ones. Static decisions can be modified when system monitoring suggests that the overall behavior of the system is outside the specification. In most systems, dynamic scheduling relies on table lookups (and therefore is essentially predetermined by the static decision), along with a few rules of thumb. To get an impression of what those rules look like, consider the following list:

6.5.1.2 Interdependencies of Local Server Loads

Entry 5 in the rules-of-thumb list is the nontrivial one; the others rely on the static load distribution being correct. If that should not be the case, a reconfiguration of the TP system’s process structure may be required. Let us forget about the remote nodes for a moment and just focus on the decision whether or not to expand the local part of a busy server class by one process.

This decision in essence determines where on the curve shown in Figure 2.13 the system will be for the next time interval. If there are more requests than processes, this indicates that higher throughput is required. Higher throughput, though, means higher response times—a situation that is tolerable only up to a certain level. Note that all performance requirements at the core read like this: provide maximum throughput, while keeping response times below t seconds in 90% of all transactions. This is, for example, the basis of the TPC benchmark definition.

Creating a new process moves the system to the right on the response-time curve; more processes mean more load on the CPU. No new process means the system stays on its curve, but the request waits in front of the server class. An intuitive reaction might suggest that it makes no difference whether the request waits in front of the CPU (having a new process) or in front of the server class. This, however, is a misleading intuition.

Consider a server class “database system” to which a sequence of requests of the same type are submitted. Each request is an instantiation of the same program, just with different parameters, and they all operate on shared data. By massive simplification, we reduce the whole system to one server with one queue. Let the arrival rate of requests⁷ be R and the service time T₁. Then, assuming a simple M/M/l queue with an infinite number of requests coming in, the average service time per request is S₁ = T₁/(1 − T×R). Implicit in this formula is that only one database request is processed at a time. If we admit more than one process per server class (say, n), we would expect the system to behave like a single queue with n identical servers. However, two assumptions are required for this to hold true: (1) there is enough CPU for everybody, and (2) there is no interference on the data. Let us grant the unlimited CPU capacity for the moment; we still have to take into account the fact that transactions will get into conflict on the shared data. A model of this is sketched in Chapter 7, Section 7.11; for the present discussion, the following argument is sufficient. If there are n processes (n transactions accessing the database concurrently), the chances for an arbitrary transaction to be delayed by another transaction are proportional to n. The degree to which data sharing among transactions may cause conflicts, and thereby transaction wait situations, is measured by c. If the duration of the delay is assumed to be fixed,⁸ the original service time is increased by an amount that is proportional to n. Of course, each server now only gets 1/n of the total load.

This very simple model then yields the following estimate of the service time:

${\text{S}}_n=(\text{T}(1+c(n-1)))/(1-T(R/n)(1+c(n-1)))$

To give an idea of what that amounts to, Figure 6.15 shows a plot of Sn over n; T is set to 0.8 second, R is set to 0.9 requests per second, and c is 0.02. Note that this is not another version of Figure 2.13; here the abscissa is the number of server processes at a fixed arrival rate, whereas Figure 2.13 plots the response time over the arrival rate. The important aspect of this simple model is that CPU utilization has not been taken into account, and still there is a fairly narrow margin (given a response time threshold) within which the server class behaves properly.

Of course, a complete analysis cannot ignore CPU load as we have done here. When all processes allocated to a server class are busy and more are needed, then this not only shifts the system to the right on Figure 6.15, but it is also an indicator for a higher arrival rate, which increases R as well. A higher R affects the abstract server class as well as the physical resources (the CPU), so these effects are cumulative.

The point of this example is that request-based load balancing performed by the TP monitor must look at both the utilization of each server class and the utilization of the underlying physical resources. Just monitoring the physical resources, and basing all scheduling decisions on that, would not be sufficient. Consider the same scenario with the database server class, and assume that CPU utilization was the only criterion for the decision whether or not new processes should be admitted. Let the CPU utilization with 40 transactions running in parallel be 60%—not a very high value. As long as the utilization is below 85%, the system will allow new server processes to be created. With parallelism increasing, the service time per transaction goes up. More and more transactions actually wait for other transactions to finish, which reduces the load on the CPU. This allows more processes to be created, which further increases the service time—this is a version of thrashing, a phenomenon better known from virtual memory management.⁹ The transition from normal system behavior to thrashing, which is always caused by making scheduling decisions with insufficient information, is shown in Figure 6.16.

The consequence of all this can be put as follows: the TP monitor has to monitor the utilization of all server classes, as well as the utilization of the CPU(s) and perhaps other physical resources, such as communication busses and disks. For its dynamic scheduling, it then needs heuristics, which specify the minimum and maximum number of processes per class, depending on the utilization. That requires careful a priori analysis of the system load. For example, the degree of interference of transactions on data must be determined (parameter c in our model); this task is performed by the system administrator. Fully adaptive systems that, without prior knowledge, automatically achieve optimal balance with respect to a specified set of performance criteria, do not currently exist, and they probably will not for a long time.

6.5.1.3 Scheduling Across Node Boundaries

In distributed systems, where nodes do not share memory but are connected via a high-bandwidth, low-latency communication channel (a fast bus or a switch), scheduling a request at a remote node is not significantly slower than scheduling it locally—especially, if the local CPU is highly loaded. Let T_c be the communication overhead for sending the request to a remote node and for sending the response back. The scheduling decision then has to be based on the following considerations:

If any remote node can be found such that S_r + T_c < S_l, then the request should be executed at that node, rather than locally. To make these estimates, the TP monitor has to keep track of the performance figures of remote servers as well as local ones. These figures do not have to be kept current to the millisecond; the principle of locality is applicable to load balancing, too, and thus states that load patterns change gradually. TP monitors supervising parts of the same server classes need to be in session with each other anyway, and one type of message that is exchanged via such sessions is a periodic sample of the utilizations, response time, and so on, of the local resources at the participating nodes. Note that the scheduling decision need not actually be made according to the response time estimates we have given. As long as the utilization samples show that all nodes are running within the prespecified load limits, each node can schedule requests to all nodes that provide that service using a round-robin scheme. Given stability of load conditions, this is cheap to implement and is a good heuristic for keeping the load evenly distributed.

Simple as that seems, this approach to global scheduling has two problems that may go unnoticed and result in high overhead as well as (potentially) poor overall performance. One is frequently referred to as control block death, and the other has to do with data affinity.

Control block death becomes a problem as the number of nodes and the number of processes per node increase. This is likely to happen in large systems. Assume two server classes, A and B. If there are N nodes in the system and each node has I_a processes for A and I_b processes for B, then—according to our current scheduling model—each instance of A could send its request to any instance of B. If these requests are not context-free, the instances must bind to each other: a session has to be established. Now each session requires a control block describing its end points, the context that is associated with it, and other administrative details. If the assumed configuration operates in that mode for a while, each instance of A eventually will be in session with each instance of B, yielding c = (NI_a)(NI_b) = N ²I_aI_b control blocks. As N gets large, there will be a point where the number of control blocks growing quadratically will get too large—this is control block death.

The problem of data affinity can best be described by referring to Figure 6.17. There is a database, which is partitioned across two nodes, 1 and 2. Node 1 is currently heavily loaded; node 2 has little to do. A request from a terminal attached to node 1 is routed to node 2, using the global balancing strategy already described.

The service effectively invoked at node 2 needs access to the database, and the TP monitor makes sure that this resource manager invocation is kept local. It turns out, though, that the data to be accessed are in partition A, so the actual data manipulation has to be requested from node 1 via RPC, adding further to its high load. The problem is that the TP monitor at node 1 could not foresee the service requests done by server class 2. And even if it had that information, the need to access data partition A may depend on parameter values in the request. But let us go even further and assume the TP monitor understood these data fields. The best thing it could do would be to keep the request for server class 2 local to node 1; this would improve things just marginally, because node 1 had too high a load to start with.

If the high load results from frequent requests to data partition A (which is frequently observed), the dynamic load balancing cannot help. A static balancing measure has to redistribute the data across the nodes such that each one gets about the same number of accesses. In current systems, such a load-sensitive data partitioning is often combined with application-specific routing; after all, the TP monitor does not understand the parameter fields. The application router knows the partitions and their value ranges and makes sure requests are routed to the node where the data are. Given the way the TP monitor works, this requires hiding the fact that the server classes are the same at each node; they only pretend to be different. Specifically, server class 2 at node 1 is announced as “server class 2 needing data from partition A,” while server class 2 at node 2 is “server class 2 needing data from partition B.”

6.5.2.1 The Role of Authids in Transaction-Oriented Authorization

In a classical time-sharing environment, for which the operating system’s security mechanisms have been designed, the question of which userid an application runs under is trivial to answer. As the user logs on, he gets a process (or a number of them), which runs under his authid. Programs that are loaded into this process’s address space execute under the same authid, making it easy to decide on whose behalf a request (say, for accessing a file) is issued: it is the authid of the process the program runs in. This is also what makes such systems penetrable by Trojan horses. In a transaction processing system (or, more precisely, in each client-server system), the situation is a little more involved. To appreciate this, consider Figure 6.18.

Figure 6.18 is an elaboration of the mail system application depicted in Figure 1.2. A mail system user at his workstation is logged in under userid myself. At some point, he decides to run the mail application, which executes within transaction system at his node. The application runs under the authid localadm. The local TPOS does exactly what is described in this chapter, namely, handling transactional RPCs, commit processing, and all the other services of the TPOS. On behalf of the user, it issues a call to the mail server node, where the mail system runs in a process under userid mailguy. The call arrives; from the mail server’s perspective, it is user localadm that is requesting service. As this continues, the mail server uses an SQL database system to implement its services. As far as the database is concerned, the arriving SQL select has been issued by user mailguy (the database is running under DBadmin). But as the figure points out, mailguy is, in fact, working on behalf of localadm, which in turn is working on behalf of myself. What should be the criteria for access control under these circumstances?

The simple solution of having each process along the way take on the user’s authid does not work. There are two reasons: first, in a distributed system, the userids cannot be expected to be known at all nodes. Second, the end user (myself, in this example) usually has fewer rights on shared resources like databases than the administrator of these services. Referring to Figure 6.18, authid DBadmin is well authorized to access the SQL database catalog, for example, whereas userid myself is not authorized to do so at all. In other words, running process C under myself (even if it were registered at the database node) would merely result in denial of access.

The other extreme is to collect all the authids along the way and specify access rights for these concatenations. This does not make sense either, because it is neither manageable nor even required. Request-based access control exercised by the TP monitor is usually based on a two-level scheme: it authorizes clients’ requests for the servers it invokes directly (for example, is the mail server running under mailguy allowed to issue requests to the SQL database server?), and it passes the transaction’s authid along with each request. This is the authid of the user who started the transaction and who eventually will receive the result. Thus, the basic idea is to authorize each invocation step individually and tell the server what the transaction’s authid is; that way, the server can decide, even if it accepts in principle the request from the client, whether it can provide the service to the client, given that it works on behalf of that user. This attitude is reflected in the message format declared in Subsection 6.3.3.

Note that this scheme with two authids has two effects; one is restrictive, the other one permissive. The restrictive effect is easy to see: from the perspective of the SQL database, the mail server can access all the tuples in the mail database, because that is how it implements its services. But it must be prevented, of course, from giving a user (like myself) tuples that do not belong to his mailbox. If the database knows the transaction’s userid, it can properly restrict mailguys access rights where necessary. As an example of the permissive effect, take the following: assume I want to use the mail system to send a file out of my private database to Jim. As usual, the mail system calls upon the database, and, yes, it can access its files, but mailguy has no access rights on my file. Knowing, though, that its actually myself calling, these rights can be granted temporarily.

Note that the TP monitor checks only the client’s authority to call the server; the second part, which uses the transaction authid, is left to the resource managers. All the TPOS does to help in that is to pass on the original authid. This reflects a simple separation of concerns: the TP monitor does not “own” the database, or the log, or the user files; the only resources it manages is the set of resource managers that run the database, maintain the log, and so on. Consequently, the TP monitor only controls access to the resource managers. Each server is left to protect its own resources, in turn.

As mentioned, authorization in TP systems is a multidimensional problem. In addition to controlling who is going to access what, restrictions can be applied on when a request can be made (certain services are made available only between, say, 9 and 5, or only on Fridays, or whatever), and on where requests are allowed to originate. For example, a user may have the right to execute a fund transfer application involving large amounts of money, but only from a special terminal in a particularly protected area. There are many more restrictions and regulations one could think of, but these are the criteria applied by normal TP monitors. Some of them allow an invocation-specific password to be checked. The access matrix is stored in a relation that is part of the local repository and, thus, is owned by the TPOS. Accesses to it require the invocation of TPOS functions—and, of course, these accesses have to be authorized in the access matrix. There is a simple recursion problem here, which is left to the reader to figure out. A sample declaration of the TP monitor access matrix looks like this:

6.5.2.2 When to Do Authentication and Authorization

The previous subsection dealt with authorization, and only from the perspective of which criteria go into the decision. Let us now put everything together and describe how the TP monitor controls access to its services from the moment the user logs on to the system until the last resource manager in the line is invoked. Refer back to Figure 6.17 as an illustration of the different steps.

We assume that the user at the workstation is interested only in transaction processing, so switching back and forth between a transactional and a non-transactional environment need not be considered. First, the user logs on to the TPOS; that is, a session is established between the TPOS and the user. The user can be either a human or a machine, such as an automated teller machine (ATM). Establishing the session requires authentication. Once this has happened, the TPOS considers the user working on that terminal as authenticated; that is, upon future function requests from the terminal, the TPOS performs no authentication. Thus, the possibility of the user physically changing in midsession is ruled out. As part of the logon handling, the TPOS loads the user’s security profile from the repository. The profile describes general capabilities of the user, which are independent of a specific resource manager invocation. The user’s password (or his public encryption key) is kept here, along with the expiration date of the password, which days of the week he is not allowed to use the system, and more things of this kind.

With this, the user has been accepted as a legal citizen; as before, his authid is myself. The TP monitor typically provides a selection menu that contains the names of applications (resource managers) the user is allowed to use. These can be all the services he is granted in the TP_access_matrix, or a restricted set of those services. The name of the entry menu is specified as part of the user profile. In case the user can run only one application (think of the ATM), the input menu of that application is displayed. Returning to Figure 6.17, the user invokes the application running in server class A. This requires the TP monitor to do a lookup in the privileges relation:

If there is no tuple, the user has no right to call the service. If there is one, the TP monitor must further check if there are date and time restrictions and if the user works on the right terminal.

It is too expensive to query an authorization database every time some client issues a resource manager call. This leads to the distinction of run-time authorization versus bind-time authorization. Assume a transactional application that needs to invoke a number of servers—for example, the mail server mentioned before. At some point, the TP monitor has to load the code for that application into a process’s address space. In doing so, it has to resolve all the external references, like any linker or loader does. Some of these external references go to the stubs provided by the TPOS to handle the TRPCs. If the application supplies constants for the names of the services, the TP monitor can check right away if the application program makes any nonauthorized calls. If no such calls are detected, then at run time there is no need to reauthorize all the resource manager calls coming out of that process.¹⁰ Strictly speaking, this is true only if the access condition does not contain time constraints or restrictions with respect to the terminal, because those can only be checked at run time. This leads us directly to the methods for run-time authorization.

There is nothing really new here. The process circles around, caching, as in the case of name binding. The TP monitor keeps an in-memory copy of authorized requests in a data structure that provides fast access via authid; see Section 6.3 for a discussion of how to access the TP monitor’s system control blocks. If the number of users per node is not too large, the whole TP_access_matrix might fit into main memory. To further speed things up, each process control block could have a tag saying whether any authentication is necessary for resource manager calls issued by that process—except for the value-dependent parts.

So far, this all takes place in one node. In the example of Figure 6.17, the next TRPC goes to an instance of server class B at node 2. What does that mean in terms of authentication and authorization?

From the perspective of the process running server class B, neither the process at node 1 issuing the call nor the user has been heard about. That would suggest authenticating them both before accepting the request. And, indeed, a truly paranoid system might do just that. However, in normal systems, one tries to exploit the knowledge about the way requests are sent and about the components involved.

According to the architecture outlined in this chapter, remote requests are sent via the session managers of the participating nodes. Because these session managers keep at least one session between the TPOSs on either side, they have authenticated each other and have no reason to question the identity of their peers. Each TPOS administers its local resource managers by creating processes and loading the code; this is something like a session, too. If a TPOS sends out a request saying it comes from resource manager A, its peer in the other node can accept this as enough support for A’s claimed identity. If the client TPOS has also authenticated the user, it can indicate this in the request message, suggesting that the server need not do so again. Both types of confirmation can be ignored by the server in favor of doing its own authentication.

Figures 6.17 and 6.18 illustrate that as soon as there is a chain of requestors/servers working on behalf of one user, the TP monitor provides step-by-step authentication rather than end-to-end authentication. The problem of achieving higher security without losing too much flexibility and performance is an area of active research.