移動計算技術讀書筆記

1、題目 題目作者名 孫杰, 作 者 張傳楷, 作者1(軟件學院 (系)全名,省 市(或直轄市) 郵政編碼) 單位2(軟件學園(系)全名,省 市(或直轄市) 郵政編碼)7.移動數(shù)據(jù)管理及移動數(shù)據(jù)庫 一、 移動數(shù)據(jù)庫概述什么是移動數(shù)據(jù)庫？移動數(shù)據(jù)庫：移動著的分布式數(shù)據(jù)庫，支持移動計算的分布式數(shù)據(jù)庫。 即：（1）、人在移動是，可以訪問數(shù)據(jù)庫；（2）、人可以帶著數(shù)據(jù)庫移動。一般認為，移動數(shù)據(jù)是分布式數(shù)據(jù)庫的推廣，是支持移動計算的分布式數(shù)據(jù)庫，由于移動終端是諸如掌上電腦、PDA、車載設備、移動電話等嵌入式設備，因此，又被成為嵌入式移動數(shù)據(jù)庫系統(tǒng)。二、移動數(shù)據(jù)庫應用移動數(shù)據(jù)庫將在移動據(jù)算平臺、家庭信息環(huán)境、

2、通訊計算平臺、電子商務平臺、車載計算平臺等領域得到廣泛的應用。移動數(shù)據(jù)庫主要應用領域： 公共信息發(fā)布 實時數(shù)據(jù)采集 位置相關查詢 配合GPS等技術電子商務D移動商務7.1移動數(shù)據(jù)庫的特性 標題21、計算平臺的移動性2、網絡短接頻繁性3、網絡條件的多樣性4、網絡通信非對稱性5、移動計算平臺電源能力的有限性6、低可靠性7、系統(tǒng)的高伸展性等一、理想的移動數(shù)據(jù)庫系統(tǒng)應實現(xiàn)以下四個目標：（1） 克用性和伸縮性（2） 移動性（3） 可串行性（4） 收斂性二、什么是分布式數(shù)據(jù)庫？ 數(shù)據(jù)物理上被存放在網絡的多個節(jié)點上，邏輯上是一個整體。三、移動數(shù)據(jù)庫與分布式數(shù)據(jù)庫的差別具體表現(xiàn) （1）位置特性 分布式數(shù)據(jù)庫：

3、處理的對象位置是透明的，事務所在位置清楚且不變化（2）不同的代價/性能觀 分布式數(shù)據(jù)庫中的最佳解決方案因移動性、機損跨區(qū)、通信的不對稱性等因素，在移動計算環(huán)境中有可能不在使用。（3）事務處理的負載型 由于移動計算環(huán)境的特性：移動事務處理比分布數(shù)據(jù)庫系統(tǒng)中的事務處理更復雜。由于用戶常常要求在間斷期間進行數(shù)據(jù)操作；所以對于本地數(shù)據(jù)庫的自治性要求比較高。在移動事務處理模型的設計中必須考慮無線網絡的有限帶寬和通信的不對稱性等移動計算環(huán)境特征，必須提供對移動終端斷接操作的支持。還必須保持數(shù)據(jù)庫系統(tǒng)ACID要求的基礎上支持移動的事務處理。四、移動數(shù)據(jù)庫的基本特點 （1） 移動性 （2） 移動事務處理 （3

4、） 故障修復 （4） 數(shù)據(jù)復制 （5） 查詢處理 （6） 名字解析 （7） 異構性 （8） 易錯性7.2 移動數(shù)據(jù)查詢移動環(huán)境的特點：1、 查詢模型和查詢支持環(huán)境2、 查詢優(yōu)化標準的變化3、 個性化查詢的變化4、 脫機查詢的支持5、 查詢語言和查詢表達方式6、 查詢的不確定性和不精度性7.2.1 移動查詢模型一、移動查詢模型大體上可分為兩類：一類是基于客戶緩存和復制的模型，另一類是基于代理的模型。基于客戶端緩存管理技術：利用復制、緩存技術來支持間斷條件下的查詢，即采用數(shù)據(jù)緩存技術，分析用戶訪問數(shù)據(jù)的歷史信息，并結合用戶提出的簡檔文件決定緩存那種數(shù)據(jù)。基于代理的移動查詢模式二、兩類移動模型的對比

5、 基于緩存和復制技術的模型具有獨特的優(yōu)點，可以有效的支持斷接的查詢，但此類模型應用上具有局限性：要求移動設備端具有存儲管理數(shù)據(jù)、數(shù)據(jù)同步等能力，承擔處理任務比例大；不適合于高度動態(tài)的數(shù)據(jù)庫查詢。 基于代理的移動模型有著不可替代的作用，適用于受客戶機，適合搞查詢高度動態(tài)數(shù)據(jù)。7.2.2 移動查詢語言1、 位置相關查詢1）、位置敏感查詢2）、位置相關查詢2、與時空相關查詢語言-FTL FTL主要使用了兩個關于未來狀態(tài)的算子UNTIL和NEXTTIME。形如 f UNTIL g 的語句表示當且僅當以下兩個情形之一發(fā)生時滿足：g在這時滿足或將來未來某個狀態(tài)下滿足并且知道g滿足前f是持續(xù)滿足的；形如NE

6、XTTIME f 的語句表示當且僅當f在下一次滿足的時候滿足。在DOMINO系統(tǒng)中，一個查詢由如下語法來定義： RETRIEVE<targets-list>WHERE <condition>此處condition由FTL語句給出如果一個不斷移動的用戶連續(xù)發(fā)出位置相關查詢，則按照位置條件將以前查詢結果進行緩存，可以使用花奴才能內部分數(shù)據(jù)滿足部分查詢要求，從而加快響應速度，減少通信開銷，提高查詢處理效率。7.2.3 弱連接下的移動查詢技術弱連接：具有易中斷、低帶寬、高延遲或高費用等特性的通信鏈路。強連接：典型固定計算機網絡，帶寬高，費用低。無線移動通信網絡的一個基本特性是弱

7、連接性在應用層的查詢處理中如何適應這話總網絡環(huán)境特性的變化構成了移動查詢的關鍵技術之一。兩種方法：最直接的做法：利用復制、緩存技術來支持斷接條件下的查詢，即采用數(shù)據(jù)緩存技術，分析用戶訪問數(shù)據(jù)的歷史信息，并結合用戶提出的簡檔文件決定緩存那種數(shù)據(jù)。另一種做法：采用代理技術，亦稱適應性中間件技術。實際上就是一種根據(jù)數(shù)據(jù)流類型進行的有損壓縮，目的是使應用能適應多變的網絡環(huán)境。7.2.4 支持移動查詢的人機交互技術易操作的人機界面 由于移動計算機的體積越來越小，鍵盤輸入會代之以筆輸入、圖形或語言輸入、傳統(tǒng)的數(shù)據(jù)庫人機界面必須加以改進?？梢暬樵冋Z言表達 支持以單機圖標的方式構造查詢7.2.5 省電查詢與

8、查詢優(yōu)化查詢優(yōu)化的主要目標:提高間斷狀態(tài)下移動數(shù)據(jù)庫的可用性和查詢效率，減少查詢引起的通信開銷，減少功耗，提高查詢的可伸展性。移動通信在很多場合無法不保證始終具有可用的鏈路，未來保證提供用戶可用的、正常的服務，必須支持斷接查詢。斷接查詢主要通過預存與緩存技術來實現(xiàn)廣播查詢: 廣播數(shù)據(jù)組織方法、索引方法； 數(shù)據(jù)廣播調度算法、三層復制體系結構間斷查詢： 卡內基梅隆大學CODA系統(tǒng) 緩存與同步算法7.3 移動數(shù)據(jù)管理7.3.1 數(shù)據(jù)廣播一、 定義所謂數(shù)據(jù)廣播是指數(shù)據(jù)庫服務器把大多數(shù)移動用戶頻繁訪問的數(shù)據(jù)組織起來，周期性地廣播給移動終端，是移動用戶以最小的代價有選擇性地接收數(shù)據(jù)。二、 廣播的局限性廣播

9、是順序進行的，用戶需要持續(xù)保持接收聽狀態(tài)知道所需數(shù)據(jù)出現(xiàn)。數(shù)據(jù)訪問時被動的，訪問延遲與廣播數(shù)據(jù)量成正比。利用數(shù)據(jù)廣播訪問數(shù)據(jù)庫僅僅適用于查詢輸入數(shù)據(jù)集與結果數(shù)據(jù)集相差不大的情況。具有“拉”服務特征的從移動終端發(fā)出的查詢能有更多自主性和針對性?！巴啤薄ⅰ袄狈盏慕Y合可以獲得更好的綜合性能。三、 數(shù)據(jù)廣播的所研究的主要問題如何組織數(shù)據(jù)廣播信道中的數(shù)據(jù)，如何在廣播信道總分配數(shù)據(jù)和索引，即數(shù)據(jù)調度問題。衡量數(shù)據(jù)廣播調動算法的參數(shù)有兩個，即訪問時間與調度時間。四、 數(shù)據(jù)廣播的若干概念訪問時間：也稱訪問時延指從移動終端提出數(shù)據(jù)請求開始，到用戶從數(shù)據(jù)廣播中得到結果為止所需的時間。訪問時延決定了移動終端查詢

10、的響應時間。訪問時延由兩個部分組成：探測等待和廣播等待。調度時間：咋完成一個訪問請求期間，移動終端保持偵聽廣播的總時間。移動終端必須保持在活躍才能監(jiān)聽廣播信道的信息，因此調度時間的長短決定了移動終端的電能消耗。五、訪問時延與調度時間的優(yōu)化可以降電能消耗，這也是廣播數(shù)據(jù)組織與調度的主要依據(jù)。 （1）訪問時延優(yōu)化 平坦調度：將所有及誒聽數(shù)據(jù)廣播的客戶機所需的數(shù)據(jù)對象簡單地并在一起，由服務器周期地廣播，每個周期內每個對象都出現(xiàn)一次且只有一次。多盤廣播調度 將數(shù)據(jù)重新組織，根據(jù)數(shù)據(jù)對象的訪問概率，服務器確定每個對象在廣播中所占的最佳比例。（2）調度時間的優(yōu)化 在完成一個訪問請求期間，移動客戶機保持接聽

11、廣播的總時間 1）調度時間最優(yōu) 簡單索引平坦調度（SIFS） 是最簡單的索引方法，在每個平坦調度的廣播周期的其實處插入索引信息，每個廣播數(shù)據(jù)單元都有附帶的一個地址指針，這個指針指向下一個廣播周期中的索引段的開始地址，移動終端在訪問廣播數(shù)據(jù)時，首先接聽當前的一個數(shù)據(jù)單元，確定廣播中下一個索引段的地址并等待索引的到來，并轉入休眠狀態(tài)，知道所需的數(shù)據(jù)項開始廣播時重新激活，最后接受數(shù)據(jù)項。 2）簇集索引 高度索引方式包括（1，m）索引與分布式索引，它們均被稱作簇集索引，所謂簇集索引是指具有ixangtong屬性值的數(shù)據(jù)在隊列中連續(xù)出現(xiàn)。 （1，m）索引是指在一個文件的廣播周期中索引會被播出m次，整個索

12、引被放在數(shù)據(jù)隊列的每個片段（1/m）之前。 4）訪問時延 探測等待時間為（index+L/m）/2,找到索引段 廣播等待時間為（m*index）+L）/2+C，找到記錄并下載完成 訪問時延=探測等待時間+廣播等待時間=(m+1)*index+(1/m+1)*L/2+C 5)調諧時間 第一次探測是得到下一索引段的指針，然后，根據(jù)索引樹的指針K次探測，找到第一個記錄，最后還需要C次用以下載所有的記錄。調諧時間=1+K+C通過上面的公式，可以計算出最優(yōu)m值，讀值使得訪問延遲到達最小。7.3.2 移動數(shù)據(jù)復制與同步復制的主要目的： 提高移動計算系統(tǒng)的可用性，可靠性以及訪問性能。傳統(tǒng)的復制策略： 靜態(tài)的

13、，由于系統(tǒng)管理員統(tǒng)一安排好復制結構就固定不變了。一、 兩級復制機制針對移動客戶機頻繁斷接的特點而提出構成移動數(shù)據(jù)庫的節(jié)點類型。 數(shù)據(jù)庫服務節(jié)點直接連串到固定網絡上，維護數(shù)據(jù)庫的第一級復制。移動節(jié)點通過無線網絡與基節(jié)點連接，維護數(shù)據(jù)庫第二級復制。在多個服務器上建立副本可保證移動終端移動到任何位置都能就近訪問服務器得到所需信息。二、 兩級復制移動節(jié)點的每個復制數(shù)據(jù)對象都維護兩個版本 主版本從服務器節(jié)點得到的最新值 暫態(tài)版本斷接對于由本地暫態(tài)事務更新的對象值兩類事務 基事務只在對象主節(jié)點上執(zhí)行，并更新版本 暫態(tài)事務間接時對本地暫態(tài)數(shù)據(jù)操作，產生新的暫態(tài)版本，以后將產生一個基事務，以更新數(shù)據(jù)只能訪問主

14、節(jié)點是基節(jié)點或是本身的數(shù)據(jù)對象不能訪問其他移動節(jié)點的數(shù)據(jù)。三、 兩級復制的原理移動節(jié)點處于聯(lián)機狀態(tài) 從主節(jié)點復制數(shù)據(jù)移動節(jié)點處于斷接狀態(tài) 能夠繼續(xù)使用節(jié)點上的數(shù)據(jù)庫 由暫態(tài)事務來處理數(shù)據(jù)對象移動界定啊結束斷接，重新與基節(jié)點相連 丟棄基數(shù)據(jù)對象的暫態(tài)版本 將移動節(jié)點所有的暫態(tài)事務及其輸入參數(shù)傳送給基節(jié)點，由基接待你按照暫態(tài)事務在移動節(jié)點上的提交順序依次執(zhí)行對應的基事務。四、 斷接情況下的復制有2種方法1、樂觀復制 2、動態(tài)復制五、 三級復制為增強系統(tǒng)的靈活性與可伸縮性，提出了一種基于客戶緩存、空中復制、服務器級復制的三級復制移動數(shù)據(jù)庫系統(tǒng)結構TTR 啟發(fā)式多盤調度算法 針對于空中復制，設計了一種

15、數(shù)據(jù)廣播的啟發(fā)式多盤調度算法。 該算法將待廣播數(shù)據(jù)項分配到K個具有不同廣播頻率的盤中，并根據(jù)各盤的平均訪問概率的平方根之比確定其相對廣播頻率，最終生成一種多盤數(shù)據(jù)廣播調度序列。六、 三級復制的特點在TRR體系結構中，服務器紙復制通過在告訴網絡中復制數(shù)據(jù)，不僅提高了整個數(shù)據(jù)庫系統(tǒng)的可用性，而且使以哦對那個終端在任何一個無限網絡單元都可以就近訪問數(shù)據(jù)，從而分組了服務器的開銷。服務器紙復制于移動終端緩存具有交互作用的特性，在保證系統(tǒng)收斂性的基礎上，針對弱一致性與可變一致性情形獲得事務執(zhí)行可串行性。七、 復本的一致性維護策略從不同的角度，一致性維護策略可以有若干種分類： 由服務器方發(fā)起的更新傳送策略，

16、由客戶方發(fā)起的請求維護策略。服務器可以分為有狀態(tài)服務器、無狀態(tài)服務器與混合狀態(tài)服務器。八、 移動終端與服務器的3種同步策略1）、回調策略2）、按需請求策略3）、定期廣播更新策略7.3.3 數(shù)據(jù)緩沖與預存對于頻繁訪問的數(shù)據(jù)在本地進行緩存可以減少訪問延遲，降低網絡開銷。緩存技術的目的：通過在客戶機上緩存部分數(shù)據(jù)，達到減少訪問數(shù)據(jù)庫服務器，提高性能。傳統(tǒng)的緩存技術要求客戶機經常與服務器保持連接一、緩存失效報告廣播技術客戶機緩存的原因:減少通信量，避免網絡堵塞緩存失效報告：由服務器發(fā)出的，通過移動客戶機內緩存的數(shù)據(jù)變?yōu)槭У膱蟾?。緩存失效報告廣播技術的目的：使客戶機的緩存與服務器保持同步，服務器定期或

17、異步地廣播緩存失效報告。二、緩存失效報告廣播技術 時間戳廣播算法 服務器定期地廣播失效報告，失效報告由最近w個時間單位內被更新的數(shù)據(jù)對象標志id及其最新時間戳ts參數(shù)對（id，ts）組成。 若在失效報告中，某個對象的時間戳逼緩存中對應數(shù)據(jù)對象的時間戳新，則從緩存中清楚該對象。 如果失效報告中沒有該對象的時間戳，則將緩存中該對象的時間戳更新為此次失效報告的時間戳。 失效終端算法三、移動環(huán)境下緩存替換策略五、 預取技術根據(jù)移動用戶的行為，猜測用戶將要用到的數(shù)據(jù)，在數(shù)據(jù)使用前預先取到移動終端的緩存中。CMU提出了TIP預取策略。7.4 移動事務及事務處理 事務概述 數(shù)據(jù)庫事務的概念：所謂一個事務是由

18、一系列的讀寫操作組成的操作，以begin操作開始，以一個夭折操作或提交操作中止，它是數(shù)據(jù)庫的邏輯工作單位。移動事務是由移動端提交的事務，它是分布事務的一種，其中部分計算在移動終端上執(zhí)行，而其他部分在固定主機上執(zhí)行。一、 數(shù)據(jù)庫事務數(shù)據(jù)庫事務：工作的一個邏輯單元一個事務由一系列操作組成，從一個begin操作開始，以一個提交活或者中止結束。二、 數(shù)據(jù)庫事務ACID原子性：要么全都執(zhí)行，要么全都不執(zhí)行一致性：事務在完成時，必須所有的數(shù)據(jù)都保持一致隔離性：并發(fā)執(zhí)行的各個事務之間不能相互干擾持久性：事務完成之后，它對于系統(tǒng)的影響是永久的?？赡苁故澄顰CID特新遭到破壞的因素有以下兩種情況：（1）、多個事

19、務并發(fā)執(zhí)行時，不同事務的操作交叉執(zhí)行。（2）、事務在運行過程中被強行中止。7.4.2 移動事務特征移動事務：在移動終端上發(fā)起執(zhí)行的事務。它實際上是一種分布事務，其中一部分計算放在移動終端上完成，而其他部分則交給固定節(jié)點完成。移動客戶發(fā)出移動事務的方式有兩種：（1）、在一個請求消息中發(fā)送事務全部操作，移動客戶與協(xié)調器的交互以整個事務為基本單元，在發(fā)出事務請求后，將執(zhí)行控制權交給協(xié)調器，直到該事務執(zhí)行完畢。（2）、一個事務操作分多次發(fā)送。一、 移動事務處理的特點（1）、移動性（2）長事務（3）、易錯性（4）、異構型7.4.3 關鍵問題及技術1、移動事務的一致性2、移動事務的持久性3、移動事務的過區(qū)切換4、移動事務的斷接與恢復一般的處理一致性問題存在以下3種方法： （1）、可任意讀/任意寫的弱一致性復制 （2）、延遲的收斂性控制 （3）、每次寫操作都進行依賴關系的檢查7.4.4 移動事務處理模型理想的移動事務處理模型特點1 較低的事務夭折率2 正確性3 低通信代價和高并行性4 自