Paxos
Paxos算法是莱斯利·兰伯特于1990年提出的一种基于消息传递的一致性算法。
Raft（Understandable Distributed Consensus）
论文：https://raft.github.io/raft.pdf
算法演示网址：http://thesecretlivesofdata.com/raft/
Raft是一种共识算法，旨在替代Paxos。
它通过逻辑分离比Paxos更容易理解，但它也被正式证明是安全的，并提供了一些额外的功能。
Raft提供了一种在计算系统集群中 分布状态机 的通用方法，确保集群中的每个节点都同意一系列相同的状态转换。
问题分解
问题分解是将 “复制集中节点一致性" 这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。
在raft，子问题包括，leader election， log replication，safety，membership changes。
状态简化
对算法做出一些限制，减少需要考虑的状态数，使得算法更加清晰。
raft会先选举出leader，leader完全负责replicated log的管理。
leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。
名词介绍
Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）、候选人（Candidate）以及term（ Raft算法将时间分为一个个的任期）。
Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。
Raft算法角色状态转换如下：
Leader Election
Raft 使用 heartbeat 触发 Leader 选举。
当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。
如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。
Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送RequestVote RPC 。
结果有以下三种情况：
- 收到majority的投票（含自己的一票），则赢得选举，成为leader。
赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。
投票者的视角，投票者如何决定是否给一个选举请求投票呢，有以下约束：
- 在任一任期内，单个节点最多只能投一票。
- 候选人知道的信息不能比自己的少（log replication和safety）。
- first-come-first-served 先来先得。
-
被告知别人已当选，那么自行切换到follower。
-
一段时间内没有收到majority投票，则保持candidate状态，重新发出选举。
平票 split vote 的情况。超时后重新发起选举。
如果出现平票的情况，那么就延长了系统不可用的时间（没有leader是不能处理客户端写请求的），
因此raft引入了randomized election timeouts来尽量避免平票情况。
同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。
Log Replication
有了leader，系统应该进入对外工作期了。
客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。
将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。
为什么是日志？
如何保证所有节点 get the same inputs in the same order，使用replicated log是一个很不错的注意。
log具有持久化、保序的特点，是大多数分布式系统的基石。
Replicated state machines
共识算法的实现一般是基于复制状态机（Replicated state machines），
何为复制状态机：相同的初识状态 + 相同的输入 = 相同的结束状态。
因此，可以这么说，在raft中，leader将客户端请求（command）封装到一个个log entry，将这些log entries复制到所有follower节点，然后大家按相同顺序应用log entry中的command，则状态肯定是一致的。
下图展示了这种log-based replicated state machine
请求完整流程
当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤：
- leader append log entry
- leader issue AppendEntries RPC in parallel
- leader wait for majority response
- leader apply entry to state machine
- leader reply to client
- leader notify follower apply log
leader只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。
logs由顺序编号的log entry组成 ，每个log entry除了包含command，还包含产生该log entry时的leader term。
raft算法为了保证高可用，并不是强一致性，而是最终一致性。
leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。
在上面的流程中，leader只需要日志被复制到大多数节点即可向客户端返回，一旦向客户端返回成功消息，那么系统就必须保证log（其实是log所包含的command）在任何异常的情况下都不会发生回滚。
commit（committed）是指日志被复制到了大多数节点后日志的状态
apply(applied) 是节点将日志应用到状态机，真正影响到节点状态。
…………
etcd
etcd 是 CoreOS 团队发起的开源项目，目标是构建一个高可用的分布式键值(key-value)数据库。
etcd 内部采用raft协议作为一致性算法，etcd 基于 Go 语言实现。
总体架构
Blotddb：BoltDB是相当出名的纯Go实现的KV读写引擎。
Wal： WAL(Write Ahead Log)预写日志，是数据库系统中常见的一种手段，用于保证数据操作的原子性和持久性。
Snapshot：磁盘快照 (Snapshot)是针对整个磁盘卷册进行快速的档案系统备份。
在 etcd 架构中，有一个关键的概念叫做 quorum，quorum 的定义是 （n+1）/2，也就是说超过集群中半数节点组成的一个团体。
3个节点容忍1个故障，5个节点容忍2个故障。
允许部分节点故障之后继续提供服务，怎么解决分布式一致性？
分布式一致性算法由 Raft 一致性算法完成。
-
任意两个 quorum 的成员之间一定会有一个交集（公共成员），也就是说只要有任意一个 quorum 存活，其中一定存在某一个节点（公共成员），它包含着集群中所有的被确认提交的数据。
-
基于这一原理，Raft 一致性算法设计了一套数据同步机制，在 Leader 任期切换后能够重新同步上一个quorum 被提交的所有数据，从而保证整个集群状态向前推进的过程中保持数据的一致。
怎样获取数据呢？
- 通过 etcd 提供的客户端去访问集群的数据。
- 直接通过 http 的方式（类似 curl 命令）直接访问 etcd。
- 在 etcd 内部，把 etcd 的数据存储理解为一个有序的 map，它存储着 key-value 数据。
- etcd 支持订阅数据的变更，提供 watch 机制，通过 watch 实时地拿到 etcd 中数据的增量更新，从而实现与etcd 中的数据同步等业务逻辑。
API 介绍
API文档： https://github.com/coreos/etcd/blob/6acb3d67fbe131b3b2d5d010e00ec80182be4628/Documentation
配置项：https://github.com/coreos/etcd/blob/master/Documentation/op-guide/configuration.md
大致分为五组：
- 第一组是 Put 与 Delete。类似Map的使用。
- 第二组是查询操作：
- 第一种是指定单个 key 的查询。
- 第二种是指定的一个 key 的范围。
- 第三组是数据订阅：
- Watch 支持指定单个 key。
- 指定一个 key 的前缀，在实际应用场景中的通常会采用第二种形势；
- 第四组事务操作。etcd 提供了一个简单的事务支持，类似于代码中的 if else 语句，etcd 确保整个操作的原子性。
- 第五组是 Leases 接口。
分布式系统理论之租约机制
在分布式系统中，往往会有一个中心服务器节点。
该节点负责存储、维护系统中的元数据。
如果系统中的各种操作都依赖于中心服务器上的元数据，那么中心服务器很容易成为性能瓶颈及存在单点故障。
而通过租约机制，可以将中心服务器的“权力”下放给其他机器，就可以减轻中心服务器的压力。
数据版本机制
要正确使用 etcd 的 API，必须要知道内部对应数据版本号的基本原理。
term：代表的是整个集群 Leader 的任期。
revision：代表的是全局数据的版本。
在集群中跨 Leader 任期之间，revision 都会保持全局单调递增。
正是 revision 的这一特性，使得集群中任意一次的修改都对应着一个唯一的 revision，
因此我们可以通过 revision 来支持数据的 MVCC，也可以支持数据的 Watch。
MVVC (Multi-Version Concurrency Control)
MVCC是为了实现事务的隔离性，通过版本号，避免同一数据在不同事务间的竞争，
可以把它当成基于多版本号的一种乐观锁。
当然，这种乐观锁只在事务级别提交读和可重复读有效。
MVCC最大的好处，相信也是耳熟能详：读不加锁，读写不冲突。
在读多写少的OLTP应用中，读写不冲突是非常重要的，极大的增加了系统的并发性能。
对于每一个 KeyValue 数据节点，etcd 中都记录了三个版本：
- 第一个版本叫做 create_revision，是 KeyValue 在创建时对应的 revision。
- 第二个叫做 mod_revision，是其数据被操作的时候对应的 revision。
- 第三个 version 就是一个计数器，代表了 KeyValue 被修改了多少次。
数据订阅
使用 etcd 多版本号来实现并发控制以及数据订阅（Watch）。
- 支持对同一个 Key 发起多次数据修改，每次数据修改都对应一个版本号。
- 在查询数据的时候如果不指定版本号，etcd 会返回 Key 对应的最新版本.
- etcd 支持指定一个版本号来查询历史数据。
数据存储
etcd 中所有的数据都存储在一个 b+tree 中（灰色），该 b+tree 保存在磁盘中，并通过 mmap 的方式映射到内存用来支持快速的访问。
灰色的 b+tree 中维护着 revision 到 value 的映射关系，支持通过 revision 查询对应的数据。
revision 是单调递增的，通过 watch 来订阅指定 revision 之后的数据时，仅订阅该 b+ tree 的数据变化即可。
在 etcd 内部还维护着另外一个 btree（蓝色），它管理着 key 到 revision 的映射关系。当客户端使用 key 查询数据时，首先需要经过蓝色的 btree 将 key 转化为对应的 revision，再通过灰色的 btree 查询到对应的数据。
问题
etcd 将每一次修改都记录下来会导致数据持续增长。
这会带来内存及磁盘的空间消耗，同时也会影响 b+tree 的查询效率。
为了解决这一问题，在 etcd 中会运行一个周期性的 Compaction 的机制来清理历史数据，将一段时间之前的同一个 Key 的多个历史版本数据清理掉。
最终的结果是灰色的 b+tree 依旧保持单调递增，但可能会出现一些空洞。
mini-transactions
etcd 的 事务机制比较简单，基本可以理解为一段 if-else 程序。
在 etcd 内部会保证整个事务操作的原子性。
使用场景
- 元数据存储
- Server Discovery （Naming Service）
- Distributed Coordination: leader election
- Distributed Coordination 分布式系统并发控制
参考
Paxos：
Raft：
etcd：
- https://www.zhihu.com/question/283164721/answer/1953060665
- https://www.cnblogs.com/yogoup/p/12020477.html
- https://edu.aliyun.com/roadmap/cloudnative
__EOF__
