分布式數(shù)據(jù)庫(kù)的數(shù)據(jù)分配算法

1、分布式數(shù)據(jù)庫(kù)的數(shù)據(jù)分配算法第1頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一主要內(nèi)容一、數(shù)據(jù)分配問(wèn)題的提出二、典型數(shù)據(jù)分配算法分析與對(duì)比三、數(shù)據(jù)分配的研究趨勢(shì)第2頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一一、數(shù)據(jù)分配問(wèn)題的提出在分布式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)中，數(shù)據(jù)分配主要是解決數(shù)據(jù)片段在分布式系統(tǒng)各節(jié)點(diǎn)上的分布。當(dāng)然，解決方案應(yīng)滿足一定的優(yōu)化標(biāo)準(zhǔn)，其實(shí)質(zhì)是要得到一個(gè)最優(yōu)分配方案。不過(guò)這樣的問(wèn)題因其復(fù)雜性太大被列為NP難題。在很多實(shí)際應(yīng)用中，其實(shí)也并不一定要得到最優(yōu)分配方案，一個(gè)足夠接近最優(yōu)分配方案的近似最優(yōu)分配方案往往也可以滿足要求。國(guó)內(nèi)外學(xué)者在數(shù)據(jù)分配的基本原則上是有兩

2、點(diǎn)共識(shí)的。 (1)數(shù)據(jù)應(yīng)盡可能靠近要使用它的站點(diǎn)，并用負(fù)載平衡方法找出一個(gè)系統(tǒng)性能的全局優(yōu)化。第3頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一 (2)檢索事務(wù)應(yīng)盡量局部化；更新事務(wù)所涉及的數(shù)據(jù)片段的副本不宜過(guò)多，以減少保持?jǐn)?shù)據(jù)一致性的代價(jià)。對(duì)于分布式數(shù)據(jù)庫(kù)系統(tǒng)的應(yīng)用需求和理論研究，國(guó)外都要領(lǐng)先于國(guó)內(nèi)。對(duì)于數(shù)據(jù)分配問(wèn)題的研究，國(guó)外學(xué)者在基礎(chǔ)理論方面貢獻(xiàn)頗多，如文獻(xiàn)8 中提出的方法對(duì)于避免由于系統(tǒng)IO瓶頸造成的效率下降提供了幫助。國(guó)內(nèi)學(xué)者在對(duì)該問(wèn)題的研究上雖然起步較晚，但是也逐步跟上領(lǐng)先者的步伐，獲得不少研究成果，如“啟發(fā)式試消副本法”在降低分配算法的復(fù)雜度方面有很好的效果。第4頁(yè)，

3、共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一二、典型數(shù)據(jù)分配算法分析與對(duì)比 對(duì)于分布式數(shù)據(jù)庫(kù)的數(shù)據(jù)分配方法，國(guó)內(nèi)外學(xué)者的研究從未間斷，下面列舉四個(gè)典型方法。21 分組局部?jī)?yōu)化法分組局部?jī)?yōu)化的數(shù)據(jù)分配方法的算法思想為：將片段等分成若干個(gè)組(最后一個(gè)組的片段數(shù)可能少于前面組的片段數(shù))，設(shè)定一個(gè)初始分配L0。首先對(duì)一個(gè)組獲得各種分配方案而不考慮其它組的分配，以此獲得整體n個(gè)片段的各種分配方案，從中選擇最優(yōu)的，得到該組的局部最優(yōu)。按照這個(gè)方法對(duì)余下的每個(gè)組進(jìn)行分配得到各組的局部?jī)?yōu)化，由此獲得一個(gè)總體的優(yōu)化分配方案L1，比較L1和L0的代價(jià)誤差，若誤差未滿足條件，再對(duì)上述過(guò)程進(jìn)行迭代處理直至誤

4、差滿足條件。第5頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一優(yōu)缺點(diǎn)：分組局部?jī)?yōu)化中代價(jià)公式本身是很復(fù)雜的，難于理解。它既考慮了單目查詢和雙目查詢，又考慮了本地處理代價(jià)和通信代價(jià)，要確定哪些是單目運(yùn)算，哪些是雙目運(yùn)算很不容易，公式的復(fù)雜性很高，算法的可操作性差，不利于實(shí)際應(yīng)用。第6頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一22 啟發(fā)式添加副本法該方法的主要思想是：設(shè)待分配的數(shù)據(jù)片段為Fj，首先用最佳適應(yīng)法確定一個(gè)非冗余的最佳分配方案，然后再分別計(jì)算在剩余的場(chǎng)地中的一個(gè)場(chǎng)地上增加片段Fj的副本后整個(gè)系統(tǒng)的總費(fèi)用，找出其中的最小費(fèi)用，如果該費(fèi)用大于增加Fj副本前的最小費(fèi)

5、用，則停止計(jì)算；否則，決定在相應(yīng)的場(chǎng)地上增加數(shù)據(jù)片段Fj的副本。這樣一直計(jì)算下去，直到找出最小費(fèi)用為止。第7頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一優(yōu)缺點(diǎn)：添加副本法是一種典型的啟發(fā)式方法。它不但考慮到副本之間的相互影響，還考慮到隨著副本的增加而帶來(lái)的費(fèi)用上升問(wèn)題。從總的代價(jià)因素來(lái)考慮，增加副本數(shù)與提高系統(tǒng)的可靠性之間不是線性關(guān)系。從以往經(jīng)驗(yàn)來(lái)看， 當(dāng)副本數(shù)為2或3時(shí)，系統(tǒng)費(fèi)用較理想。當(dāng)副本數(shù)進(jìn)一步增加時(shí)，系統(tǒng)費(fèi)用不一定會(huì)降低，甚至有可能上升在此方法中，形成初始分配的方法是采用非冗余最佳適應(yīng)法。非冗余最佳適應(yīng)法非本文的主要參考，不作詳述，只介紹一下它的優(yōu)缺點(diǎn)。第8頁(yè)，共18頁(yè)

6、，2022年，5月20日，10點(diǎn)10分，星期一用非冗余最佳適應(yīng)法進(jìn)行數(shù)據(jù)分配，存儲(chǔ)代價(jià)最小，但是系統(tǒng)的可用性、可靠性和數(shù)據(jù)的訪問(wèn)效率不高，并且沒(méi)有體現(xiàn)出分布式數(shù)據(jù)庫(kù)系統(tǒng)的優(yōu)越性。另外，假設(shè)數(shù)據(jù)片段的數(shù)量為m，站點(diǎn)數(shù)為q，則非冗余最佳適應(yīng)法在每次決定分配某個(gè)數(shù)據(jù)片段之前要計(jì)算q次全局代價(jià)，然后將q個(gè)結(jié)果進(jìn)行比較。隨著已分配的數(shù)據(jù)片段的增多，每次的計(jì)算量會(huì)越來(lái)越大。這種不使用啟發(fā)式公式而用大量的計(jì)算的方式，嚴(yán)重影響了初始分配的效率，也給整個(gè)啟發(fā)式添加副本法的算法復(fù)雜性帶來(lái)不利的影響。第9頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一2. 3 啟發(fā)式試消副本法啟發(fā)式試消副本法的基本思路是

7、：對(duì)檢索應(yīng)用，可以按照應(yīng)用發(fā)出的原始站點(diǎn)將目標(biāo)片段放在應(yīng)用所在站點(diǎn)而使得檢索最優(yōu)。這樣一來(lái)，每個(gè)數(shù)據(jù)片段可能有多個(gè)副本分布在網(wǎng)絡(luò)的多個(gè)站點(diǎn)上。對(duì)更新應(yīng)用，則會(huì)因?yàn)橐S護(hù)多個(gè)站點(diǎn)上片段多副本的數(shù)據(jù)一致性而增加開銷。因此，第一步僅考慮檢索需求片段的完全本地化，即先保證檢索應(yīng)用最優(yōu)，得到初始分配，顯然這種初始分配對(duì)更新應(yīng)用是最壞的。然后再考慮更新應(yīng)用的影響，逐步消除片段副本數(shù)以減小更新的通信代價(jià)。第10頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一其間，用目標(biāo)函數(shù)作為衡量其副本是否該被消除的判斷依據(jù)，當(dāng)去掉一個(gè)片段副本時(shí)，計(jì)算產(chǎn)生的總代價(jià)是否小于原方案(未去掉該片段副本時(shí)的中間方案)，若

8、是就消除該片段副本，否則不消除，目的是盡可能使最終的分配方案的總代價(jià)最小。該算法是一種啟發(fā)式算法，第一步，基于條件設(shè)定，可以根據(jù)檢索訪問(wèn)矩陣和檢索事務(wù)執(zhí)行頻率矩陣很容易地得到初始片段分配表；第二步以第一步得到的分配表為基礎(chǔ)，逐步消除片段副本。在消除片段副本的過(guò)程中，目標(biāo)函數(shù)的計(jì)算量受分配表的影響，隨著副本數(shù)的減少，計(jì)算量也相應(yīng)減小。第11頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一優(yōu)缺點(diǎn)：這種啟發(fā)式試消副本法比起分組局部?jī)?yōu)化法有著明顯的實(shí)用性，但是這種方法只是對(duì)檢索應(yīng)用較多、事務(wù)的檢索更新比普遍較大的分布式數(shù)據(jù)庫(kù)系統(tǒng)有著良好的實(shí)用性。而對(duì)于更新應(yīng)用較多或不比檢索應(yīng)用少、事務(wù)的檢索

9、更新比并非普遍較大甚至是更新檢索比普遍較大的系統(tǒng)時(shí)，由于開始只考慮檢索應(yīng)用(而分布式數(shù)據(jù)庫(kù)系統(tǒng)可能是更新應(yīng)用占有相對(duì)較大比例)，數(shù)據(jù)片段的副本過(guò)多，導(dǎo)致消除副本這一步的復(fù)雜度隨更新應(yīng)用所占的比重的增加而增加。第12頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一2. 4 基于代價(jià)得益和內(nèi)部數(shù)據(jù)交換的啟發(fā)式數(shù)據(jù)分配方法基于代價(jià)得益和內(nèi)部數(shù)據(jù)交換的啟發(fā)式片段分配方法的算法思想為：先按照最小代價(jià)原則分配片段，然后考慮片段之間的相關(guān)性，對(duì)相關(guān)性大的片段進(jìn)行合并成組，最后以片段組為分配單位按照最小代價(jià)原則進(jìn)行分配。分配步驟分為三步：片段分配、片段組的構(gòu)造、片段組分配到系統(tǒng)節(jié)點(diǎn)上。第13頁(yè)，共1

10、8頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一優(yōu)缺點(diǎn)：該分配算法為了考慮片段間的相關(guān)性，將整個(gè)分配分為三個(gè)步驟，這顯得十分繁瑣，并且用IDC概念來(lái)構(gòu)造片段組的計(jì)算開銷非常大。其中分配過(guò)程要進(jìn)行兩次，一是片段的分配，二是片段組的分配，這極大地增加了算法本身的復(fù)雜性和執(zhí)行算法的開銷。該算法對(duì)統(tǒng)計(jì)信息考慮得比較合理，但是片段組分配用到的某些統(tǒng)計(jì)信息必須受第一步分配結(jié)果即片段分配的限制，也增加了復(fù)雜性。另外，在代價(jià)公式中將通信代價(jià)和存儲(chǔ)代價(jià)一并處理，沒(méi)有考慮代價(jià)單位的換算問(wèn)題?？傊?，該分配方法的復(fù)雜性還是較大，實(shí)際應(yīng)用中的可行性不高。第14頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一

11、三、數(shù)據(jù)分配的研究趨勢(shì)目前，國(guó)內(nèi)外學(xué)者已經(jīng)研究出多種數(shù)據(jù)分配方法，但基本上都存在代價(jià)公式復(fù)雜，算法執(zhí)行效率較低或所求結(jié)果與最優(yōu)分配方案相差較大的不足之處。一種基于遺傳算法的數(shù)據(jù)分配策略，更好地解決了數(shù)據(jù)分配問(wèn)題。這種分配策略利用了遺傳算法高并行性，魯棒性，簡(jiǎn)單易行，實(shí)現(xiàn)方式規(guī)范，能夠在深度優(yōu)先搜索和廣度優(yōu)先搜索之間維持很好的平衡，以及不受優(yōu)化函數(shù)連續(xù)可導(dǎo)等性質(zhì)約束的優(yōu)良性能。第15頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一同時(shí)在應(yīng)用過(guò)程中對(duì)遺傳算法進(jìn)行了一定改進(jìn)：根據(jù)數(shù)據(jù)片段的更新檢索比來(lái)初始群體，采用適應(yīng)度比例和精英保留策略相結(jié)合的選擇機(jī)制，采用自適應(yīng)的交叉算子和變異算子。改

12、進(jìn)后的算法具有更強(qiáng)的搜索全局最優(yōu)解的能力，以及更快的搜索速度。該分配策略采用以事務(wù)處理為主的代價(jià)公式，在選擇統(tǒng)計(jì)信息時(shí)，以統(tǒng)計(jì)信息本身的重要性，獲取統(tǒng)計(jì)信息的代價(jià)，統(tǒng)計(jì)信息對(duì)代價(jià)公式的復(fù)雜性的影響為原則，忽略了對(duì)代價(jià)公式準(zhǔn)確性影響不大或很難獲取的統(tǒng)計(jì)信息，降低了代價(jià)公式的復(fù)雜度，從而減小了算法的執(zhí)行開銷。第16頁(yè)，共18頁(yè)，2022年，5月20日，10點(diǎn)10分，星期一四、參考文獻(xiàn)1邵佩英分布式數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用M北京：科學(xué)出版社，2000：72肖凌，劉繼紅，姚建初分布式數(shù)據(jù)庫(kù)系統(tǒng)的研究與應(yīng)用J計(jì)算機(jī)工程，2001，27(01)：33353王于同一種分布式數(shù)據(jù)分布的啟發(fā)式算法J計(jì)算機(jī)時(shí)代，199

13、5，4：18-204Shuoi W，Hsing-Lung CNearoptimal data allocation over multiple broadcast channelsJComputer Communications，2006，29：134113495楊洲分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)分配策略的研究D哈爾濱：哈爾濱工程大學(xué)，20076鄭宇，周廣聲分布式數(shù)據(jù)庫(kù)中的數(shù)據(jù)分配策略及其實(shí)例研究J計(jì)算機(jī)工程與應(yīng)用1997,12：17頁(yè)7楊藝分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)分配方法的研究D重慶：重慶大學(xué)，20048Ching-Ter ChangOptimization approach for data allocat

14、ion in multidisk databaseEuropean Joumal of Operational Research2002，43：210217P9Ran C,-iladi，Ephraim Korach,Rony OhayonPlacement of network resources in communication networksComputer Networks2003，43：195209P10韓啟龍，郝忠孝分布環(huán)境下實(shí)時(shí)數(shù)據(jù)的分配算法J計(jì)算機(jī)工程，2006，l(3)：525411李想.分布式數(shù)據(jù)庫(kù)中數(shù)據(jù)分配策略研究.大連：大連理工大學(xué)，2009.12師廣利，余東梅，袁占亭分布式數(shù)據(jù)庫(kù)設(shè)計(jì)中的數(shù)據(jù)分配問(wèn)題研究甘肅工業(yè)大學(xué)學(xué)報(bào)，199912：616513陳江萍分布式數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用前景現(xiàn)代圖書情報(bào)技術(shù)，1996，3：293114Kang S，Moon SA Integrated Access Control in Heterogeneous Distributed Database Systems.1992 IEEE Region 10 Conference on Co