PacificA基于日志的分布式存储系统中复制
这是elasticsearch的日志复制算法。
Lin, W., Yang, M., Zhang, L., & Zhou, L. (2008). PacificA: Replication in log-based distributed storage systems.
概要
大规模分布式存储系统因其存储和处理日益增长的数据量而越来越受欢迎。复制机制通常是这样系统中达到高可用和高吞吐量的关键。共识算法的研究为复制协议奠定了坚实的基础。然而架构设计和实际复制机制的工程问题仍然是一门艺术。
这篇论文描述了我们的实现通用的基于日志存储系统的副本复制实现。我们提出了一个通用的复制框架，它简单，使用并且强一致。使用一个协议系统叫做PacificA，我们实现三个不同的副本复制策略，都使用了相同的复制框架。这篇论文报告描述了性能评估结果，特别是在故障，下的行为和恢复。
介绍
随着大规模存储系统需求的增长来持有日益增加的数字信息。为了有效的成本，为了有效的成本，这写系统通常构建在通用的组成上。因此故障变得常见，故障恢复技术，例如复制变成了实现可靠和高可用系统的关键。
众所周知，可证明的正确复制协议是存在的。然而，构建实际的分布式存储系统不仅仅是应用一个已知的复制协议。在理论的复制协议和实际的复制机制之间存在显著的差距。
例如复制协议的理论设计通常以过于简化的性能指标为指导，比如消息轮数，然而实际的复制机制旨在优化端到端客机感知的性能指标，如系统吞吐量，请求处理延迟，还有故障恢复时间。理论设计聚焦于复制协议的单个实例，然而现实的复制机制必须优化多个实例共存的性能。
在这篇论文中，我们描述了我们设计，实现和评估复制机制在大规模基于日志的存储系统在局域网中的经验。这样的基于日志的设计通常被用在存储系统来提高性能，通过把随机写变为顺序写和批处理，以及支持事务语义。许多最近提出的基于lan的存储系统（petal，grangipani，boxwood和bigtable）都是用日志。
基于日志的存储系统踢狗了丰富的结构，提供了有趣的设计选择。可以在不同的语义级别和不同类型的目标上进行复制（即，本地状态，日志，或者在磁盘上的物理数据）。
我们选择了设计和实现简单，现实和可证明正确性的通用复制框架而不是实现不同的复制机制来考察设计选择。不同的选择转化为相同复制框架的不同实例。相比于不同的模式，这明显减少了实现，debug，管理系统和故障恢复的开销。
复制框架的设计反应了我们相信可证明正确的复制协议在现实的复制机制中重要的。一个定义清晰的系统模型能够阐明协议运行所基于的假设，使我们能够理解和评估潜在风险。自定义的复制协议经常在未知的情况下失败。
选择合适的复制协议，以及选择正确的体系结构设计，是获得良好的实用复制机制的关键。我们相信，简单和模块化是构建实用系统的关键要素。我们的复制框架拥抱这些原则通过以下的特性：
- 复制组配置管理与数据分割，通过paxos来管理配置和主备。
- 去中心化的监控来探测故障并且触发重配置，以及遵循数据复制通信模式的监控流量。
- 一个通用并且抽象的模型，它澄清准确性并且允许不同的现实实例。
在基于日志的分布式系统上下文中，复制框架也能让我们探索新的复制模式，不同于之间的boxwood和bigtable系统。特别是，我们的方案在简单性（不依赖于单独的锁服务）和由于更好的数据协同定位而减少的网络流量方面提供了吸引人的优势。
为了评估提出的复制模式，我们实现了pacificA，一个分布式日志系统的原型，用于存储结构化和半结构化的web数据。我们进行了广泛的评估来来了解各种复制方案的性能和成本，对于单个复制实例和具有多个实例的整个系统都是如此。系统在故障和恢复过程中的行为在实践中非常重要。我们提供了这些情况下系统行为的详细分析。
PacificA 复制框架
在这篇论文中，我们聚焦于基于局域网环境的集群，其中系统通常由大量的机器组成。一个服务有一个或多个CPU，本地内存一个或多个的本地存储。所有的服务被连接到告诉的欲望。我们假设单一收管理的区域，其中所有设备都是可信的。不需要考虑安全机制。
服务可能故障。我们假设故障时服务停止工作。我们不假设服务之间的消息延迟有界，虽然他们在正常情况下很小。消息可能被丢弃或者重排序，但不会被注入或者丢弃。网络分区也是有可能发生的。服务器上的始终不一定是同步的或者即时是松同步的，但假设时钟的偏移是有界的。
系统维护数据集合。每一篇的数据被复制到一组服务中，称为复制组。每个服务在复制组服务中是一个副本。一个服务可以作为多个组的副本。数据复制协议服从主备模式。一个副本在复制组中被设计为primary（接下来翻译为主），其他被叫做secondaries（从）。副本组的构成，即指明谁是主节点、谁是从节点的信息，被称为副本组的配置。副本组的配置由于副本失败或添加而更改。版本被用来跟踪这些修改。
我们关注与复制协议，它实现强一致性，因为它代表了最自然一致性的模型。自然的，强一致性确保复制系统的行为与非复制系统系统，从而实现线性化语义。处理弱一致性的语义模型通常增加了复杂性。
2.1 主备数据复制
我们适配了主备模式进行数据复制。我们区分了俩种客户端请求：不修改数据的查询，和修改数据的更新操作。在主备模式下，所有的请求都被发送到主节点。主在本地执行所有的查询请求，并且在更新时涉及所有从服务器。主备模式吸引人是因为几个原因。它很简单，于主节点作为唯一访问点的复制案例非常相似。查询它是许多工作负载中的主导，在单个服务器上直接处理。
如果副本组中所有的服务器以相同的顺序处理同一组请求在更新是确定的情况向下，则可实现强一致性。主节点会为更新操作分配连续且单调递增的序列号，并且指示从及诶单按此顺序持续处理请求。为了清楚期间，我们将副本建模为维护一个准备好的请求列表和该列表已提交点。该列表是根据分配给请求的序列号排序的，并且是连续的（序列号为sn的复制请求只会在sn-1后才被插入）。准备列表倒提交点的前缀称为提交列表。
主的应用状态是按初始状态上序号的递增顺序应用提交列表中所有请求顺序的结果。在提交列表中的请求不会丢失，只要系统没有经历不可容忍的故障（当前配置中所有副本永久性故障）。准备列表中未提交的内容用于确保在重新配置期间保留提交列表的请求。我们使用$\text{committed}_p$来表示服务p上提交列表，$\text{prepared}_p$表示p的准备列表。
正常的查询和更新 在正常情况下（没有重配置），数据复制协议是直接的。当一个主接受到一个请求，它执行查询，并立即返回响应。
对于更新来说，主p分配下一个可用的需要给请求。然后发送请求伴随着配置的版本和序列的数字到准备好的消息中给所有副本。一旦接收到一个准备消息，副本r按照序号的顺序插入请求到它的prepared列表中，请求被认为在副本上准备好的。r然后发送ack到准备好的主。当接收到所有副本的ack时主提交请求。在此时，主移动它的提交点到更高的点，因此所有到这个点的请求都被提交。p之后发送ack到客户端表示成功完成。对于每个消息，主服务器进一步在提交点装载序列号，以通知复制服务器已提交的所有请求。从节点然后可以移动提交点到对应的地方。
因为主添加了请求到提交列表（当向前移动提交点时），只有在所有服务都插入了它们的准备列表时，主上的提交列表才会添加请求，主上的提交列表始终是任何副本上准备列表的前缀。同样，因为从添加请求到它的提交列表当且晋档主也完成了，从上的提交列表一定是主提交列表的前缀。因此这个简单的数据复制协议支持以下提交不变性。
提交不变性：设 $p$ 为主副本，$q$ 为当前配置中的任意副本，则恒有 $\text{committed}_q \subseteq \text{committed}_p \subseteq \text{prepared}_q$ 成立
这个基础的主备协议只在复制组没有改变配置时工作。我们的复制框架将配置管理与数据管理分开。在下一个小章节中我们描述配置管理和他与数据复制的交互。
2.2 配置管理
在我们的设计中，全局配置管理器维护了所有系统中复制组的配置。对于每个复制组，配置管理者维护当前的配置和他们的版本。
当服务怀疑（通过故障探测）它的副本故障时，服务开始重配置；重配置将会从故障副本从配置中移除。服务也可以向配置中添加新的副本。例如恢复所需的冗余水平。在俩种情况下，服务器都会将新配置与当前的版本一起发送给配置管理器。当且晋档版本与配置管理上当前配置匹配时，请求才会被执行。在这个例子中，被提出的新配置随着更高的版本号被安装。否则请求将会被拒绝。
当网络分区导致主副本和从不能通信，可能会出现冲突的重配置请求：主可能想要扇出一些从，这些从可能尝试删除主节点。因为这些请求都基于当前的配置，所以配置管理器接受到的第一个请求获胜。所有的其他的冲突请求被拒绝，因为配置管理机已经升级到具有更高版本的新配置。
任何确保主不变的故障检测机制都可以用来触发当前副本的删除。在2.3我们描述了实现这样故障探测的机制。
主不变性：在任何时间，一个服务p认为他自己是主只有当配置管理器在当前配置中将p作为主。因此，任何时间，在任何时候，最多只有一个服务器认为自己是副本组的主服务器。
2.3 租约和故障探测
即使配置管理器维护当前配置的真实性，主不变式也不一定成立。这是因为不同服务的本地配置视图并不一定是同步的。实际上，我们必须避免老的主和新的主同事处理查询请求。旧的主服务器可能不知道重新配置已经创建了一个新的主服务器，并已将其从配置中删除。因为新的主服务器可能已经处理了更新，所以旧的主服务器可能正在处理过时状态的查询，从而违反了强一致性。
我们的解决方案是使用租约。主服务器通过定期向每个从服务器发送信息并等待确认，每个从服务器获取租约。如果上次确认的租约周期已经过去，主服务器认为它的租约已经过期。当任意的从节点到期，主节点不再认为自己是主服务器。在这种情况下，主服务器将联系配置管理器从当前配置中删除从服务器。
只要发送方在当前配置中保持为主，从服务器就会确认信息。如果子从服务器收到主节点信息以来已经过了grace period（宽限期），则从服务认为主服务的租约已经过期，并将联系配置管理器以删除当前的主服务器并成为新的主服务器。
假设没有时钟偏移，只要宽限期大于等于租约即可。当且晋档七对旧主服务器的租约到期时，从服务器提出配重更新以尝试承担主服务器的职责。因此它保证了在新主建立之前老的主服务器已注销；因此主不变性能够保证。
我们使用租约机制作为故障探测机制，类似的故障探测机制被用在FGS，boxwood，比高铁和Chubby中。一个关键的不同是这些系统的租约被中心化的实例持有。在我们的例子中，故障探测的监控流量总之在俩个本就需要数据沟通的服务之间的：主和从进行修改更新时需要交流；信标和确认消息同样在主节点与从节点之间传递。这样一来，故障检测机制就能准确捕捉到数据复制所需的通信通道状态。实际的信标和确认仅在通信通道空闲时发送，从而最大限度地减少故障检测的开销。此外，这种分散的实现消除了对集中式实体的负载和依赖。负载可能很大，因为信标和确认是在中心化实体和系统中的每个服务器之间定期交换的；间隔必须很小，以便快速检测故障。在集中式解决方案中，集中式实体的不可用（例如，由于网络分区）可能导致整个系统不可用，因为当失去中央实体的租约时，所有主节点都必须退出。
2.4 重配置，协调与恢复
副本复制协议的复杂性依赖于如何处理重配置。我们将重配置分为三种类型，移除从节点，移除主节点和天极爱从节点。
移除从节点一个或多个从节点的移除是直观的，当主节点怀疑从节点的子集故障了。主节点提出一个新的配置，排除那些可疑的从节点，并且配置管理器批准该建议后不适用这些辅助服务器。
修改主。当从节点怀疑主节点没能用之前提到的租约时，主节点会被移除。从节点提出一个新的配置，让自己成为主节点，旧的主节点将会被排除。当接受后，从p认为自己自己是新主并且在reconciliation后开始处理。在reconciliation时，p将其列表中未提交的请求发送准备消息，并将其提交到新配置上。设sn为调和后的p的提交点对应的序号，则p只是所有副本阶段其准备好的提交列表，并切保留序列号为sn的所有请求。如果任何新的配置的副本故障，另一个重配置可以在协调时触发。
因为从服务器上的准备列表总是包含所有已提交的请求，通过提交准备列表中的所有请求，协调确保重配置不变性。
重配置不变性： 如果一个新的主p在时间t完成了重协调，任何在副本组中在任何t之前时间的若新主副本 p在时间 t完成协调（reconciliation），则保证副本组中任意副本在 t之前维护的任意已提交列表，都一定是 t时刻主副本 p的已提交列表的一个前缀。
重配置不变性扩展了提交不变性到配置。它还确保分配给任何提交请求的序列号将被保留，即使发生主要更改也不会重新分配。相反，准备列表中未提交部分中的请求不一定要保留。
例如当主将序列号分配失败时，新主可以分配一个相同的序列号给不同的请求，只要序列号没有在提交请求中出现。从节点总是选择来自具有最高配置版本的主要服务器的分配。
图1 重协调。A是老配置的主节点。在旧配置中， 旧的从B被提升为新的主，并从配置中移除A。第一行显式了基于列表中最高序号的已准备列表和提交副本列表的状态。第二根线展示了在重协调后的对应状态。
图1展示了主节点变更时，各副本的预备列表和提交点（committed points）的变化过程。初始状态下，A为主节点，B、C、D为次级副本。需注意，此时B的已提交列表（committedₑ）是A的已提交列表（committedₐ）的前缀，而A的已提交列表又是任意副本上预备列表的前缀。假设一次重新配置中，B取代故障的A成为新主节点。在B完成协调（reconciliation）后，新的B的已提交列表（committedₑ）与旧的B的预备列表（preparedₑ）相同，且该列表包含（subsumes） 了原A的已提交列表（committedₐ）。同时，C的预备列表被更新以满足提交不变性（Commit Invariant），而D的预备列表中多余的请求则被移除（或撤销）。
增加新从 新的副本可以被添加到复制组来重建在组故障之后的冗余级别。提交不变性在新的服务被添加到配置中时必须要保持。这需要新的副本在加入复制组时有合适的准备列表。新副本获得正确状态的过程称为恢复。
一个简单的方法是让主服务延迟执行任何更新，直到新的副本被复制到所有存在的副本。这种实现往往是由破坏性的。或者，一个新的副本作为候选者从节点。主服务器继续处理更新，并想候选从服务器发送准备消息。如果主服务器无法从新的副本获得确认，那么主服务器将终止该副本的候选资格。除了在主服务器的准备消息中记录现有更新外，候选从服务器c还将从任何现有副本获取它尚未拥有的准备列表部分。当c最终追赶上来的时候，它要求主吧c加入到配置中。只要c的后选人资格尚未终止，主将会联系配置管理者添加c到配置中作为一个从。一旦通过，主将c作为一个从。
在恢复期间将状态转移到新的副本可能代价高昂。对于从未在副本组中存在过的副本，完全状态转移是不可避免的。在某些情况下，由于错误猜疑、网络分区或其他临时故障，副本从复制组中删除。当这样一个过时的副本重新加入组时，理想的做法是让新副本执行追赶恢复，它只获取在副本离开组时已经处理的缺失更新。由于Reconfiguration Invariant，旧副本的提交列表是保证的。
后面的懒得翻译了。看原文去吧
2.5是正确性证明。2.6是优化方案，2.7是讨论