
Computer Engineering
1999ꡡ254ڡVol.25No.41999



WCSR: һһԵĸݿϵͳ
ء
ժҪһһԵĸݿϵͳWCSRϵͳַ֧ƶϽӣRead-Any-Write-AnyƷͣͨͬʽάϵͳһԣEpsilin-ɴԣֿ֧ɱһԵ˷ǳʺƶ
ؼʡƶһEpsilin-ɴ
WCSRA Weakly Consistent Replicated Database System
LiLing Zhou Xinmin
Dept.of Computer,National Univ.of Defence Tech.Change 410073)
Abstarct:This paper presents a weakly consistent replicated database system,called WCSR.WCSR supports mobile server and its disconnection,provides Read-Any-Write-Any replication for databases,and maintains comsistency (Epsilon-serializability)by periodic pairwise synchronization.WCSR can also support variable-consistency transaction processing.Finally,we argue that WCSR is suitable for mobile computing environments.
Key words:Mobile computing;Replication;Weak consistency;Epsilon-serializability.s
ݸָڶάݿıݣҪĿ߷ֲʽݿϵͳĿԡɿԻܡƶ㻷[1,2]УƶݿʱϽӣϸһԸЭ鲻Ч֧һ棬ȣӦɷϸһԡˣƶ㻷һһԸݿϵͳWCSRWCSRϵͳҪĿΪַ֧ƶʱϽӣRead-Any-Write-Anyƻƣ֤ϵͳĳԣάEpsilon-ɴԣ֧ûһɱһԵȡ
1WCSRϵͳ
WCSRϵͳùϵģ͡иƷܺ͹һƼϣÿһƷSӵһȫΨһıʶS.idÿƷֱͨšͨӵģôϢݱȷĴWCSRԽƶϣ˿ʱϽӡ
ûԸƷķΪλһϵж/дɡǰֻжѯ(ֻ)д񡣷UndoRedo־˿Իعɵĸ
WCSRϵͳRead-Any-Write-AnyһԸƲԣÿƷֲ֧ѯ²֮ʱĲһ¡ˣһûڷݿʱֻҪһƷɡƷӵһѯ֮󣬸ݱݿ״̬زѯڸ񣬷ʱ־УڱݿִУظûʶͽûصȴĽݸƷ˾н϶̵Ӧʱ䡣
2WCSRϵͳһԵά
WCSRϵͳУûԸݿĸ¾ΪλˣάWCSRϵͳһԣʵϾάͬϲ֮һԡ
2.1WCSR
WCSRϵͳвѯִвӰ츴ݿ֮һԣںкԲѯĴڣ˵ᵽָ
WCSRϵͳһƷղִи񣬲ʱｫ䴫ķʱͬϵܻ֮ΪͻʹĳЩĽȡ(Undo)ˣϸһԸϵͳͬWCSRִнʱԵģδûǰЩʱ񣬶ûύӦأݿÿ¼汾ύ汾ʱ汾ύ汾ӳύִе½ʱ汾Ǳʱִе½
WCSRϵͳûʱĲƼÿάһ߼ʱ(߼ʱ֮ͬLamportֲʱͬ㷨[3]ά)SӵһtʱSݱ߼ʱΪtָһʱts߼ʱӣȻt뱾ʱ־TTLС󣬷Stִн¼ظݿʱ汾С
Ƚtķ(tʼ)ıʶΪt.sidtWCSRϵͳȫΨһʶΪt.id=<t.ts,t.sid>WCSRϵͳidʱʱt1t2ʶ֮ϵ£

WCSRʱ־TTL¼бط֪ʱвûֱӷط񣬻Ʒϴʱ־еʱ񶼰idĴС
2.2WCSRϵͳĳɶͬ
WCSRϵͳԵĳɶͬʽʱĴͲͬƷ֮ͬÿͬڣѡһཻͬδ֪ʱʹߵݿ״̬һ¡ֳɶͬѾһЩһԸϵͳеõӦ(Bayouϵͳ[4])ŵǣ翪ϵͣɿԸߣʹϣڹϻָͬ̽δ֪͸
WCSRϵͳеķڳɶͬУǰid(<ts,sid>)Ĵһͱصʱ־շյʱ־뱾ʱ־ϲ°idĴСʱ͵ԣÿάһʱNTSVڼ¼ʱ־֪ʼڸƷʱʱڳɶͬУͨȽNTSVһֻһδ֪ʱ񣬶شʱ־Լ翪
ɶͬеĽշӵµʱ֮󣬽յÿʱt뵽ʱ־TTLУͬʱtıʶ<ts,sid>±صNTSVЩʱʱ뱾TTLеԭʱ棬˽շҪع֮ʱ񣬲TTL֮µĴִʱ񣬵õµݿʱ汾󣬷ҪµõʱжǷҪص߼ʱӡ
WCSRɶͬе־һֵĽʽֻ̣贫ͶԷδ֪־֣˶ԿܷϾкܺõݴԡ
2.2.1ɶͬеͻ
ڽĸ־ʱҪعصĲʱڲͬʼʱ֮ĲԣЩͻʱϵͳѡزĳͻ
Ϊ˽ʱʱزʣWCSRϵͳһֻӦĳͻⷽ÷ӦóָʱĳͻԼͻܹⷽʱĳɹʡƪޣǽרϸWCSRϵͳлӦͻⷽ
2.3WCSREpsilon-ɴ
ϸһԸϵͳеĲ㵥ɴ(1SR[5])׼򣬶ڲһԸЭWCSRϵͳ䲢ִв1SRΪǽCalton PuһԸϵͳEpsilon-ɴ[6]ĸΪWCSRִ׼Ǽ򵥽һEpsilon-ɴԵĸ
Epsilon-ɴ(Epsilon-serializability ESR)׼ϵͳ첽ķʽάƽһ(һ)֧ESR׼ķֲʽϵͳڲͬĸƽ֮ʱĺ޵Ĳ𣬵и񴫲ÿƽ֮иƽ״̬1SRһ״̬
ִʱݲгЩһִе(schedule)һִееĲж˳ִе񹹳ɣнƸõһ(serial)ȡһѯ͸ִеsӸõɾвѯĲ֮ʣɸɵִеs' һеȣsһEpsilon-еȡһִеȵִнȼһEpsilon-еȣƸõEpsilon-ɴ(serializable)ģESRȡ
ESRѯִ⽻棬˲ѯܻʵһµݡǣΪѯ񲢲ıݿ״̬ESRȻܹ֤άݿһԡ
WCSRһһԸϵͳƷݿ״̬ʱĲһ¡ǣͨԵĳɶ̣ͬWCSRϵͳ֮ͬĲһԣʹϵͳһµ״̬ͬڸִеĲҲһеĵС֤(֤)ûµĸʱWCSRϵͳезϵݿ״̬һ״̬зʼĲ֮Epsilon-ɴԡ
3  ʱû
УǼٶִжʱģδûڳɶͬлعĿʹĽûЩʱҪʵʱûתΪύWCSRϵͳԲʱû(ύ)㷨ǷֱȻ(Natural Converge,NC)ύ㷨(Primary ServerPS)ύ㷨㷨ȱ㣬ڲͬĻƪֻ򵥽һύ㷨
3.1ύ㷨
ύ㷨WCSRϵͳָһΪύʱ񡣾˵PSĳɶ֮ͬPSյʱidĴύͬʱÿύһύк(csn)Щύ񽫺ʱһڳɶͬдķ˸ύʱ֮⣬Ĺȫͬ
WCSRϵͳʼĳһʱǰid˳򴫲Ҳ⣬ύ㷨Уʼͬһʱύȫǰidġǣύ㷨֤ύ˳ͬidĴʼڲͬύȫȡЩͨɶ̵ͬ˳ĳЩύܻʼid֮Ϊȷϵͳһԣύ㷨뱣֤ÿύִеĴһģΪҪWCSRϵͳ־֯Լɶ̼ͬ޸ġ
ڲύ㷨WCSRϵͳУ־ɣύ񲿷ֺʱ񲿷֡ύĽѾûִдԼٷ仯ʱ񲿷ȴԺĳɶͬлع־Уύʱ֮ǰǣύ㷨ύͬidĴǸΪ<csn,id>Ĵ־򣬲ʱcsnΪ<csn,id>ϵΪ

ǣ֮ĳɶ̲ͬҪδ֪ʱ񣬻Ҫδ֪ύʱƣΪͬжЩύǶԷδ֪ģÿSҪάһS.LCSNS־ύcsnֵԱʾS֪ύ񲿷֡
֤Ȼύ㷨֤ύ˳ͬid˳򣬵ʹύ㷨WCSRϵͳУÿϵύ˳Ȼһµģ䲢ִEpsilon-ɴԵġ
4ɱһ
WCSRϵͳҪԵǿԵһӦáǣʹһӦҲڱҪʱҪϸһԣһ񷢸֮ҪύҲûٷع
WCSRϵͳУǰҪύĸǿ(Strict TransactionST)Ӧأǰ۵һ(Weak TransactionWT)ΪԣУȻǰᷨδύΪʱ񣬶ύ֮ύ
ǹ涨ǿĶ/дֻܶϵͳµݿύ汾Уʱֻܶ/дݿµʱ汾ǿִв뱾طеʱͻΪ˱֧ǿĹ棬Ҳ֧ӦõĿɱһԣWCSRϵͳʱύ㷨ʱݿύ汾ϵͳݿύ汾
SӵûһǿstΪstһΨһǿţsnostʱΪ0ȻSst͸PSPSûӦ򷵻ʧϢSûһʧϢǿstزۣPSӵstִstύύstһύкcsnst<csn,0,S>Ĵ뵽PS־(ύ־)ִнԼst.csnظSӵķϢSûɹϢԼִнˣǿstѾ˳ύĳɶͬдķϡ
֤ǿ벢ӰԭWCSRϵͳȷԣ֧ǿĿɱһWCSRϵͳУƷϵύһµģ䲢(ѯ)ִȻEpsilon-ɴġ
5WCSRϵͳ
Ϊ֤WCSRݿϵͳȷԣھʵһԭ֤ϵͳWCSR-SPԸƽ϶WCSRϵͳģ⡣
ʵģWCSRϵͳĸһԿԵõ֤临άǿԳܵģͬ븴ƽԹϵʱύٶҲȽϿ죬һڼ֮ͬڼύϵͳҲȽϺá
ûķܷ棬WCSRϵͳRead-Any-Write-AnyĸƻƣûӱطõִеĽнϿķܡ
WCSRõһԸЭԼԵسɶͬڸƼвֽĹϲӰϵͳȷWCSRϵͳкܸߵĿɿԣңֻҪûܹʵһWCSRƷʹ÷ʧȥϵ(ж)ûȻܹʸݿ⣬ϻָ֮÷ͬû񴫲ˣWCSRϵͳзǳõĿԣرʺƶ㻷
6С
WCSRһԸݿϵͳʵиƷ֧ͬEpsilon-ɴ(һ)ʵʱĽû֧ӦõĿɱһԣ߷ͬʱʱĳɹʣܺܺõ֧ƶ㻷
߼飺ءУ27꣬ʿƶƶݿϵͳ
ߵλ:ƼѧѧԺɳ410073
ο
1Imielinski TBadrinath B R.Mobile Wireless ComputingChallenges in Data Management.Communications of the ACM199437(10)18-28
2أ.ƶݿ⼼:ս.ѧ199724(3)
3Lamport L.TimesClocksand the Ordering of Events in a Distributed System. Communications of the ACM197821(7)558-565
4Demers A.The Bayou Architecture:Support for Data Sharing Among Mobile Users.InProc IEEE Workshop on Mobile Computing Systems and ApplicationsSanta CruzCalifornia,19942-7
5Bernstein P A.Concurrency Control and Recovery in Database Systems.Addison Wesley Publishing company1987
6Ramamrithan KPu C.A Formal Characterization of Epsilon Serializability.IEEE Transactions on Knowledge and Data Engineering1995(7)
ո:1998-06-15
