前言
There is only one consensus protocol, and that’s Paxos. ——Mike Burrows(Google Chubby)
Overview
Paxos 和 Raft 的共识方式是类似的，大多数是术语的区别，比如对于 Multi-Raft 而言，大致可以分为三个层，Client，Server，Raft。
- Client 层给请求包一个唯一 id，扔到对应 Raft Group Server 层的 Leader 节点；
- Server 层是处理请求的地方，需要和 Raft 层交互，具体而言，Server 层需要将 Client 的请求发送到 Raft 层进行共识，多数派共识之后这个 Raft Group 的不同 Server 都会执行相同的请求，但是由 Leader 返回结果；
- Raft 层通过领导人选举、心跳、日志复制进行共识，日志过多时还能进行快照压缩；其中，Raft 的 leader 对应 Paxos 的 Proposer，会分配一个 rnd 并发起一次 Paxos 共识，Paxos 还有 Acceptor 和 Learner。
- Raft 的 Term 还被 Paxos 称作 views, ballot numbers, proposal numbers, round numbers。
- Raft 的选举的过程有些类似于 Classic Paxos 的 phase-1。
- Raft Leader 的日志复制则类似于 Classic Paxos 的 phase-2。
Classic Paxos phase-1
当 Paxos 的 Proposer 向 Acceptor 发送一个共识的请求时，如果请求中的 rnd 比 Acceptor 的 last_rnd 小，则拒绝共识该请求（返回自己的 last_rnd 和 value）；反之，则将 last_rnd 设置为 rnd，从此 Acceptor 只接受 last_rnd 的 phase-2 请求。所以 rnd 大的请求会覆盖 rnd 小的请求。
PBFT，即实用拜占庭容错。本文不赘述 BFT 相关概念，而是简述论文的具体实现部分。
默认情况下的 PBFT
假设节点数量为 3f+1，每个节点需要维护一致的状态机，为了能够迅速达成共识，需要有一个主节点，其他节点则作为从节点，主节点带领其他节点共识的这段时间称为 view，有点像 Raft 的任期，是自增的。
GFS 是 Google 2003 年发表的论文，是分布式系统最早的大规模工业化实践。当时的背景是 Google 需要一个适用于各种 application 的 Global 存储系统。
GFS 的目标
- 部署在廉价机器，需要自动监控、容错和恢复。
- 能够处理海量大文件，数十亿 GB 级别的文件组成的 TB 级快速增长的数据。
- 总是批量读取数据，侧重于顺序读取和 Append 数据，因此没有太大的内存加速需求。
- 能够自动让数据在机器之间同步。
Design Overview
iterface
create, delete, open, close, read, write, snapshot, record append.
BigTable 是搭建在 GFS 之上的结构化数据的存储系统，其作用主要是作为分布式的 NoSQL。
在 GFS 和 Chubby 的基础上在工程中实现了 LSM-Tree。
数据结构
实际上就是 KV
Key：row+column+timestamp
value：blob
CRDT 是一种无冲突复制数据类型，它支持强最终一致性（SEC, Strong Eventual Consistency）。这种数据类型常用于需要多用户协作编辑的文档，或者那些要求快速响应但不需要很高实时性保证的场景，比如强调（AP, Availability and Partition Tolerance）的应用。
本文将会介绍 IPFS 以及 IPFS Cluster 的原理，并且简述 https://github.com/loomts/ipfs-clsuter 的纠删码优化以及测试的细节。
IPFS
IPFS 是一个分布式文件系统，其最大的特点是内容寻址，能够将文件的 CID 作为索引，在世界各地获取文件的内容。
此文是分布式系统领域的经典论文，定义了分布式系统中事件的偏序关系，并且提出了一种分布式系统的时间同步算法。
在多进程通信时，独立的计算机也可能是分布式系统，换句话说，只要不同进程之间的通信时延不能忽略都可以算作分布式系统。
在分布式系统的运行过程中，事件的执行顺序非常重要，论文首先明确定义了事件的 happened before 关系，
进而阐明了事件的偏序关系（不叫全序的原因是有些事件不能以物理时钟的视角进行排序，可以看做是并行的，没有绝对的先后顺序），
为了实现对分布式系统中所有事件排序，又定义了全序关系，在偏序关系的基础上用进程的逻辑时钟对没有先后顺序的事件进行排序。
Reed-Solomon 是
目前工业界最常用的纠删码（Erasure Code）之一，本文主要讲述其在存储领域如何进行数据容错，并且附带简要实现思路。
Reed-Solomon 原理
Reed-Solomon 通过数据冗余实现容错，并且根据冗余数据的大小实现与其一致的容错。