分布式系统相关

Lamport/Vector Clock

在分布式系统中无法保证所有节点的绝对时钟保持同步，于是退而求其次使用相对时钟。 Lamport时钟定义了一个全序关系，保证发生消息传递的双方发送和接收时间戳满足因果关系：如果事件 \(a\) 导致了事件 \(b\) ( \(a\rightarrow b\) )，那么 \(C(a) < C(b)\)

向量时钟则在消息传播时的消息中加上了每台机器的事件戳，使得这个全序关系可以判断两个事件是否是并发的。

我个人的理解是向量时钟是对所有消息传播历史的一个可全序化编码。

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

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

Paxos 算法中有三个角色：

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

一轮 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 机制。

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

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