Object-Based Locking Protocol for Replicated Objects
Object-Based Locking Protocol for Replicated Objects Kyouji Hasegawa and Makoto Takizawa
Dept.of Computers and Systems Engineering
Tokyo Denki University
Email kyo,taki@takilab.k.dendai.ac.jp
Abstract
Distributed systems are composed of multiple objects. Each object supports more abstract operations than the low-level read and write operations.The objects are replicated to increase the performance,reliability,and availability.In this paper,we discuss a synchronization method to make multiple replicas of objects mutually consistent.In the tra-ditional optimistic two-phase locking(O2PL),every replica is?rst locked in a read mode to write an object.Finally, all the replicas are locked in a write mode when the trans-action commits.We propose a novel object-based locking (OBL)method based on the abstract operations.Here,the number of the replicas locked is decided based on the access frequency and the strength of the lock mode.
1.Introduction
In distributed systems,it is critical to keep data objects consistent in to presence of multiple accesses and faults.
Many kinds of concurrency control methods[2]are dis-cussed so far.In the famous two-phase locking(2PL)proto-col[2,3],the transactions lock the objects before computing the operations on the objects.Most systems adopt the strict 2PL protocol where the locks obtained are released at the end of the transactions in order to resolve the cascading abort.One of dif?culties in the distributed applications like the groupware is that objects are locked for a longer time. The optimistic concurrency control[7]is discussed to reduce the overhead implied by the locking.Here,the transaction manipulates objects without locking the objects.When the transaction ends up,commits unless the objects ma-nipulated by are manipulated by other transactions in the modes con?icting with.
In order to increase the reliability,availability,and per-formance of the system,the objects in the system are repli-cated.In the mobile database systems[1],the objects are also replicated by cashing the data in the?xed servers into the mobile clients in order to resolve the disconnected oper-ations[4,6].Here,it is critical to make the replicas of the object mutually consistent.Jing[5]discusses an optimistic two-phase locking(O2PL)method to maintain the mutual consistency among the replicas.In the O2PL,if a transac-tion would write an object,locks all the replicas of in a read mode.If locked,manipulates the repli-
cas.When commits,tries to convert the mode on the replicas to a write mode.If succeeded, commits.Otherwise,aborts.
The distributed applications are modeled to be a col-lection of multiple objects which are cooperating to achieve some objectives.CORBA[9]is becoming a standard frame-work of the distributed applications.The objects support more abstract operations to and.For example, a object supports and operations. In this paper,before each object is manipulated by an opera-tion,the object is locked in an abstract mode corresponding to the operation,e.g.mode for operation of the object.Two operations1and2support by an object con?ict if the result obtained by applying1and 2
to depends on the application order of1and2. The con?icting relation between the lock modes is de?ned based on the con?icting operations.That is,if an operation 1
con?icts with2,the lock mode of1con?icts with 2
.We discuss a novel concurrency control to maintain the mutual consistency among the replicas.In this paper,we propose a novel locking scheme for the replicated objects, named(-)protocol.The num-ber of replicas to be locked depends on how the lock mode of the operation is and how the operation is invoked.The stronger and more frequently used the lock modes are,the fewer replicas are locked.
In section2,we present the system model.In section3, we discuss the protocol.
2.System Model
A distributed system is composed of multiple objects 1which are cooperating by exchanging messages in the communication network.Let be a set of objects
in the system,i.e.=1.The communication network supports every pair of objects and with a reliable,bidirectional channel.Thus,can send messages to by the channel without any message loss in the sending order.
A transaction sends a request to an object.On receipt of,computes.Here,may invoke an operation on another object.sends the response of back to.is an atomic sequence of operations.
only if all the operations invoked by success-fully complete,i.e.operations commit.The operation invoked by commits only if all the operations invoked by commit.is also an atomic unit of computation.Thus, the operations are,i.e.nested transaction[8]. Each object supports a set of operations 1for manipulating.is encapsulated so that can be manipulated only through the operations sup-ported by.Let denote a state obtained by applying to a state of.An operation is with iff()=()for every state of.with()unless
is compatible with.If con?icts with,the state obtained by computing and is independent of the computation order.If some operations con?icting with are being computed on,has to wait until the operations complete.In this paper,we assume that“”is symmetric, i.e.iff.It is written. The interleaved and parallel cooperation of operations has to be serializable[2].That is for every pair of transactions and,if some operation of precedes of which con?icts with,every con?icting of precede.
A transaction manipulates objects1by invok-ing operations1,respectively.On receipt of the request,is locked in an is able to make the computation serializable.Here,let be a set of lock modes of.
A mode1is with2in if the operations
1
of mode1is compatible with2of2.Otherwise, 1
con?icts with2.For example,two are com-patible in a?le object.and denote the lock modes of and.and are compatible in a object.If is locked in a mode with which con?icts,blocks.is computed only if is locked in.After computing,the lock of is released.Problem is when is released. Here,suppose that invokes on1. There are the following ways for releasing the locks: [Releasing schemes]
(1)Open:is released when completes.
(2)Semi-open:1are released when com-
pletes.However,is not released.
(3)Close:Every object locked in is not released.Only
if completes,all the objects locked in are released. In the open scheme,the object is released as soon as completes.Here,the fewest number of the objects are locked which to cascading abort may occur.On the other hand,every object is locked until the transaction completes in the close scheme.The close scheme is the same as the strict two-phase locking(2PL)[2].The largest number of the objects are locked and the throughput of the system is decreased in the close one,but no cascading abort occurs.
In order to increase the reliability,availability,and perfor-mance,an object is replicated in a collection1
(1)of replicas,where is a replica of.Each supports the same data and operations as the other repli-cas.Let be11.Here,suppose that an operation on an object is invoked.Suppose that invokes an operation on an object and further invokes on[Figure1].Here,= 1.If sends a request to the replicas 1,is computed on the replicas.On receipt of,computes and then invokes.Since multiple replicas invoke,is computed multiple times on.If updates,the state of gets inconsistent since is computed multiple times on.
In order to resolve the multiple redundant invocations of operations on replicas,the following invocation rule is adopted;
(1)does not invoke any operation;If changes
the state of,is computed on every replica.
Otherwise,is computed in one replica. (2)invokes on;is invoked on one
replica or every replica if changes or not like(1).In either case,only one replica invokes .On receipt of the response of from,
forwards it to all the other replicas if changes
.On receipt of the state for,changes the state so as to be the same as by using the state.
3.Object-Based Locking
The system includes multiple objects1.Each object supports a set of operations1.
is replicated in a set of replicas1(1). We discuss the-()scheme for maintaining the consistency among the replicas of.
3.1.Lock modes
First,we discuss the lock modes supported by the object .Before computing,is locked in a mode in
Figure1.Invocation on replicas.
.Suppose that is locked in a mode and would be computed on.If is with,can be started to be computed on.Otherwise,has to wait until the lock of the mode is released.Here,let
be a set of modes with which con?icts in,i.e.
=con?icts with.In this paper,we assume that the compatibility relation among the modes are symmetric. Hence,is in for every’in.
[De?nition]For every pair of modes1and2in, 1
is than212iff1
2.
[Example1]Let us consider a?le object with operations and.Let and be lock modes for
and,respectively.Since con?icts with
,con?icts with.is compatible with.=and=
.Since,
is more restricted than(). [Example2]A object supports operations, ,and.Let,,and be,,and.
and are compatible.con?icts with and.==and =.Since
,neither nor
.
In Example2,there is no relation among the modes. However,has more modes con?icting with
than and.We discuss which modes are stronger.
[De?nition]For every pair of modes1and2in, 1
is than2iff12and1
2.
In Example2,.Here,is stronger than and.It is straightforward that
12if12.
Some mode1may be more frequently used than2. Here,let be the usage frequency of a mode,i.e. how many operations whose modes are are issued to for a unit time.The frequencies of the modes in are normalized to be 1.The
is de?ned to be. [De?nition]For every pair of modes1and2in, 1
is than2on the(12)iff
12,21,and12 .
It is clear that12if12. Hence,12if12.Suppose that1and2are operations of modes1and2in an object,respectively. Let us consider a probability that waits for the release of the lock con?icting with.If1 2,1has a higher blocking probability than2. In Example1,since. In Example2,suppose that the usage ratios of, ,and are60%,30%,and10%,re-spectively,i.e.=0.6,=0.3,and =0.1.
=0.4.= 0.6.Hence,and
since and
.has a higher blocking probability than and.
The modes in are partially ordered by the strength relation“”.A mode is referred to as in
iff there is no mode’in such that’.is iff’for every mode’in.The
and modes are de?ned in the similar way.For every pair of modes1and2in,a mode is a()12iff1,2, and there is no mode’such that1’and 2’.The()12 is similarly de?ned.
3.2.Locking protocol
The traditional systems support only two types of oper-ations,i.e.and,where is stronger than ().In the O2PL,the replicas are?rst locked in.The replicas are?nally locked in. In the object-based system,each object supports more ab-stract objects which support more types of operations.That is,there may be more than two lock modes.For example, the bank object supports,,, and operations.In addition,the lock modes in are partially ordered by the strength relation“”as discussed in the preceding subsection.
We discuss the concurrency control to maintain the mu-
tual consistency among multiple replicas1of an object.Suppose that a transaction invokes an oper-ation on.First,some number of the replicas in are locked in a mode1which is not stronger than.Let1be the number of the replicas locked by before is computed.Unless all of1replicas can be locked,is aborted.If all of1replicas could be locked,is computed on the replicas as presented before.When would commit, some number2of the replicas are locked in a mode .12and1. We discuss how to decide the numbers1and 2of the replicas to be locked and the lock mode 1.The more replicas are locked,the more commu-nication and computation are required.Hence,the more frequently is invoked,the fewer replicas are locked. 1and2are decided depending on the proba-bility that con?icts with other operations of.There are the following constraints on1and2:
(1)If con?icts with,2+2
>and2+1>.
(2)22iff. Here,suppose that locks replicas in= 1.Suppose that two operations and are invoked and con?ict in.The probability that both and can lock the replicas is given1-[
][].is a set of operations con?icting with in.Here,the probability
that can lock replicas is1-
[].2can be decided so that the probability2is the minimum.
In this paper,we present a simpli?ed protocol, where1is equal to2,say=1
=2,and is the same for every operation
of the object.We?rst de?ne a mode in the system.is de?ned to be a mode satisfying the constraint that for every mode in and con?icts with. is the lub of.If=,,is because.If there is the minimum in, an arti?cial mode is included in.
Suppose that an operation in a transaction would lock replicas1of.is locked by the following locking scheme.
[Locking scheme]
(1)First,replicas in are randomly selected.
Let be a subset of the replicas selected from.
(2)Every replica in is locked in the bottom mode.
(3)If succeeded in locking all the replicas in,the replicas
in are manipulated by.
(4)When the transaction commits,the lock mode of
every replica in is converted up to.If suc-ceeded,commits.Otherwise,aborts.4.Concluding Remark
This paper discusses the-
protocol on the replicas of the objects.The objects support more abstract operations than the traditional and operations.
References
[1]D.Barbara,and T.Imielinski,“Sleepers and Worka-
holics:Caching Strategies in Mobile Environments,”
Proc.of the ACM SIGMOD,pp.1–12,1994.
[2]P.A.Bernstein,V.Hadzilacos,and N.Goodman,
“Concurrency Control and Recovery in Database Sys-tems,”Addison-Wesley,1987.
[3]J.M.Carey,and M.Livny,“Con?ict Detection Trade-
offs for Replicated Data,”ACM TODS,V ol.16,No.4, pp.703–746,1991.
[4]R.Gruber,F.Kaashoek,B.Liskov,and L.Shrira,
“Disconnected Operation in the Thor Object-Oriented Database System,”Proc.of IEEE Workshop on Mo-bile Computing Systems and Applications,pp.51–56, 1994.
[5]J.Jing,O.Bukhres,and A.Elmagarmid,”Distributed
Lock Management for Mobile Transactions,”
15pp.118-125,1995.
[6]J.J.Kistler,and M.Satyanaranyanan,“Disconnected
Operation in the Coda File System,”ACM Trans.on Database Systems,V ol.10,No.1,pp.2–25,1992. [7]H.T.Kung,and J.T.Robinson,“On Optimistic
Methods for Concurrency Control,”ACM Trans.on Database Systems,V ol.6,No.2,pp.81–87,1994. [8]J.E.Moss,“Nested Transactions:An Approach to Re-
liable Distributed Computing,”The MIT Press Series in Information Systems,1985.
[9]M.Silvano,and C.S.Douglas,“Constructing
Reliable Distributed Communication Systems with CORBA”IEEE Communications Magazine,V ol.35, No.2,pp.56–60,1997.
[10]T.Yoshida,and M.Takizawa,“Model of Mobile Ob-
jects,”Proc.of the7th DEXA(Lecture Notes in Com-puter Science,No1134,Springer-Verlag),pp.623–632,1996.