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

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

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

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

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

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

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

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

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

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

10、可能該數(shù)據(jù)分片的候選節(jié)點(diǎn)，條件是被選節(jié)點(diǎn)不招致任何約束被破壞。3.2 環(huán)境描述假設(shè)有一個(gè)由 M 個(gè)節(jié)點(diǎn)組成的完全互聯(lián)的網(wǎng)絡(luò)，每一個(gè)節(jié)點(diǎn)有 N 個(gè)數(shù)據(jù)分片，這些分片最初以靜態(tài)方式分布在節(jié)點(diǎn)上，如圖 1 所示。節(jié)點(diǎn)Sj上的每一個(gè)分片F(xiàn)i有兩個(gè)變量， LACi（代表本地Fi的計(jì)數(shù)值）和RACi（代表遠(yuǎn)端訪問(wèn)Sj上Fi的計(jì)數(shù)值）。每一個(gè)節(jié)點(diǎn)Sj有兩個(gè)約束：容量Cj（任何節(jié)點(diǎn)都不能接受超過(guò)改值的數(shù)據(jù)量）和分片限制FLj（代表每一個(gè)節(jié)點(diǎn)能處理的最大分片數(shù)量），當(dāng)下述(1),(2)和(6)三個(gè)條件滿足時(shí)才會(huì)把分片F(xiàn)i從Sh移動(dòng)到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)式表示對(duì)于分片F(xiàn)i（9）計(jì)數(shù)器值應(yīng)當(dāng)大于本地計(jì)數(shù)器值。(2)式表分片F(xiàn)i時(shí)，節(jié)點(diǎn)Sh和節(jié)點(diǎn)Sj之間平均請(qǐng)求開(kāi)銷應(yīng)該高于節(jié)點(diǎn)Sh和所有其他節(jié)點(diǎn)之間的平均開(kāi)銷(除節(jié)點(diǎn)Sj之外)。(3)式用來(lái)計(jì)算Sh節(jié)點(diǎn)和Sj節(jié)點(diǎn)之間的請(qǐng)求開(kāi)銷（相同的等式也可以用來(lái)計(jì)算節(jié)點(diǎn)Sh同其他所有節(jié)點(diǎn)的總的請(qǐng)求開(kāi)銷），節(jié)點(diǎn)Sh和Sj之間的請(qǐng)求開(kāi)銷可以通過(guò)它們之間的傳輸單元開(kāi)銷(TCh)乘上計(jì)算出j的數(shù)據(jù)(DRh)，該

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

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

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

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

16、可能N 個(gè)數(shù)據(jù)分片分布在 M 個(gè)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)包含一個(gè)或多個(gè)分片。請(qǐng)求分配在不同節(jié)點(diǎn)的多個(gè)分片。每一個(gè)節(jié)點(diǎn)有 2 個(gè)約束：分片限制(FL)和節(jié)點(diǎn)容量(C)，如表 5 所示。b.每個(gè)節(jié)點(diǎn)儲(chǔ)每個(gè)節(jié)點(diǎn)的分片一個(gè)叫做節(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 對(duì)每次1.2.3.被的分片標(biāo)識(shí)，見(jiàn)表 5。來(lái)訪節(jié)點(diǎn)地址 ASA執(zhí)行請(qǐng)求 Q 的數(shù)據(jù)DR（字節(jié)為），請(qǐng)求 Q 是指節(jié)點(diǎn)位于本節(jié)點(diǎn)的數(shù)據(jù)分片。4.5.本節(jié)點(diǎn)分片的時(shí)間。節(jié)點(diǎn)被計(jì)數(shù)器（AC）,次數(shù)c.對(duì)于節(jié)點(diǎn)內(nèi)的每一個(gè)數(shù)據(jù)分片一個(gè)叫做計(jì)數(shù)以下信息：（

17、ACR）的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)在每次分片后1.候選節(jié)點(diǎn)地址（CSA）：它是在時(shí)間間隔（t1 到 t2）內(nèi)請(qǐng)求開(kā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)地址選取的時(shí)間（TCS） 對(duì)每一個(gè)本地的分片，本地和遠(yuǎn)端計(jì)數(shù)初始為 0（LAC=0,RAC=0）4.算法比較基于以下 3 個(gè)因子，比較了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)大于一個(gè)閾值t 時(shí)，分片F(xiàn)i進(jìn)行遷移。TTCA 算法是當(dāng)節(jié)點(diǎn)的 counter值比閾值t 大，并且所有剩余的t+1 個(gè)都會(huì)在特定時(shí)間T 內(nèi)發(fā)生，那么分片F(xiàn)i進(jìn)行遷移。而Mukherjee 的綜合算法是當(dāng)持有數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)傳輸成本比任何其他節(jié)點(diǎn)的都要高，并在最近的一些時(shí)間間隔內(nèi)都高于一個(gè)閾值，那么就將數(shù)據(jù)遷移到一個(gè)計(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)的最短路徑也會(huì)被更新。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 算法開(kāi)銷比較大，因?yàn)樗鼮槊恳粋€(gè)數(shù)據(jù)分片了多個(gè)counter 值；閾值算法相對(duì)于Optimal 算法不需要多少空間，因?yàn)樗鼮槊恳粋€(gè)數(shù)據(jù)分片只了一個(gè)counter 值；TTCA

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

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

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

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

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

25、COSPA評(píng)價(jià)Optimal算法是是否否否否否否否高傳輸成本，大數(shù)據(jù)遷移引起高網(wǎng)絡(luò)通信量，高本成本，低計(jì)算成閾 值法算否是是否否僅最近訪問(wèn)節(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)符號(hào)本地Local AcsLARemoteAcsRA閾值Threshold ValueTHV數(shù)據(jù)的時(shí)間約束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 算法試圖解決以上算法中的所有問(wèn)題來(lái)減少交流代價(jià)和提高DDBS 的性能。POEA 算法增加了一些新的特性，更好地避免不必要的數(shù)據(jù)遷移?？紤]到網(wǎng)絡(luò)的全接連，增加的特性包括了：A.B.C.D.Synthesis 算法使用數(shù)據(jù)傳輸容量的合并查詢代價(jià)，開(kāi)發(fā)新的數(shù)據(jù)節(jié)點(diǎn)約束，本地和的變量，使用傳輸代價(jià)矩陣來(lái)計(jì)算閥值，閥值的運(yùn)行采用和之前算法都不一樣的方法。這個(gè)

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

28、確地在比較中表示成一個(gè)性能因子。因?yàn)樗梢院畹赝ㄟ^(guò)其他比較因子推導(dǎo)出來(lái)，比如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í)上，這里有五個(gè)基本的影響 DDBS 性能和減少不必要的分片遷移的因子，分別是時(shí)間約束(time constra

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

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

31、通過(guò)與之前算法比較更好地減少網(wǎng)絡(luò)通信量和減少數(shù)據(jù)傳輸。POEA 唯一的不足就是，與之前的算法比較，它需要更多的空間。然而，DDBS 性能提高補(bǔ)償了這個(gè)缺點(diǎn)，同時(shí)在急劇下降的情況下，這被視為一個(gè)并不重要的缺點(diǎn)。硬件價(jià)格的參考文獻(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