【正文】 有要么全無 的特性簡化了編程人員的工作。在硬盤和在線數(shù)據(jù)庫出現(xiàn)之前，所有的文件都保存在 磁帶 上。l 計算機從兩盤磁帶上讀取數(shù)據(jù)，并生成新的主庫存磁帶，如圖所示：陳香蘭 21分布式系統(tǒng)同步（續(xù)）l 這種設計的最大優(yōu)點（盡管與它生活在一起的人們并沒有意識到）在于l 對任何原因引起的運行錯誤，所有的磁帶都可以倒卷（rewound），其工作可以毫無損失地重新開始。陳香蘭 22分布式系統(tǒng)同步（續(xù)）在線更新數(shù)據(jù)庫模型 銀行 在線更新數(shù)據(jù)庫 :l 客戶通過帶有調制解調器的 PC機連接到銀行，想將一個賬戶下的錢取出再存入另一賬戶。錢就消失在了未知的空間中。l 要么兩個都執(zhí)行，要么任何一個都不執(zhí)行。我們真正需要的是像使用磁帶時那樣的對數(shù)據(jù)庫倒卷的方法。陳香蘭 24分布式系統(tǒng)同步（續(xù)） 事務模型 事務的屬性和模型：l 假設 1： 系統(tǒng)由一些相互獨立的進程組成，每個進程都會隨機出錯。陳香蘭 25分布式系統(tǒng)同步（續(xù)）假設 3： 穩(wěn)定存儲器l 存儲器有三種分類。l 第二種是磁盤存儲器，它不受 CPU錯的影響，但磁頭錯會導致信息丟失。它不受其他任何錯誤的影響。l 在一個郵件系統(tǒng)中，可能有發(fā)送、接收以及轉發(fā)郵件等原語。l 在一個事務中，也允許使用 普通語句 、 過程調用 等等。l 它們之間的操作構成了 事務體 。l 這些操作也可能是 系統(tǒng)調用，庫過程 ，或者是某種語言中用括號括起來的語句，這取決于應用的需要。由于沒有直達火車，只能買聯(lián)票。 下面通過 3個操作預定了這 3條獨立的路線的座票。那么 事務 就會因此而 中止 ， 前兩個預定的結果 也將被 取消 —— 售票系統(tǒng)的數(shù)據(jù)庫恢復到了事務開始前的狀態(tài)，就像什么也沒有發(fā)生一樣。l 這幾個屬性通常按其字母簡稱為 ACID。l 這個特性 確保了 每個事務 要么全部發(fā)生，要么全部不發(fā)生 。l 當一個事務處在處理過程中，其他進程（無論是否與事務有關）都不能看到任何 中間狀態(tài) 。l 這意味著 系統(tǒng)擁有某種必須保持的不變性 ，一旦在事務開始之前有這樣的性質，則事務結束后該性質還應該存在。在任何內部轉帳之后，銀行的資金賬目應與轉帳前保持一致，但是在 事務執(zhí)行的短暫時刻內，這種不變性會改變 。陳香蘭 34分布式系統(tǒng)同步（續(xù)）3）事務的孤立性l 第三個特性說明事務是孤立的。陳香蘭 35分布式系統(tǒng)同步（續(xù)）4）事務的持久性l 第四個特性說明事務是持久的。提交之后發(fā)生的任何錯誤都不可能將結果取消或導致結果丟失。l 頂層事務可以在不同的處理機上創(chuàng)建并運行子事務，以提高性能簡化編程。l 子事務會引起持久性問題。l 經(jīng)過更進一步的計算，父事務被中止，并將系統(tǒng)恢復到了頂層事務開始前的狀態(tài)。l 因此，持久性只是對頂層事務 而言。l 在分布式系統(tǒng)中，提交操作 可能需要不同機器上的多個進程的協(xié)作 ，這些進程中的每一個都有一些 被事務改動過的變量、文件、數(shù)據(jù)庫 或者其他對象。一般來說這個進程就是執(zhí)行事務的進程。陳香蘭 39分布式系統(tǒng)同步（續(xù)）l 當一個下屬收到消息后，它先進行檢查以確認是否為提交作好了準備，然后將它是否準備提交的決定發(fā)回給協(xié)調者。l 如果所有的進程都準備提交，那么事務就可以提交了。l 無論是提交還是終止，協(xié)調者都要寫一條日志記錄并給每個下屬發(fā)送一條消息以便將決定通知它們。陳香蘭 40分布式系統(tǒng)同步（續(xù)）崩潰和恢復l 由于在穩(wěn)定存儲器上寫的日志，所以，這個協(xié)議在（多個）崩潰面前仍然是可以恢復的。l 如果在響應第一條消息之前某個下屬崩潰了，那么協(xié)調者將會給它不斷地發(fā)送消息。陳香蘭 41分布式系統(tǒng)同步（續(xù)） 并發(fā)控制l 當多個事務在不同的進程（在不同的處理機上）中同時執(zhí)行時，需要一些機制以保證它們互不干擾。l 本節(jié)將研究三個不同的算法1）加鎖法2）樂觀并發(fā)控制3）時間戳陳香蘭 42分布式系統(tǒng)同步（續(xù)）加鎖法l 最古老而且使用最廣泛的并發(fā)控制算法是加鎖法。l 由于正常的進程在一個文件被加鎖前不會試圖去存取它，因此對文件加鎖可以防止其他進程對文件的訪問，這就保證了一個事務的生存期內文件不會被改變。陳香蘭 43分布式系統(tǒng)同步（續(xù)）加鎖法實現(xiàn)1. 可以使用一個 集中式加鎖管理程序 來實現(xiàn)2. 可以在每臺機器上有一個 本地加鎖管理程序 來管理本地文件。陳香蘭 44分布式系統(tǒng)同步（續(xù)）讀鎖和寫鎖l 上述方案的限制過于嚴格，可以通過區(qū)分讀鎖和寫鎖來加以改進。l 讀鎖用來確保文件不會被改寫（也即排斥所有的寫入者），但不禁止其他讀取文件的事務。l 所以說 讀鎖是可以共享的，而寫鎖必須是互斥的 。但在實際中，l 可能是更小一些的單位，比如 記錄 或 頁面 ，l 也可能是大一些，比如 整個數(shù)據(jù)庫 。l 粒度越細，加鎖就可以越精確，也就能實現(xiàn)更大的并發(fā)度 （例如，并不因為某個進程正在使用文件的開頭就阻塞另一個試圖使用該文件末尾的進程）。陳香蘭 46分布式系統(tǒng)同步（續(xù)）兩階段加鎖法l 在需要或不再需要鎖時去請求或釋放鎖可能會導致 不一致和死鎖 。l 在兩階段加鎖法中， 進程在增長階段先請求它需要的所有鎖，然后在收縮階段釋放它們 。這也是兩階段加鎖法廣泛使用的原因。l 若兩個進程都試圖以相反的順序請求同一對鎖，那么就會發(fā)生死鎖。2）通過對一張描述哪個進程可以擁有哪個鎖，它還想請求哪個鎖的圖進行死鎖掃描，以便檢查是否有環(huán)路出現(xiàn)，以防止死鎖。陳香蘭 49分布式系統(tǒng)同步（續(xù)）樂觀并發(fā)控制l 處理同時運行多個事務的第二種方法是樂觀并發(fā)控制法（ Kung and Robinson， 1981）。如果有問題出現(xiàn)，那么以后再考慮吧 。陳香蘭 50分布式系統(tǒng)同步（續(xù)）樂觀并發(fā)控制 — 沖突的處理l 盡管沖突會非常少，但存在的可能性還是有的，因此還需要一些處理沖突的方法。l 在提交時刻，檢測其他的事務以判斷在本事務開始后它的文件是否被其他事務修改過。l 如果沒有修改過，那么本事務就可以提交了。l 每個事務都獨立地修改各自的文件，不會涉及其他的事務。l 樂觀并發(fā)控制算法的優(yōu)點 :l 避免了死鎖，而且允許最大限度的并行度（進程不需要去等待一個鎖）l 缺點 :l 有時可能會失效，這時，所有事務都必須退回重新運行l(wèi) 在重負載的情況下，算法失效的可能性將會直線上升。陳香蘭 53分布式系統(tǒng)同步（續(xù)）時間戳（ cont’d）l 若事務都很短小且在時間間隔上比較大，那么一般來說當一個進程試圖訪問某個文件時，該文件的讀寫時間戳將早于當前事務的時間戳。陳香蘭 54分布式系統(tǒng)同步（續(xù)）時間戳（ cont’d）l 當次序不正確的時候，就表明一個晚于當前事務開始的事務試圖插入、訪問文件并提交。需要中止陳香蘭 55分布式系統(tǒng)同步（續(xù)）時間戳（ cont’d）l 在某種意義上，這種方案同 Kung和 Robinson的方案一樣，也是樂觀的，盡管兩者的細節(jié)完全不同。l 在時間戳方法中，我們不介意并發(fā)事務是否使用同一個文件，只要郵戳小的事務總是先執(zhí)行就可以了。l 當一個事務碰到了更晚的時間戳時，就要中止，l 加鎖法在相同的情況下要么等待要么立即執(zhí)行。l 總而言之l 事務具備許多優(yōu)點，因此對構造可靠的分布式系統(tǒng)而言它就成為了一種比較好的技術。陳香蘭 57分布式系統(tǒng)同步（續(xù)） 分布式系統(tǒng)中的死鎖l 分布式系統(tǒng)中的死鎖類似單處理機系統(tǒng)中的死鎖，只是情況更壞。l 在分布式數(shù)據(jù)庫系統(tǒng)中，死鎖的問題可能會相當嚴重。 例如，進程 A試圖發(fā)送消息給進程 B，進程 B給進程C發(fā)送消息，而 C又試圖給 A發(fā)送消息，那么就會發(fā)生死鎖。l 當多個進程為了互斥訪問 IO設備、文件、鎖或其他資源時就會發(fā)生資源死