分布数据一致性技术研究

发布时间：2019-05-15 03:28

【摘要】：进入21世纪以来,大规模分布式系统和云计算日益流行。为满足新平台和新计算模式对系统的性能、可用性、容错性、可扩展性等指标的需求,底层的数据存储系统通常采用分布数据技术—这包括数据分区技术和数据复制技术。然而,与此同时,分布数据带来了数据一致性问题：对于上层应用而言,如何理解处于分布形态的数据?什么叫作数据是一致的?又该如何像使用(集中式)共享数据一样方便且正确地使用分布数据?从技术角度来说,上层应用以何种顺序观察到作用在底层分布数据上的并发更新?又如何基于分布数据所提供的更新顺序性质编写程序并论证其正确性?作为管理分布数据的中间件,分布共享数据服务在分布数据之上向上层应用提供符合某种规约的共享数据抽象。由于以数据一致性为核心,有一系列的固有权衡,不存在普适的、完美的一致性解决方案,数据一致性问题因此成为分布共享数据服务中一项具有挑战性的研究课题。从历史角度来看,数据一致性问题并非为分布式系统和云计算领域所独有,对它的研究可追溯到多处理器系统和并行计算的发端时期。但是,传统的“以程序为导向、强调正确性”的数据一致性理论并不能很好地体现新平台和新计算模式下日益凸显的应用价值观。一方面,不同应用甚至同一应用中的不同实体,对数据一致性有着不同需求。一致性理论需要融合不同强弱程度的数据一致性,甚至融合一致的数据状态与不一致的数据状态；另一方面,应用关于数据是否一致的“正确性”标准变得模糊。一致性理论需要从连续谱的角度—而非“一致”与“不一致”的二元视角—看待数据一致性,以满足应用对数据一致性的更精细的量化需求。为体现新平台和新计算模式下日益凸显的应用价值观,本文提出“以应用为导向的”、“多样化,可调节；精细化,可度量”的数据一致性问题研究理念。“多样化,可调节”指的是,数据一致性理论应该支持来自应用的、更为多样的一致性需求,并允许应用在运行时动态选择或调节其一致性需求；“精细化,可度量”指的是,数据一致性理论应该支持来自应用的、更为精细的一致性需求,并能向应用提供有关一致性服务质量的量化信息。落实“多样化,可调节；精细化,可度量”的研究理念,需要解决来自一致性模型、一致性实现机制以及一致性度量三个维度的挑战。这包括,如何形式化定义“多样化”的一致性模型、如何在尽可能通用的系统架构下实现应用动态调节一致性的功能、如何形式化定义“精细化／量化”的一致性模型以及如何设计高效的一致性模型验证算法或者建立合适的数学模型以量化一致性程度。本文即专注于应对这些挑战,以更好地落实“多样化,可调节；精细化,可度量”的研究理念。本文的主要工作如下：1.在充分分析了数据一致性问题研究的历史阶段和发展趋势的基础上,为体现大规模分布式系统和云计算模式下日益凸显的应用价值观,提出了“以应用为导向的”、“多样化,可调节；精细化,可度量”的一致性问题研究理念,并总结出涵盖“一个基础,三个维度”的研究思路：以数据类型(包括读写寄存器与事务)为基础,以一致性模型、一致性实现机制和一致性度量为维度。其中,研究理念“多样化,可调节”体现在一致性模型和一致性实现机制两个维度上,而“精细化,可度量”体现在一致性模型和一致性度量两个维度上。2.提出并解决了针对读写寄存器的Pipelined-RAM一致性模型验证问题(theproblem of Verifying Pipelined-RAM Consistency;简称VPC)。具体而言,根据(1)读写操作记录是否涉及多寄存器(Single or Multiple)以及(2)写操作是否允许写入重复值(Unique or Duplicate),我们考察VPC问题的四种变体：VPC-SU、VPC-MU、VPC-SD以及VPC-MD。我们证明了VPC-SD(以及VPC-MD)是NP-complete问题,并为VPC-MU(以及VPC-SU)问题设计了多项式时间算法。该算法可用于测试系统是否正确实现了Pipelined-RAM一致性模型,而上述NP-completeness结果则有助于我们进一步理解弱一致性模型的复杂度。3.提出了针对读写寄存器的“近乎强”一致性(almost strong consistency)概念,并以此作为一致性／延迟权衡(consistency/latency tradeoff)的一种可行选项。“近乎强”一致性要求在保证(读操作)低延迟的前提下,既提供基于版本的、陈旧度确定性有界的读操作,又要从概率的角度量化读操作“读取到陈旧值”的速率。我们深入研究了“近乎强”一致性概念的一个具体实例—probabilistically-atomic 2-atomicity (PA2AM)一致性：提出定义、设计并证明算法正确性以及量化算法中读操作违反atomicity一致性的速率。与弱一致性模型的对比显示,PA2AM(及其PA2AM维护算法)既(在统计意义上)满足强一致性模型对数据一致性的高标准,又具有弱一致性模型的性能优势。4.针对事务数据类型,基于Snapshot Isolation (SI)提出了一种新的事务一致性模型：Relaxed Version Snapshot Isolation (RVSI)。RVSI可以形式化地、定量地规约它相对于SI所产生的异常的严重程度。为此,我们将SI分解为三个相对独立的“视图”性质,然后通过为每个“视图”性质引入一个量化参数(得到k1-BV、k2-FV及k3-SV),来定量规约RVSI相对于SI的三类异常。这种定义方式使得我们实现的满足RVSI一致性模型的分布式事务键值存储原型系统可以支持应用程序的每个事务在运行时动态选择或调节其所需的一致性条件。更进一步,RVSI为深入研究SI提供了一种有效途径。初步实验表明,适当放松事务对RVSI版本规约—包括k1-BV、 k2-FV鎈及k：3-SV—的要求能降低事务中止率,而RVSI能否“显著”降低事务中止率则与负载类型相关。
[Abstract]:......
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP333

【相似文献】