对共识算法的简单了解

发表于 更新于 分类于 ， ， 阅读次数： 评论： 本文字数： 2k 阅读时长 ≈ 5 分钟

共识算法

共识算法（consensus A7M），即达成共识的过程，而非一致性算法。一致性（consistency）是终态，共识算法是达成一致性的一种实现手段和过程。

常见的共识算法有

PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错算法）

PoW（Proof of Work，工作量证明）

PoS（Proof of Stake，权益证明）

DPoS（Delegate Proof of Stake，委托权益证明）

Ripple（瑞波）

共识机制（协议）

需要一种机制来保证区块链中的每一区块只能由一个节点来负责修改，如何选出修改数据的节点，这就是共识机制。让平等的参与者按照某种秩序达成一致意见。

参考资料

什么是共识算法

分布式系统集群设计中面临着一个不可回避的问题，一致性问题。

对于系统中的多个服务节点，给定一系列操作，如何试图使全局对局部处理结果达成某种程度的一致？

这个一致性问题大致有如下的场景：

  • 节点之间通讯不可靠的，延迟和阻塞

  • 节点的处理可能是错误的，甚至节点自身随时可能宕机

  • 节点作恶

一个很重要的解决一致性算法的解决思路，即：

将可能引发不一致的并行操作进行串行化，就是现在计算机系统里处理分布式一致性问题基础思路和唯一秘诀。

CAP 原理

  • C（一致性）：所有的节点上的数据时刻保持同步，即数据一致
  • A（可用性）：每个请求都能在一定时间内接受到一个响应，即低延迟
  • P（分区容错）：当系统发生分区时仍然可以运行的

一致性：是指分布式系统中所有节点在同一时刻持有同样的数据信息;

可用性：是指系统处于服务状态,当客户端发出请求,服务端能在有效的时间内返回结果;

分区容忍性：是指允许网络中部分节点不与其他节点通信,即允许网络发生分区(不同区域之间的节点不能建立通信)。

定理：任何分布式系统只可同时满足二点，没法三者兼顾。即一致性、可用性和分区容忍性不可能同时满足。

CAP原理在分布式网络系统的应用讨论，其实就是讨论在允许网络发生故障的系统中，该选择一致性还是可靠性？

如果系统重视一致性，那么可以基于ACID原则做系统设计

即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）。

ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。

  • Atomicity：每次操作是原子的，要么成功，要么不执行；
  • Consistency：数据库的状态是一致的，无中间状态；
  • Isolation：各种操作彼此互相不影响；
  • Durability：状态的改变是持久的，不会失效

相应的有一个BASE原则，（Basic Availiability，Soft state，Eventually Consistency）则强调了可用性。

Paxos 最早的共识算法，非拜占庭算法的代表

Paxos有三种角色：

  • proposer：提出一个提案，等待大家批准为结案。客户端担任该角色；
  • acceptor：负责对提案进行投票。往往是服务端担任该角色；
  • learner：被告知结案结果，并与之统一，不参与投票过程。即普通节点

系统运行由proposer驱动，当合法提案在一定时间内收到1/2以上投票后达成共识。

因此，可得出无法达成共识的条件：

  1. proposer故障
  2. 二分之一以上acceptor故障

对于拜占庭问题来说，假如将军总数为 N，叛变将军数为 F，则当N>=3F+1 时，问题才有解，即叛变的将军不超过1/3时，存在有效的算法，如BFT，不论叛变者如何折腾，忠诚的将军们总能达成一致的结果。

PBFT 在区块链上的实现

区块链的节点分为记账节点和普通节点两个角色

记账节点负责向全网提供记账服务，并维护全局账本，每过一段时间从记账节点中选一个议长，进行命令的分发，其他记账节点则作为议员进行验证

将军就是记账节点，拥有全局账本，并验证交易的有效性，过互相传达验证结果，在f<=(n-1)/3的前提下，可以保证能达到全局的一致性

共识的一般流程

  1. 任一节点接收到发送者签名的交易数据请求后，向全网广播

  2. 所有记账节点均独立监听全网的交易数据，并记录在内存

  3. 议长在经过t后发送共识请求提案request

  4. 议员在收到提案后，进行相关验证，发送响应response

  5. 节点在限定时间内收到至少F+1个response后，共识达成，把交易记录入区块并发布给全网，如果超时，则更换视图和议长

  6. 任意节点在收到完整区块后，把包含的交易从内存中删除

开始下一个共识循环

共识算法介绍

区块链共识算法研究综述

个人思考

首先要建立起一个基本的认知框架。

然后，要扩大共识算法所囊括的个体，以保证整体的稳固性。

控制整体的大小。

思考：以相对较少的低延迟节点构建分布式系统的核心，以极高的同步速率来避免三分之一以下节点异常导致的系统不正常变化。

节点异常：

  1. 故障的，不响应的节点

  2. 恶意响应的节点