移動計(jì)算技術(shù)讀書筆記

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

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

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

4、） 故障修復(fù) （4） 數(shù)據(jù)復(fù)制 （5） 查詢處理 （6） 名字解析 （7） 異構(gòu)性 （8） 易錯(cuò)性7.2 移動數(shù)據(jù)查詢移動環(huán)境的特點(diǎn)：1、 查詢模型和查詢支持環(huán)境2、 查詢優(yōu)化標(biāo)準(zhǔn)的變化3、 個(gè)性化查詢的變化4、 脫機(jī)查詢的支持5、 查詢語言和查詢表達(dá)方式6、 查詢的不確定性和不精度性7.2.1 移動查詢模型一、移動查詢模型大體上可分為兩類：一類是基于客戶緩存和復(fù)制的模型，另一類是基于代理的模型?；诳蛻舳司彺婀芾砑夹g(shù)：利用復(fù)制、緩存技術(shù)來支持間斷條件下的查詢，即采用數(shù)據(jù)緩存技術(shù)，分析用戶訪問數(shù)據(jù)的歷史信息，并結(jié)合用戶提出的簡檔文件決定緩存那種數(shù)據(jù)?；诖淼囊苿硬樵兡Ｊ蕉深愐苿幽Ｐ偷膶Ρ?/p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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