理解分布式一致性:拜占庭容错与PBFT
之前的几篇文章我们讲了分布式协议里面的Paxos协议和Raft协议。这两个协议主要适用于可信节点的情况,所谓可信节点就是节点只会出现因为系统或者网络问题的宕机情况,不会有恶意节点。
那么如果有恶意节点的情况下,我们怎么去达成共识呢?一个很简单的办法就是少数服从多数,下面我们看一下拜占庭是做的。
拜占庭问题
先看一下我们要解决的问题,也叫做拜占庭将军问题。
话说有一天有n个拜占庭将军相约于魔法师大峡谷中,他们的目标就是推掉对方的塔。塔有点强大,只有不少于m个将军同时去推塔才能成功,如果一个一个的去推塔,就免不了身死道消的结果。那时候他们的微信版本还比较低,不能建群聊天,只能一对一的通信。
将军之间并不是表面上看起来的一条心,假如一个将军想组织大家在下午两点钟去偷塔,那需要怎么样操作才能保证不少于m个将军同时执行”两点钟偷塔“这个命令呢?
这个问题就叫做拜占庭将军问题,是指在不可信任环境下的分布式一致性问题。
这里我想强调一点,分布式一致性是指各个节点之间的数据同步一致,跟数据正确与否没有关系。
拜占庭容错BFT
拜占庭容错是分布式协议的一种属性,如果这种协议可以解决不可信任环境下的分布式一致性问题,那么它就是拜占庭容错。
PBFT(Practical Byzantine Fault Tolerance)
PBFT是拜占庭容错的一种实现。它的性能很高并且低延时,能够解决不信任节点的问题。
其有如下几个特征:
1. 同一时间只有一个Leader向外发送消息,其它节点只是被动接收消息。
2. 所有的节点互相之间通信,并且将其收到的消息转发给其他节点,从而达成多数共识。
3. 节点之间的消息需要保证:A:节点收到的消息确实是某个节点转发的。B:消息在发送过程中不会被篡改。
如果想让PBFT正常工作,那么恶意节点个数不能大于总节点个数的1/3。
正常来讲,节点个数越多,恶意节点所占有的比率就会越低,系统就会越稳定,但是因为所有的节点之间需要两两通信,节点个数的增多会带来节点之间通信的压力。
下面看下PBFT的工作流程:
- 客户端发给服务器说我要执行命令A。
- Leader将该命令分发给所有被动节点。
- 客户端收到f+1(f 是系统能够承受的最大恶意节点个数,即系统总节点个数为3f+1)个相同的结果,那么客户端即认为共识完成。
这里Leader是随机选择出来的,如果选出来的Leader在给定的时间内并没有发出广播,那么系统会自动挑选新的Leader并进入下一轮。
why 3f+1 ?
很多同学可能不理解为什么对于f个恶意节点来说,至少要3f+1个节点才能正常工作。这里给大家解释一下。
之前在Paxos和Raft协议里面,我们给大家讲过在可信任节点的环境里面,达成共识的条件是收到的消息需要>n/2 ,即要收到大多数节点的反馈才能表示共识完成。
那么在有不可信节点f的情况下,我们的可信任节点个数是n-f个,我们收到的可信任节点个数的反馈必须>(n-f)/2才表示绝大多数可信任节点已经收到消息了。同时我们也可能收到f个不信任节点发来的消息,那么当(n-f)/2 > f 的时候,根据多数原则,我们可以区分出哪些是信任消息,哪些是不可信任消息,因此得出 n> 3f .
PBFT 的优点
- 一致性结果一旦产出,不会更改。在区块链世界,像是比特币,以太坊,经常会听到区块确认的概念,这个就是结果不确定的问题,他们用的POW算法是以链的长度来决定最终的区块,当有更长的链产生的时候,之前的交易会被完全推翻。而PBFT不会存在这个问题。
- 相对于POW,PBFT对能源的消耗会少很多很多,再也不用浪费资源去挖坑了。
PBFT 的缺点
说完优点说缺点。其实前面我们也提到了,PBFT需要节点之间两两通信,当节点个数太多的话,节点之间通信的消耗会大大增加。所以PBFT只适合用在联盟内部少数节点的情况。像是Hyperledger这样的联盟链。
同时,PBFT也可能会受到女巫攻击(Sybil attack),这个后面我们有时间再单独讲。
更多教程请参考flydean的博客
相关文章
- 漫话:为什么程序员喜欢使用0 ≤ i < 10这种左闭右开的形式写for循环?
- 火爆Github!这份LeetCode刷题模板太实用了吧
- 扩展Kubernetes插件,从这6个方向开始
- 2020毕业生报告发布:IT行业最受欢迎,「求稳」是求职趋势
- 前端开发与架构师
- Go 语言 map 解析之 key 的定位核心流程
- 用 20 行代码写出清晰易用的 Go 中间件 API
- 仅仅1行代码的“拍一拍”,网友们都已经玩上瘾了!
- 高级技术人员必须具备的三大思维模式
- 年中盘点:2020年炙手可热的10家DevOps初创公司
- 替代Matlab的国产软件出现,开发商知乎答疑,称半年实现70%功能
- C语言与物联网之简单通信协议
- 美国商务部:针对华为新规没有漏洞,已向半导体企业发出新规指南
- 全球TOP10超级计算机8台都选英伟达的三大原因
- 消息队列失败经验总结(幂等性概念以及影响)
- 如果每个程序员都必须要纹一段代码在身上,你会纹哪个语句?
- 采用Kubernetes时API网关面临的两个很重要的挑战
- 怎样度过第一份编码工作的艰难时期?
- 容器编排之王,2020年Kubernetes有趣的12个数据
- 刷题两个月,从入门到字节offer,这是我的模板 | GitHub 1.2k星