共识算法

1）什么是共识，为什么需要共识

共识-在发生故障和延迟时,在多个节点之间协商相同的值/值序列。传统上，状态复制任务（State Machine Replication，SMR）是解决方案：存在确定性状态机器和总体操作顺序。

• 共识（SMR）：统一的总命令顺序→线性存储/注册表，群集元数据，事务协调员。
• 没有完全顺序的法定操作（类似Dynamo，CRDT）：允许差异和随后的合并；在需要全球序列化的地方不能取代共识。

2）时间与故障模型

2.1时间模型

异步网络：延迟是无限的；如果没有额外的假设，FLP定理⇒无法保证安全性和生活性。
部分同步（通常在实践中）：在未知的T之后，系统"表现"同步-大多数算法（Raft，Paxos）都依赖它。
同步：对通道的严格超时限制（除专用网络/PTP外，很少销售）。

2.2故障模型

Crash-fault tolerant （CFT）：节点可能会掉落/挂起,但不表现恶意。
Byzantine-fault tolerant （BFT）：节点可以说谎/伪造消息。需要3f+1节来耐受f拜占庭语。

3）共识属性

安全（安全）：一致性（两个正确的节点不会解决不同的值）。
Liveness（活着）：如果网络"健康",解决方桉就会实现。
可线性化（线性）：操作"可见"为单一顺序的原子。
耐用性：所作出的决定不会退回（日志保护/法定人数）。

4）法定人数，多数和交叉点

在CFT世界中，经典：法定人数>N/2。领导者的记录和选举使用法定人数的交集，因此两个"有效"操作不会发生冲突。
在BFT世界中：3f+1中的2f+1的法定值提供了至少f+1诚实节点的交叉点。

交叉规则：任何两个法定人数必须具有≥1通用诚实节点（CFT）或≥f+1（BFT）。

5）状态复制（日志+应用）

• Snapshots（可以删除/编译早期记录的状态切片）。
• 杂志汇编和日志三重奏。
• 确定性检查（密码/密码的相同版本）。

6）领导和非领导力计划

领导者（Raft，Multi-Paxos，ZAB）：一位领导者将记录序列化→在精神和操作上更简单，在稳定的领导者上更好。
无标记/多标记（EPaxos，Caesar）：对领导者的更多并发性和宽容，但实现和冲突解决更为困难；在小团队冲突中可见利润。

7）经典CFT算法

7.1 Paxos/Multi-Paxos（和实践）

想法：两个阶段（prepare/propose），接受者的承诺，多数法定人数。Multi-Paxos留下"稳定的领导者"，并在"预热"后将操作转换为单运行（用于新记录）。

• 灵活但难以实现的模型。
• 通过特殊记录（joint consensus）重新配置。
• 实际上，是库/引擎（Chubby/Spanner世代）。

7.2 Raft

可培训性的解密：领导者选择、日志复制、重新配置。

选择：随机定时，热量投票；一个领导一个任期。
AppendEntries：领导者流记录,跟随前缀匹配（索引/term）,通过多数提交进行通信。
读取路径：用于线性读取的lease-reads（具有强大的领导者）或读取索引。
Reconfig："协作配置"（joint）-节点在转换前在两个群集中进行投票。

优点：更容易开发/debag,强阶不变量。缺点：领导者是压力点。

7.3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB：领导者广播事务，恢复阶段，zxid（时代+索引）。
VRR：具有主要复制的"视图"（视图）在精神上类似于Multi-Paxos。

8）非里德/多用户CFT

8.1 EPaxos

没有永久领导者：任何节点都可以启动命令。
冲突团队获得部分顺序；无冲突-在本地被命令进入1-2 RTT。
在低冲突但复杂的依存关系/图代码下赢得地理分布。

8.2 Caesar, Mencius

在WAN中优化延迟/平衡和操作的变化。

9） BFT算法和PoS系列

9.1 PBFT (Practical BFT)

三个阶段（pre-prepare/prepare/commit）,需要3f+1节点。
局域网、多通道道路和O （N ²）消息的低潜伏率。

9.2 Tendermint（BFT-PoS风格）

Proposal和两个投票（prevote/precommit）的回合。
确定性建议验证器，超时，部分同步。
适用于具有数十个/数百个验证器的永久性/PoS网络。

9.3 HotStuff（和衍生产品）

将三相方案统一为具有法定证书（QC）的"包"。
线性通信复杂性，对批处理和并行管道化的支持对于区块链实现（例如Diem/Move生态系统）非常方便。
使用阈值签名（threshold signatures）可减少流量。

9.4 PoW/累积共识（简述）

不是严格意义上的BFT，而是概率收敛性（工作最多的链）。优点：简单/开放；缺点：能量，~秒钟到最后一分钟。

10）读数： 线性、串行和缓存

线性读取：带有活动优惠或通过read-index （Raft）的领导者通过法定人数→确认。
连续：您可以从任何节点读取,但不保证新鲜度。
Follower reads：宽松要求允许使用；对于缓存-ok。

11）重新配置（群集组成变更）

需要两种重叠的配置（joint consensus）：任何commites都通过两种配置的法定人数→没有"孔"。
每次添加/删除一个,遵守法定人数的大小。
领导力转移（领导力转移）减少了停顿。

12）性能和调音

12.1个延误

领导算法：每条记录1个RTT（具有稳定的领导者）+复制。
地理分配：RTT WAN占主导地位→使用本地区域+跨区域重铺或EPaxos/HotStuff方法。

12.2个吞吐量

与AppendEntries平行的Batching（命令分组），paig-kesh日志，并行应用（当操作切换时）。
驱动器：NVMe/日志在单独的设备上，"O_DIRECT"/AIO，带有SLA约束的大型"fsync" Intervel（可执行性/延迟权衡）。

12.3尾巴p99

避免热节点（领导者始终是其中之一）：定期轮换或阅读到追随者。
控制GC暂停（JVM/Go）、CPU Pins、NUMA。

13）地理和拓扑

1个区域，3个区域：经典的CFT集群（N=3/5）。
2个区域：避免-分隔1-1时无法获得可靠的法定人数。
3+区域："中间"或无限制算法的领导者；具有异步日志的区域代理/本地前沿是可能的。

14）实际操作问题

14.1 Snapshots和恢复

日志大小/操作数阈值。
将狙击手转移到新节点；验证基准金额。

14.2监视

领导：谁是领导者，改变了多少时间表（term/epoch）。

Лаги: `append_latency`, `commit_index - applied_index`.

定额健康： "多数/2f+1活着吗？"

日志大小/堆叠速度，快门队列。
对于BFT：选票份额，取消签名者，QC延迟。

14.3安全性/代码一致性

协议在线上的忠诚度，迁移与日志兼容性。
外部效果上的折射令牌（请参阅"分布式锁定"）：领导期限（term）传递给CRON/jobs。

15）反模式

将"为了时尚"的共识放在一个没有序列化的DBMS或法定阅读中。
溷合CP和AP无界限（CAP） →不可预测的UX。
重新评估具有数十个节点的企业任务的PoW/PoS（复杂/昂贵）。
更改组成时忽略重新配置和"相交的法定人数"。
缺少read-barrier（lease/read-sindex）→"脏"读取。
运行2节点群集（没有多数）。
低估磁盘和fsync："在内存中一切都在飞行"-直到第一次重新启动。

16）选择支票清单

1.故障模型： CFT（污垢）或BFT（恶意）?

2.地理：一个区域/三个区域或WAN?RTT决定。
3.阅读语义：需要线性阅读吗？Lease/read-index/follover rids。
4.负载：p50/p99，throughput的期望；是否需要多领导能力。
5.操作复杂性：库/完成引擎（etcd/ZK/Consul/Raft-libs）与自己的实现。
6.重新配置：频繁吗？需要联合咨询和迁移工具。
7.整合：外部副作用-是否有epoch/term fencing？
8.安全性：节点身份验证，链路加密，协议版本控制。
9.测试花花公子：分区，GC停止，杀手，慢盘，clock skew。
10.可观察性：已配置领导者/拉格/日志和差分度量。

17）迷你手册： 什么时候拿什么

etcd/Raft群集，用于DC内部的配置/锁定/协调。
ZooKeeper/ZAB用于已经绑定到ZK（旧堆栈，队列，领导力）的服务。
通过高度专业化的系统中的现成服务/库来实现多功能。
EPaxos在地理分布和低命令冲突中。
Tendermint/HotStuff 用于永久性网络/PoS layer，具有数十到数百个验证器和最终要求。
当不需要共识时，类似于Dynamo/CRDT的可用性/规模很重要，然后合并。

18）接口示例（伪）

18.1 Commit录音（Raft风格）

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18.2线性读取索引（Raft）

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18.3联合配置

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18.4 BFT（HotStuff接近）

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

问：为什么不使用两个节点和决胜局？
答：没有第三个仲裁员的两个节点在分手时不会产生法定人数。需要≥3（CFT）或3f+1（BFT）。

Q： Raft对Paxos"简单"有什么好处?

答：清晰的解构，可理解的逻辑和配置不变性；更容易实施和陪伴。

Q： 如何在不加载领导的情况下快速阅读?

A：非临界的follower-reads（串行），线性的lease-reads/read-sindex；缓存。

问：p99杀死什么？
A： WAN-RTT、fsync磁盘、GC脚、过热的领头羊、"高峰时段"的大狙击手。

Q： 是否需要对缓存/目录达成共识?

A：如果有足够的事件一致性-没有。如果需要事务不变量-是的。

20）结果

共识是严格一致和精简的工具。根据故障模型和地理位置选择算法；提供法定相交、正确的re配置、关键位置的线性读取和可观察性。不要忘记对外部效果、快照和杂志纪律的思考。然后状态复制将是可预测的，并且事件是罕见且易于理解的。