分布式系统相关

Lamport Timestamp
RPC (Remote Process Call)
- 动机
- 主要原理
Paxos
Raft
DHT(Distributed Hash Table)

Lamport Timestamp

source: Time, Clocks, and the Ordering of Events in a Distributed System
wiki (lamport timestamp): https://en.wikipedia.org/wiki/Vector_clock
wiki (vector clock): https://en.wikipedia.org/wiki/Vector_clock

Lamport时钟是确定分布式系统中事件发生的顺序的一种算法：给所有进程中发生的事件一个编号，

同一个进程中事件按照发生先后顺序从小到大编号。
不同进程中的事件编号按照消息传播的方向有：接收者的ID >= 发送者的ID + 1。

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
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

rpc_stub.h

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
Acceptor (PROMISE phase)
- 如果承诺过忽略该 ID
  - 忽略该请求
- 如果未承诺过忽略该 ID
  - 在未来忽略所有比它小的 ID
  - 如果有接受过某个值（假设接受的值对应 ID 为 ID')
    - 向 Proposer 发送 PROMISE ID, accepted ID', value
  - 否则
    - 向 Proposer 发送 PROMISE ID
Proposer (ACCEPT-REQUEST phase)
- 如果 Proposer 接受到超过半数的关于某个 ID 的 PROMISE 回复
  - 发送 ACCEPT-REQUEST ID, value 给 acceptors.
  - 关于 value 的取值
    - 如果 PROMISE 中提到了之前有接收过的值，则使用改值
    - 否则任选一个希望大家达成共识的值。
Acceptor (ACCEPT phase)
- 如果承诺过忽略该 ID
  - 忽略该请求
- 否则
  - 回复 ~ACCEPT ID value~，并抄送给所有的 learners

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

可能的问题(阻塞)

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

TODO Paxos 完整版

Raft

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

设定

我们希望在一组服务器机器上维护相同的日志，其中一部分机器可能会宕机，需要允许一定的容错性。常用的模型是Replicated State Machine（复制状态机），客户端与一致性模块交互，服务端之间通信形成共识并更新自己的日志，将更新过的状态返回给客户端：

我们期望分布式共识算法能够在非拜占庭条件下满足安全性，包括网络延迟、分区、丢包、冗余和乱序。