分布式系统·作业六

对以下每个应用程序,你认为最多一次语义和最少一次语义哪个更好?

  1. 从文件服务器上读写文件;
  2. 编译一个程序;
  3. 远程银行;
  1. 从文件服务器上读写文件:至少一次。对文件读写要保证其可靠性。
  2. 编译程序:至少一次。要编译文件的时候消息至少要被传送一次保证编译结果;多次编译其实影响不大。
  3. 远程银行:至多一次。比如,最多只能发出一次扣款消息,如果不成功,可以让客户重新发出扣款请求。不能在分布式系统内部作出扣款一次以上的动作,会带来负面影响(客户钞票多扣了)。

简述 Flooding、PAXOS、RAFT、PBFT、PoW 的使用场景?

  1. Flooding(洪泛)洪泛算法简单可靠,当网络的通信流量很小时,可使分组的传送时延最小。在许多条并行发送的路由中,显然会有一条是最佳的。洪泛不要求维护网络的拓扑结构和相关的路由计算,仅要求接收到信息的节点以广播方式转发数据包,在小型局域网络中被用的比较多,更大一点的分布式系统中更多使用的是下面的算法。
  2. Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个「一致性算法」以保证每个节点看到的指令一致。
  3. Raft 最初是一个用于管理复制日志的共识算法,它是一个为真实世界应用建立的协议,主要注重协议的落地性和可理解性。Raft 算法不论出于教学目的还是作为实践项目的基础都是要比 Paxos 或者其他一致性算法要优异的。它比其他算法更加简单,更加容易理解;它的算法描述足以实现一个现实的系统;它有好多开源的实现并且在很多公司里使用;它的安全性已经被证明;它的效率和其他算法比起来也不相上下。(来自于Github 上 Raft 算法的翻译
  4. PBFT(实用拜占庭容错系统)降低了拜占庭协议的运行复杂度,从指数级别降低到多项式级别(Polynomial),使拜占庭协议在分布式系统中应用成为可能。拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因,计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为,并满足所要解决的问题的规范要求。
  5. PoW(Proof of Work,工作量证明):去中心化账本系统。每个加入这个系统的节点都要保存一份完整的账本,但每个节点却不能同时记账,因为节点处于不同的环境,接收到不同的信息,如果同时记账的话,必然会导致账本的不一致,造成混乱。因此,需要有共识来达成哪个节点有权记账。比如,比特币区块链通过竞争记账的方式解决去中心化的记账系统的一致性问题,即以每个节点的计算能力即「算力」来竞争记账权的机制。

任意选择一种编程语言实现的 RAFT 程序,运行该程序并测试记录结果。

我选择了一个更加简洁的 python 实现:https://github.com/hangsz/raft。终端输入下述指令,将仓库拉取到本地:

git clone https://github.com/hangsz/raft
cd raft

分三个终端分别执行下述三个指令,启动三个节点进程:

python node1.py
python node2.py
python node3.py

三个服务进程启动后的结果如图所示,自上而下三个终端分别是 node1、node2、node3。可以看到每个节点开始的时候都是 follower。

raft1

一轮选举之后,node1 被选举为 leader。

raft2

平稳运行若干「心跳时间」(heartbeat)。

raft3

手动关掉 leader 进程,这时候其他几个节点还没有反应。

raft4

下一个选举周期,node3 被选为 leader。

raft5

在终端运行下述指令,启动一个客户端进程。

python client.py

可以看到客户端启动后发送了一条消息并被 node3(leader)收到。

raft6

node2 现在也收到了。

raft7