第10章數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)

1、Silberschatz, Korth and Sudarshan18.1Database System Conceptsn第第10章章 數(shù)據(jù)庫(kù)體系結(jié)構(gòu)數(shù)據(jù)庫(kù)體系結(jié)構(gòu)n第第11章章 分布式數(shù)據(jù)庫(kù)分布式數(shù)據(jù)庫(kù)n第第12章章 并行數(shù)據(jù)庫(kù)并行數(shù)據(jù)庫(kù)n第第13章章 大數(shù)據(jù)與云數(shù)據(jù)管理大數(shù)據(jù)與云數(shù)據(jù)管理Silberschatz, Korth and Sudarshan18.2Database System Conceptsn本章內(nèi)容參考本章內(nèi)容參考:數(shù)據(jù)庫(kù)概念數(shù)據(jù)庫(kù)概念(第第6版版) by A. SilberschatzChapter 17 Database System Architectures補(bǔ)充

2、內(nèi)容補(bǔ)充內(nèi)容n本章內(nèi)容特色本章內(nèi)容特色:數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)內(nèi)容比較數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)內(nèi)容比較“宏觀宏觀”著重從計(jì)算機(jī)系統(tǒng)體系結(jié)構(gòu)的歷史演化角度進(jìn)行分析著重從計(jì)算機(jī)系統(tǒng)體系結(jié)構(gòu)的歷史演化角度進(jìn)行分析n本章要解決的關(guān)鍵問(wèn)題：本章要解決的關(guān)鍵問(wèn)題：如何認(rèn)識(shí)和解決數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)演化過(guò)程中面臨的如何認(rèn)識(shí)和解決數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)演化過(guò)程中面臨的“分分”與與“合合”的矛盾的矛盾Silberschatz, Korth and Sudarshan18.3Database System Conceptsn10.1 概述概述n10.2 集中式系統(tǒng)集中式系統(tǒng)n10.3 客戶客戶-服務(wù)器系統(tǒng)服務(wù)器系統(tǒng)n10.4 并

3、行系統(tǒng)并行系統(tǒng)n10.5 分布式系統(tǒng)分布式系統(tǒng)n10.6 網(wǎng)絡(luò)類型網(wǎng)絡(luò)類型n10.7分布式系統(tǒng)計(jì)算模型分布式系統(tǒng)計(jì)算模型(補(bǔ)充補(bǔ)充)Silberschatz, Korth and Sudarshan18.4Database System Conceptsn一個(gè)系統(tǒng)的體系結(jié)構(gòu)一個(gè)系統(tǒng)的體系結(jié)構(gòu)(architecture)定義了它的結(jié)構(gòu)定義了它的結(jié)構(gòu)(structure)，給出了其組成成份，每個(gè)成份的功能，給出了其組成成份，每個(gè)成份的功能，成分間的相互關(guān)系和交互方式成分間的相互關(guān)系和交互方式n數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)與計(jì)算機(jī)系統(tǒng)體系結(jié)構(gòu)密切相關(guān)數(shù)據(jù)庫(kù)系統(tǒng)體系結(jié)構(gòu)與計(jì)算機(jī)系統(tǒng)體系結(jié)構(gòu)密切相關(guān):集中式體系結(jié)

4、構(gòu)集中式體系結(jié)構(gòu)- 集中式數(shù)據(jù)庫(kù)系統(tǒng)集中式數(shù)據(jù)庫(kù)系統(tǒng)計(jì)算機(jī)聯(lián)網(wǎng)計(jì)算機(jī)聯(lián)網(wǎng)- 客戶客戶/服務(wù)器數(shù)據(jù)庫(kù)系統(tǒng)服務(wù)器數(shù)據(jù)庫(kù)系統(tǒng)分布計(jì)算分布計(jì)算 - 分布式數(shù)據(jù)庫(kù)系統(tǒng)分布式數(shù)據(jù)庫(kù)系統(tǒng)并行處理并行處理- 并行數(shù)據(jù)庫(kù)系統(tǒng)并行數(shù)據(jù)庫(kù)系統(tǒng) Silberschatz, Korth and Sudarshan18.5Database System Conceptsn自主性自主性(Autonomy)n分布性分布性(Distribution)n異質(zhì)性異質(zhì)性(Heterogeneity)Silberschatz, Korth and Sudarshan18.6Database System Conceptsn單個(gè)單個(gè)DB

5、MS的本地運(yùn)算不因系統(tǒng)其它的本地運(yùn)算不因系統(tǒng)其它DBMS的加入而受影響的加入而受影響n單個(gè)單個(gè)DBMS處理查詢和優(yōu)化查詢的方式不處理查詢和優(yōu)化查詢的方式不 受全局查詢的影響受全局查詢的影響n系統(tǒng)已執(zhí)行的操作在單個(gè)系統(tǒng)已執(zhí)行的操作在單個(gè)DBMS加入或離開(kāi)加入或離開(kāi)時(shí)不受影響時(shí)不受影響Silberschatz, Korth and Sudarshan18.7Database System Conceptsn數(shù)據(jù)分布數(shù)據(jù)分布n功能分布功能分布n控制分布控制分布nSilberschatz, Korth and Sudarshan18.8Database System Conceptsn硬件的差異性硬件

6、的差異性n網(wǎng)絡(luò)協(xié)議的差異性網(wǎng)絡(luò)協(xié)議的差異性n操作系統(tǒng)的差異性操作系統(tǒng)的差異性n數(shù)據(jù)管理器的差異性數(shù)據(jù)管理器的差異性n數(shù)據(jù)模型的差異性數(shù)據(jù)模型的差異性語(yǔ)法上的差異性語(yǔ)法上的差異性語(yǔ)義上的差異性語(yǔ)義上的差異性nSilberschatz, Korth and Sudarshan18.9Database System ConceptsSilberschatz, Korth and Sudarshan18.10Database System ConceptsnA0：代表無(wú)自主性（緊密集成）：代表無(wú)自主性（緊密集成）nA1：代表半自主性（部分集成）：代表半自主性（部分集成）nA2：代表全自主性（全隔離）：

7、代表全自主性（全隔離）Silberschatz, Korth and Sudarshan18.11Database System Concepts1. 設(shè)計(jì)自主性設(shè)計(jì)自主性(Design autonomy)：?jiǎn)蝹€(gè)：?jiǎn)蝹€(gè)DBMS可以按它們喜歡的方式使用數(shù)據(jù)模塊可以按它們喜歡的方式使用數(shù)據(jù)模塊和事務(wù)管理技術(shù)和事務(wù)管理技術(shù)2. 通信自主性通信自主性(Communication autonomy)：每：每 個(gè)獨(dú)立個(gè)獨(dú)立DBMS可以自由決策為其它可以自由決策為其它DBMS提供何種類型的數(shù)據(jù)或者控制全局執(zhí)提供何種類型的數(shù)據(jù)或者控制全局執(zhí)行的策略行的策略3. 執(zhí)行自主性執(zhí)行自主性(Execution aut

8、onomy)：每個(gè)：每個(gè) DBMS可以按自己希望的方式執(zhí)行和提交事可以按自己希望的方式執(zhí)行和提交事務(wù)務(wù)Silberschatz, Korth and Sudarshan18.12Database System ConceptsnD0：全集中：全集中 (無(wú)分布無(wú)分布)nD1：client/server系統(tǒng)系統(tǒng)(功能分布功能分布/數(shù)據(jù)集中數(shù)據(jù)集中)nD2：表全分布：表全分布(peer-to-peer)Silberschatz, Korth and Sudarshan18.13Database System ConceptsnH0：同構(gòu)系統(tǒng)：同構(gòu)系統(tǒng)nH1：異構(gòu)系統(tǒng)：異構(gòu)系統(tǒng)Silberschatz

9、, Korth and Sudarshan18.14Database System Conceptsn(A0, D2, H0)：代表一個(gè)：代表一個(gè)(peer-to-peer) 分布式同分布式同 構(gòu)多數(shù)據(jù)庫(kù)構(gòu)多數(shù)據(jù)庫(kù)multidatabase系統(tǒng)系統(tǒng)n(A2, D2, H1) ：代表一個(gè)：代表一個(gè)(peer-to-peer) 分布式分布式 異構(gòu)多數(shù)據(jù)庫(kù)異構(gòu)多數(shù)據(jù)庫(kù)multidatabase系統(tǒng)系統(tǒng)n(A0, D1, H0)：系統(tǒng)是分布的并提供給用：系統(tǒng)是分布的并提供給用 戶一個(gè)集戶一個(gè)集成的視圖成的視圖nSilberschatz, Korth and Sudarshan18.15Database

10、 System Conceptsn運(yùn)行在一臺(tái)計(jì)算機(jī)上，數(shù)據(jù)集中存儲(chǔ)在一臺(tái)運(yùn)行在一臺(tái)計(jì)算機(jī)上，數(shù)據(jù)集中存儲(chǔ)在一臺(tái)計(jì)算機(jī)中，不與其他計(jì)算機(jī)系統(tǒng)交互的數(shù)據(jù)計(jì)算機(jī)中，不與其他計(jì)算機(jī)系統(tǒng)交互的數(shù)據(jù)庫(kù)系統(tǒng)庫(kù)系統(tǒng)n規(guī)模：個(gè)人微機(jī)規(guī)模：個(gè)人微機(jī) - 大型主機(jī)大型主機(jī)n單用戶系統(tǒng)：管理簡(jiǎn)單單用戶系統(tǒng)：管理簡(jiǎn)單n多用戶系統(tǒng)多用戶系統(tǒng): 具有并發(fā)控制、故障恢復(fù)等具有并發(fā)控制、故障恢復(fù)等能力能力 Silberschatz, Korth and Sudarshan18.16Database System ConceptsSilberschatz, Korth and Sudarshan18.17Database Sys

11、tem ConceptsSilberschatz, Korth and Sudarshan18.18Database System Conceptsn微機(jī)變得更快，能力更強(qiáng)，價(jià)格更低微機(jī)變得更快，能力更強(qiáng)，價(jià)格更低 - 集中式系統(tǒng)中的終端被微機(jī)所代替集中式系統(tǒng)中的終端被微機(jī)所代替 - 集中式系統(tǒng)直接執(zhí)行的用戶界面功能由微機(jī)來(lái)處理集中式系統(tǒng)直接執(zhí)行的用戶界面功能由微機(jī)來(lái)處理 n集中式系統(tǒng)集中式系統(tǒng) - 客戶機(jī)客戶機(jī)/服務(wù)器系統(tǒng)服務(wù)器系統(tǒng) Silberschatz, Korth and Sudarshan18.19Database System Conceptsn服務(wù)器系統(tǒng)響應(yīng)若干個(gè)客戶機(jī)系統(tǒng)的請(qǐng)

12、求服務(wù)器系統(tǒng)響應(yīng)若干個(gè)客戶機(jī)系統(tǒng)的請(qǐng)求, 一般結(jié)一般結(jié)構(gòu)如下構(gòu)如下:Silberschatz, Korth and Sudarshan18.20Database System Conceptsn系統(tǒng)功能分為系統(tǒng)功能分為:后端后端: 管理存取結(jié)構(gòu)管理存取結(jié)構(gòu), 查詢處理與優(yōu)化查詢處理與優(yōu)化, 并發(fā)控制和恢復(fù)并發(fā)控制和恢復(fù)前端前端: 提供各種工具提供各種工具, 如表格如表格, 報(bào)表制作報(bào)表制作, 圖形用戶界面圖形用戶界面n前端與后端的交互通過(guò)前端與后端的交互通過(guò)SQL或應(yīng)用程序界面或應(yīng)用程序界面APISilberschatz, Korth and Sudarshan18.21Database Sy

13、stem Conceptsn用工作站或個(gè)人計(jì)算機(jī)通過(guò)網(wǎng)絡(luò)連接后端服務(wù)用工作站或個(gè)人計(jì)算機(jī)通過(guò)網(wǎng)絡(luò)連接后端服務(wù)器器, 好處好處:性價(jià)比高性價(jià)比高靈活性靈活性用戶界面更好用戶界面更好易于維護(hù)易于維護(hù)?n服務(wù)器系統(tǒng)分為兩類服務(wù)器系統(tǒng)分為兩類:事務(wù)服務(wù)器事務(wù)服務(wù)器: 廣泛用于關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)中廣泛用于關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)服務(wù)器數(shù)據(jù)服務(wù)器: 用于面向?qū)ο髷?shù)據(jù)庫(kù)系用于面向?qū)ο髷?shù)據(jù)庫(kù)系Silberschatz, Korth and Sudarshan18.22Database System Conceptsn亦稱為亦稱為查詢服務(wù)器查詢服務(wù)器系統(tǒng)或系統(tǒng)或SQL服務(wù)器系統(tǒng)服務(wù)器系統(tǒng)n客戶發(fā)送請(qǐng)求給服務(wù)器系統(tǒng)執(zhí)

14、行事務(wù)客戶發(fā)送請(qǐng)求給服務(wù)器系統(tǒng)執(zhí)行事務(wù), 結(jié)果在結(jié)果在送回給客戶送回給客戶nSQL請(qǐng)求通過(guò)遠(yuǎn)程過(guò)程調(diào)用請(qǐng)求通過(guò)遠(yuǎn)程過(guò)程調(diào)用(RPC) 機(jī)制傳給服機(jī)制傳給服務(wù)器務(wù)器n事務(wù)事務(wù)RPC允許多個(gè)允許多個(gè)RPC調(diào)用共同構(gòu)成一個(gè)事務(wù)調(diào)用共同構(gòu)成一個(gè)事務(wù)nODBC 是一個(gè)是一個(gè)C語(yǔ)言應(yīng)用程序界面標(biāo)準(zhǔn)語(yǔ)言應(yīng)用程序界面標(biāo)準(zhǔn)(Microsoft), 用于連接服務(wù)器用于連接服務(wù)器, 發(fā)送發(fā)送SQL請(qǐng)求請(qǐng)求, 接收接收結(jié)果nJDBC標(biāo)準(zhǔn)類似標(biāo)準(zhǔn)類似ODBC, 用于用于JavaSilberschatz, Korth and Sudarshan18.23Database System Conceptsn典型的事務(wù)服務(wù)器包

15、含多個(gè)進(jìn)程在共享內(nèi)存中典型的事務(wù)服務(wù)器包含多個(gè)進(jìn)程在共享內(nèi)存中存取數(shù)據(jù)存取數(shù)據(jù)n服務(wù)器進(jìn)程服務(wù)器進(jìn)程接收用戶查詢接收用戶查詢(事務(wù)事務(wù)), 執(zhí)行查詢并返回結(jié)果執(zhí)行查詢并返回結(jié)果進(jìn)程可以是進(jìn)程可以是多線程的多線程的, 允許單個(gè)進(jìn)程并發(fā)執(zhí)行多個(gè)用戶查詢?cè)试S單個(gè)進(jìn)程并發(fā)執(zhí)行多個(gè)用戶查詢通常有多個(gè)多線程服務(wù)器進(jìn)程通常有多個(gè)多線程服務(wù)器進(jìn)程n數(shù)據(jù)庫(kù)寫(xiě)進(jìn)程數(shù)據(jù)庫(kù)寫(xiě)進(jìn)程不斷輸出更新后的緩沖塊到磁盤(pán)不斷輸出更新后的緩沖塊到磁盤(pán)Silberschatz, Korth and Sudarshan18.24Database System Conceptsn寫(xiě)日志進(jìn)程寫(xiě)日志進(jìn)程服務(wù)器進(jìn)程向日志記錄緩沖區(qū)增加日志記錄服

16、務(wù)器進(jìn)程向日志記錄緩沖區(qū)增加日志記錄日志寫(xiě)進(jìn)程將日志記錄輸出到穩(wěn)定存儲(chǔ)器日志寫(xiě)進(jìn)程將日志記錄輸出到穩(wěn)定存儲(chǔ)器nCheckpoint進(jìn)程進(jìn)程執(zhí)行周期性的執(zhí)行周期性的checkpointsn進(jìn)程監(jiān)控進(jìn)程進(jìn)程監(jiān)控進(jìn)程監(jiān)控其他進(jìn)程監(jiān)控其他進(jìn)程, 當(dāng)其他進(jìn)程失敗時(shí)采取恢復(fù)行動(dòng)當(dāng)其他進(jìn)程失敗時(shí)采取恢復(fù)行動(dòng)E.g. 中止正在由服務(wù)器進(jìn)程執(zhí)行的任何事務(wù)并重啟之中止正在由服務(wù)器進(jìn)程執(zhí)行的任何事務(wù)并重啟之Silberschatz, Korth and Sudarshan18.25Database System ConceptsSilberschatz, Korth and Sudarshan18.26Databa

17、se System Conceptsn共享內(nèi)存包含共享數(shù)據(jù)共享內(nèi)存包含共享數(shù)據(jù) 緩沖池緩沖池(Buffer pool)鎖表鎖表日志緩沖區(qū)日志緩沖區(qū)Cached查詢計(jì)劃查詢計(jì)劃(如果同一查詢?cè)俅翁岢隹梢灾赜萌绻徊樵冊(cè)俅翁岢隹梢灾赜?n所有數(shù)據(jù)庫(kù)進(jìn)程都可存取共享內(nèi)存所有數(shù)據(jù)庫(kù)進(jìn)程都可存取共享內(nèi)存n為確保兩個(gè)進(jìn)程不同時(shí)存取同一數(shù)據(jù)結(jié)構(gòu)為確保兩個(gè)進(jìn)程不同時(shí)存取同一數(shù)據(jù)結(jié)構(gòu), 系統(tǒng)通過(guò)系統(tǒng)通過(guò):操作系統(tǒng)信號(hào)燈操作系統(tǒng)信號(hào)燈原子指令原子指令n實(shí)現(xiàn)實(shí)現(xiàn)互斥互斥Silberschatz, Korth and Sudarshan18.27Database System ConceptsSilberschat

18、z, Korth and Sudarshan18.28Database System Conceptsn并行系統(tǒng)由多個(gè)處理器和多個(gè)磁盤(pán)通過(guò)高速互并行系統(tǒng)由多個(gè)處理器和多個(gè)磁盤(pán)通過(guò)高速互連網(wǎng)絡(luò)連接而組成連網(wǎng)絡(luò)連接而組成n粗粒度并行粗粒度并行機(jī)由少量強(qiáng)大的處理器組成機(jī)由少量強(qiáng)大的處理器組成n大規(guī)模并行大規(guī)模并行或或細(xì)粒度并行細(xì)粒度并行機(jī)利用了成千上萬(wàn)的機(jī)利用了成千上萬(wàn)的較小處理器較小處理器n兩個(gè)主要性能指標(biāo)兩個(gè)主要性能指標(biāo):吞吐量吞吐量 - 在給定時(shí)間區(qū)間可以完成的任務(wù)數(shù)量在給定時(shí)間區(qū)間可以完成的任務(wù)數(shù)量響應(yīng)時(shí)間響應(yīng)時(shí)間 - 單個(gè)任務(wù)從提交到完成所花的時(shí)間單個(gè)任務(wù)從提交到完成所花的時(shí)間Silber

19、schatz, Korth and Sudarshan18.29Database System Conceptsn加速比加速比:將在小系統(tǒng)上執(zhí)行的固定大小的問(wèn)題拿到將在小系統(tǒng)上執(zhí)行的固定大小的問(wèn)題拿到N倍倍大的系統(tǒng)上執(zhí)行大的系統(tǒng)上執(zhí)行n度量方法度量方法:加速比加速比 = 小系統(tǒng)所花時(shí)小系統(tǒng)所花時(shí) / 大系統(tǒng)所花時(shí)間大系統(tǒng)所花時(shí)間如果等于如果等于N則稱加速比是線性的則稱加速比是線性的n擴(kuò)展比擴(kuò)展比: 同步增加問(wèn)題和系統(tǒng)的大小同步增加問(wèn)題和系統(tǒng)的大小n用用N-倍大的系統(tǒng)來(lái)執(zhí)行倍大的系統(tǒng)來(lái)執(zhí)行N-倍大的任務(wù)倍大的任務(wù)n度量方法度量方法:擴(kuò)展比擴(kuò)展比 = 小系統(tǒng)小問(wèn)題所花時(shí)間小系統(tǒng)小問(wèn)題所花時(shí)間/大系

20、統(tǒng)大問(wèn)題所花時(shí)間大系統(tǒng)大問(wèn)題所花時(shí)間n如果等于如果等于1則稱擴(kuò)展比是線性的則稱擴(kuò)展比是線性的Silberschatz, Korth and Sudarshan18.30Database System ConceptsSilberschatz, Korth and Sudarshan18.31Database System ConceptsSilberschatz, Korth and Sudarshan18.32Database System Conceptsn批量擴(kuò)展批量擴(kuò)展:單個(gè)大任務(wù)單個(gè)大任務(wù); 典型的典型的, 如數(shù)據(jù)庫(kù)查詢和科學(xué)模擬如數(shù)據(jù)庫(kù)查詢和科學(xué)模擬使用使用N-倍大的計(jì)算機(jī)計(jì)算倍大

21、的計(jì)算機(jī)計(jì)算N-倍大的問(wèn)題倍大的問(wèn)題n事務(wù)擴(kuò)展事務(wù)擴(kuò)展:由獨(dú)立用戶提交許多小查詢到共享數(shù)據(jù)庫(kù)由獨(dú)立用戶提交許多小查詢到共享數(shù)據(jù)庫(kù); 典型的如典型的如事務(wù)處理系統(tǒng)和分時(shí)系統(tǒng)事務(wù)處理系統(tǒng)和分時(shí)系統(tǒng)N-倍多的用戶提交請(qǐng)求倍多的用戶提交請(qǐng)求(因此有因此有N-倍多的請(qǐng)求倍多的請(qǐng)求)到到N-倍大的計(jì)算機(jī)上的倍大的計(jì)算機(jī)上的N-倍大的數(shù)據(jù)庫(kù)倍大的數(shù)據(jù)庫(kù)適合于并行執(zhí)行適合于并行執(zhí)行Silberschatz, Korth and Sudarshan18.33Database System Conceptsn加速比和擴(kuò)展比經(jīng)常是亞線性的加速比和擴(kuò)展比經(jīng)常是亞線性的, 原因是原因是:n啟動(dòng)代價(jià)啟動(dòng)代價(jià):如果并行度很

22、高的話如果并行度很高的話, 啟動(dòng)多個(gè)進(jìn)程啟動(dòng)多個(gè)進(jìn)程的代價(jià)可能主宰計(jì)算時(shí)間的代價(jià)可能主宰計(jì)算時(shí)間n干擾干擾: 訪問(wèn)共享資源的進(jìn)程訪問(wèn)共享資源的進(jìn)程(如系統(tǒng)總線如系統(tǒng)總線, 磁盤(pán)磁盤(pán), 鎖鎖)相互競(jìng)爭(zhēng)相互競(jìng)爭(zhēng), 因此要花時(shí)間等待其他進(jìn)程因此要花時(shí)間等待其他進(jìn)程, 而不而不是執(zhí)行有用的工作是執(zhí)行有用的工作n偏斜偏斜: 增加并行度會(huì)增加對(duì)并行執(zhí)行的任務(wù)的增加并行度會(huì)增加對(duì)并行執(zhí)行的任務(wù)的服務(wù)時(shí)間的偏差服務(wù)時(shí)間的偏差, 總的執(zhí)行時(shí)間由最慢的任務(wù)總的執(zhí)行時(shí)間由最慢的任務(wù)決定決定Silberschatz, Korth and Sudarshan18.34Database System Conceptsn共

23、享內(nèi)存共享內(nèi)存 處理器共享同一內(nèi)存處理器共享同一內(nèi)存n共享磁盤(pán)共享磁盤(pán) 處理器共享同一磁盤(pán)處理器共享同一磁盤(pán)n無(wú)共享無(wú)共享 處理器既不共享內(nèi)存也不共享處理器既不共享內(nèi)存也不共享磁盤(pán)磁盤(pán)n層次式層次式 上述體系結(jié)構(gòu)的混合上述體系結(jié)構(gòu)的混合Silberschatz, Korth and Sudarshan18.35Database System Conceptsn定義定義:分布式系統(tǒng)為一組通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)分布式系統(tǒng)為一組通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)互聯(lián)的、具有相對(duì)互聯(lián)的、具有相對(duì)” ”自主性自主性” ”的處理單元（的處理單元（不一定同構(gòu)），并通過(guò)協(xié)同工作，完成指不一定同構(gòu)），并通過(guò)協(xié)同工作，完成指派的任務(wù)的系統(tǒng)派

24、的任務(wù)的系統(tǒng)n所謂計(jì)算單元，指的是可以在其上面執(zhí)行所謂計(jì)算單元，指的是可以在其上面執(zhí)行程序的計(jì)算設(shè)施程序的計(jì)算設(shè)施Silberschatz, Korth and Sudarshan18.36Database System Conceptsn分布處理，如果不分程度，則到處都有，分布處理，如果不分程度，則到處都有，即便是單處理器的計(jì)算機(jī)系統(tǒng)中也有分布即便是單處理器的計(jì)算機(jī)系統(tǒng)中也有分布處理處理n事實(shí)上，計(jì)算機(jī)技術(shù)發(fā)展的過(guò)程就是一個(gè)事實(shí)上，計(jì)算機(jī)技術(shù)發(fā)展的過(guò)程就是一個(gè)不斷將處理分布化的過(guò)程，例如，將不斷將處理分布化的過(guò)程，例如，將CPU和和I/O功能分開(kāi)就是一種分布處理的范例功能分開(kāi)就是一種分布處理

25、的范例n不過(guò)，目前所講的分布處理則要復(fù)雜得多不過(guò)，目前所講的分布處理則要復(fù)雜得多，因此任何單處理器系統(tǒng)不包括在內(nèi)，因此任何單處理器系統(tǒng)不包括在內(nèi)Silberschatz, Korth and Sudarshan18.37Database System Conceptsn分布式軟件系統(tǒng)分布式軟件系統(tǒng)(Distributed Software Systems)是支持分布式處理的軟件系統(tǒng)是支持分布式處理的軟件系統(tǒng), 是在是在由通信網(wǎng)絡(luò)互聯(lián)的多處理機(jī)體系結(jié)構(gòu)上執(zhí)行計(jì)由通信網(wǎng)絡(luò)互聯(lián)的多處理機(jī)體系結(jié)構(gòu)上執(zhí)行計(jì)算任務(wù)的系統(tǒng)算任務(wù)的系統(tǒng) 分布式操作系統(tǒng)分布式操作系統(tǒng)分布式程序設(shè)計(jì)語(yǔ)言及其編譯分布式程序設(shè)計(jì)語(yǔ)言

26、及其編譯(解釋解釋)系統(tǒng)系統(tǒng)分布式文件系統(tǒng)分布式文件系統(tǒng)分布式數(shù)據(jù)庫(kù)系統(tǒng)分布式數(shù)據(jù)庫(kù)系統(tǒng). Silberschatz, Korth and Sudarshan18.38Database System ConceptsnLocal-area networks (LANs) composed of processors that are distributed over small geographical areas, such as a single building or a few adjacent buildings. nWide-area networks (WANs) compose

27、d of processors distributed over a large geographical area.Discontinuous connection WANs, such as those based on periodic dial-up (using, e.g., UUCP), that are connected only for part of the time.Continuous connection WANs, such as the Internet, where hosts are connected to the network at all times.

28、Silberschatz, Korth and Sudarshan18.39Database System ConceptsnWANs with continuous connection are needed for implementing distributed database systemsnGroupware applications such as Lotus notes can work on WANs with discontinuous connection:Data is replicated.Updates are propagated to replicas peri

29、odically.No global locking is possible, and copies of data may be independently updated.Non-serializable executions can thus result. Conflicting updates may have to be detected, and resolved in an application dependent manner. Silberschatz, Korth and Sudarshan18.40Database System ConceptsnBus. Syste

30、m components send data on and receive data from a single communication bus;Does not scale well with increasing parallelism.nMesh.(網(wǎng)狀) Components are arranged as nodes in a grid, and each component is connected to all adjacent componentsCommunication links grow with growing number of components, and

31、so scales better. But may require 2n hops to send message to a node (or n with wraparound connections at edge of grid).nHypercube. Components are numbered in binary; components are connected to one another if their binary representations differ in exactly one bit.n components are connected to log(n)

32、 other components and can reach each other via at most log(n) links; reduces communication delays.Silberschatz, Korth and Sudarshan18.41Database System ConceptsCopyright: Silberschatz, Korth and Sudarhan42Silberschatz, Korth and Sudarshan18.43Database System Concepts43n分布式系統(tǒng)計(jì)算模型的復(fù)雜性分布式系統(tǒng)計(jì)算模型的復(fù)雜性系統(tǒng)由并

33、發(fā)執(zhí)行部件構(gòu)成系統(tǒng)由并發(fā)執(zhí)行部件構(gòu)成系統(tǒng)中無(wú)全局時(shí)鐘系統(tǒng)中無(wú)全局時(shí)鐘必須捕捉系統(tǒng)部件可能的失效必須捕捉系統(tǒng)部件可能的失效n對(duì)策對(duì)策因果關(guān)系（因果關(guān)系（Causality）一致?tīng)顟B(tài)（一致?tīng)顟B(tài)（Consistent states）全局狀態(tài)（全局狀態(tài)（Global states）Silberschatz, Korth and Sudarshan18.44Database System Concepts44n協(xié)議中的控制語(yǔ)句協(xié)議中的控制語(yǔ)句 1.Send（destination, action; parameters） destination：處理器抽象，可以是通信實(shí)體的地址：處理器抽象，可以是通信實(shí)

34、體的地址： 機(jī)器名，機(jī)器的端口號(hào)機(jī)器名，機(jī)器的端口號(hào)(即即1個(gè)個(gè)socket地址地址) action： 控制控制msg，希望接收者采取的動(dòng)作，希望接收者采取的動(dòng)作 parameters：參數(shù)集合：參數(shù)集合n假定：假定： msg發(fā)送是無(wú)阻塞、可靠的（語(yǔ)義類似于發(fā)送是無(wú)阻塞、可靠的（語(yǔ)義類似于TCP套接字）套接字）有時(shí)假定較弱的有時(shí)假定較弱的msg傳遞層（等價(jià)于傳遞層（等價(jià)于UDP）Silberschatz, Korth and Sudarshan18.45Database System Concepts452.接收接收msg 接收接收msg可推廣至接收事件，引起事件的原因是：可推廣至接收事件，引

35、起事件的原因是：外部外部msg、超時(shí)設(shè)定、內(nèi)部中斷、超時(shí)設(shè)定、內(nèi)部中斷 事件在處理前，一般在緩沖區(qū)（如事件隊(duì)列）中，若一處理器想處理事件事件在處理前，一般在緩沖區(qū)（如事件隊(duì)列）中，若一處理器想處理事件，它必須執(zhí)行一個(gè)聲明處理這些事件的線程，它必須執(zhí)行一個(gè)聲明處理這些事件的線程 例如，一個(gè)處理器通過(guò)執(zhí)行下述代碼等待事件例如，一個(gè)處理器通過(guò)執(zhí)行下述代碼等待事件A1, A2,., An waiting for A1, A2,., An ：/聲明聲明 A1（Source; parameters） Code to handle A1 . A1（Source; parameters） Code to ha

36、ndle An 當(dāng)當(dāng)p執(zhí)行執(zhí)行send(q, A1; parameters)且且q執(zhí)行上述代碼時(shí)，執(zhí)行上述代碼時(shí)，q將最終處理由將最終處理由p發(fā)發(fā)送的送的msgSilberschatz, Korth and Sudarshan18.46Database System Concepts463.超時(shí)超時(shí) 當(dāng)懷疑遠(yuǎn)程處理器失效時(shí)，可通過(guò)超時(shí)檢測(cè)來(lái)判定：當(dāng)懷疑遠(yuǎn)程處理器失效時(shí)，可通過(guò)超時(shí)檢測(cè)來(lái)判定：當(dāng)當(dāng)T秒后仍未收到秒后仍未收到P的類型為的類型為event的的msg時(shí)，執(zhí)行指定的動(dòng)作時(shí)，執(zhí)行指定的動(dòng)作 waiting until P sends (event; parameters), timeout

37、=T on timeout timeout action僅當(dāng)收到一個(gè)響應(yīng)僅當(dāng)收到一個(gè)響應(yīng)msg時(shí)才采取動(dòng)作，超時(shí)不做任何動(dòng)作時(shí)才采取動(dòng)作，超時(shí)不做任何動(dòng)作 waiting until P sends (event; parameters), timeout=T on timeout； if no timeout occurred Successful response actions 處理器等待T秒 若處理器在等待開(kāi)始后T秒內(nèi)沒(méi)響應(yīng)，則等待結(jié)束，協(xié)議繼續(xù) waiting up to T seconds for (event; parameters) msgs Event: Silberscha

38、tz, Korth and Sudarshan18.47Database System Concepts47n 分布式系統(tǒng)為何缺乏全局的系統(tǒng)狀態(tài)？分布式系統(tǒng)為何缺乏全局的系統(tǒng)狀態(tài)？ 1.非即時(shí)通信非即時(shí)通信 A A和和B B同時(shí)向?qū)Ψ胶霸捦瑫r(shí)向?qū)Ψ胶霸?他們都認(rèn)為是自己先喊話他們都認(rèn)為是自己先喊話 C C聽(tīng)到兩人是同時(shí)喊話聽(tīng)到兩人是同時(shí)喊話 結(jié)論：系統(tǒng)的全局狀態(tài)依賴于觀察點(diǎn)結(jié)論：系統(tǒng)的全局狀態(tài)依賴于觀察點(diǎn) 原因：原因： 傳播延遲傳播延遲 網(wǎng)絡(luò)資源的競(jìng)爭(zhēng)網(wǎng)絡(luò)資源的競(jìng)爭(zhēng) 丟失丟失msgmsg重發(fā)重發(fā) ACBd1 = d2Silberschatz, Korth and Sudarshan18.48D

39、atabase System Concepts482.相對(duì)性影響相對(duì)性影響假設(shè)張三和李四決定使用同步時(shí)鐘來(lái)觀察全局狀態(tài)他們約定下午5點(diǎn)在某餐館會(huì)面，張三準(zhǔn)時(shí)到達(dá)，但李四在一個(gè)接近光速的日光系統(tǒng)中游覽張三在等待李四1小時(shí)后離開(kāi)餐館，而李四在自己的表到達(dá)5點(diǎn)時(shí)準(zhǔn)時(shí)達(dá)到餐館，但他認(rèn)為張三未達(dá)到因?yàn)榇蠖鄶?shù)計(jì)算機(jī)的實(shí)際時(shí)鐘均存在漂移，故相對(duì)速度不同，時(shí)鐘同步仍然是一個(gè)問(wèn)題n 結(jié)論：使用時(shí)間來(lái)同步不是一個(gè)可靠機(jī)制！結(jié)論：使用時(shí)間來(lái)同步不是一個(gè)可靠機(jī)制！Silberschatz, Korth and Sudarshan18.49Database System Concepts493.中斷中斷假設(shè)張三和李四在

40、同一起跑線上賽跑，信號(hào)為小旗，前兩個(gè)問(wèn)題可以忽略，但是即使可忽略其他影響，也不可能指望不同的機(jī)器會(huì)同時(shí)做出某些反應(yīng): 因?yàn)楝F(xiàn)代計(jì)算機(jī)是一個(gè)很復(fù)雜的系統(tǒng)：CPU競(jìng)爭(zhēng)、中斷、頁(yè)錯(cuò)誤等，執(zhí)行時(shí)間無(wú)法預(yù)料結(jié)論：不可能在同一時(shí)刻觀察一個(gè)分布式系統(tǒng)的全局狀態(tài)！必須找到某種可以依賴的性質(zhì)：時(shí)間回溯因果相關(guān)Silberschatz, Korth and Sudarshan18.50Database System Concepts50n設(shè)分布式系統(tǒng)構(gòu)成：設(shè)分布式系統(tǒng)構(gòu)成： P PPP1 1, P, P2 2,., P,., Pn n ：處理器集合：處理器集合 E E：全體事件的集合：全體事件的集合 E Ep p

41、E E, , E Ep p表示發(fā)生在表示發(fā)生在p p上的所有事件上的所有事件n次序次序 e e1 1ee2 2： 事件事件e e1 1發(fā)生發(fā)生e e2 2在之前（亦記：在之前（亦記：e e1 1ee2 2） e e1 1 I e e2 2：事件：事件e e1 1發(fā)生發(fā)生e e2 2在之前，在之前，I為信息源為信息源n定序：定序： 有些有些E E中事件很容易定序：中事件很容易定序： 發(fā)生在同一節(jié)點(diǎn)發(fā)生在同一節(jié)點(diǎn)p p上的事件滿足全序：上的事件滿足全序： 若若e e1 1,e,e2 2 E Ep p，則，則 e e1 1 pe e2 2 或或 e e2 2 pe e1 1 成立成立e e1 1發(fā)送

42、消息發(fā)送消息m,em,e2 2接收接收m m，則，則e e1 1 me e2 2Silberschatz, Korth and Sudarshan18.51Database System Concepts51nHappens-before關(guān)系（關(guān)系（ H）規(guī)則規(guī)則1 1：若：若e e1 1 pe e2 2，則，則e e1 1 He e2 2規(guī)則規(guī)則2 2：若：若e e1 1 me e2 2，則，則e e1 1 He e2 2規(guī)則規(guī)則3 3：若：若e e1 1 He e2 2，且，且e e2 2 He e3 3，則，則e e1 1 He e3 3n該（該（ H）關(guān)系是節(jié)點(diǎn)次序和消息傳遞次序的傳遞

43、閉包）關(guān)系是節(jié)點(diǎn)次序和消息傳遞次序的傳遞閉包 e e1 1 He e3 3表示存在表示存在1 1個(gè)事件因果鏈，使個(gè)事件因果鏈，使e e1 1在在e e3 3之前發(fā)生之前發(fā)生 Note: Note: H是一種偏序關(guān)系，即是一種偏序關(guān)系，即存在存在e e和和e e，二者之間無(wú)這種關(guān)系，二者之間無(wú)這種關(guān)系并發(fā)事件：若兩事件不能由并發(fā)事件：若兩事件不能由 H定序定序 Silberschatz, Korth and Sudarshan18.52Database System Concepts52n舉例舉例1)1)因事件因事件e1,e4e1,e4和和e7e7均發(fā)生在均發(fā)生在P1P1上，故：上，故：e e1

44、 1 P1e e4 4 P1e e7 72)2)因因e1e1發(fā)送發(fā)送1 1個(gè)個(gè)msgmsg到到e3e3，故：，故：e e1 1 me e3 3，類似地，類似地e e5 5 me e8 83)3)應(yīng)用規(guī)則應(yīng)用規(guī)則1 1和和2 2得：得： e e1 1 He e4 4 He e7 7，e e1 1 He e3 3，e e5 5 He e8 84)4)由由 H的傳遞閉包性質(zhì)得：的傳遞閉包性質(zhì)得：e e1 1 He e8 85)e15)e1和和e6e6是并發(fā)的：是并發(fā)的：e1e1和和e6e6之間無(wú)之間無(wú) 路徑路徑 P1P2P3e1e2e4e3e7e5e8e6timeSilberschatz, Kort

45、h and Sudarshan18.53Database System Concepts53nHDAG 有時(shí)將有時(shí)將Happens-before關(guān)系描述為一個(gè)有向無(wú)環(huán)圖關(guān)系描述為一個(gè)有向無(wú)環(huán)圖頂點(diǎn)集頂點(diǎn)集V VH H是事件集是事件集E E：eVeVH H 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) e eE E 邊集邊集E EH H：若：若(e(e1 1，e e2 2)E)EH H 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)e e1 1 Pe e2 2或或e e1 1 me e2 2 Silberschatz, Korth and Sudarshan18.54Database System Concepts54n系統(tǒng)有序性的重要性系統(tǒng)有序性的重

46、要性若分布式系統(tǒng)中存在全局時(shí)鐘，則系統(tǒng)中的事件均可安排若分布式系統(tǒng)中存在全局時(shí)鐘，則系統(tǒng)中的事件均可安排為全序?yàn)槿蚶?，可以更公平地分配系統(tǒng)資源例如，可以更公平地分配系統(tǒng)資源n全序?qū)κ录挠绊懞陀扇驅(qū)κ录挠绊懞陀蒆關(guān)系確定的偏序?qū)κ录挠瓣P(guān)系確定的偏序?qū)κ录挠绊懯且恢碌捻懯且恢碌膎如何通過(guò)如何通過(guò)H關(guān)系確定的偏序關(guān)系來(lái)建立一個(gè)關(guān)系確定的偏序關(guān)系來(lái)建立一個(gè)“一致一致”的全序關(guān)系？的全序關(guān)系？在在 H的的DAGDAG上拓?fù)渑判蛏贤負(fù)渑判騉n the fly：Lamport提出了動(dòng)態(tài)即席地建立全序算法提出了動(dòng)態(tài)即席地建立全序算法 Silberschatz, Korth and Sudarsh

47、an18.55Database System Concepts55nLamport算法的思想算法的思想每個(gè)事件每個(gè)事件e有一個(gè)附加的時(shí)戳：有一個(gè)附加的時(shí)戳：e.TS;每個(gè)節(jié)點(diǎn)有一個(gè)局部時(shí)戳：每個(gè)節(jié)點(diǎn)有一個(gè)局部時(shí)戳：my_TS;節(jié)點(diǎn)執(zhí)行一個(gè)事件時(shí)，將自己的時(shí)戳賦給該事件；節(jié)點(diǎn)執(zhí)行一個(gè)事件時(shí)，將自己的時(shí)戳賦給該事件；節(jié)點(diǎn)發(fā)送節(jié)點(diǎn)發(fā)送msg時(shí)，將自己的時(shí)戳賦給所有發(fā)送的時(shí)，將自己的時(shí)戳賦給所有發(fā)送的msg;Silberschatz, Korth and Sudarshan18.56Database System Concepts56nLamport算法的實(shí)現(xiàn)算法的實(shí)現(xiàn) Initially：my_TS

48、=0; On event e： if ( e是接收消息是接收消息m ) then my_TS = max ( m.TS, my_TS ); /取取msg時(shí)戳和節(jié)點(diǎn)時(shí)戳的較大者作為新時(shí)戳?xí)r戳和節(jié)點(diǎn)時(shí)戳的較大者作為新時(shí)戳 my_TS+; e.TSmy_TS; /給事件給事件e打時(shí)戳打時(shí)戳 if ( e是發(fā)送消息是發(fā)送消息m ) then m.TSmy_TS; /給消息給消息m打時(shí)戳打時(shí)戳Silberschatz, Korth and Sudarshan18.57Database System Concepts57nLamport算法賦值的時(shí)戳是因果相關(guān)的算法賦值的時(shí)戳是因果相關(guān)的 若若e e1 1

49、 He e2 2，則，則 e e1 1.TS e.TS e2 2.TS.TS 若若e e1 1 Pe e2 2或或e e1 1 me e2 2，則的，則的e e2 2時(shí)戳大于時(shí)戳大于e e1 1的時(shí)戳的時(shí)戳 在因果事件鏈上，每一事件的時(shí)戳大于其前驅(qū)事件的時(shí)戳在因果事件鏈上，每一事件的時(shí)戳大于其前驅(qū)事件的時(shí)戳n問(wèn)題：系統(tǒng)中所有事件已為全序？問(wèn)題：系統(tǒng)中所有事件已為全序？不同的事件可能有相同的時(shí)戳（并發(fā)事件）nLamport算法改進(jìn)算法改進(jìn)因?yàn)椴l(fā)事件的時(shí)戳可以任意指定先后故可用節(jié)點(diǎn)地址作為時(shí)戳的低位Silberschatz, Korth and Sudarshan18.58Database Sy

50、stem Concepts58n改進(jìn)的改進(jìn)的Lamport時(shí)戳?xí)r戳 事件標(biāo)號(hào)：時(shí)戳事件標(biāo)號(hào)：時(shí)戳.id.id 事件事件e8e8為為4.3:4.3: my_TS=max(m.TS,my_TS) my_TS=max(m.TS,my_TS) =max(3,1)=3 =max(3,1)=3 按字典序得全序：按字典序得全序： 1.1,1.2,1.3,2.1,2.2,3.1,3.2,4.3 1.1,1.2,1.3,2.1,2.2,3.1,3.2,4.3n算法特點(diǎn)：分布、容錯(cuò)、系統(tǒng)開(kāi)銷小算法特點(diǎn)：分布、容錯(cuò)、系統(tǒng)開(kāi)銷小timeP1P2P3e1e2e4e3e7e5e8e61.22.23.23.12.11.14

51、.31.3Silberschatz, Korth and Sudarshan18.59Database System Concepts59nLamport時(shí)戳缺點(diǎn)時(shí)戳缺點(diǎn) 若若e e1 1 He e2 2，則，則 e e1 1.TS e.TS e2 2.TS.TS；反之不然；反之不然 例如：例如：1.32.11.32.1，但是，但是e e6 6ee4 4不成立不成立 原因：并發(fā)事件之間的次序是任意的原因：并發(fā)事件之間的次序是任意的 不能通過(guò)事件的時(shí)戳判定兩事件之間是否是因果相關(guān)不能通過(guò)事件的時(shí)戳判定兩事件之間是否是因果相關(guān)n判定事件間因果關(guān)系的重要性判定事件間因果關(guān)系的重要性 例子：違反因果關(guān)

52、系檢測(cè) 在一個(gè)分布式系統(tǒng)中，為了負(fù)載平衡，對(duì)象是可移動(dòng)的，對(duì)象在處理器之間遷移是為了獲得所需的調(diào)用的進(jìn)程或資源。如下圖： Silberschatz, Korth and Sudarshan18.60Database System Concepts601)P1持有對(duì)象持有對(duì)象O，決定遷移到，決定遷移到P2 為獲取資源，為獲取資源，P1P1將將O裝配在消息裝配在消息 M1中發(fā)送給中發(fā)送給P22)P1收到收到P3訪問(wèn)訪問(wèn)O的請(qǐng)求的請(qǐng)求 P1將將O的新地址的新地址P2放在消息放在消息M2 中通知中通知P33)P3在在M3中請(qǐng)求訪問(wèn)中請(qǐng)求訪問(wèn)P2的的O 當(dāng)當(dāng)M3 3達(dá)到達(dá)到P2P2時(shí)，時(shí)，O不可用，故不

53、可用，故 回答一個(gè)出錯(cuò)消息回答一個(gè)出錯(cuò)消息問(wèn)題：當(dāng)問(wèn)題：當(dāng)debug該系統(tǒng)時(shí)，會(huì)發(fā)該系統(tǒng)時(shí)，會(huì)發(fā) 現(xiàn)現(xiàn)O已在已在P2上，故不知錯(cuò)在哪？上，故不知錯(cuò)在哪？P1P2P3M1On P2Where is O?遷移O到P2I dont knowM2Where is O?M3Error!Silberschatz, Korth and Sudarshan18.61Database System Concepts61n錯(cuò)誤原因：違反因果序錯(cuò)誤原因：違反因果序 P3請(qǐng)求請(qǐng)求O是發(fā)生在從是發(fā)生在從P1遷移到遷移到P2之后，但該請(qǐng)求被處理是在遷移達(dá)到之后，但該請(qǐng)求被處理是在遷移達(dá)到P2之前之前 形式地，設(shè)：形式地，

54、設(shè)： s(m)是發(fā)送是發(fā)送m的事件的事件 r(m)是接收是接收m的事件的事件 若若s(m1)s(m1)H s(m2)s(m2)，則稱消息，則稱消息m1m1因果關(guān)系上先于因果關(guān)系上先于m2m2，記做，記做m1m1C m2m2 若若m1 m1 C m2m2，但，但 r(m2) r(m2) P r(m1)r(m1)，則違反，則違反“因果關(guān)系因果關(guān)系”： 即，若即，若m1m1先于先于m2m2發(fā)送，但在同一節(jié)點(diǎn)發(fā)送，但在同一節(jié)點(diǎn)P P上上m2m2在在m1m1之前被接收之前被接收 例如，在上例中有：例如，在上例中有： M1CM3，但，但 r(M3) P2 r(M1)Silberschatz, Korth

55、and Sudarshan18.62Database System Concepts62n違反因果序檢測(cè)違反因果序檢測(cè)定義：若時(shí)戳定義：若時(shí)戳VT具有比較函數(shù)具有比較函數(shù) V滿足：滿足： e1 e1H e2 e2 iff e1.V e1.VT T V e2.Ve2.VT T則我們能夠檢測(cè)出是否違反因果關(guān)系則我們能夠檢測(cè)出是否違反因果關(guān)系nV VT T性質(zhì)性質(zhì) 1 1）因）因 H 是偏序，故是偏序，故 V 也是偏序；也是偏序； 2 2）因?yàn)楸仨氈涝谝蚬P(guān)系上每一節(jié)點(diǎn)中哪些事件是在事件）因?yàn)楸仨氈涝谝蚬P(guān)系上每一節(jié)點(diǎn)中哪些事件是在事件e e之前，故之前，故e.Ve.VT T中必須包中必須包含系

56、統(tǒng)中每一個(gè)其它節(jié)點(diǎn)的狀態(tài)含系統(tǒng)中每一個(gè)其它節(jié)點(diǎn)的狀態(tài) 這兩個(gè)性質(zhì)導(dǎo)致了向量時(shí)戳這兩個(gè)性質(zhì)導(dǎo)致了向量時(shí)戳V VT T的引入的引入Silberschatz, Korth and Sudarshan18.63Database System Concepts63n向量時(shí)戳向量時(shí)戳VT VT是一個(gè)整數(shù)數(shù)組：是一個(gè)整數(shù)數(shù)組： e.VTi=k表示在節(jié)點(diǎn)表示在節(jié)點(diǎn)i（或（或 Pi）上，因果關(guān)系上）上，因果關(guān)系上e之前有之前有k 個(gè)事件（可能包括個(gè)事件（可能包括e自己）自己） e.VT=(3,6,4,2)表示因果序：表示因果序： 在在P1上，有上，有3個(gè)事件須在個(gè)事件須在e之前之前 在在P2上，有上，有6個(gè)事件

57、須在個(gè)事件須在e之前之前 在在P3上，有上，有4個(gè)事件須在個(gè)事件須在e之前之前 在在P4上，有上，有2個(gè)事件須在個(gè)事件須在e之前之前P1P2P31P4325431215416423132eSilberschatz, Korth and Sudarshan18.64Database System Concepts64n向量時(shí)戳的意義在因果關(guān)系上，e1.VT V e2.VT表示e2發(fā)生在 e1及e1前所有的事件之后更精確的說(shuō)，向量時(shí)鐘的次序?yàn)椋?e1.VTV e2.VT iff e1.VTi e2.VTi,i=1,2,M e1.VTV e2.VT iff e1.VT VTe2.VT且e1.VTe2

58、.VT n向量時(shí)戳算法 my_VT：每個(gè)節(jié)點(diǎn)有局部的向量時(shí)戳：每個(gè)節(jié)點(diǎn)有局部的向量時(shí)戳 e.VT：每個(gè)事件有向量時(shí)戳：每個(gè)事件有向量時(shí)戳 m.VT：每個(gè)：每個(gè)msg有向量時(shí)戳有向量時(shí)戳 節(jié)點(diǎn)執(zhí)行一個(gè)事件時(shí)，將自己的時(shí)戳賦給該事件；節(jié)點(diǎn)執(zhí)行一個(gè)事件時(shí)，將自己的時(shí)戳賦給該事件； 節(jié)點(diǎn)發(fā)送節(jié)點(diǎn)發(fā)送msg時(shí)，將自己的時(shí)戳賦給所有發(fā)送的時(shí)，將自己的時(shí)戳賦給所有發(fā)送的msg。Silberschatz, Korth and Sudarshan18.65Database System Concepts65n算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： Initially：my_VT=0,0; On event e： if ( e是消

59、息是消息m的接收者的接收者 ) then for i=1 to M do /向量時(shí)戳的每個(gè)分量只增不減向量時(shí)戳的每個(gè)分量只增不減 my_VT i = max( m.VTi, my_VTi ); my_VT self +; /設(shè)變量設(shè)變量self是本節(jié)點(diǎn)的名字是本節(jié)點(diǎn)的名字 e.VTmy_VT; /給事件給事件e打時(shí)戳打時(shí)戳 if ( e是消息是消息m的發(fā)送者的發(fā)送者 ) then m.VTmy_VT; /給消息給消息m打時(shí)戳打時(shí)戳Silberschatz, Korth and Sudarshan18.66Database System Concepts66n算法性質(zhì)算法性質(zhì) 1）若）若e eH

60、 e e，則，則e.VTe.VTVT e e.VT.VT 算法確保對(duì)于每個(gè)事件滿足：算法確保對(duì)于每個(gè)事件滿足： 若若e eP e e或或e em e e ，則，則e.VTe.VTVT e e.VT.VT 2）若）若eeH e e，則，則e.VTe.VTVT e e.VT.VT pf：若若e e和和e e 因果相關(guān)，則有因果相關(guān)，則有e eH e e，即，即e e.VT.VTe2.VT1 e1.VT2e2.VT2 e1到e2及e2到e1均無(wú)路徑 2）e3在因果序上先于e1 即：e3.VTV e1.VT e1的前驅(qū)事件見(jiàn)方框P1P2P31000P43300230054134400130012000