设计数据密集型应用 —— 副本

数据分布式存储

我们已经介绍了单个机器节点处理数据的相关知识，在大数据场景，单机节点已经无法满足业务需求，接下来我们学习分布式数据处理的相关知识。

原因

采用分布式数据处理的原因:

• 可扩展性(Scalability)。当数据点读负载或者写负载超出单机处理能力的时候，可以将读写负载分布到多台机器上。
• 高可用(Fault tolerance/high availability)。当某个机器节点出现问题无法继续提供服务的时候，可以将请求路由到其他节点，从而使整体服务不受影响。
• 低延时(Low latency)。可以将机器部署在世界各地的不同机房，当不同地区的用户访问时，选择就近的机器提供服务，减少服务的延时。

副本和分区

副本(Replication)和分区(Partitioning,也称作Sharding)是数据分布式存储的两种方式:

• 副本。将同一数据复制多份，分布存储到不同的机器节点。副本提供了冗余性，如果部分节点失效了，可以通过其他节点上的副本继续提供服务。
• 分区。将大数据库切分成多个子集，每个子集分布存储到不同的机器节点。分区解决了单个节点容量不足的问题。

在实际的大数据处理场景中，副本和分区通常被结合使用。下图是一个被切分成两个分区，每个分区存储两个副本的示例:

本章我们先来介绍一下副本的相关原理。

副本

如果数据是永远不变的，那么副本的实现将会非常简单 ———— 将数据复制到各个节点即可。在分布式系统中，副本实现的主要技术挑战，在于数据不断变化的过程中，在节点之间实现数据同步。

主流的副本模式有三种:单主(single-leader)模式、多主(multi-leader)模式、无主(leaderless)模式。现实场景中，有很多的实现细节需要考量，比如是采用同步还是异步的方式更新副本，如何处理出错的副本。

单主模式

存储在节点中的数据备份被称作副本，副本需要解决的核心问题是:集群中发生一次写入操作之后，如何保证所有副本中的数据都是一致的？

最常见的解决方案是基于主从节点(leader-based replication)的复制，具体步骤如下:

• 首先在集群中确定一个主节点，客户端的任何写入操作，首先将数据发送到主节点，写入主节点的本地存储。
• 主节点的数据变更，通过日志(replication log)或者数据流(change stream)的形式，发送给所有的从节点。
• 从节点在本地执行这些变更，从而保证和主节点数据的一致性。

对于客户端来说，数据既可以访问主节点，也可以访问从节点。但是写入数据只能是访问主节点。

在主流的关系数据库比如PostgreSQL、MySQL、Oracle、SQL Server中，非关系型数据库MongoDB，以及消息中间件Kafka、RabbitMQ，都采用了这种基于主从节点的副本复制模式。

同步与异步复制

副本的写入操作采用同步还是异步的方式，是一个需要重点关注的细节。

举一个例子，社交网站上的某位用户，执行了更新头像的操作:

• 从节点1(Follower1)的复制被配置为同步方式:主节点的数据变更，发送到从节点1之后，需要等待从节点1返回写入成功的响应。
• 从节点2(Follower2)的复制被配置为异步方式:主节点的数据变更，发送到从节点2，但是不需要等待从节点2的执行结果。

同步复制的优势在于，可以保证从节点的数据和主节点是强一致的，就算主节点挂了，我们也可以在从节点读到最新的数据。同步复制的劣势在于，如果从节点挂了或者发生了网络延迟，响应不能及时返回，主节点就需要一直等待，整个集群的写入操作就会被阻塞。

在实际的生产集群中，把所有从节点的配置为同步复制模式是不现实的，任何一个从节点发生问题都会造成集群的写入操作阻塞。

实际常常使用一种半同步(semi-synchronous)的方式:将一个从节点配置为同步复制模式，其他从节点配置为异步复制，这样就可以保证集群中至少有两个节点存储了最新数据。当同步模式的从节点不能及时返回数据时，从其他的异步从节点选择一个，切换到同步模式。

实际生产集群中还常常把所有的从节点都配置为异步复制模式。优势在于就是集群中所有的从节点都发生了延迟，也不会阻塞主节点的写入操作。缺陷在于当主节点fail over的时候，部分已写入数据可能会丢失。

处理节点服务中断

分布式系统中的每一个节点都有可能发生服务中断，可能是由于机器重启，也可能是由于系统维护。如何让集群的整体服务，免于个别节点服务中断的影响，以实现整体的高可用呢？

从节点失败

从节点失败之后的错误恢复相对简单：

1. 每个从节点在本地磁盘记录已经成功执行的变更日志。
2. 当从节点从失败中恢复之后，会重新连接上主节点。基于本地记录的上一次成功操作的点位，拉取失败期间，需要执行的变更。
3. 从节点重新执行这些变更，从而追上(Catch-up)主节点。

主节点失败

主节点失败之后的恢复过程相对复杂一些，整个过程被称作failover：

1. 确定主节点已经失败。集群可以依据一些标准，来判断出主节点确实已经失败了，比如30秒没有收到主节点的心跳信息，以便启动failover过程。
2. 在集群的其他从节点中，选举出一个新的主节点。这步可以通过领导者选举算法(比如Paxos)来实现。
3. 重新配置系统使主节点生效。

主节点恢复需要考虑几个问题:

• 如果集群采用的是异步模式，那么在主节点failover的时候，集群中可能会出现数据丢失，因为可能每个从节点都存在数据落后的情况。
• 当之前挂掉的主节点，重新连入集群的时候，可能会错误地认为自己仍然是主节点，整个集群中就会同时存在两个主节点，发生脑裂(brain split)的情况，导致整个集群无法正常运转。

节点失败、不可靠的网络、可用性和一致性之间的权衡、数据延迟等待问题，是分布式系统设计中绕不开的话题。

副本复制的实现

在单个主节点的集群中，副本复制可以有多种实现方式：

基于执行语句的复制

这是最容易想到的实现方式，把主节点上执行的数据修改相关语句(INSERT、UPDATE、DELETE)，在从节点上也执行一次，这样从节点就可以和主节点保持一致。

线上场景中可能会遇到以下问题:

• 某些没有确定结果的操作，比如NOW(),RAND()，在从节点执行的时候结果和主节点不一致。
• 如果语句的执行结果受已有的数据影响，比如UPDATE ... WHERE <some condition>，那么从节点上就需要按照和主节点完全一样的顺序来执行这些语句，这在并发更新的场景并不容易实现。

在MySQL5.1之前的版本，副本复制采用的是基于执行语句的模式，由于上面提到的种种问题，新版的MySQL已经废弃了这种方式。

基于Write-ahead log的复制

上一章讲数据库存储引擎实现的时候，我们提到了Write-ahead log(WAL)，副本复制也可以使用WAL。

WAL中包含了包含所有写入结果信息的字节序列，从节点接受主节点点发送的WAL并执行，构建和主节点完全一致的数据结果。

PostgresSQL和Oracle使用了这种副本复制方式。WAL方式的主要劣势在于，它描述的是磁盘区块的字节变动信息，偏底层，无法兼容不同版本的数据库实现。

基于逻辑日志的复制

另一种实现副本复制的方式是采用与存储引擎无关的逻辑日志，以数据行为粒度来描述数据更新的结果:

• 对于插入操作，逻辑日志包含所有列的新值。
• 对于删除操作，逻辑日志中包含需要删除的数据行的唯一标识。(通常是主键)
• 对于更新操作，逻辑日志包含被更新行的相关列的所有数据。

对于更新了多行数据的事务操作，逻辑日志中加入一条额外记录来标识事务提交信息。Mysql的binlog就采用了这种方式。

逻辑日志让副本复制与存储引擎解耦，不受存储引擎内部实现方式的约束，还可以用来把数据变更同步到外部系统，比如OLAP数据分析引擎。

复制延迟的问题

在分布式系统中，当处理大部分都是读请求的场景时，通过增加从节点数量来实现负载均衡，并提高集群的吞吐能力，是十分有效的。

这种读扩展(read-scaling)架构，需要使用异步复制模式，以避免单个节点失败阻塞整个集群。在异步复制模式下，数据复制延迟是一个无法避免的问题，从节点和主节点之间的数据并没有强一致性保障，只能保证最终一致性(eventual consistency)，但是最终是何时，就像永远是多远一样，是一个并不确定的保证。

理论上可以通过分布式事务来实现集群中节点之间的强一致性，但是分布式事务在现实世界中困难重重，这里就不详细展开了。

无主模式

上文描述的是基于单个主节点(single-leader)的副本复制模式，也有一些其他的系统采用了无主节点(leaderless)的模式，比如亚马逊著名的Dynamo，以及开源的Cassandra、Riak，都采用了无主模式，集群中的任意一个节点都可以从客户端接收写入操作。

一个节点挂掉

首先我们来一个最简单的场景，假设一个采用无主模式的数据库集群，由3个副本节点构成，其中的一个节点挂了。当客户端同时这3个节点发送写请求的时候，会发生什么呢？

和单主节点模式不同的是，由于无主模式场景中不存在主节点，所以不需要通过failover操作来重新选出主节点。

客户端向3个节点发出写请求之后，由于有一个从节点挂了，剩余的两个从节点会返回ok，数据库集群认为本次写入操作已经成功。

当挂掉的节点重新连上集群之后，客户端同时从多个节点读取数据时，就可以根据版本号(version number)，发现重新连入节点的数据是过期(stale)的，为了实现数据最终一致性的目标，集群会采用以下两种方式:

• 读修复
  • 读操作发现过期数据之后，会额外发起一次写操作，让过期数据追上最新版本的数据。比如上图的示例中，客户端同时读到了版本6和版本7的数据，那么会重新发起一次写请求将节点3上面的数据更新到版本7。
• 后台整理
  • 除了读修复之外，某些数据存储系统还会在后台启动一个进程，持续扫描各个副本之间的数据差异，更新落后的数据。

法定数目(Quorum)

在上图的场景中，当向3个副本同时发送写请求之后，只要其中的两个副本返回OK，我们就认为写入成功了。那么在后续的读取中，需要同时读取多少个副本，才能保证可以读到最新版本的数据呢？

两个副本返回OK，只有一个副本上的节点数据是过期的，所以后续读取的时候，从2个副本中读取数据，就能确保能够读取到最新版本的数据。

就像选举需要达到法定票数才能通过一样，读写副本的数量也需要达到一个法定数目，才能确保能够读取到最新版本的数据。

在通用的场景，假设集群中有n个副本，每次写操作需要w个节点确认ok，每次读操作需要获取r个节点的数据，那么当满足w + r > n时，结合版本号信息，就能确保读到最新的数据。

在实际场景中，参数n、w、r通常都是可以配置的。机器数量n通常被设置为奇数，w、r通常配置为w=r=(n+1)/2。

处理并发写入

无主模式允许多个客户端同时向不同的节点写入数据，那么不可避免地会遇到并发问题，如果没有恰当处理的话，整个集群就会陷入数据不一致的状态。

以下图为例:

• 节点1收到了客户端A的写入请求，但由于网络原因为未收到客户端B的写入请求。
• 节点2首先收到了客户端A的写入请求，然后又收到了客户端B的写入请求。
• 节点3首先收到了客户端B的写入请求，然后又收到了客户端A的写入请求。

如果简单地采用覆盖式写入算法的话，节点1和节点3会认为X的最终值是A，节点2会认为X的最终值是B，整个集群就会陷入数据不一致的状态。

所以简单的覆盖式写入算法不可行，我们需要找到合适的算法来解决并发写入的问题。

采纳最新一次写入

一种简单的方案，是在并发写入的场景中，采纳最新一次写入(Last write wins, LWW)。

这要求集群中所有节点对什么是最新一次写入，达成一致共识。一种可行的策略是在每次写入操作中，基于事件发生时间(Event Time)打上时间戳。在发生并发写入的时候，只保留最新时间戳的数据。

LWW可以实现最终一致性的目标，但是劣势在于牺牲了持久性，并发写入时，时间上较早的写入会被丢弃掉。在某些场景中，比如分布式缓存，只记录最新一次写入是可行的，但如果是所有写入操作都需要完整记录的场景，LWW就不合适了。

合并并发写入的值

多人同时向代码仓库提交代码的时候，代码库自动对代码做合并(merge)。多客户端同时向集群写入数据的时候，也可以采用类型的方式做合并。

举个例子，假设客户1和客户2并发向同一个购物车中添加数据，需要注意的是，数据库不负责合并数据，数据合并的逻辑在客户端代码中实现。

1. 客户1向购物车添加数据milk，数据库中存储的数据为版本1:[milk]。
2. 客户2向购物车并发添加数据egg，并且不知道客户1也在同时添加数据。数据库将本次写入操作标记为版本2，由于不知道该如何做合并，数据库同时保存两个分裂的数据:[milk],[egg]
3. 客户端1向购物车中继续添加flour，认为数据应该变成[milk,flour]，于是把这个值发送给数据库，并且带上版本号version 1。数据库把[milk]更新成[milk,flour]，并打上新的版本号version 3，但是之前的version 2数据[egg]仍然被保留。
4. 与此同时，客户端2并发向购物车中添加ham。上一步客户端1执行的操作，由于是并发的，客户端2此时还未能读到上一步的结果，所以客户端2读到的数据是[milk]和[egg]。客户端2此时执行一次合并操作，生成新数据[egg,milk,ham],连同version 2一起发送到数据库。数据库把之前版本2的数据[eggs]更新为[egg,milk,ham]，并打上新的版本号version 4，但仍然保留版本3数据[milk, flour]。
5. 最后，客户端1并发向购物车中添加bacon，和上一步同理，数据库中的数据从版本3[milk,flour]被更新到版本5[milk, flour, eggs, bacon]，版本4数据[egg,milk,ham]仍然被保留。

上述过程描述了当客户端存在并发写入时，数据库中的数据变化状态，和LWW不同，这里每一步写操作都没有被丢弃。当然，一个购物车不能并存两份数据，为了实现最终一致性，这两份数据最终会以某种方式被合并。可能的方式是取并集，最终购物车的数据为 [milk, flour, eggs, bacon, ham]。

版本向量(Version vectors)

上面的例子中，我们描述了在无主模式的集群中，单个副本的情况下，如何通过一个递增的版本号，来解决并发写入时的数据合并，实现最终一致性的目标。

现实情况要更加复杂，因为集群中有多个副本，单个递增的版本号就不足够了，我们需要为每个副本都维护一个版本号，整个集群需要维护一组版本号，称作版本向量(Version vectors)。

版本向量也常常被称作向量时钟，实际上两者之间有一些细微的差别，这里就不展开叙述了。

总结

本章主要描述了副本的实现。

使用副本的原因包括:高可用(High availability)、低延时(Low latency)、可扩展(Scalability)。

对于副本的实现，我们描述了单主模式和无主模式场景下，是如何通过各种手段，来解决副本实现的核心难题 ———— 副本间数据一致性，以达到最终一致性目标。