基于Ｐ２Ｐ的數(shù)據(jù)庫管理系統(tǒng)研究

摘 要：傳統(tǒng)的大型數(shù)據(jù)庫系統(tǒng)是典型的C/S結構，系統(tǒng)中有一個中心服務器，上面運行一個大型數(shù)據(jù)庫系統(tǒng)，其他節(jié)點通過服務器訪問數(shù)據(jù)庫系統(tǒng)。但這種C/S結構容易在服務器處產生系統(tǒng)瓶頸。為了解決這個問題，將P2P的觀念引入數(shù)據(jù)庫系統(tǒng)，建立了一種C/S與P2P相結合的新系統(tǒng)。在該系統(tǒng)中，服務器和客戶端是C/S模式，同時所有的客戶端組成一個P2P系統(tǒng)。為了提高系統(tǒng)效率又將這個P2P系統(tǒng)根據(jù)節(jié)點訪問的數(shù)據(jù)表的不同劃分為多個小的P2P網絡。通過此方式客戶端之間實現(xiàn)了數(shù)據(jù)緩存的共享，從而減少了對服務器訪問的頻率，減輕了服務器的負擔，降低了系統(tǒng)發(fā)生瓶頸的可能性。該系統(tǒng)是C/S模式與P2P模式相結合的一次有益嘗試。

關鍵詞：對等網絡； 數(shù)據(jù)庫管理系統(tǒng)； 客戶機/服務器模式

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695(2008)08-2514-04

Research on P2P database management system

SHEN Xin-peng， LI Zhan-huai

(College of Computer Science Engineering， Northwestern Polytechnical University， Xi’an710072， China)

Abstract:The traditional large-scale database system is a typical C/S structure. There are server nodes and a central server in the system. The large database system is running on the server. The nodes access the database through the server. But the C/S structure easily produces the system bottleneck on the server. To solve this problem， this paper introduced the peer-to-peer concept into database management system. Built a new system which had the benefit of the C/S model and peer-to-peer model at the same time. In this system， the relation between server and the clients was C/S mode. And all the clients form a peer-to-peer system. In order to improve system efficiency， this peer-to-peer system was split into several small peer-to-peer networks according to their visiting tables.Through the approach， achieved the cache data sharing between the clients，reduced the frequency to visits to the server.lightened the burden of the server，and reduced the possibility of system bottleneck. So the system is a beneficial experiment to combine the benefit of C/S mode and peer-to-peer model.

Key words:peer-to-peer network; database management system; C/S model

0 引言

隨著計算機處理能力和存儲容量的提高以及通信技術的進步，人們可以隨時隨地接入網絡并通過直接交換共享計算機資源和服務，對等計算^[1]（peer-to-peer computing）也就應運而生了。對等網^[2]（peer-to-peer，P2P）是沒有任何集中控制的分布式系統(tǒng)，系統(tǒng)中每個節(jié)點在功能上是等同的，既是客戶機又是服務器，沒有主從之分。

Napster、Gnutella和KaZaA等P2P系統(tǒng)的廣泛應用以及P2P計算的潛在應用前景，使得P2P計算成為計算機科學極端活躍的研究課題。最初，P2P計算的研究重點是構建重疊網絡(overlay network)和建立P2P文件共享系統(tǒng)，但這時的P2P系統(tǒng)缺乏語義支持，既不能很好地滿足用戶需求，也不能有效地利用系統(tǒng)資源。由于P2P系統(tǒng)的大多數(shù)問題都可歸結為數(shù)據(jù)放置和檢索問題，數(shù)據(jù)庫研究人員加入到P2P計算研究的行列，出現(xiàn)了PeerDB^[3]、Hyperion^[4]、Piazza^[5]等P2P數(shù)據(jù)管理項目，引起P2P系統(tǒng)從文件共享向復雜查詢處理的轉換。

數(shù)據(jù)庫團體對P2P系統(tǒng)的主要貢獻是引入了模式的概念，出現(xiàn)了基于模式的P2P數(shù)據(jù)管理系統(tǒng)。這種基于模式的數(shù)據(jù)管理系統(tǒng)本質上是一種分布式數(shù)據(jù)庫系統(tǒng)。整個數(shù)據(jù)庫由多個分布在不同節(jié)點上的數(shù)據(jù)庫組成。使用P2P拓撲結構主要解決各個數(shù)據(jù)庫的不同模式的問題。

1 P2P DBMS系統(tǒng)介紹

傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)是基于C/S模式的，系統(tǒng)中有一個中心服務器，上面運行一個大型數(shù)據(jù)庫系統(tǒng)，其他節(jié)點通過服務器訪問該數(shù)據(jù)庫系統(tǒng)。如果有多個客戶同時訪問數(shù)據(jù)庫，這些訪問請求就要按照某種規(guī)則進行排隊，依次訪問數(shù)據(jù)庫。

如果用戶數(shù)量超過一定程度，訪問延遲加大，系統(tǒng)的可用性將降低。解決這個問題常用的方法是增加服務器的個數(shù)，在每個服務器上保存一個數(shù)據(jù)庫備份，設法保持數(shù)據(jù)的一致性，將訪問請求平均分配到這些服務器上。這種方法在一定程度上可以緩解服務器的壓力，但是增加了系統(tǒng)復雜性，卻不能真正解決問題，系統(tǒng)的瓶頸依然存在。隨著用戶的不斷增加，原有的問題將再次出現(xiàn)。為此，筆者結合P2P和傳統(tǒng)DBMS系統(tǒng)的特點，提出了一種全新的基于P2P的數(shù)據(jù)庫管理系統(tǒng)(P2P DBMS系統(tǒng))來解決這個問題。

在P2P DBMS系統(tǒng)中每個節(jié)點都緩存一部分數(shù)據(jù)，當某個節(jié)點需要從數(shù)據(jù)庫中讀取數(shù)據(jù)時，先在P2P系統(tǒng)中查找緩存數(shù)據(jù)，只有在找不到時，才去訪問數(shù)據(jù)庫，從而有效地減少對數(shù)據(jù)庫的訪問。當需要對數(shù)據(jù)庫中的記錄進行更新或刪除時，在數(shù)據(jù)庫中操作后，通過一定的機制，使原來緩存的數(shù)據(jù)失效，以保證數(shù)據(jù)的一致性。采用這種預取數(shù)據(jù)的方法來實現(xiàn)數(shù)據(jù)庫系統(tǒng)的好處有：a）減少系統(tǒng)對服務器的頻繁讀取工作，減輕服務器的負擔，部分消除系統(tǒng)瓶頸；b）有效地利用P2P系統(tǒng)中節(jié)點的資源，提高系統(tǒng)的響應速度。

1.1 系統(tǒng)拓撲結構

P2P DBMS系統(tǒng)是C/S與P2P模型進行完美結合的產物。它首先是一個C/S模型的系統(tǒng)，系統(tǒng)中有一個或多個運行數(shù)據(jù)庫系統(tǒng)的服務器，其他終端作為服務器的客戶端來訪問服務器上的數(shù)據(jù)。同時，系統(tǒng)中除了服務器外的其他節(jié)點組成一個P2P系統(tǒng)，服務器不參與組成P2P系統(tǒng)。原因是作為服務器，它的負擔已經很重，容易形成系統(tǒng)瓶頸，如果加入P2P系統(tǒng)將進一步加重它的負擔，使整個系統(tǒng)的穩(wěn)定性降低。系統(tǒng)拓撲結構如圖1所示。

客戶端P2P系統(tǒng)采用分布式結構化P2P系統(tǒng)進行組織。采用一致性哈希(consistent hashing) 算法^[6]將網絡中每個節(jié)點的標志映射成一個長度為M 位(bit)的二進制序列：節(jié)點標志符(pID)，并將其惟一分配給該節(jié)點。它表示為1~2M-1間的數(shù)，在一維環(huán)空間（模2M）上由小到大按順時針排列。選擇合適的M值，可以保證兩個節(jié)點的pID相同的概率接近0。

每個節(jié)點還有各種IP地址，但是IP地址在節(jié)點退出再次連入系統(tǒng)時，可能會發(fā)生變化。因此使用哈希機器CPU的ID方法來生成節(jié)點標志符。每臺機器的CPU的ID是惟一不變的，以此來確保節(jié)點多次接入系統(tǒng)時，它的pID保持不變。

在C/S數(shù)據(jù)庫系統(tǒng)中有很多個表，根據(jù)數(shù)據(jù)庫系統(tǒng)的規(guī)模將這些表分成若干個組。在進行分組時考慮各個表的規(guī)模及訪問的頻繁程度等因素，使得分組均衡。每個組就是一個小的P2P網絡，稱為表P2P網絡(table P2P network，TPN)，每個TPN網都有一個惟一的組標志符gID(gID表示為一個N位的二進制數(shù))。TPN（圖2）可以是任何一種P2P網絡結構，為了便于敘述，下面以Chord為例進行說明。每個客戶端加入它正在訪問的表對應的TPN中。當它開始訪問另一個表時，將加入這個新表所屬的TPN。這樣客戶端始終屬于它訪問的表所在的TPN中，從而可以快速地得到需要的數(shù)據(jù)緩沖?？紤]到一個客戶端經常會同時訪問多個數(shù)據(jù)表，因此允許一個客戶端同時屬于多個TPN。

同時屬于多個TPN的節(jié)點將使它所屬的TPN相互連通起來，但依然會存在部分完全孤立的TPN。這樣當這些孤立的TPN上的節(jié)點要加入其他TPN時將出現(xiàn)問題。為此，需要設計一種機制來保證所有的TPN都是相互連通的。假定一個節(jié)點的節(jié)點標志符(pID)為x(x是一個M位的二進制數(shù))，取x的前N位為y，則將節(jié)點x加入組標志符為y的TPN中，并取y為該節(jié)點的組標志符。這樣就將所有的節(jié)點根據(jù)節(jié)點標志符平均分配到了2N個TPN中，每個節(jié)點同時加入它訪問的數(shù)據(jù)表的TPN，從而使所有的TPN連通起來（圖3）。

原來系統(tǒng)中根據(jù)數(shù)據(jù)表分配的TPN數(shù)目可能小于2N個，則這些多出來的TPN(如圖3中的gID=11的TPN)就僅僅作為連通TPN網絡用的輔助TPN，它們不參與系統(tǒng)中數(shù)據(jù)緩存等工作。

數(shù)據(jù)庫系統(tǒng)建立起來后，所有的客戶端將構成P2P系統(tǒng)。整個客戶端P2P系統(tǒng)由多個TPN構成。每個TPN中的成員共享一個或多個表的數(shù)據(jù)。每個客戶端可以同時屬于一個或多個TPN，這樣做的好處有：a）可以保證整個客戶端P2P系統(tǒng)的連通性；b）如果一個客戶端經常訪問幾個表，而它同時在這幾個表的TPN中，則不需要進行TPN的切換就可以享受到這些TPN帶來的數(shù)據(jù)緩存。

1.2 節(jié)點的數(shù)據(jù)存儲

假設系統(tǒng)中有N個TPN網，每個節(jié)點最多可加入A(N>A>1)個TPN網。這A個TPN網是A個Chord網，因此需要在每個節(jié)點上分別建立A個鏈表，分別表示這A個Chord網需要的相關信息。如果該節(jié)點實際加入的TPN網小于A個，則多余的鏈表為空。

當節(jié)點P0加入P2P系統(tǒng)時，它首先要知道系統(tǒng)中至少一個節(jié)點P1，然后按如下流程處理：

a） 根據(jù)其CPU的ID值計算它的節(jié)點標志符(pID)為x。然后得到它的組標志符為y(取x的前N位二進制數(shù)為y)。

b） 在節(jié)點P1的鏈表中查找組標志符為y的TPN，如果找到，P0加入該TPN，并根據(jù)Chord算法把相關信息保存到第一個鏈表中。

c）如果P1的鏈表中沒有組標志符為y的TPN的信息，在y后面補M-N個0得到二進制數(shù)z，在P1所屬的任意一個TPN中查找z的后繼節(jié)點P2，在P2的鏈表中查找組標志符為y的TPN。如果找到，P0加入該TPN，并根據(jù)Chord算法把相關信息保存到第一個鏈表中；如果沒有找到，在P2所在的TPN中再次查找z的后繼節(jié)點，直到找到組標志符為y的TPN的信息為止。

在P1所屬的TPN中查找z的后繼節(jié)點P2，如果P2的節(jié)點標志符的前N位是y，則節(jié)點P2必屬于組標志符為y的TPN。因此使用該方法可簡單有效地找到需要的TPN信息。

在系統(tǒng)運行過程中，如果節(jié)點P0需要訪問一個數(shù)據(jù)表(該數(shù)據(jù)表TPN的組標志符為y)，需要對鏈表進行如下操作：

a） 在P0的A個鏈表中查找該組標志符為y的TPN的信息。如果在鏈表中找到，先修改訪問該鏈表的時間，并到此TPN中讀取緩存數(shù)據(jù)。

b）如果沒有找到，在y后面補M-N個0得到二進制數(shù)z，讀取P0的第一個鏈表信息，在該TPN中查找z的后繼節(jié)點P1。在P1的鏈表中查找組標志符為y的TPN，如果沒有找到，在P1所在的TPN中再次查找z的后繼節(jié)點，直到找到組標志符為y的TPN的信息為止。

c）如果P0的A個鏈表中還有鏈表為空，則將第二步得到的TPN信息填入空的鏈表中，并記錄訪問該鏈表的時間。

d）如果P0的A個鏈表中沒有空的鏈表存在，則在第二個及以后的鏈表中選擇最久沒有被訪問的鏈表，將其清空后，將第二步得到的TPN信息填入該鏈表中，并記錄訪問該鏈表的時間。

使用該方法，將節(jié)點為了訪問數(shù)據(jù)表而加入的TPN的相關信息保存在第二個及以后的鏈表中，而第一個鏈表專門用來保存節(jié)點為了保持系統(tǒng)的連通性而加入的TPN的信息。這樣既保持了系統(tǒng)的連通性，又保證了節(jié)點訪問多個數(shù)據(jù)表不受影響。

1.3 數(shù)據(jù)緩存

當一個客戶端P0需要訪問服務器的一個數(shù)據(jù)表進行一次查詢操作時，它首先在數(shù)據(jù)緩存中查找需要的數(shù)據(jù)；找不到時，才訪問服務器上的數(shù)據(jù)庫取得信息，并將得到的數(shù)據(jù)存放到TPN網中，便于其他客戶端使用。具體過程如下：

a）將SQL查詢操作轉換為對一個個表的按關鍵字查詢的操作。

b）確定客戶端是否在查詢表的TPN中，如果不在，按上面的介紹方法加入該表的TPN中。

c）將關鍵字進行哈希運算得到該數(shù)據(jù)緩存的文件標志符z。

d）在TPN中查找z的后繼節(jié)點P1，并在P1上查找是否有需要的緩存信息。如果找到相應的記錄，正常退出。

e）如果沒有找到相應的信息，訪問服務器上的數(shù)據(jù)表取得信息。

f）將從服務器上得到的數(shù)據(jù)記錄轉換為XML文本格式，存放到節(jié)點P1上。

上面的操作流程可以部分實現(xiàn)數(shù)據(jù)緩存來提高整個系統(tǒng)的可用性，但是還存在兩方面的問題：

a） 緩存數(shù)據(jù)存放在TPN中文件標志符的后繼節(jié)點上，對存放緩存的節(jié)點沒有嚴格要求，可能會將數(shù)據(jù)存放在一個不穩(wěn)定的節(jié)點或僅僅是臨時訪問該TPN的節(jié)點上，從而需要不斷地進行數(shù)據(jù)遷移，增加系統(tǒng)負擔。

b） 對同一個表中的同一條記錄，可能會有多種查詢方式，上面的方法使用一種查詢方式對應的文件標志符來存儲數(shù)據(jù)，會降低緩存數(shù)據(jù)的命中率。

問題a)的解決方法很簡單。在P2P DBMS系統(tǒng)中，每個節(jié)點的第一個鏈表存放的是節(jié)點為了保持系統(tǒng)的連通性而加入的TPN的信息。這個TPN在節(jié)點加入系統(tǒng)后就惟一地確定了，并且一直保持不變(為了敘述方便，如果節(jié)點P的第一個鏈表存放的是組標志符為y的TPN的信息，則稱節(jié)點P是組標志符為y的TPN的固定節(jié)點) 。如果將信息都存放在固定節(jié)點中，就可以減少數(shù)據(jù)遷移的發(fā)生從而提高系統(tǒng)效率。

根據(jù)前面的算法可知，組標志符為y的TPN的所有固定節(jié)點的節(jié)點標志符(pID)的前N位是y。修改緩存數(shù)據(jù)的文件標志符算法，使得文件標志符由兩部分組成，前N位是組標志符，后M-N位對記錄關鍵字進行哈希計算得到。這樣存放數(shù)據(jù)時，找到文件標志符的后繼節(jié)點必然是該TPN的固定節(jié)點，從而保證了數(shù)據(jù)存儲在固定節(jié)點上，減少了數(shù)據(jù)遷移，提高了系統(tǒng)效率。

為了解決問題b)引入索引的概念。索引就是同一條或多條記錄的多個關鍵字與文件標志符的一種對應關系。在系統(tǒng)中，每個索引也有一個惟一的索引標志符(iID)。為了方便，使用與文件標志符一樣的方法將索引標志符的前N位設置為TPN的組標志符。

為了使系統(tǒng)可以使用多種方式查詢到同一條記錄，在保存索引標志符k的節(jié)點P1上建立一個索引信息表。在索引信息表中記錄了該索引所有可能的取值和對應的緩存記錄的文件標志符。例如關鍵字“學校”對應的索引信息如表1所示。表1 關鍵字“學?！睂乃饕畔⒈?/p>

關鍵字取值文件標志符西北工業(yè)大學12，19，56西安交通大學15，28西北大學17，9，30陜西師范大學13，46增加關鍵字修改后的算法如下：

a） 將SQL查詢操作轉換為對一個個表的按關鍵字查詢的操作。

b） 確定客戶端是否在查詢表的TPN中，如果不在，將節(jié)點加入該表的TPN中。

c） 對關鍵字進行哈希運算得到該關鍵字的索引標志符z。

d） 在TPN中查找z的后繼節(jié)點P1，并在P1上的索引信息表中查找要求的關鍵字取值，如果找到，讀取相應的文件標志符，再按照文件標志符找到真正存放數(shù)據(jù)緩存的節(jié)點P2，從P2上讀取需要的數(shù)據(jù)，正常退出。

e） 如果在索引信息表沒有找到或按照文件標志符沒有找到數(shù)據(jù)，訪問服務器上的數(shù)據(jù)表取得信息。

f）將從服務器上得到的數(shù)據(jù)記錄轉換為XML文本格式，根據(jù)數(shù)據(jù)表的主鍵及取值通過哈希運算得到該記錄的文件標志符y，在TPN中查找y的后繼節(jié)點P3，將數(shù)據(jù)存放到節(jié)點P3上。

g） 根據(jù)對該數(shù)據(jù)表常用的查詢方式，生產若干個查詢索引，計算索引標志符，將索引信息記錄到索引標志符后繼節(jié)點的索引信息表中。

例如要在數(shù)據(jù)表student(主鍵是學號)中，查找學校是西北工業(yè)大學的記錄。先計算查詢關鍵字“學?！钡乃饕龢酥痉?，找到關鍵字“學?！睂乃饕畔⒈?，在表中找到“西北工業(yè)大學”對應文件標志符；然后分別取得這些記錄。如果要查找的是“西安理工大學”，在索引信息表中沒有，則訪問服務器，取得所有“學?！笔恰拔靼怖砉ご髮W”的記錄；然后將這些記錄按照它們的主鍵(學號)及取值算得文件標志符并把記錄存放在適當?shù)墓?jié)點；最后修改關鍵字“學?！钡乃饕畔⒈?。

1.4 緩存記錄的失效

數(shù)據(jù)庫系統(tǒng)的常見操作除了查詢外，還有更新和刪除操作。在進行更新和刪除操作后，數(shù)據(jù)庫中的數(shù)據(jù)發(fā)生了變化。為了保證數(shù)據(jù)的一致性，需要對客戶端的數(shù)據(jù)緩存進行失效處理。在P2P DBMS系統(tǒng)中，更新(刪除)操作的流程如下：

a）客戶端連接服務器上的數(shù)據(jù)庫進行更新(刪除)操作。

b）確定客戶端是否在操作表的TPN中，如果不在，將節(jié)點加入該表的TPN中。

c）根據(jù)該表的主鍵和對應的取值計算該記錄的文件標志符z。

d）在TPN中查找z的后繼節(jié)點P1。如果找到，在P1上修改(刪除)記錄，正常退出；如果沒有找到，正常退出。

如果是同時修改(刪除)多條記錄，如全表替換，這時可以將整個表的所有數(shù)據(jù)緩存都清除，以提高命令的執(zhí)行速度。

2 P2P DBMS系統(tǒng)分析

根據(jù)以上介紹可以發(fā)現(xiàn)P2P DBMS系統(tǒng)同時具有C/S和P2P系統(tǒng)的特點，結合了兩種系統(tǒng)的優(yōu)點，可以大大提高系統(tǒng)性能。

2.1 系統(tǒng)的健壯性分析

在P2P DBMS系統(tǒng)中，所有的客戶端組成一個P2P網絡，訪問同一個數(shù)據(jù)表的客戶端又組成一個個小的P2P網絡(TPN)，各TPN之間相互連通。每個TPN中既包含專門用來連通網絡的固定節(jié)點又包含許多訪問該TPN的節(jié)點，任意兩個TPN都有多個共用的節(jié)點。因此一個或多個客戶端的失效，不會引起系統(tǒng)癱瘓，整個P2P網絡不存在單點故障問題。同時數(shù)據(jù)緩存的存在，大大減輕了服務器的負擔，減少了同時訪問服務器進程的數(shù)量，使得服務器的瓶頸現(xiàn)象得到了很大緩解，減少了發(fā)生系統(tǒng)堵塞的可能。系統(tǒng)的健壯性得到了大大提高。

2.2 算法復雜度分析

在P2P系統(tǒng)中，對系統(tǒng)性能影響最大的是訪問節(jié)點，因此下面以訪問節(jié)點的個數(shù)為依據(jù)，簡單地分析各主要算法的系統(tǒng)開銷。以下分析都假定沒有節(jié)點失效問題。假定系統(tǒng)中有M個節(jié)點，有N個TPN，每個TPN中最多有X個節(jié)點。因此在TPN中查找節(jié)點的算法復雜度為log X。

首先看一下節(jié)點加入TPN的算法復雜度。系統(tǒng)穩(wěn)定后，任意兩個TPN都有交集，因此節(jié)點在它的第一個鏈表的TPN中可以查到要加入的TPN的至少一個節(jié)點，然后就可以使用Chord算法加入該TPN。其復雜度為log X。其實，一個節(jié)點同時保存有A個鏈表，且一段時間內，一個節(jié)點要訪問的數(shù)據(jù)表的數(shù)量是有限的，因此，設置適當?shù)莫獳值，可以保證節(jié)點一直在它要訪問的表的TPN中，從而無須進行加入操作。

進行查詢操作時，如果不考慮節(jié)點加入TPN的操作，僅僅需要一次查找索引標志符的后繼節(jié)點和一次查找文件標志符的后繼節(jié)點即可找到需要的數(shù)據(jù)。這樣兩個查找的算法復雜度都是log X。因此查詢操作的算法復雜度是log X。

進行更新(刪除)操作時，如果不考慮節(jié)點加入TPN的操作，僅僅需要一次查找文件標志符的后繼節(jié)點即可找到需要的數(shù)據(jù)，因此操作的算法復雜度是log X。

3 結束語

從以上分析可以看出P2P DBMS系統(tǒng)同時具有C/S系統(tǒng)和P2P系統(tǒng)的特點，結合了兩種系統(tǒng)的優(yōu)點，可以大大提高系統(tǒng)性能。同時P2P DBMS系統(tǒng)的健壯性很好。它的節(jié)點加入和緩存查找的算法復雜度都是log X(X是一個TPN中的節(jié)點數(shù))，在提高系統(tǒng)性能的同時，并沒有增加太多的系統(tǒng)負擔。因此是一個很有前途的新型P2P系統(tǒng)。

參考文獻：

[1]FOX G. Peer-to-peer networks[J]. Web Computing，2001，3(3):75-77.

[2]MILOJICIC D S， KALOGERAKI V， LUKOSE R，et al.Peer-to-peer computing[M]. [S.l.] :Hewlett-Packard Company， 2002:16-32.

[3]NG W S， OOI B C， TAN K L， et al. PeerDB:a P2P-based system for distributed data sharing [C]. DAYAL U.Proc of the 19th Int’l Conf on Data Engineering (ICDE). Bangalore: IEEE Computer Society Press， 2003:633-644.

[4]KEMENTSIETSIDIS A， ARENAS M. Data sharing through query translation in autonomous sources[C]//NASCIMENTO M A， OZSU M T， KOSSMANN D，et al.Proc of the 30th Int’l Conf on Very Large Data Bases. San Fransisco: Morgan Kaufmann Publishers， 2004:468-479.

[5]TATARINOV I， HALEVY A. Efficient query reformulation in peer data management systems[C]//WEIKUM G， KONIG AC， DEBLOCH S.Proc ofACM SIGMOD Int’l Conf on the Management of Data. Paris: ACM， 2004:539-550.

[6]KARGER D， LEHMAN E， LEIGHTON F， et al.Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proc of the 29th Annual ACM Symposium on Theory of Computing.1997:654-663.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文