高級數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫報(bào)告

1、關(guān)于分布式數(shù)據(jù)庫中數(shù)據(jù)分配算法的組員學(xué)號分工21521213相關(guān)算法，算法評價，總結(jié)21521222相關(guān)算法，POEA 算法21521228相關(guān)算法，背景與意義，算法比較摘要隨著大數(shù)據(jù)和云計(jì)算時代的到來，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫已經(jīng)不能夠滿足海大數(shù)據(jù)的需求，因此，分布式技術(shù)在這種環(huán)境下應(yīng)運(yùn)而生。分布式數(shù)據(jù)庫由于其高可擴(kuò)展性、高可用性和可并發(fā)性的特點(diǎn)，在近年來得到了快速的發(fā)展，而合適的數(shù)據(jù)分配是分布式數(shù)據(jù)庫高效工作的關(guān)鍵，本文在了現(xiàn)有一些數(shù)據(jù)分配算法的基礎(chǔ)上，著重介紹了一個性能較好的 POEA 算法。POEA 是 Performance Optimality Enhancement Algorithm

2、 的簡寫，POEA 算法在借鑒前人的算法基礎(chǔ)之上進(jìn)行優(yōu)化。通過采用 Dijkstra 算法，計(jì)算在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中數(shù)據(jù)遷移的最短路徑，并且采用閾值來判斷數(shù)據(jù)是否需要遷移。POEA 的優(yōu)勢在于在動態(tài)環(huán)境下進(jìn)行無副本的數(shù)據(jù)分配任務(wù)，旨在降低數(shù)據(jù)傳輸?shù)拈_銷，避免不必要的數(shù)據(jù)遷移，減少節(jié)點(diǎn)間數(shù)據(jù)遷移的頻率和時間，最終優(yōu)化分布式數(shù)據(jù)庫的整體性能。1.背景與意義分布式數(shù)據(jù)庫指的是利用高速的計(jì)算機(jī)網(wǎng)絡(luò)將物理位置上分散的多個數(shù)據(jù)節(jié)點(diǎn)，邏輯上連接起來組成一個數(shù)據(jù)庫。分布式數(shù)據(jù)庫的基本是：在邏輯上作為一個整體的基礎(chǔ)上，將原本由集中式數(shù)據(jù)庫中的數(shù)據(jù)分散地到多個通過網(wǎng)絡(luò)連接的數(shù)據(jù)節(jié)點(diǎn)中，這樣就能夠得到更大的的容量，同時

3、支持更高的并發(fā)量。近年來，隨著數(shù)據(jù)量的快速增長，分布式數(shù)據(jù)庫技術(shù)也相應(yīng)得到了快速的發(fā)展，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫開始從集中式模型向分布式架構(gòu)發(fā)展，關(guān)系型的分布式數(shù)據(jù)庫有著傳統(tǒng)數(shù)據(jù)庫的數(shù)據(jù)模型，在保留其基本特征的基礎(chǔ)上，從原來的集中式變?yōu)榉植际剑瑥募惺接?jì)算分布式計(jì)算。數(shù)據(jù)分配是分布式數(shù)據(jù)庫的一個重要方向，合適恰當(dāng)?shù)臄?shù)據(jù)分配能夠大大降低數(shù)據(jù)傳送的代價，提高系統(tǒng)整體性能。這也是分布式數(shù)據(jù)庫相對于傳統(tǒng)集中式數(shù)據(jù)庫架構(gòu)的一個優(yōu)勢所在，這是因?yàn)榇蠖鄶?shù)針對數(shù)據(jù)庫的操作具有很強(qiáng)的局部性。因此一個高效的數(shù)據(jù)分配算法在降低數(shù)據(jù)傳輸代價，繼而提高分布式數(shù)據(jù)庫性能方面有重要意義。從數(shù)據(jù)庫設(shè)計(jì)上講，分布式數(shù)據(jù)庫系統(tǒng)中的分布

4、式數(shù)據(jù)庫設(shè)計(jì)和普通數(shù)據(jù)庫設(shè)計(jì)相比較具有自己的特色。在分布式數(shù)據(jù)庫設(shè)計(jì)中，要解決的絕大部分問題是由數(shù)據(jù)的分布性而引起的，這些問題對整個應(yīng)用系統(tǒng)的可用性、可靠性及數(shù)據(jù)的存取效率都產(chǎn)生很大的影響，同時又與分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)的諸多其它方面問題密切相關(guān)，尤其是分布式查詢處理與更新處理問題，它們往往彼此交織在一起，需要統(tǒng)籌考慮。分布式數(shù)據(jù)庫設(shè)計(jì)的主要目標(biāo)之一便是達(dá)到是數(shù)據(jù)處理的本地性，即通過設(shè)計(jì)，讓數(shù)據(jù)盡可能都存放在使用它們的應(yīng)用所處的節(jié)點(diǎn),減少，性能。由此產(chǎn)生了“數(shù)據(jù)冗余”這一技術(shù)，但它卻是一把 “雙刃劍”, 雖然能為檢索提供便利，卻給數(shù)據(jù)的一致性帶來新的問題。所以，在分布式數(shù)據(jù)庫系統(tǒng)的優(yōu)化設(shè)計(jì)中,設(shè)

5、計(jì)數(shù)據(jù)如何分布的問題就顯得特別重要。數(shù)據(jù)分配問題包括兩個方面的內(nèi)容：數(shù)據(jù)邏輯分割（數(shù)據(jù)分片）和片段物理分配（數(shù)據(jù)分配）。數(shù)據(jù)分配問題對整個分布式數(shù)據(jù)庫應(yīng)用系統(tǒng)的改進(jìn)、數(shù)據(jù)的可用性、數(shù)據(jù)庫效率和可靠性有很大影響。若數(shù)據(jù)片段分配得好,整個應(yīng)用系統(tǒng)的性能、數(shù)據(jù)的可用性以及分布式數(shù)據(jù)庫的效率和可靠性都會處于一個良好的狀態(tài)，否則，就體現(xiàn)不出分布式數(shù)據(jù)庫的優(yōu)越性。各國的學(xué)者該問題的目標(biāo)是一致的，即通信代價，Lc 表示局部C=Rc+Lc 最小，其中 C 表示代價，Rc 表示事務(wù)處理代價，以此為目標(biāo)探索邏輯片段應(yīng)該放置的最佳位置。對于分布式數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)分配問題的具有相當(dāng)大的學(xué)術(shù)及實(shí)用意義，它不僅是一個重要

6、的學(xué)術(shù)問題，而且對于分布式數(shù)據(jù)庫系統(tǒng)深度融入企業(yè)的競爭力等方面的實(shí)用意義也十分巨大。、節(jié)約成本和增強(qiáng)2.相關(guān)算法Amer 和 Abdalla (2012)提出了用于分布式系統(tǒng)的動態(tài)數(shù)據(jù)分配算法，它描述了在動態(tài)環(huán)境下，即節(jié)點(diǎn)數(shù)據(jù)的概率隨著時間而改變，如何進(jìn)行動態(tài)數(shù)據(jù)分配。作者提出了一種通過更改節(jié)點(diǎn)上的數(shù)據(jù)模式，進(jìn)行數(shù)據(jù)重新分配的模型。假設(shè)數(shù)據(jù)分片最初是根據(jù)查詢頻繁度的合適的集分布在不同的網(wǎng)絡(luò)節(jié)點(diǎn)上。該模型提出了一個基于節(jié)點(diǎn)之間的通信代價的數(shù)據(jù)分片再分配以及每個數(shù)據(jù)分片的更新代價的方法。重新分配過程將根據(jù)選擇的最大更新代價對每個片段進(jìn)行相應(yīng)的重分配。經(jīng)驗(yàn)結(jié)果表明，所技術(shù)將有效地在一個分布式關(guān)系數(shù)據(jù)

7、庫系統(tǒng)的上下文中解決動態(tài)片段重新分配問題做出貢獻(xiàn)。而Chang (2002)也了DDBS 的數(shù)據(jù)分配問題，并涵蓋了冗余和非冗余情形，但是數(shù)據(jù)分配執(zhí)行在一個節(jié)點(diǎn)數(shù)據(jù)概率不變的靜態(tài)環(huán)境中，這種靜態(tài)分配在概率改變的情況下會降低數(shù)據(jù)庫的性能。Brunstrom 等人 (1995)展示了一個非數(shù)據(jù)庫系統(tǒng)的最優(yōu)化算法。Ulus,Uysal (2007)和Singh, Kahlon (2009)分別提出了兩個非分布式數(shù)據(jù)庫算法，前者使用了閾值算法，根據(jù)數(shù)據(jù)模式的改變持續(xù)地重分配數(shù)據(jù)分片，而后者在此基礎(chǔ)上增加了時間約束來重分配數(shù)據(jù)。Nilarun Mukherjee (2011)提出了一個更加綜合性的算法，它

8、包含了對時間約束，閾值以及運(yùn)行時數(shù)據(jù)分片動態(tài)重分配到節(jié)點(diǎn)所傳輸?shù)臄?shù)據(jù)量的考量。Daudpota (1998)通過初次分配提出數(shù)據(jù)分配模型，以此模型來陳述和解決DDBS 問題并提出數(shù)據(jù)分配問題。Grebla,Mldovan, Darabant, Campan (2004)提出了 DDBS 中數(shù)據(jù)分配和優(yōu)化的解決方案，它利用移動的方式執(zhí)行。在此之后，又有一個基于觀察節(jié)點(diǎn)模式的非集中式方法用于 DDBS 的動態(tài)表分片和分配(Hauglid, Ryeng (2010)，它根據(jù)最近的歷史執(zhí)行數(shù)據(jù)的分片，和重分配的操作。KarimiAdl, Rouhani Roohi (2009)提出了一個基于蟻群算法的

9、啟發(fā)式算法來減少數(shù)據(jù)傳輸和分配的開銷。本文在了現(xiàn)有一些數(shù)據(jù)分配算法的基礎(chǔ)上，著重介紹了一個性能較好的POEA 算法。POEA 是Performance Optimality Enhancement Algorithm 的簡寫，POEA 算法在借鑒前人的算法基礎(chǔ)之上進(jìn)行優(yōu)化。下一節(jié)主要描述一下 POEA 算法。3.POEA 算法3.1 問題描述增強(qiáng) DDBS 性能的一個基本建議是把每一個數(shù)據(jù)分片存在它最頻繁被的節(jié)點(diǎn)。問題就在于為每一個數(shù)據(jù)分片選擇這樣一個節(jié)點(diǎn)是很復(fù)雜的。實(shí)際上，最好的解決方案之一是為每一個節(jié)點(diǎn)對于某一數(shù)據(jù)分片的和更新進(jìn)行計(jì)數(shù)。在此基礎(chǔ)上，對該數(shù)據(jù)分片的相應(yīng)計(jì)數(shù)值最高的那個節(jié)點(diǎn)成為

10、可能該數(shù)據(jù)分片的候選節(jié)點(diǎn)，條件是被選節(jié)點(diǎn)不招致任何約束被破壞。3.2 環(huán)境描述假設(shè)有一個由 M 個節(jié)點(diǎn)組成的完全互聯(lián)的網(wǎng)絡(luò)，每一個節(jié)點(diǎn)有 N 個數(shù)據(jù)分片，這些分片最初以靜態(tài)方式分布在節(jié)點(diǎn)上，如圖 1 所示。節(jié)點(diǎn)Sj上的每一個分片F(xiàn)i有兩個變量， LACi（代表本地Fi的計(jì)數(shù)值）和RACi（代表遠(yuǎn)端訪問Sj上Fi的計(jì)數(shù)值）。每一個節(jié)點(diǎn)Sj有兩個約束：容量Cj（任何節(jié)點(diǎn)都不能接受超過改值的數(shù)據(jù)量）和分片限制FLj（代表每一個節(jié)點(diǎn)能處理的最大分片數(shù)量），當(dāng)下述(1),(2)和(6)三個條件滿足時才會把分片F(xiàn)i從Sh移動到Sj。 ，( = 1,2, , )（1） , (, = 1,2, , )（2）=

11、1=1 = （3）=1FTC = , （4）=1 1Thresholdvalue = ( )（5）=1 =1（6）Thresholdvalue FTCC , 1 （7）=1（8） , =1 = , 1 =1(1)式表示對于分片F(xiàn)i（9）計(jì)數(shù)器值應(yīng)當(dāng)大于本地計(jì)數(shù)器值。(2)式表分片F(xiàn)i時，節(jié)點(diǎn)Sh和節(jié)點(diǎn)Sj之間平均請求開銷應(yīng)該高于節(jié)點(diǎn)Sh和所有其他節(jié)點(diǎn)之間的平均開銷(除節(jié)點(diǎn)Sj之外)。(3)式用來計(jì)算Sh節(jié)點(diǎn)和Sj節(jié)點(diǎn)之間的請求開銷（相同的等式也可以用來計(jì)算節(jié)點(diǎn)Sh同其他所有節(jié)點(diǎn)的總的請求開銷），節(jié)點(diǎn)Sh和Sj之間的請求開銷可以通過它們之間的傳輸單元開銷(TCh)乘上計(jì)算出j的數(shù)據(jù)(DRh)，該

12、數(shù)據(jù)量即 Karimi Adl 和Rouhani Roohi (2009)中使用的傳輸j數(shù)據(jù)量，（這一數(shù)據(jù)是通過執(zhí)行節(jié)點(diǎn)Sj請求分配在Sh上的分片F(xiàn)i中的某一數(shù)據(jù)得到的）。(4)式用來給出把分片F(xiàn)i從節(jié)點(diǎn)Sh傳輸?shù)絊j的分片傳輸開銷。(5)式計(jì)算分片F(xiàn)i的閾值。(6)式表明分片傳輸開銷應(yīng)當(dāng)大于閾值。下面三條約束應(yīng)當(dāng)在整個分配過程中都予以考慮：(7)式表示容量約束，即每個節(jié)點(diǎn)都不能接受超過其容量的數(shù)據(jù)。(8)式表示一個數(shù)據(jù)分片只會被分配在一個節(jié)點(diǎn)上。(9)式表示每個節(jié)點(diǎn)都不能處理超過分片限制(FL)的分片數(shù)量。表 1.變量RAC計(jì)數(shù)LAC本地計(jì)數(shù)S數(shù)據(jù)節(jié)點(diǎn)C節(jié)點(diǎn)容量FL分片數(shù)量約束FI分片標(biāo)識符

13、ASA當(dāng)前節(jié)點(diǎn)位置圖 1. 數(shù)據(jù)節(jié)點(diǎn)網(wǎng)絡(luò)3.3 算法描述POEA 算法按以下三個步驟執(zhí)行： A.決定最短路徑和它們的值；B.初始化病確定變量值；C.執(zhí)行算法并周期性檢查節(jié)點(diǎn)約束。CSA候選節(jié)點(diǎn)位置AC計(jì)數(shù)TFA分片時刻TCS候選節(jié)點(diǎn)位置的時段選擇從到的分片中數(shù)據(jù)大小AT每個節(jié)點(diǎn)的時刻 到的平均查詢耗時 到所有其他節(jié)點(diǎn)的平均查詢耗時當(dāng) 需要時,為 1,否則為 0從 出發(fā)的檢索操作的頻率從 出發(fā)的更新操作的頻率從 出發(fā)的第i 次頻率V分片的總量SC開銷當(dāng)分配到 時,為 1,否則為 0從 到的開銷A.最短路徑。偶然情況下，在網(wǎng)絡(luò)拓?fù)涓淖兒?，算法首先在每個節(jié)點(diǎn)執(zhí)行 Dijkstra 算法來得到從本節(jié)點(diǎn)

14、到所有其他節(jié)點(diǎn)的最短路徑。這個算法將會一直重復(fù)直到所有節(jié)點(diǎn)間的最短路徑都已得到。在帶權(quán)有向圖 G=(V,E)中，有一個權(quán)重函數(shù) W:E-R 將邊 為的權(quán)重值（見圖 1）。最短路徑表如表 2 所示。表 2. 最短路徑矩陣B.計(jì)算閾值。開銷矩陣 ACM 來表SAR（表 7），每個數(shù)據(jù)分片都至少被一個節(jié)點(diǎn)。所有用示。ACMij給出節(jié)點(diǎn)Sj分片F(xiàn)i的次數(shù)。在這里，基于節(jié)點(diǎn)開銷矩陣 ACM 如表 3 所示。傳輸開銷矩陣TCM（表 4）表示節(jié)點(diǎn)Sj分片F(xiàn)i的傳輸開銷。將 ACM 矩陣乘以TCM 矩陣得到的分片使用矩陣FUM。在此基礎(chǔ)上，計(jì)算出閾值。表 3. 分片開銷矩陣ACM表 4. 傳輸開銷矩陣TCM表

15、 5. DDBS 數(shù)據(jù)分片從分片使用矩陣 FUM 中選擇對于分片的平均下面將舉例說明。C.初始化變量。開銷最大的那個節(jié)點(diǎn)，分片F(xiàn)1F2F3F4F5F6標(biāo)識符123456大小810B620B900B660B521B701BSitesS1S2S3S4S105918S250164S3916011S4184110S/FF1,S1F2,S2F3,S4F4,S3F5,S3F6,S4S1110100S2131022S3200111S4012002源地址目的地路徑路徑開銷S1S2S1-S25S1S3S1-S39S1S4S1-S2-S39S2S3S2-S1-S314S2S4S2-S44S3S4S3-S411a.

16、可能N 個數(shù)據(jù)分片分布在 M 個節(jié)點(diǎn)上，每個節(jié)點(diǎn)包含一個或多個分片。請求分配在不同節(jié)點(diǎn)的多個分片。每一個節(jié)點(diǎn)有 2 個約束：分片限制(FL)和節(jié)點(diǎn)容量(C)，如表 5 所示。b.每個節(jié)點(diǎn)儲每個節(jié)點(diǎn)的分片一個叫做節(jié)點(diǎn)(SAR)的獨(dú)立的數(shù)據(jù)結(jié)構(gòu)。SAR 存，用表示，表明節(jié)點(diǎn)的第 k 次以下信息：，其中 k=1,2,3.,信息j=1,2,3,.,m. SAR 對每次1.2.3.被的分片標(biāo)識，見表 5。來訪節(jié)點(diǎn)地址 ASA執(zhí)行請求 Q 的數(shù)據(jù)DR（字節(jié)為），請求 Q 是指節(jié)點(diǎn)位于本節(jié)點(diǎn)的數(shù)據(jù)分片。4.5.本節(jié)點(diǎn)分片的時間。節(jié)點(diǎn)被計(jì)數(shù)器（AC）,次數(shù)c.對于節(jié)點(diǎn)內(nèi)的每一個數(shù)據(jù)分片一個叫做計(jì)數(shù)以下信息：（

17、ACR）的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)在每次分片后1.候選節(jié)點(diǎn)地址（CSA）：它是在時間間隔（t1 到 t2）內(nèi)請求開銷高于其他任何節(jié)點(diǎn)的節(jié)點(diǎn)地址。最初 CSA 被設(shè)為分片當(dāng)前所在節(jié)點(diǎn)的地址。2.3.4.本地遠(yuǎn)端計(jì)數(shù)（LAC）計(jì)數(shù)（RAC）候選節(jié)點(diǎn)地址選取的時間（TCS） 對每一個本地的分片，本地和遠(yuǎn)端計(jì)數(shù)初始為 0（LAC=0,RAC=0）4.算法比較基于以下 3 個因子，比較了POEA 算法和已經(jīng)存在的 4 種算法（最優(yōu)化算法 Optimal，Threshold 算法，TTCA 算法和Synthesis 算法）：數(shù)據(jù)分片遷移決策成本（SC）；傳輸成本（TC）和計(jì)算成本（CO）還有網(wǎng)絡(luò)流量成本（NT

18、）。A. 數(shù)據(jù)分片遷移決策：Brunstrom 的 Optimal 算法是當(dāng)節(jié)點(diǎn)的 counter值比持有數(shù)據(jù)的節(jié)點(diǎn)的 counter 值大，分片F(xiàn)i進(jìn)行遷移。閾值算法是當(dāng)持有數(shù)據(jù)的節(jié)點(diǎn)大于一個閾值t 時，分片F(xiàn)i進(jìn)行遷移。TTCA 算法是當(dāng)節(jié)點(diǎn)的 counter值比閾值t 大，并且所有剩余的t+1 個都會在特定時間T 內(nèi)發(fā)生，那么分片F(xiàn)i進(jìn)行遷移。而Mukherjee 的綜合算法是當(dāng)持有數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)傳輸成本比任何其他節(jié)點(diǎn)的都要高，并在最近的一些時間間隔內(nèi)都高于一個閾值，那么就將數(shù)據(jù)遷移到一個計(jì)劃的節(jié)點(diǎn)上。然而，POEA 算法是當(dāng)節(jié)點(diǎn)的 counter 值大于本地持有數(shù)據(jù)節(jié)點(diǎn)的 counte

19、r 值，并且新老節(jié)點(diǎn)的查詢成本 QC 比老節(jié)點(diǎn)到其他節(jié)點(diǎn)的 QC 都要高，則分片F(xiàn)i進(jìn)行遷移，新老節(jié)點(diǎn)的最短路徑也會被更新。90%80%70%60%OA50%TTCASYNPOEA40%30%20%10%0%TCSCCONT90%80%70%60%OA50%TTCASYN POEA40%30%20%10%0%TCSCCONT圖 2. DDBS 性能B.成本因子：從圖 2 中容易看出，Brunstrom 的 Optimal 算法開銷比較大，因?yàn)樗鼮槊恳粋€數(shù)據(jù)分片了多個counter 值；閾值算法相對于Optimal 算法不需要多少空間，因?yàn)樗鼮槊恳粋€數(shù)據(jù)分片只了一個counter 值；TTCA

20、算法相對于前兩個算法需要的空間。Mukherjee 的綜合算法需要很高的成本，因?yàn)樗撕脦讉€數(shù)據(jù)結(jié)構(gòu)體。而 POEA 算法的成本和Mukherjee 的綜合算法差不多，原因也是C. 傳輸成本和計(jì)算開銷：圖 2 的 DDBS 性能了好幾個數(shù)據(jù)結(jié)構(gòu)體。的中清楚地顯示了 Optimal算法的傳輸成本最高。這是因?yàn)榛镜慕?jīng)驗(yàn)法則：更高的頻率會帶來更高的傳輸成本和網(wǎng)絡(luò)流量開銷。閾值算法使網(wǎng)絡(luò)流量開銷最小化并且使用閾值因子來控制傳輸成本，閾值算法的計(jì)算開銷也比 Optimal 算法更低。然而相對于前兩個算法，TTCA 算法通過時間限制和閾值來進(jìn)一步的降低網(wǎng)絡(luò)流量開銷和傳輸成本。Mukherjee 的綜合算

21、法造成的計(jì)算開銷，因?yàn)樗€要在時間間隔 t 內(nèi)計(jì)算這個數(shù)據(jù)分片傳輸?shù)剿袛?shù)據(jù)節(jié)點(diǎn)的成本。而 POEA 算法相對于其他算法，最引人注目的是，通過增加以下幾個特點(diǎn)來使分片遷移的傳輸成本最?。汗?jié)點(diǎn)的counter（必須大于本地已遷移的分片 Fi 的 counter），閾值（閾值的計(jì)算算法和其他幾個算法的不同），查詢成本（QC）的計(jì)算，相對于綜合算法使用的數(shù)據(jù)傳輸總量，POEA 使用節(jié)點(diǎn) 和節(jié)點(diǎn) 的查詢成本,節(jié)點(diǎn) 和所有其他節(jié)點(diǎn)的查詢成本，最后還采用了最短路徑算法。在POEA 算法里，只要節(jié)點(diǎn)存在約，那么分片會一直呆在持有節(jié)點(diǎn)。束5.評價與Brunstrom 等人Optimal 算法保留了一個計(jì)數(shù)矩陣

22、，矩陣的每一行表示特定的數(shù)據(jù)分片能夠的數(shù)據(jù)節(jié)點(diǎn)。數(shù)據(jù)分片中的數(shù)據(jù)節(jié)點(diǎn)最大訪問計(jì)數(shù)將會成為數(shù)據(jù)分片的候選節(jié)點(diǎn)。這個算法中的最關(guān)鍵的問題在于當(dāng)數(shù)據(jù)模式快速變化時，該算法將花費(fèi)很長的時間去轉(zhuǎn)化數(shù)據(jù)節(jié)點(diǎn)上的數(shù)據(jù),因?yàn)閷γ總€數(shù)據(jù)分片的時間會比本地高。這個過程將會產(chǎn)生巨大的網(wǎng)絡(luò)超負(fù)載轉(zhuǎn)化。然而，閥值算法證明了一個數(shù)據(jù)分片將會在它原始位置停留更長的時間，只要這個數(shù)據(jù)分片的計(jì)數(shù)值小于閥門值,并且本地分片的可能計(jì)數(shù)器性比要高。這個閥值算法只為每個數(shù)據(jù)分片保留了一個（一般為最后的數(shù)據(jù)節(jié)點(diǎn)去的數(shù)據(jù)節(jié)點(diǎn)）。到目前為止，數(shù)據(jù)分片并沒有方法選擇一個新數(shù)據(jù)分片除了最后一個數(shù)據(jù)節(jié)點(diǎn)，也就是說，無論何時在一個數(shù)據(jù)分片計(jì)數(shù)大于閥

23、值之后，最后一個數(shù)據(jù)節(jié)點(diǎn)將會被選中用于保存數(shù)據(jù)分片。閥值的選擇將會影響數(shù)據(jù)分片在 DDBS 的數(shù)據(jù)節(jié)點(diǎn)之間移動.增加閥值意味著減少數(shù)據(jù)分片在數(shù)據(jù)節(jié)點(diǎn)之間的移動，反之亦然。這又會出現(xiàn)一個問題，如果有很多的數(shù)據(jù)節(jié)點(diǎn)對于一個數(shù)據(jù)分片有一樣的可能性，這將會導(dǎo)致數(shù)據(jù)分片去訪問所有的數(shù)據(jù)節(jié)點(diǎn)，結(jié)果增加了轉(zhuǎn)化的代價以及網(wǎng)絡(luò)通信。Singh 和 Kahlon 在 2009 年TTCA 算法盡管和 Optimal 算法一樣保留了一個計(jì)數(shù)矩陣，但是它在不同的矩陣中了的時間而不是在同樣的矩陣中。無論何時，一個特定分片的數(shù)據(jù)節(jié)點(diǎn)的計(jì)數(shù)器比閥值大，那么這個數(shù)據(jù)節(jié)點(diǎn)將會成為問矩陣終數(shù)據(jù)分片的候選節(jié)點(diǎn)。TTCA 的主要問題

24、就是它并不在訪時間，也沒有在一個不可預(yù)料的情況發(fā)生時給出一個可說服的措施.舉個例子，在 t+1 次達(dá)到了要求的數(shù)量之前的時間消逝.在這個算法中，當(dāng)時間增加,轉(zhuǎn)化代價也就增加，反之亦然。然而，Mukjherjee 的synthesis算法開發(fā)了一個技術(shù)，增加新的數(shù)據(jù)分片遷移的限制來減少轉(zhuǎn)化代價。它采用了特定的數(shù)據(jù)結(jié)構(gòu)來保留最后一個節(jié)點(diǎn)的信息。這花費(fèi)了的空間，增加了代價。同時，它產(chǎn)生了的計(jì)算負(fù)荷，由于需要計(jì)算連續(xù)時間間隔的數(shù)據(jù)節(jié)點(diǎn)之后的整個數(shù)據(jù)容量交換。在這個算法中，閥值或者高，數(shù)據(jù)遷移就會越少，反之亦然。表 6. 標(biāo)準(zhǔn)符號的容量越表 7.不同算法的開發(fā)標(biāo)準(zhǔn)使用情況算ARATHVTTCHICQCS

25、COSPA評價Optimal算法是是否否否否否否否高傳輸成本，大數(shù)據(jù)遷移引起高網(wǎng)絡(luò)通信量，高本成本，低計(jì)算成閾 值法算否是是否否僅最近訪問節(jié)點(diǎn)否否否高計(jì)算成本，低數(shù)據(jù)遷移和TTCA 算法否是是是否最近否否否高計(jì)算成本和成本，低數(shù)據(jù)遷移，低網(wǎng)絡(luò)通信量和低傳輸成本節(jié)點(diǎn)Synthesis 算法否是是是是是否否否高計(jì)算成本和成本，低數(shù)據(jù)遷移和比TTCA 低的傳輸成本標(biāo)準(zhǔn)標(biāo)準(zhǔn)符號本地Local AcsLARemoteAcsRA閾值Threshold ValueTHV數(shù)據(jù)的時間約束Time constras for data acsingT節(jié)點(diǎn)之間的傳輸成本Transmiscost betn sitesT

26、C查詢成本Query CostQC保留歷史信息Maain history information for acsHIC節(jié)點(diǎn)約束Site constraSCO最短路徑算法Shortest PalgorithmSPA表 8. 不同性能因子的比較POEA 算法試圖解決以上算法中的所有問題來減少交流代價和提高DDBS 的性能。POEA 算法增加了一些新的特性，更好地避免不必要的數(shù)據(jù)遷移?？紤]到網(wǎng)絡(luò)的全接連，增加的特性包括了：A.B.C.D.Synthesis 算法使用數(shù)據(jù)傳輸容量的合并查詢代價，開發(fā)新的數(shù)據(jù)節(jié)點(diǎn)約束，本地和的變量，使用傳輸代價矩陣來計(jì)算閥值，閥值的運(yùn)行采用和之前算法都不一樣的方法。這個

27、 POEA 算法和 Synthesis 算法一樣擁有空間花費(fèi)和計(jì)算超負(fù)荷的產(chǎn)生.然而,和之前的方法比較，它實(shí)現(xiàn)了數(shù)據(jù)節(jié)點(diǎn)的約束和最短路徑算法，這大大減少了數(shù)據(jù)遷移和傳輸代價。表 7 顯示了運(yùn)行時期不同算法的通過和發(fā)展特點(diǎn)。表 6 顯示了表 7 中使用的標(biāo)準(zhǔn)名詞的符號。被采用的比較元素包括：傳輸代價(transmiscost，TC)，代價(storagecost，SC)，計(jì)算成本(compuion overhead，CO)和網(wǎng)絡(luò)通信量(network traffic，NT)。這些元素在表 8，圖 2 中顯示。至于數(shù)據(jù)分片遷移決策(fragment migration deci，F(xiàn)MD)，并不能明

28、確地在比較中表示成一個性能因子。因?yàn)樗梢院畹赝ㄟ^其他比較因子推導(dǎo)出來，比如TC 和 NT，因?yàn)樗鼈冎g存在正相關(guān)關(guān)系。算法TC(%)SC(%)CO(%)NT(%)Optimal 算法7080575閾值算法45302550TTCA 算法40504050Synthesis 算法30807015POEA 算法10807010POEA 算法是是是是是是是是是高計(jì)算成本和成本，與前面的算法比，由于采用SPA，有低數(shù)據(jù)遷移和傳輸成本圖 3.的所有算法的分片遷移百分比圖 4. 分片遷移百分比事實(shí)上，這里有五個基本的影響 DDBS 性能和減少不必要的分片遷移的因子，分別是時間約束(time constra

29、， T)分片(remote fragment acs，RFA)，閾值(threshold value，THV)，節(jié)點(diǎn)約束違背(site constras violation， SCV)以及節(jié)點(diǎn)之間的查詢代價(query costs，QC)。當(dāng) T，RAC 增加，THV，SCV，QC 減少時，分片遷移將減少，反之亦然。舉個例子，當(dāng)固定了 V，SCV，QC，增加T 或者 RAC，那么分片遷移就會增加，反之亦然。圖 3(A)和 3(B)描述了這個事實(shí)并顯示了所有因子和數(shù)據(jù)遷移頻率之間的關(guān)系。圖 4 顯示了不同算法的數(shù)據(jù)分片遷移百分比比較。包括了 Optimal 算法(OA)，Threshold 算法

30、()，TTCA算法，Synthesis 算法(SYN)以及 POEA 算法。這證明的數(shù)據(jù)遷移頻率。POEA 算法具有最低6.總結(jié)本文了幾種分布式數(shù)據(jù)庫中的數(shù)據(jù)分配算法，并詳細(xì)介紹了性能較好的POEA 算法。POEA 算法結(jié)合了很多因子，比如時間，數(shù)據(jù)節(jié)點(diǎn)約束，數(shù)據(jù)模式，閾值以及包含了數(shù)據(jù)傳輸容量，運(yùn)行時數(shù)據(jù)節(jié)點(diǎn)之間的數(shù)據(jù)分片動態(tài)再分配的查詢成本，POEA 算法加強(qiáng)了整個DDBS 的性能，通過維持嚴(yán)格的分片再分配使得DDBS 中的從數(shù)據(jù)節(jié)點(diǎn)到另一個節(jié)點(diǎn)的分片遷移頻率顯著地減少。POEA算法在動態(tài)數(shù)據(jù)分配上是前面提到的算法中最有效的，一旦需要數(shù)據(jù)移動，它采用了最短路徑算法來提高 DDBS 的性能，

31、通過與之前算法比較更好地減少網(wǎng)絡(luò)通信量和減少數(shù)據(jù)傳輸。POEA 唯一的不足就是，與之前的算法比較，它需要更多的空間。然而，DDBS 性能提高補(bǔ)償了這個缺點(diǎn)，同時在急劇下降的情況下，這被視為一個并不重要的缺點(diǎn)。硬件價格的參考文獻(xiàn)1Abdalla, H. I. (2011). An efficient approach for data placement in distributedsystems. In: 2011 Fifth FTRAubiquitous engineering.ernational conference on multimedia and2Hauglid, J. O., & Ryeng, N. H. (2010). DYFRAM: Dynamic fragmenion and replica management in distributed database systems. Distributed and Parallel Databases,28, 157185.Ahmad, I., Karlapalem, K., Kwok, Y. K., & So, S. K. (2002). Evolutionaryalgorithm