A Causal-Phase Protocol to Order Soft Real-Time Transactions in a Distributed Database

Bruno Sadeg, Laurent Amanton and Samia Saad-Bouzefrane

LIH, Faculte' des Sciences et Techniques du Havre, 25 rue Philippe Lebon, 76 600 Le Havre, FRANCE

{ BrunoSadeg, Laurent.Arnanton, Sarnia.Bouzefrane} @univ-lehavre.fr Tel : (3310) 2 32 74 43 17

Fax : (3310) 2 32 74 43 14

Abstract

Real-time database applications are distributed in na- ture. Incorporating distributed data into a real-time database framework incurs complexity associated with transaction concurrency control and database recovery in a distributed context. This article presents an algorithm that manages soft real-time transactions in a distributed database. It uses a spec$c causal-ordering protocol to ensure the precedence relationships between transactions. Our algorithm is based on a technique, which subdivides transactions into sets. Then the protocol virtually serializes the executions on distributed servers by using causal phase ordering properties. Causal phases are created according to transactions conflicts that may occur between transac- tions sets. Transactions of the same phase are scheduled according to their criticality and transactions of two suc- cessive phases are ensured to commit in a causal partial ordel: This strategy permits to reduce the execution time, allowing more transactions meeting their deadlines. Key-words: causal phase, soft real-time, transaction serial- ization, commit protocol, distributed database, virtual syn- chrony.

1. Introduction

A variety of commit protocols have been proposed by database researchers in distributed databases [ 14, 71 over the last two decades. These articles include the classical two phase commit (2PC) protocol and its variations such as the presumed commit and abort commit protocols, and the three phase commit protocol. All these protocols require the exchange of multiple messages, in multiple phases,

0-7695-1321-2/01 $10.00 0 2001 IEEE

between the participating distributed sites where the trans- actions are executed. The commit processing takes then a significant place in transaction execution times [I], that's why the choice of a commit protocol becomes an important design decision in a distributed context.

Concurrency control techniques for real-time databases [ 19, 171 that use serializability [8] as the correctness criteria include lock-based protocols as the 2PC and its variants like timestamp-ordering protocols [20, 1 11. Conflicts between two real-time transactions or between one real-time trans- action and a set of real-time transactions can be detected by using any of these techniques. For lock-based protocols [ 181, conflicts are resolved by either transaction blocking or transaction abort. When a transaction requests a data item held by another transac- tion in a conflicting mode such as a write-lock, solutions exist to resolve such a conflict: to block or to abort the lock-requesting transaction, or to abort the lock-holding transaction. In order to avoid situations such as priority in- version, the protocols can use priority inheritance concept, in which the lower priority transaction that is blocking other transactions inherits the highest priority of the transaction it blocks, until it releases the lock.

Other lock-based protocols for real-time databases in- clude ordered sharing that eliminates blocking, and dy- namic adjustment of the serialization order [ 1 11 of trans- actions in order to execute high-priority transactions before low-priority transactions. Timestamp-ordering protocols [20] use timestamps that are assigned to transactions when they are started, for re- solving conflicts during transaction execution. Different priority-based timestamp-ordering protocols are proposed

288

and evaluated in the literature. One interesting approach is to assign timestamp dynamically whenever actual conflicts occur [ 31.

When the execution of transactions is deployed on a lot of distributed database servers, some algorithms that main- tain virtual synchrony [5] can successfully be used. A causal ordering protocol ensures that if two messages are causally related and have the same destination, they are delivered to the application in their sending order. In this paper, we use a causal ordering algorithm [lo, 15, 41 to serialize transaction executions. This specific method per- mits to construct consistent cuts [ 121 between conflicting

r

Pl

P2

P3

P4

transactions.

We present in this article a protocol that manages soft real-time transaction execution by using the causal phase concept to serialize transactions which may be subdivided in a set of atomic actions for the distributed servers. In the next section, we review the research in the causal or- dering domain. We explain in the section 3 the model we consider for the real-time transactions and for the causal al- gorithm. Our protocol is described in the section 4, then we give a detailed example in the next section before conclud- ing by summarizing this article and by giving some future directions to this work.

+5 / $x+1 \ $x+2

........... consistent cut causal cut L

Figure 1. Sequence of overlapped causal phases

2. Related Work

2.1. Causal phase ordering

A lot of programs can be easily divided into some trans- actions, and the major problem is the communications or- dering between the distributed system components, which have to be obviously total or causal to satisfy the constraints of most applications. We distinguish two types of ordering: a first way consists of ordering each transaction and a second of cutting the execution into a lot of consistent phases, then, into a lot of

1

ordering groups of transactions, or groups of subtransac- tions. The first possibility includes protocols that use the concept of Re-Synchronization. This kind of ordering algo- rithms has been developed by Raynal [ 131 and Ezhilchelvan [6]. The basic principles consist of cutting the execution in phases, which permit to order transactions. Raynal has de- veloped a protocol by using additional resynchronization transactions where it is shown that there is a trade-off be- tween the “as early as possible delivery time” and the “as small as possible timestamps size” criterium for timestamp- based protocols implementing causal order. Ezhilchelvan uses the time-silence mechanism to ensure a causal order:

289

this is a kind of timeout period. According to those results, a new kind of ordering has been introduced: a causal-phase ordering[2]. This protocol cuts the execution of a distributed program into a lot of phases, where transactions are not ordered, but where two transac- tions of different phases are causally ordered.

The figure 1 depicts this basic principle of the causal phases. Let S be a set of processes which define a distributed sys- tem. The communications are established point to point, and we consider that the FIFO ordering is guaranteed. Let $ and $ I be two distinct phases of an execution. We denote by + the "happened before" relation (defined in [9]) and by p z p ' the send of a message m from the process p to the destination p'.

$ + $' V(m,ml) such that m € $ A m'E$'

That is, for each process p of the system, the message or transaction m will be delivered before the message or the transaction m'. This special scheduling establishes a synchronization be- tween two distinct phases, that may overlap, while preserv- ing the asynchrony of the communications, without block- ing the servers.

2.2. Distributed commit protocols

The design of real-time commit protocols is based on a common theme of allowing individual sites to unilaterally commit: the principle is that unilateral commitment results in greater timeliness of actions. If later it is found that the decision is not globally consistent, "compensation" trans- actions are used to resolve the problem. A common model of a distributed transaction is that there is one process, called the master, which is executed at the site where the transaction is submitted, and a set of other processes, called cohorts, which execute on behalf of the transaction at the other sites that are accessed by the trans- action. For this model, a variety of transaction commit protocols have been devised, most of which are based on the classical two phase commit (2PC) protocol.

The two-phase commit protocol operates in two phases. In the first phase, the master reaches a global decision (com- mit or abort) based on the local decisions of the cohorts. In the second phase, the master conveys this decision to the cohorts. The protocol assumes that each cohort of a trans- action is able to provisionally perform the actions of the

'

transaction in such a way that they can be undone if neces- sary by using sequential histories of transaction actions in stable storage.

The 2PC protocol requires transmission of several mes- sages and writing or force-writing of several log records. A variant of the 2PC protocol, called presumed abort (PA), tries to reduce this overhead by requiring all participants to follow a "in case of doubt, abort" rule. This PA proto- col behaves identically to 2PC for committing transactions, but has reduced message and logging overheads for aborted transactions. A variation of the presumed abort protocol is based on the observation that, in general, the number of committed trans- actions is much more than the number of aborted transac- tions. In this variation, called presumed commit (PC), the overhead is reduced for committing transactions rather than aborted transactions by requiring all participants to follow a "in case of doubt, commit" rule.

3. The model

3.1. The distributed database system

We assume that the distributed database system is a set of servers that can communicate with each other by ex- changing messages: transactions and subtransactions. This system has a specific server, called the master, as shown in figure 2.

This particular site manages the transactions of all the clients, and then dispatches the transactions on the entire distributed system. We make the assumption that the communication channels deliver their transactions according to a3fo ordering.

3.2. The management of transactions

The causal ordering to resolve conflicts

When some successive transactions do not conflict, they can be executed during the same causal phase on the servers. Let be this group of transactions. Obviously, this group may contain only a singleton (one transaction). The master M manages this group of transactions as fol- lows:

when a current transaction T does not generate any conflict with transactions of the current group G, T is added to G.

0 when a current transaction T might create a conflict, M starts a new causal phase: all the transactions of

290

the group G will be achieved before the execution of T and the next transactions. The group G is then erased and initialized with the new transaction T for the next phase.

when a transaction T’ of G has committed or aborted (according its deadline), T’ is removed from G.

The causal phase ordering guarantees that two successive groups of transactions will be executed on the distributed servers according to a causal order: this partial order per- mits to preserve the consistency of the data.

Actions of a transaction

We assume that the transactions sent by the clients can be divided in some atomic actions that correspond to resources of the distributed servers. If we consider a distributed database system composed of five servers (SI, S2, ..., S5), a transaction T can be divided into five distinct actions that correspond to operations (7-1,

72 , ..., 7 5 ) , which have to be executed on the five servers. Obviously, each action may interact with any other action.

The master site (denoted M ) has to manage transactions as follows (see figure 3):

a specific scheduler orders all the transactions in a transaction queue according to their respective dead- lines.

each transaction is divided into simple actions.

a new causal phase is generated from M only if there is a conflict between the current transaction and the group of transactions that are executed on the servers since the previous phase has begun.

Real-time scheduling, commit or abort mechanism

When the master M receives a transaction, the scheduler puts it in the waiting queue according to its deadline. If the deadline expires before the execution of the trans- action, this transaction is removed from the queue. If the deadline is reachedidwing the execution phase, the both fol- lowing possibilities can be chosen:

all the actions of the transaction abort: the data are initialized with the previous values, that is the values in the previous phase.

[ 161). 0 the protocol: may use approximate results (€-data

When the deadline of a transaction is not reached, the principle of the causal ordering guarantees that there is no conflict and so that the transaction can commit.

4. The causal-phase protocol

We present in this section an algorithm which guarantees a causal order for groups of transactions. This algorithm establishes a virtual synchrony for groups of concurrent transactions and guarantees consistent executions of these groups of transactions.

4.1. Data structure description at node i

We need some data-structures in the algorithm. We start by describing the variables used.

- nack : integer variable which counts the Ack messages ; initially, n a c k t O ;

- pp : integer value which represents the first process that has sent the message Mark to site i ; initially, p p t n i l

- LocalColor : variable which represents the local color of the process ; initially, Loca lCo lor tb lack ;

- Neighbours : List of the neighbours of the site z.

4.2. Two specific messages

Two types of messages are used to ensure the causal- phases ordering:

- Compute (m,c) : computation message where m rep- resents the transaction and c the local color of the sender;

-Mark () : this message is sent by M and then broad- casted by all other processes in order to begin a new phase.

4.3. Text of algorithm

Phase change decision on M The master has to create a new causal phase when it detects a conflict between the transaction to execute and the group of transactions that are executing on the servers. if nac k= 0 then

waitfor the end of the transactions

ChangeColor(LocalCo1or) send Mark ( ) to Neighbours nackt# Neighbours wait (nack=O)

executions for the current LocalColor

fi

291

Receipt of a Mark() message from the site j The server j broadcasts first the message and changes the

hase if nack=0 A pp=null then PPtj

send Mark ( ) to {Neighbours - j} nackt# Neighbours - 1

elsenacktnack - 1 fi

waitfor the end of the transactions

ChangeColor(LocalCo1or)

send Mark ( ) to pp pptnil Execute(Buffer(LocalCo1or))

executions for the current LocalColor

if nack=O A pp#null then

fi

transaction Tl Sl x1 t x1+ 2 S?

Receipt of a Compute(m,c) message from site j if c#LocalColor then

else Execute(m) (according to its deadline)

if nac k= 0 then

else

fi

Execute (m)

put (m) toBuffer(c)

fi

T2 Y1 t x2 Yz t 0

Procedure Changecolor (a) if a=white then atblack else atwhite fi - COMMIT -

The consistency correctness and liveness properties of this protocol can be found in a similar form in [ 2 ] .

Si s 4

5. A relevant execution example

X s t X z f 3 x4 t 0

5.1. Context description

We suppose that the distributed database system is or- ganized as shown on the figure 2: one master M and rive servers SI, S2, ..., S5. Each server Si manages two data items: X i and Yi. In order to simplify the demonstration, we suppose that the clients have sent four transactions to the master, and that the master’s scheduler has ordered them in its local queue: T I , T2, T3, and finally T4, which has the latest deadline. Finally, the actions of transactions for each server are:

S5 This table presents the subdivisions of the four trans C-

tions. There is no conflict between the transactions T I , Tz and T3. On the other hand, the last transaction modifies the item Y1 and Y2 (see Tz), uses the item X3, which is mod- ified by TI and also uses Y3 which is modified by T3. So, this configuration can be cut into two causal phases: the first one gathers T I , Tz and T3 together, and the second contains only the singleton T4 in this example.

5.2. Execution

According to these assumptions, the master broadcasts the actions of the first phase transactions that are immedi- ately executed.

step 1: M sends a message Mark to its neighbour 5’1, and then it broadcasts the actions of the transaction T4.

step 2: The server SI receives those messages and changes its phase (commits) if all the previous actions are ter- minated. Then it broadcasts the message Mark to the other sites. From this moment, the server S1 is ready to execute actions of the second phase, that is actions of the transaction T4.

step 3: Four of the five servers have committed and have begun a new causal phase. Only the server S5 has not changed of phase. If actions from T4 that are exe- cuted on those servers has to read values of the server S5, the causal ordering guaranteed by the protocol as- sures that these requests will be executed on S5 after all the actions of the previous phase have finished. If an action of S5 wants to read any value of the other servers, it can read it without generating any conflict: if an action of the second phase has modified an item, the server has not yet committed the transactions.

step 4: All the servers have committed and the transactions of the new phase can be executed everywhere on the distributed database system.

292

step 5 : After this last step, the master receives a message Murk that indicates the end of the phase change. The master has the possibility to create a new (third) phase if necessary.

This example shows that two phases can overlap whereas conflicting transactions belong to those phases. Moreover, it is easy to increase the number of overlapping phases: we just have to use more than two colors in the algorithm (see section 4) to distinguish successive causal phases.

6. Conclusion

We have proposed in this paper, a protocol based on the causal ordering, that distributes transactions on several database servers. The causal ordering offers a simple way to execute transactions on a distributed system: conflict- ing transactions are virtually serialized and non conflicting transactions are simultaneously executed. This protocol needs only 2 x M short messages (just an acknowledge- ment) where M is the number of network links. The master of the distributed database manages the soft real-time crite- ria by ordering the transactions according to their deadlines. When a transaction has to abort, the global consistent view guaranteed by the causal phases permits to easily recover the previous state.

In our ongoing work we want to suppress the master role: all the servers will become a master with the possibility to change the causal phase independently of the other servers.

References

[ 11 R. Abbot and H. Garcia-Molina. Scheduling real-time trans- actions: a performance evaluation. ACM Transactions on Database Systems, 17(3):513-560, 1992.

[2] L. Amanton and M. Nami. A causal-phase ordering protocol with multi-initiators for overlapped broadcasts. In LCN’99, 24th IEEEAnnual Conference on Local Computer Networks, Boston, Massachusetts, USA, 1999.

[3] R. Bayer, E. Elhardt, H. Heigert, and A. Reiser. Dynamic timestamp allocation for transactions in database systems. In H. Schneider, editor, In Distributed Data Bases, Proc. Second International Symposium on Distributed Data Bases, Berlin, September 1982. North Holland Publishing Com- pany.

[4] B. K. Bhargava. Concurrency control in database systems. Knowledge and Data Engineering, 1 I(l):3-16, 1999.

[SI K. Binnan and J. Joseph. Exploiting virtual synchrony in dis- tributed systems. In I Ith ACM Symp. on Operating Systems Principles, pages 123-138, December 1987.

[6] P. Ezhilchelvan, R. Macedo, and S. Shrivastava. Newtop: a total order multicast protocol using causal blocks. Technical report, Dept. of Computing Science, University of Newcastle upon Qne, UK, 1993.

[7] B. Kao and H. Garcia-Molina. An overview of real-time database systems, 1995.

[8] K.-W. Lam, S. H. Son, and S. lun Hung. A priority ceiling protocol with dynamic adjustment of serialization order. In ICDE, pages 552-561, 1997.

[9] L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications ofthe ACM, 21(7):558- 565, July 1978.

[IO] B. Lee, T. Park, H. Y. Yeom, and Y. Cho. An efficient algo- rithm for causal message logging. In Symposium on Reliable Distributed Systems, pages 19-25, 1998.

[ l l ] Y. Lin and S. H. Son. Concurrent control in real-time databases by dynamic adjustment of serialization order. In I l t h IEEE Real-Time Systems Symposium, Orlando, Florida, December 1990.

[ 121 K. Marzullo and G. Neiger. Detection of global state predi- cates. In S.-V. L. 579), editor, Proceedings of the Fifth Work- shop on Distributed Algorithms and Graphs, pages 254-272, October 1991.

[ 131 A. Mostefaoui and M. Raynal. Definition and implemen- tation of a flexible communication primitive for distributed programming. Technical Report 765, IRISA, Rennes, France, Octobre 1993.

[I41 K. Ramamritham. Real-time databases. journal of Dis- tributed and Parallel Databases, l(2): 199-226, 1993.

[I51 L. Rodrigues, R. Baldoni, E. Anceaume, and M. Raynal. Deadline-constrained causal order. In 3rd IEEE Interna- tional Symposium on Object-oriented Real-time distributed Computing, March 2000.

[I61 S. Saad-Bouzefrane and B. Sadeg. Relaxing the correctness criteria in real-time dbmss. International Journal of Com- puters and Their Applications, 7(4):209-2 17, 2000.

[ 171 B. Sadeg and S. Saad-Bouzefrane. Enhancing concurrency control and scheduling of real-time transactions. In WIP- Int. Real-Time System Symposium (RTSS’99), pages 80-84, Phoenix, Arizona, USA, 1999.

[I81 L. Sha, R. Rajkumar, S. H. Son, and C.-H. Chang. A real- time locking protocol. IEEE Transactions on Computers,

[ 191 A. Thomasian. Checkpointing for optimistic concurrency control methods. IEEE Transactions on Knowledge and Data Engineering, 7(2):332-339, 1995.

[20] 0. Ulusoy and G. G. Belford. Real-time transaction schedul- ing in database systems. Information System Journal, (18), 1993.

.

40(7):793-800, 1991.

293

...................................................................... : Distributed database

......................................................................

Figure 2. Distributed database system

/ \ Transactionqueue I

. . . . ty I t l i t2 i t3 i t4 i t5 I

, . . . \ Transaction partitioning / \ \ 1 I

to the servers S I ... s5

Figure 3. The master schedules the transactions and broadcasts subtransactions to the distributed database

294

Step 2 1 2

5 3

1 Steo 4 2

3

3 5

I SteD 5 2

7 5

- new-phase request

1 2 3 4 5 : processes

5 3 5

Figure 4. Progress of the transactions executions

295