构建Paxos：Google的工程实践
5星 · 超过95%的资源 需积分: 17 54 浏览量
更新于2024-07-29
1
收藏 240KB PDF 举报 "Paxos Made Live - An Engineering Perspective"
Paxos Made Live 是一篇由 Tushar Chandra、Robert Griesemer 和 Joshua Redstone 于2007年6月26日发表的技术论文，主要讨论了在Google实现Paxos共识算法的实际工程经验。Paxos 是一种分布式计算中的共识算法，旨在确保在一个存在网络延迟、故障或通信异常的环境中，多个节点能够就一系列值达成一致。尽管Paxos在理论上有丰富的研究，但将其应用于实际系统中仍面临许多挑战。
1. Paxos 算法简介
Paxos 算法的核心是解决分布式系统中的一致性问题，尤其是在节点之间存在不稳定网络连接时。它允许一组节点（称为“接受者”）在大多数节点存活且正常通信的情况下，就一个提案（提议的值）达成一致。Paxos 包含三个主要角色：提议者（Proposer）、接受者（Acceptor）和学习者（Learner）。提议者提出值，接受者接收并投票，最后学习者根据多数票结果学习并应用值。
2. 实际工程问题与解决方案
在构建基于Paxos的容错数据库时，作者遇到了几个关键问题：
- **提案编号**：如何确保提议者之间的冲突得以解决？他们采用了唯一的提案编号，以确保每次只有一个提议被接受。
- **活锁与饥饿**：如何防止系统陷入无休止的提议循环？通过设计智能的提议重试策略来避免活锁，并确保每个提议最终都能得到处理。
- **故障恢复**：如何处理节点故障？他们引入了检查点和持久化状态的机制，以便在故障后能恢复到一致的状态。
- **性能优化**：如何提高系统的吞吐量和响应时间？通过优化通信协议，减少不必要的消息交换，以及利用批量处理和预处理技术来提升效率。
3. 性能评估
作者进行了详细的性能测量，证明了他们的实现是具有竞争力的。这包括在不同故障场景下系统的稳定性和恢复速度，以及在正常运行条件下的操作延迟和吞吐量。
4. 应用场景
Paxos 的应用不仅限于数据库一致性，还可以用于构建其他需要一致性保证的服务，如分布式锁服务、配置管理和服务发现等。通过在每个副本上构建相同的日志，并对这些日志应用相同的操作序列，可以在所有副本上实现一致的数据结构。
"Paxos Made Live" 揭示了Paxos共识算法在现实世界中的挑战和实践，对于理解如何将理论上的分布式一致性算法转化为实际可用的系统具有重要的指导意义。
Figure 2: API for fault-tolerant log.
between replicas. Replicas have access to persistent storage that survives crashes. Some replica s may submit
values for consens us. If eventually a majority of the replicas run for long e nough without crashing and there
are no failures, all running replicas are guaranteed to agree on one of the values that was submitted. In our
system, the value to be agreed upo n is the next entry in a (replicated) log as described in the introduction.
The algorithm consists of three phases, which may be repeated (because of failures ):
1. Elect a replica to be the coordinator.
2. The coordinator selects a value a nd broadcasts it to all replicas in a message called the accept message.
Other replicas either acknowledge this message or reject it.
3. Once a majority of the replicas acknowledge the coordinator, consensus has been rea ched, and the
coordinator broadcasts a commit message to notify replicas.
To provide some intuition about how the algorithm works, consider first the case in which there is only
a single coordinator and no failures. Consensus is reached once a majority of replicas receive the accept
message from the coordinator and acknowledge it. Subsequently, if any minority of the replicas fail, we are
still guaranteed that at least one replica will be alive that rece ived the consensus value.
In reality the coordinator may fail. Paxos does not require that only one replica act as coordinator at a
time. Multiple replica s may decide to become coordinators and e xecute the algorithm at any time. Typically
the system is engineered to limit coordinato r turnover, as it can delay reaching consensus .
This flexible election policy means there may be multiple replicas who simultaneously believe they are
the coor dinator. Further, these coordinato rs may select different values. Paxos ensures consensus can be
reached o n a single va lue (it can be from any coo rdinator) by introducing two extra mechanisms: 1) as signing
an ordering to the successive coordinators; and 2) restricting each coordinator’s choice in selecting a value.
Ordering the coordinators allows each replica to distinguish between the current coordinator and previous
coordinators. In this way, replicas can re ject messages from old coor dinators and prevent them from disrupt-
ing consensus once it is reached. Paxos orders the coordinators by ass igning them an increasing sequence
number as follows. Each replica keeps track of the most recent sequence number it has seen so far. When a
replica wants to become coordinator, it gener ates a unique
1
sequence number higher than any it has seen,
1
For example, in a system with n replicas, assign each replica r a unique id i
r
between 0 and n − 1. Replica r picks the
smallest sequence number s larger than any it has seen such that s mod n = i
r
.
4
剩余15页未读，继续阅读
2019-05-14 上传
2009-12-18 上传
2020-01-31 上传
2018-09-25 上传
2021-06-25 上传
2021-04-14 上传
2023-06-12 上传
2021-06-14 上传
2021-03-08 上传
ken_henderson
- 粉丝: 2
- 资源: 11
我的内容管理
展开
