ѧ
JOURNAL OF SOFTWARE
1999 4 10 Vol.10 No.4 1999



ϵͳ״ָ̬һŻ*
 ׼¿
ժҪɶɵķֲʽϵͳ,Ϊ˱֤ϵͳʧЧ֮״ָ̬һ,ĳһ̵״̬ؾ֮ϵĽ̵ĺ.еϵϸ,¶˽״̬֮ϵ,ԼС״̬ɵӰ.
ؼʡݴ,״̬һԻָ,ָ.
ͼšTP316
A New State Recovery Approach in Distributed System
WANG Zhun1,2CHEN Jun-liang2
1(Beijing Institute of Southern Telecommunication Development CO. Ltd.Beijing100086)
2(National Laboratory of Switching Technology and Telecommunication Networks
Beijing University of Posts and TelecommunicationsBeijing100876)
Abstract In the distributed system, all processes that depend on the process, which must be rolled back, have to be rolled back as well in order to keep the global state consistency. The dependency relation defined in the previous literature is too restrict. A new definition of dependency relation is proposed in this paper, and the influence of a process' rolling back can be reduced.
Key wordsSoftware fault tolerant, consistent state recovery, recovery block.
ݴԻϿԷΪռʱ.ʱҪB.Randell1ݵĻָ飨recovery blockĻչ.νָ,˳̶,ָڽ̵ִйлĳЩִָеԽ̵״̬ղ,д,򽫽ָ̻ĳһ޴ִ״̬,ͼַַͨͬͬԵֶεõȷ.ڻָ鷽Ӧڶ̵Ĳϵͳʱ,νпЧϵͳ״ָ̬ԵʮҪ.
һ˵,̵״ָ̬ԷΪЭģcoordinatedͷЭģnon-coordinatedָֻ.ЭĻָ,ϵͳڶִ̬йн֮ϢΪཻɵԪ,ÿԪĽ̼ضʱڵϢ,ЩԪΪỰconversation1.Ựִоз,ɻỰĸڻỰвǻỰ̽ỰԭҪỰκν̵Ĵв̾Ựǰ״̬.ϵͳĸԽΪỰĸ,ͨԻỰľ,̵ľؾõЧĿ,Էֹŵķ.ԲͬӦ,Ựֱ,Exchange2,ĿǰҲѴֻ֧Ựĳ.ЭĻָ,ɽ̵ԱָҪ״̬Ϊ㣩,öӦó͸,ıĿԸݾӦŻ,ӶͿ.
ЭĻָӦó͸,ϵͳݴԶΪñԱָ֮.ЭĻָڴ͵ļӦбձ,һöڱ汸ķ,ڼʮСʱ.д̽ϵͳвø÷до׶,һ뷨Lamport3ġڣhappened beforeϵΪ,ȷ״̬֮ϵϵcausual relation4ݣ,ĳһ״ָ̬ʱ,жϵĽ̾ʵ״̬ؾԱ֤ȫ״̬һԣ5.÷ȱ,Ϊ˷ֹŵķ,Ҫõı6,ϵͳִЧҪۿ.,ܶŲõһı㷽,Ϣ־ͬʹ.
ЭĻָ,ỰķҪỰĲڻỰĹвκηǻỰ̽.,Ự֮Ź̵ͬĻ,ֻԴеķʽִЩỰ.صĻỰ,һỰִʱϳ,ϵͳִЧʵӰǱȽϴ.
ڷЭĻָ,ѭԺ˷,һ̵ĺƱжϵĽ̵ĺ.Ľ̶ĳһ̾,ý̵ĺ˵µĺ˽ĿʮӴ.Ҫϳϵͳ״ָ̬ʱ.
ϣϢĲ,ͬһϵеĽĿԽԽ.,֮ǲϵ,ӶǲЭĻָ,ǲ÷ЭĻָ,һʧЧϵͳĻָ涼С,ͬʱҲϵͳ޴ʱЧ.
һŻ㷨,ͨ¶״̬ϵ,С״̬ؾӰ.йؽ̵״ָ̬Բͨصֶʵ.ϵͳǰ,ϵͳһʱڴڴͳϽ֮״̬һµ.ñŵǣڲЭĻָʱ,Խйؽ̴ӻỰ뿪,Ӷ˻Ự֮䲢ִеĻ᣻ڲ÷ЭĻָʱ,ԼٵһʧЧϵͳĻָ.
ĵ1㷨ɼ.2ڳ㷨.3ǰ˵ĹһЩȽ.
1
 ǵ㷨¼ģ֮ϣ
(1) ϵͳN̹ɵļ.֮Ϣͣյķʽͨ,֮,κ֮佻ķʽ.ϵͳ״̬ϵͳڸ״̬ļ.ڽ֮ͨŵ첽ԺͲԵĴ,ͬʱʵָԵĿ,ҪЩ̵״̬ͬʱϵͳĳһʱӦ̵״̬.
(2) ͨŵĿɿǱ֤.Ϣʧظյ.
(3) ̵Ϊ-Ӧʽ.ڴ󲿷ʱڴڵȴϢ״̬,̵һȡյϢ.ڴϢ֮,»صȴϢ״̬.
(4) ̵ʧЧ7ʧЧֹͣfail-stop,ҲͬһʱʧЧ.
ԮLamportڡڣhappened beforeϵĶ3.
1.1. ڷֲʽϵͳ,¼ǽ״̬ĸı,Ҳǽջ߷Ϣ.¼a¼b,ҽ
(1) abͬһڵ¼,ab֮ǰ
(2) aĳ̷Ϣm¼,bһ̽m¼.
(3) ڹϵ÷š<ʾ,<д,(a<b)(b<c)a<c.
һ㽫״̬֮ϵȼڹϵ,a<bRaRb,зšʾϵ,Raʾ¼a̵״̬.Leongˣ8Ϊϵϸ,Ϣĸ,״̬ӰϢΪҪϢinsignificant message,ҪϢĴݲϵ,ӶС˽״̬Ĺģ.ҪϢĶ.
1.2. ɽPiPjϢmǷҪ,ֻҪ֮һ
(1) mûPjʽʽ״̬仯νʽ״̬仯,̵ָݷ˸ı.ʽ״̬仯ָϢ.
(2) mûPj״̬ʽ仯,mҪϢ.
(3) mPj״̬ʽ仯,Ǹñ仯PjյһϢmд,mҪϢ.
(4) mPj״̬ʽ仯,Ǹñ仯PjδյĳϢmдmҪϢ,mm֮ύPjϢǷҪ.
mǷҪϢ,ҪϢ.
֮ϵͨҪϢµġڡϵȷ.ΪϢнһĿ.
ϵͳĳʧЧ,ȽʧЧ̾һ޴״̬,ȻѰҰ״̬ڵһȫһԽ״̬.̵״̬һµ,ָһ,ҪϢĳһ̵ı״̬֮,һ̵ı״̬֮ǰյ.״̬һµֱǲ˹¶.
1.3. mɽPiPjһҪϢ.Pi˷m֮ǰ״̬Ri,Pj˽m֮״̬Rj,״̬RiRjһ,ҽҪϢmΪ¶Ϣ,״̬RjĽPjΪϢmĹ¶.
ͼ1˲һ״̬һ״̬.

ͼ1
ڻָ״̬ʱ,̵ȷԵ,Ա֤PiݵĹPjظϢm,Ϊ¶ϢڻָĹб,Pj಻ǹ¶.ֹ۵Ϣ־״̬һֶ֮һ9,ҪϢĽսظϢ.̵ǲȷģܱ֤PiPjͬݵϢm,ȻͬݵϢ,˳ͬͬ,PjԶΪ¶.
ͨӦý̵Ŀ,.1,ĳЩӦ,ĳЩϢĹ¶,ʹ״̬ľҲӰϵͳܵȷ,Ӱ쵽ϵͳܣں½,ǽٳӦӣ.̽Ƶ,,ֽ̽зŻһ.2,ĳЩ̵Ĺؼ״̬ݾӦòͬͬԸ̵״̬ؽ,ֻҪϵͳĽ֮ݵࣨע,ǳڷݴԭ,ЧʵƵģ,ʹŽһ̶Ƚ״̬ؽĿ.
ڵ2,ǽֵĻ,״ָ̬Ż.
2Ż
,콻еԴ.
ڽϵͳеÿһԴ,ûߡмߺͽͨ·,ӦԴ̸.һ,ںеĽ׶,нһ˳һӦԴԴ,ڵõ֮,ںеͷŽ׶һĴͷЩԴ.Դ̼еĺн̽.Իͨ·̣spΪ,͵Ľͼ2ʾ.m1m3ֱǽP1P2뽻ͨ·Ϣ,m2m4ӦӦϢ.ڽյϢm1m3,ѰǷڿеĻͨ·,ڿͨ·,ѡеһ,ͨ·æ̷֮ظͨ·ıţm2ڿͨ·,̷ʧϢm4.mnmn+1ͷŻ·Ĺ,mnЯͷŻ·ı,·̽û·֮󷵻һӦϢmn+1.,û·ɱռ.

ͼ2
ڿǽP1kʧЧ.P1ʧЧ״̬˻صĳ̬l,ݶ1.2µϵ,sp״̬Ϣm1֮ǰj,ӶP2Լжj״̬ϵĽ̵ĺ.spڽյm1֮Ľ̽˽,,Ҫ˵Ľ̿ܺܶ.ʵӦ,еĺǲܵ,,绷Ϣջأеĺǲǵ,,Ӱڽеͨ.
ʵ,ؽsp״̬,ֻ轫P1״̬l,ΪP2Ƚ̲ûܵP1ʧЧӰ.P1ʧЧspĸЧӦĳһ·ռ.ͨܵĻ,Ӳͨ·Ĵ˶ԣ10ݣsp״̬.
,ڸ̵һԵ״ָ̬㷨.
,ǿ񽻻ϵͳĶûϵͳĹȷ.
2.1. ̿״̬ԶF=(Q,E,,q0)ʾ,Qǽ״̬޼,E¼޼,һ״̬ת:QEQ,q0Ϊ̵ĳʼ״̬.
pp,ppʾһ,Ϊpp乹ɵϵͳΪ.šΪ.ǽϵͳн̵ļϼΪS.Կһ̵ϵͳ,еÿһ̱ʾһܷû,Ϊ,̵ļϼΪSENV.
뼣ĸӦӣ
 һΪļ¼һ.
 (ab)ab򵥵ƴһ,һ.
 (tA)ʾtڼAе¼,tвA¼ȥ֮µļ.磺e1,e2,e4,e3,e4{e1,e4}=e1,e4,e4.
ܣ ǰ׺.ttһʼ,ҵtĳչ,ʹt=t.tt(.t=t).
pпܵļȫп֪,Ƕ庯Trace(p).
2.2. pĹܶڽpȷ,ҽ

Comm(p,p)ʾpp佻¼ļ.
,ϵͳûpĹȷ.
2.3. ϵͳĹȷ,ҽ
pSENV.ϵͳûpĹȷ.
ϵͳܵȷ,ӵûӽϵͳΪ,ûΪһϵͳҪ.Ȼ,û໥Ӧϵͳ,ϵͳܵȷȼڹȷν໥,̵ָ״̬֮䲻ϵ.
ڽϵͳ,ǽһκ漰ûһû,û֮Դ,û֮໥.бҪԴ̼Է.ûͨԴ໥Ӱ,ԷΪ:1,Ӱ˷Դľ,ռ2,ӰԴĳɹ,ռСı.û̵ĽǶϿ,ӰԺ.,ǿָӰ첻,,ԴյԴϢΪҪϢ,Եû֮Ƕ.
ǵ˼·,ȸӦϵͳص㻮û,ӸϳжϵͳܵȷǷѾ㹻.жϳ,ɶϵͳ̵ĽϵƶϳûϵĽӦϢ.ȻһԸýеĽ̽з,жϸý̽ӦϢµ״̬仯һû̵Ӱ,ΪӰԺ,򽫴ϢΪҪϢ,Ӷû֮ϵ.ûпԱǵϢ,ΪϵͳʺϵŻ.ϲڽ̵֮.
ϵͳڻָʱҪϢγɵϵ.
pһϢM=m1,m2,...,mN.miؽipһεϢ,mpΪpķϢ.pÿһϢ,mpֵ1,ΪϢһַĿĽ.ڽյһϢ֮,ϢиϢ޸ԼϢֵ.,ͬһ̽յϢıӦǵ.յϢСڻߵжӦϢֵ,˵Ϣķͽ̲˺.
pϵͳĻָ֮ؽ̵ĺ,Բǰָ˼Խp״̬.ṩһܵĽ.pͣĴ,һԻ.ڸöԻ,֮Ϲϵйؽ̷Ϣ,ռ״ָ̬,ֱеϢõӦ,p״̬õ,Ի.pĴ.ԻѡһϵͳɺʱΣڽϵͳ,Կ賿Ի,Ӷܼ״̬ϵͳӰ.ڽϵͳԵǰָ,ǽĸ.
״ָ̬㷨㷨(ף2,5ݵ )Ļ,.
Ƿ㷨ӦЭĻָʱܴĺô.һ͵ĻỰִйͼ3aʾ,p1,p2,p3p֮ĽɻỰC1,p4,p5,p6p֮ĽɻỰC2.ͼпԿ,C1C2ŹͬĲp,ʹC1C2Դеķʽִ.Խ̿Ӧ㷨,԰ͼ3bʾķʽִ.ԭ,ڶ˷ҪϢi1i2,ʹýpѭỰ̵Ļعع.

ͼ3
ڷЭĻָӦñ㷨ĺôͨͼ2˵ѾԿ,ﲻ׸.
3
ϢĸLeongAgrawal,ע⵽Ϣύܲᵼ½ս״̬ĸı,˲״̬Ϣ.ڴ˻˽һ,ָĳЩضӦý,ʹϢս̵״̬˸ıҲԲ½״̬Ϣ.֮,LeongķԷҪϢжԲҪӦýߵĲ,þ̬Ͷִ̬㷨ֶʵ֣ǵķ,ҪϢҪԱݾӦý̵.
ڻỰĲ,J.Xuһֳ֮ΪЭԭӶCAģͣ11,ģͽӻỰз뿪ΪⲿԭӶ,ΪⲿԭӶĲԿԼָӦԿ.ĵ˼ĳЩ֮֮.
ĵķǽӦý̵ص.Ϊ,ضӦáضݽṹ,ƶضķкʵ.
*оõҽίʿ.
ͨѶϵ:׼,100086,9628410901
߼顡׼,1971,ʿ,ҪоΪݴ,ͨ,ֲʽϵͳ.
¿,1933,,ʿʦ,йѧԺԺʿ,йԺԺʿ,ҪоΪ̿ؽϵͳ,,ͨ.
ߵλ ׼(Ϸͨ()ʵҵ޹˾о100086)
 ׼¿(ʵѧ̿ؽͨصʵҡ100876)E-mail: wangzhun@263.net
ο
1Randell B. System structure for software fault tolerance. IEEE Transactions on Software Engineering, 1975,1(2):220232
2Anderson T, Knight J C. A framework for software fault tolerance in real time systems. IEEE Transactions on Software Engineering, 1983,9(3):355364
3Lamport L. Time, clocks, and the ordering of events in a distributed system. Communication of the ACM, 1978,21(7):558565
4Birman K, Schiper A, Stephenson P. Lightweight causal and atomic group multicast. ACM Transactions on Computer Systems, 1991,9(3):272314
5Johnson D B, Zwaenepoel W. Recovery in distributed systems using optimistic message logging and checkpointing. Journal of Algorithms, 1990,11(3):462491
6Wang Y M. Consistent global checkpoints that contain a given set of local checkpoints. IEEE Transactions on Computers, 1997,46(4):456468
7Cristian F. Understanding fault tolerant distributed systems. Communication of ACM, 1991,34(2):5678
8Leong H V, Agrawal D. Using message semantics to reduce rollback in optimistic message logging recovery schemes. In: Proceedings of the 14th International Conference on Distributed Computing System. Los Alamitors, CA: IEEE Computer Society Press, 1994. 227234
9Strom R, Yemini S. Optimistic recovery in distributed systems. ACM Transactions on Computer Systems, 1985,3(3):204226
10Nakamura R, Ono H et al. Reliable switching system recovery. In: 1994 IEEE GLOBCOM, NJ: IEEE Inc., 1994. 15961600
11Xu Jie, Randell B, Romanovsky A et al. Fault tolerance in concurrent object-oriented software through coordinated error recovery. In: Proceedings of the 25th International Symposium on Fault Tolerant Computing, Digest of Papers. Los Alamitors, CA: IEEE Computer Society Press, 1995. 499508
1997-12-05յԭ,1998-04-17յ޸ĸ
