分布式系統(tǒng)課件：chapter10

1、Distributed File SystemsChapter 10Introduction基本概念基本概念： (1) File 被命名的信息集合; (2) File System負(fù)責(zé)存儲(chǔ)和管理文件的軟件系統(tǒng); (3) 文件系統(tǒng)的分層結(jié)構(gòu)：目錄、文件操作、文件存儲(chǔ)、設(shè)備; (4) 文件操作接口及其實(shí)現(xiàn);文件類型舉例1、可執(zhí)行文件2、歸檔文件不可變的（immutable） a.可執(zhí)行文件;b.歸檔文件: 不可變的immutable 典型的文件擴(kuò)展名文件的屬性文件基本操作1. Create2. Delete3. Open4. Close5. Read6. Write7. Append8. Seek

2、9. Get attributes10.Set Attributes11.Rename文件操作舉例文件操作舉例IntroductionWhat is Distributed File System?Distributed file systems support the sharing of information in the form of files throughout the intranet.A distributed file system enables programs to store and access remote files exactly as they do o

3、n local ones, allowing users to access files from any computer on the intranet.IntroductionTwo distinct concepts:File service: The interface to file system functionality (primitives, parameters, semantics).True file service: operations on filesDirectory service: operations on directories (or metafil

4、es).File server: An implementation of this interface.file servers may be local or remote.file servers may be replicated.IntroductionDFSDFS的透明性的透明性: :u 存取透明性（本地與遠(yuǎn)程存取透明性（本地與遠(yuǎn)程-通信問(wèn)題）；通信問(wèn)題）；u 位置透明性（命名問(wèn)題）；位置透明性（命名問(wèn)題）；u 并發(fā)存取透明性（同步問(wèn)題）；并發(fā)存取透明性（同步問(wèn)題）；u 性能透明性（緩存性能透明性（緩存/ /復(fù)制及一致性問(wèn)題）；復(fù)制及一致性問(wèn)題）；u 故障透明性（容錯(cuò)問(wèn)題）；故障透

5、明性（容錯(cuò)問(wèn)題）；u 其它其它: : 擴(kuò)展、復(fù)制、遷移透明性等。擴(kuò)展、復(fù)制、遷移透明性等。Distributed File System設(shè)計(jì)目標(biāo)設(shè)計(jì)目標(biāo) 不同的不同的DFSDFS根據(jù)其各自的設(shè)計(jì)目標(biāo)其根據(jù)其各自的設(shè)計(jì)目標(biāo)其實(shí)現(xiàn)策略不同，如：訪問(wèn)透明、高可用、實(shí)現(xiàn)策略不同，如：訪問(wèn)透明、高可用、對(duì)等、資源訪問(wèn)統(tǒng)一以及高安全性等。對(duì)等、資源訪問(wèn)統(tǒng)一以及高安全性等。Two main access models for distributed file services:1. Remote Access Model: File system runs on servers and fine grain

6、ed access is allowed.File system is truly remote.Little space is needed in the clientRemote Access Model2. Upload/Download model: The entire file is transferred from server to client and vice versa. That is, only whole files are moved.Simple.Whole file transfer is efficient.More storage needed in th

7、e client, transferring entire file may be wasteful or impossible.Remote Access ModeluThe remote accesses modeluThe upload/download model(如FTP)Remote Access ModelNFS Architecture NFS（Network File System）是由SUN公司最早開(kāi)發(fā)的, 運(yùn)行在SUN UNIX上的系統(tǒng)。 從誕生到現(xiàn)在為止，已經(jīng)有多個(gè)版本，如NFS V2（rfc1094），NFS V3（rfc1813）,最新的版本是V4（rfc3010）

8、, 主要支持在Internet上的有效運(yùn)行。NFS ArchitectureThe basic NFS architecture for UNIX systems.由安裝點(diǎn)識(shí)別File System ModelAn incomplete list of file system operations supported by NFS.Operationv3v4DescriptionCreateYesNoCreate a regular fileCreateNoYesCreate a nonregular file(4-6)LinkYesYesCreate a hard link to a fil

9、eSymlinkYesNoCreate a symbolic link to a fileMkdirYesNoCreate a subdirectory in a given directoryMknodYesNoCreate a special fileRenameYesYesChange the name of a fileRmdirYesNoRemove an empty subdirectory from a directoryOpenNoYesOpen a file (v3: Lookup/read-write, or create )CloseNoYesClose a fileLo

10、okupYesYesLook up a file by means of a file nameReaddirYesYesRead the entries in a directoryReadlinkYesYesRead the path name stored in a symbolic linkGetattrYesYesRead the attribute values for a fileSetattrYesYesSet one or more attribute values for a fileReadYesYesRead the data contained in a fileWr

11、iteYesYesWrite data to a fileCluster-Based Distributed File Systems (1) The difference between (a) distributing whole files across several servers and (b) striping files for parallel access.Cluster-Based Distributed File Systems (2)GFS (Google File System)將整個(gè)系統(tǒng)的節(jié)點(diǎn)分為三類角色：Client（客戶端）、Master（主服務(wù)器）和Chun

12、k Server（數(shù)據(jù)塊服務(wù)器）；Client是GFS提供給應(yīng)用程序的訪問(wèn)接口，它是一組專用接口，不遵守POSIX規(guī)范，以庫(kù)文件的形式提供；Master是GFS的管理節(jié)點(diǎn)，在邏輯上只有一個(gè)，它保存系統(tǒng)的元數(shù)據(jù)，負(fù)責(zé)整個(gè)文件系統(tǒng)的管理，是GFS文件系統(tǒng)中的“大腦”；Chunk Server負(fù)責(zé)具體的存儲(chǔ)工作。數(shù)據(jù)以文件的形式存儲(chǔ)在Chunk Server上，Chunk Server的個(gè)數(shù)可以有多個(gè)，它的數(shù)目直接決定了GFS的規(guī)模。GFS將文件按照固定大小進(jìn)行分塊，默認(rèn)是64MB，每一塊稱為一個(gè)Chunk（數(shù)據(jù)塊），每個(gè)Chunk都有一個(gè)對(duì)應(yīng)的索引號(hào)（Index）；Cluster-Based Di

13、stributed File Systems (3)The organization of a Google cluster of servers.Master維護(hù)了一個(gè)名空間、訪問(wèn)控制信息和文件到塊的映射信息，以及塊當(dāng)前所在的位置。GFS的特點(diǎn):1采用中心服務(wù)器模式采用中心服務(wù)器模式 GFS采用中心服務(wù)器模式來(lái)管理整個(gè)文件系統(tǒng)，可以大大簡(jiǎn)化設(shè)計(jì)，從而降低實(shí)現(xiàn)難度。Master管理了分布式文件系統(tǒng)中的所有元數(shù)據(jù)。文件劃分為Chunk進(jìn)行存儲(chǔ)，對(duì)于Master來(lái)說(shuō)，每個(gè)Chunk Server只是一個(gè)存儲(chǔ)空間。2不緩存數(shù)據(jù)不緩存數(shù)據(jù) 根據(jù)應(yīng)用的特點(diǎn)，沒(méi)有實(shí)現(xiàn)緩存: 客戶端大部分是流式順序讀寫，并

14、不存在大量的重復(fù)讀寫; 從可行性上講，如何維護(hù)緩存與實(shí)際數(shù)據(jù)之間的一致性是一個(gè)極其復(fù)雜的問(wèn)題。3在用戶態(tài)下實(shí)現(xiàn)在用戶態(tài)下實(shí)現(xiàn) 直接利用操作系統(tǒng)提供的POSIX編程接口就可以存取數(shù)據(jù)，無(wú)需了解操作系統(tǒng)的內(nèi)部實(shí)現(xiàn)機(jī)制和接口，從而降低了實(shí)現(xiàn)的難度，并提高了通用性。Master和Chunk Server都以進(jìn)程的方式運(yùn)行，單個(gè)進(jìn)程不會(huì)影響到整個(gè)操作系統(tǒng)，從而可以對(duì)其進(jìn)行充分優(yōu)化4只提供專用接口只提供專用接口 GFS是在應(yīng)用層實(shí)現(xiàn)，專用接口直接和Client、Master、Chunk Server交互，減少了操作系統(tǒng)之間上下文的切換，降低了復(fù)雜度，提高了效率。Cluster-Based Distribu

15、ted File Systems (3)GFS的容錯(cuò)機(jī)制容錯(cuò)機(jī)制 1Master容錯(cuò)容錯(cuò) Master上保存了三種元數(shù)據(jù)：1）命名空間（Name Space）； 2）Chunk與文件名的映射表；3）Chunk副本的位置信息； 對(duì)于前兩種元數(shù)據(jù)，GFS通過(guò)操作日志來(lái)提供容錯(cuò)功能。第三種元數(shù)據(jù)信息則直接保存在各個(gè)Chunk Server上，當(dāng)Master啟動(dòng)或Chunk Server向Master注冊(cè)時(shí)自動(dòng)生成。因此當(dāng)Master發(fā)生故障時(shí)，在磁盤數(shù)據(jù)保存完好的情況下，可以迅速恢復(fù)以上元數(shù)據(jù)。2Chunk Server容錯(cuò)容錯(cuò) 采用副本的方式實(shí)現(xiàn)Chunk Server的容錯(cuò)。每一個(gè)Chunk有多

16、個(gè)存儲(chǔ)副本（默認(rèn)為三個(gè)），分布存儲(chǔ)在不同的Chunk Server上。 Chunk Server存儲(chǔ)的是Chunk的副本，副本以文件的形式進(jìn)行存儲(chǔ)。每一個(gè)Chunk以Block為單位進(jìn)行劃分，大小為64KB，每一個(gè)Block對(duì)應(yīng)一個(gè)32bit的校驗(yàn)和。當(dāng)讀取一個(gè)Chunk副本時(shí)，Chunk Server會(huì)將讀取的數(shù)據(jù)和校驗(yàn)和進(jìn)行比較，如果不匹配，就會(huì)返回錯(cuò)誤，從而使Client選擇其他Chunk Server上的副本。 Cluster-Based Distributed File Systems (4)Symmetric ArchitecturesThe organization of the

17、 Ivy distributed file system.DHT (Distributed Hash Table)，見(jiàn)命名系統(tǒng)一章 Processes有存儲(chǔ)服務(wù)器和文件管理器等多個(gè)協(xié)作進(jìn)程有存儲(chǔ)服務(wù)器和文件管理器等多個(gè)協(xié)作進(jìn)程. .1. 1. 無(wú)狀態(tài)服務(wù)無(wú)狀態(tài)服務(wù)(Stateless)(Stateless) Server Server在為在為ClientClient的請(qǐng)求進(jìn)行服務(wù)時(shí)的請(qǐng)求進(jìn)行服務(wù)時(shí), ,不保存該不保存該ClientClient的任何信息（的任何信息（WebWeb等）等）. .2. 2. 有狀態(tài)服務(wù)有狀態(tài)服務(wù)(Stateful)(Stateful) ServerServer在為在

18、為ClientClient的請(qǐng)求進(jìn)行服務(wù)時(shí)的請(qǐng)求進(jìn)行服務(wù)時(shí), ,保存該保存該ClientClient的有關(guān)信息的有關(guān)信息. . 無(wú)狀態(tài)無(wú)狀態(tài)服務(wù)器 當(dāng)客戶發(fā)送一個(gè)請(qǐng)求給服務(wù)器，服務(wù)器完成請(qǐng)求，發(fā)送一個(gè)應(yīng)答，然后從內(nèi)部表中移出關(guān)于該請(qǐng)求的所有信息。在請(qǐng)求之間，服務(wù)器不保存具體客戶的信息； 請(qǐng)求必須是獨(dú)立的，為了使服務(wù)器能夠工作，它必須包含全文件名和文件中的偏移量； 不需要OPEN和CLOSE調(diào)用； 有狀態(tài)有狀態(tài)服務(wù)器 服務(wù)器保存兩個(gè)請(qǐng)求之間的客戶的狀態(tài)信息； 可以預(yù)讀； ProcessesCommunication常用的3種：NFS RPC；RPC2；面向文件的通信；Remote Procedu

19、re Calls in NFS(a)Reading data from a file in NFS version 3.(b)Reading data using a compound procedure in version 4.The RPC2 Subsystem (1)RPC2RPC2是對(duì)是對(duì)RPCRPC功能的增強(qiáng)：功能的增強(qiáng)：n 在在UDPUDP協(xié)議上提供可靠的協(xié)議上提供可靠的RPCRPC：首先啟動(dòng)一個(gè)新線程，：首先啟動(dòng)一個(gè)新線程，向向SERVERSERVER發(fā)請(qǐng)求，隨后阻塞，直到接收到發(fā)請(qǐng)求，隨后阻塞，直到接收到SERVERSERVER的的響應(yīng)。響應(yīng)。n SIDE EFFECTSID

20、E EFFECT：ClientClient和和ServerServer可以針對(duì)應(yīng)用程序的可以針對(duì)應(yīng)用程序的協(xié)議進(jìn)行通信的機(jī)制。例如：允許雙方建立單獨(dú)的協(xié)議進(jìn)行通信的機(jī)制。例如：允許雙方建立單獨(dú)的連接連接, ,實(shí)現(xiàn)在規(guī)定的延時(shí)內(nèi)將視頻數(shù)據(jù)傳給客戶。實(shí)現(xiàn)在規(guī)定的延時(shí)內(nèi)將視頻數(shù)據(jù)傳給客戶。The RPC2 Subsystem (1)Side effects in Codas RPC2 system.RPC2提供了副作用例程的接口，供應(yīng)用程序開(kāi)發(fā)人員實(shí)現(xiàn)該例程The RPC2 Subsystem (2)(a) Sending an invalidation message one at a time.

21、(b) Sending invalidation messages in parallel.支持多播：支持多播：ServerServer記錄所有的客戶副本，修改時(shí)記錄所有的客戶副本，修改時(shí)ServerServer通知有關(guān)的通知有關(guān)的ClientClient使副本失效使副本失效(invalidation)(invalidation)。File-Oriented Communication in Plan 9Files associated with a single TCP connection in Plan 9.n Plan 9是一個(gè)基于文件的DFS。即對(duì)所有資源的訪問(wèn)用類似于文件的語(yǔ)法和操

22、作進(jìn)行。n 例如：ctl用于向連接發(fā)送控制命令，發(fā)送方向ctl中寫：connect 2. 接收向ctl中寫：announce 23(表示可以接收傳入的會(huì)話請(qǐng)求)。 Data文件通過(guò)執(zhí)行read和write實(shí)現(xiàn)數(shù)據(jù)交換.Naming 把主機(jī)名和文件的本地名字結(jié)合（簡(jiǎn)單、不提供把主機(jī)名和文件的本地名字結(jié)合（簡(jiǎn)單、不提供位置透明，如：網(wǎng)絡(luò)操作系統(tǒng)）位置透明，如：網(wǎng)絡(luò)操作系統(tǒng)）; ; 將遠(yuǎn)程文件目錄附加到本地名字空間中（比如：將遠(yuǎn)程文件目錄附加到本地名字空間中（比如：SUNSUN的的NFSNFS，系統(tǒng)提供，系統(tǒng)提供mountmount機(jī)制）機(jī)制）; ; 構(gòu)造全局的命名空間構(gòu)造全

23、局的命名空間. . Naming (1)Mounting (part of) a remote file system in NFS.Naming(2)Mounting (part of) a remote file system in NFS.Naming (4)Mounting nested directories from multiple servers in NFS.Naming(3)NFS采用Iterative方式解析AutomountingA simple automounter for NFS.Automounting (2)Using symbolic links with

24、automounting.Constructing a Global Name SpaceJunctions in GNS. GNS提供了建立全局名空間的方法，將維護(hù)一棵虛擬樹(shù)，其中每個(gè)結(jié)點(diǎn)都是一個(gè)目錄或者連接點(diǎn)（Junction）.同同 步步 (a) On a single processor, when a read follows a write, the value returned by the read is the value just written. Semantics of File Sharing (1)Semantics of File Sharing (2) (b)

25、In a distributed system with caching, obsolete（過(guò)時(shí)） values may be returned.Semantics of File Sharing (3)Four ways of dealing with the shared files in a distributed system.File Locking (1)NFSv4 operations related to file locking.實(shí)現(xiàn)了會(huì)話語(yǔ)義（續(xù)租）File Locking (2) The result of an open operation with share re

26、servations in NFS. (a) When the client requests shared access given the current denial state.客戶端請(qǐng)求的一種共享訪問(wèn)狀態(tài)，服務(wù)器給出了當(dāng)前的拒絕狀態(tài)。共享預(yù)約(share reservations )是另一種鎖定文件的隱含方法：客戶打開(kāi)文件時(shí)指定所需的訪問(wèn)類型（R,W,B），服務(wù)器當(dāng)前拒絕的訪問(wèn)類型（N,R,W,B）File Locking (3) The result of an open operation with share reservations in NFS. (b) When the

27、client requests a denial state given the current file access state. 試圖打開(kāi)已經(jīng)被另一個(gè)客戶訪問(wèn)的文件狀態(tài)，根據(jù)已被訪問(wèn)類型而確定的拒絕狀態(tài)。Sharing Files in CodaThe transactional behavior in sharing files in Coda. Coda提供了一種多副本修改的方法，設(shè)2個(gè)進(jìn)程A和B，若A以寫方式打開(kāi)文件，則其他打開(kāi)不允許；若A以讀方式打開(kāi)文件，則其他還允許再打開(kāi)，但通過(guò)失效信息告訴A讀的是老版本。Consistency and Replication緩存緩存 遠(yuǎn)程服務(wù)

28、遠(yuǎn)程服務(wù)( (效率低效率低) ) 本地緩存本地緩存緩存問(wèn)題包括緩存問(wèn)題包括: : 粒度粒度( (與通信有關(guān)與通信有關(guān)) ) 緩存位置緩存位置( (主存主存/ /副存副存) ) 一致性問(wèn)題一致性問(wèn)題 如何傳播副本的修改如何傳播副本的修改Client Caching (1)Client-side caching in NFS.Cache consistencyCan be divided into four types:Write through Good enough.Delayed Write Better Performance but can be ambiguous.Write on C

29、lose Matches session semantics.Centralized control Unix Semantics but not robust Client Caching (2)Using the NFS v.4 callback mechanism to recall file delegation.V4允許NFS Server將它的一部分權(quán)利委派給ClientClient-Side Caching in CodaThe use of local copies when opening a session in Coda.Coda客戶會(huì)緩存整個(gè)文件，服務(wù)器記錄了副本情況（

30、稱為回調(diào)承諾），當(dāng)客戶第一次更新其本地副本時(shí)通知服務(wù)器，向其它客戶發(fā)回調(diào)中斷，已表示副本無(wú)效，需要更新。需要更新不需要更新回調(diào)中斷Server Replication為提高性能，一般在客戶端對(duì)文件進(jìn)行為提高性能，一般在客戶端對(duì)文件進(jìn)行CacheCache副本副本; ;服務(wù)器端的復(fù)制往往是為了容錯(cuò)，實(shí)際性能可能會(huì)下降；服務(wù)器端的復(fù)制往往是為了容錯(cuò)，實(shí)際性能可能會(huì)下降；CodaCoda復(fù)制的單位是復(fù)制的單位是卷卷（傳統(tǒng)的文件系統(tǒng)）；（傳統(tǒng)的文件系統(tǒng)）；卷副本的卷副本的CodaCoda服務(wù)器集合服務(wù)器集合稱為稱為卷存儲(chǔ)組卷存儲(chǔ)組（VSGVSG）；出現(xiàn)故）；出現(xiàn)故障時(shí)，客戶不能訪問(wèn)障時(shí)，客戶不能訪問(wèn)V

31、SGVSG中的所有服務(wù)器。中的所有服務(wù)器?？稍L問(wèn)卷存儲(chǔ)組可訪問(wèn)卷存儲(chǔ)組（AVSGAVSG）是指由）是指由VSGVSG中，客戶此刻可以聯(lián)系的那些服務(wù)器組。中，客戶此刻可以聯(lián)系的那些服務(wù)器組。如果如果AVSGAVSG是空的，那么稱該客戶是斷開(kāi)的。是空的，那么稱該客戶是斷開(kāi)的。Server Replication in CodaTwo clients with a different AVSG for the same replicated file.一致性協(xié)議：一致性協(xié)議：ROWA（Read-One， Write-All），當(dāng)客戶需讀取一個(gè)文件時(shí)，該客戶聯(lián)系該文件所屬卷的AVSG中的一個(gè)成員。關(guān)閉

32、一個(gè)更新文件上的會(huì)話時(shí)，客戶將更新文件并行地傳給AVSG中的每個(gè)成員。但是，當(dāng)出現(xiàn)故障時(shí)，如何檢測(cè)不一致性？如下圖所示（一個(gè)跨3個(gè)服務(wù)器的卷S1,S2,S3）：Server Replication in CodaCoda采用版本向量CVV(Coda version vector) 方法解決一致性問(wèn)題。u客戶A從其AVSG中的一個(gè)服務(wù)器讀取（比如S1）f時(shí)，它也收到了CVV1（f）。當(dāng)它更新f后，A向其AVSG中的每個(gè)服務(wù)器（S1和S2）多播f，即CVV1（f）= CVV2（f）=2，2，1。u客戶B從S3接收副本f，并更新后，向S3傳遞更新： CVV3（f）=1，1，2。u這時(shí)通過(guò)CVV1（f

33、）= CVV2（f）=2，2，1不等于CVV3（f）=1，1，2就知道產(chǎn)生了沖突，通過(guò)解決沖突的方法來(lái)達(dá)到一致性。對(duì)等文件系統(tǒng)中的復(fù)制Structured Peer-to-Peer SystemsBalancing load in a peer-to-peer system by replication.Copalakrishnan等，2004給出了一種模式，把沿著查詢路徑分布的結(jié)點(diǎn)上的當(dāng)前負(fù)載考慮在內(nèi)。如下圖所示，當(dāng)從P到Q的查詢經(jīng)過(guò)R時(shí)，R將檢查是否把它的文件卸載給P（如果R服務(wù)的查詢請(qǐng)求過(guò)多）.容錯(cuò)性Handling Byzantine FailuresThe different pha

34、ses in Byzantine fault tolerance.準(zhǔn)備前：主機(jī)多播一個(gè)序號(hào)準(zhǔn)備：所有進(jìn)程對(duì)都應(yīng)該對(duì)請(qǐng)求次序達(dá)成一致提交：告訴其它進(jìn)程其在本地存儲(chǔ)了當(dāng)前視圖的請(qǐng)求。服務(wù)器組至少包含3K+1個(gè)進(jìn)程，2K+1稱為法定數(shù)量。無(wú)論何時(shí)一個(gè)進(jìn)程接收到一個(gè)請(qǐng)求，它都會(huì)把這個(gè)請(qǐng)求發(fā)給所有其它進(jìn)程，并且等待，直到從其他2K個(gè)進(jìn)程接收到一條確認(rèn)。并通過(guò)5個(gè)階段解決Byzantine的錯(cuò)誤SecurityThe NFS security architecture. Secure channel. Access controlSecure RPCs通過(guò)身份認(rèn)證建立Secure channel，有3種方

35、法:n 系統(tǒng)身份認(rèn)證，客戶向服務(wù)器發(fā)送有效ID等；n 使用Diffie-Hellman密鑰交換建立一個(gè)會(huì)話密鑰；n 通過(guò)Kerberos認(rèn)證協(xié)議，NFS4中支持RPCSEC-GSS（Generic Security Service ），它基于GSS-API，可以支持各種建立安全信道的安全性協(xié)議。Secure RPCsSecure RPC in NFSv4.Access ControlThe various kinds of users and processes distinguished by NFS with respect to access control.Access Control

36、The classification of operations recognized by NFS with respect to access control.OperationDescriptionRead_dataPermission to read the data contained in a fileWrite_dataPermission to to modify a files dataAppend_dataPermission to to append data to a fileExecutePermission to to execute a fileList_dire

37、ctoryPermission to to list the contents of a directoryAdd_filePermission to to add a new file t5o a directoryAdd_subdirectoryPermission to to create a subdirectory to a directoryDeletePermission to to delete a fileDelete_childPermission to to delete a file or directory within a directoryRead_aclPerm

38、ission to to read the ACLWrite_aclPermission to to write the ACLRead_attributesThe ability to read the other basic attributes of a fileWrite_attributes Permission to to change the other basic attributes of a fileRead_named_attrsPermission to to read the named attributes of a fileWrite_named_attrsPermission to to write the named attributes of a fileWrite_ownerPermission to to change the ownerSynchronizePermission to to access a file locally at the server with synchronous reads and writesDece