分布式系统相关

Table of Contents

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时钟是确定分布式系统中事件发生的顺序的一种算法:给所有进程中发生的事件一个编号,

  1. 同一个进程中事件按照发生先后顺序从小到大编号。
  2. 不同进程中的事件编号按照消息传播的方向有:接收者的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
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

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

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 只会产生一个共识。

算法流程

  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 信息,则知道共识已经达成。

可能的问题(阻塞)

paxos-contention.png

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

TODO Paxos 完整版

Raft

设定

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

replicate_state_machine.png

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

每个节点可能有三个状态:

  • leader(领导)
  • follower(跟随者)
  • candidate(领导候选)

Leader Election(领导选举)

Log Replication(日志复制)

DHT(Distributed Hash Table)

Author: expye(Zihao Ye)

Email: expye@outlook.com

Date:

Last modified: 2021-10-25 Mon 21:58

Licensed under CC BY-NC 4.0