Paxos 协议与工程实现
写在前面，我没有完整实现过 Paxos 协议，不敢保证下面描述的内容完全正确。本文主要是学习的笔记，如果有错误，十分欢迎指出，大家一起讨论学习。
本文所有内容都是参考 PaxosStore 论文 《PaxosStore: High-availability Storage Made Practical in WeChat》
概念定义
为了后续方便描述，我们先定义会用到的概念
- Proposal 提议，包含提议号和提议值；
- Prepare 第一阶段 Proposer 发出的请求，包含一个提议号；
- Promise 第一阶段 Proposer 回应的消息，包含一个提议号和一个（如果有）已经 Accepted 的最大提仪；
- Accept 第二阶段 Proposer 发出的请求，包含一个提议号和一个提议值；
- Accepted 第二阶段 Proposer 回应的消息，包含一个提议号。也表示一个提议被一个该 Proposer 接受；
- Chosen 代表一个提议被大多数的 Proposer 接受，不会再发生改变；
- Proposer 提议成员；
- Acceptor 发送 Accepted 消息的成员；
- Learner 学习者，不参与 Paxos 投票过程。
与可以用代码语言描述，参考 链接
// Prepare 请求，包含一个提议号
struct Prepare {
int n;
};
// 在收到大多数的 Promised 请求后，发出的 Accept 请求，包含一个提仪号以及一个值。
// 这个值是 Promised 中最大提议号的值，如果所有 promised 都没有返回值，则可以自己提出任意值。
// 对应到工程实现上，则代表这个位置已经被占了，可以再起一轮新 paxos
struct Accept {
int n;
void *value;
};
// n 承诺不 accept 小于 n 的 accept 请求，返回当时最大提议号对应的值。
struct Promised {
int n;
Accept *proposal = nullptr;
};
// 如果满足承诺，返回最大的提议号
struct Accepted {
int n;
};
// paxos 成员会在内存中纪录的值，包括最大的提议号，以及对应的值。
class Acceptor {
int last_n = 0;
Accept *proposal = nullptr;
};
Basic Paxos 协议
Basic Paxos 是理论上的最基础的一致性算法，作用是：多个（奇数）成员确定唯一一个值。
算法分为两轮，第一轮 Prepare 请求会得到承诺后续不通过小于本次 Prepare.n 的提议，同时返回自己已经 accepted 的最大提议。第二轮 Accept 请求会带上上一轮收到的最大提议值（如果没有，则可以自己提出），每个 Acceptor 在不违背承诺的情况下更新本地状态。
一个提仪一旦被大多数结果 accepted，就会被认为是 chosen。对于一个值来说，accepted 还是可以变的，chosen 的永远不会变。一组经典的 paxos 实例只能确定（chosen）一个值。
算法的详细描述可以参考论文：
Phase 1.
A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.
Phase 2.
If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
注意细节：
- Accept 请求中的 value 是一阶段返回所有 promised 中 n 最大的那个值。是 promised→proposal.n 的 n，而不是 promised.n
- acceptor 上 accept 值还是会被修改的。
- 在提议被大多数通过的一瞬间，这个值就确定下来了，再也不会被修改。
对于证明的思路是这么一种思路：证明一个值 chosen 不会被修改，可以通过加强的方式。如果一个大于当前提仪号并且值不同的提仪，不会被发出。chosen 的值自然就不会被修改。
Multi Paxos 实现方法
可以看到，Basic Paxos 算法只能确定一个值，同时要走两轮流程。为了在真实系统上实际使用起来，还需要做一些修改优化。
我们可以在 Basic Paxos 上增加一个 Entry ID 的维度，每个 Entry 保存一个值。同时，可以在第 i 个 Entry 中携带上第 i+1 个 Entry 的 Prepare 信息：当 $E_i$ 被 chosen 时，同时认为 $E_i+1$ 已经完成了 prepare 流程。
工程实现上的问题
论文只描述了 Paxos 算法的流程和证明，在实际实现上，还有很多细节要处理，例如怎么 CatchUp、怎么 GetALL以及一些细节的问题。
写读读问题
写读读的问题场景：假设三机日志都commit到了Entry 100，然后机器 A执行 Entry 101 的二轮过程然后挂掉。这个时候会读到 100 的值。然后机器 A 恢复同步状态到 BC，后续就读到了 Entry 101。
重复执行问题
重复执行的问题场景：机器 A 收到一个写请求，在执行完 Paxos 后被 chosen，然后发送响应给客户端。这个响应可能因为网络原因未发到或者超时。然后客户端超时后重发请求到机器 B。机器 B 重新跑一次 Paxos 过程，然后回复客户端。这儿更新过程就会执行两次，如果是有状态的更新就会有问题。
所以要让请求幂等，方法就是在请求上带上 request ID， svr 端检查 request ID 。
The request ID is generated by the client and sent together with the write request, and checked by the PaxosStore node to detect potential duplication of actual request handling.
PlogKV 实现问题
文章同时提到了一个 PaxosLog for KV Data，可以优化掉 DB 部分的成本。那么正常的plog存储的key应该是entityid和entryid？怎么用key来查询？
答案是只维护两个entry，一个最新chosen，一个pending。每个 key 都是一个 paxos 实例。
