A Bank Teller Interface on the Web

M. Dipperstein          K. O'Gorman
For CS 274, Spring 1998
Department of Computer Science
University of California Santa Barbara, CA 93106

The World Wide Web as implemented in HTML offers great promise and presents significant obstacles for distributed database access. This project explores some of both. Of particular interest is the HTTP paradigm of connectionless and nominally stateless interactions. We decided to stay within the spirit of these limitations by using static HTML interactions, driven entirely by Perl CGI scripts, and to perform scheduling without any persistent process. Transaction state was preserved between HTTP interactions in order to provide continuity and to inform the scheduling decisions. The project implements an interface for banking transactions against accounts in multiple bank branches. Two versions were implemented, one using strict 2PL scheduling, and one using the lessons of the first to implement using a more sophisticated deadlock resolution scheme and semantic­based scheduler. To varying degrees, the two versions deal with correctness, concur­ rency, deadlock, livelock, and garbage­collection issues, some of which are peculiar to the HTTP environment.

1 The Application

     We implemented a bank teller's interface to bank branch data, with the ability to enter transactions which involve any combination of cash received, deposit or withdrawal to as many as eight of the accounts at ten bank branches, and cash returned to a customer. The system imposes application consistency constraints on the transaction which would be expected in a banking environment.

2 The Implementations

     Both the teller interface and the bank branches are implemented as web pages, and can be used by e.g. a Netscape browser. The human­accessible interface consists of three WWW access points:

• A bank branch selector page, with links to each of ten bank branches. URL: http://www.cs.ucsb.edu/cgi­bin/kogorman/bank.pl
• The first version of the bank teller interface. URL: http://www.cs.ucsb.edu/cgi­bin/kogorman/atm.pl
• The second version of the bank teller interface. URL: http://www.cs.ucsb.edu/cgi­bin/kogorman/atm2.pl

NOTE: Since the authoring, of this paper, the ATM simulator has lost its host. Click here for information on obtainig an archive of the simulator.

2.1 Methodology

     Interaction with the user is entirely in standard HTML. The illusion of multiple web pages is provided by the use of CGI programming. In fact all pages are produced on the fly by the programs.
     All coding was done in Perl. Frequent reference was made to [WCS91] and [Gun96].
     System V IPC implementation required Perl versions of system header files. These were produced in two versions, one for Linux for use during development and one for Solaris to be used on the campus machines. These were created from the system header (.h) files by the utility h2ph provided with Perl.
     Some of the CGI interface code was simplified by using utility programs provided on the web page for the CGI reference [Gun96]. The programs mime.pl and common.pl were obtained from that source.

2.2 The Constraints

We chose to work within constraints of standard HTML, and consistent with a financial application. The primary constraints imposed by HTML were:

• The several user interactions of a transaction are performed without a connection; as a result the application cannot determine if a user has become disconnected. Although we were permitted by the problem to assume to failures, we considered dropped connections so much a feature of the WWW that we treated the problem of a disconnected transaction. We will discuss this more completely in Section 2.3.
• The interactions of HTTP are to a certain extent stateless; in any event there is no persistent process waiting for, and timing out for lack of, resposes from the user. As a result we used hidden fields in web pages to identify a transaction, and kept state information on the transaction at the server.
• The lack of a persistent process prevents the use of true timeouts. We used an approach that uses timestamps to achieve much the same effect as timeouts.
• Browsers generally have a "Back" key or something similar. This poses problems of synchronization of the user's view of the transaction with the saved state. We decided to detect synchronization changes and to abort transactions when this was detected.
• Browsers can send multiple requests when the user presses a button multiple times before receiving a reply. This can also cause lost synchronization and in all cases where it mattered, we also aborted the transaction.
• The look­and­feel of the WWW dictates that the server process never wait on behalf of a user; some form of reply is sent as soon as possible. We chose to observe this discipline, with the result that all waiting is done by the user. In the event of a lock conflict, first the deadlock resolution methods are tried, and if the conflict persists, the user is given a response that indicates that some part of the requested transaction cannot be honored. This usually takes the form of a message like "Cannot read lock" or "Cannot hold $500.00".

     Since our application is dealing with dollar amounts and account balances, we imposed constraints suggested by this environment:

• No account balance is allowed to be negative.
• No transaction is allowed to commit while requesting a change that would cause an account balance to be negative.
• The sum of dollars in (cash and checks) plus account activity must not be negative, although it can be positive to reflect the normal bank practice of allowing partial deposits accompanied by cash back to a customer.

2.3 Deadlock and Livelock

     Both versions of the bank teller interface use schedulers that can have deadlock. The two versions use different resolution methods, but both rely on timestamps to simulate timeouts. In both versions, any acquired lock has a timestamp that is set when the lock is first acquired. If the lock becomes older than a systemwide value (currently 3 minutes for demonstration purposes), any conflicting lock will assume that deadlock has occurred.
     A variant of "wound­wait" timeout­based deadlock detection is used. We call this variation "wound­ask" because the user is presented with a page indicating the lock, and providing an opportunity to change the transaction, retry the request, or abort. The waiting is done in the cycle of user requests to retry, but may be resolved in the other indicated ways.
     In the first version, because of concerns mentioned above about disconnected users, any conflict with a lock that is older than the system limit (3 minutes) causes the transaction with the stale lock to be wounded. In this way, any abandoned or disconnected transaction is prevented from deadlocking the entire application. However, this approach can in principle lead to livelock, where a transaction is repeatedly wounded and never proceeds to completion.
     In order to deal with this potential livelock, the second version uses a timestamp on each transaction to determine which is the "older", and normally only the younger transaction is wounded. Since provision is made to restart the wounded transaction with the same timestamp, livelock is avoided in this case.

2.4 Lock Semantics

     In the first version, locking is standard strict 2PL, with read and write operations, and single account granularity. We considered this inconsistent with normal banking practice, which uses the concept of a "hold" on part of the balance of an account without affecting the remainder of the balance.
     Accordingly, the second version uses only increment (deposit) and decrement (withdrawal) operations on the accounts. In the absence of the constraints of Section 2.2, this would have allowed us to dispense with locks altogether. However, the constraint that account balances not be allowed to become negative leads to a requirement to implement locks much like the "holds" familiar to bankers. Such locks are in effect write­locks on a certain portion of an account, and locks conflict when they would amount to more than the committed balance of an account.

3 Saved State

     All three application sections use SYSV IPC to save state. That is, the each bank branch uses a shared memory segment to save accounts and balances, and each of the two teller implementations uses a shared memory segment for transaction state.
    The bank branch data has been alive on the campus web server since early May. It has not required rebuilding in that time.
     Each shared memory segment was set to a size of 10000 bytes, which has been more than adequate for testing.

4 Garbage Collection

     The saved state for the teller interface may include data for abandoned or disconnected transactions. This became a problem for debugging because dumps of the data were getting confusing. Accordingly, the second version implements a garbage collector that uses an activity timestamp on each transaction in the saved state.
     The result is that any transaction on which there has been no progress (no interaction with the user) in a specified period will be aborted by the next transaction that does make progress. The time limit is set to 15 minutes for demonstration purposes.

5 Conclusion

     We have implemented two versions of the banking application. The first, while correct, was primarily a learning experience for the team.
     The second version has several improvements on the first:

• Livelock­free deadlock resolution through the use of transaction timestamps.
• Increment/decrement semantics for reduced transaction conflict
• Recovery of wounded transactions without user retyping
• Garbage collection of saved state

References

[Gun96] Shishir Gundavaram. CGI Programming on the World Wide Web. O'Reilly & Associates, Sebastopol, CA, 1996.
[WCS91] Larry Wall, Tom Christiansen, and Randal L. Schwartz. Programming Perl Second Edition. O'Reilly & Associates, Sebastopol, CA, 1991.