● 摘要
随着互联网、云计算、移动计算和大数据等技术的快速发展，面向海量终端用户的互联网软件服务不断涌现,在线服务已经逐渐成为软件的重要形态和发展趋势。由于互联网具有全球性和开放性的特点，软件服务需要支撑大量用户的并发请求，并提供7x24持续不断的服务。相关统计发现，终端用户对软件服务的响应延迟极其敏感，延迟的上升甚至会影响到服务提供商的整体收益；同时，可用性几乎成为了大型软件服务的服务等级约定中必须声明的属性之一，可用性的高低也会影响用户使用该软件服务的信心。由此可知，高可扩容性和高可用性已经成为互联网软件服务的关键需求。
目前，为提升软件服务的可扩容性和可用性，副本技术在大规模分布式数据中心中广泛使用。通过副本技术，互联网软件服务可以有效和快速的进行扩容，在不同副本之间进行负载均衡，并使用服务副本进行失效备份。然而，负载均衡和失效备份的前提都是：副本间状态是一致的。根据CAP和PACELC等理论的描述，副本协议一致性和性能、一致性和可用性之间存在着相互权衡的关系。这为副本协议的相关研究带来了挑战。
为了解决一致性和性能、一致性和可用性之间相互权衡的问题，弱一致性的副本协议被提出，并被许多商业和开源系统接受和使用。但是，弱一致性会给软件服务带来潜在的系统风险，比如，读请求读到的数据可能是陈旧的，不同副本同一数据项的数值可能不一致等。所以，在选择和配置副本协议时，预先了解相应副本协议一致性、性能和可用性的程度很有必要。国内外研究人员在副本协议的弱一致性模型、一致性和性能的权衡、一致性和可用性的权衡以及强一致性副本协议优化等方面开展了大量工作，但还存在不足。
首先，已有工作虽然提出了许多具有特定弱一致性的副本协议，但一般仅适用于有限的应用场景，且对一致性主要得到定性结论；其次，一致性和性能的权衡方面，一致性的量化主要集中于副本协议正常工作、没有失效发生时的情形，且只涉及对读请求陈旧度的衡量，很少涉及写请求带来的不一致性，也缺少对副本协议性能的量化工作；再次，一致性和可用性的权衡方面，可用性的量化工作主要基于简单的网络开展，比如，全连接网络，并未考虑真实数据中心网络的复杂性；最后，强一致性副本协议的性能优化还未出现针对软件服务特征的优化方法。
针对上述问题，本文从量化分析和优化管理的角度出发，以提升互联网软件服务的可扩容性和可用性为目标，围绕副本协议进行研究，在副本协议一致性和性能的量化分析和权衡、一致性和可用性的量化分析和权衡以及强一致性副本协议优化等方面展开研究工作，主要贡献如下：
1. 提出了副本协议的量化分析模型和优化框架。通过对常见副本协议进行归纳分 析，基于已有的副本协议模型，得出副本协议的量化分析模型，该模型针对常见的数据中心网络、副本放置以及副本状态机和Quorum系统等两种副本协议模型，提出副本协议模型的量化分析和优化框架，分别讨论弱一致性可容忍条件下一致性、延迟、可用性的量化分析思路和它们之间的量化权衡方法，以及强一致性条件下的副本协议优化方法。
2. 提出了副本状态机模型一致性和延迟的量化分析和优化权衡方法。通过对副本状态机模型的分析，提出了副本状态机通用模型RSM-d，该模型可以描述典型的副本状态机实现方法以及变体。在该模型基础上，构建了写冲突和延迟的量化概率模型，分别用于度量副本协议的一致性和延迟。基于一致性和延迟的量化结果，从服务提供商角度提出了面向最大化系统效益的一致性和延迟量化权衡方法，并分析了在不同一致性补偿函数和副本数为3时如何具体使用该权衡方法。通过基于真实数据的蒙特卡诺仿真实验，验证了一致性和延迟量化模型的准确度，以及对两者进行最优化权衡方法的有效性。
3. 提出了Quorum系统模型一致性和可用性的量化分析和优化权衡方法。基于Quorum系统模型QS(DCN,PM,W/R)，分别量化了四种典型数据中心网络中Quorum系统的可用性，包括2层基本树、3层基本树、K胖树、folded clos网络，并进一步把量化结果扩展到了跨地域的多数据中心网络。分析了副本放置对可用性的影响，并且在2层基本树和副本数为常用值3的情况下给出了直观的分析结论。基于可用性的量化结果，通过构建可用性-一致性表格，给出了一组规则用于选择最优的(W,R)配置对可用性和一致性进行量化权衡。最后，基于真实数据的蒙特卡诺仿真实验，对可用性量化结果的准确度进行了验证，并且证实了一致性和可用性量化权衡方法是有效的。
4. 设计了强一致性保持的高性能Paxos副本协议。基于强一致性的Paxos协议，通过利用请求间的可交换性动态构建请求依赖图RDG，使得某些请求可以在保证一致性的前提下提前执行，从而进一步提升了副本协议性能。量化分析了请求依赖图带来的性能提升幅度，并严格证明了优化后副本协议的强一致性。设计了主副本节点和从副本节点失效情况下的恢复算法以保障服务可用性。最后通过真实实验说明，与已有副本协议相比，经过优化后的强一致性副本协议具有良好的性能和可用性。