發(fā)布時間：2019-05-15 03:28

【摘要】：進(jìn)入21世紀(jì)以來,大規(guī)模分布式系統(tǒng)和云計算日益流行。為滿足新平臺和新計算模式對系統(tǒng)的性能、可用性、容錯性、可擴(kuò)展性等指標(biāo)的需求,底層的數(shù)據(jù)存儲系統(tǒng)通常采用分布數(shù)據(jù)技術(shù)—這包括數(shù)據(jù)分區(qū)技術(shù)和數(shù)據(jù)復(fù)制技術(shù)。然而,與此同時,分布數(shù)據(jù)帶來了數(shù)據(jù)一致性問題：對于上層應(yīng)用而言,如何理解處于分布形態(tài)的數(shù)據(jù)?什么叫作數(shù)據(jù)是一致的?又該如何像使用(集中式)共享數(shù)據(jù)一樣方便且正確地使用分布數(shù)據(jù)?從技術(shù)角度來說,上層應(yīng)用以何種順序觀察到作用在底層分布數(shù)據(jù)上的并發(fā)更新?又如何基于分布數(shù)據(jù)所提供的更新順序性質(zhì)編寫程序并論證其正確性?作為管理分布數(shù)據(jù)的中間件,分布共享數(shù)據(jù)服務(wù)在分布數(shù)據(jù)之上向上層應(yīng)用提供符合某種規(guī)約的共享數(shù)據(jù)抽象。由于以數(shù)據(jù)一致性為核心,有一系列的固有權(quán)衡,不存在普適的、完美的一致性解決方案,數(shù)據(jù)一致性問題因此成為分布共享數(shù)據(jù)服務(wù)中一項具有挑戰(zhàn)性的研究課題。從歷史角度來看,數(shù)據(jù)一致性問題并非為分布式系統(tǒng)和云計算領(lǐng)域所獨(dú)有,對它的研究可追溯到多處理器系統(tǒng)和并行計算的發(fā)端時期。但是,傳統(tǒng)的“以程序為導(dǎo)向、強(qiáng)調(diào)正確性”的數(shù)據(jù)一致性理論并不能很好地體現(xiàn)新平臺和新計算模式下日益凸顯的應(yīng)用價值觀。一方面,不同應(yīng)用甚至同一應(yīng)用中的不同實體,對數(shù)據(jù)一致性有著不同需求。一致性理論需要融合不同強(qiáng)弱程度的數(shù)據(jù)一致性,甚至融合一致的數(shù)據(jù)狀態(tài)與不一致的數(shù)據(jù)狀態(tài)；另一方面,應(yīng)用關(guān)于數(shù)據(jù)是否一致的“正確性”標(biāo)準(zhǔn)變得模糊。一致性理論需要從連續(xù)譜的角度—而非“一致”與“不一致”的二元視角—看待數(shù)據(jù)一致性,以滿足應(yīng)用對數(shù)據(jù)一致性的更精細(xì)的量化需求。為體現(xiàn)新平臺和新計算模式下日益凸顯的應(yīng)用價值觀,本文提出“以應(yīng)用為導(dǎo)向的”、“多樣化,可調(diào)節(jié)；精細(xì)化,可度量”的數(shù)據(jù)一致性問題研究理念�！岸鄻踊�,可調(diào)節(jié)”指的是,數(shù)據(jù)一致性理論應(yīng)該支持來自應(yīng)用的、更為多樣的一致性需求,并允許應(yīng)用在運(yùn)行時動態(tài)選擇或調(diào)節(jié)其一致性需求；“精細(xì)化,可度量”指的是,數(shù)據(jù)一致性理論應(yīng)該支持來自應(yīng)用的、更為精細(xì)的一致性需求,并能向應(yīng)用提供有關(guān)一致性服務(wù)質(zhì)量的量化信息。落實“多樣化,可調(diào)節(jié)；精細(xì)化,可度量”的研究理念,需要解決來自一致性模型、一致性實現(xiàn)機(jī)制以及一致性度量三個維度的挑戰(zhàn)。這包括,如何形式化定義“多樣化”的一致性模型、如何在盡可能通用的系統(tǒng)架構(gòu)下實現(xiàn)應(yīng)用動態(tài)調(diào)節(jié)一致性的功能、如何形式化定義“精細(xì)化／量化”的一致性模型以及如何設(shè)計高效的一致性模型驗證算法或者建立合適的數(shù)學(xué)模型以量化一致性程度。本文即專注于應(yīng)對這些挑戰(zhàn),以更好地落實“多樣化,可調(diào)節(jié)；精細(xì)化,可度量”的研究理念。本文的主要工作如下：1.在充分分析了數(shù)據(jù)一致性問題研究的歷史階段和發(fā)展趨勢的基礎(chǔ)上,為體現(xiàn)大規(guī)模分布式系統(tǒng)和云計算模式下日益凸顯的應(yīng)用價值觀,提出了“以應(yīng)用為導(dǎo)向的”、“多樣化,可調(diào)節(jié)；精細(xì)化,可度量”的一致性問題研究理念,并總結(jié)出涵蓋“一個基礎(chǔ),三個維度”的研究思路：以數(shù)據(jù)類型(包括讀寫寄存器與事務(wù))為基礎(chǔ),以一致性模型、一致性實現(xiàn)機(jī)制和一致性度量為維度。其中,研究理念“多樣化,可調(diào)節(jié)”體現(xiàn)在一致性模型和一致性實現(xiàn)機(jī)制兩個維度上,而“精細(xì)化,可度量”體現(xiàn)在一致性模型和一致性度量兩個維度上。2.提出并解決了針對讀寫寄存器的Pipelined-RAM一致性模型驗證問題(theproblem of Verifying Pipelined-RAM Consistency;簡稱VPC)。具體而言,根據(jù)(1)讀寫操作記錄是否涉及多寄存器(Single or Multiple)以及(2)寫操作是否允許寫入重復(fù)值(Unique or Duplicate),我們考察VPC問題的四種變體：VPC-SU、VPC-MU、VPC-SD以及VPC-MD。我們證明了VPC-SD(以及VPC-MD)是NP-complete問題,并為VPC-MU(以及VPC-SU)問題設(shè)計了多項式時間算法。該算法可用于測試系統(tǒng)是否正確實現(xiàn)了Pipelined-RAM一致性模型,而上述NP-completeness結(jié)果則有助于我們進(jìn)一步理解弱一致性模型的復(fù)雜度。3.提出了針對讀寫寄存器的“近乎強(qiáng)”一致性(almost strong consistency)概念,并以此作為一致性／延遲權(quán)衡(consistency/latency tradeoff)的一種可行選項�！敖鯊�(qiáng)”一致性要求在保證(讀操作)低延遲的前提下,既提供基于版本的、陳舊度確定性有界的讀操作,又要從概率的角度量化讀操作“讀取到陳舊值”的速率。我們深入研究了“近乎強(qiáng)”一致性概念的一個具體實例—probabilistically-atomic 2-atomicity (PA2AM)一致性：提出定義、設(shè)計并證明算法正確性以及量化算法中讀操作違反atomicity一致性的速率。與弱一致性模型的對比顯示,PA2AM(及其PA2AM維護(hù)算法)既(在統(tǒng)計意義上)滿足強(qiáng)一致性模型對數(shù)據(jù)一致性的高標(biāo)準(zhǔn),又具有弱一致性模型的性能優(yōu)勢。4.針對事務(wù)數(shù)據(jù)類型,基于Snapshot Isolation (SI)提出了一種新的事務(wù)一致性模型：Relaxed Version Snapshot Isolation (RVSI)。RVSI可以形式化地、定量地規(guī)約它相對于SI所產(chǎn)生的異常的嚴(yán)重程度。為此,我們將SI分解為三個相對獨(dú)立的“視圖”性質(zhì),然后通過為每個“視圖”性質(zhì)引入一個量化參數(shù)(得到k1-BV、k2-FV及k3-SV),來定量規(guī)約RVSI相對于SI的三類異常。這種定義方式使得我們實現(xiàn)的滿足RVSI一致性模型的分布式事務(wù)鍵值存儲原型系統(tǒng)可以支持應(yīng)用程序的每個事務(wù)在運(yùn)行時動態(tài)選擇或調(diào)節(jié)其所需的一致性條件。更進(jìn)一步,RVSI為深入研究SI提供了一種有效途徑。初步實驗表明,適當(dāng)放松事務(wù)對RVSI版本規(guī)約—包括k1-BV、 k2-FV鎈及k：3-SV—的要求能降低事務(wù)中止率,而RVSI能否“顯著”降低事務(wù)中止率則與負(fù)載類型相關(guān)。
[Abstract]:......
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP333

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張曉梅;;文獻(xiàn)數(shù)據(jù)庫生產(chǎn)中的數(shù)據(jù)一致性問題分析[J];中華醫(yī)學(xué)圖書情報雜志;2010年02期

2 黃淑冬;;客戶數(shù)據(jù)一致性管理系統(tǒng)的研究與應(yīng)用[J];計算機(jī)光盤軟件與應(yīng)用;2013年21期

3 呂艷娥;周力青;;基于策略協(xié)商的數(shù)據(jù)一致性的維護(hù)方法[J];大眾科技;2009年02期

4 帖軍;王小榮;金佳;;移動實時環(huán)境下的數(shù)據(jù)一致性研究[J];中南民族大學(xué)學(xué)報(自然科學(xué)版);2011年02期

5 杜毅迪;數(shù)據(jù)一致性模型的設(shè)計與實現(xiàn)[J];湖北郵電技術(shù);2001年04期

6 宋長宏,劉宇棟,朱R，

本文編號：2477277