基于Ｐ２Ｐ的數據庫管理系統研究

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

關鍵詞：對等網絡； 數據庫管理系統； 客戶機/服務器模式

中圖分類號：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）是沒有任何集中控制的分布式系統，系統中每個節點在功能上是等同的，既是客戶機又是服務器，沒有主從之分。

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

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

1 P2P DBMS系統介紹

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

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

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

1.1 系統拓撲結構

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

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

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

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

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

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

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

1.2 節點的數據存儲

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

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

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

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

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

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

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

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

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

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

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

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

1.3 數據緩存

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

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

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

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

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

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

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

上面的操作流程可以部分實現數據緩存來提高整個系統的可用性，但是還存在兩方面的問題：

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

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

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

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

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

為了使系統可以使用多種方式查詢到同一條記錄，在保存索引標志符k的節點P1上建立一個索引信息表。在索引信息表中記錄了該索引所有可能的取值和對應的緩存記錄的文件標志符。例如關鍵字“學校”對應的索引信息如表1所示。表1 關鍵字“學校”對應的索引信息表

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

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

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

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

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

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

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

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

例如要在數據表student(主鍵是學號)中，查找學校是西北工業大學的記錄。先計算查詢關鍵字“學校”的索引標志符，找到關鍵字“學校”對應的索引信息表，在表中找到“西北工業大學”對應文件標志符；然后分別取得這些記錄。如果要查找的是“西安理工大學”，在索引信息表中沒有，則訪問服務器，取得所有“學校”是“西安理工大學”的記錄；然后將這些記錄按照它們的主鍵(學號)及取值算得文件標志符并把記錄存放在適當的節點；最后修改關鍵字“學校”的索引信息表。

1.4 緩存記錄的失效

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

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

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

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

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

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

2 P2P DBMS系統分析

根據以上介紹可以發現P2P DBMS系統同時具有C/S和P2P系統的特點，結合了兩種系統的優點，可以大大提高系統性能。

2.1 系統的健壯性分析

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

2.2 算法復雜度分析

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

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

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

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

3 結束語

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

參考文獻：

[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格式閱讀原文