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

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

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

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

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

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

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

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

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

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

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

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

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

13、5，4：18-204Shuoi W，Hsing-Lung CNearoptimal data allocation over multiple broadcast channelsJComputer Communications，2006，29：134113495楊洲分布式數(shù)據(jù)庫中數(shù)據(jù)分配策略的研究D哈爾濱：哈爾濱工程大學，20076鄭宇，周廣聲分布式數(shù)據(jù)庫中的數(shù)據(jù)分配策略及其實例研究J計算機工程與應(yīng)用1997,12：17頁7楊藝分布式數(shù)據(jù)庫中數(shù)據(jù)分配方法的研究D重慶：重慶大學，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ù)據(jù)的分配算法J計算機工程，2006，l(3)：525411李想.分布式數(shù)據(jù)庫中數(shù)據(jù)分配策略研究.大連：大連理工大學，2009.12師廣利，余東梅，袁占亭分布式數(shù)據(jù)庫設(shè)計中的數(shù)據(jù)分配問題研究甘肅工業(yè)大學學報，199912：616513陳江萍分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用前景現(xiàn)代圖書情報技術(shù)，1996，3：293114Kang S，Moon SA Integrated Access Control in Heterogeneous Distributed Database Systems.1992 IEEE Region 10 Conference on Co