Position Paper for HPTS’99

First Name: Calton

Last Name: Pu

Title: Professor

Company: Oregon Graduate Institute

Address: P.O. Box 91000

City: Portland

State: OR

Zip Code: 97291-1000

Telephone: 503-748-1214

FAX: 503-748-1553

Email: pu@cse.ogi.edu

Classic ACID properties of transactions assume that transactions run entirely within a database. For example, the Consistency property requires that a transaction transform a consistent database state into another consistent database state. In contrast, Internet transaction processing needs analogous properties that span autonomous databases. We call the new kind of transactions Inter-database Transactions, since the traditional single-database assumption no longer holds. In this position paper, we discuss some research issues caused by the removal of this assumption.

Many of the current electronic commerce applications connect clients to single databases run by vendor companies, by extending their client/server application architecture to include Web clients. While many initial electronic commerce transactions are small, one would expect more sophisticated transactions involving multiple databases and companies to develop over time. An interesting question is whether these sophisticated transactions will require the system management of dependencies and states across databases. If the answer were negative, then there would be no need for inter-database transactions, since the current software infrastructure would suffice for sequences of independent single-database transactions.

One could argue that current Web-based clients are willing to maintain the state and dependencies themselves, therefore dispensing with the need for sophisticated transactions. This is the case of web-based travel agencies (e.g., ITN, Travelocity, Expedia), which connect to airlines, hotels, and car rental companies, but do not offer atomic commitment of reservations across companies. This situation is acceptable to many clients because of the particular application semantics of travel. Specifically, the cancellation cost (rollback of reservation transaction) is very low for car rental (usually no penalty for unclaimed reservations) and quite low for hotel (no penalty if the reservation is not guaranteed). Consequently, it is common to make independent car and hotel reservations while searching for the best deal in airline tickets.

However, airlines impose serious penalties for unused reservations (e.g., $75 for ticket exchange or reservation changes at United) unless the customer pays a significant premium for unrestricted fare. We observe the difference between hotel/car rental and airlines to be related to their products. Although all of them offer services, an airline’s product (seats on a flight) is the most perishable. If a car is not rented, the cost is limited to parking and lost revenue. The cost of an empty seat on a flight is more significant since the plane has to fly anyway. In general, businesses offering perishable goods will incur higher costs for cancellations that result in unsold products.

High cancellation costs will imply high pressure for customers to commit early, with airlines as a good example. This early commitment represents an actual charge for cancellation, which reflects the high cost of rollback for perishable goods. While low-cost carriers have been able to reduce the cancellation costs by increasing the yield (reducing the number of empty seats on a flight), the cost of "spoiled" products remains an important threat.

Many of the current electronic commerce businesses focus on non-perishable goods (e.g., books and toys), therefore bypassing the problem of early commit. We do not see this situation as a statement that customers do not wish to buy perishable goods over the Internet. We think that perhaps the lack of better system support for cost management and reduction makes it difficult to offer perishable goods conveniently.

With non-zero cancellation penalty, it becomes important to manage the dependencies and state in an inter-database transaction involving several companies. It will be difficult for non-expert customers to remember the rules and compare costs, therefore making it difficult to find good deals at minimal risk.

In a single-database world, one could use nested transactions to manage these multiple component transactions and commit all of them atomically. This bypasses the rollback problem. However, in an inter-database transaction, the component databases do not necessarily trust each other, since denial-of-service attacks are a real threat in the Internet. It is easy to see that no DBA would accept entering a two-phase commit protocol with another company, due to management difficulties introduced by the window of vulnerability, among other problems.

Since our goal is to reduce the length of time a product is locked by a reservation, two-phase commit (or any kind of commit) protocol should be avoided. Without an atomic commit, there will be some risk of failure, where some component transactions commit, and others abort. We hypothesize that the risk of failure, if made sufficiently small, will be acceptable to most customers, since manual means of recovery exist. All electronic businesses recognize the need for technical support, which can handle these failures. In addition, credit card companies may offer another layer of recovery from the small number of partially failed transactions. Finally, to reduce the cost of manual recovery, it is conceivable that the vendors will allow customer-initiated cancellation (at no cost) within a sufficient short window from the commit.

More constructively, preventive methods may be devised to reduce the risk of partial failures. For example, we can introduce a simulation phase of execution, where the entire component transaction runs through to the end (the classic prepared state). But instead of entering the two-phase commit protocol, the component transaction simply reports "successful simulation" and terminates the transaction without any concrete action (equivalent to abort). The purpose of the simulation phase is to gather run-time information about the actual execution, in terms of available resources and execution time. Once the inter-database transaction manager has gathered this run-time information, it may start all the component transactions in parallel in an actual execution phase, asking them to unilaterally commit.

If the information gathered during the simulation phase remains true during the actual execution phase, then the inter-database transaction will commit. The probability of partial failure is minimized if the system state during the actual execution phase is reasonably close to the system state during the simulation phase. Suppose that a significant amount of time has elapsed (say due to client think time between the beginning and the end of the simulation phase). Since the simulation phase has no side-effects, the inter-database transaction manager could re-run the simulation phase from the beginning to end in a rapid succession (or in parallel). If all the component transactions validate their pre-conditions for commit, then we can start the actual execution phase immediately, thus reducing the probability of partial failure.

The management of dependencies and state will help in automated recovery, should an inter-database transaction fail partially. For example, knowing which databases allow no-cost cancellation may allow the automatic generation of no-cost cancellations to reach a unanimous decision.

In this position paper, we argue that inter-database transactions are useful for sophisticated transactions involving perishable goods (or services). We observe that perishable goods require non-zero cancellation fees, which make sophisticated inter-database transactions desirable and perhaps necessary.

Since two-phase commit protocol is unlikely to be adopted in inter-database transactions, we discuss the alternative of allowing non-uniform decision in an inter-database transaction. The idea is to reduce the probability of such non-uniform decisions by using a simulation phase, in which we validate the pre-conditions for committing the component transactions. In the immediately following actual execution phase, each component transaction commits unilaterally.

We are still working on the technical details of the execution model, its correctness properties, and recovery mechanisms. But we believe that the support for sophisticated inter-database transactions, particularly involving perishable goods and services, will be an interesting research and application area.