Replication

Replication

Replication意味着将一份数据的副本保存在不同的机器上.为什么要备份呢?

保证你的数据更靠近你的用户(用以减少延迟,比如CDN).
当部分数据失效了,系统能够持续工作.
增加可读机器的数量,提供更好的读效率(提高了读操作的吞吐量).

数据的复制最大的困难在于处理复制数据的更新变化,也就是保持副本的一致性.遇到的问题有很多,包括是同步还是一部进行备份操作?如何处理失败的备份?这一章主要讲述了三种备份架构,以及一致性问题.

Leaders and Followers

在多副本的情景下,我们如何确保我们的数据都存在于所有的副本机器上呢?最常用的架构就是leader-based replication,也被称为active/passive或者master–slave replication.

一台副本机器被指派为leader,所有的客户端的写操作请求,都必须发送到leader副本机器上,leader会先把数据写到本地磁盘上.
其他的副本机器被称为followers.leader除了负责将数据写入本地磁盘,还需要将数据的变化发送给所有的followers,一般都是以replication log或者change stream的形式.所有的followers从leader那里获取到日志,然后更新自己本地的数据文件,并且保持和leader一致的处理顺序.
当一个客户端想要从数据库读取数据时,它可以把请求发送给任意leader或者followers.但是写操作必须发送给leader.

需要关系型数据库内置的复制模式就是这种模式.一些非关系型数据库也采用这种模式.不近数据库使用这种模式,就连分布式的消息代理Kafka也采用这种模式.

同步异步复制

复制的一个重要的细节就是,是同步复制还是异步复制.一般复制操作都是很快的,但是很难保证复制操作到底会延迟多久.

同步复制的优势是保证所有的followers都和leader是一致的,就算leader挂掉了,随便一个follower都能顶上.但是劣势也很明显,如果某个follower由于某种原因迟迟没有回应,那么这次写操作就会被阻塞,直至这个follower恢复正常.实际上,同步复制是不可操作的,任意一个follower的故障就会将整个服务阻塞,因此如果你在一个数据库配上设置为同步,通常意味着其中一个follower是同步的,而其他follower的复制操作仍然是异步的.当一个同步的follower不可用的时候,就会将一个异步的follower升级为同步follower,这样做的好处是,始终保证数据存在至少两个节点上,这种方式被称为semi-synchronous.

通常情况下,leader-based模式都是完全异步进行复制.这意味着如果leader发生了故障,会导致一些写入的数据不可读从而丢失了.但是完全异步的复制有这样一个优势,就是就算所有的follower都故障了,leader仍然能够提供服务.弱化数据的保障看起来不是一个好的选择,但是异步复制正在被广泛使用,尤其是有很多follower分布在世界各地的时候.

chain replication是一种异步复制.节点按照链式排列,而不是传统的星状排列.

所有的读操作必须发送到尾节点(primary节点)上.
所有的写操作发送到头结点,然后写入成功操作发送到下一个节点,直至发送到尾节点,由尾节点响应客户端.

新加follower

从leader上复制某个时间点的快照.
将快照复制到新增的follower上.
接着follower需要连接上leader,并且请求快照之后所有的数据变化.这就需要快照指明复制日志的具体位置.
然后follower需要执行快照以后的日志内容,直到追上leader,这个时候就可以正常的工作了.

处理节点故障

follower故障

由于follower都从leader那里同步了复制日志,因此可以很容易的通过复制日志进行恢复.恢复后还需要从leader那里获取故障之后发生的数据变化日志.执行完这些后,follower就能正常对外提供服务了.

leader故障

leader出现故障比较麻烦.首先需要新选择一个follower作为新的leader,然后客户端需要被重新配置,将写操作发往新的leader,最后其他的follower需要从新的leader同步数据.这被称为故障转移.故障转移操作可以是手动的,也可以是自动的,自动的操作如下:

首先需要确定leader是否真的失效了,由于故障原因很多,例如leader崩溃了,断电了,网络问题或者其他.常用的策略就是通过心跳检测,来确认进程是否还活着.
选择一个新的leader.新的leader可以通过一个选举过程选择,也可以是之前的leader指定的.最好是数据变化最接近原来的leader的follower被选为新的leader.如何让所有的节点同意这个新的leader,是一个一致性(consensus)问题.
重新配置系统使用这个新的leader.客户端需要发送写操作到新的leader上,然后旧的leader即使恢复了,也要变成follower,并且认可新的leader.

故障转移过程里伴随着很多异常:

如果采用了异步复制策略,新的leader也许会丢失之前写到旧的leader还没来及发送给其他follower的请求.最简单的措施就是,丢弃这些写操作.
但是丢弃写操作将会导致很多问题,比如主键被重复使用了.
在选择新leader的时候,可能会发生脑裂问题.安全起见,系统应该有一个机制就是自动关闭其中一个leader,保证系统只有一个leader.
心跳的时长该怎么选择呢?如果心跳时长太长,导致故障恢复的时间会变长,如果心跳时长太短,会导致不必要的故障恢复操作.

由于这些问题并不是那么容易解决,因此很多时候,故障转移操作都是管理员手动去操作.节点故障,不可靠网络,节点一致性权衡,持久化,可用性以及延迟都是分布式系统不可避免的问题.

复制日志实现

基于语句的复制

最简单的实现就是,将请求里的操作发送给各个follower,对于关系型数据库,就是将增删改查操作都发送给follower,让follower再执行一遍.尽管这个方法听起来很靠谱,但是操作起来就会发现问题.

如果执行语句中包含非确定的函数,例如now(),rand(),那么数据肯定就不一致了.
如果执行的语句需要依赖数据的当前状态,那么执行的顺序就非常重要了.一旦要求了执行顺序,那么并发执行事务就会很麻烦.
有些执行的语句包含有副作用.除非这些副作用是确定的.

实际上,也不是没办法解决,对于那些非确定的操作,leader提前将这些操作的结果写回来替代这些操作.不过,其他的复制方法更好,所以不采用这些方法.

预写日志的方式

leader可以将预写日志发送给follower,然后让follower重复执行日志内容.主要的问题在于,这些日志内容都是二进制格式,并且与存储引擎紧密相关.因此如果主从机器上的存储引擎版本不同,都有可能导致复制问题.这看起来是个小问题,但是想一下,如果版本是可以兼容的,那么我们可以做到无宕机升级操作,但是如果版本不兼容,那么我们不得不进行停机操作进行升级更新.

逻辑日志方式

逻辑日志是为了和物理引擎的数据表达格式进行区分.一行逻辑日志内容,通常就是数据库里的一行数据.

对于插入的行,那么日志内容包含每列的最新数据.
对于删除行,日志包含标识该删除行的信息.如果有主键还好,没有主键的情况下,删除行的数据需要被记录下来.
对于update操作,日志包含唯一标识改行的信息,并且包含更新的数据信息.

事务往往会更改多行数据,因此还需要记录事务提交的标识.binlog就是采用这种方式.由于逻辑日志与引擎内部实现无关,因此很容易做到向后兼容,因此避免了预写日志复制的问题.被用于建立数据仓库,索引和填充缓存.这种技术被称为CDC(change data capture)

基于触发器的方式

有些时候,我们只希望复制部分的数据内容,这个时候我们就需要把复制工作上移到应用层来实现了.我们可以利用数据库里的触发器和存储过程来实现.当发生数据变更时,触发器被触发将执行指定的存储过程,将响应的变更写入其他的数据库里.但是这种方式也会带来额外的工作量,并且容易导致更多的bug.

复制日志的问题

我们需要复制操作的一个原因,就是为了能够容忍部分节点故障.当然还有扩张性和低延迟的考虑.主从结构中,写操作都只能到主节点上,读操作可以到任意节点.对于读操作多,写操作少的应用来说,设置很多follower能够极大的提高应用性能.当然在这种场景下,主从结构必须采用异步复制的模式.

然而,既然应用的读是从异步follower上读,那么就会出现follower上的数据落后于leader.因此当发送同一个请求到leader和follower上,就会发现结果可能会不一致,当然如果停止写操作然后等一会儿,follower慢慢会追上leader,然后两者的数据最终会完全一样.这被称为最终一致性(eventual consistency).最终的意思其实就是说,不清楚到底何时会达到一致.一般来说,这个延迟很小,但是如果发生了节点故障或者网络问题,那么这个延迟有可能会很长.当延迟很明显的时候,就会导致一些问题.

写后读一致性.

想象这样一种场景,你提交了一个写操作到leader节点,随后你预览你的写操作,请求被打到了follower上,由于复制延迟,你看不到你提交的写操作.这种被称为read-after-write一致性.

当读取有可能更改的数据时,应该选择从leader节点返回数据.而数据是否可能更改,需要你自己提前去测试.
但是如果应用中所有的操作都可能变化,那么1就不具备可操作性了.这个时候可以选择,在提交写操作后的一段时间内,所有请求都发往leader节点.或者根据可观测的复制延迟,来选择这个时间.
也可以选择让客户端记录最近写操作的时间戳,当请求发送到follower时,只返回时间戳大于写操作时间戳的结果,如果没有就把请求转发给其他副本.或者可以等当前副本满足条件了再返回结果.时间戳可以使用逻辑时间戳(自定的序列号)或者实际系统时钟.
如果副本部署在不同的机房,那么还必须保证发送到leader所在的机房.

当请求来自不同的设备的时候,这个问题会更棘手.因此又衍生出cross-device read-after-write一致性:

不同设备只能记录自己更新的时间戳,没办法获知其他设备的更新时间戳.因此更新时间戳这种元数据还得提供一个中心化的服务来管理.
如果数据分布在不同的机房.那么不同的设备就有可能被分配到不同的机房.那么你需要强制一个用户所有的设备的请求都分发到一个机房里.

单调读一致性

由于读请求会被分发到不同的副本节点上,这会导致前一个请求获取到了数据,后一个请求就没数据了.单调读一致性比强一致性弱,比最终一致性强.

为了保证单调读一致性,就需要保证请求始终发到同一个副本节点上.

一致前缀读一致性

这种一致性要求,读取的顺序必须和写入的顺序是一致的.如果数据库没有分区,那么这种一致性很明显是满足的,但是对于有分区的分布式数据系统,某个分区内部是有序的，但是不同分区之间是无序的。

一种解决方案，是使得有因果关联的写操作都写入同一个分区，但并不是总能做到，因此需要一些算法来跟踪这些因果关联的写操作。

日志延迟问题

当我们工作在最终一致性的系统上时，我们应该思考这样一种情况，当日志复制的延迟增大时，我们的系统还能正常工作么？如果不能的话，那么我们需要依赖一个更强的一致性保证。日志的复制是异步的，而不是我们认为的同步，这是问题出现的根源。

我们可以通过应用层手段来提供更强的一致性，但是这会使得程序变得复杂而且容易出错。或者我们干脆让事务来简化我们的应用层实现，但是分布式的事务受制于性能和可用性，因此最终一致性成为分布式应用系统的最终选择。

Multi-Leader Replication

上一个主题是单主架构，这个架构有个明显的缺点，就是只能写主，如果主节点挂掉了，那么你就不能再写了。因此为了解决这个问题，可以增加主节点形成多主结构。

多主复制场景

在单机房里面部署多主节点，实际上没有什么意义。多主带来的问题和复杂度远比带来的好处多。

多数据中心

我们部署数据库的时候，有时候会部署多个数据中心（也许是为了容错一个数据中心崩溃，也许是为了让数据离用户更近）。每个数据中心都是单主架构，然后多个数据中心之间的主节点之间进行同步数据。

属性	对比
性能	单主节点中，每个写必须连接到主节点所在的数据中心，因此会增加延迟。多主架构中，写操作直接到达本地数据中心的主节点，之后异步同步到其他的数据中心，因此速度上会更快
容错率	如果主节点所在的数据中心故障了，其他数据中心的follower会成为新的主节点。多主架构中，各个数据中心独立运行，副本复制可以等到故障数据中心恢复回来
网络问题	数据中心之间的数据传输走的是公共互联网，稳定性远不如局域网。单主架构对于网络延迟很敏感，网络问题导致同步写操作会很慢。多主节点因为不同数据中心之间是异步复制，因此能很好的容忍网络不稳定。

多主架构有点很多，但是有个很大的问题，就是不同的数据中心会出现并发写问题。需要处理写冲突问题。此外还有自增长主键，触发器以及完整性约束也是个问题。

离线操作

此外，当应用需要在没有联网的情况下工作，也可以采用这种架构。例如多个设备上的app，当离线的时候也应该能够使用，然后再次联网的时候和应用服务器进行同步操作。每个app上的本地数据库可以看做leader，然后后台异步进程进行同步数据。这种场景可以看做是非常极端的多数据中心情况。

协同编辑

实时协同编辑应用运行用户同时编辑一个文档。这种场景其实不是一种数据备份问题，但是和离线操作场景有很多共同点，当编辑文档的时候，文档状态存储在本地，然后异步和其他人进行同步。如果你想保证没有冲突，那么就需要一个同步锁，当一个人编辑时其他人不可编辑，就类似单主架构了。但是为了更快的编辑效率，那么就需要允许大家共同编辑，但这就需要解决冲突问题。

处理写冲突

如果都提交成功了才发现冲突，这个时候再通知用户就太晚了。如果检测完是否有冲突后，再告诉用户是否成功，那么就失去了多主架构的优势。因此如果采用同步的冲突检测，还不如使用单主架构。

冲突避免

避免发生冲突时解决冲突的最好方法。例如单个用户的请求始终发送到某个数据中心，这样就避免了冲突。整体上是多主架构，但是单个用户来看这是单主架构。但是这并不总是有用，例如一个机房崩溃了或者用户搬家了，还是会出现并发写的问题。

收敛到一致性状态

冲突会导致数据不一致，因此我们需要一些方法，使得数据最终一致。

给定每个写操作一个唯一ID，然后最大的ID就是最终的结果。如果我们使用时间戳，这也就是LWW（last write win），当然这个方法会导致数据的丢失。
给每个副本一个唯一的ID，然后大ID的副本数据始终优先于小副本，很明显，这同样会导致数据丢失。
将数据按照字典序连接起来。
保留所有的信息，然后交给客户端去处理冲突。

冲突解决逻辑

解决冲突最合适的方式就是根据应用来定，有很多工具依赖应用程序来解决冲突。

写时解决：当数据库系统发现冲突时，会执行冲突解决代码。这个代码是管理员提供的而且需要快速在后台执行。

读时解决：但冲突发生时，所有的信息被记录。当下一次数据被读取的时候，都发送到客户端，然后交由客户端解决冲突并写会数据库。

冲突解决的规则会变得越来越复杂，例如亚马逊发现购物车冲突时，只会增加购物车而不会删减。已经有一些自动解决冲突的算法，但是还都很不成熟。

什么是冲突

有些冲突很明显，比如同时写同一个属性值。然而有些冲突比较微妙，例如会议室预定系统，预定前都会查询会议室的可用性，但是由于存在于不同的数据中心，因此很有可能会发生冲突。

多主副本拓扑

副本拓扑描述了写操作传播的路径。 Figure 5-8. Three example topologies in which multi-leader replication can be set up

大多数拓扑结构都是all-to-all结构。在环形结构和星状结构可能会存在循环复制，为了避免循环复制，每个节点给定一个唯一标识，然后每个写入请求会携带所有经过的标识，当一个节点收到请求时，如果发现了自己的标识，那么这个请求就会被忽略掉。此外，这两种拓扑结构中，如果存在任一一个节点失败了，就会中断复制路径需要等待人工恢复。因此all-to-all结构应用比较广泛一些。

但是all-to-all结构也会出现问题，因为有些路径快一些有些路径慢一些，会导致同一个节点接收到不同的请求顺序。通过时间戳是不可取的，因为不同节点上的时间戳有可能是不一致的。大部分多主数据库是不提供冲突检查的。

Leaderless Replication

在无主架构中，客户端发送写入请求到若干个副本上。那么当进行读取的时候，同样会将读请求并发地发送到若干个副本上，然后通过version numbers来选择最新的数据。

读时修复与反熵

有两种机制用来修复重新上线的副本节点数据。

读时修复。当客户端从若干副本节点读取到数据后，进行合并然后将最终的数据写回到副本节点。这种方法比较适合读取频繁的场景。
反熵进程。数据库有一个后台进程持续观察副本之间的数据差异并进行复制。不同于单主架构中的副本日志，这个进程在复制操作中是没有任何特定的顺序的，并且数据有延迟。

Quorums机制

如果有n个副本，每个写入请求必须保证有w个节点成功，我们读取的时候至少读取r个节点。只要w+r>n我们就认为最新的数据已经被读取到了。因为至少有一个节点既写入成功了，也被读取到了。符合这个条件的读写操作被称为Quorums读写。如果想要写的时候快一些，那么只需要w=1，那么r=n。如果想要读时快一些，那么就需要w=n，那么r=1。这里注意，一个集群当中存在不止n个节点，但是某个指定的数据只存在于n个节点上。

Quorums一致性的限制

通常w和r会选择超过n/2的节点数，这样就能确保容忍最多n/2个节点失败。当然也可以选择更小点的数，一方面很有可能读取到过期的数据，但另一方面可以得到较低的延迟和更高的可用性。即使满足了w+r>n，也存在一些问题：

如果一个sloopy quorums，例如写入的w个节点和读取的r个节点是完全不同的节点，那么他们之间就不存在重叠的节点了。
如果两个写操作同时发生了，那么哪一个先发生呢？那么这个时候需要合并并发写入的操作。如果根据时间戳来判定，那么写请求有可能会因为时钟偏移而丢失。（这也是接下来要说的问题）
如果读写操作同时发送，那么写入只是发生在部分副本上，读取操作返回的是旧值还是新值呢？
如果一个写操作，在一部分副本上写入成功了，而在另一部分的副本上写入失败了，并且成功的节点数少于w，在成功的节点上也没有回滚操作。那么这就意味着如果写入失败了，那么接下来的读取操作有可能返回写入值，也有可能不返回。
如果一个保留有新值的节点失败了，恰巧从一个保存旧值的节点上进行了恢复，此时保留有新值的节点数不足w个，因此新值就丢失了。
尽管一切都正确运行了，但由于时延可能会有一些边界情况发生（由于时延，写入操作在读取操作之后才到达服务器）

因此，尽管Quorums机制保证了会有一个读取时最新的值，但实际上并不是那么简单。实际操作中，尽量避免使用这种方法，它只保证了最终一致性，而对于之前提到的各种一致性是不支持的。

监控

我们应该对过时的数据返回进行监控,从而能够及时排查到原因.对于单主系统,通常会有针对数据延迟的度量数据产出,然后给定监控系统进行监控.由于单主系统中,写入是有序的,因此通过对比主从节点的复制日志内容,可以估算出差异.但是对于无主模型,这样的监控有点儿困难.

Sloppy Quorums

对于无主的架构,可以容忍个别节点失败变慢并且无需进行故障恢复.w+r>n的特性使得无主架构具备高可用性和低延迟,并且能够容忍临时的旧数据.但是,Quorums机制并不能够容错,如果因为网络原因导致客户端无法连接服务器,那么就会导致w和r都达不到要求数据量,因此客户端无法正常工作.当在一个很大的集群环境下,客户端只能连接到部分节点,而且这些节点并不是包含当前指定值的节点,这个时候就需要一个权衡:

返回error信息.
接受写请求,忽视原来值存活的节点.

后者就会引发sloppy quorums问题,就是说读写个数都满足必须的w和r个,但是读写处理的节点并不全是存储有指定数据的那个n个节点.举个例子,比如你把自己所在自己家门外面了,然后你跑到邻居家敲门问问能不能借宿一宿.而当网络恢复了正常,那么写入到临时节点的请求就会被发送给原来的指定节点上.这叫做hinted handoff. sloppy quorums能提高可用性,但可能会读取到过期的数据.因此,sloppy quorums只能保证数据被持久化,在数据回写完成前,无法保证能读取到最新的数据.

多机房部署

Cassandra和Voldemort在多机房部署中,n个备份存在于各个机房里,可以通过配置设置各个机房里具体的备份数.所有的写操作被发送到全部备份节点上,但是只需要等待本地机房节点的ack响应.因此可以很好的降低延迟和容忍跨机房的网络中断.而其他机房的写入操作可以异步完成.

而Riak则将n限定在一个本地机房里,然后跨机房的备份节点之间在后台进行异步备份,这和多主结构很相似.

并发写操作

无论是在读时修复还是回写时,都会存在并发写冲突的问题.

happens-before和并发

当B操作依赖于A操作的写入时,我们说B causally dependent A.
当A操作和B操作之间没有任何依赖时,我们认为他们属于并发操作.

因此只要你有两个操作,要么A先发生于B,要么B先发生于A,要么A和B并发.如果存在先发生的关系,你们后发生的操作就应该覆盖先发生的操作,但如果是并发操作,那么我们就需要解决冲突问题.由于分布式系统时钟不同步的问题,因此并发操作和时间没有必然联系.如果说两个操作互相无感知,那么这两个操作就是可并发的.我们需要一个算法来告诉我,两个操作是否是并发的.

这个算法可以这么操作

服务器端为每个key维持一个版本号,每次这个key被重写时就增加版本号,并将新的版本号和值一起保存起来.
当客户端读取一个key时,服务器返回最新的版本号和所有的数据值.也就是说客户端在写之前必须读.
当客户端写入一个key时,请求里必须包含之前读取的版本号,也必须负责合并之前读到的数据值.
当服务器接收到带有特定版本号的写请求时,就可以复写相同版本号或者更低版本号的值.但是必须保留更高版本号的值.

合并值最简单的方式,就是根据版本号和时间戳,但这样会丢失部分数据.还可以取数据值的并集.但是如果允许删除操作的话,就不能只是取并集了,一般删除的时候不会直接进行删除,而是使用一个占位符来指示该值被删除.

版本向量

针对多个副本,需要为每个副本上的key都保持自己独立的版本号,从而形成了版本向量.

总结

副本机制的存在是为了:

高可用性:保证即使在一台机器故障的情况下,系统仍然能够提供服务.
无连接操作:允许应用在网络故障下继续工作.
延迟:将数据存放在离用户更近的位置,加速用户的访问.
可扩展性:通过将读取请求分发到不同副本,提供更高的读取性能.

尽管只是将相同数据的副本保存在多台机器上,却带来了一系列问题,例如并发问题等等.

副本架构有三种:

单主架构:所有客户端将写请求发往主节点,主节点将数据更改操作同步到从节点.读取操作可以发往任一节点.
多主架构:客户端把请求发往任一一个主节点上,然后主节点间进行同步.
无主架构:客户端把请求发往一些节点,并且并行的从一些节点读取数据,来规避读取到过期数据的问题.

每种架构间各有千秋,单主节点很流行因为它很容易理解,并且不存在冲突的问题.多主节点和无主节点更加鲁棒,在应对节点故障,网络分区和延迟峰值问题上.

副本的复制可以是同步的,也可以是异步的.当出现故障时复制方式有很大的影响.当系统顺利运行时,异步复制会更快,但当复制延迟增加并且主节点故障了,这时就会丢失一些已经提交的数据.当复制延迟出现时,会出现一些一致性问题:

读写一致性:用户总能看到他们已经提交的数据.
单调读一致性:当用户看到某个数据后,不应该看到该数据更早的版本.
一致前缀读取一致性:用户会看到因果颠倒的数据.

最后就是并发问题,在多主架构和无主架构,因为允许并发写操作到不同节点,因此会产生冲突.我们提供了一个算法来甄别是否多个操作是并发的,还是有依赖关系的,并且提供merge操作来合并冲突数据.

Designing Data-Intensive Applications读书笔记(5)