一個行動式計算環境下以傳遞 log 為主的交易管理系統

廖學鴻、呂永和、唐學明

摘要

　　因無線通訊的技術不斷演進，使得隨時隨地可使用的 無線通訊環境日趨成熟。在無線通訊環境下，我們開始思考利用現有的無線通訊架構，來完成電腦系統之間的連繫，這就產生了行動式計算的環境。在本研究中，我們依據目前大家所採用的行動式計算環境架構，並針對行動主機與資料庫間的主從關係，提出了以傳遞 log 為主的資料庫交易管理方法。此一方法以「樂觀式並行控制」協定為核心，避免在交易執行過程中，因資料鎖定對系統整體的效率造成不利影響。另外，在資料回復方面，則採用傳回交易 記錄(log)的方式以降低行動主機與伺服主機之間的資料傳輸量。接著再依照樂觀式並行控制協定發展出正確的資料回復程序，可以全面改進行動式計算環境下交易執行的效率。

　　近年來由於無線通訊的技術不斷演進，使得「行動式計算環境」的相關研究亦日趨成熟。所謂行動式計算環境，是指人們可以利用可攜帶式電腦，無論是筆記型或掌上型，在任何時間任何地點，利用無線通訊的技術與在遠端的伺服主機相連，讀取、更動伺服主機上的資料，或是利用伺服主機的程式計算並傳回結果。這種結合了無線通訊技術與電腦應用的環境，稱之為行動式計算環境。

　　資料庫技術的發展，從集中式、分散式，到主從式，不同的系統架構，有各種交易管理的相關研究。交易管理的主要目的是要維持交易的ＡＣＩＤ特性，資料庫的交易管理模組包括「並行控制」（Concurrency Control）及「資料回復」（Failure Recovery）兩大功能。其中並行控制是用來控制交易的序列化執行，以確保資料的一致性。資料回復則用以確保系統在發生異常狀況，如天災出現、人為錯誤等，導致系統中斷、資料損毀時，能藉由資料回復的動作而將損失減少到最低。

　　在實體連線的環境下，不論是集中式、分散式，或者是主從式的架構，關於資料庫的交易管理，均已發展出相當有效率而且穩定的技術。我們有興趣的是，如何在行動式計算環境下，考慮無線通訊的特性和需求，設計出一套合適的交易管理方法，例如：如何利用暫存資料，減少訊息的傳遞，並提高資料共用的效率；又如一旦遇到斷訊或突發狀況，要如何將正在執行的交易做資料回復，不致發生資料不一致的問題…等，都是本研究所討論的主題。

　　在傳統資料庫中，關於並行控制的方法，通常採用二階段鎖定法（two-phase locking），但是在行動式計算環境下，二階段鎖定法會因傳遞訊息量過大，以及資料被鎖定時間過久而導致系統效率降低。因此，在〔１〕的研究中即指出，在行動式計算環境下，由於無法透過大量訊息傳遞來進行溝通，「樂觀式並行控制」（optimistic concurrency control, 簡稱 OCC）方法具有較高的效率。樂觀式並行控制方法最早在〔２〕中提出，在〔３〕中有更進一步的討論，並提出實作上更具有彈性的「向前驗證」（forward validation）方法，本研究即採用此一向前驗證樂觀式並行控制方法，並加以調整，使適用於行動式計算環境之下。關於資料回復方面的研究， C. Mohan在〔４〕中提出了 log-based 的ARIES資料回復方法，使用 log sequence number (LSN) 將相同交易的 log 資料加以串連，以便執行資料回復的動作。 D. Kuo 亦發表論文來說明ARIES資料回復方法〔５〕，可供參考。由於本研究與主從式資料庫架構有關，而 C. Mohan 亦曾發表過在主從式架構上的 ARIES 資料回復方法〔６〕，本文即基於此一資料回復方法的精神，提出一個以傳遞 log 為主的交易管理系統。因 ARIES 資料回復方法著重在鎖定式的並行控制方法，故本研究特將其方法加以修改，使適合於樂觀式並行控制方法。

　　本文除了第一節所討論的研究動機與背景之外，接下來在第二節介紹行動式計算的架構與交易管理，提出一個主從式行動計算環境架構，並探討這個架構的基本特性。在第三節中，我們提出在此一行動式計算環境下，所設計的樂觀式並行控制方法，並討論其適用性。在第四節中，我們針對第三節所設計的樂觀式並行控制方法，提出相對應的資料回復方法。第五節為結論及未來研究方向。

　　隨著通訊技術的發展，使用者已經可以透過無線網路擷取資料庫上的資料，這種結合電腦與無線通訊技術的系統，稱之為行動式計算環境。如圖一所示，此一環境主要是由固定主機（fixed host）與行動單元（mobile unit, MU）所組成。各固定主機間使用有線的固定網路進行資料通訊，固定主機如果擁有無線通訊傳輸功能者，我們則稱之為行動支援工作站（mobile support station, MSS）。行動單元與固定主機間的資料傳遞，則是先透過無線網路連接到行動支援工作站，再由它透過固定式網路傳送到固定主機上〔７〕。

　　如果我們將傳統的主從式架構導入行動式計算環境中， 將伺服端置於固定主機上，而客戶端則置於行動式單元上，我們稱之為行動客戶端（Mobile Client, MC），MC 與伺服端之間則透過 MSS 來傳遞訊息。與傳統主從式架構最大不同之處在於，MC 與伺服端之間由實體連線變為無線通訊網路，兩者之間的通道是由上傳通道（uplink channel）與下傳通道（downlink channel）所組成。MC 執行交易時，利用上傳通道對伺服器發出資料要求，伺服器則是透過下傳通道將所要求的資料傳給對方。

　　依上述的通訊方式，我們可提出兩種伺服端與 MC 間的訊息溝通方式：一是資料廣播法（data broadcasting），由伺服器主動將 MC 執行時所需的資料，經由下傳通道以週期性的廣播方式將資料傳遞給 MC。二是交互需求法（data on demand），MC 執行交易時必須向伺服端提出資料請求，伺服端再依MC的請求將所需資料透過下傳通道傳送給MC。本研究所討論的主從式行動計算架構所採用的是第二種方法，其前提是系統的應用偏重個別資料的查詢與更新，共用唯讀資料的情形不多。

　　主從式行動計算環境架構如圖二所示，伺服端有 database 以及存放交易記錄的 log database ，在主記憶體內有兩塊空間，其一是 server cache，存放由 database 載入系統的資料，另一個是 transmission buffer，當 MC 上的交易完成所有資料更改動作 之後，必須將所有的更改記錄（log）傳給伺服端，這些更改記錄就存於 transmission buffer 內。至於伺服端與 MC 之間的訊息傳遞，MC 透過 MSS 以無線網路的方式溝通，伺服端與 MSS 之間則是以實體連線的方式傳輸資料。 在 MC 上有一個 cache 存放向伺服端要求的資料，另外有一個 log buffer 存放交易 執行過程中的更改記錄。為簡化問題，在本研究中，我們假設一個 MC 之內， 同一時間只會有一個交易執行。

　　無線通訊的特徵是可使用的通訊頻寬不足、斷訊頻繁，使資料傳輸易受延遲等。因無線通訊的成本相當昂貴，故如何減少連線的時間及次數，就成為行動式計算環境的首要考慮因素。在理想的情形下，除了必要的資料要求以及將交易結果寫回資料庫 外，我們希望儘量利用 MC 上的暫存資料以低資料的傳輸量。在這一節我們將提出向前驗證的樂觀式並行控制（OCC-FV）方法，及其在實作上的考量。使用的架構採用上一節所提的主從式行動計算環境架構。

　　OCC方法對交易的執行抱持著樂觀的態度，認為交易之間的衝突可能性很低。因此，使用OCC方法，交易在執行的過程中不管資料讀寫的順序，一直到工作完成時，才去做驗證（validation）的工作。在OCC方法中，交易的執行分成三個階段：

(1) 讀取階段（read phase）–在此階段，交易讀取資料庫的資料，或使用暫存記憶體中的資料。而寫入動作都僅存於暫存記憶體中，而不會更新實際的資料庫。

(2) 驗證階段（validation phase）–交易進行驗證測試，以決定是否能將暫存記憶體的寫入資料拷貝到資料庫，而不會影響交易的序列化。

(3) 寫入階段（write phase）–如果交易在驗證階段成功，那麼它執行過程中所修改的資料就可以寫到資料庫中。

　　三個階段中最重要的是驗證階段，可以根據向前驗證或向後驗證的原則來確保交易執行的序列化：(a) 向前驗證（forward validation）：檢測目前正在執行的的交易，看這些交易的 read set 與待驗證交易的 write set 是否有交集，若有，則表示資料有衝突，系統將正在執行的的交易abort。這個方法的保證進入驗證階段的交易一定可以commit，且以進入驗證階段的先後來決定執行的序列化順序。其演算法如圖三所示：

　　　　Validate(Ti)
　　　　{
　　　　　valid = True;
　　　　　for each active transaction Tj in system besides Ti 
　　　　　　　if readset(Tj) ∩ writeset(Ti) ≠ {} then
　　　　　　　　　valid = False;
　　　　　if valid then
　　　　　　　enter_write_phase(Ti);
　　　　　else
　　　　　　　conflict_action(Ti);
　　　　　}

(b) 向後驗證（backward validation）：檢測待驗證交易的 read set 與最近 完成交易的 write set ，如果有交集，表示資料發生衝突，則正在做驗證的交易將會被abort。此處所說最近完成交易，指的是從待驗證交易啟動開始至此交易進入驗證階段前這一段時間，系統內完成驗證動作的那些交易。其演算法在此暫省略。

　　由上面兩種驗證方法中，向前驗證法可以選擇是自己abort或是將與自己有資料衝突的交易abort，故比較有彈性。此外，向前驗證法還可以提早檢測出資料衝突，向後驗證法則必需在交易的最後，才可以發現資料衝突，故造成許多工作上的浪費。基於效率上的考量，我們採用向前驗證的樂觀式並行控制方法。然而，向前驗證的樂觀式並行控制方法在實作上最大的困難在於，難以掌握目前正在執行的交易，因為這些交易的 read set 是動態的，而且隨時會有新的交易產生。所以對於讀取資料、建立新的交易以及執行資料驗証這三種動作，我們設計了一些方法使其在實作時不致產生問題。

　　在行動計算環境下，在交易執行的過程中，MC會不斷向伺服端發出訊息（message）。訊息送到了伺服端，會先放在訊息佇列（message queue）中，由訊息處理行程逐一處理。訊息可分為request和log兩類，訊息處理行程如果處理到型態為request的訊息，也就是屬於新建交易、讀取資料、或準備執行資料驗証這三種請求，會把訊息中的request取出，加到請求佇列（request queue）的尾端，由並行控制行程來處理。如果是處理到型態為log的訊息，這就表示MC已完成當地資料的讀取、運算或更改，並將記錄送達伺服端，這時，訊息處理行程將訊息內的log取出，在 transmission buffer 上新增一塊空間，然後將這些log放到這塊空間上。這些log都是來MC，已完成當地計算，並等待驗證的交易，它們與伺服端所掌握的 read set 和 write set 有關。

MC需要資料時，會先在cache中尋找，如果不在cache中，則向伺服端發出讀取資料的request，再由伺服端將該項資料傳回給MC，並在伺服端 read set 中記錄所讀取的資料ID。如果所需要的資料存在MC端，MC就不會向伺服端發出請求，而直接使用舊的資料，並且在 log buffer 寫入一個型態為讀取資料的log。在交易進行資料驗証之前，伺服端會利用這些log來檢查這些舊的資料是否曾被其他交易更改過。在此一方法中，顯然交易的 read set 分成兩部份，一部份在伺服端，另外一部份則在MC端， write set 則先暫存在MC端。在執行驗證程序之前，MC端的 read set 和 write set 都會以log的形式傳送至伺服端。

　　並行控制行程是一個無限迴圈的程式，不停地由請求佇列的前端拿出一個request來處理。如果所處理的request目前暫時無法處理（譬如MC端處於斷訊中、或有交易正在執行資料驗証…等），就將該項request移到請求暫存佇列的尾端，繼續等待。並行控制行程處理到由交易所發出的準備執行資料驗証，或稱之為 partial commit request，如果目前沒有其他交易在進行資料驗証的話，即可進行資料驗証。資料驗証會檢查所有正在執行交易的 read set ，看是否與進行資料驗証交易的 write set 有交集。由於伺服端所掌握的 read set 只是一部份，而不是交易全部的 read set ，所以接下來的abort動作也只有部份衝突的交易會被abort（如果交易在伺服端的 read set 被發現有衝突，就會被abort）。至於一些漏掉的交易，它們在傳回log之後，仍會被abort。在我們的設計中，系統在驗証一個現存交易之前，會先把該交易在伺服端的 read set 予以凍結，直到驗証結束為止；即被驗証的交易在驗証結束之前暫時不能要求讀取新的資料。 Read set 未被凍結的交易，仍可繼續要求讀取新的資料。另外，在驗証進行時，新建交易的 read set 也是被凍結的。這些措施都是為了避免因交易的 read set 不斷變化所造成困擾而設計的。

　　在資料驗証完成之後，系統就會啟動寫入的動作，把 transmission buffer 上型態為update的log寫入系統的 log database 中，並更改在 server cache上面的資料。等到系統進行檢查點工作時會把在 server cache上被更改過的資料寫入資料庫。寫入動作完成之後，便送出commit訊息給MC端，並且釋放 read set、write set 所佔用的空間。MC端收到commit訊息之後，會通知使用者交易完成，最後再移除 log buffer 上面的log。在cache上的資料並不移除，這些資料可留待下次交易執行時使用。

　　為了實作上的需要，在此說明在行動計算環境下，OCC-FV方法所使用到的資料結構。將分別說明 log、message、以及交易表格（transaction table）等的資料結構。

　　在MC端，當執行一項更改的動作之前，會先在 log buffer 上加入一個log；執行讀取暫存資料時會在 log buffer 上加入一個log；commit時也會產生一個log。另外，伺服端執行檢查點（Checkpoint）動作時，會記錄一個log，使用同樣的資料結構，其資料結構如下：

logrecord　record
　　LSN:　 number;　 /*更改記錄在伺服端log disk中的流水號，寫入log database時才給定*/
　　txID:　 Tansaction identifier;　 /*每個交易的代號*/
　　pageID: Page identifier;　 /*所更改的分頁代碼*/
　　Type:　 {Update,Read,Commit,Chkpt};　/*有四種型態的更改記錄*/
　　Image:　 case (Type) of　 /*log的內容依型態而有不同*/
　　　　Update: 　record
　　　　　　BeforeImage:Data item value; /*更改前的資料值*/
　　　　　　AfterImage:Data item value; /*更改後的資料值*/
　　　　　endrecord;
　　　　　break;
　　　　Read: Data item value; /*在MC舊分頁的資料值，可供伺服端比對*/
　　　　　break;
　　　　Commit: null;
　　　　　break;
　　　　Chkpt: a set of tx_table_entry; 
　　　　　/*伺服端上遇檢查點時會存下當時的transaction table*/
　　　　　break;
　　　endcase;
　endrecord;

　　這裡一共有四種型態的log，Update log為更改資料時所寫入；Read log是直接讀取MC上的暫存資料後所寫入，將來伺服端後可依這些Read log來檢查在MC上的舊分頁是否已被更改，有的話就abort該交易，並傳回這些驗証失敗的資料頁代碼。Commit log是當MC完成所有動作，最後加上去，做為交易結束，交付驗證的記號。Chkpt log則是由伺服端在檢查點時所產生，內容記錄當時的 transaction table。

　　所有MC端與伺服端之間的互動，都是以message的格式來傳遞，是所有使用的資料結構中最複雜的，其資料結構如下：

Msg　record
　　MCID: Mobile Client identifier; /*MC的代碼，當使用通道不同時，可據此辨識*/
　　txID: Transaction identifier; /*交易代碼，用以辨識是那一個交易的訊息*/
　　Type: {Start_tx,Request,Finish_read,Upload,Logs,Partial_commit,Fail,
　　　　　Ack,Commit,Abort,Shutdown,tx_state};　　/*十二種訊息*/
　　Nxt_Msg: Pointer to Msg;
　　　　/*訊息送到伺服端之後會加到訊息佇列的尾端，因此訊息是串列型態*/
　　Msg_content: case (Type) of /*訊息的內容，依訊息型態而有所不同*/
　　　　Start_tx: null; break; /*MC通知伺服端要新建交易*/
　　　　Request: pageID; break; /*MC所需要的資料分頁*/
　　　　Finish_read :null; break; /*MC通知伺服端要離線作業*/
　　　　Upload :null; break; /*MC通知準備要送log上伺服端*/
　　　　Logs: A set of logrecords; /*MC送多個log上伺服端*/
　　　　Partial_commit: null; break; /*MC通知伺服端log傳送完畢*/
　　　　Fail: null; break; /*MC通知伺服端發生錯誤或當機*/
　　　　Ack: record /*正常狀況下，伺服端回應MC的訊息*/
　　　　　AckType: {Start_tx,read,Finish_read,Upload};
　　　　　AckData: case (AckType) of /*回應訊息內容依型態而有不同*/
　　　　　　　Start_tx: transaction identifier; break;
　　　　　　　/*告訴MC交易新建成功，並附上此交易的代碼*/
　　　　　　　read: data page; break;
　　　　　　　/*回應MC的read request，附上所讀取的資料分頁*/
　　　　　　　Finish_read:null; break;　/*回應離線作業*/
　　　　　　　Upload: null; break;　/*回應傳送log*/
　　　　　　endcase;
　　　　　endrecord;
　　　　　break;
　　　　Abort: A set of inconsistent page ids; break;
　　　　/*當交易與其他交易發生資料衝突時，會附上所衝突到的資料分頁代碼
　　　　　如果是因為其他錯誤，則此欄為空*/
　　　　Commit: null; braeak; /*伺服端通知MC交易已完成確認*/
　　　　Shutdown: null; break; /*伺服端儲存媒體發生錯誤，通知MC停止新建交易*/
　　　　tx_state: {read, validation, write, commit, null}; break;
　　　　/*MC發生斷訊或錯誤時，向伺服端詢問目前交易的執行狀態時及
　　　　　伺服端回應時使用，MC向伺服端發出詢間時Msg_content為null */
　　　endcase;
　endrecord;

Message_queue: Pointer to Msg;

　　Message可以分為兩類，一類是由MC送給伺服端的，如Request、Finish_read、Upload、Logs、Fail；另一類則是由伺服端送給MC的，如Ack、Commit、Abort、Shutdown；也有MC端與伺服端兩邊互傳用的，如 tx_state。如果訊息型態是request，表示這是由MC端送給伺服端的請求，有建立新的交易的請求（Start_tx）、讀取資料的請求（Request），以及傳送log之後，等待進行資料驗証的請求（Partial_commit）。Finish_read為MC通知伺服端，MC往後不需要再讀取資料，要離線作業的訊息。Upload為MC通知伺服端準備要連線，開始傳送log的訊息。Logs內含MC傳送的log，是log的集合。Fail為MC通知伺服端，MC上已發生錯誤或當機的訊息。Ack則是伺服端回應MC的訊息，並依原來message型態而附上不同資料，附上的資料就放在AckData中。Commit為伺服端通知MC交易已完成確認的訊息；Abort則是交易發生資料衝突，被要求abort的訊息，在Msg_content部份會附上所衝突到的資料所屬的資料分頁代碼。Shutdown則是伺服端的儲存媒體發生錯誤（Media Failure）時，通知MC必須停止要求新建交易的訊息。最後是Tx_state，這是MC發生斷訊或錯誤而向伺服端詢問目前交易的執行狀態時及伺服端回應時使用。

　　訊息進入伺服端後存於訊息佇列中，然後再依FIFO方式被訊息處理行程所處理。

每一個交易從開始執行到交易結束之前，都會在交易表格中留有一個記錄，上面有目前交易的執行狀態，於是我們就可以利用交易表格來追蹤所有交易的執行。其資料結構如下：

tx_table_entry　record
　　txID: Transaction identifier;　/*交易代碼*/
　　MCID: Mobile Client identifier;　/*MC代碼*/
　　readset: Pointer to data_item  list;　/*指向目前交易已讀取的資料的串列*/
　　writeset: Pointer to  logrecord;　/*指向在 transmission buffer中，由MC傳送
　　　　　　　　　　　　　　　　到伺服端的log起始位址*/
　　halt_read_flag: Boolean;　/*標示資料驗証是否已驗証過此交易*/
　　connect_state: {Active_online, Active_offline, Hand-off, Disconnected};
　　　　　　　　　　　　　/*記錄目前MC與伺服端之間的連線狀態*/
　　tx_state: {read,validation,write,commit};　/*記錄目前交易執行所處的階段*/
　　time_out: system timestamp; 　/*MC若斷訊，計算離線時間，離線過久交易會被abort*/
　　Nxt_rec: pointer to tx_table_entry;　/*指向下一個交易表格記錄*/
　end record;

tx_table: pointer to tx_table_entry;
/*交易表格是一個動態的表格，所以必須用串列形式*/
　
data_item　record　/*為readset所指向的已讀取資料項集合*/
　　data: pageID;　/*所讀取的資料分頁*/
　　nxt_rec: pointer to data_item;　/*指向下一個已讀取的資料記錄*/
　end record;

　　交易表格是一個以tx_table_entry所組成的串列，其中的readset是一個指向目前已讀取資料的串列的指標，當交易的讀取請求被並行控制行程執行後，除了將資料以訊息方式送給MC外，也會在readset所指的串列上面再加上所讀取的這個資料項。另外當MC把 log buffer上的log送上伺服端的 transmission buffer 後，writeset這個欄位所存的指標，便會指向交易在 transmission buffer 中暫存的log的起始位址。而halt_read_flag則是記錄著資料驗証是否已驗証過此交易的readset，若此欄為True，表示已驗証過或是正在驗証，在資料驗証未結束之前，交易不能執行讀取資料的請求，因為這樣會影響readset的內容，就會導致資料驗証不正確。

　　connecte_state記錄著目前交易的執行狀態，是處於read phase、validation phase、write phase或是已commit。如果交易的log已寫入log database，而MC這時產生斷訊或當機的情況，tx_state保留commit這個狀態值，當MC重新連線之後，可以詢問伺服端，如果太久都沒有再連上伺服端，系統就會將該交易在交易表格上的記錄移除，視為abort。time_out這個欄位是記錄若MC斷訊（可能是訊號太弱、當機或是在Hand-off過程中沒有可用的通道）會將目前的系統時間記錄在此欄位，系統會去檢查這個欄位，若是已超過設定的時間，就會將這個交易在交易表格上的記錄移除。若是MC又連上，會送出型態為tx_state的訊息查詢，伺服端會以訊息通知MC交易已被abort。

　　我們以交易的執行順序，依次說明OCC-FV詳細的動作。

　　MC要求讀取一個資料項，伺服端先檢查交易表格中該交易的halt_read_flag欄位，如果是True，表示目前有其他的交易正在執行資料驗証，就要拒絕讀取的請求，並將此請求移到請求暫存佇列的後面，等待下次執行。如果請求被接收，則資料分頁傳給MC，並更改交易表格中的readset欄位。MC收到後，會將資料分頁放到cache上。所有的更改的動作均以in place方式更改cache上的資料分頁，並將logrecord依序寫在log buffer 中。當所有的動作均完成，最後會加上一個型態為commit的logrecord。

　　一進入write phase，先將交易表格上的tx_state欄位值改為write，將writeset所指型態為 update 的log寫入log database，然後送一個commit的訊息給MC。接下來依次執行寫入的動作，以inplace方式更改在 server cache 上的資料。最後消除在 transmission buffer上的log，移除該交易在交易表格上的記錄，同時交易也結束。

四、基於樂觀式並行控制的資料回復方法

4.1 背景及基本資料結構說明

　　DirtyPage  record
　　　　PageID:page identifier;　　/*記錄被交易更改過的資料分頁代碼*/
　　　　LSN: sequence number;　　　/*記錄著最後寫入這個分頁的log序號*/
　　　end record;

　　DirtyTable: pointer to the DirtyPage;

4.2 主從式行動計架構下的資料回復

　　在本小節中，我們依照在 transaction failure、system failure、以及 media failure三種狀況下，分別討論資料回復的方法。

4.2.1 Transaction Failure

4.2.2 System Failure

4.2.3 Media Failure

五、結論與未來研究方向

相關研究論文