分布式數(shù)據(jù)庫系統(tǒng)的設計.ppt

1,分布式數(shù)據(jù)庫系統(tǒng)的設計 及 RMI 簡介,姚易 簡婕 王偉,2,課本知識目錄,2.1 分布式數(shù)據(jù)庫系統(tǒng)設計概述 2.5 自底向上設計分布式數(shù)據(jù)庫 2.2 自頂向下設計分布式數(shù)據(jù)庫 2.3 DATAID-D方法 2.4 實例研究：飛機訂票系統(tǒng),3,2.1分布式數(shù)據(jù)庫系統(tǒng)設計概述,1 分布式數(shù)據(jù)庫系統(tǒng)定義 2 分布式數(shù)據(jù)庫設計的目標 3 分布式數(shù)據(jù)庫系統(tǒng)設計的內(nèi)容 4 分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法 5 分布式數(shù)據(jù)庫設計的方法,4,2.1.1分布式數(shù)據(jù)庫系統(tǒng)定義,分布式數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)是物理分布在用計算機網(wǎng)絡連接起來的各個站點上；每一個站點是一個集中式數(shù)據(jù)庫系統(tǒng)，都有自治處理的能力，完成本站點的局部應用；而每個站點上的數(shù)據(jù)并不是互不相關的，它們構成一個邏輯整體，統(tǒng)一在分布數(shù)據(jù)庫管理下，共同參與并完成全局應用，并且分布式數(shù)據(jù)庫系統(tǒng)中的這種“分布”對用戶來說是透明的，也就是說，本地與遠程結合的“接縫”是被隱蔽的，用戶幾乎感覺不到遠程與本地結合的接縫的存在，即“一個分布式系統(tǒng)應該看起來完全像一個非分布系統(tǒng)”。,5,2.1.2分布式系統(tǒng)設計的目標,1 分布式數(shù)據(jù)庫的本地性或近地性 盡可能減少站點之間的通信次數(shù)和通信量 2 控制數(shù)據(jù)的適當冗余 考慮到本地性，并發(fā)性，可靠性，一致性，開銷等 3 工作負荷分布 充分利用每個站點計算機的能力和資源提高性能 4 存儲的能力和費用,6,2.1.3分布式數(shù)據(jù)庫系統(tǒng)設計的內(nèi)容,相類似于集中式數(shù)據(jù)庫設計：數(shù)據(jù)庫+應用 數(shù)據(jù)庫設計：全局模式設計+局部模式設計 關鍵點：全局模式如何劃分并映射到站點 新設計問題：數(shù)據(jù)的分片、片段的位置分配 需求增加： 各個應用的發(fā)出點 /各個應用在每個站點被激活 的頻率 /各個應用對訪問對象的每個數(shù)據(jù)對象的訪問次 數(shù)，類型和統(tǒng)計分析,7,2.1.4分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法,組合法：自底向上的創(chuàng)建方法,8,2.1.4分布式數(shù)據(jù)庫系統(tǒng)的創(chuàng)建方法,重構法：自頂向下的創(chuàng)建方法,9,2.1.5分布式數(shù)據(jù)庫設計的方法,自頂向下方法：從頭開始設計 自底向上方法：聚集現(xiàn)存數(shù)據(jù)庫 然而！ 許多情況下，設計者都是一部分使用自頂向下方法，另一部分使用自底向上方法 GO ON：分別詳述這些方法,10,2.2自底向上設計分布式數(shù)據(jù)庫,1 構造全局模式的設計問題 2 構造全局模式的解決方法 3 自底向上綜合的一個示例,11,2.2.1構造全局模式的設計問題,在異構分布式數(shù)據(jù)庫設計中特別重要： 1 選擇公有數(shù)據(jù)庫模型來描述數(shù)據(jù)庫的全局 模式 2 把每個站點上的本地模式翻譯成公有的數(shù)據(jù)模型 3 把各站點上本地數(shù)據(jù)模式集成一個公有的全局模式,12,2.2.2構造全局模式的解決方法,1 識別相似性 2 識別沖突： 命名沖突/域差異/定標差異/結構差異 3 處理操作期間的不一致性 4 經(jīng)典解法是生成三個實體： 一個具有共同屬性 另兩個具有非相交屬性,13,2.2.3自底向上綜合的一個示例,問題： 假設已存在兩個飛機訂票系統(tǒng)A和B，可供查詢各自班機的可用情況。二者有不同的概念模型?，F(xiàn)需要將這兩個系統(tǒng)合為一個分布式數(shù)據(jù)庫系統(tǒng)，以便從兩個公司的任一辦公室能查詢班機的可用情況。 結果： 綜合后建立起來的全局模式中，有一個概括分層被用來表示兩個子類型班機A和班機B。值得注意的是，對兩個局部模式，應以不同的方法翻譯一個需要有關班機從一給定機場起飛的信息的查詢。,14,2.2.3自底向上綜合的一個示例,15,2.2.3自底向上綜合的一個示例,16,2.2.3自底向上綜合的一個示例,17,2.3自頂向下設計分布式數(shù)據(jù)庫,1 自頂向下設計分布式數(shù)據(jù)庫的步驟和內(nèi)容 2 數(shù)據(jù)的分片設計 3 數(shù)據(jù)庫片段的位置分配設計,18,2.3.1步驟和內(nèi)容,集中式：需求分析 概念設計 邏輯設計 物理設計 分布設計：位于邏輯設計與物理設計之間，以一個全局的與站點無關的模式作為輸入，以產(chǎn)生分布式數(shù)據(jù)庫各站點的子模式為結果輸出，包括數(shù)據(jù)的分片設計和片段的位置分配設計 分片：把一全局對象（實體或關系）細分成若干邏輯片段的過程 分配：把各片段映射到一個或多個站點的過程，片段是最合適的數(shù)據(jù)分配單位,19,2.3.2數(shù)據(jù)的分片設計,基本目標： 產(chǎn)生一個對全局數(shù)據(jù)合適的劃分方案。這種方案得到的片段作為分布式數(shù)據(jù)庫中數(shù)據(jù)的分配和存儲單位，不但能夠減少應用中的操作量，而且能夠?qū)τ趹镁哂凶畲罂赡艿谋镜匦?，即使得各片段位于其使用最多的站點，或者說，使用絕大多數(shù)應用所使用的數(shù)據(jù)位于該應用的原發(fā)始點。 當分片的好處太小，不足以補償分片造成的開銷時，不必要分片,20,分片方法：水平分片 垂直分片 混合分片 遵守規(guī)則：完整性 可重構 不相交 水平分片：對全局關系執(zhí)行“選擇”操作，可以具體分為初始分片和導出分片兩種 垂直分片：對全局關系執(zhí)行“投影”操作，組之間必須只在某個鍵屬性上重疊，而垂直群集的組在其他屬性上也可以重疊,2.3.2數(shù)據(jù)的分片設計,21,數(shù)據(jù)片段位置分配的方法 1 非冗余分配： 估算每種分配后選擇最佳冗余分配： 2 所有得益站點法： 非復制問題的解+若干唯一復本 3 附加復制法： 非復制問題的解+從最有益處起逐步附加復本，直至無明顯好處,2.3.3數(shù)據(jù)庫片段的位置分配設計,22,數(shù)據(jù)片段分配的費用和得益估算 假定 i 表示片段的下標 j 表示站點的下標 k 表示應用的下標 Fkj 表示應用k在站點j上被激活的頻率 Rki 表示應用k被激活一次，對片段i進行檢索訪問的次數(shù) Uki表示應用k被激活一次，對片段i進行更新訪問的次數(shù) Nki= Rki+ Uki表示應用k被激活一次，訪問片段i的總次數(shù),2.3.3數(shù)據(jù)庫片段的位置分配設計,23,水平分片情況 1 非冗余分配：將片段分配到訪問次數(shù)最多的站點,2.3.3數(shù)據(jù)庫片段的位置分配設計,2 所有得益站點：本站點的應用的檢索訪問費用總比任何一個其他站點發(fā)出的應用對該片段進行更新訪問的費用要低,3 附加復制法：Dj表示片段Ri冗余度；Fi表示Ri在每個站點都復制的得益,24,2.3.3數(shù)據(jù)庫片段的位置分配設計,垂直分片情況 假定把站點r上的關系R垂直分成兩個片段Rs和Rt，并將Rs和Rt分別分配在站點S和t,然后將應用分組并估算它們的利益情況,25,2.3.3數(shù)據(jù)庫片段的位置分配設計,垂直分片情況 1 應用組As:自站點s發(fā)出，它們只使用Rs,因而是本地應用，得益,2 應用組At:自站點t發(fā)出，它們只使用Rt,因而是本地應用，得益,3 應用組A1:自r發(fā)出，原使用Rt或Rs,現(xiàn)在需要一次額外的遠程訪問，損失：,4 應用組A2:自r發(fā)出，原來使用R，現(xiàn)在需要兩次額外的遠程訪問，損失：,5 應用組A3:與r,s,t不同，訪問Rs和Rt, 現(xiàn)需一次額外的遠程訪問，損失：,26,2.3.3數(shù)據(jù)庫片段的位置分配設計,垂直群集情況 與垂直分片的情況類似，只是要注意檢索及更新要同時涉及到Rs和Rt了 GO ON： 詳述自頂向下法中的一個具體方法：DATAID-D方法 以飛機訂票系統(tǒng)為例講述分布式數(shù)據(jù)庫系統(tǒng)設計,27,2.4 DATAID-D 方法,2.4.1 DATAID-D方法概述 2.4.2 分布要求分析階段 2.4.3 分布設計階段,28,2.4.1 DATAID-D方法概述,是自頂向下設計分布式數(shù)據(jù)庫的一個典型方法， 由意大利米蘭工業(yè)大學提出 作為集中式數(shù)據(jù)庫設計DATAID-1方法論的擴充而 構造的 集中式數(shù)據(jù)庫設計的四個階段 需求分析，概念設計，邏輯設計和物理設計 增加兩個階段：分布要求分析階段和分布設計階段,29,DATAID-D 方法的分布式數(shù)據(jù)庫設計步驟,30,主要設計步驟簡要概述,需求分析 需求分析簡單地說就是分析用戶的要求 概念設計 將需求分析得到的用戶需求抽象為信息結構 即概念結構設計，如畫-圖 邏輯設計 將E-R圖轉(zhuǎn)換為相應的數(shù)據(jù)模型相符合的 邏輯結構，如關系模型,31,主要設計步驟簡要概述,物理設計 確定數(shù)據(jù)庫的物理結構； 對物理結構進行評價 分布要求分析 收集關于分布的信息，如水平分片的劃分謂詞 每一應用在各站點激活的頻率等 分布設計 產(chǎn)生全局數(shù)據(jù)的分片模式和片段的位置分配模 式，分配模式描述了分配在各站點上的數(shù)據(jù)情況,32,2.4.2 分布要求分析階段,目的：收集以后用于推動分布設計所需要 的信息 輸入：用戶對分布的要求和全局數(shù)據(jù)概念 模型與操作模式 輸出：應用的頻率表，實體的劃分表和 數(shù)據(jù)與應用的極化表,33,三種類型的表,1.頻率表 給出各站點上每一應用激活次數(shù)這里假設所有應用在 所有站點上都有可能執(zhí)行 2.劃分表 指明可使用于模式中各實體的潛在水平分片規(guī)則 3.極化表 基于定量分析方法來說明分片如何影響著應用處理的本地性一個極化值表指明由一給定站點發(fā)出的一給定應用訪問一給定片段的概率,34,2.4.3 分布設計階段,目標：從全局數(shù)據(jù)模式，邏輯訪問表和分 布要求出發(fā)，將數(shù)據(jù)分配在站點上 輸出：各站點的邏輯模式和邏輯訪問表 包括四個階段： 分片設計，非冗余分配，冗余分配和局部模式的重新構造,35,分片設計,分片設計對實體進行水平分片和垂直分片，以便為以后設計階段確定可能的分配單位要使每一片段是一個合適的分配單位，就必須保證由各站點上執(zhí)行的各應用，大約以同一方式（即相同頻率）訪問在片段中的事例（元組） 分片設計主要包括邏輯判定，進行邏輯判定時，從極化表中選擇某些謂詞，并用它們定義邏輯片段,36,目標：是把各片段映射到使用該片段最多的站點上 問題：如何識別最頻繁訪問該片段的站點？ 方法：根據(jù)頻率表與極化表，采用“最佳適應法”，令 Fij應用i使用站點j的頻率； Pijk應用i使用站點j時片段k的極化值 于是從站點j訪問片段k的次數(shù)給出如下： 因此，片段k被分配到站點j，使得,非冗余分配,37,冗余分配,冗余分配的執(zhí)行是使用“貪婪”啟發(fā)式，可以采用上面已經(jīng)闡述過的“所有得益站點法” 或采用 “附加復制法”就是初起使用非冗余分配，在每次迭代時，計算因增加一副本使其變成本地的檢索訪問的得益與為維護該副本一致性所需要的附加遠程修改訪問的損失之差值這個數(shù)字是個較大的正數(shù)時，把該片段的副本存儲到得益站點，否則就不增加,38,局部模式重新構造,局部模式的重新構造是重新構造片段分配站點上的局部模式，這一階段也負責ER全局模型中的聯(lián)系分配大多數(shù)聯(lián)系是作為對應實體標識符間的結合實現(xiàn)的，DATAID-D方法建議把聯(lián)系放置在具有最大基數(shù)性的實體或片段的站點上，使得必須傳送的實體標識符盡可能少,39,2.5 實例研究：飛機訂票系統(tǒng),2.5.1 實例研究概述 2.5.2 飛機訂票系統(tǒng)中的分布要求分析 2.5.3 飛機訂票系統(tǒng)中的分布設計,40,2.5.1 實例研究概述,這是在飛機訂票系統(tǒng)中應用DATAID-D方法進行分布式數(shù)據(jù)庫設計的例子 問題： 我們要研究的訂票系統(tǒng)維護一個分布在三個站點（即機場1、2、3）上的數(shù)據(jù)庫，為使這個系統(tǒng)更形象，考慮在美國開業(yè)的一家公司。其中：1=丹佛，代碼為CO，位于美國的西部；2=紐約，代碼為NY，在北部；3=亞特蘭大，代碼為GA，在南部。數(shù)據(jù)庫存儲有關機場規(guī)程、班機調(diào)度、班機可用情況和旅客訂票等數(shù)據(jù)。,41,飛機訂票數(shù)據(jù)庫的全局數(shù)據(jù)模式,42,飛機訂票數(shù)據(jù)庫的全局操作模式,43,訂票應用圖2.7(a),每當一新的旅客想預定一班機的機票時，該應用就被激活。在這種情況下，訪問數(shù)據(jù)庫中的起飛與到達的機場，起飛與到達時間和班機日期。這些屬性在圖中標以k，表明它們被用作訪問數(shù)據(jù)的關鍵詞。箭頭表明經(jīng)由兩個關系“從”與“到”訪問從機場實體到班機實體的進行情況。實體左下角和右下角中的數(shù)字分別表示示例總數(shù)和由應用選擇的平均示例數(shù)。一旦確定了班機，就建立旅客實體的一個新的示例及聯(lián)系訂票的一個示例；關于旅客名字、電話和種類（對應于票價）的數(shù)據(jù)被寫入數(shù)據(jù)庫。 注意：可用座位屬性先讀后寫（“o，w”; o表示輸出，w表示寫入）。 問題：示例總數(shù)和由應用選擇的平均示例總數(shù)有何異同？ 解答：以班機實體為例，圖中的數(shù)字2000，表示的是班機示例的總的樣本空間數(shù)，假設在該樣本中，a應用發(fā)生的次數(shù)為n1，b應用發(fā)生的次數(shù)為n2，c應用發(fā)生的次數(shù)為n3，那么就有如下等式： 2000=3n1+n2+30n3 其中：3，1，30分別為應用a，b，c選擇的平均示例數(shù),44,登記應用圖2.7(b),凡旅客實際登機時，先執(zhí)行登記任務。根據(jù)旅客名字和班機號與日期，查明有關旅客和班機的示例（”k“屬性），然后，顯示檢索種類信息（”o“），并根據(jù)這一信息和班機座位圖，將一座位號分配給旅客，寫入座位圖和座位號屬性，以及旅客的檢查行李號（即托運行李的票據(jù)號）。,45,起飛應用圖2.7(c),從機場起飛時的應用，產(chǎn)生描述即將離開該機場的30架班機的起飛信息的報告并顯示在TV監(jiān)視器上。機場符號和當前日期與時間用于標識所涉及的機場和班機實體。對各次班機，從數(shù)據(jù)庫中抽取班機號、起飛時間、出入口、延期和目的地機場符號與城市，使用”到“聯(lián)系來確定關于目的地機場的信息。 在了解這些應用的操作模式之后，對每個實體，需估算應用的定量數(shù)據(jù)，建立起邏輯訪問表。以實體班機為例簡要介紹一下，表2.1展示了實體班機的邏輯訪問表。,46,實體訪問表：班機,表中的列對應于操作，行對應于實體屬性，矩陣元素表示在對象上所執(zhí)行的動作類型（”o“，”w“，”k“）。由RA（聯(lián)系訪問）表示的行指明一個聯(lián)系是否用于訪問實體，而由AN（訪問數(shù)）表示的行給出了在該操作中涉及的示例總數(shù)。,47,2.5.2 飛機訂票系統(tǒng)中的分布要求分析,在前面，我們已經(jīng)了解到分布要求分析階段的輸出是三個表：頻率表、劃分表、極化表，那么，這三個表的具體內(nèi)容到底是什么呢？ 表2.2頻率表中說明了在節(jié)點1（丹佛）、2（紐約）、3（亞特蘭大）上全局操作模式所描述的應用a，b，c的頻率。,48,基本劃分表,在這里給出的是實體機場和旅客的基本劃分表。設計者將區(qū)域?qū)傩赃x作為機場實體的劃分準則，而將電話號碼前三位（區(qū)域碼）選作為旅客實體的劃分屬性。謂詞選擇性用每一可能的劃分屬性值給出該實體元組的百分數(shù)。,49,導出劃分表,導出劃分，顧名思義，是在基本劃分的基礎上產(chǎn)生的。在這里我們只考慮基于機場劃分為區(qū)域的這個基本劃分可能產(chǎn)生的導出劃分。表2.4中考慮了四種導出劃分選擇。,1）可以用兩種方法來劃分班機實體：依據(jù)聯(lián)系“從”（起飛機場）或“到” （到達機場）和基于已把機場分成區(qū)域來劃分班機實體。 2）表的最后兩行給出了劃分旅客實體的兩個方法：依據(jù)聯(lián)系訂票和班機， 按班機起飛區(qū)域或第一訂票地點劃分。,50,導出劃分表的注釋表,該注釋表是對表2.4的注釋，其中說明了七種可能情形：旅客可能預定只離開一個區(qū)域（A，B，C）的班機，或離開兩個區(qū)域（AB，BC，AC）的班機，或離開所有區(qū)域（ABC）的班機。由于訂票是一種多對多關系（每個旅客可能多次訂票），所以需要以上七種情況。具體如圖：,51,注意問題,按照分片的定義，現(xiàn)實世界中的每個旅客映射到旅客實體中只有一個實例，為此要注意存在兩種可能情形： 第一種情形： 當旅客進行第一次訂票時，靜態(tài)地給每一旅客示例分配到一個旅客片段中； 第二種情形： 當某一旅客再次訂票時，因為旅客示例到片段的映射是動態(tài)的，相應的旅客示例就有可能從一個旅客片段移動到另一個旅客片段。 舉例說明： 若依據(jù)旅客各次訂票的班機起飛區(qū)域來劃分旅客，那么可假設某旅客第一次訂票的起飛區(qū)域為A，示例被分配到片段P1中，而當該旅客又預訂一張起飛區(qū)域為B的票時，相應的示例就會移動到p4中。,52,極化表,表2.6展示了一個極化表。表中的列關系到每一站點上應用的激活信息，表中行關系到劃分謂詞。一個極化值表指明由一給定站點發(fā)出的一給定應用訪問一給定片段的概率。在實際的表中，只畫出了少數(shù)實體，而其余的實體可以通過假設其余示例的一致分布來進行計算。有些應用不使用實體，所以與某些子炬陣不相關，在表中就畫上個叉。,53,2.5.3 飛機訂票系統(tǒng)中的分布設計,飛機訂票系統(tǒng)中的分布設計由四步組成： 1、對每一實體選擇分片準則； 2、確定非冗余分配； 3、在非冗余分配上引入冗余； 4、在每一站點上重新構造局部模式 下面具體闡述各步要完成的內(nèi)容與任務,54,分片設計,在分布要求分析階段中，已給定了一些包含在極化表中的可能有的劃分準則。在分片設計時設計者必須為各個實體選擇最合適的準則，并確認選定的劃分準則自身是方便的。這要求對有關的應用做定量分析，可以把這些應用分成三類：通過劃分變得容易的，變得更困難的和不受影響的應用。如果第一類“大于”第二類，那么劃分是方便的。在這個實例研究中考慮： 1）對于確定分配單位，垂直劃分是沒有用的，事實上，通過垂直劃分，沒有哪個應用會明顯變得容易些； 2）相反地，所有實體都有水平分片： 機場實體由一個基于區(qū)域的水平分片（片段：機場1，機場2，機場3）； 班機實體由一個基于起飛機場的導出水平分片（片段：班機1，班機2，班機3）； 旅客實體有一個基于旅客預定的所有班機起飛的導出水平分片（片段：旅客1，旅客2，旅客3，旅客4，旅客5，旅客6，旅客7）。,55,非冗余分配,在有些情形中，根據(jù)選定的劃分準則，容易得出非冗余分配。例如，機場1、班機1和旅客1被直接分配在站點1，同樣地，機場2，班機2和旅客2被分配在站點2；機場3，班機3和旅客3被分配在站點3；對于實體旅客的其他片段，必須根據(jù)極化表和頻率表來選擇使用該片段最