分布式系統(tǒng)第二章

分布式系統(tǒng)第二章第一頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈22.1體系結(jié)構(gòu)的樣式2.2系統(tǒng)體系結(jié)構(gòu)2.3體系結(jié)構(gòu)與中間件2.4自主管理2.5客戶/服務(wù)器模型第二章主要內(nèi)容第二頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈3

軟件體系結(jié)構(gòu)（SoftwareArchitecture）軟件的組件，以及組件之間的相互關(guān)系軟件體系結(jié)構(gòu)的要素組件(component)：模塊單元，能提供良好的接口連接器（connector）：實現(xiàn)組件間通信的機(jī)制軟件體系結(jié)構(gòu)的樣式如何表示一個體系結(jié)構(gòu)常用的有4種2.1體系結(jié)構(gòu)的樣式第三頁，共五十八頁，2022年，8月28日2009-9-14計算機(jī)軟件所于戈4

系統(tǒng)由自上而下的不同層次的組件組成；只有相鄰的層次可以通信；請求消息自上而下，響應(yīng)自下而上。層次型體系結(jié)構(gòu)第N層第N-1層第2層第1層第四頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈5

基于對象模型每個組件對應(yīng)一個對象；組件之間通信通過遠(yuǎn)程方法調(diào)用（RMI）實現(xiàn)；面向?qū)ο蟮捏w系結(jié)構(gòu)對象對象對象對象對象第五頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈6

組件間的通信，通過基于一個公用的存儲（如共享的分布式文件系統(tǒng)）實現(xiàn)例如，基于Web的分布式系統(tǒng)，組件使用共享的基于Web的數(shù)據(jù)服務(wù)以數(shù)據(jù)為中心的體系結(jié)構(gòu)第六頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈7

組件間的通信，通過事件（可帶有數(shù)據(jù)）的傳播實現(xiàn)；例如，發(fā)布/訂閱(publish/subscribe)系統(tǒng)以事件為中心的體系結(jié)構(gòu)組件組件傳送發(fā)布事件總線組件組件組件共享（持久）的數(shù)據(jù)空間傳送發(fā)布第七頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈8

系統(tǒng)體系結(jié)構(gòu)（SystemArchitecture）軟件體系結(jié)構(gòu)的具體實例

集中型體系結(jié)構(gòu)客戶/服務(wù)器模型

服務(wù)器：實現(xiàn)特定服務(wù)的進(jìn)程客戶：向服務(wù)器提出請求、等待答復(fù)的進(jìn)程請求/答復(fù)模式2.2系統(tǒng)體系結(jié)構(gòu)請求答復(fù)客戶服務(wù)器等待第八頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈9層次型C/S體系結(jié)構(gòu)用戶接口層、處理層、數(shù)據(jù)層例：搜索引擎第九頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈10多層C/S體系結(jié)構(gòu)瘦客戶/胖服務(wù)器：用戶接口簡單，但后端負(fù)載重胖客戶/瘦服務(wù)器：能提高性能，但管理困難客戶機(jī)服務(wù)器第十頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈11三層C/S體系結(jié)構(gòu)舉例用戶接口應(yīng)用服務(wù)器數(shù)據(jù)庫服務(wù)器時間第十一頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈12新型體系結(jié)構(gòu)垂直分布：不同功能的分布水平分布：相同功能的復(fù)制對等型（peer-peer）分布水平分布的Web服務(wù)器負(fù)載平衡、容錯等第十二頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈13P2P技術(shù)從C/S模式到P2P模式

引自：中科院計算所羅杰文PeertoPeer綜述第十三頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈14P2P技術(shù)P2P應(yīng)用文件內(nèi)容共享和下載，例如Napster、Gnutella、eDonkey、eMule、Maze、BT等；計算能力和存儲共享，例如SETI@home、Avaki、PopularPower等；協(xié)同與服務(wù)共享平臺，例如JXTA、Magi、Groove等；即時通訊工具，包括ICQ、QQ、YahooMessenger、MSNMessenger等；P2P通訊與信息共享，例如Skype、Crowds、OnionRouting等；網(wǎng)絡(luò)電視：沸點、PPStream、PPLive、QQLive、SopCast等。

第十四頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈15P2P技術(shù)覆蓋網(wǎng)絡(luò)(overlaynetwork)：

建立在另一個網(wǎng)絡(luò)上的網(wǎng)絡(luò)，屬于應(yīng)用層網(wǎng)絡(luò)，面向應(yīng)用層的，不考慮或很少考慮網(wǎng)絡(luò)層，物理層的問題。P2P網(wǎng)絡(luò)是建立在Internet之上一種覆蓋網(wǎng)絡(luò)。P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)集中型（CentralizedTopology）；分散型無結(jié)構(gòu)拓?fù)洌―ecentralizedUnstructuredTopology）；分散型結(jié)構(gòu)化拓?fù)洌―ecentralizedStructuredTopology，也稱作DHT網(wǎng)絡(luò)）；半分散型拓?fù)洌≒artiallyDecentralizedTopology）。

第十五頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈16P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)集中型拓?fù)浣Y(jié)構(gòu)

例，MP3共享軟件Napster，通過一個中央索引服務(wù)器保存所有Napster用戶上傳的音樂文件索引和存放位置的信息。存在問題中心節(jié)點的單點失效中心節(jié)點的維護(hù)成本可伸縮性第十六頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈17P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分散型無結(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)

例，Gnutella協(xié)議?；谕耆S機(jī)圖的Flooding搜索算法。存在問題不能保證性能網(wǎng)絡(luò)帶寬的消耗非常大可伸縮性差第十七頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈18P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)覆蓋網(wǎng)絡(luò)構(gòu)造算法（Gossip-basedprotocols）

關(guān)于所有節(jié)點的表，稱為全局視圖（totalview）。每個節(jié)點維護(hù)一個部分視圖（partialview），含有c個鄰接點的列表。表項：=<IP，age>節(jié)點之間定期交換表項。由主動線程（可主動發(fā)起通信）和被動線程完成。節(jié)點的加入與任意一個已知的節(jié)點進(jìn)行視圖交換節(jié)點的刪除可自行離開，無需通知其他節(jié)點。當(dāng)其他節(jié)點發(fā)現(xiàn)某節(jié)點P不再響應(yīng)時，將其從表中刪除第十八頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈19P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)主動線程和被動線程的執(zhí)行步驟doforeverreceivebufferpfromp

ifpullthen//0istheinitialagebuffer←((MyAddress,0))view.permute()moveoldestHitemstoendofviewbuffer.append(view.head(c/2-1))sendbuffertopview.select(c,H,S,bufferp)view.increaseAge()doforeverwait(Ttimeunits)p←view.selectPeer()

ifpushthen//0istheinitialagebuffer←((MyAddress,0))view.permute()moveoldestHitemstoendofviewbuffer.append(view.head(c/2-1))sendbuffertop

else//emptyviewtotriggerresponsesend(null)top

ifpullthenreceivebufferpfrompview.select(c,H,S,bufferp)view.increaseAge()（a）（b）第十九頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈20P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分散式結(jié)構(gòu)化拓?fù)浣Y(jié)構(gòu)

采用分布式散列表（DistributedHashTable,簡寫成DHT）技術(shù)來組織網(wǎng)絡(luò)中的結(jié)點。加密散列函數(shù)，將一個對象的名字或關(guān)鍵詞映射為128位或160位的散列值DHT是一個由廣域范圍大量結(jié)點共同維護(hù)的巨大散列表。散列表被分割成不連續(xù)的塊，每個結(jié)點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。Tapestry，Pastry，Chord和CAN第二十頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈21P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分散式結(jié)構(gòu)化拓?fù)浣Y(jié)構(gòu)

例：MIT的Chord

系統(tǒng)網(wǎng)絡(luò)結(jié)點按照一定的方式分配一個唯一結(jié)點標(biāo)識符(NodeID)通過散列運(yùn)算為對象產(chǎn)生一個唯一的對象標(biāo)識符(ObjectID）分布式查找協(xié)議，將指定的關(guān)鍵字(Key)映射到對應(yīng)的結(jié)點(Node)時間復(fù)雜性O(shè)(log(N))第二十一頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈22P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分散式結(jié)構(gòu)化拓?fù)浣Y(jié)構(gòu)

例：CAN系統(tǒng)將(key,value)對存儲在擁有該點所在區(qū)域的結(jié)點內(nèi)路由算法：將請求傳給當(dāng)前結(jié)點四鄰中坐標(biāo)最接近目標(biāo)點的結(jié)點時間復(fù)雜性O(shè)(n/d)，d為系統(tǒng)維數(shù)第二十二頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈23P2P網(wǎng)絡(luò)的拓?fù)涔芾硎褂脽o結(jié)構(gòu)P2P技術(shù)構(gòu)造特定的結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)的兩層結(jié)構(gòu)第二十三頁，共五十八頁，2022年，8月28日2009-9-14計算機(jī)軟件所于戈24P2P網(wǎng)絡(luò)的拓?fù)涔芾硎褂脙蓪拥臒o結(jié)構(gòu)P2P系統(tǒng)，最終生成的特定的覆蓋網(wǎng)絡(luò)第二十四頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈25超級節(jié)點（Superpeer）超級節(jié)點：能夠維護(hù)索引或充當(dāng)代理的節(jié)點第二十五頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈26混合型體系結(jié)構(gòu)將客戶/服務(wù)器結(jié)構(gòu)與非集中式結(jié)構(gòu)相結(jié)合邊界服務(wù)器系統(tǒng)（edgeserver）C/SP2P第二十六頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈27混合型體系結(jié)構(gòu)協(xié)作分布式系統(tǒng)例1：文件共享系統(tǒng)BitTorrent強(qiáng)制每個參與者，即可下載文件，也負(fù)責(zé)上載文件全局目錄：在Web站點中保存，指向下載文件的tracker。跟蹤器（tracker）:記錄活動節(jié)點的服務(wù)器第二十七頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈28混合型體系結(jié)構(gòu)協(xié)作分布式系統(tǒng)例2：Globule系統(tǒng)協(xié)作式CDN（collaborativecontentdistributionnetwork）沒有邊界服務(wù)器用戶提供增強(qiáng)型Web服務(wù)器，包含如下3種組件可重定位客戶請求到其他服務(wù)器可分析訪問模式可管理Web頁復(fù)制第二十八頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈292.3體系結(jié)構(gòu)與中間件中間件在體系結(jié)構(gòu)中的位置中間件如何適應(yīng)于應(yīng)用需要中間件的多種版本中間件可重新配置和定制第二十九頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈30攔截器（Interceptor）攔截器（Interceptor）軟件結(jié)構(gòu)可中斷正常執(zhí)行的控制流，插入執(zhí)行其他代碼例：遠(yuǎn)程對象調(diào)用請求級攔截器消息級攔截器第三十頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈31自適應(yīng)軟件自適應(yīng)軟件可以地自動適應(yīng)環(huán)境變化，如移動、QoS、故障、能耗隨著環(huán)境變化而變化三種方案分離關(guān)注點（Separationofconcerns）把主要功能與附加功能分離開面向方面的軟件開發(fā)（aspect-orientedsoftwaredevelopment）第三十一頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈32自適應(yīng)軟件三種方案計算反射（Computationalreflection）自我檢查，并調(diào)整自身行為基于組件的設(shè)計運(yùn)行時，進(jìn)行動態(tài)配置遲后綁定（latebinding）第三十二頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈33自治計算（autonomiccomputing）可自動地自適應(yīng)變化自主系統(tǒng)（self-starsystem）自主管理自主恢復(fù)自主配置自主優(yōu)化2.4分布式系統(tǒng)的自主管理第三十三頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈34反饋控制模型三要素：①測量；②分析；③調(diào)整；自主控制第三十四頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈35例：Astrolabe監(jiān)視系統(tǒng)觀察系統(tǒng)行為。區(qū)域信息：數(shù)據(jù)收集和信息聚集自主監(jiān)視第三十五頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈36例：Globule差分復(fù)制策略What-if分析：復(fù)制的位置、一致性維護(hù)策略自主復(fù)制管理第三十六頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈37例：Globule差分復(fù)制策略軌跡驅(qū)動模擬方法：根據(jù)預(yù)測誤差與跟蹤軌跡長度的關(guān)系，確定復(fù)制策略自主復(fù)制管理第三十七頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈38例：Jade系統(tǒng)自動組件修復(fù)管理修復(fù)過程的執(zhí)行步驟:終止非故障組件和故障組件之間的所有綁定請求節(jié)點管理器去在域中啟動和增加一個新節(jié)點將新節(jié)點配置成與崩潰節(jié)點相同的組件重新建立所有在前面已終止的所有綁定自主修復(fù)第三十八頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈392.5客戶-服務(wù)器模型服務(wù)器（Server）：服務(wù)方，實現(xiàn)特定服務(wù)的進(jìn)程客戶(Client)：委托方，請求服務(wù)的進(jìn)程交互方式：請求-回答(request-reply)時間第三十九頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈40客戶和服務(wù)器舉例頭文件第四十頁，共五十八頁，2022年，8月28日2009-9-14計算機(jī)軟件所于戈41客戶和服務(wù)器舉例Server程序第四十一頁，共五十八頁，2022年，8月28日2009-9-14計算機(jī)軟件所于戈42客戶和服務(wù)器舉例Client程序第四十二頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈43消息格式舉例structmessage{longsource;/*發(fā)送者標(biāo)識*/longdest;/*接受者標(biāo)識*/longopcode;/*操作碼：讀、寫、創(chuàng)建、刪除*/longresult;/*返回結(jié)果代碼：成功、失敗*/longoffset;/*讀寫位置*/longcount;/*讀寫計數(shù)*/charfilename[MAX_PATH};/*文件名*/chardata[BUF_SIZE];/*數(shù)據(jù)區(qū)*/}第四十三頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈44服務(wù)器程序舉例voidmain(void){structmessagem1,m2;/*輸入、輸出的消息*/intr;/*返回的執(zhí)行結(jié)果*/while(1）{

receive(FILE_SERVER,&m1);/*等待客戶請求*/case(m1.opcode){/*執(zhí)行請求的操作*/caseREAD:r=do_read(&m1,&m2);break;:default:r=E_BAD_OPCODE;}m2.result=r;

send(m1.source,&m2);/*返回結(jié)果*/}}第四十四頁，共五十八頁，2022年，8月28日2009-9-14計算機(jī)軟件所于戈45客戶程序舉例intread(char*file,intposition,intnbytes,char*buf){structmessagem1;/*消息緩沖區(qū)*/m1.opcode=READ;/*設(shè)置參數(shù)*/m1.offset=position;/*讀位置*/m1.count=nbytes;/*讀長度*/

strcpy(&m1.filename,file)/*文件名*/send(FILE_SERVER,&m1);/*發(fā)送請求*/receive(CLIENT,&m1);/*等待服務(wù)器應(yīng)答*/

if(m1.result==OK)strcpy(buf,&m1.data);/*置緩沖區(qū)*/return(m1.result);/*返回結(jié)果*/}}第四十五頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈46客戶-服務(wù)器模型的實現(xiàn)客戶：用戶進(jìn)程（程序）服務(wù)器：能夠提供服務(wù)的進(jìn)程

12OS內(nèi)核客戶OS內(nèi)核服務(wù)器請求應(yīng)答第四十六頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈47通信協(xié)議簡化的請求/應(yīng)答協(xié)議無路由、無連接兩個基本操作send(dest,&mptr)receive(addr,&mptr)765請求/應(yīng)答432鏈路層1物理層第四十七頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈48尋址方式(Addressing)1、計算機(jī)+進(jìn)程計算機(jī)號/進(jìn)程號機(jī)號+進(jìn)程號機(jī)號+本地標(biāo)識號例：UNIX機(jī)器IP地址端口號(port)/*Socketaddress,internetstyle.*/structsockaddr_in{shortsin_family;/*AF_INET*/u_shortsin_port;structin_addrsin_addr;charsin_zero[8];};第四十八頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈49尋址方式(Addressing)2、全局進(jìn)程標(biāo)識符廣播定位進(jìn)程3、ASCII碼進(jìn)程名名字服務(wù)器第四十九頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈50

（1）阻塞發(fā)送原語同步式（2）非阻塞發(fā)送原語異步式內(nèi)核緩沖區(qū)copy（3）阻塞接受原語等待（4）非阻塞接受原語

Test輪詢接收（5）超時（timeout)時間時間阻塞與非阻塞型發(fā)送/接收第五十頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈51有緩沖與無緩沖型接收無緩沖區(qū)服務(wù)器等待客戶直接丟棄消息暫存“意外”消息有緩沖區(qū)郵箱（mailbox)：緩存所有的輸入消息“溢出”問題第五十一頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈52可靠的和非可靠的發(fā)送/接收非可靠的收發(fā)可能丟失消息由用戶負(fù)責(zé)確認(rèn)可靠的收發(fā)由系統(tǒng)確認(rèn)（acknowledge）內(nèi)核-內(nèi)核確認(rèn)應(yīng)答(reply)作為確認(rèn)客戶內(nèi)核確認(rèn)折衷方法服務(wù)器端設(shè)置計時器，超時后，發(fā)確認(rèn)消息第五十二頁，共五十八頁，2022年，8月28日2011-9-14計算機(jī)軟件所于戈53實現(xiàn)技術(shù)小結(jié)項目方案1方案2方案3尋址機(jī)器號稀疏的全局進(jìn)程號ASCII名（NS）阻塞？阻塞copy-to-kernel式非阻塞，中斷式非阻塞緩沖？無緩沖，丟棄意外的消息無緩沖，暫存意外的消息緩存，郵箱方式可