分布式系统相关
Table of Contents
RPC (Remote Process Call)
动机
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 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
主要的关注点在于工程实现:
Paxos
简化版逻辑
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 只会产生一个共识。
算法流程
- Proposer (PREPARE phase)
- 以递增次序(e.g. 1, 3, 5)选择一个独有的 ID,并向 acceptor 发出信息
PREPARE ID
- 如果超过半数的 acceptor 接受了这个请求, 结束该阶段
- 如果超时,增加 ID,重新发送
PREPARE ID
- 以递增次序(e.g. 1, 3, 5)选择一个独有的 ID,并向 acceptor 发出信息
- Acceptor (PROMISE phase)
- 如果承诺过忽略该 ID
- 忽略该请求
- 如果未承诺过忽略该 ID
- 在未来忽略所有比它小的 ID
- 如果有接受过某个值(假设接受的值对应 ID 为 ID')
- 向 Proposer 发送
PROMISE ID, accepted ID', value
- 向 Proposer 发送
- 否则
- 向 Proposer 发送
PROMISE ID
- 向 Proposer 发送
- 如果承诺过忽略该 ID
- Proposer (ACCEPT-REQUEST phase)
- 如果 Proposer 接受到超过半数的关于某个 ID 的
PROMISE
回复- 发送
ACCEPT-REQUEST ID, value
给 acceptors. - 关于 value 的取值
- 如果
PROMISE
中提到了之前有接收过的值,则使用改值 - 否则任选一个希望大家达成共识的值。
- 如果
- 发送
- 如果 Proposer 接受到超过半数的关于某个 ID 的
- Acceptor (ACCEPT phase)
- 如果承诺过忽略该 ID
- 忽略该请求
- 否则
- 回复 ~ACCEPT ID value~,并抄送给所有的 learners
- 如果承诺过忽略该 ID
如果超过半数的 acceptor 接受了 ID 和 value,则共识达成,值为接受的 value 值,并且不会发生变化(ID 可能会更新)。如果 proposer 和 learner 收到了超过半数的关于一个 ID 的 ACCEPT 信息,则知道共识已经达成。
可能的问题(阻塞)
如图所示,由于超时——重新发送的机制,两个 proposer 的 PREPARE
和 ACCEPT-REQUEST
阶段可能会互相阻塞,解决方案之一是 exponential backoff 机制。