可靠的分布式KV存储产品

目录

• Paxos
• Raft（Understandable Distributed Consensus）
  • 名词介绍
  • Leader Election
  • Log Replication
  • 请求完整流程
• etcd
  • 总体架构
  • API 介绍
  • 数据版本机制
  • 数据订阅
  • 数据存储
  • mini-transactions
  • 使用场景
• 参考

Paxos

官网：https://paxos.com/

Paxos算法是莱斯利·兰伯特于1990年提出的一种基于消息传递的一致性算法。

Raft（Understandable Distributed Consensus）

官网：https://raft.github.io/

论文：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

文档：https://etcd.io/docs/v3.5/

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：

• https://baike.baidu.com/item/Paxos 算法/10688635

Raft：

• https://zhuanlan.zhihu.com/p/32052223
• https://www.cnblogs.com/xybaby/p/10124083.html

etcd：

• https://www.zhihu.com/question/283164721/answer/1953060665
• https://www.cnblogs.com/yogoup/p/12020477.html
• https://edu.aliyun.com/roadmap/cloudnative