可靠的分布式KV存储产品-ETCD-初见

Paxos

官网://paxos.com/

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

Raft(Understandable Distributed Consensus)

官网://raft.github.io/

论文://raft.github.io/raft.pdf

算法演示网址://thesecretlivesofdata.com/raft/

Raft是一种共识算法,旨在替代Paxos。

它通过逻辑分离比Paxos更容易理解,但它也被正式证明是安全的,并提供了一些额外的功能。

Raft提供了一种在计算系统集群中 分布状态机 的通用方法,确保集群中的每个节点都同意一系列相同的状态转换。

问题分解

问题分解是将 “复制集中节点一致性” 这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。

在raft,子问题包括,leader electionlog replicationsafetymembership 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.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文档: //github.com/coreos/etcd/blob/6acb3d67fbe131b3b2d5d010e00ec80182be4628/Documentation

配置项://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: