(window.webpackJsonp=window.webpackJsonp||[]).push([[149],{462:function(_,v,l){"use strict";l.r(v);var a=l(10),o=Object(a.a)({},(function(){var _=this,v=_._self._c;return v("ContentSlotsDistributor",{attrs:{"slot-key":_.$parent.slotKey}},[v("h1",{attrs:{id:"共识算法"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#共识算法"}},[_._v("#")]),_._v(" 共识算法")]),_._v(" "),v("h2",{attrs:{id:"_2pc"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#_2pc"}},[_._v("#")]),_._v(" 2PC")]),_._v(" "),v("p",[_._v("：两阶段提交（two-phase commit），是 1980 年代发布的一个共识算法。")]),_._v(" "),v("ul",[v("li",[_._v("流程：\n"),v("ol",[v("li",[_._v("Voting 阶段：一个节点担任 coordinator 角色，发送一个提议（比如想 commit 一个事务）给其它节点。其它各个节点对该提议进行投票，回复一个表示同意或否决的消息。")]),_._v(" "),v("li",[_._v("Commit 阶段：如果所有节点都投票同意，则 coordinator 执行该提议，并通知其它节点跟随该决策。\n"),v("ul",[v("li",[_._v("如果投票不通过，则 abort 该提议。并且如果该提议已经修改了一些数据，则 rollback 到之前状态。")])])])])]),_._v(" "),v("li",[_._v("缺点：\n"),v("ul",[v("li",[_._v("如果 coordinator 在发送提议之后故障，则其它节点可能不知道投票结果，即该提议是被 commit 还是 abort ，导致其它节点阻塞在当前阶段，该问题称为 fail-stop 。")]),_._v(" "),v("li",[_._v("在 Commit 阶段，coordinator 需要阻塞等待其它节点都行动完毕，才能确定该提议的执行结果。")]),_._v(" "),v("li",[_._v("要求所有节点都投票同意，没有容错性，存在单点故障的风险。")])])])]),_._v(" "),v("h2",{attrs:{id:"_3pc"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#_3pc"}},[_._v("#")]),_._v(" 3PC")]),_._v(" "),v("p",[_._v("：三阶段提交（three-phase commit），是 1980 年代发布的一个共识算法。")]),_._v(" "),v("ul",[v("li",[_._v("流程：\n"),v("ol",[v("li",[_._v("Voting 阶段")]),_._v(" "),v("li",[_._v("PreCommit 阶段：如果所有节点都投票同意，则 coordinator 将投票结果发送给其它节点。其它节点收到投票结果之后，回复一个表示确认的消息。")]),_._v(" "),v("li",[_._v("Commit 阶段：如果其它节点已确认，则 coordinator 执行该提议，并通知其它节点跟随该决策。")])])]),_._v(" "),v("li",[_._v("优点：\n"),v("ul",[v("li",[_._v("3PC 在 2PC 的基础上增加了 PreCommit 阶段，能解决 fail-stop 问题。")]),_._v(" "),v("li",[_._v("在 Commit 阶段，coordinator 不必阻塞等待其它节点都行动完毕。")])])]),_._v(" "),v("li",[_._v("缺点：\n"),v("ul",[v("li",[_._v("发生网络分区时，3PC 依然不能达成共识。例如一半的节点收到了 PreCommit 消息，另一半的节点没收到，导致作出不同的决策。")])])])]),_._v(" "),v("h2",{attrs:{id:"paxos"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#paxos"}},[_._v("#")]),_._v(" Paxos")]),_._v(" "),v("p",[_._v("：一个共识算法，于 1990 年发布。")]),_._v(" "),v("ul",[v("li",[_._v("系统中一些节点担任 Proposer ，有权发出提议（Proposal）、投票。\n"),v("ul",[v("li",[_._v("其它节点担任 Acceptor ，有权投票。")])])]),_._v(" "),v("li",[_._v("一个提议需要超过半数的节点投票同意，才能通过。\n"),v("ul",[v("li",[_._v("用公式描述：假设节点总数为 N ，要求法定成员数为 "),v("code",[_._v("Quorum = N/2 + 1")]),_._v(" ，其中 / 为整除运算符。当一个提议被至少 Quorum 个节点投票同意时，才能通过。")]),_._v(" "),v("li",[_._v("这属于多数派（Majority）策略，可容忍不超过半数的节点不同意、离线。")])])])]),_._v(" "),v("h2",{attrs:{id:"raft"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#raft"}},[_._v("#")]),_._v(" Raft")]),_._v(" "),v("p",[_._v("：一个共识算法，于 2013 年发布，在 Paxos 算法的基础上作了改进，是目前流行的共识算法。")]),_._v(" "),v("ul",[v("li",[_._v("系统中有且仅有一个节点担任 Leader ，有权发出提议（Proposal）、投票。\n"),v("ul",[v("li",[_._v("其它节点担任 Follower ，有权投票。")]),_._v(" "),v("li",[_._v("Leader 会定期发送心跳包给其它 Follower 节点。如果其它节点超过一定时长没有收到心跳包，则变为 Candidate 状态，选举一个节点担任新 Leader 。\n"),v("ul",[v("li",[_._v("每次选出新 Leader ，就开始一个新任期，称为 Term 。")])])])])]),_._v(" "),v("li",[_._v("每次准备修改集群数据时，Leader 会将该提议发送给所有 Follower ，等超过半数的节点同意并执行之后，才通过该提议，从而达成共识、数据一致性。\n"),v("ul",[v("li",[_._v("Quorum 必须超过半数。如果允许 Quorum 等于集群半数，甚至小于半数，则集群可能同时存在不止一个 Leader ，发生脑裂。")]),_._v(" "),v("li",[_._v("Leader 并不会等待所有节点都同意，因此属于最终一致性。")]),_._v(" "),v("li",[_._v("每个节点都信任其它节点发来的信息，因此不能实现拜占庭容错。")])])]),_._v(" "),v("li",[_._v("部署更多节点，增加 Quorum 的值，可以提高系统可用性，但是会增加每次达成共识的耗时。\n"),v("ul",[v("li",[_._v("Raft 集群应该部署奇数个节点。例如从节点总数从 3 增加到 4 ， Quorum 依然为 2 ，并不会提高可用性。")]),_._v(" "),v("li",[_._v("至少需要部署 1 个节点，但此时没有冗余节点，存在单点故障的风险。")]),_._v(" "),v("li",[_._v("建议部署 3 或 5 个 节点，此时允许 1 或 2 个节点故障，可用性较高。")]),_._v(" "),v("li",[_._v("如果部署 7 个或更多节点，可用性虽然很高，但会明显增加写操作的耗时。")])])])]),_._v(" "),v("h2",{attrs:{id:"bully"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#bully"}},[_._v("#")]),_._v(" Bully")]),_._v(" "),v("p",[_._v("：一个共识算法，与 Raft 算法相似。")]),_._v(" "),v("ul",[v("li",[_._v("如果 Leader 节点故障，则由 ID 最大的一个节点担任新 Leader 。")])]),_._v(" "),v("h2",{attrs:{id:"gossip"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#gossip"}},[_._v("#")]),_._v(" Gossip")]),_._v(" "),v("p",[_._v("：一个广播消息的协议，常用于 P2P 服务。")]),_._v(" "),v("ul",[v("li",[_._v("每个节点定期散播一次消息，最多发送给 k 个节点。\n"),v("ul",[v("li",[_._v("发送消息之后，不必确保对方接收。")]),_._v(" "),v("li",[_._v("其它节点收到消息之后，会散播给除了源节点之外的其它节点。")])])]),_._v(" "),v("li",[_._v("消息被病毒式传播，能实现最终一致性。")])]),_._v(" "),v("h2",{attrs:{id:"pow"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#pow"}},[_._v("#")]),_._v(" PoW")]),_._v(" "),v("p",[_._v("：工作量证明（Proof of Work），区块链的一个共识算法。")]),_._v(" "),v("ul",[v("li",[_._v("例如比特币采用基于哈希函数的 PoW 算法：\n"),v("ul",[v("li",[_._v("以区块为单位写入数据。")]),_._v(" "),v("li",[_._v("一些节点担任矿工，负责生成新区块，即写入数据到区块链。\n"),v("ul",[v("li",[_._v("每个矿工节点需要进行大量哈希运算，穷举猜测下一个区块的 nonce 随机数，第一个猜出来的节点有权生成该区块，然后广播给其它节点。")]),_._v(" "),v("li",[_._v("生成新区块的矿工，可以获得该区块产生的一定量 BTC 作为奖励。")])])]),_._v(" "),v("li",[_._v("非矿工的普通节点，只能读取区块链，或者向矿工发送写入请求。")])])]),_._v(" "),v("li",[_._v("可实现顺序一致性，并实现拜占庭容错。")])]),_._v(" "),v("h2",{attrs:{id:"pos"}},[v("a",{staticClass:"header-anchor",attrs:{href:"#pos"}},[_._v("#")]),_._v(" PoS")]),_._v(" "),v("p",[_._v("：权益证明（Proof of Stake），区块链的一个共识算法。")]),_._v(" "),v("ul",[v("li",[_._v("例如以太坊采用 PoS 算法：\n"),v("ul",[v("li",[_._v("一些节点质押 32 个 ETH ，获得成为验证者的资格，负责投票验证新区块是否有效。\n"),v("ul",[v("li",[_._v("如果行为不诚实，或者没有准时验证新区块，则质押的 ETH 销毁一部分，作为惩罚。")]),_._v(" "),v("li",[_._v("如果工作称职，则质押的 ETH 少量增加，作为奖励。")])])]),_._v(" "),v("li",[_._v("每个出块周期，随机选取一个验证者来打包新区块，然后广播给其它节点。")])])]),_._v(" "),v("li",[_._v("与 PoW 相比，PoS 去掉了工作量成本，大幅降低了挖矿消耗的计算机硬件、电能。")])])])}),[],!1,null,null,null);v.default=o.exports}}]);