随着云计算范式的发展,云存储的重要性和价值得到了人们的广泛认可。作为分布式系统、数据库发展衍生的产物,云存储系统沿用来自这些领域并且已经得到了深入研究和广泛应用的复制技术,将其作为提供高可用性水平、实现快速访问并确保容错的必要手段。随着支撑技术的快速演进和应用需求的持续提高,云存储系统已经从单数据中心架构进化到跨不同地理位置分布的多数据中心架构。在如此大规模的系统环境下,复制技术面临着许多新的挑战,亟待进一步的完善与提高。保证副本间的数据一致性是复制中的一个至关重要的问题。一方面,一致性水平越强,执行它的成本越高,而可扩展性越低;另一方面,弱一致性更为廉价,但却以潜在的一致性违背为代价。在现实中,应用和数据在一致性需求上的多样性和多变性并非某种单一的一致性模型所能应对的。在此背景下,复制蕴含了一致性与各种因素如性能、成本等之间的权衡。从理论研究与实践应用的意义上,在保持强一致性水平的情况下尽可能提高性能以及综合考虑一致性与其他因素之间的权衡是具有重要意义且极具挑战性的课题。本文从复制状态机及强一致性协议的设计方法出发,研究能够在大规模云环境下提供高吞吐量的强一致性协议的实现,继而建立相应的性能定量分析模型,最后探索其在一致性权衡方面的延伸。本文的主要研究内容和创新点归纳如下:1.当前针对不同资源约束或优化目标进行的复制状态机及强一致性协议设计通常都采用传统而冗长的文字表述方式,即使它们中的许多设计结果最终都表现出了类似的特征。在深入调研多个典型设计的基础上,本文提取了各种复制状态机的共同特征,通过功能抽象和属性定义,提出了复制状态机的模块化抽象框架。框架实现了对状态机的准确解析,在一定程度上解耦了各个功能模块的设计。通过提供不同的模块实现,框架可用于简单而有效地重构现有或新的复制状态机。此外,框架中的架构协议也规范并简化了强一致性协议的设计。该模块化抽象框架是对传统表述方式的一种有效的补充,对不同环境/资源约束或优化目标下复制状态机及一致性协议的高效设计具有实际的指导意义。2.当在云端跨多数据中心副本复制的场景下实现强一致性时,现有以唯一leader为中心的协议——如著名的Paxos协议——将面临两个主要问题:高延迟的广域消息传输和不均衡的链路依赖。基于实例并发执行的思想,本文定义了一个被称为分层复制状态机的复制状态机并相应地设计了一个实现该状态机并提供高吞吐量的强一致性协议D-Paxos。分层复制状态机和D-Paxos通过批处理和逻辑流水线处理实现了对空闲资源的充分利用,在大规模云环境下提供高性能同时不牺牲其强一致性。本文从理论上证明了D-Paxos满足分层复制状态机的安全性和活性属性从而可以被用于实现一个分层复制状态机。此外,本文还基于模块化抽象框架进行分层复制状态机及D-Paxos的实例化,这从侧面反映了模块化抽象框架的实用性。3.通常,针对一致性协议的性能评估主要是通过实验来完成的,本文最初关于D-Paxos的吞吐量、可扩展性和容错能力的评估也是如此。实验评估固然重要,不过,如果可以结合某种定量的分析方法,显然将对协议性能的更深入分析与理解大有裨益。为了更深入地理解批处理和逻辑流水线处理这两种优化方式对D-Paxos性能的影响,本文从理论角度建立了关于D-Paxos预排序请求批次尺寸的定量分析模型。分析模型为最优预排序请求批次尺寸提供了一个很好的近似,这一点在实验中得到了验证。结合模型的分析,协议性能与相关属性如延迟、请求尺寸、批次尺寸、副本数量等之间的关系得到了更深入的研究,而D-Paxos在批处理和逻辑流水线处理下的可扩展性也得到了进一步的探讨。4.随着数据在世界范围内被复制,固有的一致性权衡问题由于数据中心间的高通信延迟而变得更为突出。不同于只考虑一致性/成本权衡或只考虑一致性/性能权衡的解决方案,本文针对基于地域复制的云存储提出了一种综合考虑成本和响应时间约束的一致性权衡方案。为此,本文在中间件层面上提出了一个分组复制框架及与之对应的权衡策略,其能够在考虑成本、响应时间约束的情况下实现一致性水平的运行时自适应切换。分组复制框架采用主/辅分组方式和主动/被动复制相结合的方式来提供强一致性保证和较弱的一致性保证。成本策略和性能策略中采用的概率方法通过使用收集的历史数据来确定后续请求的一致性水平及访问的目标副本,从而实现一致性与成本、响应时间之间的权衡。