分布式期末復習題

概述題

1.分布式系統的定義？如何從硬體和軟體的角度理解分布式系統的內容？
??答：分布式系統是若干獨立計算機的集合，但對用戶來說是一個統一的系統，

2.分布式系統的設計的四個關鍵目標？
??答：資源可用性、分布式透明性、開放性、可伸縮性

3.事務處理具有的四個特性？
??答：1.原子性：事務在邏輯上是不可分割的操作單元；2.一致性：事務處理不會違反系統的不變性；3.隔離性：事務的執行不受其他事務的干擾，事務執行的中間結果對其他事務必須是透明的；4.持久性：對于任意已提交的事務，必須保證該事務對系統的改變不被丟失，即使系統出現故障，

體系結構

1.分布式系統的體系結構有哪幾種？簡要解釋，
??答：1.集中式；2.非集中式；3.混合式， 集中式體系結構有C/S架構、服務器兼職客戶端架構、多客戶端/單服務器架構、多客戶端/多服務器架構，C/S架構分為客戶端和服務端，服務端實作特定的存盤或計算的服務行程，客戶端遵循請求和回復的方式來向服務端請求服務；服務端兼職客戶端架構就是一臺服務器既會擔任客戶端的角色又會擔任服務端的角色；多客戶端/單服務器架構是指多臺客戶端向單臺服務器請求服務；多客戶端/多服務器架構是指服務會有多臺服務器來提供，根據服務方式又有，多臺服務器協作提供一個服務和多臺服務器各自提供相同的服務，集中式體系結構一般分為：用戶結構層、處理層和資料層，
??非集中式體系結構中沒有單一的劃分客戶端和服務器角色，每個節點作為客戶的同時又會向其他節點提供服務，比如P2P和超級對等體，P2P又可以分為結構化、非結構化和混合式，
??混合式體系結構是C/S架構和P2P架構的融合，有經常用于內容分發網路的邊界服務器系統，以及BitTorrent等，

行程

1.什么是行程？行程、程式的區別？
??答：行程是計算機程式關于某資料集合上的一次運行活動，是系統進行資源分配的最小單位，是作業系統結構的基礎，
??計算機程式是一組計算機能識別和執行的指令，運行于電子計算機上，是由某種程式設計語言撰寫的一串靜態代碼以及相應的資料，
??一個行程可以執行多個程式，一個程式可以產生多個行程，

2.為什么要引入執行緒，分布式系統中行程和執行緒的聯系與區別？
??答：對于分布式系統而言，使用行程就意味著有可能需要頻繁的發生背景關系切換，并且系統對于行程的創建、管理和維護要承擔較大的負擔，此時引入的執行緒可以有效解決這個問題，另外，執行緒提供了一種便捷的方式允許導致阻塞的系統呼叫而不阻塞該執行緒所屬的行程，這樣可以方便地將通信表示為維護多個邏輯連接的形式，
??一個執行緒只能屬于一個行程，而一個行程可以創建多個執行緒；執行緒本身不擁有資源，資源分配給行程，該行程所屬的所有執行緒共享該行程的所有資源；對于多處理器系統而言，一個行程只能在一個處理器上執行，但可以將一個行程中的多個執行緒分配到多個處理器上進行并行執行；執行緒是行程的一個可執行物體，是CPU調度和分派的基本單位；在創建、管理、撤銷方面，行程由于作為擁有資源的基本單位會導致其系統開銷遠遠大于執行緒的系統的開銷，不恰當地說，執行緒是輕量版的行程，

3.用戶級執行緒的主要優勢和缺陷？如何解決它的缺陷？
??答：用戶級執行緒是指不需要內核支持，而用戶程式可以自行創建的執行緒，不依賴于作業系統核心，用戶級執行緒有創建、管理、撤銷的開銷很小，而且可以通過簡單地幾條指令來實作背景關系切換，可以在不支持執行緒的作業系統中實作，允許每個行程定制自己調度演算法、管理靈活，執行緒能夠利用的表空間和堆疊空間比內核級執行緒多；但是對引起阻塞的系統呼叫的呼叫會阻塞該執行緒所屬的整個行程，也即，該行程所屬的其他執行緒也隨之阻塞，
??系統將多個輕型行程（LWP）分給行程，LWP可以通過系統呼叫來獲得內核提供的服務，而行程中的用戶級執行緒可通過復用來關聯到LWP，從而獲取內核服務，這樣當某個用戶級執行緒阻塞時，可切換到其他LWP，就不會導致整個行程被阻塞掛起，

4.有狀態服務器、無狀態服務器？對于狀態無關的服務器使之維持狀態的方法？
??答：有狀態服務器是一直保存客戶端的資訊直到顯式的洗掉；無狀態服務器是不保存其客戶對方狀態資訊，而且不將自身的狀態變化告知任何客戶；對于狀態無關服務器來說，運用軟狀態的資訊維護方式，這種情況下服務器會維護客戶狀態，但是僅僅維持一小段時間，

5.遷移代碼時，根據本地資源方式的不同，如何采用不同的做法？
??答：在分布式系統中，代碼遷移以行程遷移的形式展現，整個行程從一臺機器遷移到另一臺機器上去，遷移代碼時，需要在不影響行程對資源系結的條件下改變指向資源的參考，即資源對機器系結方式需要考慮如下幾點：（1）未連接資源：可以方便在機器之間移動，一般要遷移 的是與程式相關的資料檔案；（2）附著鏈接資源：可以進行復制移動，但是開銷比較大；（3）緊固鏈接資源：資源緊密地系結到特定的機器，無法進行移動，

通信

1.電子郵件系統采用什么樣的通信服務？持久通信、瞬時通信、異步通信、同步通信之間的組合方式，以及每種組合之間的區別？
??答：電子郵件系統采用持久通信服務，組合方式有：持久通信加異步通信、持久通信加同步通信、瞬時通信加異步通信、瞬時通信加同步通信，
??持久異步通信是指發送方發送訊息后就轉向處理其他事務，訊息存盤在本地主機緩沖區或者通信服務器的緩沖區中，當接收方上線運行后通過中間件獲取訊息，
??持久同步通信是指發送方發送訊息并等待， 直到接收方的accepted反饋后轉向處理其他事務，接收方將訊息存盤在接收主機上等待上線運行時received，
??瞬時異步通信是指當發送端應用程式提交訊息進行傳輸時，訊息暫時存盤在發送發送主機的本地緩沖區中，隨后發送者立即繼續執行其他程式，與此同時，通信系統將訊息繼續向接收方傳送，如果在訊息送達接收方時，接收方不在執行中，那么傳輸將失敗，
??瞬時同步通信有多種不同形式，最弱的是基于訊息接收的，即訊息送達接收主機并且存盤在那里的本地緩沖區后就解除發送者的阻塞，此時發送者會接收到一個確認訊息，轉向處理其他事務，基于角度的瞬時同步通信中，在訊息送達接收者進行進一步處理之前，發送者一直處于阻塞狀態，最強的是在發送者收到接收者發來的回應訊息之前一直阻塞，

2.為什么要引入遠程程序呼叫，遠程程序呼叫包含哪些步驟？
??答：許多分布式系統是基于行程間的顯示訊息交換的，然而，訊息的發送和接收程序是無法隱藏通信的存在，而通信的隱藏對于分布式系統中實作訪問透明性是極其重要的，
??遠程程序呼叫包含如下幾步：（1）客戶程序以正常的方式呼叫客戶存根；（2）客戶存根生成一個訊息，然后呼叫本地作業系統；（3）客戶端的操作將訊息發送給遠程呼叫系統；（4）客戶作業系統將訊息交給服務器存根；（5）服務器存根將引數提取出來，然后調用服務器；（6）服務器執行要求的操作，操作完成后回傳給服務器存根；（7）服務器存根將結果打包成一個訊息，然后呼叫本地作業系統；（8）服務器作業系統將含有結果的訊息發送給客戶端作業系統；（9）客戶端作業系統將訊息交給客戶存根；（10）客戶存根將結果從訊息中提取出來，回傳給呼叫它的客戶程序，

3.在RPC中，可能發生的5種失敗形式？如何處理？
??答：5種失敗形式有：一、客戶端無法定位服務器；二、客戶端到服務器的請求訊息丟失；三、服務器回傳給客戶端的訊息丟失；四、服務器再接收到訊息后阻塞；五、客戶端在發送完訊息后阻塞，
??失敗一：可以使用特殊符號作為回傳值來指明該失敗；讓無法回傳訊息的錯誤產生一個例外或者是信號，
??失敗二：內核在發送訊息時候設定一個計時器，若計時器時長內回傳訊息則正常處理；若訊息丟失則直接重傳；若重傳多次依舊失敗則服務器失聯，
??失敗三：內核在發送訊息時設定一個計時器，若超時還未接收到訊息則重傳；若操作不是冪等的，客戶的內核為請求分配序列號允許服務器的內核區分重傳和原始資料，
??失敗四：等服務器重啟后重新操作，或者立即放棄并報告錯誤，
??失敗五：（1）在客戶端存根發送RPC之前，生成一個日志條目后重新啟動，檢查日志并殺死孤兒；（2）將時間劃分為順序編號的時間段，當客戶端重新啟動時，它會廣播一條訊息，宣告新時間段的開始，當廣播到來時，所有遠程計算都被殺死，無需撰寫磁盤記錄；（3）每個RPC都有一個標準的時間長T來完成這項作業，如果它無法完成，則必須明確申請新的時長T，

4.什么是訊息佇列系統？為什么需要訊息佇列系統？使用佇列的松散耦合通信有哪幾種組合方式？
??答：應用程式通過在特定佇列種插入訊息來進行訊息通信的系統叫做訊息佇列系統，為了保證發送的訊息在接收方未處于運行狀態的時候也可以送達，接收方構造一個訊息佇列，發送方發送的訊息存盤在接收方之中，
??使用佇列的松散耦合通信的組合有：發送方和接收方在整個傳輸程序中都在運行、發送方在運行，接收方不運行，處于一種無法進行訊息交付的狀態，但是發送方可以發送訊息、發送方不運行，接收方運行，接收方可以讀出發送給它的訊息、發送方和接收方都不運行，但是訊息可以由系統存盤，

5.離散媒體、連續媒體的含義、區別是什么？
??答：連續媒體是指在連續媒體資料中，資料項之間存在緊密的時間聯系，是理解連續媒體資料的含義基礎，資料項之間的時間聯系對于正確理解資料含義并不重要，

6.資料流傳輸中，如何確保服務質量QoS？交錯傳輸的作業原理？
??答：在網路層面上，發送資料可以把要發送的資料包區分為哪一種型別，例如“快速轉發”，快速轉發要求資料包以絕對的優先級來轉發資料包，在接收端，假設當前資料包在網路傳輸上有不同的延時，接收方先將資料包存盤到緩沖區中，如果總是有足夠的資料進入緩沖區，就可以把穩定的資料傳給應用程式，否則會產生一定的延時，
??交錯傳輸是要把發送的資料包中的資料塊交錯排序，然后按順序傳輸資料塊，例如資料包1（塊1，塊4，塊7...）、資料包2（塊2，塊5，塊8）、資料包3（塊3，塊6，塊9），然后傳輸順序為塊1、塊2、塊3、塊4...

同步化

1.分布式系統為什么需要同步？可舉例說明，在分布式系統中實作同步，存在哪些困難？可從物理時鐘、傳輸延遲等角度分析，
??答：事務的處理具有一定的先后順序，分布式系統各種服務器事務的處理也是如此，然而由于物理特性的原因，分布式系統中各個機器的物理時間無法做到統一，假設現有一臺運行編譯(output.o)的機器和運行編輯(output.c)的機器，前者快后者兩個時間單位，若output.o的時間為A，緊接著output.c被修改，但是由于它所在的機器時鐘略慢，結果output.c的時間值被賦為A-1，那么編譯程式將不呼叫編譯器，最終的可執行二進制程式將包含由舊的源檔案和新的源檔案所產生的的混合目標檔案，從而可能導致程式崩潰，
??各個機器由于電子物理特性的緣故，導致各個機器的物理時間不統一，從而導致同步出現困難，另外在各個機器同步的程序中，需要進行傳輸各自的時間，而由于傳輸路徑的途徑不同，耗時不同，也會導致同步出現困難，

2.有哪些時鐘同步演算法？Berkeley演算法、均值同步演算法的具體步驟？
??答：有Cristian演算法、Berkeley演算法、平均值演算法和多個外部時間源，
??在Berkeley演算法中，服務器是主動地，它定期詢問每臺機器的時間，基于這些回答，讓他計算出一個平均時間，并告訴其他機器講它們的時鐘撥快、或者撥慢，直到某個指定的減少量到達為止，
??將時間劃分為固定長度的間隔，在每次間隔開始處，每臺機器根據自己的時鐘廣播當前時間（廣播不同事發送），在一臺機器發送了他的時間后，啟動本地定時器接受在某個間隔S里收到的其他廣播，所有廣播到達后，執行一個演算法從這些值中計算得到一個新的時間值，

3.邏輯時鐘與物理時鐘的區別？如何通過Lamport演算法校正不同行程的時鐘？
??答：物理時鐘是根據物理元器件來確定時間，邏輯時鐘是通過跟蹤各自事件執行順序的方式來實作操作處理上的先后順序，
??每個行程Pi都維持一個區域時鐘Ci，根據如下規則來調整這個時鐘：（1）對于發生在Pi內的任意兩個連續事件，Ci都會加1；（2）每當行程Pi發送一個訊息m時，該訊息都會收到一個時間戳ts(m)=Ci;（3）無論行程Pj什么時候收到訊息，Pj都會調整它的區域時鐘Cj至max{Cj, ts(m)}；然后在把m傳到應用程式之前執行步驟一，

4.Lamport邏輯時鐘與向量時鐘的聯系與區別？向量時鐘的作業原理（三個步驟）？
??答：lamport邏輯時鐘與向量時鐘都是邏輯時鐘，不過lamport不能捕捉因果關系，向量時鐘可以，
??向量時鐘的作業原理：（1）每個行程Pi都有一個向量VCi[1,...,n]，VCi[j]代表行程pi知道在行程pj發生的事件數；（2）當pi發送一個訊息m，VCi[i]就加1，并發送VCi與m一起作為向量時間戳vt(m)，結果：到達后，接收方會知道Pi的時間戳；（3）當一個行程Pj從pi接收到帶有向量時間戳ts(m)的訊息m時，①更新每個VCi[k]至max{vcj[k]， ts(m)[k]}，②VCj[j]加1.

5.如何使用向量時鐘，實作因果有序多播？
??
6.分布式系統中，為了訪問共享資源，有哪些互斥演算法？請從不同角度分析他們的區別？如進出訊息數，進入前延遲，存在問題等？
??

一致性和復制

1.以資料為中心的一致性模型，有哪些型別？每一種一致性模型的作業原理？

2.以客戶為中心的一致性模型，有哪些型別？每一種一致性模型的作業原理？
??答：有最終一致性、單調、單調寫、讀寫一致性

3.基于主備份的協議的復制寫協議，分別有哪些？每種協議的基本原理？
??答：主備份寫協議有本地寫協議和遠程寫協議

容錯性

1.分布式系統中的故障、錯誤、失敗三種的定義、聯系與區別？
?? 答：故障是指造成錯誤的原因，錯誤是指系統狀態的一部分，失敗是指系統無法完成指定任務或目標，故障會產生錯誤，錯誤會導致失敗，

2.拜占庭協定問題、拜占庭將軍問題的定義、原理、程序、結論？
??答：拜占庭協定問題是在地理上隔開的n個藍軍將軍想協力攻打紅軍，但是n個藍軍將軍里有m個叛徒，那么這些忠誠的將軍如何才能達到一致的協定？
??拜占庭將軍問題的含義是存在訊息丟失的不可靠資訊途徑的前提下，試圖通過訊息傳遞的方式，使得所有資訊保持一致性是不可能的，
??假定通信信道良好的情況下，必須要實作下面兩個充分條件：IC1. 所有忠誠的將軍都遵守同一命令，即一致性；IC2. 若發令者是忠誠的，那么每一個忠誠的將軍都遵守它發出的命令，即正確性，
??通過口頭協定可以來一定程度上解決拜占庭將軍問題，即若叛徒數少于將軍數的1/3，問題可解，
??口頭協議演算法程序：
??OM(0)演算法：(1) 發令將軍將他的命令發送給其他將軍；(2) 其他n-1個將軍采用從發令將軍發來的命令，如果沒有收到命令，則默認為撤退命令，
??OM(m)演算法：(1) 發令將軍將他的命令發送給其他將軍；(2) 對于其他n-1個將軍從發令將軍i那收到命令Vi，如果沒有收到，則默認為撤退，i在OM(m-1)中作為發令者將自己得到的命令發送給另外n-2個將軍；(3) 對于每個j，和每個k（k≠j），在第二步，j獲得從k那里發送過來的命令Vk，如果沒有收到該命令，則默認為撤退命令，最后j使用majority(v1, ..., vn-1)得到最終命令，
??majority()函式代表了大多數將軍的命令，若不存在則默認為撤退命令，

3.為什么需要兩階段提交，兩階段提交的原理和程序？
??答：在分布式系統中，為了保證資料的高可用，通常系統會將資料保留多個副本(replica)，這些副本會放置在不同的物理的機器上，為了對用戶提供正確的增\刪\改\差等語意，系統需要保證這些放置在不同物理機器上的副本是一致的，
??第一階段：a. coordinator發送投票請求給參與者；b. 當參與者受到投票請求時，它將投票提交或者投票中止發給coordinator，如果它發送投票中止，那么它將中止其本地計算，
??第二階段：a.coordinator收集所有的投票，如果都是投票提交，它就會發送一個全域提交給所有的參與者，否則就發送全域終止；b. 每個參與者等待全域提交或者全域終止，并進行相應的處理，

其他

1.網路檔案系統的基本思想，UNIX系統中的基本NFS體系結構和作業程序？有哪些型別的分布式檔案系統？
??答：網路檔案系統的基本思想是每個檔案服務器都提供一個標準化的視圖，即并不關心本地檔案系統如何實作，每個NFS服務器都支持相同的模型，NFS帶有一個通信協議，從而使得允許異構行程訪問網路上的檔案，
??本地客戶端呼叫VFS介面，VFS根據訪問的需求，訪問本地檔案系統，或者進行遠程服務器檔案訪問，如果是進行遠程服務器訪問，VFS便會將訪問的請求傳遞給一個NFS客戶端，然后客戶端通過RPC訪問遠程服務器的NFS，客戶端的訪問訊息到達服務器后會與客戶端與相似的方式傳遞服務器的VFS，然后由VFS訪問本地的檔案系統，訪問對應的檔案，
??分布式檔案系統有客戶-服務器結構的檔案系統、基于集群的分布式檔案系統和對稱式結構的檔案系統，

2.Coda檔案系統中的客戶端快取、服務器端復制？
??答：客戶快取：當一個客戶端打開一個檔案f時，f的副本會被傳送到客戶端，服務器會記錄下客戶端具有f的副本，在一個檔案的起始狀態，如果客戶端A以寫操作的方式打開某個檔案，當另一個客戶B也想打開檔案F時，B會失敗，在一個檔案的起始狀態，如果其先被客戶端A以讀的方式打開，隨后客戶端B試圖以寫的方式打開，那么B是可以打開，并且可以做修改的，此時A本地的副本是過時的，但是不影響A繼續讀取他本地的副本，
??服務器端復制要確保并發更新被檢測到：每個客戶端都有可訪問卷存盤組，是實際卷存盤組的一個子集；版本向量CVVi(f)[j]=k=>服務器Si知道服務器Sj看到了f的版本k，

3.介紹一個典型的基于web的分布式系統，如www？

專題報告

1.大資料處理系統簡介

2.Distributed Map/Reduce