TIDB 架构及分布式协议Paxos和Raft对比

近来newsql大热，尤以TIDB最火，pingcap不断打磨TiDB，现如今版本已经迭代到3.0，产品已经基本趋于成熟。
对于TiDB，整体架构图如下图所示

是由四个模块组成，TiDB Server，PD Server，TiKV Server，TiSpark。

• TiDB Server负责接受SQL请求，处理SQL的相关逻辑，并通过PD找到存储计算所需数据的TiKV地址，与TiKV交互获取数据，最终返回结果。TiDB Server是无状态的，其本身并不存储数据，只负责计算，可以无限水平扩展，可以通过负载均衡组件（如LVD，HAPROXY，F5等）对外提供统一的接入地址。推荐部署俩个实例，前端通过负载均衡组件对外提供服务，当单个实例失效时，会影响正在这个实例上进行的session，从应用的角度看，会出现单次请求失败的情况，重新连接后即可继续获得服务。
• Placement Driver (简称 PD)，是整个集群的管理模块，其主要的工作有三个，一是存储集群的元信息，（某个Key存储在哪个TiKV节点上）；二是对TiKV集群进行调度和负载均衡（如数据的迁移，Raft group leader的迁移等），三是分配全局唯一且递增的事务ID。PD 通过 Raft 协议保证数据的安全性。Raft 的 leader server 负责处理所有操作，其余的 PD server 仅用于保证高可用。单个实例失效时，如果这个实例不是 Raft 的 leader，那么服务完全不受影响；如果这个实例是 Raft 的 leader，会重新选出新的 Raft leader，自动恢复服务。PD 在选举的过程中无法对外提供服务，这个时间大约是3秒钟。推荐至少部署三个 PD 实例。
• TiKV Server 负责存储数据，从外部看 TiKV 是一个分布式的提供事务的 Key-Value 存储引擎。存储数据的基本单位是 Region，每个 Region 负责存储一个 Key Range（从 StartKey 到 EndKey 的左闭右开区间）的数据，每个 TiKV 节点会负责多个 Region。TiKV 使用 Raft 协议做复制，保持数据的一致性和容灾。副本以 Region 为单位进行管理，不同节点上的多个 Region 构成一个 Raft Group，互为副本。数据在多个 TiKV 之间的负载均衡由 PD 调度，这里也是以 Region 为单位进行调度。TiKV 是一个集群，通过 Raft 协议保持数据的一致性（副本数量可配置，默认保存三副本），并通过 PD 做负载均衡调度。单个节点失效时，会影响这个节点上存储的所有 Region。对于 Region 中的 Leader 结点，会中断服务，等待重新选举；对于 Region 中的 Follower 节点，不会影响服务。当某个 TiKV 节点失效，并且在一段时间内（默认 30 分钟）无法恢复，PD 会将其上的数据迁移到其他的 TiKV 节点上。
• TiSpark作为 TiDB 中解决用户复杂 OLAP 需求的主要组件，将 Spark SQL 直接运行在 TiDB 存储层上，同时融合 TiKV 分布式集群的优势，并融入大数据社区生态。至此，TiDB 可以通过一套系统，同时支持 OLTP 与 OLAP，免除用户数据同步的IO损耗。

分布式协议Paxos和Raft
算法演进过程

Paxos

Paxos算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法。由于算法难以理解，起初并没有引起大家的重视，Lamport在1998年将论文重新发表到TOCS上，即便如此Paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述。

06年Google发布了三篇论文，其中在Chubby锁服务使用Paxos作为Chubby Cell中的一致性算法，Paxos的人气从此一路狂飙。

基于Paxos协议的数据同步与传统主备方式最大的区别在于：Paxos只需超过半数的副本在线且相互通信正常，就可以保证服务的持续可用，且数据不丢失。

Basic-Paxos

Basic-Paxos解决的问题：在一个分布式系统中，如何就一个提案达成一致。

需要借助两阶段提交实现：

Prepare阶段：

Proposer选择一个提案编号n并将prepare请求发送给 Acceptor。
Acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息，则Acceptor将自己上次接受的提案回复给Proposer，并承诺不再回复小于n的提案。

Accept阶段：

当一个Proposer收到了多数Acceptor对prepare的回复后，就进入批准阶段。它要向回复prepare请求的Acceptor发送accept请求，包括编号n和根据prepare阶段决定的value（如果根据prepare没有已经接受的value，那么它可以自由决定value）。
在不违背自己向其他Proposer的承诺的前提下，Acceptor收到accept请求后即接受这个请求。

Mulit-Paxos

Mulit-Paxos解决的问题：在一个分布式系统中，如何就一批提案达成一致。

当存在一批提案时，用Basic-Paxos一个一个决议当然也可以，但是每个提案都经历两阶段提交，显然效率不高。Basic-Paxos协议的执行流程针对每个提案（每条redo log）都至少存在三次网络交互：1. 产生log ID；2. prepare阶段；3. accept阶段。

所以，Mulit-Paxos基于Basic-Paxos做了优化，在Paxos集群中利用Paxos协议选举出唯一的leader，在leader有效期内所有的议案都只能由leader发起。

这里强化了协议的假设：即leader有效期内不会有其他server提出的议案。因此，对于后续的提案，我们可以简化掉产生log ID阶段和Prepare阶段，而是由唯一的leader产生log ID，然后直接执行Accept，得到多数派确认即表示提案达成一致（每条redo log可对应一个提案）。

相关产品

X-DB、OceanBase、Spanner都是使用Multi-Paxos来保障数据一致性。

MySQL Group Replication的xcom中也使用了Multi-Paxos。

PaxosStore

PaxosStore是腾讯WXG基于Paxos实现的分布式一致性中间件，在微信的用户账号管理、用户关系管理、即使消息、社交网络、在线支付等场景中广泛应用。

Raft

Raft是斯坦福大学的Diego Ongaro、John Ousterhout两个人以易理解为目标设计的一致性算法，在2013年发布了论文：《In Search of an Understandable Consensus Algorithm》。从2013年发布到现在，已经有了十几种语言的Raft算法实现框架，较为出名的有etcd，Google的Kubernetes也是用了etcd作为他的服务发现框架。

与Paxos相比，Raft强调的是易理解、易实现，Raft和Paxos一样只要保证超过半数的节点正常就能够提供服务。

众所周知，当问题较为复杂时，可以把问题分解为几个小问题来处理，Raft也使用了分而治之的思想，把算法分为三个子问题：

选举（Leader election）
日志复制（Log replication）
安全性（Safety）

分解后，整个raft算法变得易理解、易论证、易实现。

相关产品

etcd使用Raft来保障数据一致性。

Mulit-Raft

许多NewSQL数据库的数据规模上限都定位在100TB以上，为了负载均衡，都会对数据进行分片（sharding），所以就需要使用多个Raft集群（即Multi-Raft），每个Raft集群对应一个分片。

在多个Raft集群间可增加协同来减少资源开销、提升性能（如：共享通信链接、合并消息等）。

相关产品

TiDB、CockroachDB、PolarDB都是使用Mulit-Raft来保障数据一致性。

Raft和Multi-Paxos的区别

Raft是基于对Multi-Paxos的两个限制形成的：

发送的请求的是连续的, 也就是说Raft的append 操作必须是连续的， 而Paxos可以并发 (这里并发只是append log的并发, 应用到状态机还是有序的)。
Raft选主有限制,必须包含最新、最全日志的节点才能被选为leader. 而Multi-Paxos没有这个限制，日志不完备的节点也能成为leader。

Raft可以看成是简化版的Multi-Paxos。

Multi-Paxos允许并发的写log,当leader节点故障后，剩余节点有可能都有日志空洞。所以选出新leader后, 需要将新leader里没有的log补全,在依次应用到状态机里。

Raft选举过程
Raft协议中，一个节点有三个状态：Leader、Follower和Candidate，但同一时刻只能处于其中一种状态。Raft选举实际是指选举Leader，选举是由候选者（Candidate）主动发起，而不是由其它第三者。

并且约束只有Leader才能接受写和读请求，只有Candidate才能发起选举。如果一个Follower和它的Leader失联（失联时长超过一个Term），则它自动转为Candidate，并发起选举。

发起选举的目的是Candidate请求（Request）其它所有节点投票给自己，如果Candidate获得多数节点（a majority of nodes）的投票（Votes），则自动成为Leader，这个过程即叫Leader选举。

在Raft协议中，正常情况下Leader会周期性（不能大于Term）的向所有节点发送AppendEntries RPC，以维持它的Leader地位。

相应的，如果一个Follower在一个Term内没有接收到Leader发来的AppendEntries RPC，则它在延迟随机时间（150ms~300ms）后，即向所有其它节点发起选举。

采取随机时间的目的是避免多个Followers同时发起选举，而同时发起选举容易导致所有Candidates都未能获得多数Followers的投票（脑裂，比如各获得了一半的投票，谁也不占多数，导致选举无效需重选），因而延迟随机时间可以提高一次选举的成功性。