引言

复制是在各个节点中存储相同的数据,而数据复制模式的背后是分布式节点的部署方式.通过这些方式我们希望达到以下几个目的:

1. 数据在地理上据用户更近,这也意味着网络延迟的减少.
2. 可对整个系统进行水平扩展,提高吞吐量.
3. 部分机器或者子系统出现问题的能够对外界继续提供服务.

在一般情况下我们的数据都是可变的,这个时候根据不同的需要衍生出三种数据复制的方法,使得能够高效的处理这些动态的数据(数据是静态的话直接全部复制一次就完事了嘛):

1. 主从复制
2. 多主节点复制
3. 无主节点复制

它们在不同的情况下有各自的优点,现在几乎所有的分布式数据库都使用的是上述三种模型之一.

虽然只是复制,但是我们的问题仍旧很多,比如某个节点宕机如和保证数据不丢失且持续提供服务?数据复制采用同步去保证强一致性还是异步复制去保证最终一致性?如何高效的进行节点间数据的交换?..接下来我们就来看看这些问题.

如何确保主从节点间数据一致

这里其实是分很多种情况的,首先是同步数据的方式,是使用同步复制还是异步复制呢?同步复制也就是把数据发给每一个从节点(或者其他主节点),等待回复,当所有有效从节点数量个回复时向客户端回复收到消息,这样的缺点不必多说,就是不确定的网络情况,这种同步复制的方式可以使我们的服务器集群获得强一致性,当主节点宕机时从服务器总是可以访问最新数据,如果从节点没有接到最新消息的话,写入就始终不能算成功,这样就可以保证写入成功以后的全局数据一致性.那么异步复制呢?其实就是异步的发送同步信息给从节点,然后直接向主服务器报告写入成功,这样确实使得客户端反应很快,但是这种最终一致性的保证可能会出现诸多问题,我们后面慢慢说,最重要的时这样很可能在主从复制的时候出现数据丢失.所以现在很多主从复制模型采用的都是半同步,即一些节点是同步的,保证从节点中始终有最新数据.

像我们平时的单节点主从复制结构,正常的由主节点同步给从节点就可以了,也就是上面我们说的那样,但现实情况是会出现多节点的,一般情况下集群中的网络拓扑结构是这样的:

其实网状拓扑结构是有一些问题的,比如某些网络链路快于其他网络链路,这样的话就可能出现A节点进行SET,B节点看到SET的结果以后UPDATE,但是C节点先看到UPDATE后看到SET,这样是很有问题的,解决的方案就是版本向量技术,这种技术可以分辨某些操作是并发的还是有依赖关系的.

这时某个节点上的数据更新又如何传播到上述节点呢?答案就是基于各种协议的心跳包,比较常见的就是gossip协议.这样不但可以以很快的速度在全局中更新数据,还可以判断某个节点下线.

如何处理节点失效

一般来说节点的失效我们分为以下步骤来进行:

1. 故障发现: 发现某个节点下线
2. 故障转移: 进行主节点切换,把所属从节点进行升级
3. 在宕机主节点上线后的更新,其实这种主节点完全可以当做一个出现网络分区的单个节点,数据出现落后,当它发送心跳包的时候,其他节点就会发现,从而对其进行数据更新,这里其实会在每个节点维护一个offset,标记当前最新数据,这样就可以不必进行全部替换,只更新缺失部分了.Redis中的做法是在服务器维护一个叫做"复制积压缓冲区"的buffer,其中存着最新offset对应的数据,当然缓冲区大小是可配置的,缓冲区越大,存储的命令越多,复制时进行部分同步的概率越大,当然需要付出内存代价.

这里其实会出现一些问题值得我们注意,当采用异步复制的时候可能主节点进行数据同步以后直接宕机,但此时数据还未传到任何一个从节点上,这个时候一个从节点升级为主节点,然后宕机的主节点又恢复了,并成了这个新主节点的从节点,此时这个从节点的数据版本是高于主节点的(判断版本的方式就是使用配置纪元),常见的解决方案就是丢弃与主节点冲突的请求.

还有故障恢复的细节是什么呢,首先我们需要判断某个节点下线,最常用有效的方法就是心跳包了,当一段时间为接到心跳包的恢复就可以认为某节点主观下线,然后请求其他节点看法,当多数同意即也判断为下线时认为某个节点已经下线,并开始故障转移.然后我们需要选举出一个新主节点,redis采用的一致性方案是raft算法的选举部分,当然一致性方案还有paxos.这样就完成了一次故障转移.

复制日志

这是一个非常重要的问题,首先它一定要阐明某个语句的语义,在此基础上还要尽可能简洁,以减小数据量,我们有以下几种方案:

1. 基于语句的复制:也就是把每个到达服务器的请求再发送给其他节点,有一些不确定的命令则发送确定后的数据,以保证节点间数据一致.
2. 预写式日志:记录数据库写入的字节序列,这样主从之间是内容完全相同的.但是它的描述过于底层,与存储引擎耦合度过高.
3. 逻辑日志:用一系列记录来描述行级别的写请求,这种逻辑式的日志可以与存储引擎解耦合,也更容易解析.也叫变更数据捕获.

多主节点复制

我们不去讨论但主节点的主从复制,因为局限太大,在读上几乎没有扩展性可言,当然也可以使用一个代理服务器(Twemproxy)去使得单主节点主从复制更为高效,但此时的瓶颈又到了代理服务器上,所以多主节点当然有其必要性的.它的优点如下:

1. 多主节点可以使得数据中心距客户端更近,网络延迟更短.
2. 多主节点中每个节点都是独立的,也就是说在宕机以后直接换个IP就可以继续服务.在单主节点中还要进行选举,从节点升级,与其他从节点通信,其无法进行写操作.
3. 多主节点也可以更好的容忍网络问题,在单主节点中由与写为同步,所以依赖于网络,但多主节点中为异步,可以很好的容忍网络问题,并在一段时间后达到数据一致.

虽然益处多多.但是也有挑战.最大的一点问题的就是数据冲突,即在两个不同的节点逻辑上并发的写入,这样两个写入都是成功的,会在后面数据的同步中发现冲突,显然我们不希望数据不一致,所以需要使用一些方法来解决这个问题.理论上来说我们可以同步写入,这样就是第二个写入操作覆盖第一个,但这样显然丧失了多主节点的优势.解决方法如下:

1. 避免冲突:我们可以在应用层是不同的用户始终访问地理上据他更近的同一个节点,这样就不会发生写冲突.这样对于用户来说就相当于是单节点主从复制,典型例子就是Redis的集群.当我们使用某个账号对应节点时确实是非常不错的,但是如果换到了另一个地方,此时距离原节点地理上就太远了.
2. 收敛于一致状态:多主节点不像单主节点那样写入有顺序性,多主节点互相都不知道对方此刻发了哪些消息,这些消息都是并发的,那么如何收敛于一致状态,保证全局数据一致呢?可以分配UUID,或者使用基于存储的哈希,比较大小,大的删除,此时这里的纪元应该是高于其他节点的,几轮心跳包以后就数据一致了.
3. 自定义冲突解决:最典型的就是git了吧,当我们有了两个分支以后把这些值混合在一起,用户自定义选择.

无主节点复制

其实就是放弃使用主节点,此时所有的客户端都可向任何节点发送写请求.这样做的好处就是更好的容忍并发写入,网络中断(sloppy quorum),我们可以根据不同的配置使得某个节点有不同的数据一致性保证.可以保证在任何时候都是可写的.
无主节点有什么好处呢?

An extension of symmetry, the design should favor decentralized peer-to-peer techniques over centralized control. In the past, centralized control has resulted in outages and the goal is to avoid it as much as possible. This leads to a simpler, more scalable, and more available system.
作为对称性的扩展，设计应优先考虑去中心化的点对点控制而不是集中控制。 过去，集中控制已导致中断，我们的目的是尽可能避免这种情况。 这导致了一个更简单，更可扩展且更可用的系统。(2.3)

在这样一个网络中如何算写入成功呢?就是在写入时向大量节点发送请求,当其中多数回复以后算是一次写入成功,那么假如我们读取未写入成功的节点呢?还是无法取到准确数据呀,此时我们可以向多个节点发起请求,即:
仲裁条件: w+r>n 表示如果有n个副本,写入需要w(N/2+1)个节点确认,读取至少需要查询r个节点.这样可以保证读取中一定有最新数据.
这种情况下我们当然也需要去同步信息,毕竟还有一部分未更新,有两种策略:

1. 读修复: 读取多个副本的时候可以发现旧值并得到新值,把新值写入旧值即可.适合于频繁读取的场景(更新更快).
2. 反熵: 其实功能类似于心跳包(有更高级的实现MerkleTree,这个我没有细看),用于后台比较和其他副本差异,选择更高版本更新.

而且这样的结构是有很好的容错性的,当出现问题宕机不需要执行故障转移,也可以忍受某些节点出现网络延迟,因为只需要N个节点中的w或者r回复就算是成功,这样在高可用低延迟的场景确实是一个很好的选择,但是在一些网络中断的时候有大于(N-w)节点宕机时整个集群就属于不可用状态,因为请求不会成功.但是此时客户端仍能连接到一些节点,如果此时鲁莽的直接把错误返回客户端好像有点不优雅,此时的解决方案就是sloppy quorum,就是先接收这些请求,并放入一些其他的节点中,这些节点并不在N个节点中(一致性哈希中N为某个节点顺时针方向的N个值,但其中有不可用节点时可顺时针再找一个节点).此时写入和读取仍需w和r节点,但是可以包含不是那N个节点,当N节点中上线以后再把数据传回去.这样可以大幅的提高可用性,只要有w个节点可用就可以接收新的数据,这样也有坏处,就是无法保证读取的一定是新值.

当然在这样的无主节点复制模型中也可能出现ABA问题,就是并发修改导致数据不一致,我们希望副本可用收敛于相同的内容,如何做呢?

1. 最后写入者胜利:在更新中选择时间戳更高的写入,丢弃较早的时间戳请求,这样就可以保证一致性.但是并发写入的其他数据都丢失了.要想完全避免LWW完全无副作用的唯一方法是:只写入一次然后写入值视为不可变,这样就避免了对同一个主键的并发写.例如,Cassandra的一个推荐使用方法就是采用UUID作为主键,这样每个写操作都针对不同的,系统唯一的主键.(Amazon Dynamo就是这样做的)
2. 使用矢量时钟判断操作的并发关系.

参考:
《数据密集型应用系统设计》笔记五：第五章 数据复制

Amazon Dynamo论文中文版

Amazon Dynamo论文解读 — 技术介绍（转载）