支援行動資訊管理之主動式資料複製演算法 |
|
|
|
jackkcg
站務副站長  發表：891 回覆：1050 積分：848 註冊：2002-03-23 發送簡訊給我 |
http://tanet98.ndhu.edu.tw/TANET98/HOMEPAGE/paper/5a_1/5a_1.htm#references <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=big5">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<META NAME="Template" CONTENT="C:\PROGRAM FILES\MICROSOFT OFFICE\OFFICE\html.dot">
<META NAME="GENERATOR" CONTENT="Mozilla/4.06 [en] (Win95; I) [Netscape]">
<TITLE>支援行動資訊管理之主動式資料複製演算法</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#800080">
支援行動資訊管理之主動式資料複製演算法吳秀陽、張宇策
國立東華大學 資訊工程研究所 |
發表時間：2002-09-06 00:56:38
IP:61.70.xxx.xxx 未訂閱
|
|
|
|
3.2 Primary Copy Model
我們採用 primary copy model (圖二) 為一致性維護架構：針對某一資料項 (O) 的所有複製 (O-scheme) 中選出一份當作 primary copy (P(O))。P(O) 所在的伺服器必須掌握系統中所有與 O 有關的資訊，包括其複製所在位置，以及系統中所有使用者對 O 的 write 次數。而其複製所在的伺服器也必須知道 P(O) 的位置。任何一份複製在發生 write 動作時，必先通知 P(O)，P(O) 再負責通知 O-scheme 的所有複製作更新，以維護各複製版本的一致性。此外，在選擇使用何種資料複製更新協定方面，我們是先以最基本的 read-one-write-all 協定作考慮，也就是 read 可以讀任何一份複製，write 則必須待 O-scheme 的所有複製皆作更新才算完成，其成本與 O-scheme 在分散式系統中所形成的樹 (tree) 的大小成正比。其它更精妙的更新協定，本系統仍可採用，但其詳細內容及演算法並不在本文的討論範圍之內。3.3 系統資訊
在說明我們的演算法之前，我們必須先介紹演算法運作時所必須使用到的各種系統資訊。我們先定義下列名詞及符號，以方便說明系統資訊及演算法：- O1、O2、．．．．、Ok 代表系統內所有的資料項共 k 個。
- Cell1、Cell2、．．．．、Celln 代表系統內所有的基地台通訊範圍共 n 個。
- Site1、Site2、．．．．、Siten 代表系統內所有的基地台伺服器共 n 個，也是系統有線網路上的節點。
- User1、User2、．．．．、Userm 代表系統內所有的行動式使用者共 m 個。
- Prof1、Prof2、．．．．、Profm 代表系統內行動使用者的識別檔共 m 個。
- Schd1、Schd2、．．．、Schdm 代表系統內行動使用者在其識別檔內所宣告的行程表共 m 個。
3.3.1 記錄於識別檔內的存取資訊
在我們的演算法中，有一個非常重要的環節就是充分利用使用者識別檔來記錄其存取資訊，包括：使用者的行程表、讀/寫的歷史記錄 (read/write history)、以及目前的開放資料項 (open objects)。使用者事先宣告自己的行程和工作並記錄於識別檔內稱為使用者行程表。其基本內容為：在什麼時段內、位置將會在哪裡、將從事什麼工作或需要什麼資料項。例如：在醫院系統中，第五十一號使用者，在時段 01:00 ~ 05:00 時，會到內科門診去主持門診，需要所有已預約看診病患的病歷，以及最近三個月的流行病的追蹤資料。系統必須有相關的應用程式提供使用者一些有關地點、工作、資料的選單來製訂其行程表，並以文字檔的形式展現出行程表的內容以供使用者查閱。(圖三) 是一個文字檔行程表的例子。諸如資料的規劃和分類、地點、工作、各工作所需的資料項，都是由系統管理者靜態手動制定。當一個區域伺服器在讀取使用者行程表時必須透過這些制定來判定行程表中所宣告的地點是網路上的哪個節點，所宣告的工作需要哪些資料項，再將這些資料項和使用者在行程表中所特別指明的資料作聯集，而得到該使用者完整的存取需求。我們再定義下列名詞：(1)遵照行程的使用者 (on schedule)：當某個使用者在某個時間地點，而該時間地點符合這個使用者在行程表中的宣告。(2)非遵照行程的使用者 (off schedule)：當某個使用者在某個時間地點，而該時間地點不符合這個使用者在行程表中的宣告。 讀寫的歷史記錄是一個使用者對於個別資料項的讀取及寫入次數或頻率。有鑒於一個使用者並不是隨時需要存取系統內全部的資料項，在某個地點的某一段時間，所存取的資料項目有限。因此我們定義一個使用者的「開放資料項」為：該使用者位在某一區域時，若是屬於遵照行程的使用者，則行程表內這段行程中所宣告的需求資料項；以及，不論這個使用者是不是遵照行程，從進入目前所在地點開始到現在，其存取過的資料項。它的意義代表一個使用者目前的存取範圍；並且因為有些開放資料項是在行程表內所宣告，所以也包含了提前預測使用者存取動向的意義。(圖四) 表示了某個使用者的「開放資料項」的定義。|
|
|
|
3.3.2 記錄於伺服器內的存取資訊
在區域伺服器內存有下列與複製管理有關的元件：(1)資料項的複製。(2)複製管理系統控制單元。(3)區域存取資訊。其中複製管理系統控制單元就是我們主動式資料複製計畫演算法的程式碼，該演算法詳述於 3.5 節。而所謂的區域存取資訊則是包含該區域使用者們的識別檔，以及記錄哪一些是行程內使用者，以及記錄每一個資料項目前的「區域被開放讀取的數據」(local_open_read)。何謂「區域被開放讀取的數據」呢﹖若一個資料項是某個使用者現在的「開放資料項」，則我們稱這個資料項被這個使用者打開 (open)。一個資料項的「區域被開放讀取的數據」是目前所有在該區域內打開這個資料項的使用者們，對這個資料項讀取的歷史記錄總和。顯然這個記錄是動態改變的，它在邏輯上是一個提供區域伺服器查詢的表格。 P(O) 所在的伺服器內除了記錄 O-scheme 的成員之外，還必須記錄該資料項 O 的「全域被開放寫入的數據」(global_open_write)，定義為：目前所有在分散式系統全域內打開這個資料項的使用者們，對這個資料項寫入的歷史記錄總和。顯然這個記錄也是動態改變的，而且是從所有使用者的識別檔內所記錄的寫的歷史記錄加總而得。它在邏輯上也是一個提供區域伺服器查詢的表格。3.4 事件
主動式複製管理系統是以事件驅動的方式來運作。所謂事件 (event) 就是系統事先定義會在系統內發生的某種特定情況，這種情況必須是系統能偵測到的；而該情況一發生時系統必須去作因應處理，稱為事件驅動。事件有下列六種：(1) 讀取事件 (read event)：某個使用者讀取某個資料項。(2) 寫入事件 (write event)：某個使用者寫入某個資料項。(3) 更新事件 (update event)：某個資料項複製被更新。(4) 進入事件 (enter event)：某個使用者進入某個 cell。(5) 離開事件 (exit event)：某個使用者離開某個 cell。(6) 固定時間檢查事件 (time-check event)：每個區域伺服器會每隔一段固定時間作例行性的資料複製管理檢查。(7) 緊急事件 (emergency event)：其他由系統管理者所定義必須即時處理的緊急事件。3.5 緊急資料項
為了加強我們演算法的有效性，可以讓使用者在行程表內定義緊急資料項 (emergency object)，用以表示該資料項在該行程時立刻被需要；若該行程一旦發生時，我們的資料複製管理系統立刻無條件給予複製支援。(圖五) 表示在一個使用者行程表內定義緊急資料項的例子。如果系統要處理緊急資料項，則區域伺服器內的存取資訊就必須再多增加一項，紀錄每個資料項目前在該區域內「被宣告是緊急資料項的計數」(local_emergency_counter)，意思是該資料項在該區域內被多少個行程內的使用者宣告為緊急資料項。例如目前在第二十區域，共有十八個行程內的使用者將第四十資料項宣告為緊急資料項，則該區域所記錄的第四十資料項「被宣告是緊急資料項的計數」值就等於18。|
|
|
|
3.6 網路傳輸成本計算
主動式資料複製演算法的成本分析模式和前述的相關研究中各個演算法相似，我們把複製放置的節省成本和多付出更新成本做比較，以判斷複製是否放置。我們的成本分析模式是針對網路傳輸成本加以考慮，把網路上相鄰的節點間每一次的要求和回覆設定其成本等於 1；而所謂的網路距離，是指傳輸路徑上所經過的邊的數目。舉例如 (圖六)：若節點A到節點B的傳輸路徑上共經過四個邊，則稱節點 A 到節點 B 的網路距離為4，若節點 A 到節點 B 之間有一次資料存取發生，其網路傳輸成本也是 4。所以一次本地讀取比遠地讀取節省成本 d，d 為兩者網路距離；同理多更新一份複製一次所多耗費的成本也是 d。 假設某節點對一個資料項 Oj 的開放讀取平均是每單位時間 local_open_readj 次，而 Oj 的全域被開放寫入平均是每單位時間 global_open_writej 次。將存有 Oj 的一份複製的情況，和沒有 Oj 複製的情況相比較，前者比後者每單位時間總共節省成本是 (local_open_readj * d)，總共多花費的更新成本是 (global_open_writej * d)。當 (local_open_readj * d) >= (global_open_writej * d) 時，也就是 (local_open_readj) >= (global_open_writej) 時，表示本地伺服器存有一份 Oj 的複製是有利的。當 (local_open_readj * d) < (global_open_writej * d) 時，也就是 (local_open_readj) < (global_open_writej) 時，表示本地伺服器存有一份 Oj 的複製是不利的。這就是主動式資料複製演算法的成本計算基礎。3.7 演算法
我們以事件驅動、分散式處理的形式來設計主動式資料複製演算法，它們常駐在每個伺服器中，包括下列個組成單元：(1)讀取演算法 (read algorithm) 。(2)寫入演算法 (write algorithm) 。(3)複製更新演算法 (update algorithm) 。(4)進入演算法 (enter algorithm) 。(5)離開演算法 (exit algorithm) 。(6)固定時間檢查演算法 (time-check algorithm) 。(7)緊急事件演算法 (emergency enter & exit algorithm) 。(圖七) 表示出常駐在各區域伺服器中事件驅動形式的主動式資料複製演算法架構。|
|
|
|
|
|
|
| When (the event Useri reads Oj occurs) { if (Oj is not an open object of Useri ) { Add Oj to the list of open objects of Useri ; local_open_readj := local_open_readj readij ; global_open_writej := global_open_writej writeij ; } readij := readij 1; local_open_readj := local_open_readj 1; if (no local replica of Oj exist) AND (local_open_readj >= global_open_writej) Allocate a replica of Oj and inform P(Oj); } | When (the event Useri writes Oj occurs) { if (Oj is not an open object of Useri ) { Add Oj to the list of open objects of Useri ; local_open_readj := local_open_readj readij ; global_open_writej := global_open_writej writeij ; } writeij := writeij 1; global_open_writej := global_open_writej 1; } |
|
|
|
|
|
|
| When (an update to a replica of Oj occurs) { if (local_emergency_counterj = 0) AND (local_open_readj < global_open_writej) Discard the replica of Oj and inform P(Oj); } | When (the event that Useri enters the cell occurs) { if (Useri is on schedule) { for all Oj required in Schdi { Add Oj to the list of open objects of Useri ; local_open_readj := local_open_readj readij ; global_open_writej := global_open_writej writeij ; if (Oj is an emergency object) local_emergency_counterj := local_emergency_counterj 1; if (no local replica of Oj exist) AND ( (local_open_readj >= global_open_writej) OR (local_emergency_counterj > 0) ) Allocate a replica of Oj and inform P(Oj); } } } |
|
|
|
|
|
|
| When (the event that Useri exits the cell occurs)
{ for all open objects Oj of Useri { Remove Oj from the open objects of Useri ; local_open_readj := local_open_readj - readij ; global_open_writej := global_open_writej - writeij ; if (Oj is an emergency object requested) local_emergency_counterj := local_emergency_counterj - 1; if (Oj has a replica in the site) AND &nbs
------
********************************************************** 哈哈&兵燹 最會的2大絕招 這個不會與那個也不會 哈哈哈 粉好 Delphi K.Top的K.Top分兩個字解釋Top代表尖端的意思,希望本討論區能提供Delphi的尖端新知 K.表Knowlege 知識,就是本站的標語:Open our mind |
系統時間：2024-05-02 15:44:44
聯絡我們 | Delphi K.Top討論版
| 本站聲明 |
|
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！ |