CRII: CSR: Efficient and Available Replication in Large-scale Datacenters

复制在IT行业中被广泛用于保护用户的数据免受各种错误的影响，例如断电、磁盘损坏和网络分区。通常情况下，我们需要为能够容忍更多类型错误的更强的复制协议支付更高的成本。这对开发人员来说是一个具有挑战性的权衡，他们有时会选择使用较弱的复制形式，愿意冒偶尔数据丢失的风险以换取低成本。本项目介绍了如何降低Paxos（当今数据中心中流行的强大复制协议）的成本，同时保留其其他属性。虽然这个主题已经在学术界引起了持续的努力，但现有的方法通常会放弃Paxos的某些有用属性，例如可用性，这给开发人员提出了一个不同但同样困难的问题。这项工作提出了一种复制协议ThriftyPaxos，它可以以更低的成本实现与Paxos相同的属性。为了降低成本，ThriftyPaxos结合了按需实例化的思想，当没有故障时激活最小数量的副本，当活动副本失败时激活备份副本。为了解决按需实例化的关键限制，即当备份重建其状态时系统不可用，ThriftyPaxos结合了延迟恢复的思想，这允许系统在后台恢复备份副本时继续进行。这种设计的动机是观察到，当Paxos的两个关键组件受体和学习者解耦时，可以设计单独的机制来延迟它们的恢复，而不会阻塞系统。更便宜的Paxos协议将吸引现有的Paxos用户和那些仍在使用较弱协议的用户，因为他们将不会在数据一致性和成本之间做出同样的艰难选择。为了实现这种影响，PI将把ThriftyPaxos应用于流行的开源软件，并公布ThriftyPaxos的源代码。这个项目对教育也有影响。该代码将被转换为课程项目使用，以便研究生和本科生可以在课程项目中建立一个类似的系统。

Replication is widely used in the IT industry to protect users' data against various kinds of errors, such as power loss, disk corruption, and network partition. It is generally the case that we need to pay a higher cost for stronger replication protocols that can tolerate more kinds of errors. This presents a challenging trade-off to developers who will sometimes choose to use weaker forms of replication, willing to take the risk of occasional data loss in exchange for low cost. This project presents how to reduce the cost of Paxos, a popular strong replication protocol in today's data centers, while preserving its other properties.While this topic has already drawn a continuous effort in academia, existing approaches usually give up certain useful properties of Paxos, such as availability, presenting a different but equally hard question to the developers. This work presents ThriftyPaxos, a replication protocol that can achieve the same properties as Paxos with lower cost. To reduce cost, ThriftyPaxos incorporates the idea of on-demand instantiation, which activates the minimal number of replicas when there are no failures, and activates backup replicas when the active ones fail. To solve the key limitation of on-demand instantiation, that the system is unavailable when the backup is rebuilding its state, ThriftyPaxos incorporates the idea of delayed recovery, which allows the system to proceed while recovering a backup replica in the background. Such design is motivated by the observation that when acceptors and learners, the two key components of Paxos, are decoupled, it is possible to design separate mechanisms to delay their recovery without blocking the system.A cheaper Paxos protocol will be appealing to both existing Paxos users and to those who are still using weaker protocols, because they will not have the same type of difficult choice between data consistency and cost. To realize such impact, the PI will apply ThriftyPaxos to popular open-source software, as well as publishing the source code of ThriftyPaxos. This project has impact to education as well. The code will be converted for use in a course project so that graduate and undergraduate students can build a similar system with reasonable effort in a course project.