chapter2-分布式系統(tǒng)的基本原理2

分布計算環(huán)境鄒華北京郵電大學(xué)網(wǎng)絡(luò)技術(shù)研究院2015.9

Chapter2

分布式系統(tǒng)的基本原理主要內(nèi)容體系結(jié)構(gòu)進程通信命名一致性和復(fù)制容錯安全

通信主要內(nèi)容分層通信協(xié)議遠程過程調(diào)用和遠程對象調(diào)用面向消息的通信面向流的通信多播通信通信主要內(nèi)容分層通信協(xié)議遠程過程調(diào)用和遠程對象調(diào)用面向消息的通信面向流的通信多播通信OSI模型由于沒有共享存儲器，分布式系統(tǒng)中的所有通信都是基于（低層）消息交換的OSI模型（開放式系統(tǒng)互聯(lián)參考模型）用來支持開放式系統(tǒng)間的通信開放式系統(tǒng)是可以通過標(biāo)準(zhǔn)規(guī)則與其他開放式系統(tǒng)通信的系統(tǒng)，這些規(guī)則規(guī)定了發(fā)送和接收消息的格式、內(nèi)容以及相應(yīng)的含義OSI模型中的層、結(jié)構(gòu)和協(xié)議分層：功能分解。獨立性。接口（提供功能的操作集）：標(biāo)準(zhǔn)化。協(xié)議棧：有序性典型消息格式應(yīng)用層協(xié)議在OSI七層模型的傳輸層之上又劃分了三個層，在實踐中，只用到了其中的應(yīng)用層在Internet協(xié)議簇中，傳輸層之上的所有內(nèi)容都合并到了一起，稱為應(yīng)用層應(yīng)用層成為所有由于各種原因不能歸納到某個較低層中去的應(yīng)用程序和協(xié)議的容器缺乏對應(yīng)用程序、針對特定應(yīng)用程序的協(xié)議以及通用協(xié)議的明確區(qū)分ftp協(xié)議和ftp程序HTTP協(xié)議中間件協(xié)議有的應(yīng)用層協(xié)議，可用于支持多種應(yīng)用程序的通信，因此可看做是對多種應(yīng)用程序有用的通用協(xié)議但不能算作傳輸協(xié)議，很多情況下歸入中間件協(xié)議中間件協(xié)議（2）中間件協(xié)議是中間件提供的用于支持高層應(yīng)用系統(tǒng)通信的協(xié)議不同的中間件系統(tǒng)有不同的中間件協(xié)議支持遠程過程調(diào)用的協(xié)議，如DCE中支持遠程對象調(diào)用的協(xié)議，如CORBA中支持實時流數(shù)據(jù)傳輸并保持同步的協(xié)議可靠多播協(xié)議，用于支持可靠多播服務(wù)的中間件系統(tǒng)中間件的通信類型從通信持久性方面持久通信：傳輸?shù)南⒁恢庇赏ㄐ胖虚g件存儲，直到該消息被傳送給接收方，如電子郵件系統(tǒng)瞬時通信：通信中間件只在發(fā)送和接收應(yīng)用程序正在運行的時候才存儲消息，即由于傳輸中斷或者接收方當(dāng)前不在活動狀態(tài)，中間件就不傳輸消息，而是丟棄消息中間件的通信類型(2)從通信同步性方面同步通信：發(fā)送方提交消息后將被阻塞，直到知道其消息被接收。發(fā)送方可有三類同步點基于發(fā)送：發(fā)送方中間件請求傳輸完成基于接收：請求被傳送到目標(biāo)接收方基于響應(yīng)：接收方返回響應(yīng)異步通信：發(fā)送方在提交要傳輸?shù)南⒑罅⒖探又罄m(xù)的執(zhí)行，不會阻塞從通信連續(xù)性方面分：不連續(xù)通信和流通信這些通信方式可以進行各種組合通信持久性和同步性的組合（a)持久異步通信(b)持久同步通信通信持久性和同步性的組合（2）（a)持久異步通信(b)持久同步通信（c)瞬時異步通信(d)基于發(fā)送的瞬時同步通信通信持久性和同步性的組合（3）（e)基于接收的(f)基于響應(yīng)的瞬時同步通信瞬時同步通信通信主要內(nèi)容分層通信協(xié)議遠程過程調(diào)用和遠程對象調(diào)用面向消息的通信面向流的通信多播通信遠程過程調(diào)用RPC像調(diào)用本地子程序一樣，調(diào)用遠程子程序調(diào)用者和被調(diào)者都不用考慮通信問題服務(wù)器客戶OS主程序存根OS子程序存根RPC的基本處理過程

傳統(tǒng)RPC和異步RPC(a)傳統(tǒng)的RPC(b)異步RPC遠程方法調(diào)用RMI像調(diào)用本地對象的方法一樣，調(diào)用遠程對象的方法調(diào)用者和被調(diào)者都不用考慮通信問題通信主要內(nèi)容分層通信協(xié)議遠程過程調(diào)用和遠程對象調(diào)用面向消息的通信面向流的通信多播通信面向消息的通信遠程過程調(diào)用和遠程方法調(diào)用都有助于隱藏分布式系統(tǒng)中的通信但這兩種機制并不總是適用的如當(dāng)無法保證發(fā)送請求時接收端正在執(zhí)行的情況下如同步性會阻塞發(fā)送進程需要其他通信機制的支持如面向消息的通信面向消息的瞬時通信：套接字很多分布式系統(tǒng)和應(yīng)用程序直接構(gòu)建在傳輸層提供的簡單的面向消息的模型之上人們已對傳輸層接口的標(biāo)準(zhǔn)化給予了充分的重視程序員通過一個簡單的原語集就可以使用傳輸層提供的全部（消息傳遞）協(xié)議標(biāo)準(zhǔn)化的接口還使得應(yīng)用程序在不同機器之間的移植變得容易如支持TCP/IP的Berkeley套接字socket

TCP/IP套接字原語原語意義Socket創(chuàng)建新的通信端點Bind將本地地址附加(attach)到套接字上Listen宣布已準(zhǔn)備好接受連接Accept在準(zhǔn)備好連接請求之前阻塞調(diào)用方Connect主動嘗試確立連接Send通過連接發(fā)送數(shù)據(jù)Receive通過連接接受數(shù)據(jù)Close釋放連接使用套接字的面向連接通信模式感受套接字編程（Java）Server側(cè)：ServerSocketserver=newServerSocket(10000);While(true){ Sockets=server.accept(); newServerThread(s).start();}客戶側(cè)：Sockets=newSocket(“”,10000);InputStreamis=s.getInputStream();is.close();s.close();

面向消息的瞬時通信：MPI套接字抽象層在傳輸層，只支持簡單的send和receive原語套接字用于使用TCP/IP協(xié)議進行通信，不適用于為高速互聯(lián)網(wǎng)開發(fā)的專用協(xié)議，比如不同的緩沖和同步方式多數(shù)高性能計算機系統(tǒng)附帶專用通信庫，帶來可移植性問題消息傳遞方面的標(biāo)準(zhǔn)出臺：消息傳遞接口MPIMPI的特點提供高層通信，支持并行計算,如MPP,COW可靠的底層網(wǎng)絡(luò)支持分組通信，地址（groupID,processID）支持多種瞬時通信方式瞬時異步MPI_bsend基于發(fā)送的瞬時同步MPI_send基于接收的瞬時同步MPI_ssend基于響應(yīng)的瞬時同步MPI_sendrecvMPI原語原語意義MPI_bsend將要送出的消息追加到本地發(fā)送緩沖區(qū)中MPI_send發(fā)送消息，并等待直到消息復(fù)制到本地或遠程緩沖區(qū)中為止MPI_ssend發(fā)送消息，并等待直到對方開始接受為止MPI_sendrecv發(fā)送消息，并等待直到收到應(yīng)答消息為止MPI_isend傳送要送出消息的引用，隨后繼續(xù)執(zhí)行MPI_issend傳送要送出消息的引用，并等待直到對方開始接受為止MPI_recv接受消息，如果不存在等待的消息則阻塞MPI_irecv檢查是否有輸入的消息，但是無論有沒有消息都不會阻塞面向消息的持久通信其支持系統(tǒng)一般稱為消息隊列系統(tǒng)或者面向消息的中間件支持持久異步通信適合于對傳輸時間要求寬松的場合，如幾分鐘。不保證消息到達接收方的時間，也不保證接收方一定讀取消息松散耦合的通信方式，使用方便使用隊列的4種松耦合通信方式消息隊列接口的基本接口原語意義Put將消息追加進指定隊列Get調(diào)用進程阻塞，直到指定隊列變?yōu)榉强諡橹?，然后取出隊列中的第一個消息Poll查看指定隊列中的消息，并且取出隊列中的第一個消息。不阻塞調(diào)用進程。Notify注冊一個處理程序，在有消息進入指定隊列時調(diào)用該處理程序。消息隊列源隊列目標(biāo)隊列隊列尋址隊列名網(wǎng)絡(luò)地址隊列管理器發(fā)送/接收中轉(zhuǎn)消息隊列系統(tǒng)的一般架構(gòu)隊列級編址與網(wǎng)絡(luò)級編址含有路由器的消息隊列系統(tǒng)一般架構(gòu)消息轉(zhuǎn)換器（Broker）當(dāng)發(fā)送方發(fā)送的消息和接收方需要的消息在格式上、內(nèi)容上等有所不同時，消息轉(zhuǎn)換器可以對消息進行轉(zhuǎn)換或處理格式轉(zhuǎn)換應(yīng)用層網(wǎng)關(guān)消息轉(zhuǎn)換器的一般結(jié)構(gòu)通信主要內(nèi)容分層通信協(xié)議遠程過程調(diào)用和遠程對象調(diào)用面向消息的通信面向流的通信多播通信面向流的通信媒體（media）:媒體是指傳播信息的媒介。它是指人借助用來傳遞信息與獲取信息的工具、渠道、載體、中介物或技術(shù)手段例：圖像格式:GIF、JPEG、TIF連續(xù)型媒體(continuousrepresentationmedia)在數(shù)據(jù)項之間存在時間關(guān)系例：CD:采樣值/1/44100秒，VCD:禎/1/30秒離散型媒體

數(shù)據(jù)流數(shù)據(jù)流（stream）異步傳輸:delay(0,∞);delay(傳輸延遲)同步傳輸:delay(0,max]等時(isochronous)傳輸:delay[min,max]復(fù)雜數(shù)據(jù)流由多個子數(shù)據(jù)流（substream）組成例：DVD(（左聲道，右聲道），視頻，字幕)數(shù)據(jù)流傳輸例流的服務(wù)質(zhì)量Qos非功能需求一般稱為服務(wù)質(zhì)量QoS流的QoS描述了低層分布式系統(tǒng)及網(wǎng)絡(luò)在確保傳輸質(zhì)量方面的需求QoS屬性例：數(shù)據(jù)傳輸要求的比特率創(chuàng)建會話的最大延時端到端最大延時最大往返延時誤碼率丟包率

有很多支持QoS的方法流同步多媒體系統(tǒng)中，常常需要不同的流互相之間保持同步如離散數(shù)據(jù)流與連續(xù)數(shù)據(jù)流之間保持同步幻燈片演示與音頻如連續(xù)流之間的同步放映影片時的視頻流和音頻流同步機制例1在數(shù)據(jù)單元層上的顯式同步讀寫進程：讀流數(shù)據(jù)單元，同步寫同步機制例2由高層接口支持的同步多媒體中間件提供控制接口用戶自定義程序：檢查同步，調(diào)整流速通信主要內(nèi)容分層通信協(xié)議遠程過程調(diào)用和遠程對象調(diào)用面向消息的通信面向流的通信多播通信多播通信組：由系統(tǒng)或用戶確定的若干個進程的集合組的成員籍（membership）通信方式：點到點通信（point-to-point）:單播（unicast）一到多通信(one-to-many):多播（multicast）、廣播（broadcast）單點、多播和廣播“通信”總結(jié)進程間通信功能是所有分布式系統(tǒng)所必須的傳統(tǒng)的分布式系統(tǒng)通過基于傳輸層提供的低層消息來進行通信，如TCP/IP套接字分布計算環(huán)境（中間件）提供更高層次的通信支持RPC、RMI基于消息的通信RPC、RMI等主要提供同步通信功能，并在一定程度上放松了同步的要求但在一些應(yīng)用場合，面向消息的通信的異步通信更方便一些瞬時和持久，同步和異步“通信”總結(jié)（2）面向流的通信服務(wù)質(zhì)量QoS流的同步多播通信從發(fā)送方到多個接收方主要內(nèi)容體系結(jié)構(gòu)進程通信命名一致性和復(fù)制容錯安全

命名名稱在所有計算機系統(tǒng)中都起著非常重要的作用共享資源、唯一標(biāo)識實體等命名系統(tǒng)的主要功能是把名稱解析為它所標(biāo)識的實體分布式系統(tǒng)中，命名系統(tǒng)的實現(xiàn)本身通常是分布在多臺計算機上的其分布機制對命名系統(tǒng)的效率和可靠性起著關(guān)鍵的作用基本概念實體：系統(tǒng)中的任何事物主機、打印機、磁盤、文件、進程、用戶、郵箱、Web頁面、消息實體的名字（Name）:一個位串或字符串，可唯一地標(biāo)識一個實體如主機名、文件名、進程名、用戶名實體訪問點（accesspoint）：用于訪問該實體的接口可以有多個訪問點實體可以改變訪問點訪問點可賦給另一個實體地址（address）：訪問點的名稱可能的命名方法（1）地址（address）：訪問點的地址用地址作為名稱IP地址、電話號碼看上去用地址作為名稱似乎很方便，但實際上，這種命名非常不靈活且用戶不友好。如，服務(wù)器運行的主機經(jīng)常會變化，提供多個訪問點的實體（Web服務(wù)）可能的命名方法（2）標(biāo)識符：具有以下屬性的一個標(biāo)識符最多引用一個實體每個實體被一個標(biāo)識符所引用一個標(biāo)識符總是引用同一個實體（不準(zhǔn)重用）使用標(biāo)識符來作為實體的名稱不同進程使用的標(biāo)識符會不會重名或者不一致？在大多數(shù)計算機系統(tǒng)中，地址和標(biāo)識符僅使用計算機可讀的方式，如位串形式使用用戶友好的名稱用戶理解的字符串，如“temp”,“bank”命名系統(tǒng)在分布式系統(tǒng)中，一般使用位置無關(guān)的命名方法因此，命名系統(tǒng)的主要工作就是把名稱解析為地址簡單地，命名系統(tǒng)中可以有一個名稱到地址的綁定表如（Name，address）表大型分布式系統(tǒng)，資源眾多，一個表可能無法滿足要求分布式系統(tǒng)常見的三類命名系統(tǒng)無結(jié)構(gòu)命名結(jié)構(gòu)化命名基于屬性的命名無結(jié)構(gòu)命名無結(jié)構(gòu)名稱：名稱中不包含任何有關(guān)如何定位其相關(guān)實體的訪問點的信息多種方法支持無結(jié)構(gòu)名稱的解析廣播和多播Internet地址解析協(xié)議ARP分布式散列表………….無結(jié)構(gòu)名稱適用于機器的理解，人難以理解結(jié)構(gòu)化命名結(jié)構(gòu)化名稱：簡單的、人類可理解名稱文件命名：/user/libInternet上的網(wǎng)頁地址：名稱通常組成名字空間：根節(jié)點、目錄節(jié)點、葉節(jié)點名字空間的實現(xiàn)命名服務(wù)：管理名字空間，允許用戶和進程添加、刪除和查找名稱的服務(wù)。命名服務(wù)由命名服務(wù)器實現(xiàn)大型分布式系統(tǒng)包含很多實體，跨越很大的地理區(qū)域，需要使用多臺命名服務(wù)器來分散名字空間的管理。DNS的命名空間劃分示例名字解析方法例迭代式名字解析：名字解析器從根名字服務(wù)器開始，逐個與名字服務(wù)器交互，實現(xiàn)名字的解析root:<nl,vu,vs,ftp,pub,global,index.txt>基于屬性的命名無結(jié)構(gòu)命名和結(jié)構(gòu)化命名提供了一種唯一的與位置無關(guān)的方法來命名實體，進一步地，結(jié)構(gòu)化命名還具有良好的用戶友好性位置無關(guān)和用戶友好不是命名實體的唯一標(biāo)準(zhǔn)，隨著可用信息的增加，高效地查找實體變得更重要。在分布式系統(tǒng)中，常用（屬性、值）來描述實體，稱為基于屬性的命名。可使用實體的屬性來查找實體基于屬性的命名系統(tǒng)稱為目錄服務(wù)，實體有可供查找的相關(guān)屬性集。如LDAP目錄服務(wù)LDAP目錄服務(wù)系統(tǒng)基于LDAP協(xié)議（輕量級目錄訪問協(xié)議）從OSIX.500目錄服務(wù)派生國際電信聯(lián)盟（ITU）關(guān)于目錄服務(wù)的建議標(biāo)準(zhǔn)LDAP目錄項目錄項:由多個記錄（屬性，值）組成。多值屬性:用數(shù)組或鏈表表示目錄信息庫(DIB)所有目錄項的集合。每個記錄都是唯一命名的，所以可以被查找LDAP目錄項舉例/c=NL/O=VrijeUniversity/OU=Comp.Sc.類似于DNS名nl.vu.cs屬性縮寫值CountryCNLLocalityLAmsterdamOrganizationLVrijeUniversiteitOrganizationalUnitOUMath.&Comp.Sc.CommonNameCNMainserverMail_Servers--,192.31.231,6FTP_Server--1WWW_Server--1目錄信息樹用于描述目錄項集合的層次結(jié)構(gòu)，命名圖查找操作示例Answer=search(“&(C=NL)(O=VrijeUniversity)(OU=*)(CN=Mainserver)”)查找在國家名為NL、組織名為VrijeUniversity的地方的主服務(wù)器（CN為MainServer)，對組織名OU不關(guān)注將返回一個列表，其中每個記錄滿足上述屬性描述“命名系統(tǒng)”總結(jié)名稱可用來表示實體，基本有3種類型的名稱，地址、標(biāo)識符、用戶友好的名稱無層次命名系統(tǒng)需要將標(biāo)識符解析為對應(yīng)的實體地址，有很多方法介紹。結(jié)構(gòu)化名稱可以很容易組織成名稱空間，名稱空間可以用命名圖來表示，名稱解析的過程是通過查找路徑名的各個部分來貫穿該命名圖。基于屬性的命名系統(tǒng)中，實體是由（屬性、值）對集來描述，可基于屬性查找滿足條件的實體主要內(nèi)容體系結(jié)構(gòu)進程通信命名一致性和復(fù)制容錯安全

引言進行數(shù)據(jù)復(fù)制的主要原因：可靠性：一個副本被破壞，可以切換到另外的副本，保護數(shù)據(jù)，不影響應(yīng)用的運行。性能：并行性、可伸縮性，（服務(wù)器數(shù)量、地域）服務(wù)器數(shù)量，可均衡負載，提高訪問性能地域擴展，就近訪問，提高性能。進行數(shù)據(jù)復(fù)制是有代價的，一致性保證例1：Web頁的Cache例2：鏡像網(wǎng)站

支持伸縮性的復(fù)制技術(shù)將數(shù)據(jù)的副本放置在處理它們的進程附近以減少訪問時間，解決可伸縮性問題復(fù)制策略設(shè)進程P對數(shù)據(jù)d的訪問N次/秒，d的更新M次/秒當(dāng)N<<M時，訪問/更新比非常低，由于一致性維護帶來更大代價，因此，不應(yīng)復(fù)制Internet客戶服務(wù)器支持伸縮性的復(fù)制技術(shù)（2）一致性維護與可伸縮性問題保證所有的副本都是相同的，--〉緊密一致性當(dāng)某個副本上執(zhí)行更新操作時，需對所有副本進行全局同步，在大型系統(tǒng)上很難實施--〉可伸縮性問題解決策略松馳一致性，放寬在一致性方面的限制，所有副本不一定保持完全相同，盡量減少立即的全局同步一致性放寬的程度主要取決于復(fù)制數(shù)據(jù)的訪問和更新模式，同時還取決于這些數(shù)據(jù)的用途常見的一致性模型以數(shù)據(jù)為中心的一致性模型以用戶為中心的一致性模型以數(shù)據(jù)為中心的一致性模型分布式數(shù)據(jù)倉(datastore)模型物理上，分布的和復(fù)制的例如，分布式共享內(nèi)存、數(shù)據(jù)庫、文件操作：每個進程可執(zhí)行讀操作，寫操作寫操作在本地副本上進行，再傳播給其他副本一致性模型以數(shù)據(jù)為中心的一致性模型，實質(zhì)上是進程和數(shù)據(jù)存儲之間的一個約定如果進程遵守這些約定，那么數(shù)據(jù)存儲將正常工作顯然，一個進程在數(shù)據(jù)項上執(zhí)行讀操作時，該進程肯定期待該操作返回的是在其最后一次寫操作之后的結(jié)果但在沒有全局時鐘的情況下，精確地定義哪些寫操作時最后一次寫操作時十分困難的作為替代方法，產(chǎn)生了一系列放寬了限制條件的一致性模型，每種模型都有效地限制了在一個數(shù)據(jù)項上執(zhí)行一次讀操作所應(yīng)返回的值一致性模型舉例嚴(yán)格一致性：對數(shù)據(jù)項x的讀操作返回的值為最近寫入x的值不可實現(xiàn)順序一致性：當(dāng)進程在多臺（可能）不同的機器上并發(fā)執(zhí)行時，任何讀、寫操作的有效交叉都是可以接受的行為，但所有進程看到的是相同的操作交叉順序因果一致性：一種弱化的因果一致性，所有進程必須以相同的順序看到具有潛在因果關(guān)系的寫操作，不同進程可以以不同順序看到?jīng)]有因果關(guān)系的并發(fā)寫操作。……………….以用戶為中心的一致性模型以數(shù)據(jù)為中心的一致性模型的一個重要假設(shè)是并發(fā)進程可能同時更新數(shù)據(jù)存儲這里討論的分布式數(shù)據(jù)存儲區(qū)沒有同時更新（無寫-寫沖突）或容易解決大多數(shù)操作為讀操作哪怕是舊的數(shù)據(jù)，用戶也常認(rèn)為是可接受的，如Web網(wǎng)頁（服務(wù)器，代理緩存）客戶為中心的一致性（Client-centric）保證一個客戶對數(shù)據(jù)存儲的訪問是一致的不考慮不同客戶之間的并發(fā)訪問典型應(yīng)用場景：移動用戶問題移動用戶問題用戶在一段時間內(nèi)要連接不同的副本，而這些副本的差別應(yīng)該是透明的。以客戶為中心的一致性模型例最終一致性：如果在一段時間內(nèi)沒有更新操作，那么所有的副本將逐漸趨于一致單調(diào)讀一致性：如果一個進程已經(jīng)在t時刻看到x的值，那么以后它不會看到較老版本的x的值單調(diào)寫一致性：一個進程對數(shù)據(jù)項X執(zhí)行的寫操作必須在該進程對X執(zhí)行的任何后續(xù)寫操作之前完成………………..復(fù)制管理任何支持復(fù)制的分布式系統(tǒng)，需解決兩個問題：決定何時、何處、由誰來放置副本:服務(wù)器放置：找到放置或托管數(shù)據(jù)存儲的服務(wù)器的最佳位置。內(nèi)容放置：找到放置內(nèi)容的最佳服務(wù)器。何種機制保證副本的一致性。服務(wù)器放置基于對客戶和網(wǎng)絡(luò)屬性進行分析、優(yōu)化和決策，如：以客戶與位置之間的距離作為計算依據(jù)，距離可通過延時或帶寬來度量，在某個時間里選取服務(wù)器，使得服務(wù)器與客戶的平均距離最小。利用聚類方法，標(biāo)識放置副本的區(qū)域，區(qū)域指訪問相同內(nèi)容的結(jié)點集，且結(jié)點之間的延時小?！瓋?nèi)容復(fù)制與放置從邏輯上可以組織為三種不同類型的副本:永久副本。服務(wù)器啟動的副本。客戶啟動的副本。永久副本服務(wù)器啟動的副本客戶啟動的副本永久副本構(gòu)成分布式數(shù)據(jù)存儲的初始集，一般數(shù)量很小，常用的分布方式：集群：在單個位置、有限數(shù)量服務(wù)器，復(fù)制鏡像：地理上分布到因特網(wǎng)特點：靜態(tài)服務(wù)器