基于网络编码的分布式文件系统设计与实现

中国科学技术大学硕士学位论文基于网络编码的分布式文件系统设计与实现姓名：常乾申请学位级别：硕士专业：计算机软件与理论指导教师：许胤龙20100425IAbstractIIAbstractAselectronicandinformationtechnologydevelops,newinformationisproducedandprocessedinanunprecedentedspeed,alongwiththatthenetworkpropagateinformationevenfaster.Thisshapesanurgentstoragedemandforhugeamountofinformation.Howeverlocalinformationstorageimposesseverallimitationsonfunctionsandperformance,suchaslowreliability,poormobilityandinconvenienceforfilesharing.Sopeoplebegintomovetheirfocustonewsolutionlikenetworkstorage.Distributedfilesystemisabasicingredientofnetworkstorage,anditsresearchhasbeenemphasizedbyresearchcommunityandindustry.Distributedfilesystemsshouldusuallyprovidedatastoragewithhighreliabilityandgoodscalability,whichisachievedbyspecificdesignofdataplacementmethodsinthesystems'storagelevel.Someexistingmechanismsincludereplicationanderasurecoding,eachofwhichhasitsspecialobjectiveandlimitation.Researchinthisthesisisbyusingnetworkcodingtodividefileintosegmentsfirstandchunksfurtherandencodethemtobestoredinthedistributedenvironment.Andnetworkcodingsolutionstodesignandimplementationarealsoshowninthisthesis.Thedistributedfilesysteminthethesisprovidesauniformnamespaceandconformstolocationindependenceandtransparency.Italsosupportsbasicfileanddirectoryoperationsandkeepstheinternalimplementationtransparenttousers.Thesystemadoptsacentralizedarchitecture,whichiscomprisedbyanindexserver,storagenodesandclients.Theindexservermaintainsloadbalanceofthewholesystemthroughnetworkcodingmechanismsandrepairsfailednodewhenitisfound.Whenanewnodejoinsin,theindexserverwillissueare-balanceprocesstoprovidethesystemwithgoodscalability.Thisthesisfirstlysummarizescurrentresearchstatusofdistributedfilesystemanditssystemfunctionsandclassification.Afteranintroductiontocommonlyuseddataplacementandredundancystrategy,thenetworkcodingsolutiontodataplacementisshown.Laterdesignandimplementationdetailsandsolutionstoloadbalanceandnoderecoveryarediscussed.Andtheexperimentdesignandperformanceevaluationresultsaregivenlastly.KeyWords:distributedfilesystem,networkcoding,loadbalance,noderecovery,__________________________________________________________________________________________1111.1RAM(Caching)RAID(Pattersonetal,1988)(Internet)RAIDSAN(Silberschatzetal,2002)12ReedSolomon(MacWilliamsandSloane,1977)(Ahlswedeetal,2000)Galois1.21976DECFAL(FileAccessListener)SunNFS(Sandbergetal,1985)IPCarnegieMellonAFSCodaGoogle13GFS(GoogleFileSystem)(Ghemawatetal,2003)1.2.1NFSNFS(NetworkFileSystem)Sun1980SunNFSNFSSunNFSSunOSUnixUnixNFSNFSC/SNFSNFSUnix(mount)NFSmountNFS(stateless)NFSNFSNFS1.2.2AFSAFS(AndrewFileSytem)CarnegieMellon1983(Morrisetal,1986)TransarcAFSIBMIBM2000IBMPublicLicenseAFSAFSNFSCacheCacheKerberosAFSCacheAFSAFS(volume)14AFSAFSAFSUnix12F1F2F11AFS(callback)AFS1.2.3CodaCoda(Satyanarayanan,1990)AFSCarnegieMellon(Satyanarayananetal,1990)Coda(disconnectedoperation)CodaCoda(volume)(VolumeStorageGroup,VSG)VSGAVSGAFSAVSGVSGAVSGCodaCodaCoda15CodaCoda1.3(1)(2)(3)(4)(5)1.4162722.12.1.1(LevyandSilberschatz,1990)1.2.IPUnixmount/usrUnix282.1.2UnixUnix1)2)UnixUnixUnix1)2)2.1.3(LevyandSilberschatz,1990)openclose292.22.2.1(a)(b)(c)/(d)(e)(federation)(f)PASTCFSPOSIXAPI(re-build)POSIXNFSCodaxFS/(i)(ii)P2PFreeHavenFreenetPubliusNapster(Oram,2001)GnutellaMojoNationBit-Torrent210I/OGBPPFSZebraPVFSLustreGPFSFrangipaniPIOUSGalleyInternetGoogleGoogleFileSystemUCBerkeyOceanStoreGoogleGFSOceanStoreOceanStoreP2P(Kubiatowiczetal,2000)2.2.2-(client/server,C/S)P2PC/SP2PP2PC/SC/SC/S211POSIXI/OP2PP2PP2PNapster(Oram,2001)(SinglePointofFailure)P2PP2PP2PGnutellaFastTrackClippeeBit-TorrentP2PP2PInternetP2PP2PFreeHavenFreenetIvyP2PP2P2.2.3212POSIX()InternetP2P2.2.42.2.4.1NobleSatyananrayanan(1994)CodaBolosky(2000)85%95%CPU18%70%Farsite(Adyaetal,2002)2.2.4.2P2PP2P213Bit-Torrent(Cohen,2003)2.2.4.3CPU2.2.5ACID(HaerderandReuter,1983)ACID1.(Atomic)(Rollback)2.(Consistency)3.(Isolation)4.(Durability)ACID()ACID214C/SP2PxFSCodaIvyIvyCoda(AccessControlList,ACL)()ACLP2PhashSHA(NIST,1995)MD5(Rivest,1992)hashhashByzantine(agreementprotocol)2152.2.6OverlayC/SP2PNapsterP2PP2PP2PGnutellaP2P(Oram,2001)P2PTTL(TimeToLive)TTLP2POverlayDHT(DistributedHashTable)(Plaxtonetal,1997)peerpeerIDIDIPIDDHTOverlay2.321631733.11~128Linuxext2RAID-0RAID(Pattersonetal,1988)RAIDRAIDRAID-0RAID-6RAID-0(striping)()3.13183.1RAID-0RAIDRAID-0RAID64KB128KBI/ORAID-0RAID-03.2(replication)RAIDRAID-13.2510%RAID-03195%101.0)1.0()Pr()Pr(22====RAID-0I/O3.2RAID-1RAID-1RAID-1I/OJimGrayetal(1996)n3.3RAIDRAID-5RAID-6RAID-5RAID-6320EVENODD(Blaum,1995)EVENODD)2()1(+×−pp2+p2+pp3=p3.3RAID-5SSddcSddcddSdddcdddc++=++=+=++=++=3246135464225311+3.3EVENODDEVENODD][654321ddddddD=][4321654321ccccddddddC=GDC⋅==011010000011010100001110001000100100010010100000100101000001GG(generatormatrix)EVENODDI(MacWilliamnsandSloane,1977)EVENODDRAID-6i)XOR)2(GFii)I(systematic)RAIDI/Oiii)3212RAID(erasurecode)nmn+n1)/(+=mnnrEVENODD)2/(+pppRAID-12/1GaloisXORReedSolomon(MacWilliamsandSloane,1977)GaloisReedSolomonVandermonde=−−−1212121333