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 semanticbased scheduler. To varying degrees, the two versions deal with correctness, concur rency, deadlock, livelock, and garbagecollection issues, some of which are peculiar to the HTTP environment.
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.
Both the teller interface and the bank branches are implemented as web pages, and can be used by e.g. a Netscape browser. The humanaccessible interface consists of three WWW access points:
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.
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
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.
We chose to work within constraints of standard HTML, and consistent with a financial application. The primary constraints imposed by HTML were:
Since our application is dealing with dollar amounts and account balances, we imposed constraints suggested by this environment:
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
A variant of "woundwait" timeoutbased deadlock detection is used. We call this variation "woundask" 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.
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 writelocks on a certain portion of an account, and locks conflict when they would amount to more than the committed balance of an account.
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.
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.
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:
[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.