分布式旅行預(yù)訂系統(tǒng)

1、<p><b>　　分布式旅行預(yù)訂系統(tǒng)</b></p><p><b>　　??必備知識</b></p><p>　　具備數(shù)據(jù)庫系統(tǒng)原理或與之相當(dāng)?shù)闹R是完成本課程作業(yè)的前提。假定每一個學(xué)生都已經(jīng)了解了數(shù)據(jù)庫系統(tǒng)的基本實現(xiàn)技術(shù)，包括對事務(wù)功能性的一個基本了解（例如，ACID性質(zhì)）。</p><p>　　此項課程作

2、業(yè)，建議每個學(xué)生都具備一些用JAVA語言編程的經(jīng)驗，并且對并發(fā)程序的抽象概念，比如線程、互斥很熟悉。此項作業(yè)要求學(xué)生具備JAVA線程編程（JAVA THREADS）和JAVA 遠程方法調(diào)用（JAVA RMI）的知識，但并不要求對JAVA語言的其他方面，比如圖形用戶界面工具箱（GUI TOOLKITS）、基于JAVA的數(shù)據(jù)庫互連（JDBC）、服務(wù)器端嵌入程序（SEVLETS）及網(wǎng)頁內(nèi)嵌小程序（APPLETS）等知識很了解。</p&g

3、t;<p><b>　　?課程作業(yè)簡介</b></p><p>　　作業(yè)是由幾個步驟組織起來的，這些步驟遞歸地增加程序的成分和系統(tǒng)結(jié)構(gòu)。我們給每個成分都提供了通用的接口，此外，我們還提供了一個基本的檢測代碼用來檢測基本的功能。我們還將提供若干基本的已建好的模塊，比如鎖管理器（LOCK MANAGER）。</p><p>　　實驗評分將大體根據(jù)學(xué)生提交的自

4、動進行的測試程序，一個演示程序以及一個具體的設(shè)計文檔來評定。</p><p><b>　　?任務(wù)描述</b></p><p>　　這個任務(wù)的目標(biāo)是用JAVA建立一個分布式的應(yīng)用程序以實現(xiàn)一個簡單的旅行預(yù)訂系統(tǒng)。為了完成此任務(wù)，你將要經(jīng)歷三個階段：</p><p>　　階段一 實現(xiàn)一個簡單的資源管理器(Resource Manager，一個具有

5、固定的表和操作集的非常簡易的數(shù)據(jù)庫系統(tǒng))，用來支持并發(fā)事務(wù)的ACID性質(zhì)(原子性、一致性、獨立性、持久性)；</p><p>　　階段二 實現(xiàn)一個工作流程控制器（Workflow Controller）和一個事務(wù)管理器（Transaction Manager），用來在多個資源管理器（Resource Managers）之間實現(xiàn)分布式事務(wù)處理；</p><p>　　??簡易的旅行資源管理器

6、（Simple Travel Resource Manager）</p><p>　　實現(xiàn)一個簡單的資源管理器(Resource Manager or RM)，用來支持并發(fā)事務(wù)的ACID性質(zhì)(原子性、一致性、獨立性、持久性)。具體的說，這個RM存儲著關(guān)于航班，出租車，賓館房間和客戶的數(shù)據(jù)信息。多個客戶端通過一個事務(wù)處理界面可同時訪問這個RM以查詢和更新數(shù)據(jù)。這個RM要保證這些并發(fā)事務(wù)的執(zhí)行正確性，即符合ACID性

7、質(zhì)的要求。</p><p>　　從概念上講，這個RM存儲著下列表：</p><p>　　FLIGHTS (String flightNum, int price, int numSeats, int numAvail)HOTELS(String location, int price, int numRooms, int numAvail)CARS(String location, i

8、nt price, int numCars, int numAvail)CUSTOMERS(String custName)RESERVATIONS(String custName, int resvType, String resvKey) </p><p>　　為簡單起見，作下列假設(shè)：</p><p>　　假定這里只有一條航線，并且在給定的一個班機上，所有的座位價格也一樣；flig

9、htNum是表FLIGHTS的一個主鍵（primary key）。</p><p>　　假定在同一個地方的所有的賓館房間價格也一樣；location是表HOTELS的一個主鍵。</p><p>　　假定在同一個地方的所有的出租車價格也一樣；location是表 CARS的一個主鍵。</p><p>　　custName是表CUSTOMERS的一個主鍵。</p&

10、gt;<p>　　表RESERVATIONS包含那些和客戶預(yù)訂的航班、出租車或賓館房間相應(yīng)的條目，具體的說，resvType指預(yù)訂的類型（1為預(yù)訂航班，2為預(yù)訂賓館房間，3為預(yù)訂出租車），而resvKey是表RESERVATIONS的一個主鍵。</p><p>　　在表FLIGHTS中，numAvail表示指定航班上未被預(yù)訂的座位數(shù)。對于一個給定的航班（flightNum）,數(shù)據(jù)庫一致性的條件之一是

11、，表RESERVATIONS中所有預(yù)訂該航班的條目數(shù)加上該航班的剩余座位數(shù)必須等于該航班上總的座位數(shù)。這個條件對于表CARS和表HOTELS同樣適用。</p><p>　　資源管理器（Resource Manager）的標(biāo)準(zhǔn)接口（詳見ResourceManager API）。這個接口允許每一個在RM中存儲的表中的行被添加、刪除和修改。你的工作是為每一個我們提供的接口寫出實現(xiàn)程序。</p><p

12、>　　RM支持事務(wù)處理。一個事務(wù)調(diào)用RM的start( )方法來獲取一個唯一的事務(wù)標(biāo)識（transaction id）。所有對RM的后續(xù)調(diào)用都要包括這個事務(wù)標(biāo)識。最后，事務(wù)調(diào)用commit( )或abort( )方法結(jié)束事務(wù)處理。一個典型的客戶端事務(wù)可能象以下這樣：（當(dāng)然，在現(xiàn)實中，你要檢查返回值及獲取異常。你也可以查看Client.java文件來看另一個例子）</p><p>　　int xid = rm

13、.start ();</p><p>　　// If it's cheap enough and there're seats left</p><p>　　if (rm.queryFlightPrice(xid, "347") < 300 &&</p><p>　　rm.queryFlight (xid,

14、"347") > 0) {</p><p>　　rm.reserveFlight (xid, "John", "347");</p><p><b>　　}</b></p><p>　　rm.commit (xid); </p><p>　　并發(fā)控制是通

15、過兩階段鎖（two-phase locking）來實現(xiàn)的。當(dāng)一個客戶端要求查詢或更新信息時，你的RM要適當(dāng)?shù)亟o相應(yīng)元組加鎖，并在事務(wù)正常完成（commits）或異常中斷（abort）時釋放所有的鎖。我們提供了一個鎖管理器（lock manager）幫助你完成任務(wù)。這個鎖管理器支持以下API（這里給出的是偽代碼，實際的代碼請見LockManager API）：</p><p>　　lock(xid, thingBe

16、ingLocked, read|write) throws DeadlockException </p><p>　　unlockAll(xid) </p><p>　　如前所述，xid是唯一的事務(wù)標(biāo)識。鎖管理器用超時機制（目前設(shè)為10秒）來處理死鎖。一個死鎖操作會拋出一個死鎖異常（DeadlockException）。鎖管理器還用來處理鎖的轉(zhuǎn)換（也被稱為鎖的升級）。鎖的升級發(fā)生在一個已具

17、備在某個元組上的‘讀鎖’的事務(wù)需要獲得此元組的‘寫鎖’的時候。</p><p>　　lock (xid, foo, read); // read foolock (xid, foo, write); // write foo</p><p>　　其他的事務(wù)也可能具有foo上的‘讀鎖’，因此，在鎖升級時死鎖有可能發(fā)生。</p><p>　　下面介紹如何開始你的編程工

18、作：</p><p>　　首先介紹一下對JAVA編程環(huán)境要求:</p><p>　　你要安裝Jdk1.2.2以上版本，然后如下設(shè)置環(huán)境變量（假設(shè)你的JDK安裝目錄為C:\Program Files\j2sdk1.4.0_01，且你的項目文件所在的目錄是D:\project\）：</p><p>　　Set path = ……………; C:\Program Files

19、\j2sdk1.4.0_01\bin\</p><p>　　Set classpath= .; C:\Program Files\j2sdk1.4.0_01\lib\tools.jar;C:\Program Files\j2sdk1.4.0_01\lib\dt.jar;C:\Program Files\j2sdk1.4.0_01\jre\lib\rt.jar;D:\project\</p><

20、;p>　　提供的源碼（詳見API）有兩個壓縮包：lockmgr和transaction。其中，lockmgr實現(xiàn)了LockManager的功能，你不必修改這個包中的內(nèi)容。transaction提供了一些基本的類以幫助你完成工作，它包含了ResourceManager的接口。請注意，你不要修改此文件，你的RM實現(xiàn)要基于名為ResourceManagerImpl的類（以及一些自己定義的新類），這個類提供了ResourceManager

21、的接口。你必須自己編寫接口實現(xiàn)代碼，以替代目前提供的這個ResourceManagerImpl.java文件中的接口實現(xiàn)代碼。</p><p>　　事務(wù)目錄還包含一個簡易的客戶端（詳見Client.java）。在實現(xiàn)中你可能想編寫一些更復(fù)雜的客戶端來測試你的RM，但是課程不要求你提交自己編寫的客戶端。</p><p>　　客戶端通過JAVA 遠程方法調(diào)用（JAVA Remote Metho

22、d Invocation or RMI）與RM進行通信。你可以在http://java.sun.com/docs/books/tutorial/rmi/上看到RMI的使用指南。但是，這里給出的簡易ResourceManagerImpl.java和Client.java已經(jīng)提供了這一部分所需要的所有RMI代碼。你唯一要做的是修改transaction/Makefile的第一行，以便給自己一個唯一的在RMI上注冊的端口號，這樣你就不會與那些

23、和你碰巧使用同一臺機器的人在端口號上發(fā)生沖突了（請見后）。</p><p>　　你要上交所有你編寫的源代碼文件以及一個小的README文件（說明文件）。</p><p><b>　　編程提示：</b></p><p>　　下面給出一個實現(xiàn)各個功能的方法步驟（請注意，以下各步驟并不是同一個難度的，某些步驟會比其他的步驟都難以實現(xiàn)）：</p&

24、gt;<p>　　?步驟一: 實現(xiàn)一個簡易的RM</p><p>　　先忽略事務(wù)的原子性和持久性，另外假設(shè)數(shù)據(jù)都存儲在內(nèi)存中。一種可行的實現(xiàn)方法是把數(shù)據(jù)都存儲在一個或多個哈希表（hash tables）中。你可以為每一個數(shù)據(jù)庫表建立一個哈希表，或者把所有的數(shù)據(jù)庫表連接起來組成一個哈希表。這樣，數(shù)據(jù)庫表中的每一行都可作為哈希表的一個條目，并以數(shù)據(jù)庫的主鍵為索引。你也可以用一個JAVA的類來代表每一類型

25、的行，例如，用一個與FLIGHT數(shù)據(jù)庫表相應(yīng)的類，那么這個類就要含有flightNum, price, numSeats, numAvail等成員變量和一些其他數(shù)據(jù)以實現(xiàn)事務(wù)的ACID性質(zhì)。</p><p>　　表RESERVATIONS并沒有主鍵，但是經(jīng)常以custName為索引；所以，一種可行的實現(xiàn)方法是把表RESERVATIONS和表CUSTOMERS聯(lián)合起來。這樣，就擁有了一個以custName為索引的哈

26、希表，并且每個條目都增加了resvType和resvKey兩個數(shù)據(jù)項。</p><p>　　請注意，在這個簡單的數(shù)據(jù)模型中，你只能讓同一個地方的價格保持一樣，因此，以下操作的實際結(jié)果為：</p><p>　　addCars(T1, "San Diego", 4, $52);</p><p>　　addCars(T2, "San Dieg

27、o", 7, $54);</p><p>　　11輛出租車的價格都是54美元，而并不是其中的7輛車54美元，另外的4輛52美元！</p><p>　　?步驟二: 實現(xiàn)原子性（Atomicity）</p><p>　　利用影子方法（shadowing）來實現(xiàn)事務(wù)的原子性。在內(nèi)存中保留兩個數(shù)據(jù)庫的拷貝，并且建立一個指針指向那個活躍的拷貝。把正在執(zhí)行的事務(wù)的各個

28、更新結(jié)果保留在一個獨立的哈希表中。當(dāng)這個事務(wù)正確完成時，將事務(wù)的更新結(jié)果與那個不活躍的數(shù)據(jù)庫拷貝合并，然后交換指向活躍數(shù)據(jù)庫的指針。</p><p>　　在現(xiàn)行系統(tǒng)中，唯一要處理的失敗是事務(wù)的異常中斷。由于內(nèi)存映像在進程完成時被丟棄，在這個階段并不需要任何復(fù)原方法（recover method）。</p><p>　　?步驟三 : 實現(xiàn)獨立性（Isolation）</p>&

29、lt;p>　　RM應(yīng)該為每個事務(wù)適當(dāng)?shù)亟o數(shù)據(jù)加鎖，并當(dāng)事務(wù)完成時釋放所有加在數(shù)據(jù)上的鎖。你可以試著給數(shù)據(jù)加上不同粒度的鎖。概括地說，希望你為每個操作加上可行的最輕粒度的鎖，這樣可以保證最大的并發(fā)性。RM需要恰當(dāng)?shù)亟鉀Q死鎖問題：當(dāng)一個事務(wù)遭遇了死鎖（以LockManager拋出的DeadLockException所指示），RM要強制地中斷這個事務(wù)的運行。</p><p>　　?步驟四 : 實現(xiàn)持久性（Dura

30、bility）</p><p>　　給RM加上持久性和恢復(fù)方法。所有的狀態(tài)都被存儲在磁盤上（你可以輕松地找到JAVA的java.io.ObjectOutputStream類，它可以把內(nèi)存中的一串?dāng)?shù)據(jù)保存到磁盤的一個文件中；相應(yīng)的java.io.ObjectInputStream類作用與之相反）。當(dāng)一個事務(wù)完成時磁盤映象就要做更新。影子方法是用來保證原子性的：將數(shù)據(jù)庫的兩個拷貝保存在磁盤上，另外還有一個指向活躍的數(shù)

31、據(jù)庫的指針。在啟動時，RM必須調(diào)用恢復(fù)方法（recover( )）從磁盤上它的當(dāng)前狀態(tài)恢復(fù)到原有狀態(tài)，并且能妥當(dāng)?shù)靥幚砀鱾€異常，比如調(diào)用未知的事務(wù)標(biāo)識的操作。</p><p><b>　　檢測RM的方法：</b></p><p>　　用多個客戶端和一個獨立的資源管理器來檢測這個簡易的RM。資源管理器中的Shutdown( )方法用來檢測RM是否妥當(dāng)?shù)仃P(guān)閉。所謂妥當(dāng)?shù)仃P(guān)

32、閉，就意味著它要等待所有運行的事務(wù)完成，并清理它的文件，以使RM下次啟動時，不必恢復(fù)狀態(tài)。Dienow( )方法使RM立即調(diào)用system.exit( )，以模擬一次系統(tǒng)故障，使數(shù)據(jù)庫停留在它的現(xiàn)行狀態(tài);當(dāng)RM下次重啟時，它將恢復(fù)原有狀態(tài)。dieBeforePointerSwitch() 和dieAfterPointerSwitch()方法設(shè)定標(biāo)記，以便讓RM在下一個commit操作前調(diào)用system.exit( )。細節(jié)請參閱API。