о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



һֻڽķֲʽ㷨DCC
֣ޱ֣γ
ժҪվȺϵͳҪһܵĲļϵͳӦ롢ݴҪ󣬶߲ļϵͳܵĹؼǺ漼.һֻڽķֲʽ㷨DCC.㷨ۺ˻ȫֹͻھֲϢ㷨ŵ,һλڽϵϢվķ,ͨϢվϢάﵽȫϢĸ.㷨ûľֲϢάԣλжϵ׼ȷ.GMS㷨Hints㷨ȣDCC㷨ĿСҾнϺõĿչ.
ؼʡȺϵͳ,ֲʽ, Ϣվ 
ͼšTP338.8
A DISTRIBUTED COOPERATIVE CACHING ALGORITHM FOR WORKSTATION CLUSTER FILE SYSTEM
ZHENG Xiao-Wei, ZHENG Wei-Min, and SHEN Mei-Ming
(Department of Computer Science, Liaoning Normal University, Dalian 116029)
(Department of Computer Science & Engineering, Tsinghua University, Beijing 100084)
AbstractWith the development of workstation cluster systems, a high performance file system on such systems is needed. A impotent technology to further improve the performance of cluster file system is cooperation of cache. A distributed cooperative caching algorithm (DCC) is brought forward in this paper. This algorithm combines the advantages of the global manager based algorithms and the local message based algorithms. It gives a concept of master copy message station. This approach uses active safeguard decision of local messages. The judgment of master copy position is more accurate. Consequently, the cost of the algorithm is the lowest among the available algorithms and it also exhibits a good scalability.
Key wordscluster system, distributed cooperative cache, master copy station
1
NFS, AFS1ݵȴͳļϵͳļģַĿչԽϲϵͳģ,Ϊϵͳƿ,ӵ.ϺõĸĽǷֲʽ漼ü÷ֲʽ㷨ȫֹ,ļϵͳĹ䵽ɣϵĻ໥ЭнϵĻԿһȫֻ.Ӧóʹļ鱣ڽڴ滺,ٴηʸÿͿԾöضд,Ӷϵͳٶ.
ƺ㷨ʱӦ⽵;ֲܣӦóҪڴʱý㲻ӦκԶ̽ݿ飬Ӧ滻ȥ.㷨һصȫݿĿٲңеķΪȷϢһʹȫֹά㻺оȷĿϢַʽGMS㷨2ݡXFS3еN-Chance㷨һΪģϢҪάȷȫϢ,ͨÿõһϢĿ¼ģңHints㷨ȣ4.
N-Chance㷨,ȫֹԷֲʽɶάڻеλúͿһԣÿοʱֱҵڻе׼ȷλã㷨Ŀܴ󣬶ÿαؿȱʧʱҪͨҵλãҪȴش.
GMS㷨Ҳǲ÷ֲʽȫֹռȫϢ,ȫϢȷݿλãȻGMSҪһеĹռϢдͷͣչԲ.
Hints㷨÷ǾȷȫϢHintsк,ͱN-Chance㷨GMS㷨άȷȫϢĿ.Hints㷨ÿάһHints,¼ȫеϿʱϢԼλϢ.Hints㷨õλͷ̶,˻ȻڻУڽȴҲ򲻶ϵǰͶλҪǰͲҵ.Hints㷨ĳԾ޷ʱ֪һԾΪеڸǰ͹ϵʱHints㷨άЩϢɵ.
DCC㷨(distributed cooperative caching algorithm)ۺ˻ȫֹͻھֲϢ㷨ŵ,øľֲϢٶԹ,ȫϢԼپֲߴ.DCC㷨ϢվMCS (master copy station) ĸMCSбϢԸվķʿʱ֪ҪʵļĿֱӶλ˷ʱ䣻һļΪͨMCSάֻҪڻУ㼴ɷʵضȡ.ڻȺϵͳиҪƵͨʶԷĴ̺ͻ棬DCC㷨ЩͨӴͱϢԼȫ״̬ϢʹϾȷȫϢϿش㷨ĿС,ҾнϺõĿչ.
2 DCC㷨ĺṹ
ڻȺϵͳDCC㷨ĺģͽдеݿͳһַ ,ÿݿ鸳һ.
ϵͳn.i㻺еݿ鼯ΪMi еݿ鼯ΪDiлеݿļдݿ鼯ϵӼ

ڵi,MiΪػ棬DiΪش;MjjiΪԶػ, DjΪԶش.ÿеݽṹͼ1ʾͼд˵.

ͼ 1DCC㷨ĺݽṹ
CM(cache manager):ȡȫֹ,еĺɷֲڸϵĻͬЭ.
̿λñDCL(disk copy list):еļӦĴ̿ԼӦűDCLУѯDCLɵ֪ĳļĸУÿݽṹͬDCLһȷٸı.
鼰ϢվMCS(master copy station):Ϊ֤ıϢܻȶȫϢ롰顱(master copy)ĸ.һζ뻺ļ̿Ϊ飬Ϊ飬ǰ͵ʱΪȫ飬ٴηʾͨõ.MCSм˱ش̿ǷѳΪԼλϢλֻڱǰʱŸı䣬еϢĸϢ.
ȫʱGVT(global vector time):ָһGVTnϵʱVT1ݣVT2ݣVTn.ÿϽк¼ʱ,޸ֲʱ
VTi=max(VT1ݣVT2ݣVTnݣ1
ͬʱ¼ϱ㵱ǰʱֵΪûʱҿԱȽ¾ɳ̶ȼߣͳʱӣ5ֻܱȽϵ¼ȺܱȽ¼Ⱥ.
3DCC㷨ĿҼ滻
DCC㷨Ҫǿ滻㷨ͨDCLMCSĲҼάʵֶλõжԼķ.DCC㷨ԺĹ:
dnsΪȫֵsʱnϷʵݿŲԻķʣMnsΪnϵݿ鼯.snϱؿȱʧʱľEnsһԪ(a,r,v,)ʾ,a{local, remote} ʾԶطʵĿǷ񻺴ڱ, r{, move, copy} ʾԶطʵĿǨƻǸƵ,vΪصı滻.
a=remote򱾵ػδv=,ʾѡ滻;a=local ұػv=d, dMns,dΪ滻飻=(e,m) ΪһԪ, ʾvǨƵm滻mϵĿe,eMmsa=remotevǨ,=.
ڲʱ,ÿȼ鱾صϢվMCSҪʵݿͷ,ֱӷ,о.ĳļĲҼ滻Ϊ:
(1) 鲻ڻEns=(local,copy,,).
ؽn=2, ļdns=5, ԶشDj=1(5ſ1Ž).
̣鱾DCL2,ٲMCS1,5#Ϣ;ʱӳ,㱾ʱӣMCS1м2:5#ʾ5#2㻺УӴD1ж5#鲢ʱ,ȻƵM2,ͨʱ˳MCS1ı仯MCS2.
(2) ڻEns=(local,copy, v,)
n=3, dns=5, =(e,4)
̣鱾صDCL3MCS1,ѯ5#2Ž㻺; ʱӳ򣬼ʱӣ3ŽеvǨƵ4Ž㣬滻4ϵĿe5#鸴ƵM3ʱͬʱ˳MCS1ϢݸMCS33ŽΪ5#ĸ.
(3) Ҫ滻ǰEns=(remote, move, v, )
n=2, v=dns=5 , =(,5).
̣ѯDCL2,MCS1,5#λøΪ5: 5#ͬʱMCS2MCS5һ޸ģʱӳ,ʱӣ5#ʱƶ5ŽΪȫ飻2Ž㻺е5#.
(4) ǰͺٴαEns=(local,copy, v,)
n=1, dns=5
̣MCS1,֪5#5Ž,MCS1иΪ1: 5#,ʾ5#ѻ1ŽϲΪ.ִʱӳ,ʱĺ5#5ŸƵ1Ž㲢滻v.
(5) 滻㷨ǰͽѡ
㷨£
 ʱֵڱرLRUѡϵķ,
 LRUֻ飬ѡϵ飬ʽ1ϵȫʱVCTеĽΪǰͽ㣻
 ýΪؽ㣬Ϊ㣬ǰ.ػϿǰͿʱҪ£ǰͿǰͣǰnҲսǰͿ鶪.
4DCC㷨ģԽ
ͨʵģϵͳ6ݶDCC㷨˲Լ,DCC㷨Hints㷨ԵĽ˱Ƚ..
ϵͳΪ8155Mbit/s ATMӵĹվȺϵͳϢվ8㻺200/400/800飬̿10 000飬С 8KBʴ50 000Σطʱ0.25 ms,Զطʱ1.5 ms,̷ʱ15.85 ms,ӳ0.2 ms.
4:
A:ļʼжȦ=30/5(5%̿30%ķʱ),صȦ=1(ʾͬݼ).ʵ1Žе,400飻
B:ļʼжȦ=30/5,صȦ=1.зʼתʽֲڸ,400飻
C:=30/5,=1000(ԷʼƵ).зʼ400飻
D:=5/5,=1.㼯зʼͬʼתʽֲڸĴϣ400.
(1) ֲϢ׼ȷԲ
DCC㷨Hints㷨,άֲϢڱؾ.
ڿʱάϢվMCS׼ȷ.ñϢжϱȱʧ㻺Ĵռұȱʧд֮1ʾ.
 1DCCHintsλñ׼ȷԱȽ

ABCD
DCC91.35%86.02%85.10%88.07%
Hints54.27%53.28%76.90%65.48%

ӱпԿ,DCC㷨4¾Hints㷨DCC㷨˻ľֲϢά.ÿν佻Ϣʱ,˳˫״̬ϢԼйϢ,ʹϢȽ׼ȷ,Hints㷨,ֻǰͿʱ,˫ŽϢ.
(2) ʼжȶ㷨ܵӰ
A,ʼжȷֱΪ30/520510555۲㷨ƽʱͼ2ʾ.Կ,żжȱС,㷨ܶڽ,㷨ܵĲС.DCC㷨ܽϺõļݵļж,ܽϺ.

ͼ 2ͬʼжȶ㷨ܵӰ
(3) ϵͳнܵӰ
ͼ3ʾϵͳнݷֱΪ81632ʱ㷨ƽʱ.Ž,Hints㷨ܻ,DCC㷨ŽӶ.˾нϺõĿչ.

ͼ 3ϵͳн㷨ܵӰ(A)
ӲԽԿ,ֲʽ㷨DCCŽ,,˿ڻбļ,Ӷϵͳ.

5
DCC㷨øϵϢվMCSĽϾȷıϢȫϢкĹߣЧݿʵ׼ȷԣ˷ʱ.㷨ݽṹʹ˴λñDCLļź֮ӦĽţʹļĲڱؽУȻٲѯMCSϵϢ ͿԽһѰʱ䣬Ӷ㷨Ŀ.ʱֻ轫DCLԼ޸ļɣMCSӰ죬㷨ĿչҲϺ.
߼飺֣ޱŮ195710ڣҪоΪϵͳṹļϵͳ.
֣γУʿʦҪоΪϵͳṹֲʽϵͳд.
ŮʿʦҪоΪϵͳṹֲʽϵͳд.
ߵλ֣ޱʦѧϵ116029
֣γ廪ѧѧ뼼ϵ100084
ο
1Howard J,Kazar M,Menees S et al.Scale and performance in a distributed file system.ACM Trans Computer Systems,1988,6(1):5181
2Feeley M J, Morgan W E, Pighin F H et al. Implementing global memory management in a work station cluster. In: Proceedings of the ACM Fifteenth Symposium on Operating Systems Principles, USA, 1995. 201211
3 Amderson T E, Dahlin M D, Neefe J et al. Serverless network file system. In: Proceedings of the ACM Fifteenth Symposium on Operating Systems Principles,USA, 1995. 109126
4 Prasenjit Sarkar, Johnh Hartman. Efficient Cooperative caching using hints, In: Proceedings of Second Symposium on Operative System design and Implementation, USA, 1996. 3546
5 Fidge C J. Logical time in distributed computing systems. Computer, 1991, 24(8): 2833
6 ξﷶ. һֻȺļϵͳĺٻ漼. ѧ 1997 20(10) 899907
(He Jun, Tian Fanjiang, Wang Dingxing. Cooperative caching in the network file system on workstation cluster. Chinese Journal of Computers(in Chinese), 1997, 20(10): 899907) 
ԭյڣ1998-12-11޸ĸյڣ1999-04-08.
