如何理解无领导复制模型与复制延迟问题

在上一篇我们了解了基于领导者复制算法模型,今天继续上一篇的话题来聊聊基于Leaderless复制算法模型, 其次我们再来讨论Replication Lag对一致性模型带来的问题,并思考我们可以解决的方案.

Leaderless Replication

前面我们讲述的数据复制算法模型都是基于leader节点接收客户端数据写入并基于leader副本节点复制到其他Replica节点,当leader节点发生故障的时候,我们的follower节点则需要做自动故障转移机制.

那么除了这种方式,其实还有一种方式就是不存在leader节点,即每个Replica节点都能够接收客户端的读写操作,即使其中一个Replica节点发生故障,集群中的Replica也不需要进行自动故障转移.这就是我们的Leaderless Replication,即无领导复制算法模型.我们熟悉的Dynamo以及Cassandra数据库均采用无领导复制模型.

那么它们是如何进行工作的呢? 一般有两种形式, 第一种方式是客户端直接向多个Replica分别发送写入操作, 即:

图片

第二种方式是借助协调者分别向多个Replica发送写入操作, 即:

图片

这个时候也许我们会有一个疑问, 就是上述Replica发生故障导致不可用了,这个时候我们写入机制如何保证? 这个时候就是通过Quorum NWR来解决这个问题.

假如现在有三个Replica副本中, 如果其中一个Replica不可用,在基于领导者复制模型中我们会做自动故障转移的方式,但是在无领导者复制模型中,其不存在故障转移,而是基于Quorum NWR机制 + Read Repair机制来实现.

比如以下场景, 在leaderless复制模型中客户端向三个Replica发起写入操作,其中Replica3发生不可用,假如我们并发/并行发送三个写操作,仅需要有2个Replica响应成功即可认为写入成功,即在下面场景中Replica3不会返回客户端“OK”的响应,但User已经接收到Replica1以及Replica2的“OK”响应, 我们认为写入是成功的,客户端直接忽略有一个副本未收到写入这一个事实.

图片

我想我们看到这里肯定还有一个疑问, 那就是Replica3节点恢复了, 但是客户端写入的数据丢了, 这个时候Replica3与其他副本节点数据上会存在一致性问题, 那么如何让Replica3保持与其他Replica节点数据一致呢?

一般会常用两种机制, 其一是读取修复, 即客户端从数据库读取数据时, 它不会只将请求发送给一个副本, 而是将请求会同时发送给多个节点, 客户端通过不同节点可能读取到不同版本号对应的数据值, 那么客户端就根据版本设置规则来确定哪个值是最新的,这种一般是针对频繁读取场景效果良好, 即:

图片

但是如果不是频繁读取场景, 该如何进行对比修复呢? 这个时候我们的Replica副本需要进行通信比对数据并修复数据差异来实现一致性, 通常可以在对应的Replica进程中fork一个后台反熵进程用于通信以及修复对比,即持续查找其他Replica之间数据的差异,通过拉推方式来缺失的数据从一个副本复制到另一个副本中,相比多主复制传播方式这里的反熵进程并不会采取特定的顺序方式复制写入操作.

以Replica3为例,第一种方式就是每隔一段时间随机选取某个其他节点相互交换自己的所有数据消除两者之间的差异, 比如这个时候Replica3向Replica1节点交换自己的数据,如下:

图片

但是这种实现方式有个明显的问题, 就是如果数据量很大, 那网络通信的开销会很大,同时如果节点比较多且存在动态变化的时候,比如在k8s容器我们的容器IP经常是变动的,如果是部署在容器化,那么这个时候反熵会影响我们服务进程性能,比如网络以及节点变化带来更多的通信,同时由于不确定性有很可能会导致其中一个Replica产生的网络开销很大(比如多个Replica同时向Replica1节点进行反熵通信),影响cpu性能.

那有什么其他方式吗? 那就是谣言传播机制,就是当一个节点有了新的数据后,这个节点会变成活跃状态并周期地向其他节点发送新的数据,同时我们也需要记录新数据对应的活跃节点分布,直到所有节点都存储了该数据, 这种方式其实就是推的方式.同样以Replica3为例, 那么它将会收到Replica1以及Replica2节点的更新数据并进行修复:

图片

其实上述就是Gossip协议中的一些反熵实现机制, 同时我们还看到无领导者复制模型是采用Quorum NWR机制来处理我们的数据读写机制保证对外部客户端看到的数据一致性, 本质上其还是属于最终一致性模型, 因为我们允许容忍部分节点数据的不一致性, 比如上述Replica3节点, 然后通过Read Repair(读取修复)以及Anti-entropy(反熵)机制来异步修复数据的一致性问题.关于Gossip协议以及Quorum NWR机制后续我们再聊.

Replication Lag与一致性问题

接下来我们需要考虑Replication Lag的问题. 为什么? 很显然我们数据复制是建立一个无共享存储架构且满足高可用的分布式存储下, 由于多个Replica需要通过网络方式来实现不同的Replica节点数据的一致性. 在前面我们已讲述过分布式环境下网络环境是一个不可靠的因素,对此我们需要了解复制过程中由于网络延迟带来的复制延迟问题有哪些以及对应的解决方案策略.但在此之前,我们需要建立一个假设, 即数据是存储在一个无共享且满足高可用的分布式存储架构中, 每个Replica数据都具备拥有一份完整的独立数据并可对外提供读操作.基于这个前提我们再来考虑一致性模型与复制延迟问题.

1. 读己之所写 - 线性一致性问题

什么是读己之所写模型? 就是我们应用程序允许用户提交对应的数据之后用户查看自己可以看到自己提交的内容, 即用户将数据保存持久化之后要立即能够查看到自己保存的内容.

Leader-Based Replication

那么方式1, 如果我们是基于单领导者的复制模型, 这个时候我们仅考虑单个数据中心,那么这个时候我们的存储架构就是一个单数据中心的分布式主从存储架构,如下:

图片

我们发现这个时候用户请求路由到Follower2节点,但由于复制延迟的问题复制数据还没有到达Follower2副本, 从而导致用户没有读取到数据. 那么这个时候对用户而言, 提交的数据莫名其妙地消失了, 那么他们会感到不满, 甚至是紧张焦虑, 比如是Money的数据.

那么这种情况下, 我们就需要读写一致性, 这个一致性意味着用户1234总是能够查看自己提交的任何数据,但并不需要保证其他用户, 比如User2345也要看到User1234提交到的最新数据,他可以过段时间才显示User1234的最新数据.

那么对单领导者复制模型, 我们要实现读写线性一致性方式可能有以下方式:

• 解决方案1: 始终从leader节点读取用户自己的资料, Follower节点读取其他用户的资料.
• 解决方案2: 监控复制延迟, 即让我们的客户端能够感知到目前读取最新数据节点是leader以及follower1节点, 那么这个时候我们只让读请求转发到leader以及follower1节点.
• 解决方案3: 采用向量版本或者逻辑时钟, 记录一次最近一次写入的标记, 那么当用户读取服务的时候携带对应最新的标记, 根据最新标记找到匹配的数据副本节点, 比如请求到Follower2节点, 但是由于Follower2节点的标记比请求标记不够新, 那么就将请求转发到其他节点, 比如Follower1或者直接转发到leader节点上获取数据.至于为什么不能直接采用时间戳, 相信现在我们也比较清楚, 因为需要时钟同步, 否则时钟是不可靠的.

不知道细心的你是否有发现, 我们讨论的只是一个用户, 如果同一个用户使用不同的设备怎么办? 上述的解决方案哪个有问题? 肯定是解决方案3, 因为需要增加一个元数据管理记录,因为一台设备运行的代码是无法知道另一台设备运行的代码的,因此我们需要一个集中的数据管理来记录用户,更新的数据以及对应的标记.所以实现的复杂度更高.

Multi-Leader Replication

那如果是多主复制模型呢? 为简化复杂度, 这里以双数据中心为例,这个时候我们有办法实现读写一致性吗? 如下:

图片

如果用户是在DataCenter1写入数据, 然后是在DataCenter2读取数据, 这个时候还是会出现数据一致性问题, 跨中心的数据复制我们一般都是采用异步方式, 而由于异步数据复制不仅仅是数据短暂的不一致性问题, 还存在网络分区导致数据迟迟无法同步到数据中心,甚至是数据丢失, 因此这个时候我们是无法实现读写一致性的.

图片

那么有办法实现读写一致性吗? 我想我们可以先尝试以下方式思考:

指定逻辑分区, 避开写冲突, 也就是读写都是在路由到同一个数据中心上, 那么这个时候又变成单主复制模型的解决方案了.也许这个时候我们认为是可以实现读写一致性了, 但其实不是, 为什么? 

试想下, 我们做多数据中心一般在实践中都是做异地多活架构方式, 那么为什么要做异地多活? 肯定是为了应对数据中心乃至区域性级别的故障, 那这个时候即使我们可以将用户请求路由到DataCenter1, 但是如果DataCenter1发生故障了, 怎么办? 还不是需要路由到DataCenter2, 即便我们能够修复数据一致性甚至可以通过持久化机制保证数据的可靠性, 即不丢失数据, 也无法做到写更新之后立即就能够读到最新的数据,毕竟跨中心数据复制是存在网络分区的,因此采用多数据中心复制模型应用到我们异地多活架构实践中, 我们要考虑数据是只能满足最终一致性, 即给予系统有限的时间来保证数据最终一致.

Leaderless Replication

那我使用无领导者复制模型呢? 在前面我们只讲述了leaderless复制模型中的写入操作是通过Quorum NWR机制实现的,同样地我们的读取操作也是可以基于Quorum Read的方式来实现,即假如我有3个Replica, 其中w = 2, r = 2, 那么意味着读己之所写模型也能够实现,即如下:

图片

不论是单数据中心还是多数据中心, 我们都可以实现上述读己之所写的线性一致性.但是不论是单主复制还是无主复制模型,我们都要识别到其中的一致性的含义, 就是读己之所写的线性一致性,如果场景是User1更新了数据, 然后其他非User1,比如User2也要看到User1更新到最新的数据, 上述不论是哪种都可能实现不了,为什么? 因为存在网络延迟问题,这个留着后续详细阐述一致性模型再展开.

2. Monotonic Read - 无法单调读问题

如果我们采用异步复制方式, 那么复制延迟带来的第二个问题就是每次读取的数据都不一致, 我们可以类比为数据库事务中的幻读, 即每次读取的数据结果集都可能不一样.即出现下面的问题, 即用户看到是时间倒流的数据现象, 如下:

图片

比如上述的User2345第一次查询的是1个结果, 然而第二次读取的时候却出现没有匹配的结果集.那么解决此类问题的办法一般是采取单调读的方式, 什么是单调读呢? 它是一种弱于强一致性但是强于最终一致性的保障, 即保证用户每次都是从同一个副本进行读取,不同的用户可以从不同的副本读取,比如基于HashId的方式让用户指定路由到指定的副本节点上读取,而不是随机选择读取.

单调读可以类比于单点读, 但是它和单点读有一个明显的区别, 那就是单点读是单机器, 而单调读是将用户id进行hash分散/或者分区指定机器读取.

3. Consistent Prefix Reads - 违背前后因果关系

假如现在在一个IM系统中Mr.Poons以及Mrs.Cake都是在一个多人的群聊中, 并且聊天有这样的简短对话,如下:

Mr. Poons
How far into the future can you see, Mrs. Cake?
Mrs. Cake
About ten seconds usually, Mr. Poons.

我们可以看到上述的对话存在前后的因果关系, 那么假如这个时候群里有另一个小伙伴, 我们估计称之为Observer, 这个时候看到聊天为:

Mrs. Cake
About ten seconds usually, Mr. Poons.
Mr. Poons
How far into the future can you see, Mrs. Cake?

对于这位小伙伴来说Mr.Poons还没有提问就先看到Mrs.Cake的回答不免令人产生疑惑,但实际这是由于我们存储的数据库存在复制延迟导致的,如下:

图片

也就是我们要防止此类问题的发生, 那就需要另一种保障, 即一致性前缀读, 换而言之就是保持前后的因果一致性. 这也就意味着如果一系列写入操作都是按特定顺序发生,那么任何读取这些写入内容的User都会看到它们以相同的顺序出现.

怎么实现因果一致性呢? 如果Leader-Base Replication复制方式, 那么我们仅需要考虑写入操作的顺序即可,如何保证写入操作的顺序呢? 还记得我们先前讨论过的时钟问题吗? 我们可以通过逻辑时钟以及Google Spanner的True Time API来保证我们操作的顺序性, 其次还可以基于递增的版本向量的方式, 即每个Replica都拥有一份对数据写入的版本号, 多个Replica组成的版本向量来保证我们数据复制的顺序性.

其次, 如果是基于Multi-Leader Replication的模型, 其实在上述例子我们已经看到主要原因是由于分区复制延迟导致我们的Observer先获取到Mrs.Cake的消息数据, 那么为了保证消息的顺序性, 我们可以考虑将Mrs.Cake的写入操作路由到Partition 1的leader节点中应用写入,然后再根据单leader节点通过上述手段来保证消息的顺序性并复制数据到其他Replica节点中,但这种方式效率并不高,因为写入操作又变成单点leader写入,并没有达到Multi-Leader Replication目的,即实现高可用的写入.

最后如果是Leaderless模型, 其实也和Multi-Leader模型一样, 但它很难实现因果一致性,即满足W + R > N也无法保证读取的其他Replica就已经将数据copy并应用到当前的节点上, 可能你会想W = 1, R = 1 不就可以了吗? 是的, 但已经改变架构本质的初衷, 这样还不如单点来得简单.

我想我们可能也会有些疑惑, 怎么知道因果关系, 好比上述聊天场景, Message2的输入依赖于Message1的输出结果, 

图片

然而像上述的因果依赖场景我们在大数据业务比较常见, 通过构建DAG方式来描述对应的算子依赖, 以Dataflow的方式运行.识别因果一致性是取决于我们的业务层面逻辑,但是我们可以通过引入顺序性来让存储层面感知到对应的前后顺序关系,从而保证我们业务层面的因果关系一致性.

总结

对于数据复制模型, 我们已经了解了基于Leader-Base Replication, Multi-Leader Replication以及Leaderless Replication机制,并且我们也了解到不同的复制模型在对应的复制延迟上带来的问题,主要有线性一致性、数据幻读以及因果一致性问题并讨论其中的解决方案思路.