分布式數據庫第一節基本概念一，集中式數據庫系統和分布式數據庫系統1．集中式數據庫系統，是指數據庫中的數據集中存儲在一臺計算機上，數據的處理也集中在一臺計算機上完成。2.分散式數據庫系統，采用了數據分散存儲的辦法，將數據庫分成多個建立在多臺計算機上，此時各個數據庫的管理和應用程序是分開的并獨立的，這種系統稱為分散式系統。3.分布式數據庫系統，是指數據庫數據存放在計算機網絡上的不同場地的計算機中，每一個計算機都有自治處理能力，并完成局部應用；而每一場地也參與（至少一種）全局應用程序的執行，全局應用程序可以通過網絡通信訪問系統中的多個場地的數據，這樣的系統，稱為分布式數據庫系統。4.分布式數據庫管理系統DDBMS，是分布式數據庫系統的核心，它是分布式數據庫系統中的一組軟件，負責分布式數據庫的建立、查詢、更新、復制、管理的軟件。5.局部自治性，是指有獨立處理能力并能完成局部應用。區分一個系統是分散式還是分布式系統，就是判斷系統是否支持全局。二，分布式數據庫體統的透明性分布式數據庫系統具有位置透明性和復制透明性，使用戶看到的系統如同一個集中式數據庫系統。位置透明性：是指用戶或應用程序員應當了解分片情況，但不必了解片段的存儲場地。位置透明性位于分片視圖與分配視圖之間。數據復制：是指數據在每個場地的重復存儲。復制透明性：即用戶或程序員不必關心數據庫在網絡中各個節點的數據復制情況，更新操作引起的波動由系統來處理。三，分布式數據庫的特點數據的分布性。分布式數據庫中的數據分布在網絡中的各個節點。統一性。包括數據在邏輯上的統一性和數據在管理上的統一性。邏輯上的統一性指的是分散在計算機網絡各個節點上的數據庫構成一個在邏輯上單一的數據庫，呈現給用戶的如同一個統一的集中式數據庫。管理上的統一性指的是分布式數據庫是由分布式數據管理系統統一管理和維護。透明性。用戶在使用數據庫時，與使用集中式數據庫一樣，無需知道其所關心的數據存放的位置，存儲了幾次。用戶需要關心的僅僅是整個數據庫的邏輯結構理想的分布式數據庫所具有的規則和目標局部節點自治性。與集中式DBS相比，分布式DBS中數據庫的存儲是分布性的，即數據不是存儲在一個場地。與分散式DBS相比，分布式DBS中的數據庫具有與集中式DBS相比，分布式DBS中數據庫的存儲是分布性的，即數據不是存儲在一個場地。與分散式DBS相比，分布式DBS中的數據庫具有“邏輯整體性”，即從表面看，分布式數據庫的數據分散在各個場地，但這些數據在邏輯上卻是一個整體，如同一個集中式數據庫。能繼續操作。具有位置獨立性（位置透明性）。分片獨立性（分片透明性）。數據復制獨立性（復制透明性）支持分布查詢處理。支持分布事務管理。具有硬件獨立性。具有操作系統獨立性。具有網絡獨立性具有DBMS獨立性。三，分布式數據庫系統的分類1.按照DDBMS軟件的同構度來分，分為同構和異構分布式數據庫。同構分布式數據庫（homogeneousdistributeddatabase）中，所有的站點都使用同樣的數據庫管理系統軟件，彼此了解，合作處理用戶需求。異構分布式數據庫（heterogeneousdistributeddatabase）中，不同的站點有不同的模式和不同的數據庫管理系統軟件。如果細分可以分三類：如果細分可以分三類：同構同質型DDBS：不同的站點采用同一類型的數據模型，相同的DBMS.同構異質型DDBS：不同的站點采用同一類型的數據模型，不同的DBMS.異構性DDBS：不同的站點的數據庫模型是不同的，DBMS也不同。2.按照局部自治度來分，分為：無局部自治和局部自治局部自治分布式數據庫：當局部事務允許對服務器軟件進行直接存取，則系統稱為有一定的局部自治。無局部自治分布式數據庫：當對DDBMS的存取必須通過客戶軟件，則系統稱為無局部自治；四，分布式數據庫系統的模式結構全局外模式：它們是全局應用的用戶視圖，是全局概念模式的子集。全局概念模式：定義分布式數據庫中數據的整體邏輯結構。分片模式：每一個全局關系可以劃分為若干個不相交的部分，每一個部分稱為一個片斷。分片模式就是定義片段及全局關系到片斷的映像。（1：M）分布模式：每一個片斷物理上可以分配到網絡不同的節點上，分布模式定義片斷的存放節點。局部概念模式：被分配到某個場地上的邏輯片斷的集合。局部內模式：局部內模式是DDB中關于物理數據庫的描述。這種6層模式結構具有顯著的特征：數據分片和數據分布概念的分離，形成了“數據分布獨立性”概念。數據冗余的顯式控制。數據在各個場地的分配情況在分配模式中一目了然，便于系統管理。局部DBMS的獨立性。這個特征也稱為：“局部映射透明性”。分布式數據庫的優點：具有靈活的體系結構。適應分布式管理和控制機構。經濟性能優越。系統可靠性高。局部應用的響應速度快。可擴展性好，易于集成現有系統。分布式數據庫的缺點系統開銷大，主要在通信部分。復雜的存取結構，集中式系統的存取數據技術，在分布式不再適用。數據的安全性和保密性較難處理。第二節分布式數據庫系統的體系結構分布式數據庫數據存儲可以從兩個角度考察：分片和分配。一，分布式數據庫數據分配：數據分配就是數據在計算機網絡各個場地上的分配策略，也稱為數據分布。1.數據分配的策略集中式：所有數據均安排在同一場地。分割式：數據在每個場地重復存儲。全復制：數據在每個場地重復存儲。混合型：數據庫分成若干個可相交的子集，每一個子集安置在一個或多個場地上，但每一個場地未必保存全部數據。四個評估因素：存儲代價、可靠性、檢索代價、更新代價。存儲代價和可靠性是一對矛盾的因素。檢索代價和更新代價，是一對矛盾的因素。二，數據分片數據分片是指數據存放單位不是全部關系，而是關系的一個片斷，也就是關系的一部分。分布式數據庫中的數據可以被復制在網絡場地的各個物理數據庫中，數據分片是通過關系代數的基本運算實現的。1.數據分片包括三種：水平分片：按一定的條件把全局關系的所有元組劃分為若干個不相交的子集，每個子集為關系的一個片斷。垂直分片：把一個全局關系的屬性集分成若干個子集，并在這個子集上作投影運算，每個投影為一個垂直分片。混合分片：將水平分片和垂直分片方式綜合起來使用，則為混合分片。2.數據分片應遵循的原則完備性條件：必須把全局關系的所有數據映射到各個片斷中，決不允許發生屬于全局關系的某一個數據不屬于任何一個片斷。重構條件：劃分所采用的方法必須確保能夠由各個片斷重建全局關系。（指垂直分割）不相交條件：要求一個全局關系被劃分后，得到的各個數據片斷互不重疊。（指水平劃分）。三，分布式數據庫系統的體系結構全局外模式：它們是全局應用的用戶視圖，是全局概念模式的子集。全局概念模式：它們定義了分布式數據庫中所有數據的邏輯結構。分片模式：定義了片斷以及全局關系與片斷之間的映像。這種映像是一對多的，即每個片斷來自一個全局關系，而一個全局關系可分為多個片斷。分配模式：片斷是全局關系的邏輯部分，一個片斷在物理上可以分配到網絡上的不同場地上，分配模式根據分配策略的選擇定義片斷的存儲場地。四，分布的透明性分布透明性，也稱為分布的獨立性，是指用戶不必關心數據的邏輯分片，不必關心數據存放的物理位置等細節，也不必關心各個場地上數據庫的數據模型。分片的透明性：用戶無需知道關系是如何分片的。位置的透明性：用戶不必知道數據存放的物理位置。局部數據庫模型的透明性：這個透明性位于分配視圖與局部概念視圖之間，指用戶或應用程序要了解分片及各個片斷存儲的場地，但不必了解局部場地使用了何種數據模型。（復制透明性：用戶不必關系復制了什么數據對象，也不必關系副本的存放位置）分布式數據存儲（復制和分片）對于一個要存儲到數據庫中的關系R，在分布式DBS中有兩種方法：（1）復制：系統維護這個關系的幾個副本，各個副本存儲在不同的場地。（2）分片：把關系劃分為幾個片斷，每個片斷存儲在不同的站點上。分片和復制可以組合，一個關系可以分成幾個片，每個片有幾個副本。數據復制如果關系r被復制，則在兩個以上關系中存在副本，極端情況下是每個場地都有一個副本，稱為全復制（fullreplication）數據復制的優點可用性。當包含關系r的站點之一發生故障，系統仍可以運行。增加的并行性。由于有多個副本，增加了查詢操作的并行性。增加了更新的開銷。復制的缺點復制可以提高read操作的性能，但對數據更新的開銷增大，一致性維護復雜。如何保證兩個站點沒有對不同的數據項實用相同的名字？使用中央名字服務器（nameserver）注冊，確保名字不重復使用在名字的前面加上站點的標識符以示卻別。但破壞了位置的透明性。五，分布式數據庫管理系統distributeddatabasemanagementsystem分布式數據庫管理系統的結構：LDBMS。局部場地上的數據庫管理系統，其功能是建立和管理局部數據庫，提供場地自治、執行局部應用及全局查詢的子查詢。GDBMS。全局數據庫管理系統，其功能是提供分布透明性，協調全局事務的執行，協調各局部DBMS以完成全局應用，保證數據庫的全局一致性，執行并發控制，實現更新同步，提供全局恢復功能。全局數據字典。存放全局概念模式、分片模式、分布模式的定義及各模式之間的映像的定義。存放用戶存取權限、數據庫安全性，完整性約束條件。通信管理（CM）。在分布數據庫各場地之間傳送消息和數據，完成通信功能。對全局控制有幾種方式：全局控制集中的DBMS：全局控制成分GDBMS集中在一個場地上。全局控制分散的DBMS：全局控制成分GDBMS分散在各個場地上。全局控制部分分散的DBMS：控制成分GDBMS分散在某些場地上。第三節分布式事務處理復習：事務的ACID特性原子性atomicity：事務是數據庫的邏輯工作單位，事物的操作要么都做，要么都不做。一致性consistency：事務執行的結果必須是使數據庫從一個一致性狀態轉換為另一個一致性狀態。隔離性isolation：數據庫中一個事務的執行同其他事務的執行是隔離的，互不干擾。持續性durability：事務一旦提交，則對數據庫中數據的改變就是永久的，以后的操作或故障不會對事務的操作產生影響。局部事務localtransaction：僅訪問和更新一個局部數據庫的事務。全局事務globaltransaction：訪問和更新多個局部數據庫中數據的事務。一，分布式事務的系統結構組成：事務管理器和事務協調器（1）事務管理器，transactionmanager，管理那些訪問存儲在一個局部站點中數據的事務的執行（即可以是局部事務，也可以是全局事務）。維護一個用戶恢復的日志。參與適當的并發控制，以協調在該站點執行的事務的并發執行。（2）事務協調器transactioncoordinator，協調該站點上發起的各個不同事務的執行（即有全局事務，也有局部事務）。（集中式DBS不需要事務協調器）啟動事務的執行。將事務分裂為一些子事務，并將這些子事務分派到恰當站點上執行。協調事務的終止，其結果是事務在所有站點上都提交或都終止。復習集中式數據庫事務的故障：復習集中式數據庫事務的故障：1.事務內部故障（包括可預期的和不可預期的）2.系統故障（軟故障）3.介質故障（硬故障）二，分布式數據庫事務的系統故障模式分布式系統的故障包括集中式的故障類型（事務內部故障、系統故障、介質故障、其他故障）外，分布式系統另外還有一些基本故障類型：站點故障、消息丟失、通信鏈路故障、網絡分割。故障恢復的難度，從小到大依次為：一是節點故障；二是節點故障和消息丟失，但無分區故障；三是節點故障、消息丟失、分區故障。三，兩段提交協議為了保證事務的原子性，就必須做到事務T要么在所有站點上都提交，要么都終止。為了保證這一原子特性，T的事務協調器必須執行一個提交協議。兩端提交協議two-phasecommitprotocol，2PC是最簡單和使用最廣泛的提交協議。設定從一個站點Si發起一個事務T，并設Si的事務協調器是Ci階段1。Ci將記錄<prepareT>寫入日志中，并存入穩定存儲器中。發送一條prepareT到所有站點。各站點接收到此消息，先加入到日志中去。當站點事務管理器確定如果不愿意提交屬于該站點的事務，事務管理器把記錄<noT>寫入日志，并向Ci發送一條abortT的消息。當站點事務管理器愿意提交屬于該站點的事務，則事務管理器把記錄<readyT>寫入日志，并向Ci發送一條readyT的消息。階段2。當Ci發送prepareT消息一段預定時間間隔或者收到所有站點的回復時，Ci就可以確定該事務是提交還是終止。如果Ci收到所有站點的readyT消息，則將記錄<commitT>寫入日志，并向所有參與站點發送<commitT>消息。如果Ci收到有一個站點的abortT消息，則將記錄<abortT>寫入日志，并向所有參與站點發送<abortT>消息。由于事務的提交要求全體站點一致，只要有一個站點回答abortT消息，則事務T就被終止。只有全體站點響應readyT則事務被提交。并把記錄寫入日志文件。當所有站點收到commitT消息后，將<commitT>寫入日志文件，并提交該事務。兩階段提交的故障處理1.參與站點的故障failureofaparticipatingsite如果協調器Ci監測到某個站點發生故障，如果該站點在用readyT消息回答Ci之前發生故障，則協調器認為該站點是用abortT消息回答的，則事務終止。如果該站點是在發送readyT之后發生故障的，則協調器按照通常方式提交協議的剩余部分，忽略該站點的故障。此時，該站點故障恢復后，檢查日子文件，根據日志文件作以下操作：日志文件包含<commitT>記錄。執行redo(T)。日志文件包含<abortT>記錄。執行undo(T)。日志文件包含<readyT>記錄。詢問Ci確定T的最終結果，執行相應的redo(T)或者undo(T)操作。2.協調器故障failureofthecoordinator如果協調器在為事務T執行提交協議的過程發生故障，則必須根據參與站點的日志決定T的最終結果。如果某個活躍站點日志中包括<commitT>記錄，則T必須被提交。如果某個活躍站點日志中包括<abortT>記錄，則T必須被終止。如果某個活躍站點日志中不包含<readyT>記錄，則T被終止。如果上述情況都不成立，則所有活躍站點都包含<readyT>記錄，還有別的站點包含<commitT>或<abortT>記錄，因此必須等待Ci故障恢復，這段時間，其他事務必須被迫等待，因此發生阻塞。3.網絡分割networkpartition協調器同他的參與者處于一個分區，這種情況故障對提交協議沒有影響。協調器和他的參與者處在不同分區，不在協調器分區的站點執行處理協調器故障的協議；在協調器分區的執行一般提交協議。因此，2PC的主要缺陷在于發生協調器故障時可能導致阻塞，這種情況必須等到Ci恢復才能做出是提交還是終止T的決定。恢復與并發控制為了處理分布式提交協議（2PC或3PC），恢復過程必須對疑問十五進行特殊對待：疑問事務是發現有<readyT>日志記錄，但未發現<commitT>或<abortT>的日志記錄的事務。如果協調器發生故障，而任何站點都沒有關于未完事務的狀態（提交/終止），在使用2PC時就存在著恢復被阻塞的可能。為了克服這個問題，恢復算法通常提供對在日志中記載封鎖信息的支持（假設這里用于并發控制），此時所寫的日志記錄不再是<readyT>，而是<readyT,L>，其中L是寫入日志記錄時事務T所有的寫鎖的列表。當恢復時，對所有的寫鎖需要從新獲取。當所有疑問事務的鎖從新獲取完成后，即使疑問事務的提交-終止狀態確定之前，該站點的事務處理就可以開始了。疑問事務的提交和回滾與新事務的執行是并發的。這樣，站點的恢復就會加快，并且不會產生阻塞。三，三階段提交3PC三階段提交是兩階段提交的擴展，在某種前提條件下可以避免阻塞問題，只有在大于k個站點發生故障時才發生阻塞。如果網絡分割會產生多于k個站點，仍然會發生阻塞。3PC協議由于開銷太大，沒有被廣泛使用。四，并發控制并發控制是為了保證事務的原子性，是保證多個事務的高效、正確的執行，是分布式事務管理的基本任務之一。在數據庫系統中，事務是以發出讀操作和寫操作原語的方式來存取數據的，事務的并發控制就是保證事務的并發操作正確執行。在實際應用中，可以采用鎖的方法和時間戳方法來實現事務的可串行化調度。1.鎖模型基本思想原則：事務對任何數據的操作必須先申請該數據項的鎖，只有申請到鎖以后，即加鎖成功以后，才可以對數據項進行操作。操作完成以后，要釋放已申請的鎖。通過鎖的共享與排斥的特性，實現事務的可串行化。對于基本鎖，不區分共享鎖和排他鎖，有可能降低事務的并發程度。讀鎖，共享鎖：是對數據項進行讀操作時加的鎖，可共享操作。寫鎖，排他鎖：是對數據項進行寫操作時加的鎖，不可共享操作。讀鎖寫鎖讀鎖共享排他寫鎖排他排他兩段鎖協議：任何事務對數據項的操作先加鎖，加鎖的方法是事務中全部加鎖操作在第一個解鎖操作之前完成。因此，加鎖和解鎖分布在事務的兩個階段，故稱為兩段鎖協議，即2PL協議。在集中式數據庫中,2PL可以保證事務可串行化調度。在分布式數據庫系統中，也遵循兩段鎖協議，實現分布式事務的并發處理。因此，全局事務遵循2PL協議時，各子事務也遵循2PL協議。2.時間戳模型對每一個事務在激活是分配一個時間戳，唯一標識該事務和事務激活的順序。事務對數據項的操作時，先把自己的時間錯賦予該數據項。當事務間發生沖突時，時間戳小的先執行，時間戳大的后執行。當一個事務的時間戳小于另一個已經執行的事務時，該事務被終止，并重新啟動，且賦予一個新的時間戳。時間戳分為讀時間戳和寫時間戳。在鎖的方式中，當兩個以上的事務互相鎖住對方所需的資源時，系統就發生了死鎖。因此需要有死鎖檢測和消除機制及死鎖防治機制，進行死鎖后處理和預防。而時間戳協議中，事務要么繼續執行，要么終止，重新獲得時間戳，因此不會發生死鎖。但重新啟動頻繁。時間戳的算法有兩種：基本時間戳方法和保守時間戳方法。第四節分布式查詢分布式查詢有兩個新特點：網絡通信速率較低，因此考慮查詢處理時各節點之間通信造成的明顯時間延遲。由于各節點有獨立的計算機，有了在各臺計算機上進行并行處理各個子查詢部分，以及在各節點之間進行并行傳送數據的可能性。分布式數據庫系統中的查詢處理過程：由全局數據庫管理系統在查詢產生節點時對查詢進行詞法和語法分析，生成查詢樹。對全局查詢樹進行變化，查詢分解，把查詢分解成若干個子查詢，確定處理子查詢的運算次序和節點。對子查詢進行優化和執行。子查詢結果的匯總和處理。一，全局查詢樹的變換為了提高查詢執行效率，可對全局查詢樹進行下述變換。用片斷替換查詢樹中的全局關系。水平分割用“并”操作，垂直分割用“聯結”操作。盡可能把選擇、投影等一元操作推向查詢樹的葉端。減少查詢中間結果，降低網絡數據傳輸。合并公共子表達式。減少查詢次數。消除空的關系和冗余度。使用邏輯化簡規則消除空關系和冗余度。移去無用的垂直葉片，減少聯結操作和網絡傳輸。二，副本的選擇和多副本的更新策略。為了提高訪問的局部性和系統的可用性，關系和片斷常常設置多個復本，分布于不同的節點，這樣，查詢處理時就存在復本選擇的問題：盡可能提高訪問的局部性，減少遠距離訪問。盡可能減少通信開銷，尤其要減少大量數據傳輸。適當考慮節點負荷的平衡。雖然多復本可以提高訪問的局部性和系統的堅固性，但是更新時，必須保證多復本的一致性：在事務提交前更新全部復本。（只要有一個復本未更新，則事務就失敗）立即更新有效節點的復本，失效節點復本留待修復后更新。主復本法。指定一個復本為主復本，其他為副本。更新時只更新主復本，所有副本根據主復本廣播的內容進行更新。主復本和副本之間可能出現不一致。為此可以讓每個副本附加一個版本號，如果主復本的版本號同副本的版本號相同，則可以讀副本，否則，讀主復本或待更新后再度副本。快照法。是指數據在某一時刻的狀態，他不隨數據庫中的數據更新而即時更新。如統計報表中的“截止×月×日止”。三，查詢樹的分解查詢樹的分解一般采用后序遍歷法。全局優化的核心問題是執行分布式聯結的策略。四，分布式查詢通常采用半聯結的查詢優化策略有時候作聯結操作時，并不需要將整個關系（或片斷）都傳送到對方，只要傳送聯結時與對方匹配的元組就夠了。半聯結可以減少節點間的數據傳輸量和運算量。在廣域網中，通信開銷是主要矛盾，通常采用半聯結方式的查詢優化策略。五，查詢優化應考慮的問題優化的代價函數對系統的影響：響應時間。系統的吞吐量。總的局部資源利用率（CPU利用率、FO操作等）網絡通信量。網絡中各節點負載的均衡分布。在集中式數據庫系統中，已經建立的優化算法通常是以耗費的CPU時間和FO操作來衡量代價函數的。分布式數據庫系統則比較復雜，全局優化執行方案受下面因素的影響：多種復本的選擇。多種執行次序。對于多元聯結個并操作，利用結合律和交換律組成多種次序。多個執行地點。多種聯結方法。分布式數據庫的查詢優化按實現方法可以分為：靜態優化法和動態優化法。靜態優化法：在事務執行前進行優化。動態優化法：在事務執行過程中進行優化，優化質量高于靜態優化法。第五節網絡環境下的數據庫系統的設計實施任務：定義全局數據庫的概念模式。設計物理數據庫，將概念模式映射到存儲區域并確定適當的存取方法。設計分片。確定將全局關系進行水平、垂直、或混合劃分，以便分配。設計片段的分配。確定片斷分配到各個場地的分配情況和復制的片斷。一，數據的分布設計1．數據劃分原則和分片方法按DDB外部特征來劃分。如按照部門來劃分。按DDB的內部特征來劃分。對DDB的組成性質劃分后仍應保持其原有的性質。劃分后個邏輯關系必須遵守下列原則：完整性原則。不允許某些數據屬于全局但不屬于任何一個片斷。可重構原則。對于水平劃分的可利用‘并操作’重構，對于垂直劃分的，可利用聯結操作重構。不相交原則。不允許一個全局關系的某些數據即屬于該全局關系的某一個片斷，同時又屬于該關系的另一個片斷（適用于水平劃分）。（3）分片方法：水平分片、垂直分片和混合分片。水平分片：按一定的條件將關系按行（水平方向）劃分為不相交的若干子集，每個子集就是一個片斷。垂直分片：將關系按照列（垂直方向）分為若干子集，每個子集就是一個片斷。混合分片。采用水平分片和垂直分片相結合的方法進行劃分。2.數據分配的策略和一般準則DDB中全局關系經邏輯劃分后，其分配通常由4種類型。集中型。數據雖經劃分，但所有邏輯片斷仍然存放在一個場地上。分割型。數據劃分后，所有邏輯片斷各自分配到一個場地所有場地上分配的知識全局關系的一個子關系。全復制型。數據被劃分后，所有邏輯片斷在每個場地上均重復設置。混合型。數據被劃分后的邏輯片斷根據需要分配。共享的片斷重復設置，高度私用的片斷只設置在所需的片斷。對各種劃分方法的評估。4個評估因素:存儲代價、可靠性、更新代價、檢索代價。集中型：存儲代價：無；可靠性：差；更新代價：無；檢索代價：高。分割型：存儲代價：無增加；可靠性好；更新代價：無；檢索代價：低。全復制型：存儲代價高；檢索代