1、Silberschatz, Korth and Sudarshan19.1Database System Concepts1n同質與異質數(shù)據(jù)庫n分布式數(shù)據(jù)存儲n分布式事務n提交協(xié)議n分布式數(shù)據(jù)庫中的并發(fā)控制n可用性n分布式查詢處理n異質分布式數(shù)據(jù)庫n目錄系統(tǒng)Silberschatz, Korth and Sudarshan19.2Database System Concepts2n分布式數(shù)據(jù)庫系統(tǒng)由松散耦合的不共享物理組件的站點組成n每個站點上運行的數(shù)據(jù)庫系統(tǒng)相互獨立n事務可以存取一個或多個站點上的數(shù)據(jù)Silberschatz, Korth and Sudarshan19.3Database

2、System Concepts3n在同質的分布式數(shù)據(jù)庫系統(tǒng)中所有站點都有相同的軟件所有站點相互知曉并可以合作處理用戶請求每個站點因不能改變模式和軟件而喪失部分自治性在用戶看來是單個系統(tǒng)n在異質的分布式數(shù)據(jù)庫系統(tǒng)中不同站點可用不同模式和軟件模式差異是查詢處理中的主要問題軟件差異是事務處理中的主要問題站點可能相互不知曉，并且在事務處理中只能提供有限的合作手段Silberschatz, Korth and Sudarshan19.4Database System Concepts4n假設使用關系數(shù)據(jù)模型n復制系統(tǒng)維護存儲在不同站點的數(shù)據(jù)副本, 以提供快速查詢和容錯.n分片關系分割成若干片段存儲于不同

3、站點n復制與分片可以結合關系分割成若干片段; 系統(tǒng)又為每個片段維護多個完全相同的副本.Silberschatz, Korth and Sudarshan19.5Database System Concepts5n復制復制是指將一個關系或關系片斷冗余存儲在兩個以上場地上.n全復制全復制一個關系是指將該關系存儲在所有場地上.n全冗余的數(shù)據(jù)庫是指每個場地都包含有整個數(shù)據(jù)庫的一個拷貝.Silberschatz, Korth and Sudarshan19.6Database System Concepts6n復制的優(yōu)點可用性可用性: 如果關系r 有副本, 則包含r 的場地發(fā)生故障時不會導致r 不可用.

4、并行性并行性: 對r 的查詢可由多個節(jié)點并行處理.減少數(shù)據(jù)傳輸減少數(shù)據(jù)傳輸: 在包含關系r 副本的場地上可以本地訪問.n復制的缺點更新代價增加: 關系 r 的每個副本都必須更新.并發(fā)控制的復雜性增加: 除非實現(xiàn)特殊的并發(fā)控制機制, 否則對不同副本的并發(fā)更新可能導致不一致數(shù)據(jù).一種解決方法: 選擇一個拷貝作為主副本主副本并且對主副本實施并發(fā)控制操作.Silberschatz, Korth and Sudarshan19.7Database System Concepts7n將關系 r 劃分成片斷r1, r2, , rn , 并且有足夠的信息重構關系r.n水平分片水平分片: r 的每個元組都被分配

5、到一個或多個片斷中n垂直分片垂直分片: 關系r 的模式分解成若干較小模式所有模式都需包含一公共的候選鍵 (或超鍵)以便確保無損連接性質.可以為每個模式加入一個特殊屬性tuple-id (元組標識)來作為候選鍵.n例如: 設關系 account 具有下面的模式Account-schema = (branch-name, account-number, balance)Silberschatz, Korth and Sudarshan19.8Database System Concepts8branch-nameaccount-numberbalanceHillsideHillsideHillsi

6、deA-305A-226Account1=branch-name=“Hillside”(account)branch-nameaccount-numberbalanceValleyviewValleyviewValleyviewValleyviewA-177A-402A-408A-639205100001123750account2=branch-name=“Valleyview”(account)Silberschatz, Korth and Sudarshan19.9Database System Concepts9branch-namecustomer-name

7、tuple-idHillsideHillsideValleyviewValleyviewHillsideValleyviewValleyviewLowmanCampCampKahnKahnKahnGreendeposit1=branch-name, customer-name, tuple-id(employee-info)1234567account numberbalancetuple-id500336205100006211237501234567A-305A-226A-177A-402A-155A-408A-639deposit2=account-number, balance, tu

8、ple-id(employee-info)Silberschatz, Korth and Sudarshan19.10Database System Concepts10n水平:允許對關系的各片斷做并行處理關系劃分時可使元組分配到最頻繁使用該元組的場地上n垂直: 分解屬性時可使不同屬性存儲在最頻繁使用的場地上tuple-id 屬性使得垂直片斷之間可以高效連接允許對關系作并行處理n水平與垂直分片可以混合.可以連續(xù)進行分片到任意深度.Silberschatz, Korth and Sudarshan19.11Database System Concepts11n數(shù)據(jù)透明性數(shù)據(jù)透明性: 分布式數(shù)據(jù)庫

9、系統(tǒng)的用戶不必知曉有關數(shù)據(jù)如何存儲以及存儲在哪里的細節(jié)的程度n考慮下列透明性問題:分片透明性復制透明性位置透明性Silberschatz, Korth and Sudarshan19.12Database System Concepts121. 每個數(shù)據(jù)項必須具有系統(tǒng)范圍內的唯一名字.2. 應能高效地找到數(shù)據(jù)項的位置.3. 應能透明地改變數(shù)據(jù)項的位置.4. 每個場地應能自主地創(chuàng)建新數(shù)據(jù)項.Silberschatz, Korth and Sudarshan19.13Database System Concepts13n結構:名字服務器分配所有名字各場地維護本地數(shù)據(jù)項的記錄場地詢問名字服務器來查找

10、非本地數(shù)據(jù)項n優(yōu)點:滿足命名準則1-3n缺點:不滿足命名準則 4名字服務器是潛在的性能瓶頸名字服務器是single point of failure (即它的故障可導致所有場地不能繼續(xù)運行)Silberschatz, Korth and Sudarshan19.14Database System Concepts14n相對于集中式方案的另一種方案: 各場地將它自己的場地標識作為它所生成的所有名字的前綴. 例如site17.account既達到了唯一標識的目的, 又避免了集中控制帶來的問題.但是, 不具有網(wǎng)絡透明性.n解決方法: 為數(shù)據(jù)項創(chuàng)建別名別名集合; 在每個場地上保存從別名到真名的映射.n

11、用戶可以不知道數(shù)據(jù)項的物理位置, 并且當數(shù)據(jù)項從一個場地移到另一場地時不受影響.Copyright: Silberschatz, Korth and Sudarhan15Silberschatz, Korth and Sudarshan19.16Database System Concepts16n事務可以存取多個場地上的數(shù)據(jù).n每個場地有一個本地事務管理器, 負責:維護用于恢復目的的日志參與協(xié)調在本地執(zhí)行的事務的并發(fā).n每個場地還有一個事務協(xié)調器, 負責:啟動本地發(fā)起的事務.將子事務分配到適當場地執(zhí)行.協(xié)調本地發(fā)起事務的終止過程, 使事務在所有場地上提交或夭折.Silberschatz, K

12、orth and Sudarshan19.17Database System Concepts17Silberschatz, Korth and Sudarshan19.18Database System Concepts18n分布式系統(tǒng)特有的故障:場地故障丟失消息由網(wǎng)絡傳輸控制協(xié)議處理, 如 TCP-IP通信連接故障由網(wǎng)絡協(xié)議處理, 通過其他路徑傳送消息網(wǎng)絡分割網(wǎng)絡分割當網(wǎng)絡被分裂成兩個或更多相互不連通的子系統(tǒng)時稱為網(wǎng)絡分割網(wǎng)絡分割 注意: 子系統(tǒng)可能由單個節(jié)點組成n網(wǎng)絡分割和場地故障一般是不可分辨的.Silberschatz, Korth and Sudarshan19.19Databas

13、e System Concepts19n提交協(xié)議用于確?？鐖龅氐脑有栽诙鄠€場地上執(zhí)行的事務必須要么在所有場地上都提交, 要么在所有場地上都夭折.事務在一個場地上提交而在另一個場地上夭折是不可接受的n兩階段提交 (2PC)協(xié)議被廣泛使用n三階段提交 (3PC)協(xié)議更復雜且更昂貴, 但可以避免兩階段提交協(xié)議的某些缺陷.Silberschatz, Korth and Sudarshan19.20Database System Concepts20n假定采用fail-stop模型 故障場地簡單地停止工作, 不會導致任何其他害處, 如向其他場地發(fā)送不正確的消息之類.n協(xié)議的執(zhí)行是由協(xié)調者在到達事務的最

14、后一步之后開始的.n協(xié)議涉及事務執(zhí)行所位于的全體局部場地n令T 是在場地Si 上開始的一個事務, Si 上的事務協(xié)調者是CiSilberschatz, Korth and Sudarshan19.21Database System Concepts21n協(xié)調者要求所有參與者準備提交事務T.Ci 在日志中加入記錄 并將日志強制寫入穩(wěn)定存儲器向所有T 執(zhí)行的場地發(fā)送 prepare T 消息n收到消息后, 參與場地上的事務管理器確定它是否能提交該事務如果不能, 在日志中加入記錄 并向Ci 發(fā)送abort T 消息如果事務可以提交, 則:在日志中加入記錄 將T 的所有記錄強制寫入穩(wěn)定存儲器向Ci 發(fā)

15、送ready T 消息Silberschatz, Korth and Sudarshan19.22Database System Concepts22n如果Ci 從所有參與場地都收到了ready T 消息, 則T 可以提交; 否則T 必須夭折.n協(xié)調者向日志加入決定記錄或, 并將記錄強制寫入穩(wěn)定存儲器. 一旦記錄寫入穩(wěn)定存儲器即不可取消(即使發(fā)生故障)n協(xié)調者向每個參與者發(fā)消息通知該決定 (提交或夭折)n參與者在本地執(zhí)行適當?shù)牟僮?Silberschatz, Korth and Sudarshan19.23Database System Concepts23當場地Sk 恢復時, 它檢查日志以確

16、定故障發(fā)生時激活事務的命運.n若日志包含記錄: 場地執(zhí)行redo (T)n若日志包含記錄: 場地執(zhí)行undo (T)n若日志包含記錄: 場地必須咨詢Ci 以確定T 的命運.若T 提交, 執(zhí)行redo (T)若T 夭折, 執(zhí)行undo (T)n若日志不包含任何涉及T 的控制記錄意味著 Sk 在響應來自Ci 的prepare T 消息之前就出故障了由于Sk 的故障導致了未響應, C1 必須夭折 TSk 必須執(zhí)行undo (T)Silberschatz, Korth and Sudarshan19.24Database System Concepts24n若協(xié)調者在執(zhí)行T 的提交協(xié)議過程中發(fā)生故障,

17、 則必須由參與場地決定 T 的命運:1.如果某個激活場地的日志中包含 記錄, 則T 必須提交.2.如果某個激活場地的日志中包含 記錄, 則T 必須夭折.3.如果某個激活場地的日志中沒有 記錄, 則發(fā)生故障的協(xié)調者 Ci 不可能決定提交T, 從而可以夭折T.4.如果以上情況都不是, 則所有激活場地的日志中都必有記錄, 但沒有其他控制記錄(如 或 ). 這時激活場地必須等待Ci 恢復來達成決定.n阻塞問題阻塞問題: 激活場地可能不得不等待故障協(xié)調者的恢復.Silberschatz, Korth and Sudarshan19.25Database System Concepts25n如果協(xié)調者與所

18、有參與者保持在同一個分區(qū)中, 則故障對提交協(xié)議沒有影響.n如果協(xié)調者與參與者屬于多個分區(qū):不與協(xié)調者同分區(qū)的場地認為協(xié)調者發(fā)生故障, 并執(zhí)行處理協(xié)調者故障的協(xié)議.這不會導致?lián)p害, 但場地可能仍需等待來自協(xié)調者的決定.n協(xié)調者視其他分區(qū)的參與者為故障, 遵循通常的提交協(xié)議.同樣者不會導致?lián)p害Silberschatz, Korth and Sudarshan19.26Database System Concepts26n疑問事務疑問事務有, 但既沒有也沒有 日志記錄.n恢復場地必須通過聯(lián)系其他場地來決定這種事務的提交-夭折狀態(tài); 這使恢復變慢甚至有可能阻塞恢復.n恢復算法可以在日志中注上鎖信息.用

19、取代, 其中 L = 寫入日志時T 所持有的鎖的列表 (讀鎖可省略).對每個疑問事務T, 重新獲得日志記錄 中標注的所有鎖.n重新獲得鎖之后, 事務處理可以恢復; 疑問事務的提交或回滾與新事務可并發(fā)執(zhí)行.Silberschatz, Korth and Sudarshan19.27Database System Concepts27n假設:沒有網(wǎng)絡分割任何時候至少有一個場地必須運行.最多 K個場地(參加者或協(xié)調者)可以故障n第一階段: 達成預備決定: 與 2PC 第一階段相同.如果被指令的話, 每個場地都準備提交n2PC的第二階段分割成兩個階段, 即3PC的第二階段和第三階段在第二階段, 協(xié)調者

20、同在2PC中一樣作出決定(稱為提交前決定)并在多個(至少為 K)場地上記錄此決定在第三階段, 協(xié)調者發(fā)送提交/夭折消息給所有參加者場地,n在3PC下, 即使協(xié)調者故障, 知道了提交前決定也可以用來提交只要少于K個場地故障就可避免阻塞問題n缺點: 高開銷實際中可能不能滿足假設前提n不做進一步研究Silberschatz, Korth and Sudarshan19.28Database System Concepts28n跨多站點的單個事務之概念對許多應用來說不合適例如跨越組織邊界的事務沒有組織會允許外部事務阻塞本地事務一個不確定的時間段n一個替換模型通過發(fā)送消息來執(zhí)行事務處理消息的代碼必須小心

21、設計以確保更新的原子性和持久性性質隔離性不能保證, 因為中間階段可見, 但代碼必須確保不會因并發(fā)而導致不一致狀態(tài)持久消息系統(tǒng)是對消息提供事務性質的系統(tǒng)能確保消息僅發(fā)送一次稍后討論實現(xiàn)技術Silberschatz, Korth and Sudarshan19.29Database System Concepts29n促動例: 兩家銀行間的資金轉帳兩階段提交具有阻塞對資金轉帳中涉及的帳戶的更新的潛在可能替換解決方案:將來自源帳戶的款項記入借方并發(fā)送一個消息給其他站點站點接受消息并記入目標帳戶的貸方消息機制早就用于分布式事務(甚至在計算機發(fā)明以前!)n原子性問題一旦發(fā)送消息的事務提交, 該消息必須確

22、保能被送到只要目標站點活著并可達就要確保, 還必須有處理不可送達消息的代碼 例如將款項記回源帳戶的貸方. 如果發(fā)送事務夭折, 消息就不能發(fā)送Silberschatz, Korth and Sudarshan19.30Database System Concepts30n處理消息的代碼必須考慮各種故障情形例如如果目標帳戶不存在, 失敗消息必須送回到源站點當從目標站點接收到失敗消息, 或者目標站點本身不存在, 款項必須存回源帳戶如果源帳戶關閉又有問題 需要人來處理問題n利用2PC執(zhí)行事務處理的用戶代碼不必處理這種故障n在很多場合下, 付出額外努力進行錯誤處理換來消除阻塞的好處是值得的例如跨組織的事

23、務Silberschatz, Korth and Sudarshan19.31Database System Concepts31n工作流工作流提供一個涉及多站點以及可能需要人工處理某些步驟的事務處理的一般模型例如當銀行接收一個貸款申請, 它可能需要聯(lián)系外部信用檢查機構獲得一個或多個經(jīng)理的批準 然后才能對貸款申請作出反應我們在第24章討論工作流持久消息機制形成了分布式環(huán)境中工作流的基礎結構Silberschatz, Korth and Sudarshan19.32Database System Concepts32n發(fā)送站點協(xié)議發(fā)送站點協(xié)議1.發(fā)送事務寫消息到一特殊關系messages-to-

24、send. 該消息獲得一個唯一標識符.H寫此關系處理為與任何其他更新相同, 若事務夭折則取消. H該消息上的鎖保持到發(fā)送事務提交2.消息傳送進程監(jiān)控關系messages-to-sendH當發(fā)現(xiàn)有新消息, 該消息被送往其目的地H當從目的地收到確認, 該消息從messages-to-send 中刪除H如果經(jīng)過一段時間還沒有收到確認, 重發(fā)該消息H重復此過程直至收到確認而刪除該消息, 或者系統(tǒng)在嘗試很長時間后確定該消息不可投送H重復發(fā)送保證了該消息的投送H只要目的地存在并且在合理時間內可到達Silberschatz, Korth and Sudarshan19.33Database System C

25、oncepts33n接受站點協(xié)議當收到一條消息時1.寫到關系received-messages 中, 如果還不存在的話(利用消息id做此檢查). 執(zhí)行寫的事務提交2.發(fā)送確認(連同消息id)給發(fā)送站點.4在有重復消息時消息投送可能有很長延遲4 如果不小心可導致處理副本消息! 選擇1: 消息永遠不從received-messages中刪除選擇2: 消息帶有時間戳4 比給定截止點更老的消息從received-messages中刪除4 接受到的消息如果比截止點更老則丟棄Copyright: Silberschatz, Korth and Sudarhan34Silberschatz, Korth a

26、nd Sudarshan19.35Database System Concepts35n修改并發(fā)控制方案以便可用于分布式環(huán)境.n我們假定每個場地都參與提交協(xié)議的執(zhí)行以確保全局事務的原子性.n我們假定任何數(shù)據(jù)項的所有副本都要更新以后會看到在場地故障的情況下如何放寬這條Silberschatz, Korth and Sudarshan19.36Database System Concepts36n系統(tǒng)維護一位于選定的單個場地上(如Si )的單個鎖管理器n當一事務需要給數(shù)據(jù)項加鎖, 它將鎖請求發(fā)給Si , 鎖管理器決定是否可以立即批準該請求如果是, 鎖管理器發(fā)消息給提出請求的場地如果不是, 請求被延

27、遲直至可被批準, 那時再發(fā)消息給初始場地Silberschatz, Korth and Sudarshan19.37Database System Concepts37n事務可從任意存有副本的場地讀數(shù)據(jù)項.n寫必須對數(shù)據(jù)項的所有副本執(zhí)行n優(yōu)點:實現(xiàn)簡單死鎖處理簡單n缺點:瓶頸: 鎖管理器場地成為瓶頸脆弱: 系統(tǒng)因鎖管理器場地故障而變得脆弱.Silberschatz, Korth and Sudarshan19.38Database System Concepts38n在這種方法中, 鎖的功能由每個場地上的鎖管理器實現(xiàn)鎖管理器控制對本地數(shù)據(jù)項的存取但對副本可使用特殊協(xié)議n優(yōu)點: 工作被分布, 對

28、故障魯棒n缺點: 死鎖檢測更復雜鎖管理器合作進行死鎖檢測稍后詳及n此方法的若干變種主副本多數(shù)協(xié)議偏見協(xié)議法定數(shù)一致Silberschatz, Korth and Sudarshan19.39Database System Concepts39n選擇數(shù)據(jù)項的一個副本作為主副本主副本. 包含主副本的場地稱為該數(shù)據(jù)項的主場地主場地不同數(shù)據(jù)項可有不同的主場地n當事務需要對數(shù)據(jù)項Q加鎖時, 須在Q的主場地請求鎖.隱含地獲得了該數(shù)據(jù)項所有副本上的鎖n好處對復制數(shù)據(jù)的并發(fā)控制可類似于非復制數(shù)據(jù)來處理 實現(xiàn)簡單.n缺點若Q的主場地發(fā)生故障, Q 即不可存取, 即使其他包含Q的副本的場地還可訪問.Silbers

29、chatz, Korth and Sudarshan19.40Database System Concepts40n各場地的本地鎖管理器管理對本場地存儲的數(shù)據(jù)項的加鎖和釋放鎖的請求.n當事務要對存儲在場地Si 的非復制數(shù)據(jù)項Q加鎖時, 則向Si 上的鎖管理器發(fā)消息.如果Q 上已有不兼容方式的鎖, 則該請求被延遲, 直至可以獲得.當鎖請求被批準, 鎖管理器向請求者回發(fā)消息, 告知鎖請求已批準.Silberschatz, Korth and Sudarshan19.41Database System Concepts41n在復制數(shù)據(jù)的情況下若Q 在 n 個場地有副本, 則鎖請求必須發(fā)給其中一半以上

30、的場地.事務只有在多數(shù)含Q副本的場地上獲得了鎖才可對Q進行操作.寫數(shù)據(jù)項時, 事務對所有副本執(zhí)行寫操作.n好處即使某些場地不可用, 此方法仍有效稍后討論在場地故障時如何處理寫操作n缺點為處理加鎖請求需要發(fā)送2(n/2 + 1) 條消息, 為處理釋放鎖請求需要發(fā)送 (n/2 + 1) 條消息.即使對單個數(shù)據(jù)項也可能死鎖 例如, 三個事務各獲得了三分之一的數(shù)據(jù)副本.Silberschatz, Korth and Sudarshan19.42Database System Concepts42n各場地上的本地鎖管理器與多數(shù)協(xié)議相同, 但對共享鎖請求的處理不同于排他鎖請求.n共享鎖共享鎖. 當事務需要

31、鎖數(shù)據(jù)項Q, 只需簡單地向一個有Q副本的場地上的鎖管理器請求即可.n排他鎖排他鎖. 當事務需要鎖數(shù)據(jù)項Q, 需要向所有有Q副本的場地上的鎖管理器請求.n優(yōu)點 - 讀讀操作開銷較小.n缺點 - 寫寫操作帶來額外開銷Silberschatz, Korth and Sudarshan19.43Database System Concepts43n是對多數(shù)協(xié)議和偏見協(xié)議的一般化n賦予各場地一個權值.令S為所有場地的權值總和n選擇兩個值: 讀法定數(shù)Qr 和寫法定數(shù)Qw使得 Qr + Qw S 且 2 * Qw S對每個數(shù)據(jù)項可分別選擇法定數(shù)和計算Sn每個讀操作必須對足夠的副本加鎖, 以使這些副本所在場地

32、的權值之和 = Qrn每個寫操作必須對足夠的副本加鎖, 以使這些副本所在場地的權值之和 = Qwn目前我們假定所有副本都要更新稍后介紹允許某些場地不可用的擴展方法Silberschatz, Korth and Sudarshan19.44Database System Concepts44n基于時間戳的并發(fā)控制協(xié)議可用于分布式系統(tǒng)n每個事務必須賦予唯一時間戳n主要問題: 如何以分布式方式生成時間戳每個站點利用邏輯計數(shù)器或者局部時鐘生成唯一局部時間戳.全局唯一時間戳是通過拼接唯一局部時間戳與唯一標識符而得到的.Silberschatz, Korth and Sudarshan19.45Datab

33、ase System Concepts45n時鐘慢的站點將賦予較小的時間戳仍然邏輯上正確: 不影響可串行化但是: “劣勢”事務n為了解決這個問題在每個站點Si 定義邏輯時鐘邏輯時鐘 (LCi), 它生成唯一局部時間戳每當從具有時間戳的事務Ti (其中x大于LCi 的當前值)收到請求,就要求Si 增加其邏輯時鐘.這時, 站點Si 將其邏輯時鐘遞增到值x + 1.Silberschatz, Korth and Sudarshan19.46Database System Concepts46n許多商用數(shù)據(jù)庫支持具有較弱級別一致性的數(shù)據(jù)復制 (即, 不保證可串行性)n例如: 主從復制主從復制: 更新在

34、單個“主”場地上執(zhí)行, 再傳播到“從”場地.傳播過程不是更新事務的一部分: 兩者是分離的可能事務提交后立即做可能周期性做在從場地只能讀數(shù)據(jù), 不能更新在任何遠程場地都不需要獲得鎖對分布式信息尤其有用例如從中央辦公室到分支辦公室對從主數(shù)據(jù)庫脫機運行只讀查詢也有用Silberschatz, Korth and Sudarshan19.47Database System Concepts47n復本應該看見數(shù)據(jù)庫的一個事務一致的快照事務一致的快照即, 數(shù)據(jù)庫的一個狀態(tài)，該狀態(tài)反映了到達串行化次序中某一點時所有事務的所有效果, 而不反映任何后面事務的效果. n例如Oracle 提供了create sna

35、pshotcreate snapshot 語句來在遠程場地創(chuàng)建一個或多個關系的快照可通過重新計算或者增量更新來刷新快照自動刷新 (連續(xù)或周期性) 或人工刷新Silberschatz, Korth and Sudarshan19.48Database System Concepts48n在多主復制(也稱為update-anywhere復制)中, 更新可以針對任何復本, 并自動傳播到所有復本分布式數(shù)據(jù)庫的基本模型, 其中事務不知道復制的細節(jié), 且數(shù)據(jù)庫系統(tǒng)將更新作為同一事務的一部分來傳播與兩階段提交結合許多系統(tǒng)支持惰性傳播惰性傳播, 其中更新是在事務提交后傳播的即使某些場地與網(wǎng)絡斷開仍允許更新發(fā)生

36、, 但代價是一致性不能保證Silberschatz, Korth and Sudarshan19.49Database System Concepts49n惰性傳播的兩種方法對任何復本的更新被翻譯成對主場地的更新, 然后再傳播給所有復本對數(shù)據(jù)項的更新串行排序但事務可能讀到數(shù)據(jù)項的舊值并用來執(zhí)行一個更新, 導致非可串行化更新可在任何復本執(zhí)行并傳播到其他所有復本帶來更多的可串行化問題: 同一數(shù)據(jù)項可能在多個場地上并發(fā)更新!n沖突檢測是個問題當更新被傳播到其他場地時可以檢測到某些由缺少分布式并發(fā)控制引起的沖突 (參見 23.5.4)n沖突消解很亂消解可能需要已提交事務被回滾破壞了事務的永久性也許不可

37、能自動消解, 需要人工干預Silberschatz, Korth and Sudarshan19.50Database System Concepts50考慮下列兩個事務及執(zhí)行過程, 設數(shù)據(jù)項X和事務T1 在場地1, 數(shù)據(jù)項Y 和事務T2 在場地2:T1: write (X)write (Y)T2: write (Y)write (X)X-lock on Xwrite (X)X-lock on Ywrite (Y)wait for X-lock on XWait for X-lock on Y結果: 發(fā)生了在各場地局部都無法檢測到的死鎖Silberschatz, Korth and Sudar

38、shan19.51Database System Concepts51n構造全局等待圖并維護在單一站點: 死鎖檢測協(xié)調器真實圖: 真實但未知的系統(tǒng)狀態(tài).構造圖: 由控制器在執(zhí)行其算法過程中生成的近似.n可在下列情況構造全局等待圖:在局部等待圖中插入或刪除了一條新邊.局部等待圖中發(fā)生了許多改變.協(xié)調器需要調用圈檢測算法時.n如果協(xié)調器找到了圈, 就選擇一個犧牲品并通知所有站點. 站點回滾犧牲品事務.Silberschatz, Korth and Sudarshan19.52Database System Concepts52局部全局Silberschatz, Korth and Sudarsha

39、n19.53Database System Concepts53初始狀態(tài):Silberschatz, Korth and Sudarshan19.54Database System Concepts54n假設從圖中狀態(tài)開始,1. T2 釋放S1資源導致從S1上的事務管理器向協(xié)調者發(fā)送刪除信息T1 T2 消息2. 然后T2 請求由T3持有的S2資源導致S2向協(xié)調者發(fā)送增加信息T2 T3 消息n進一步假設插入消息在刪除消息之前到達由于網(wǎng)絡延遲這是可能發(fā)生的n協(xié)調者將發(fā)現(xiàn)一個假循環(huán)T1 T2 T3 T1上面這個循環(huán)實際上從未存在.n如果采用兩階段鎖, 則假循環(huán)不可能發(fā)生.Silberschatz,

40、Korth and Sudarshan19.55Database System Concepts55n當發(fā)生死鎖并選擇了犧牲品時, 同時有一個事務由于與死鎖無關的原因而夭折, 這時就會出現(xiàn)不必要的回滾.n全局等待圖中的假循環(huán)可導致不必要的回滾; 但假循環(huán)的可能性很低.Copyright: Silberschatz, Korth and Sudarhan56Silberschatz, Korth and Sudarshan19.57Database System Concepts57n高可用性: 系統(tǒng)完全不可用的機會極低 (例如99.99% 的可用性) n魯棒性: 即使有部件故障而系統(tǒng)仍可工作的

41、能力n在大型分布式系統(tǒng)中更可能發(fā)生故障n為達到魯棒性, 分布式系統(tǒng)必須檢測故障重新配置系統(tǒng)以使計算能繼續(xù)當場地或連接修復時能恢復/重整合n故障檢測: 分辨連接故障和場地故障很困難(部分) 解決方法: 使用多條連接, 多個連接故障意味著場地故障Silberschatz, Korth and Sudarshan19.58Database System Concepts58n重配置:夭折故障站點上的所有活躍事務使其等待可能干擾其他事務, 因為它們可能持有其他站點上的鎖然而, 在一個數(shù)據(jù)項的某些復本故障的情況下, 繼續(xù)執(zhí)行在故障站點存取數(shù)據(jù)的事務也是可能的(稍后詳述) 如果復本數(shù)據(jù)項在故障站點上, 更

42、新系統(tǒng)目錄以從復本列表中刪除之. 當故障站點恢復時應該做逆操作, 但要注意考慮更新數(shù)據(jù)值如果故障站點是某個子系統(tǒng)的中央服務器, 必須進行選舉來確定新的服務器例如名字服務器, 并發(fā)協(xié)調器, 全局死鎖檢測器Silberschatz, Korth and Sudarshan19.59Database System Concepts59n由于網(wǎng)絡分割不能與站點故障區(qū)分, 下列情形必須避免在不同分割區(qū)選舉出了兩個以上中央服務器一個以上分割區(qū)更新了復本數(shù)據(jù)項n即使某些站點故障, 更新也必須能繼續(xù)n解決方法: 基于多數(shù)的方法替換方法 “讀一寫全可用”是有吸引力的但是帶來問題Silberschatz, Kor

43、th and Sudarshan19.60Database System Concepts60n分布式并發(fā)控制的多數(shù)協(xié)議可被修改成即使某些場地不可用也能工作每個數(shù)據(jù)項的每個副本都有一版本號版本號, 更新副本時也更新此版本號鎖請求應發(fā)給至少一半存有副本的場地, 并且僅當在多數(shù)場地上獲得了鎖操作才能繼續(xù)讀操作檢查所有加鎖副本, 并且從具有最大版本號的副本讀取值可以將這個值和版本號寫回具有較小版本號的副本 (不必獲得所有副本的鎖即可執(zhí)行這個任務)Silberschatz, Korth and Sudarshan19.61Database System Concepts61n多數(shù)協(xié)議 (續(xù))寫操作同讀

44、操作一樣找出最大版本號, 并設置新版本號為最大老版本號+1然后對所有加鎖副本執(zhí)行寫操作, 并且這些副本的版本號設置為新版本號故障 (網(wǎng)絡和場地) 在下列情況下不會導致問題提交場地包含任何被更新數(shù)據(jù)項的多數(shù)副本讀操作時, 多數(shù)副本可用來找版本號在上述情況下, 可用兩階段提交來更新副本注: 讀可確?？吹綌?shù)據(jù)的最近版本重整合是平凡的: 不用做任何事n法定數(shù)一致算法可做類似擴展Silberschatz, Korth and Sudarshan19.62Database System Concepts62n偏見協(xié)議是法定數(shù)一致協(xié)議的特例允許讀操作讀任一副本, 而寫操作需要所有副本在提交時可用 (稱為讀讀

45、一寫全一寫全)n讀一寫全可用者(忽略故障場地)有吸引力但不正確如果故障連接恢復, 沒有一個斷開站點曾知道自己斷開過該站點就具有舊值, 對該站點的讀將返回不正確的值如果站點知道故障發(fā)生, 可以執(zhí)行重整合(reintegration), 但無法保證在網(wǎng)絡分割時, 各分割區(qū)的站點可能更新并發(fā)同一數(shù)據(jù)項認為其他分割區(qū)里的站點都發(fā)生故障了Silberschatz, Korth and Sudarshan19.63Database System Concepts63n當故障場地恢復時, 必須補上故障期間漏掉的所有更新問題: 當場地正在恢復時, 其上存有副本的數(shù)據(jù)項可能正在更新解決方法: 重整合場地時停止系

46、統(tǒng)中所有更新不可接受存在其他有更好并發(fā)性的解決方法Silberschatz, Korth and Sudarshan19.64Database System Concepts64n遠程備份(熱備份)系統(tǒng)(Section 17.10)也是用來提供高可用性的n遠程備份系統(tǒng)更簡單且開銷較小所有動作都是在單個站點執(zhí)行的, 僅傳送日志記錄不需要分布式并發(fā)控制, 或者兩階段提交n利用分布式數(shù)據(jù)庫的數(shù)據(jù)項復本和多數(shù)協(xié)議可以提供更高可用性Silberschatz, Korth and Sudarshan19.65Database System Concepts65n備份協(xié)調者在某場地上維護足夠信息, 以便當實

47、際協(xié)調者發(fā)生故障時可以承擔起協(xié)調者的作用與實際協(xié)調者執(zhí)行同樣算法并維護同樣內部狀態(tài)信息當協(xié)調者發(fā)生故障時允許快速恢復, 但在正常處理中有開銷.n選舉算法發(fā)生故障時用來選舉新的協(xié)調者要求系統(tǒng)中的每個活躍場地具有唯一的標識號例如: Bully 算法 用于每個場地都能向其他所有場地發(fā)消息的系統(tǒng).假設所選新協(xié)調者總是具有最大標識號的活躍場地Silberschatz, Korth and Sudarshan19.66Database System Concepts66n當場地Si 發(fā)的請求在預設時段T 內未被協(xié)調者響應, 則假定協(xié)調者發(fā)生了故障, Si 試圖選舉自己作為新的協(xié)調者.nSi 向具有較大標識

48、號的所有場地發(fā)一條選舉消息, 然后等待這些場地中的任何一個在時段T 內回答.n如果在T 內沒有收到回答, 則假定所有標識號大于i 的場地都發(fā)生故障, Si 選舉自己作為新的協(xié)調者, 并通知所有標識號小于i 的活躍場地.n如果收到了回答, Si 開始等待時段T 以接收某較大標識號場地被選為協(xié)調者的通知.如果在T 內沒有收到消息, 則假定該具有較大標識號的場地故障; Si 重新啟動算法.Silberschatz, Korth and Sudarshan19.67Database System Concepts67n當故障場地恢復后, 立即開始執(zhí)行同一算法.如果沒有具有較大標識號的活躍場地, 則該恢

49、復場地強制所有較小標識號場地讓它成為協(xié)調者場地, 即使當前有一個較小標識號的活躍協(xié)調者.Copyright: Silberschatz, Korth and Sudarhan68Silberschatz, Korth and Sudarshan19.69Database System Concepts69n對集中式系統(tǒng), 衡量特定策略的代價的主要準則是磁盤存取次數(shù).n在分布式系統(tǒng)中, 必須考慮其他因素:網(wǎng)絡上的數(shù)據(jù)傳輸代價多個場地并行處理查詢帶來的性能上的潛在好處Silberschatz, Korth and Sudarshan19.70Database System Concepts70n翻

50、譯成對片斷的代數(shù)查詢.必須能從片斷構造出原關系 r用從片斷重構關系r 的表達式替換關系rn考慮account 關系的水平分片account1 = branch-name = “Hillside” (account)account2 = branch-name = “Valleyview” (account)n查詢 branch-name = “Hillside” (account) 即成為 branch-name = “Hillside” (account1 account2)并優(yōu)化成 branch-name = “Hillside” (account1) branch-name = “Hil

51、lside” (account2)Silberschatz, Korth and Sudarshan19.71Database System Concepts71n由于account1 中只有屬于Hillside分行的元組, 我們可以消除選擇操作.n根據(jù)account2 的定義得到 branch-name = “Hillside” ( branch-name = “Valleyview” (account)n不管account 關系的內容如何, 此表達式的結果都是空集.n最終的策略是讓Hillside 場地返回account1 作為查詢的結果.Silberschatz, Korth and S

52、udarshan19.72Database System Concepts72n考慮下列關系代數(shù)表達式, 其中三個關系都沒有復制或分片account depositor branchaccount 存儲在場地 S1depositor 存儲在場地S2branch 存儲在場地S3n對在場地SI 上發(fā)出的查詢, 系統(tǒng)需要在場地SI 上生成結果Silberschatz, Korth and Sudarshan19.73Database System Concepts73n將三個關系的拷貝都送到場地SI 并選擇一種策略在場地SI 處理整個連接n將account 關系的拷貝送到場地S2 并在S2 計算te

53、mp1 = account depositor . 再將temp1 從S2 送到S3, 并在S3計算 temp2 = temp1 branch. 最后將結果temp2 送到SI.n通過交換S1, S2, S3的角色可以設計出其它類似策略n必須考慮下列因素:傳送的數(shù)據(jù)量在場地間傳送一個數(shù)據(jù)塊的代價各場地的相對處理速度Silberschatz, Korth and Sudarshan19.74Database System Concepts74n令r1 模式為R1 , 存儲在場地S1令r2 模式為R2 , 存儲在場地S2n計算表達式 r1 r2 并在場地S1得到結果.1. 在S1計算temp1 R

54、1 R2 (r1).2. 將temp1 從S1 送到S2.3. 在S2計算temp2 r2 temp1.4. 將temp2 從S2 送到S1.5. 在S1計算 r1 temp2 . 此結果即等于r1 r2. Silberschatz, Korth and Sudarshan19.75Database System Concepts75nr1與r2 的半連接半連接r1 r2 定義為:R1 (r1 r2) n即, r1 r2 選擇r1中參與到 r1 r2 的元組.n在上面的第3步, temp2=r2 r1.n對于多個關系的連接, 上述策略可以擴展成一系列半連接步驟.Silberschatz, Ko

55、rth and Sudarshan19.76Database System Concepts76n考慮r1 r2 r3 r4 , 其中關系ri 存儲在場地Si. 結果必須在場地S1得到.nr1 送往S2 并在S2計算r1 r2 ; 同時r3 送往S4 并在S4計算 r3 r4nS2 將(r1 r2) 的元組在生成時送往S1; S4 將(r3 r4) 的元組在生成時送往S1 n一旦(r1 r2) 和(r3 r4) 的元組到達S1 即可計算(r1 r2) (r3 r4), 這可與S2 上的計算 (r1 r2)和S4上的計算(r3 r4) 并行執(zhí)行. Silberschatz, Korth and

56、Sudarshan19.77Database System Concepts77n許多數(shù)據(jù)庫應用要求從位于若干異種的硬件和軟件平臺上的多個現(xiàn)存數(shù)據(jù)庫獲得數(shù)據(jù)n數(shù)據(jù)模型可不同 (層次式, 關系式, 等等)n事務提交協(xié)議可能不兼容n并發(fā)控制可能基于不同技術 (鎖, 時間戳, 等等)n系統(tǒng)級細節(jié)幾乎肯定完全不兼容.n多數(shù)據(jù)庫系統(tǒng)多數(shù)據(jù)庫系統(tǒng)是建立在現(xiàn)存數(shù)據(jù)庫系統(tǒng)之上的一個軟件層, 設計用來操作異種數(shù)據(jù)庫中的信息創(chuàng)建出邏輯數(shù)據(jù)庫集成而非物理數(shù)據(jù)庫集成的一個幻象Silberschatz, Korth and Sudarshan19.78Database System Concepts78n保持現(xiàn)有投資硬

57、件系統(tǒng)軟件應用n本地自治性和管理控制n允許使用專用DBMSn是向統(tǒng)一的同種DBMS發(fā)展的一步完全集成進同種DBMS技術困難與轉換代價組織性/政治性困難 組織可能不希望放棄對其數(shù)據(jù)的控制 局部數(shù)據(jù)庫希望保持大量的自治性自治性Silberschatz, Korth and Sudarshan19.79Database System Concepts79n一致采用共同的數(shù)據(jù)模型典型地是關系模型n一致采用共同的概念模式同一關系/屬性的不同名字同樣的關系/屬性名實際上是不同對象n一致采用共享數(shù)據(jù)的單一表示例如數(shù)據(jù)類型, 精度字符集ASCII vs EBCDIC排序方式n一致采用度量單位n名字變形例如:

58、Kln vs Cologne, Mumbai vs BombaySilberschatz, Korth and Sudarshan19.80Database System Concepts80n異種數(shù)據(jù)庫中查詢處理的若干問題n模式翻譯為每個數(shù)據(jù)源開發(fā)一個wrapper 用于翻譯數(shù)據(jù)到全局模式Wrapper 必須將對全局模式的更新翻譯成對本地模式的更新n有限的查詢能力某些數(shù)據(jù)源只允許限制形式的選擇例如 web形式, 平坦文件數(shù)據(jù)源查詢必須分解, 部分在源處理, 部分在另一不同場地處理n當場地有重疊信息時的刪除重復信息確定哪些場地執(zhí)行查詢n全局查詢優(yōu)化Silberschatz, Korth and

59、 Sudarshan19.81Database System Concepts81nMediator系統(tǒng)是指通過提供集成的全局視圖和對全局視圖的查詢功能來集成多個異種數(shù)據(jù)源的系統(tǒng)與正規(guī)的多數(shù)據(jù)庫系統(tǒng)不同, mediators一般不管事務處理問題但有時術語mediator 和多數(shù)據(jù)庫可交換使用術語虛擬數(shù)據(jù)庫虛擬數(shù)據(jù)庫也用于指mediator/多數(shù)據(jù)庫系統(tǒng)Copyright: Silberschatz, Korth and Sudarhan82Silberschatz, Korth and Sudarshan19.83Database System Concepts83nTypical kinds

60、 of directory informationEmployee information such as name, id, email, phone, office addr, .Even personal information to be accessed from multiple placese.g. Web browser bookmarksnWhite pagesEntries organized by name or identifierMeant for forward lookup to find more about an entrynYellow pagesEntri