Sagas

SAGAS
Hector Garcaa-Molrna Kenneth Salem Department of Computer Science Princeton University Princeton, N J 08544

Abstract
Long lived transactions (LLTs) hold on to database resources for relatively long periods of time, slgmficantly delaymg the termmatlon of shorter and more common transactions To alleviate these problems we propose the notion of a saga A LLT 1s a saga if it can be writtenas a sequence of transactions that can be interleaved with other transactions The database management system guarantees that either all the transactions m a saga are successfully completed or compensatmg transactions are run to amend a partial execution Both the concept of saga and its lmplementatlon are relatively simple, but they have the potential to improve performance slgmficantly We analyzethe various lmplementatron issues related to sagas, including how they can be run on an exlstmg system that does not directly support them We also discuss techniques for database and LLT design that make it feasible to break up LLTs mto sagas

the malorlty of other transactions either because it accesses many database obJects, it has lengthy computations, it pauses for inputs from the users, ora combmatlon of these factors Examples of LLTs are transactions to produce monthly account statements at a bank, transactions to process claims at an insurance company, and transactions to collect statrstlcs over an entire database [Graysla] In most cases, LLTs present serious performance problems Since they are transactions, the system must execute them as atomic actions, thus preserving theconsistency of the database [DateSla,Ullm82a] To make a transaction atonuc, the system usually locks the objects accessed by the transaction until It commits, and this typically occurs at the end of the As a consequence, other transactransactlon tions wishing to access the LLT’s objects suffer a long locking delay If LLTs are long because they access many database obJects then other transactions arelikely to suffer from an mcreased blockmg rate as well, 1 e they are more likely to conflict with an LLT than with a shorter transaction Furthermore, the transaction abort rate can also be increased by LLTs As discussed m [Gray8lb], the frequency of deadlock 1s very sensitive to the “size” of transactions, that IS, to how many oblects transactions access (In the analysis of [GraySlb] the deadlockfrequency grows with the fourth power of the transaction size ) Hence, since LLTs access many oblects, they may cause many deadlocks, and correspondingly, many abortions From the point of view of system crashes, LLTs have a higher probability of encountering a failure (because of their duration), and are thus more likely to encounter yet more delays and more likely to be aborted themselves
2491. INTRODUCTION
As its name indicates, a long lived transactron 1s a transactlon whose execution, even without interference from other transactions, takes a substantial amount of time, possibly on the order of hours or days A long lived transaction, or LLT, has a long duration compared to

Permlsslon to copy wlthout fee all or part of this material IS granted provided that the copies are notmade or dlstrlbuted for direct commercial advantage, the ACM copyrlght notice and the title of the pubhcatlon and Its date appear, and notlce IS given that copymg IS by permlsslon of the Assoclatlon for Computmg Machmery To copy otherwlse, or to repubhsh, requires a fee and/or specfic permisslon

0 1987 ACM O-89791-236-5/87/0005/0249

75@

In general there 1s no solution that ehmmates theproblems of LLTs Even d we use a mechanism different from locking to ensure atomlclty of the LLTs, the long delays and/or the high abort rate ~111 remam No matter how the mechanism operates, a transactlon that needs to access the objects that were accessed by a LLT cannot commit until the LLT commits However, for specific applreatsons lt may be possible to alleviate the problems by relaxing the...