12. dfs

DISTRIBUTED FILE SYSTEMS,

1. Distributed Operating Systems
FILE SYSTEM
Sandeep Kumar Poonia
Head of Dept. CS/IT
B.E., M.Tech., UGC-NET
LM-IAENG, LM-IACSIT,LM-CSTA, LM-AIRCC, LM-SCIEI, AM-UACEE

2. 2
Introduction
Filesystemwereoriginallydevelopedfor
centralizedcomputersystemsanddesktop
computers.
Filesystemwasasanoperatingsystem
facilityprovidinga convenient
programminginterfacetodiskstorage.

3. 3
DISTRIBUTED FILE SYSTEMS
DEFINITIONS:
•ADistributedFileSystem(DFS)issimplyaclassicalmodelofa
filesystemdistributedacrossmultiplemachines.Thepurpose
istopromotesharingofdispersedfiles.
•Theresourcesonaparticularmachinearelocaltoitself.
Resourcesonothermachinesareremote.
•Afilesystemprovidesaserviceforclients.Theserverinterface
isthenormalsetoffileoperations:create,read,etc.onfiles.

4. 4
DISTRIBUTED FILE SYSTEMS
Clients,servers,andstoragearedispersedacrossmachines.
Configurationandimplementationmayvary–
a)Serversmayrunondedicatedmachines,OR
b)Serversandclientscanbeonthesamemachines.
c)TheOSitselfcanbedistributed(withthefilesystema
partofthatdistribution.
d)Adistributionlayercanbeinterposedbetweena
conventionalOSandthefilesystem.
ClientsshouldviewaDFSthesamewaytheywouldacentralized
FS;thedistributionishiddenatalowerlevel.
Performanceisconcernedwiththroughputandresponsetime.
Definitions

5. DISTRIBUTED FILE SYSTEMS
Distributed file system support:
•RemoteInformationSharing-Allowsafiletobe
transparentlyaccessedbyprocessesofanynodeofthesystem
irrespectiveofthefile’slocation
•User Mobility-User have flexibility to work on different node at
different time
•Availability-better fault tolerance
•Diskless Workstations
5

6. DISTRIBUTED FILE SYSTEMS
Distributed File System provide following type of
services:
•Storage Service
•True File Service
•Name Service
6

7. DISTRIBUTED FILE SYSTEMS
Desirablefeaturesofagooddistributedfilesystem
Transparency
Structuretransparency
AccessTransparency
NamingTransparency
ReplicationTransparency
UserMobility
Performance
Simplicityandeaseofuse
Scalability
HighAvailability
HighReliability
DataIntegrity
Security
Heterogeneity
7

8. File Models
Criteria: Structure and Modifiability
Structured and Unstructured Files
–Structured Files: A file appear to the file server as an
ordered sequence of records.
•Files with Indexed Records
•Files With non-indexed records
–Unstructured files: No substructure known to the
file server
8

9. File Models
Mutable and Immutable Files
•Mutable
–An update performed on a file overwrites on its old
contents
–A file is represented as a single stored sequence that is
altered by each update operation.
•Immutable Files
–A file cannot be modified once it has been created
–File versioning approach used to implement file
updates
–It support consistent sharing therefore it is easier to
support file caching and replication
9

10. File Accessing Models
FileAccessingModelsofDFSmainlydependson:Methodused
foraccessingremotefilesandtheunitofdataaccess
AccessingRemoteFiles
–RemoteServiceModel:
•Client’srequestprocessedatserver’snode
•InthiscasePackingandcommunicationoverheadcanbesignificant
–DataCachingModel:
•Client’srequestprocessedontheclient’snodeitselfbyusingthecacheddata.
•Thismodelgreatlyreducesnetworktraffic
•Cacheconsistencyproblemmayoccur
LOCUSandNFSusetheremoteservicemodelbutaddcaching
forbetterperformance
Spriteusedatacachingmodelbutemploystheremoteservice
modelundercertaincircumstances
10

11. File Accessing Models
Unit of Data Transfer
–File Level Transfer Model( Ex. Amoeba, AFS)
•The whole file is moved when an operation requires file data
•It is simple, It has better scalability
•Disk access routines on the servers can be better optimized
•But it requires sufficient storage space on client’s node
–Block Level Transfer Model( Ex. LOCUS, Sprite)
•Data transferred in units of file blocks
•It does not require client node to have large storage space
•It can be used in diskless workstations
•Network traffic may be significant
–Byte Level Transfer Model( Cambridge file server)
•Data transfers in units of bytes
•Low Storage requires but difficulty in cache management
–Record Level Transfer Model( Research Storage System)
•Suitable for Structured model
11

12. File Sharing Semantics
•A shared file may be simultaneously accessed
by multiple users.
•In such a situation it is required to decide,
how modification of file data made by user
are observable.
•Levy and Silberschatzdefined::
–Unix Semantic
–Session Semantic
–Immutable shared files semantics
–Transaction like semantic
12

13. Unix Semantics
13

14. Session Semantics
ItAssumethat:
•AClientopensafile,performsaseriesof
read/writeoperationonfileandfinallycloses
thefilewhenheorsheisdonewithfile.
•Asessionisaseriesoffileaccessesmade
betweenopenandcloseoperation.
•Herechangesmadetoafileduringasession
visibletoclientonly.
•Oncethefilecloseschangesvisibletoremote
processesonlyonthelaterstartingsessions.
14

15. Immutable shared files semantics
•Allows files to be shared only in the read only
mode.
15
Transaction like semantics
•Basedontransactionmechanism
•Itmakesurethatpartialmodificationsmade
toashareddatanotvisibletoothers
concurrentlyexecutingtransactionuntil
transactionends.

16. 16
DISTRIBUTED FILE SYSTEMS
Namingisthemappingbetweenlogicalandphysicalobjects.
–Example:Auserfilenamemapsto<cylinder,sector>.
–Inaconventionalfilesystem,it'sunderstoodwherethefileactuallyresides;the
systemanddiskareknown.
–InatransparentDFS,thelocationofafile,somewhereinthenetwork,ishidden.
–Filereplicationmeansmultiplecopiesofafile;mappingreturnsaSEToflocations
forthereplicas.
Locationtransparency-
a)Thenameofafiledoesnotrevealanyhintofthefile'sphysicalstoragelocation.
b)Filenamestilldenotesaspecific,althoughhidden,setofphysicaldiskblocks.
c)Thisisaconvenientwaytosharedata.
d)Canexposecorrespondencebetweencomponentunitsandmachines.
Naming and Transparency

17. 17
DISTRIBUTED FILE SYSTEMS
Locationindependence-
–Thenameofafiledoesn'tneedtobechangedwhenthefile'sphysicalstorage
locationchanges.Dynamic,one-to-manymapping.
–Betterfileabstraction.
–Promotessharingthestoragespaceitself.
–Separatesthenaminghierarchyfromthestoragedeviceshierarchy.
MostDFSstoday:
–Supportlocationtransparentsystems.
–DoNOTsupportmigration;(automaticmovementofafilefrommachineto
machine.)
–Filesarepermanentlyassociatedwithspecificdiskblocks.
Naming and Transparency

18. 18
DISTRIBUTED FILE SYSTEMS
TheANDREWDFSASANEXAMPLE:
–Islocationindependent.
–Supportsfilemobility.
–SeparationofFSandOSallowsfordisk-lesssystems.Thesehavelowercostand
convenientsystemupgrades.Theperformanceisnotasgood.
NAMINGSCHEMES:
Therearethreemainapproachestonamingfiles:
1.Filesarenamedwithacombinationofhostandlocalname.
–Thisguaranteesauniquename.NEITHERlocationtransparentNORlocation
independent.
–Samenamingworksonlocalandremotefiles.TheDFSisaloosecollectionof
independentfilesystems.
Naming and Transparency

19. 19
DISTRIBUTED FILE SYSTEMS
NAMINGSCHEMES:
2.Remotedirectoriesaremountedtolocaldirectories.
–Soalocalsystemseemstohaveacoherentdirectorystructure.
–Theremotedirectoriesmustbeexplicitlymounted.Thefilesarelocation
independent.
–SUNNFSisagoodexampleofthistechnique.
3.Asingleglobalnamestructurespansallthefilesinthesystem.
–TheDFSisbuiltthesamewayasalocalfilesystem.Locationindependent.
Naming and Transparency

20. 20
MountingRemote Directories (NFS)

21. 21
DISTRIBUTED FILE SYSTEMS
IMPLEMENTATIONTECHNIQUES:
–CanMapdirectoriesorlargeraggregatesratherthanindividualfiles.
–Anon-transparentmappingtechnique:
name----><system,disk,cylinder,sector>
–Atransparentmappingtechnique:
name---->file_identifier----><system,disk,cylinder,sector>
–Sowhenchangingthephysicallocationofafile,onlythefileidentifier
needbemodified.Thisidentifiermustbe"unique"intheuniverse.
Naming and Transparency

22. 22
DISTRIBUTED FILE SYSTEMS
CACHING
•Reducenetworktrafficbyretainingrecentlyaccesseddiskblocksinacache,sothat
repeatedaccessestothesameinformationcanbehandledlocally.
•Ifrequireddataisnotalreadycached,acopyofdataisbroughtfromtheservertothe
user.
•Performaccessesonthecachedcopy.
•Filesareidentifiedwithonemastercopyresidingattheservermachine,
•Copiesof(partsof)thefilearescatteredindifferentcaches.
•CacheConsistencyProblem--Keepingthecachedcopiesconsistentwiththemaster
file.
•Aremoteservice((RPC)hasthesecharacteristicsteps:
a)Theclientmakesarequestforfileaccess.
b)Therequestispassedtotheserverinmessageformat.
c)Theservermakesthefileaccess.
d)Returnmessagesbringtheresultbacktotheclient.
Thisisequivalenttoperformingadiskaccessforeachrequest.

23. 23
DISTRIBUTED FILE SYSTEMS
CACHELOCATION:
•Cachingisamechanismformaintainingdiskdataonthelocalmachine.Thisdatacan
bekeptinthelocalmemoryorinthelocaldisk.Cachingcanbeadvantageousbothfor
readaheadandreadagain.
•ThecostofgettingdatafromacacheisafewHUNDREDinstructions;diskaccesses
costTHOUSANDSofinstructions.
•Themastercopyofafiledoesn'tmove,butcachescontainreplicasofportionsofthe
file.
•Cachingbehavesjustlike"networkedvirtualmemory".
•Whatshouldbecached?<<blocks<--->files>>.Biggersizesgiveabetterhitrate;
smallergivebettertransfertimes.
•Cachingondiskgives:
—Betterreliability.
•Cachinginmemorygives:
—Thepossibilityofdisklessworkstations,
—Greaterspeed,
•Sincetheservercacheisinmemory,itallowstheuseofonlyonemechanism.

24. CACHE LOCATION
24

25. CACHE LOCATION: Relative Advantages
25

26. 26
DISTRIBUTED FILE SYSTEMS CACHE UPDATE POLICY:
Awritethroughcache
•Whenacacheentryismodified,thenewvalueisimmediatelysettoserver
forupdatingmastercopyoffile
•Ithasgoodreliability.Buttheusermustwaitforwritestogettotheserver.
UsedbyNFS.
Delayedwrite
•Modifiedvaluewrittenonlytothecacheandclientmakeanote
•Allupdategatheredandsenttoserveratatime
–Writeonejectionfromcache
–Periodicwrite
–Writeonclose
•writerequestscompletemorerapidly.Datamaybewrittenovertheprevious
cachewrite,savingaremotewrite.Poorreliabilityonacrash.

27. 27
DISTRIBUTED FILE SYSTEMS
CACHECONSISTENCY:
Thebasicissueis,howtodeterminethattheclient-cacheddataisconsistentwithwhat's
ontheserver.
•Client-initiatedapproach-
TheclientaskstheserverifthecacheddataisOK.Whatshouldbethefrequencyof
"asking"?Beforeeveryaccess,Onfileopen,atfixedtimeinterval,...?
•Server-initiatedapproach-
Possibilities:AandBbothhavethesamefileopen.WhenAclosesthefile,B
"discards"itscopy.ThenBmuststartover.
Theserverisnotifiedoneveryopen.Ifafileisopenedforwriting,thendisable
cachingbyotherclientsforthatfile.
Getread/writepermissionforeachblock;thendisablecachingonlyforparticular
blocks.

28. 28
DISTRIBUTED FILE SYSTEMS
COMPARISONOFCACHINGANDREMOTESERVICE:
•Manyremoteaccessescanbehandledbyalocalcache.There'sagreatdealoflocalityof
referenceinfileaccesses.Serverscanbeaccessedonlyoccasionallyratherthanforeachaccess.
•Cachingcausesdatatobemovedinafewbigchunksratherthaninmanysmallerpieces;this
leadstoconsiderableefficiencyforthenetwork.
•Diskaccessescanbebetteroptimizedontheserverifit'sunderstoodthatrequestsarealwaysfor
largecontiguouschunks.
•Cacheconsistencyisthemajorproblemwithcaching.Whenthereareinfrequentwrites,caching
isawin.Inenvironmentswithmanywrites,theworkrequiredtomaintainconsistency
overwhelmscachingadvantages.
•Cachingworksbestonmachineswithconsiderablelocalstore-eitherlocaldisksorlarge
memories.Withneitherofthese,useremote-service.
•Cachingrequiresawholeseparatemechanismtosupportacquiringandstorageoflargeamounts
ofdata.Remoteservicemerelydoeswhat'srequiredforeachcall.Assuch,cachingintroducesan
extralayerandmechanismandismorecomplicatedthanremoteservice.

29. 29
DISTRIBUTED FILE SYSTEMS
STATEFULVS.STATELESSSERVICE:
Stateful:Aserverkeepstrackofinformationaboutclientrequests.
–Itmaintainswhatfilesareopenedbyaclient;connectionidentifiers;servercaches.
–Memorymustbereclaimedwhenclientclosesfileorwhenclientdies.
Stateless:Eachclientrequestprovidescompleteinformationneededbytheserver(i.e.,filename,
fileoffset).
–Theservercanmaintaininformationonbehalfoftheclient,butit'snotrequired.
–UsefulthingstokeepincludefileinfoforthelastNfilestouched.

30. 30
DISTRIBUTED FILE SYSTEMS
STATEFULVS.STATELESSSERVICE:
Performanceisbetterforstateful.
–Don'tneedtoparsethefilenameeachtime,or"open/close"fileoneveryrequest.
–Statefulcanhavearead-aheadcache.
FaultTolerance:Astatefulserverloseseverythingwhenitcrashes.
–Servermustpollclientsinordertorenewitsstate.
–Clientcrashesforcetheservertocleanupitsencachedinformation.
–Statelessremembersnothingsoitcanstarteasilyafteracrash.

31. 31
FILE REPLICATION:
•Duplicatingfilesonmultiplemachinesimprovesavailabilityandperformance.
•Placedonfailure-independentmachines(theywon'tfailtogether).
Replicationmanagementshouldbe"location-opaque".
•Themainproblemisconsistency-whenonecopychanges,howdoothercopies
reflectthatchange?Oftenthereisatradeoff:consistencyversusavailabilityand
performance.
•Example:
"Demandreplication"islikewhole-filecaching;readingafilecausesittobe
cachedlocally.Updatesaredoneonlyontheprimaryfileatwhichtimeallother
copiesareinvalidated.
•Atomicandserializedinvalidationisn'tguaranteed(messagecouldgetlost/machine
couldcrash.)

32. Difference between Replication and Caching
•Replicaassociatedwithserverwhereas
Cachedcopywithaclient
•Existenceofreplicadependsonavailability
andperformancerequirementswhereas
cachedcopydependentonlocalityinfile
accesspattern.
•Replicaismorepersistent,widelyknown,
secure,available,completeandaccurate.
32

33. Advantages of Replication
•Increased availability
•Increased Reliability
•Improved Response time
•Reduces network traffic
•Improved system throughput
•Better scalability
•Autonomous operation
33

34. Replication Transparency
•Naming of Replicas
–A single identifier to all replicas of an object
•Replication Control
–Determining number and locations of replicas
34

35. Multicopy Update Problem
•Read-Only Replication
–Allows the replication of only immutable files
•Read-Any-Write-All Protocol
–Read any copy of file and write to all copies of file
•Available copy Protocol
–When a server recover after failure, it bring itself up to date by
copying from other server before accepting any user request
•Primary-Copy Protocol
–Read operation can be performed from any copy but write
operations directly performed only on primary copy
35

36. Multicopy Update Problem…..
•Quorum-Based Protocols
–Let there are n copies of replicated file F.
–To read , minimum r copies of F have to be
consulted.(r-Read Quorum)
–For a write operation minimum w Copies of F.(w-
write quorum)
–The choice of r and w is that r+w > n
36

37. 37
OVERVIEW:
•RunsonSUNOS-NFSisbothanimplementationandaspecificationofhowtoaccessremote
files.It'sbothadefinitionandaspecificinstance.
•Thegoal:toshareafilesysteminatransparentway.
•Usesclient-servermodel(forNFS,anodecanbebothsimultaneously.)Canactbetweenanytwo
nodes(nodedicatedserver.)Mountmakesaserverfile-systemvisiblefromaclient.
mountserver:/usr/sharedclient:/usr/local
•Then,transparently,arequestfor/usr/local/dir-serveraccessesafilethatisontheserver.
•Themountiscontrolledby:(1)accessrights,(2)serverspecificationofwhat'smountable.
•Canuseheterogeneousmachines-differenthardware,operatingsystems,networkprotocols.
•UsesRPCforisolation-thusallimplementationsmusthavethesameRPCcalls.TheseRPC's
implementthemountprotocolandtheNFSprotocol.
DISTRIBUTED FILE SYSTEMS
SUN Network File System

38. 38
THEMOUNTPROTOCOL:
Thefollowingoperationsoccur:
1.Theclient'srequestissentviaRPCtothemountserver(onservermachine.)
2.Mountserverchecksexportlistcontaining
a)filesystemsthatcanbeexported,
b)legalrequestingclients.
c)It'slegitimatetomountanydirectorywithinthelegalfilesystem.
3.Serverreturns"filehandle"toclient.
4.Servermaintainslistofclientsandmounteddirectories--thisisstateinformation!Butthis
dataisonlya"hint"andisn'ttreatedasessential.
5.Mountingoftenoccursautomaticallywhenclientorserverboots.
DISTRIBUTED FILE SYSTEMS
SUN Network File System

39. 39
THENFSPROTOCOL:
RPC’ssupporttheseremotefileoperations:
a)Searchforfilewithindirectory.
b)Readasetofdirectoryentries.
c)Manipulatelinksanddirectories.
d)Read/writefileattributes.
e)Read/writefiledata.
Note:
–Openandcloseareconspicuouslyabsentfromthislist.NFSserversarestateless.Each
requestmustprovideallinformation.Withaservercrash,noinformationislost.
–Modifieddatamustactuallygettoserverdiskbeforeclientisinformedtheactioniscomplete.
Usingacachewouldimplystateinformation.
–AsingleNFSwriteisatomic.AclientwriterequestmaybebrokenintoseveralatomicRPC
calls,sothewholethingisNOTatomic.Sincelockmanagementisstateful,NFSdoesn'tdoit.A
higherlevelmustprovidethisservice.
DISTRIBUTED FILE SYSTEMS
SUN Network File System

40. 40
NFSARCHITECTURE:
Followlocalandremoteaccessthroughthisfigure:
DISTRIBUTED FILE SYSTEMS
SUN Network File System

41. 41
NFSARCHITECTURE:
1.UNIXfilesystemlayer-doesnormalopen/read/etc.commands.
2.Virtualfilesystem(VFS)layer-
a)Givescleanlayerbetweenuserandfilesystem.
b)Actsasdeflectionpointbyusingglobalvnodes.
c)Understandsthedifferencebetweenlocalandremotenames.
d)Keepsinmemoryinformationaboutwhatshouldbedeflected(mounteddirectories)and
howtogettotheseremotedirectories.
3.Systemcallinterfacelayer-
a)PresentssanitizedvalidatedrequestsinauniformwaytotheVFS.
DISTRIBUTED FILE SYSTEMS
SUN Network File System

42. 42
PATH-NAMETRANSLATION:
•Breakthecompletepathnameintocomponents.
•Foreachcomponent,doanNFSlookupusingthe
componentname+directoryvnode.
•Afteramountpointisreached,eachcomponentpiecewillcauseaserveraccess.
•Can'thandthewholeoperationtoserversincetheclientmayhaveasecondmountona
subsidiarydirectory(amountonamount).
•Adirectorynamecacheontheclientspeedsuplookups.
DISTRIBUTED FILE SYSTEMS
SUN Network File System

43. 43
CACHESOFREMOTEDATA:
•Theclientkeeps:
Fileblockcache-(thecontentsofafile)
Fileattributecache-(fileheaderinfo(inodeinUNIX)).
•Thelocalkernelhangsontothedataaftergettingitthefirsttime.
•Onanopen,localkernel,itcheckswithserverthatcacheddataisstillOK.
•Cachedattributesarethrownawayafterafewseconds.
•Datablocksusereadaheadanddelayedwrite.
•Mechanismhas:
Serverconsistencyproblems.
Goodperformance.
DISTRIBUTED FILE SYSTEMS
SUN Network File System

44. 44
AdistributedenvironmentatCMU.Strongestcharacteristicisscalability.
OVERVIEW:
•Machinesareeitherserversorclients.
•Clientsseealocalnamespaceandasharednamespace.
•Servers
runvicewhichpresentsahomogeneous,locationtransparentdirectorystructuretoallclients.
•Clients(workstations):
Runvirtueprotocoltocommunicatewithvice.
Havelocaldisks(1)forlocalnamespace,(2)tocacheshareddata.
•Forscalability,offloadworkfromserverstoclients.Useswholefilecaching.
•NOclientsortheirprogramsareconsideredtrustworthy.
DISTRIBUTED FILE SYSTEMS
Andrew File System

45. 45
SHAREDNAMESPACE:
•Theserverfilespaceisdividedintovolumes.Volumescontainfilesofonlyoneuser.It'sthese
volumesthatarethelevelofgranularityattachedtoaclient.
•Avicefilecanbeaccessedusingafid=<volumenumber,vnode>.Thefiddoesn'tdependon
machinelocation.Aclientqueriesavolume-locationdatabaseforthisinformation.
•Volumescanmigratebetweenserverstobalancespaceandutilization.Oldserverhas
"forwarding"instructionsandhandlesclientupdatesduringmigration.
•Read-onlyvolumes(systemfiles,etc.)canbereplicated.Thevolumedatabaseknowshowtofind
these.
DISTRIBUTED FILE SYSTEMS
Andrew File System

46. 46
FILEOPERATIONSANDCONSISTENCYSEMANTICS:
•Ifafileisremote,theclientoperatingsystempassescontroltoaclientuser-levelprocessnamed
Venus.
•TheclienttalkstoViceserveronlyduringopen/close;reading/writingareonlytothelocalcopy.
•Afurtheroptimization-ifdataislocallycached,it'sassumedtobegooduntiltheclientistold
otherwise.
•Aclientissaidtohaveacallbackonafile.
•Whenaclientencachesafile,theservermaintainsstateforthisfact.
•Beforeallowingawritetoafile,theserverdoesacallbacktoanyoneelsehavingthisfileopen;all
othercachedcopiesareinvalidated.
•Whenaclientisrebooted,allcacheddataissuspect.
•Iftoomuchstorageusedbyserverforcallbackstate,theservercanbreaksomecallbacks.
•Thesystemclearlyhasconsistencyconcerns.
DISTRIBUTED FILE SYSTEMS
Andrew File System

47. 47
IMPLEMENTATION:
• Deflectionofopen/close:
• Theclientkernelismodifiedtodetectreferencestovicefiles.
• TherequestisforwardedtoVenuswiththesesteps:
• Venusdoespathnametranslation.
• AsksViceforthefile
• Movesthefiletolocaldisk
• Passesinodeoffilebacktoclientkernel.
• Venusmaintainscachesforstatus(inmemory)anddata(onlocaldisk.)
• Aserveruser-levelprocesshandlesclientrequests.
• AlightweightprocesshandlesconcurrentRPCrequestsfromclients.
• Stateinformationiscachedinthisprocess.
• Susceptibletoreliabilityproblems.
DISTRIBUTED FILE SYSTEMS
Andrew File System

48. 48
Inthissectionwehavelookedathowfilessystemsareimplementedacrosssystems.Of
specialconcernisconsistency,caching,andperformance.
DISTRIBUTED FILE SYSTEMS
Wrap Up