分布式數(shù)據(jù)庫中垂直分片算法研究.pdf

1、計算機網(wǎng)絡(luò)的日益發(fā)展和普及以及跨地域分布的企業(yè)組織機構(gòu)使得數(shù)據(jù)的存儲和應(yīng)用越來越分布化。分布式數(shù)據(jù)庫(Distributed Database)技術(shù)就是在這種環(huán)境下應(yīng)運而生的?；谶@種技術(shù)的系統(tǒng)可靠性、可用性和時間響應(yīng)方面較傳統(tǒng)的集中式數(shù)據(jù)庫系統(tǒng)有更多的優(yōu)越性，因此在實際中有著更廣泛的應(yīng)用。 在分布式數(shù)據(jù)庫應(yīng)用中片段劃分是一個非常重要的問題，它直接影響后續(xù)工作中的數(shù)據(jù)分配，進(jìn)而影響系統(tǒng)的最終運行效率和可靠性。 因為分布式

2、數(shù)據(jù)庫系統(tǒng)中事務(wù)通常情況下并不是存取關(guān)系中的所有數(shù)據(jù)，而是存取關(guān)系的子集，因此，分布式數(shù)據(jù)庫系統(tǒng)就存在數(shù)據(jù)的劃分問題，即數(shù)據(jù)的邏輯分割(分片)問題。通過將關(guān)系中的數(shù)據(jù)劃分成若干個不相交的子集，可以減少事務(wù)的存取代價。分布式數(shù)據(jù)庫設(shè)計的主要目標(biāo)之一就是數(shù)據(jù)處理的本地化，即將關(guān)系中的數(shù)據(jù)分成若干個互不重疊的子集(垂直分片的主鍵除外)，然后再按照一定的分配策略將各個片段分配到相應(yīng)的站點上，這樣使得數(shù)據(jù)盡可能存放在對它們有存取要求的事務(wù)所在的站

3、點上，從而減少遠(yuǎn)程訪問所需的通信代價，并且通過分片和分配，可以并發(fā)執(zhí)行事務(wù)。 數(shù)據(jù)分片的基本類型包括水平分片和垂直分片兩種方式，水平分片是將關(guān)系中的元組劃分為若干個不相交的子集，而垂直分片則是將關(guān)系中的屬性劃分為若干個不相關(guān)的子集，本文僅討論數(shù)據(jù)垂直分片的問題。 怎樣合理地對關(guān)系中的屬性劃分，這是數(shù)據(jù)垂直分片設(shè)計要考慮的根本問題。數(shù)據(jù)垂直分片問題對提高整個應(yīng)用系統(tǒng)運行效率、數(shù)據(jù)的可用性、DDB的效率和可靠性都有很大的影響

4、。如何使關(guān)系劃分得當(dāng)，使整個系統(tǒng)的運行效率提高，國內(nèi)外專家和學(xué)者一直致力于基于分布式數(shù)據(jù)庫的數(shù)據(jù)垂直分片的研究。由于其復(fù)雜性，一直還沒有找到一個兼顧代價和性能的最優(yōu)通用的數(shù)據(jù)垂直分片方法。 雖然大量的研究學(xué)者也提出了一些分片模型和算法，但是大多數(shù)模型和算法非常復(fù)雜難于理解或者計算工作量太大，因而很難應(yīng)用于實際環(huán)境。本論文主要在現(xiàn)有的研究基礎(chǔ)上，分析總結(jié)各類垂直分片算法的優(yōu)缺點和局限性，主要對文獻(xiàn)<'[7]>中提出的基于事務(wù)的垂直

5、分片算法的不完善之處進(jìn)行擴充改進(jìn)，提出了一種分片過程中計算節(jié)點估算代價的方法。該算法首先歸納出垂直分片算法所需的統(tǒng)計信息，然后確定以事務(wù)對磁盤的I/O次數(shù)為代價公式。 算法第一步是事務(wù)一屬性矩陣的獲取，通過對從后臺數(shù)據(jù)庫表中讀取的事務(wù)查詢語句的動態(tài)分析，獲取每個事務(wù)存取的屬性集；第二步就是在此基礎(chǔ)上進(jìn)行分片工作，按照事務(wù)的訪問頻率依次選擇每一個事務(wù)，構(gòu)造當(dāng)前節(jié)點的T分片(從根結(jié)點到當(dāng)前節(jié)點的路徑所包含事務(wù)存取的所有屬性)，計算該