【正文】 塊可以通過(guò)另一臺(tái)驅(qū)動(dòng)器上的相應(yīng)塊恢復(fù)。 108 一、穩(wěn)定存儲(chǔ)器 （續(xù)） ? 實(shí)現(xiàn)穩(wěn)定存儲(chǔ)器的 價(jià)值： ? 它很適合于需要高度容錯(cuò)的應(yīng)用，例如原子事務(wù)。 ? 當(dāng)數(shù)據(jù)寫(xiě)入穩(wěn)定存儲(chǔ)器并讀出以檢驗(yàn)它們是否正確寫(xiě)入時(shí)，它們相繼丟失的機(jī)會(huì)非常小。 109 二、事務(wù)原語(yǔ) ? 使用事務(wù)編程需要由 操作系統(tǒng) 提供或者由 語(yǔ)言運(yùn)行系統(tǒng) 提供特殊 原語(yǔ) ，例如： ? BEGIN_TRANSACTION：標(biāo)記一個(gè)事務(wù)的開(kāi)始。 ? END_ TRANSACTION：結(jié)束事務(wù)并設(shè)法提交。 ? ABORT_ TRANSACTION：取消事務(wù)；恢復(fù)舊值。 ? READ：從一個(gè)文件（或其它對(duì)象）讀取數(shù)據(jù)。 ? WRITE：將數(shù)據(jù)寫(xiě)入一個(gè)文件（或其它對(duì)象）。 110 二、事務(wù)原語(yǔ) （續(xù)） ? 更精確的原語(yǔ) 列表取決于事務(wù)中正在使用的對(duì)象類(lèi)型。 ? 在一個(gè)郵件系統(tǒng)中，可能有發(fā)送、接收以及轉(zhuǎn)發(fā)郵件等原語(yǔ)。 ? 而在一個(gè)帳目系統(tǒng)中可能會(huì)有很大的不同。 ? 讀取和寫(xiě)入?yún)s是 典型的應(yīng)用 。 ? 在一個(gè)事務(wù)中，也允許使用普通語(yǔ)句、過(guò)程調(diào)用等。 111 二、事務(wù)原語(yǔ) （續(xù)） —— 事務(wù)體 ? BEGIN_TRANSACTION 和 END_ TRANSACTION用來(lái)限定事務(wù)的范圍。 ? 介于它們之間的操作構(gòu)成了 事務(wù)體 。 ? 這些操作要么全部執(zhí)行，要么一個(gè)也不執(zhí)行 。 ? 這些操作可能是系統(tǒng)調(diào)用，庫(kù)過(guò)程，或者是某種語(yǔ)言中用括號(hào)括起來(lái)的語(yǔ)句，這取決于實(shí)現(xiàn)的需要。 112 二、事務(wù)原語(yǔ) 例子 ? 考慮到保定火車(chē)站買(mǎi)一張從保定到汕頭的火車(chē)。由于沒(méi)有直達(dá)火車(chē)，只能買(mǎi)聯(lián)票。保定 ?石家莊；石家莊 ?廣州；廣州 ?汕頭。 下面通過(guò) 3個(gè)操作預(yù)定了這 3條獨(dú)立的路線的座票。 BEGIN_TRANSACTION reserve 保定 石家莊 reserve 石家莊 廣州 reserve 廣州 汕頭 END_TRANSACTION 113 二、事務(wù)原語(yǔ) 例子（續(xù)） ? 現(xiàn)在假設(shè)前兩條路線已經(jīng)預(yù)定成功，但是第三條已經(jīng)定滿了。那么事務(wù)就會(huì)因此而中止， 前兩個(gè)預(yù)定的結(jié)果也將被取消 —— 售票系統(tǒng)的數(shù)據(jù)庫(kù)恢復(fù)到了事務(wù)開(kāi)始前的狀態(tài)，就像什么也沒(méi)有發(fā)生一樣。 BEGIN_TRANSACTION reserve 保定 石家莊 reserve 石家莊 廣州 廣州 汕頭 full →ABORT _ TRANSACTION END_TRANSACTION 114 三、事務(wù)的特性 ? 事務(wù)有四個(gè)重要的特性，它們是： ? 原子性 (Atomic)：對(duì)外部世界來(lái)說(shuō)，事務(wù)的發(fā)生是不可分割的。 ? 一致性 (Consistent)：事務(wù)不會(huì)破壞系統(tǒng)的恒定。 ? 獨(dú)立性 (Isolated)：并發(fā)的事務(wù)不會(huì)互相干擾。 ? 持久性 (Durable)：一旦一個(gè)事務(wù)提交，改變就是永遠(yuǎn)存在的。 ? 這幾個(gè)屬性通常按其首字母簡(jiǎn)稱為 ACID。 115 原子性 ? 所有事務(wù)具有的第一個(gè)特性是 原子性 。 ? 這個(gè)特性 確保了每個(gè)事務(wù)要么全部發(fā)生，要么全部不發(fā)生 。 ? 如果發(fā)生，就是不可分割的， 瞬間 的操作。 ? 當(dāng)一個(gè)事務(wù)處在處理過(guò)程中時(shí)，其它進(jìn)程（無(wú)論是否與事務(wù)有關(guān)）都 不能看到任何中間狀態(tài) 。 116 原子性 — 例 ? 假設(shè)某個(gè)事務(wù)要在一個(gè) 10字節(jié)的文件末尾添加數(shù)據(jù)。 ? 如果在事務(wù)處理過(guò)程中其它進(jìn)程讀取了這個(gè)文件，那么無(wú)論該事務(wù)已添加了多少內(nèi)容，那些進(jìn)程看到的只能是 10個(gè)字節(jié)。 ? 如果事務(wù)成功結(jié)束，這時(shí)文件在結(jié)束的 瞬時(shí)增長(zhǎng)到 了新的大小，無(wú)論有多少個(gè)操作存在，都不會(huì)有中間狀態(tài)。 117 一致性 ? 第二個(gè)特性說(shuō)明事務(wù)是 一致 的，這 意味著如果系統(tǒng)擁有某種必須經(jīng)常保持的不變性，那么一旦在事務(wù)開(kāi)始之前保持有這樣的性質(zhì)，則事務(wù)結(jié)束后該性質(zhì)就還應(yīng)該存在 。 ? 例如在一個(gè)銀行系統(tǒng)中，最關(guān)鍵的不變性是資金守恒規(guī)則。 ? 在任何內(nèi)部轉(zhuǎn)帳之后，銀行的資金帳目應(yīng)與轉(zhuǎn)帳前保持一致，但是在事務(wù)執(zhí)行的短暫時(shí)刻內(nèi)，這種不變性會(huì)受到損害。然而事務(wù)結(jié)束之后，這種損害就沒(méi)有了。 118 獨(dú)立性 ? 第三個(gè)特性說(shuō)明事務(wù)是 獨(dú)立的或連續(xù)的 。 ? 這意味著如果兩個(gè)或兩個(gè)以上的事務(wù)在同時(shí)運(yùn)行，那么對(duì)它們自己和其它進(jìn)程來(lái)說(shuō)，最終結(jié)果看起來(lái)就象是所有的事務(wù)是 按某種次序 （ 依賴于系統(tǒng) ）順序運(yùn)行的。 119 獨(dú)立性 — 例 ? 下面三個(gè)事務(wù)被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行。 ? 如果它們順序執(zhí)行，那么 X的最終結(jié)果應(yīng)該是1， 2或 3，取決于哪一個(gè)事務(wù)最后運(yùn)行（ X可以是一個(gè)共享變量，一個(gè)文件或其他對(duì)象）。 120 獨(dú)立性 — 例 ? 在 d中我們看到了稱之為 調(diào)度表 的不同次序，其中事務(wù)可以是交錯(cuò)的。 ? 調(diào)度 1是真正串行的，即事務(wù)嚴(yán)格按順序來(lái)運(yùn)行，因此它滿足連續(xù)性的定義。 ? 調(diào)度 2不是串行的，但是它也是合法的，因?yàn)樗祷氐?X值與嚴(yán)格串行返回的值一致。 ? 第三個(gè)調(diào)度是非法的，因?yàn)樗鼘?X的值置成了 5，這是順序執(zhí)行所不可能產(chǎn)生的。 121 獨(dú)立性（續(xù)） ? 為保證獨(dú)立的操作正確交替執(zhí)行是系統(tǒng)的責(zé)任 。 ? 通過(guò)給予系統(tǒng)按照自己需要選擇操作執(zhí)行順序的自由 —— 假設(shè)它得到的答案是正確的 —— 我們消除了程序員自己進(jìn)行互斥處理的需要，因此簡(jiǎn)化了編程。 122 持久性 ? 第四個(gè)特性說(shuō)明事務(wù)是 持久 的。 ? 這是指這樣一個(gè)事實(shí)，即一旦一個(gè)事務(wù)提交，無(wú)論發(fā)生什么，這個(gè)事務(wù)都會(huì)向前進(jìn)行，結(jié)果不會(huì)再變了。 提交之后發(fā)生的任何錯(cuò)誤都不可能使結(jié)果取消或丟失。 123 四、嵌套事務(wù) ? 事務(wù)可以包含子事務(wù)，這通常稱作 嵌套事務(wù) 。 ? 頂層事務(wù)可以在不同的處理機(jī)上創(chuàng)建并行運(yùn)行的子事務(wù)，以提高性能、簡(jiǎn)化編程。 ? 這些子事務(wù)中的任何一個(gè)都可以執(zhí)行一個(gè)或多個(gè)子事務(wù)，或者創(chuàng)建自己的子事務(wù)。 124 四、嵌套事務(wù) （續(xù)） ? 子事務(wù)引起的問(wèn)題： ? 假設(shè)一個(gè)事務(wù)啟動(dòng)了幾個(gè)并行的子事務(wù)，其中一個(gè)已經(jīng)提交，其操作結(jié)果在父事務(wù)中已經(jīng)生效。 ? 經(jīng)過(guò)更進(jìn)一步的計(jì)算，父事務(wù)被終止，并將系統(tǒng)恢復(fù)到了頂層事務(wù)開(kāi)始前的狀態(tài)。 ? 結(jié)果，已經(jīng)提交了的子事務(wù)的結(jié)果也必須被恢復(fù)。于是 上面提到的的持久性只是對(duì)頂層事務(wù)而言 。 ? 持久性：提交之后發(fā)生的任何錯(cuò)誤都不可能使結(jié)果取消或丟失。 125 四、嵌套事務(wù) （續(xù)） ? 由于事務(wù)可以嵌套任意多層，因此需要管理措施以使其一切正常。但 語(yǔ)義卻是清楚 的。 ? 當(dāng)任何事務(wù)或子事務(wù)開(kāi)始的時(shí)候，在概念上給予它一個(gè)整個(gè)系統(tǒng)全部對(duì)象的私有拷貝，可以按照其意愿進(jìn)行操作。 ? 如果事務(wù)被終止，那么它的私有空間就會(huì)消失，就象事務(wù)從來(lái)都沒(méi)有存在過(guò)一樣。 ? 如果事務(wù)提交了，那么它的私有空間就會(huì)取代父輩的空間。 ? 因此如果一個(gè)子事務(wù)提交后又開(kāi)始了一個(gè)新的子事務(wù)，那么它就可以看到第一個(gè)子事務(wù)的結(jié)果了。 126 ? 如果每個(gè)進(jìn)程執(zhí)行一個(gè)事務(wù)僅僅只是更新它自己使用的對(duì)象（文件、數(shù)據(jù)庫(kù)記錄等），那么事務(wù)就不會(huì)是原子的，而且事務(wù)異常終止時(shí)它所作的更改也不會(huì)神奇的消失。 ? 此外，運(yùn)行多個(gè)事務(wù)時(shí)也不會(huì)是串行的。 ? 顯然，需要其它的實(shí)現(xiàn)方法。經(jīng)常使用的有兩種方法： ? 私有工作空間 ? 寫(xiě)前日志 127 一、私有工作空間 ? 第一種實(shí)現(xiàn)方法： 在進(jìn)程開(kāi)始一個(gè)事務(wù)的時(shí)刻給它分配一個(gè)私有工空間 。 ? 從概念上講，當(dāng)一個(gè)進(jìn)程開(kāi)始一個(gè)事務(wù)時(shí)，會(huì)給它一個(gè)包含了所有需要訪問(wèn)的文件（和其它對(duì)象）的私有工作空間 。 ? 在事務(wù)提交或終止前所有的讀寫(xiě)操作都是在私有工空間而不是在通常所說(shuō)的真正的文件系統(tǒng)中進(jìn)行的。 ? 問(wèn)題： ? 把所有內(nèi)容都拷貝到一個(gè)私有工空間，其 代價(jià)是難以承受 的，但存在一些優(yōu)化使得該方法更可行些。 128 一、私有工作空間 （續(xù)） ? 第一個(gè)優(yōu)化 基于這樣的一種認(rèn)識(shí)， ? 當(dāng)一個(gè)進(jìn)程讀取文件而不作修改時(shí)，就不需要私有拷貝了。 ? 該進(jìn)程可以直接讀取真正的文件（除非當(dāng)事務(wù)開(kāi)始后文件已被改動(dòng)）。 129 一、私有工作空間 （續(xù)） ? 當(dāng)某個(gè)進(jìn)程開(kāi)始一個(gè)事務(wù)的時(shí)候，只要?jiǎng)?chuàng)建一私有工作空間，該私有工空間只包含一個(gè)指向父輩工作區(qū)的指針就足夠了。 ? 當(dāng)事務(wù)處于最頂層的時(shí)候，它的工作區(qū)就是真正的文件系統(tǒng)。 ? 當(dāng)一個(gè)進(jìn)程打開(kāi)文件進(jìn)行讀取的時(shí)候，指針向回指直到可以在父輩（或更老的祖先）工作區(qū)中定位文件為止。 ? 當(dāng)打開(kāi)一個(gè)文件進(jìn)行 寫(xiě)入 時(shí)，它可用同讀取時(shí)一樣的方法進(jìn)行定位，不過(guò)首先要將其復(fù)制到私有工作空間。 130 一、私有工作空間 （續(xù)） ? 第二個(gè)優(yōu)化方法 大大減少了拷貝工作。 ? 該方法并不是將全部文件都拷入私有工空間，而只將其索引拷入。索引是一個(gè)與判斷文件所在磁盤(pán)塊位置有關(guān)的數(shù)據(jù)塊。 131 一、私有工作空間 （續(xù)） ? 通過(guò)私有索引，文件可以按通常的方式讀取。 ? 因?yàn)樗饕邪形募_(kāi)始幾個(gè)塊的磁盤(pán)地址。 132 一、私有工作空間 （續(xù)） ? 當(dāng)一個(gè)文件塊第一次被修改時(shí)，將會(huì)生成該塊的拷貝，其地址也將被插入索引中，然后就可以在不影響原始?jí)K的情況下更新這個(gè)塊。 ? 添加塊也是用這個(gè)方法解決的。新塊有時(shí)也稱作 影象塊 (shadow block)。 ? 如圖所示，運(yùn)行事務(wù)的進(jìn)程看到了被修改的文件，但是其它進(jìn)程看到的仍是原來(lái)的文件。 133 一、私有工作空間 （續(xù)） ? 在一個(gè)更復(fù)雜的事務(wù)中，私有工空間可能包含了大量的文件而不僅僅是一個(gè)。 ? 如果事務(wù) 異常終止 ，那么私有工空間就會(huì)被刪除，它所指向的所有私有塊也將被釋放回自由列表中。 ? 如果事務(wù) 成功結(jié)束 ，那么私有索引將會(huì)被自動(dòng)移到父輩的工作區(qū)中，如圖所示。不需要的塊將它放回自由列表中。 134 二、寫(xiě)前日志 ? 另一個(gè)實(shí)現(xiàn)事務(wù)的常用方法是 寫(xiě)前日志(Writehead log)。有時(shí)也稱為計(jì)劃列表、意向表 (intentions list)。 ? 使用這種方法時(shí)， 文件會(huì)真正被修改 。但是在改動(dòng)任何塊之前，將一條記錄寫(xiě)入 穩(wěn)定存儲(chǔ)器 的寫(xiě)前日志中，以判斷是哪一個(gè)事務(wù)在進(jìn)行修改操作，哪一個(gè)文件的哪一塊被改動(dòng)了，舊值與新值分別是什么。 ? 只有當(dāng)日志被成功的寫(xiě)入之后才可以進(jìn)行文件的修改。 ? 先寫(xiě)寫(xiě)前日志再修改！ 135 二、寫(xiě)前日志 — 例子 ? 以下是一個(gè)日志如何工作的例子。 ? 圖 (a)中有一個(gè)使用兩個(gè)初值均是 0的共享變量（或其它對(duì)象） x， y的簡(jiǎn)單事務(wù)。 ? 對(duì)事務(wù)中三條語(yǔ)句中的每一條，在執(zhí)行之前都要寫(xiě)入一條日志，以記錄新值和舊值，它們用斜杠來(lái)區(qū)分。 136 二、寫(xiě)前日志 — 例子（續(xù)） ? 如果事務(wù) 執(zhí)行成功并被提交 ，那么它的提交記錄將被寫(xiě)入日志，但數(shù)據(jù)結(jié)構(gòu)不需要變動(dòng)，因?yàn)樗鼈円呀?jīng)被更新了。 ? 如果 事務(wù)異常終止 ，那么可用日志來(lái)備份初始狀態(tài)。 137 二、寫(xiě)前日志 — 例子（續(xù)） —— 日志用來(lái)進(jìn)行系統(tǒng)崩潰后的恢復(fù) ? 假設(shè)執(zhí)行事務(wù)的進(jìn)程在寫(xiě)入圖 (d)中的最后一條記錄之后及改變 x之前崩潰。 ? 在機(jī)器重啟動(dòng)后，日志可以用來(lái)檢查在系統(tǒng)崩時(shí)刻是否有事務(wù)正在處理中。 ? 當(dāng)讀到最后一條記錄時(shí)顯示 x的當(dāng)前值是 1，那么說(shuō)明崩潰顯然是在更新之前發(fā)生的，所以 x的值應(yīng)被改為 4。 ? 相反，如果在系統(tǒng)恢復(fù)時(shí) x的值是 4，那也同樣清楚的說(shuō)明崩潰是在更新后發(fā)生的，因此不需要進(jìn)行任何變動(dòng)。 138 二、寫(xiě)前日志 — 例子（續(xù)） ? 從日志的末尾開(kāi)始向回讀取每條記錄，再將記錄中描述的改動(dòng)復(fù)原。這個(gè)操作稱之為 滾回 。 ? 使用日志使得向前（處理事務(wù)）和向后（撤消事務(wù)）成為了可能。 139 三、兩階段提交協(xié)議 ? 事務(wù)提交操作必須是原子性的，即 瞬時(shí)的和不可再分的。 ? 在分布式系統(tǒng)中，提交操作可能需要 不同機(jī)器上的多個(gè)進(jìn)程 的協(xié)作，這些進(jìn)程中的每一個(gè)都有一些被事務(wù)改動(dòng)過(guò)的變量、文件、數(shù)據(jù)庫(kù)或者其它對(duì)象。 ? 本節(jié)將研究一個(gè)在分布式系統(tǒng)中實(shí)現(xiàn)原子性提交的協(xié)議。 ? 該協(xié)議稱為 兩階段提交協(xié)議 （ twophase mit protocol）（ Gray,1978）。盡管它不是此類(lèi)協(xié)議中唯一的一個(gè)，但它卻是使用最廣泛的一個(gè) 。 140 三、兩階段提交協(xié)議（續(xù)） ? 基本思想：進(jìn)程中的某一個(gè)會(huì)起到 協(xié)調(diào)者 的作用。一般來(lái)說(shuō)這個(gè)進(jìn)程就是執(zhí)行事務(wù)的進(jìn)程。①提交協(xié)議開(kāi)始時(shí)協(xié)調(diào)者先寫(xiě)入一條日志條目以表明它要開(kāi)始提交協(xié)議。 141 三、兩階段提交協(xié)議（續(xù)） ② 然后它給每個(gè)相關(guān)進(jìn)程（下屬