[Bernstein09] Chapter 4. Queued Transaction Processing

Chapter 4. Queued Transaction Processing
Why Use Queues?
The Queued Transaction Processing Model
Client Recovery
Handling Non-Undoable Operations
The Queue Manager
Publish-Subscribe
Other Message-Oriented Middleware
Queuing Products and Standards
Summary
4.1. Why Use Queues?
Indirect transaction processing, a client sends a request to a server andsynchronously waits for the server to run the transaction and reply.For example, using RPC, the client sends a request to the system as anRPC, which returns with a reply indicating whether or not thetransaction ran.
Even though this direct TP model is widely used in practice, it has some limitations (seeFigure 4.1).The first problem is dealing with the failure of a server or ofclient-server communications, which prevents a client fromcommunicating with the server. If a client sends a request to thisserver, it immediately receives an error telling it that the server isdown or disconnected and therefore is unable to receive the requestmessage. At this point, either the client is blocked, waiting for aserver to become available, or the user has to return later andresubmit the request to the client. A desirable alternative, which isnot possible in direct TP, is simply to ask that the request be sent assoon as the server is available, without the user or client beingrequired to wait on-line for the server to do so. For example, the usermight want to log off and come back later to get the reply.
Figure 4.1. Problems with Direct TP. (a)Sending a request to a down server. (b) Sending a reply to a downclient. (c) Balancing the request load across many servers. (d)Scheduling requests.

Thesecond problem is the inverse of the first. The client may successfullysend the request to the server. But the server, after executing thetransaction, may be unable to send a reply to the client, because theclient failed, client-server communications failed, or the serverfailed after completing the transaction and before sending the reply.In each of these failure cases, the server’s reply may be lost. So evenafter the failed component has recovered, the client still may notreceive a reply. It therefore doesn’t know whether its last requestactually ran, and hence whether it should resubmit the request.
Thefirst or second problem could occur due to failed communicationsbetween the client and server. Suppose the client sends the request tothe server and does not receive an immediate error. What does it do ifit does not receive a reply in a timely manner? It cannot tell whetherthe original request failed to be delivered to the server due to acommunication failure or server failure, or the request was deliveredto the server but the reply failed to be delivered back to the client.Under the circumstances, it is hard to imagine how the system could beprogrammed to execute each request exactly once, which is usually thebehavior that’s desired.
Athird issue is load balancing. In direct TP, if there is a pool ofservers that can handle a client’s request, then the mechanism forbinding a client to a server must select one of the servers from thepool. As discussed inSection 2.3, Server Classes,one approach is to randomize the selection of a server, so on average,the same number of clients are connected to each server. However, thisrandomization is just a guess. At any given moment, the actual load maynot be equally balanced among the servers. That is, one server couldreceive many requests requiring a lot of work and thereby becomeoverloaded. At the same time, other servers may not bereceiving any requests at all. When the variance in workload is high,this type of situation is rather likely, leading to poor response timefor some clients some of the time.
Finally,this whole model is based on first-come, first-served scheduling ofrequests. There’s no sense of priority in the system in which highpriority requests are processed early and low priority requests aredelayed until later.
Weare using the term “client” here because it’s more architecturallyneutral than front-end program or web server. The issues of interestapply to any program that is outside the TP system and submittingrequests to run transactions, rather than being a participant in thetransaction itself.
Queues as the Solution
These problems are solved by using a queue as a buffer for requests and replies between the client and the server (seeFigure 4.2).Instead of sending a request directly to the server, a client sends itto a queue. And the server receives those requests from the queue,instead of receiving them directly from the client. Similarly, theserver sends replies to a queue, and the client receives replies fromthe queue.
Figure 4.2. Queued Transaction Model. Inqueued TP, clients send requests to queues, and servers receiverequests from queues. This is in contrast to direct TP, where clientssend requests to servers.

Thequeue is a transactional resource. So operations on the queue are madepermanent or undone, depending on whether the transaction that issuedthe operations commits or aborts. Usually, the queue is persistent andis stored on disk or some other nonvolatile storage device.
Thisqueued TP model solves the problems that we just listed. First, aclient can send a request even if it is targeted for a server that isbusy, down, or disconnected, as long as the queue is available. Theclient simply stores the request in the queue. If the server isavailable, it can execute the request right away. Otherwise, when theserver becomes available, it can check the queue and run requests thatwere submitted while it was down.
Second,a server can send a reply to a client even if the client is down ordisconnected, as long as the client’s reply queue is available. Theserver simply sends the reply to the queue. When the client recovers oris reconnected to the system, it checks the queue to find any replymessages that are waiting.
Byusing queues to capture requests and replies, we can implementexactly-once execution of requests. For each request that a clientsubmits, the client can tell whether the request is waiting to beprocessed (in the request queue), executing (absent from both queues),or processed (in the reply queue). There are some corner cases thatneed attention, but with queues an implementation of exactly-onceexecution seems within reach. We will work out the details inSections 4.2 and4.3.
Third, as shown inFigure 4.3,many servers can be receiving requests from the same queue, therebybalancing the load across many servers. This load balancing is fullydynamic. As soon as a server finishes processing one request, it cantake another request from the queue. There is never a time when oneserver is overloaded while another is idle.
Figure 4.3. Load Balancing Using Multiple Servers. Whena server finishes processing one request, it takes another request fromthe queue. This dynamically balances the load across all servers.

Fourth,queues can be used for priority-based scheduling. Each request can betagged with a priority, which is used to guide the scheduling strategy.For example, each server can dequeue requests highest-priority-first.Alternatively, to ensure low priority requests are given some service,one server can be given the job of servicing low-priority requestswhile all other servers use highest-priority-first. Or each request’spriority could be set to be its deadline, and requests are processed indeadline order. Requests can also be scheduled manually, by collectingthem in a queue and running them under operator control. Once there isa queue in the picture, there is great flexibility in controlling theorder in which requests are processed.
Aqueue is also useful as an intermediary between a back-end system and aremote service, for many reasons. It can buffer the effect of networkdelays. It can be used to localize credentials for accessing the remoteservice. It can be a protocol bridge by supporting different protocolsfor remote and local access. And it is a convenient place for auditingand performance measurement of the remote service.
Thisis a long list of benefits for such a relatively simple mechanism. Forthis reason most transactional middleware products and even somedatabase systems support queues as one way of moving requests andreplies between clients and servers. Usually, queues sit between the front-end program and the request controller, as shown inFigure 3.1.Since queues can be used in other parts of a system, in the rest ofthis chapter we will use the more general client-server terminology,instead of front-end program and request controller terminology.However, to be concrete, you can think about it in the latter settingwithout being misled.