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



˫Э»hintʽ滻㷨
¡ף־ΰ
ժҪʽ漼߻ȺļϵͳܵĹؼ֮һ.s2fs(scalable single-image file system)һһӳȺļϵͳԭ,˫Эʵ˷ϸUNIXĺʽ.Ϊs2fs˻hintʽ滻㷨,Ϊ佨ܷģ.,ͬеĺʽ滻㷨N-chance,ʽ㷨¶ЧؽI/OӦʱ.
ؼʡʽ滻㷨,N-chance㷨,˫Э,s2fs(scalable single-image file system),ʽ.
ͼšTP316
Hint-based Heuristic Cache Replacement Algorithm under Dual-granularity Protocol
WANG Jian-yong1,3 ZHU Ming-fa2,3 XU Zhi-wei2,3
1 (Department of Computer Science and Technology Beijing University Beijing 100871)
2(National Research Center for Intelligent Computing Systems Beijing 100080)
3(Institute of Computing Technology The Chinese Academy of Sciences Beijing 100080)
Abstract Cooperative caching is one of the key technologies used to improve the performance of a cluster file system. s2fs (scalable single-image file system), a single-image cluster file system prototype, uses dual-granularity cache coherence protocol in order to implement efficient cooperative caching which meets the needs for strict UNIX-semantics. In this paper, a hint-based heuristic cache replacement algorithm under s2fs' dual-granularity protocol is proposed, and the analytical models are established for heuristic algorithm and one of the existing coordinated algorithmN-chance. The analytical results show that the heuristic algorithm can effectively reduce the I/O response time compared with N-chance algorithm almost in each case.
Key wordsHeuristic cache replacement algorithm, N-chance algorithm, dual-granularity protocol, s2fs (scalable single-image file system), cooperative caching.
ԽԽķֲʽϵͳø罫ڵ,ԶڴΪһ͵ڴṹ,ΪͨߴʱӵԶڴķҪȱش̿ö.Զ̻ṹ(remote caching architecture)1ǿ˸洢Σڴ桢Զڴʹ̣֮ϵĲ.ϵͳнڵ㻥ȡԵıڴԳԶڴ,ֶԳʽṹȻͬڴͳĿͻ/ģ,ף2,3ݳΪʽ(cooperative caching).
ƵĻȺļϵͳCOSMOS.Ϊ˱֤ṩһϵͳӳܵͬʱ,ﵽI/OչԵĿ,Ҳ˺ʽȼ.Ŀǰ,COSMOSϵͳԭѿ,ΪδCOSMOSϵͳ,ǳĿǰCOSMOSԭϵͳΪs2fs(Scalable Single-image File System).
1 s2fs˫Э
1.1 s2fsһչĵһӳļϵͳ
s2fsǻAIXϵͳʵֵȫļϵͳ,߱ϸĵһӳ,ʵunixļ,ڲĶAIXĵǰ,֤unixӦóȫƼ.,s2fsΪ˻ýϺõĿչԺI/O,ʵ˺ʽ桢зֲʽԪݹд洢.
s2fsɺز.s2fsĺĲļϵͳһʵֵ,Ҫǽ߼ļϵͳI/O.s2fsû3ûdaemon,Э,ͬs2fsصI/O.3daemonֱΪͻclientmanagerʹ洢storage.Ӧó򷢳s2fsصϵͳ,߼ļϵͳļϵͳ,I/O󴫸s2fsıؿͻ,I/Oɱؿͻõ,ת,ɹ֪ͨӦĿͻ洢ɾļ,ѽתؿͻ,Ȼ󾭹ļϵͳ߼ļϵͳѽظӦó.ͼ1s2fsϵͳ֯ṹ.

ͼ1s2fsϵͳ͸ͼ
1.2 ˫Э
ڷֲʽļϵͳ,ȵĻһЭݶдġٹ,ϸһάһ,̫ĸ,ĲҪĿ.ڴȺϸάһԾͿֲ˫ԵĲ֮,Ϊs2fsƲʵ˫Э.ʵ,ڵЭ,˫Экô(1) άһԶķ˵Ĺأ(2) ܹٿͻͨţ(3) ΪҪ,ܹṩĳЩhintϢ,ļϵͳЩhintϢһͷĸ翪.
s2fsڿļάһԵ.xFS,s2fsڿһöдάһԵ,Ͳ׸.ļһ,s2fsûص(callback)άһ.һͻһļ,ҲڲĹд(concurrent write-sharing)ʱ,͸ÿͻһļĻص,ŵͻԳͻʽ򿪸ļʱ,֪ͨÿͻص(callback break).ͻرĳдʽ򿪵ļʹļٴд״̬ʱ,ֻ¸Ŀǰڴ򿪸ļ״̬Ŀͻһص.ʵs2fs˫Эʱ,ص״̬Ǵһصṹе,ڸýṹл¼ļšĿǰڴ򿪸ļ״̬ĿͻĿļȼļڴϵλã洢żʼڵţ.ЩϢܹͿĶλ(block lookup),άһԵĿ,ҿΪhintڻ滻,I/O. 
2 ʽ滻㷨
2.1 о
ʽΪļϵͳĴ洢һµĲ,Զ̿ͻڴ.ͬĿͻ㷨ԲͬķʽһµĴ洢.Daulin M.D.ף3в˼Ҫĺʽ㷨,N-chanceת㷨ΪʵеġҲõĺʽ㷨.㷨ݿͻI/OΪ̬صʽǲֻĴС.Ҫ˼,Ȼ±飨ϵͳĻֻһ.һͻ滻һ±ʱֱӰӵ,ѡһͻ,Ѹù±ת,ù±Nת.ʵN-chance㷨ʱ,ͨҪһЩƴʩԷֹЧӦ,תĹ±һ±תȵ.
2.2 ʽ滻㷨
ȻN-chance㷨ù±Ȳ,ϵͳͬһ黺ĿĿ,ԵϵͳЧĿռ,в֮(1) ÿη滻ʱ,滻鲻ͻתĹ±,ͻҪѯʹ,жϱ滻ǷΪ±,翪滻Ӧʱ䣻(2) ת±ʱ,㷨ѡҪչ±ĿĿͻ,ûпǵϵͳиͻĴȡģʽڴȡת±ĸʣ״̬г̶ȣ(3) תеĹ±.ʵ,Щ±ڽԶᱻȡ,Щ±תú.
Ƶʽ滻㷨¼Ϊʽ㷨άĳЩhintϢ,˷N-chance㷨ȱ,һǿ͵N-chance㷨.ʽ㷨ڵhintϢе˫Э,ĳͻĳļǷڴ״̬Ƿڹ״̬ȵ,ЩhintϢҪʽ㷨Ĺ.һhintϢǹڻǷΪ±,ɿͻ͹ͬά.ʵʽ㷨ʱ,Ϊͻ˵Ļ״̬һЧĹ±״̬־ncbc(number of cache block copies),ֵΪ1ʱ,ʾΪ±;ֵΪ2ʱ,ʾϵͳиûĶ濽.ڿͻ˽л滻ʱֻı滻ǷΪ±,ncbc־㻺滻Ҫ,ϵͳĳľ忽ĿɹΪάһԶ¼.ncbcľά£
* ĳ1ΣӴ洢Ĵϣ/дػʱ,ncbcΪ±״̬ncbc=1
* ͻ֮תݿʱ,˫ԵncbcΪ2,ʾϵͳж2
* һͻִд,дݿͻ˵Ļ鿽ΪЧ,ͬʱ,صıдݿΪ±״̬ncbc=1
* ĳͻִл滻,ʹϵͳĳ黺ĿĿ2Ϊ1ʱ,֪ͨӵиù±Ŀͻ,ʹݿncbcΪ±״̬ncbc=1.
ĳһʱ,ϵͳеĵiͻĵj鱻ѡΪ滻,ǰΪbij,bijļΪf,ʱbij״̬У
A: bijͻתĹ±
A.1: bijδתNΣ
A.2: bijѱתNΣ
B: Ŀǰκοͻڴf״̬,ζbijڣԶᱻã
C: fڴ״̬
C.1: ֻбؿͻf
C.2: ϵͳk(k2)ͻڴf״̬
C.2.1: bijncbc1
C.2.2: bijncbc2.
ǵʽ㷨,bijA.2,BC.2.23״̬֮һʱ,ת,ֱӰbijbij״̬A.1C.1ʱ,ͻiѡһͻX,bijתXbijC.2.1״̬ʱ,ͻiȸ߹ĿǰҪת滻bij,޸껺״̬ͻiӦϢ,ӦϢа˽ҪbijĿĿͻY,YΪһʹfĿͻڴf״̬.ͻiյӦbijתͻY.ʽ㷨hintϢ,ͻԼжϳbijǷΪ±,ϵ,ͬN-chance㷨,BC״̬,ʽ㷨ܹʡһ紫,ʽ㷨ܹݿͻصĻصṹжϱ滻ļĿǰǷпͻʹ,ûпͻʹãB״̬,ʹbijΪ±Ҳת,ʹϵͳкʽŸЧݿ.,ȻC.2.1״̬Ҫ,˷һ紫,ȴ˸ת±ıػ.
3 ģ
Ϊʽ㷨,Ϊʽ㷨N-chance㷨˷ģ,ԱԶߵܽбȽ.Ϊ˼,ǵķģֻԶӦʱ,Ǻ,Ϊϵͳжռıϴ,ӰϵͳܵҪ.
һζڲͬĴ洢οɵõĸʷֱΪػPl,ԶPrPd,ڲͬ洢εõӦʱֱΪTl,TrTd,滻ʱΪT滻,ƽӦʱΪTӦ,йʽ.
Pl+Pr+Pd=1,(1)
TӦ=PlTl+PrTr+PdTd+(1-Pl)T滻.(2)
ǻ滻ʱӰܵļҪ.
Rct: ʽ棨ڴͻתĹ±Ļ棩ռͻ˻ı
Rnl: ڲᱻõĻռػ棨ʽ棩ı
Pso: ļڹ״̬ĸʣ
Psgl: ػдڹ״̬ļĻǹ±ncbc=1ĸʣ
Pk2: ؿͻڴf״̬,ϵͳҽͻڴf״̬ĸʣ
Psr: ݿ鹲ĸ,ͻiѹ±bijתͻY(пͻiYڴf״̬),ֱͻYضеĸʣ
N: N-chance㷨Զ̻Pr뱾ػPlıֵ,ʽ,
(3)
N-chance㷨·滻,ұ滻bijͻתĹ±ʱ,ؿͻҪϢѯbijǷΪ±,Ҫ/Ӧ紫.һ紫ʱ䣨ָϢʱӣΪThop,N-chance㷨µ滻Ϊ
TN滻=(1-Rct)(2Thop).(4)
ʽ(1)(3)(4)ʽ(2)õN-chance㷨µ1ζӦʱΪ
TN-chance=(T1-Td+N(Tr-Td)-2(1-Rct)Thop)Pl+Td+2(1-Rct)Thop.(5)
PA,PB,PC,PC1,PC2,PC21PC22ֱʾ滻ʱ滻鴦״̬A,B,C,C.1,C.2,C.2.1C.2.2ĸ,2.2б滻״̬ӰܵҪĶ,йʽ.
PB+PC=1-Rct,(6)
PC=(PB+PC)(1-Rnl)=(1-Rct)(1-Rnl),(7)
PC1=PC(1-Pso),(8)
PC2=PCPso,(9)
PC21=PC2Psgl,(10)
PC22=PC2(1-Psgl).(11)
ʽ㷨½л滻bij״̬C.2.1ʱ,紫,C.2.2״̬k=2ʱ,Ӧ֪ͨĳͻʹ仺Ϊ±,1紫,ʽ㷨µ滻Ϊ
T滻=PC212Thop+PC22Pk2Thop.(12)
PlPrֱΪʽ㷨µıؼԶ̻.ͬN-chance㷨,ʽ㷨״̬C.2.1ת±ʱܹӱ,ıܵĻ(غԶ),йʽ.
Pl+Pr=Pl+Pr,(13)
Pl=Pl+PC21Psr.(14)
ʽ(3)ʽ(6)(14)ʽ(2)ɵõ
T=TN-chance+(Tl-Tr)(1-Pl)(1-Rct)(1-Rnl)PsoPsglPsr+(1-Pl)(1-Rct)Thop
((1-(1-Rct)(1-Rnl)PsoPsglPsr)(1-Rnl)Pso(2Psgl+(1-Psgl)Pk2)-2).
(15)
4 
s2fsϵͳڵƽ̨,ڵ֮10Mbit/s̫,ǹϵͳõĳЩȡף3й̫ݣĴСΪ8Kbytes,ڴĴȡʱΪ250s,ʱThop=200s,ݵĴʱΪ6 250s,Ӵ̶ȡһݵʱΪ14 800s,ô,Tl=0.25ms.ף3ݲͬ,еTr=7.1ms,Td=21.9ms.ΪǵϵͳԪݵĹݵĴ洢ͻǷֿ,Զ̻ϴȡҪ3紫.
ӰӦʱĲȡֵģÿȡ3ֵ,ֵ׼ֵֵ.Rct,Pl,N,Rnl,PsoPk2Ǵף4,5ݷ.,PlNһȡֵ,Ϊص,Plʱ,NС;PlСʱ,N.PsrPsgl,Ƿֱȡ10%,50%90%Ϊֵ׼ֵֵ.ЩӰܵҪȡֵ1.
1 ĳЩӰϵͳܵĲȡֵΧ

RctPl,NRnlPsoPk2PsrPsgl
ֵ0.050.67,0.2120.050.400.020.100.10
׼ֵ0.300.78,0.180.150.650.060.500.50
ֵ0.550.94,0.040.250.900.100.900.90


ǽRct,Pl,N,Rnl,Pso,Pk2,PsrPsglͬȡֵϴ빫ʽ(5)(15),ԷֱõN-chance㷨ʽ㷨,һζӦʱ.,Щȡֲֵͬʱ,Ӧʱʽ㷨±N-chance㷨¶в̶ͬȵĽ.,Щȡ׼ֵʱ,ʽ㷨N-chance㷨,Ӧʱܹ6.4%Rct,RnlPk2ȡֵ,Pl,Nȡ׼ֵ,Pso,PsrPsglȡֵʱ,ʽ㷨,Ӧʱ併34.885%ʹ,Rct,Pl,RnlPk2ȡֵ,Pso,N,PsrPsglȡֵʱ,ʽ㷨N-chance㷨,ҲܹʹӦʱ併1.085%.ͼ2˵һ.

ͼ2㷨ܱȽ
ͼ3˵Rct,PlNȡ׼ֵ,Rnl,Pso,Pk2,PsrPsglȡֵͬʱʽ㷨Ӱ.ͼ3пԿ,Pso,PsrPsglȡֵԽ,ʽ㷨ԶӦʱĸĽҲԽ.֮,RnlPk2ȡֵԽ,ʽ㷨ԶӦʱĸĽԽС,Ӱ̶Ȳ.,ͼ3Ҳ˵˲Rnl,Pso,Pk2,PsrPsglȡʲôֵ,ڽI/OӦʱ䷽,ʽ㷨N-chance㷨.

ͼ3Rnl,Pso,Pk2,PsrPsglȡֵʽ㷨Ӱ
5  
s2fsϵͳ˫Э,һֻhintʽ滻㷨,÷ģ˵ʽ㷨еN-chance㷨ڽI/OӦʱ䷽нһĸ.,ǽs2fsϵͳоʵʽ㷨,ʵʵӦʽ㷨I/OܵĸĽ.
עоõȻѧ͹863߿ƼĿ.
ͨѶϵˣ,100871,ѧѧ뼼ϵֲϵͳо
߼飺,1969,ʿ,ҪоΪ/ֲ.
ף,1945,ʿ,оԱ,ʿʦ,ҪоΪܼϵͳ.
־ΰ,1956,ʿ,оԱ,ʿʦ,ҪоΪмϵͳ.
ߵλ¡ѧѧ뼼ϵ  100871
ף־ΰܼо뿪  100080
¡ף־ΰйѧԺ㼼о100080
ο
1Leff Avraham, Wolf Joel L, Yu Philip S. Replication algorithms in a remote caching architecture. IEEE Transactions on Parallel and Distributed Systems, 1993,4(11):11851204
2Anderson T E et al. Serverless network file systems. ACM Transactions on Computer Systems, 1996,14(1):4179
3Dahlin M D et al. Cooperative caching: using remote client memory to improve file system performance. In: Proceedings of the 1st Symposium on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 1994. 276280
4Baker M G et al. Measurements of a distributed file system. ACM Operating Systems Review, 1991,25(5):198212
5Blaze M A. Caching in large-scale distributed file systems Ph.D. Thesis. Department of Computer Science, Princeton University, 1993
1998-07-20յԭ,1998-09-07յ޸ĸ
