分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。从概念上说，将业务服务器和数据库部署在两台服务器上并通过 tcp 连接便组成了一个最简单的分布式系统。当然这样的分布式系统并没有研究的意义，我们研究分布式系统是为了解决实际问题：

是为了用廉价的、普通的机器完成单个计算机无法完成的计算、存储任务。通过多机备份避免单机故障通过增加或减少机器数量灵活调整系统的吞吐量

在本系列中我们已经提到过很多分布式存储系统了， 比如高可靠的 Etcd、ZooKeeper 前面提到的 TiDB 数据库。无论这些数据库看上去多么 fancy，他们基本的思路都是最朴素的技术 ——— 数据分片和副本。

数据分片

我们在「应对高并发」一文中提到过的分库分表便是数据分片思想最直观的展现：

数据分片的核心是分片策略，即如何决定一条数据应该放到哪一个分片中。

首先要决定根据哪个字段进行分片，我们将这个决定分片的字段称为分片键（partition key）， 在上图的示例中用户 ID 就是我们的分片键。

对于关系型数据库而言，通常在创建数据表时指定分片键，比如 Cassandra 和 TiDB 都需要在建表时指定分片键，对于 Redis 这类 KV 结构数据库来说只有一个 key 可以用来做分片键了。

CREATE TABLE articles (    id INT NOT NULL PRIMARY KEY,    uid INT,    title VARCHAR(60),    content TEXT,    create_time DATE NOT NULL DEFAULT '1970-01-01',)PARTITION BY HASH(uid) // TiDB 建表语句，按照 store_id 进行 hash 分区PARTITIONS 3;复制代码

决定分片键后，就需要将分片键映射到节点上。最简单的方法是通过哈希 hash(partition_key) % db_num， 还有一种常用的方法是号段法(Range)，即 partition key 1到1000 的在节点A、1000到2000的在节点 B……

哈希分片的好处在于数据均匀分布，单个节点的负载不会太大；而号段法则可能将一段时间内产生的数据都集中在一个分片上（特别是 partition key 为自增或由 snowflake 算法生成时），从另一个方面看某个时间段内的数据都集中在一个分片更便于进行范围查询或者统计分析，比如存储交易数据时就可以采用号段法。

麻烦才刚刚开始

再平衡

看上去数据分片就是把数据分散到多台机器上，但是分布式系统中的节点并不是固定的，有些节点会下线，有时候需要添加新的节点。 观察 node_id = hash(partition_key) % node_num 这个公式我们发现只要 node_num 发生变化, 几乎所有 partition_key 所属的 node_id 都会改变。

这意味着几乎所有数据都需要从一个节点搬到另一个节点，可想而知这样的数据迁移会消耗巨量的资源和时间，而且在迁移过程中的分片几乎是无法工作的。在分布式数据库领域我们把这种将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（rebalancing）。

为了缓解数据再平衡的压力，一致性哈希算法应运而生。一致性哈希不再使用取余的方法决定 node_id, 而是将整数空间连成一个环将 node_id 哈希后放在环上， partition_key 同样哈希后放到环上，从 partion_key 的位置开始沿着环顺时针行走遇到的第一个节点就是 partition_key 所属的节点。

这样环上的 node_id 将整个哈希空间分成了若干段，每次有节点加入只需要将原来的一段分成两段，有节点退出时只需要将两段合并成一段，极大的减少了 rebalancing 需要迁移的数据量。

跨节点查询

我们已经习惯了使用 SQL 来操作数据库，我们建立一个按班级分片的成绩表:

CREATE TABLE grades (    student_id INT NOT NULL PRIMARY KEY,    class_no INT,    score INT,)PARTITION BY HASH(class_no)PARTITIONS 20;复制代码

然后尝试查询全校前 10 名的学号:

select student_id from grades order by score desc limit 5 offset 5;复制代码

这里麻烦就麻烦就在分页器 limit 5 offset 5 上，全校第 10 名可能是自己班的第 1 名也有可能是自己班的第 10 名, 某个班可能没有一个学生是全校前 10 名，也有可能全校前 10 名都在同一个班中。

总之他们的分布完全随机，我们只能保证全校前 10 名一定是自己班级的前 10 名。 所以我们的解决方案是先把每个班的前 10 名都查出来，把他们混合在一起重新排序，在重新排序的表中找出全校第 5 到 10 名：

分布式事务

我们刚刚讨论了跨表查询在逻辑上的难点，然而与跨表写入相比，查询时小小逻辑问题可以说是微不足道了。

数据库作为一个并发系统，我们强烈依赖其事务机制提供的 ACID 保证。以经典的转账操作为例，事务机制要提供如下保证:

Atomicity 原子性：转账操作要么完成要么没有开始，不允许出现一方扣款另一方未收款的情况。Consistent 一致性：任何账户的余额都不应该为负数。Isolation 隔离性：其它事务不应该看到一方扣款另一方未收款的情况。Durability 持久性：转账操作一旦完成，对数据的修改就是永久的，即便系统故障也不会丢失。

在此例子中隔离性与原子性的表现类似，隔离性强调其它事务不应该看到执行了一半的状态，原子性强调执行过程不可分割、不可被其它操作插入

我们设计一个账户余额表并按照账户ID进行哈希分片, 若我们要对分布在不同节点（分库）上的两个账户进行转账，那应该如何操作呢？

第一种思路被称为 TCC (try-confirm-catch) 事务，TCC 事务分为三个阶段：

Try 阶段： 事务协调器要求参与方完成所有一致性检查然后预留并锁定事务所需资源；Confirm 阶段： 若所有参与方都表示资源充足可以提交，事务协调器会向所有参与方发出 Confirm 指令，要求实际执行事务。 Confirm 阶段只确认修改生效，不作任何业务检查，只使用Try阶段预留的资源，Cancel 阶段： 若 Try 或 Confirm 阶段任一参与者表示无法继续事务协调器会向所有参与方发出 Cancel 指令解锁预留资源并回滚事务。

由于 TCC 事务在 Try 阶段就进行了锁定，隔离性和一致性相对较好。同时由于锁定了资源会阻止其它事务进行，会损失一些吞吐量。

第二种实现思路的典型代表是 Saga 事务，Saga 事务将一个大事务拆分成多个有序的子事务，并且每个子事务都准备了撤销操作，事务协调器会顺序的执行子事务，如果某个步骤失败，则根据相反顺序一次执行一次撤销操作。

Saga 事务的问题显而易见，一是在实际执行前没有进行检查，有些子事务一旦执行便无法撤销；二是子事务提交之后便立刻生效，其它事务可以看到事务执行了一半的状态，隔离性比较差。

副本

我们开篇时提到使用分布式系统的目的之一是：通过多机备份提高系统的可靠性。在《应对高并发》一文中我们提到可以搭建从库一方面作为热备，另一方面做为读写分离缓解主库的的负载。

那么现在的问题是从库是如何主库保持同步的呢？通常主从同步由两个步骤组成：快照复制+日志传播。这里我们以 KV 结构的 Redis 进行说明。

数据库中所有的数据修改都是由写命令引起的，那么我们只要将主库收到的写命令按照原来的顺序发送到从库再次执行一遍就可以保持两者同步了：

从理论上说这么做没有问题，但是大多数情况下从库不是在主库启动后便一直跟随。若主库已经运行了一段时间并积累了相当规模的数据，此时再为其添加从库会有什么问题吗？

写命令的数据量十分巨大，保存和传输完整的写入日志是非常浪费资源和时间的做法。而且很多写命令是无用的，比如我们对一行记录进行了多次 update 最后将其删除，那么这行记录的 insert、update、delete 命令都不需要同步到从库。

所以在很多数据库的主从复制流程中主库会定期生成快照，当有新的从库加入时首先将快照发送给从库，然后将快照生成后日志持续复制到从库。如此便避免了保存和传输完整日志.

在分布式数据库中数据分片和从库（或者说是副本）通常结合使用。以 Redis 集群为例，数据通过一致性哈希算法分布在主节点上，每个主节点部署有若干个从节点。当集群发现某个主节点崩溃时便将它的一个从节点提升为主节点，代替崩溃的主节点继续工作:

在另外一些数据库中并没有主节点和从节点之分，而是在一个节点中存在着若干个主分片(primary partition)和从副本分片(replica partition)。当集群发现某个节点崩溃后，剩余的节点会挑选一个从分片接替主分片。Cassandra、ElasticSearch 等数据库均使用这种节点平等的架构。

在 redis 集群中从节点只负责写不负责读，这其实也是一种资源的浪费，虽然对于写入吞吐量超高的内存数据库来说这种浪费无伤大雅。但对于 Cassandra 这些需要持久化的数据库来说磁盘 IO 资源非常有限，所以每个节点都会承担部分写任务来提高系统整体的吞吐量。

副本带来的错误数据风险

虽然主节点将日志持续发送给从节点，但是网络传输和从节点执行日志中的命令是需要时间的，就是说从节点的数据和主节点并不完全一致，而可能是几十毫秒前的状态。

回顾一下上面讨论过的分布式事务，如果主节点刚刚提交了某个事务，在新数据同步到从节点前便崩溃了，在从节点被提升为主节点之后数据库中便出现了错误的数据：

谁是 Master？

在刚才我们对副本的讨论中提到当集群发现某个节点崩溃后会将从节点(副本)提升为主节点，这里的重点不在于「主节点是否崩溃」而是集群如何确认它已经崩溃。

分布式系统的节点之间通过网络进行通信，而网络是不可靠的。某个从节点发现主节点停止响应并不一定是主节点宕机，而可能是自己与主节点之间的网络中断了。若某个从节点认为原来的主节点宕机然后将自己提升为新主节点，那么集群中就会出现两个主节点。两个主节点各自写各自的数据，显而易见的会发生严重的数据冲突。我们将这种集群中出现多个主节点的故障称为「脑裂」：

因此进行主从切换的关键在于让所有节点对于主节点是否崩溃、应给提升哪个从节点作为新的主节点达成共识。（至于原来的主节点是否真的崩溃了并不重要，重要的是集群都认为它下线了。

Gossip 协议

Gossip 意为流言，它的原理也非常简单：每个节点定时将自己检测到的其它节点的状态在集群内广播，当某个节点收到过半节点广播了同一条消息时，它遍认为这条消息是真实的。

我们发现 Gossip 对网络节点的连通性和稳定性几乎没有任何要求；能够容忍网络上节点的随意地增加或者减少，随意地宕机或者重启，新增加或者重启的节点的状态最终会与其他节点同步达成一致。Gossip 把网络上所有节点都视为平等而普通的一员，没有任何中心化节点或者主节点的概念，这些特点使得 Gossip 具有极强的健壮性。

Gossip 的缺点同样显而易见，它需要经过数轮的广播才能让所有节点达成共识，在达成共识之前必然存在各节点认知不一致的情况。为了避免认知不一致造成脑裂进而出现数据错误，Redis 集群的 gossip 协议需要经过多轮协商才能选出新的主的节点, 在协商过程中故障主节点上的分片是无法进行写入的。

这个过程可以简单的分为下列几步：

疑似下线

某些节点发现主节点 A 停止响应，便将其标记为「疑似下线」状态， 并在随后的 Gossip 广播中通告疑似下线的消息。

下线判决

当一个节点收到过半节点通报的 “A 疑似下线” 消息后，便做出 A 已经下线的判决。A 下线的判决会尽快通过 Gossip 广播通知所有节点，收到 A 下线判决的节点会立即将 A 标记为下线，而不再关注 “A 疑似下线的消息”。这样做是为了减少达成共识所需的时间。

算法正常工作要求集群中不存在恶意节点，节点可能因为自身视角原因无法做出判断但不会故意发出错误信息。因此任意一个节点都可以做出下线判决。

新主节点选举

从节点在收到其主节点的下线判决时会等待一段时间，然后向集群广播一条请求消息，请求所有收到这条消息并且具有投票权的主节点给自己投票。

这段等待时长根据下面的公式决定：

500ms + random()%500ms + rank*1000ms复制代码

其中，固定延时 500 ms 是为了确保下线判决能传播到集群中其他节点；随机延时为了避免两个从节点同时拉票造成最终无人得票过半，不得不进行下一轮投票。

选举算法的目标是尽快选出新的主节点，至于谁当选并不重要。

rank 是拉票的从节点在下线主节点的所有从节点中的排名，排名根据主从同步进程而定，数据越新（和主节点数据最为接近）的从节点当选新主节点的概率越高

确认选举结果

若某一个从节点收到了过半的选票，则会当选为新一任主节点，若一轮投票结束没有从节点选票过半则进入下一次投票。

要求选票过半才能当选而不是只要得票最高就可以直接当选，是因为集群中最多有一个节点能获得过半选票，这样设计彻底封死了脑裂的可能。

选举完成后新当选的从节点会将自身切换为主节点模式，原主节点的其它从节点会与新主节点建立连接。至此集群从故障中恢复。

Redis Cluster、Consul 和 Cassandra 都是使用 Gossip 协议的知名软件。

Raft 协议

与去中心化的 Gossip 协议相对，Raft 协议是一种中心化的分布式共识协议。Raft 集群中的每个节点可能处于 Leader、Follower、Candidate 三种状态之一。Raft 协议有 Leader Selection（领导节点选举） 和 Log Replication （日志复制）两部分组成。

Raft 集群中最多有一个 Leader, 集群中所有写入操作都由 Leader 负责。 一次写入的过程是这样的：

客户端将更改提交给 Leader, Leader 会在自己的日志中写入一条未提交的记录(Entry)在下一次心跳时 Leader 会将更改发送给所有 Follower一旦收到过半节点的确认 Leader 就会提交自己日志中的记录并向客户端返回写入成功Leader 会在下一次心跳时通知所有节点提交日志

这个过程我们称为日志复制。由于在日志复制到过半节点后才返回成功，所以即使主节点返回成功后宕机某个 Follower 成为新的主节点，它也可以通过自己的日志恢复这条数据。

Leader 会定时向 Follower 广播心跳包，在集群运行过程任何一个 Follower 出现心跳超时都会引发新一轮选举。Raft 的选举策略和我们刚刚介绍的 Redis 集群的选举策略可以说是一模一样。

当 Follower 发现 Leader 超时便会随机等待一段时间，然后转变为 Candidate 向其它节点发送拉票信息。收到拉票请求的其它 Follower 会根据投票轮数、自己是否已经投票、Candidate 的日志条数来决定投票给谁。当一个 Candidate 获得超过半数的选票后便会成为新任的 Leader.

The Secret Lives of Data-CN 以图文方式介绍 Raft 算法，是非常好的入门材料。将其阅读完后您应该已经了解了 Raft 算法。

如果您还有疑惑 Raft Scope 是 Raft 官方提供的互动式演示程序，它展示了 Raft 集群的工作状态。您可以用它模拟节点宕机、心跳超时等各种情况。有了 Raft Scope 我们可以亲自“动手” 观察 Raft 集群是如何工作、如何处理各种故障的。Raft Scope 缺少说明，若在使用中遇到困难您可以阅读这篇说明：看动画轻松学会 Raft 算法。

Multi Raft

与 Gossip 通常只用来同步宕机、主从切换等集群元信息不同，Raft 协议不仅负责 Leader 选举也规定了如何将数据同步到副本定义了一个完善的分布式存储模型。

一个 Raft 组中只有一个 Leader 可以处理写请求，我们在数据分片一节中提到这样做比较浪费资源。解决方案也比较类似，将集群划分成多个 Raft 组，并且尽量让每个 Raft 组的 Leader 分布在不同的节点上。

ZooKeeper、Etcd 等分布式配置中心由于一致性要求较高，吞吐量要求较低通常采用单 Raft 实现，而 TiDB 这类高一致性的数据库则通常使用 Multi Raft.

总结

分布式数据库将数据划分为多个分片存储在多台机器上， 采用分而治之的思路处理单机数据库存储不了、处理不完的数据。在进行数据分片之后我们发现读写都出现了额外的额外的麻烦，比如很难继续维持事务的 ACID 特性。为此我们尝试通过 Try-Confirm-Catch 或者 Saga 算法来在分布式数据库中保持事务的原子性。

单台服务器总会故障，因此我们为数据配置了副本，以便在主节点故障时将副本提升为新的主节点维持系统的正常工作。此时我们发现由于网络不可靠，集群难以就某个节点是否宕机达成共识。我们为解决分布式共识问题引入 Gossip 和 Raft 两个算法。

Gossip 算法通过广播的方式将集群的最新状态通知到每个节点，Gossip 对网络质量几乎没有要求也没有中心节点，健壮性比较好。但由于需要几轮广播才能在集群中达成共识，中间不可避免的存在不一致的状态。所以我们需要在上层构建相应的策略通过多轮广播来避免不一致状态造成数据错误。

Raft 算法则是中心化的分布式一致性解决方案，它巧妙的通过随机延时的方法来进行 Leader 选举，这种选举方式也被 Redis Cluster 等使用 Gossip 协议的分布式系统使用。Raft 不仅定义了如何选举 leader， 也定义了如何将数据变更同步到副本，以在主从切换后保证不丢失数据。

原文链接：