分布式系统相关

RPC 是分布式系统的基础架构之一，RPC 库实现了 client 和 server 的简易通信，使用户不需要去了解网络协议的细节。

Software structure
  client app        handler fns
   stub fns         dispatcher
   RPC lib           RPC lib
     net  ------------ net

MIT 6.824 Lecture 2 中介绍了引入 RPC 的基本概念。

C/C++上没有原生的 RPC 支持，虽然市面上已经有很多成熟的 RPC 库(grpc)，出于学习的角度考虑，自己实现一套 RPC 是有助于理解的，洪春涛老师的Remmy是一个不错的教学项目，基本原理很显然：

// Client 端 
//    int l_times_r = Call(ServerAddr, Multiply, lvalue, rvalue)
1. 将这个调用映射为 Call ID。这里假设用最简单的字符串当 Call ID 的方法
2. 将 Call ID，lvalue 和 rvalue 序列化。可以直接将它们的值以二进制形式打包
3. 把 2 中得到的数据包发送给 ServerAddr，这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功，那么就将结果反序列化，并赋给 l_times_r

// Server 端
1. 在本地维护一个 Call ID 到函数指针的映射 call_id_map，可以用 std::map<std::string, std::function<>>
2. 等待请求
3. 得到一个请求后，将其数据包反序列化，得到 Call ID
4. 通过在 call_id_map 中查找，得到相应的函数指针
5. 将 lvalue 和 rvalue 反序列化后，在本地调用 Multiply 函数，得到结果
6. 将结果序列化后通过网络返回给 Client

作者：洪春涛
链接：https://www.zhihu.com/question/25536695/answer/221638079
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

主要的关注点在于工程实现：

• rpc_stub.h

Youtube 上有一个简化的介绍：https://www.youtube.com/watch?v=d7nAGI_NZPk

• Leader-replica schema
  • 维护一个 leader 节点和一组 replica 节点
  • 当一个 replica 需要更新某个值的时候会汇报给 leader，由 leader 序列化所有的 proposal 并分发给 replica。
• Peer-to-peer
  • 所有的节点储存相同的内容且行为一致。
  • 当有节点想更新值的时候，会广播给所有的其它节点，大家形成一致的共识，因此所有的节点按照一致的顺序操作。

在 Leader-replica 的情况下，当 leader 不可用的时候，replica 节点需要产生共识以选出新的 leader。在 Peer-to-peer 的情况下，所有节点必须持续地达成共识才能保证一致性。

Paxos 算法中有三个角色：

• proposers: 提出新的变更（需要大家达成共识）
• acceptors: 对形成共识做出贡献（投票表决者）
• learners: 学习已经达成的共识（吃瓜群众）

一个 Paxos 节点需要满足以下要求：

• 每个 Paxos 节点都可以扮演多个角色
• 每个 Paxos 节点必须知道 majority 中有多少个 acceptor
• Paxos 节点必须保持一致性：Paxos 节点不能忘记自己接受的 proposal

一轮 Paxos 只会产生一个共识。

1. Proposer (PREPARE phase)
   • 以递增次序(e.g. 1, 3, 5)选择一个独有的 ID，并向 acceptor 发出信息 PREPARE ID
   • 如果超过半数的 acceptor 接受了这个请求, 结束该阶段
   • 如果超时，增加 ID，重新发送 PREPARE ID
2. Acceptor (PROMISE phase)
   • 如果承诺过忽略该 ID
     • 忽略该请求
   • 如果未承诺过忽略该 ID
     • 在未来忽略所有比它小的 ID
     • 如果有接受过某个值（假设接受的值对应 ID 为 ID')
       • 向 Proposer 发送 PROMISE ID, accepted ID', value
     • 否则
       • 向 Proposer 发送 PROMISE ID
3. Proposer (ACCEPT-REQUEST phase)
   • 如果 Proposer 接受到超过半数的关于某个 ID 的 PROMISE 回复
     • 发送 ACCEPT-REQUEST ID, value 给 acceptors.
     • 关于 value 的取值
       • 如果 PROMISE 中提到了之前有接收过的值，则使用改值
       • 否则任选一个希望大家达成共识的值。
4. Acceptor (ACCEPT phase)
   • 如果承诺过忽略该 ID
     • 忽略该请求
   • 否则
     • 回复 ~ACCEPT ID value~，并抄送给所有的 learners

如果超过半数的 acceptor 接受了 ID 和 value，则共识达成，值为接受的 value 值，并且不会发生变化（ID 可能会更新）。如果 proposer 和 learner 收到了超过半数的关于一个 ID 的 ACCEPT 信息，则知道共识已经达成。

如图所示，由于超时——重新发送的机制，两个 proposer 的 PREPARE 和 ACCEPT-REQUEST 阶段可能会互相阻塞，解决方案之一是 exponential backoff 机制。

可视化讲解：http://thesecretlivesofdata.com/raft/