如何理解分布式领导者复制算法模型

在前面数据复制原理文章我们已经了解到数据复制是建立无共享存储架构下,存储系统每个节点通过网络连接都持有一份自己完整且相同的数据副本.而数据复制的难点在于处理复制数据的变更.数据复制算法主要有基于Leader-Based Replication、Multi-Leader Replication以及Leaderless Replication三种方式, 因篇幅内容比较多, 今天样结合《Designing Data-Intensive Applications》一书来聊聊前两种领导者数据复制算法原理.

Leader-Based Replication

谈到数据复制, 我想我们都见到一个很熟悉的名词, 即Replica. 那什么是Replica呢? 其实就是存储系统中存储一份完整的数据库副本节点我们称之为Replica.有了多个Replica, 那么我们的问题来了, 即如何确保所有的数据都能最终完整地出现在每个Replica呢? 为保证每个Replica都具备相同的数据, 因此客户端每次向数据库发起的写入操作也都需要应用到每个Replica上.

这个时候我们采用其中的一种机制, 即多个Replica中选择其中一个作为接收客户端的写入并将数据复制到其他Replica,这就是我们的Leader-Based Replication机制,我们也称之为基于领导者复制算法,也会称之为主从复制算法模型.那么其工作流程如下:

图片

• s1: 将存储系统中的多个数据副本通过共识算法选举一个leader节点, 而其他数据副本节点则成为follower节点.当客户端想要将数据写入到存储系统的时候,它们必须将请求发送给leader节点, 如果请求到follower节点, 那么follower节点会将写请求转发给leader节点, 请求路由取决于客户端是否感知到哪个数据副本为leader节点,最后由leader节点将数据写入本地存储.
• s2: 当leader节点将数据写入本地存储的同时, 它将会以指定的复制方式(同步/异步)以指定的复制格式(数据/日志/流等)发送到其他follower节点, 每个follower节点从leader中获取并解密复制格式, 然后按照leader处理写入相同的顺序应用所有写入从而相应地更新其本地数据副本.
• s3: 当客户端想要从数据库读取数据时, 它既可以查询leader数据副本, 也可以查询其他follower数据副本.

而基于上述的复制算法模型,结合之前的数据复制原理,我们的Leader-Based Replication落地实现又产生以下几种架构的变种, 即:

图片

基于单领导者复制模型, 我们更关注前面所讲的复制方式, 为什么呢? 既然数据复制是建立在网络连接情况下来进行数据同步, 那么必然存在数据一致性问题. 而数据一致性可以基于之前高可用架构设计的一致性决策框架来辅助我们进行决策.如果我要实现强一致性, 那么我的复制方式模型至少需要是同步复制方式,这个时候我们可以采用全量同步、链式同步以及半同步复制方式进行决策, 这个时候我们的同步复制方式对数据一致性的影响转向为时效性与性能上的Trade-Off问题.

怎么理解呢? 如果我追求写性能且同时需要保证读己之所写的线性一致性,那么我就采用单领导者复制的主备方式, 即读写都是走leader节点, follower节点都是备份.

如果我想提升读性能又要保证读己之所写,那么我就只能降低写性能,因为我写入数据必须要等待leader向follower节点同步复制才响应给客户端, 这个时候客户端仅从leader进行读写,从同步follower进行读操作,其他follower节点不接收读请求.这个时候就改变了架构本质,从主从架构将为部分主备架构.

同样地,如果我业务层面允许降低一致性要求,那么我就基于BASE理论考虑实现最终一致性,那么这个时候我可以采用异步数据复制方式.然而异步数据同步会带来一个新的问题,那就是存在数据丢失,因为异步存在无限延迟,我们无法知道对应的数据是不是真的同步到follower节点,如果此时follower,那么当leader发生故障时重新从follower节点之间进行选举就会发现follower节点数据缺失了leader节点上的数据.

对于这种情况,如果是缓存系统并缓存是基于sessionId维度缓存,那么我们可以直接采用异步复制,但如果是重要数据,那么就不能直接采用异步复制方式,而是需要在异步复制基础增加可靠性保证的机制,或者是切换为部分同步机制.

可见基于单领导复制算法模型,我们会面临数据丢失以及一致性问题,具体要取决于业务层面对上述两类故障类型的容忍程度.

但是它还存在一个主要缺点,那就是存在单点写故障问题,因为只有一个leader数据副本负责接受数据的写入, 所有的操作都必须经过它, 如果由于任何原因,比如存在网络分区导致无法连上leader数据副本, 那么客户端将无法向数据库写入数据.那么有什么解决方案呢?

Multi-Leader Replication

基于Leader-Based复制模型的一种自然扩展是允许多个数据副本节点接受写入操作,即Multi-Leader Replication, 当仅新增加一个Leader数据副本的时候, 我们有时也会称之为双主复制模型, 即Master-Master Replication.

对于多主复制模型,我们更多常见是做异地多活架构,一般在单数据中心做多主复制模型比较少,因为单数据中心做多主复制模型相比多数据中心多主复制模型的复杂度基本差不多,绝不会因为是单数据中心而让架构的复杂度变少,而且最重要的一点是单数据中心无法容忍数据中心级别甚至区域级别的故障,因此采用多数据中心相比单数据中心有更高的可用性,能够容忍数据中心甚至是区域级别的故障问题.

多数据中心多主复制架构如下: 我们的数据库多个Replica分布在不同的数据中心,而且每个数据中心都有一个自己的leader节点,用于接收客户端的写入请求, 并基于写入请求向其他数据中心进行异步数据复制,如下:

图片

那么单领导者复制能否也部署多数据中心呢? 其实也可以,我们可以对比下多数据中心多主复制以及多数据中心单主复制之间的差异:

图片

在我们实际落地过程中,我们的存储双主模型存在2种演进的架构变化,其他基本也是基于这两种模式进行改造演化而来. 第一种也就是我们每个数据中的数据leader副本节点是将数据异步复制到其他数据中心,即:

图片

第二种是我们基于客户端采取的双写模型,其中定时数据同步是可选的,可以思考下为啥是可选的,试想下如果是基于请求的sessionId维度缓存,那么我们其实也可以是不做数据同步的, 即:

图片

除了上述的场景, 双写为啥需要定时同步呢? 我们肯定是想消除数据一致性,即反熵,同时防止数据丢失,而且如果其中一个IDC不可用, 那么我的双写也需要增加可靠性保证,比如持久化写入日志,比如WAL机制,当IDC恢复的时候直接从另一个IDC通过日志Lag以及Offset同步增量数据.

写入冲突问题

对于多数据中心的双主复制模型,最大的问题我想很容易想到就是数据一致性以及写冲突问题.相比单主模型复杂度要高很多,关于一致性其实我们有一个之前高可用架构一致性决策框架,但框架是辅助工具而不是解决方案,在这里我们如果是要做强一致性且是多数据副本的情况下,那么需要采用共识算法来解决.

不仅如此,我们选择的共识算法决策还要结合我们对业务层面理解并采用对应的一致性模型综合考虑得出.而写冲突也会影响我们的数据一致性,而这种一致性我想我们应该要识别出来,它是在我们的FLP定理是一个安全性属性问题,即Safety属性.

写冲突就是多数据中心相互独立能够接收相同字段不同的值写入导致数据要进行持久化时无法进行判断该以什么为准.比如用户1将页面标题从A改为B，而用户2同时将标题从A改为C。每个用户的更改都在其本地领导者节点上成功应用。然而，当这些更改异步复制时，就会检测到冲突.如下:

图片

第一种方式异步变更为同步复制,那就意味着需要等待写入操作复制到所有的副本,然而如果这样做那还不如直接采用单主复制架构,因为这种方式直接将原本支持多个副本写入又间接改成单个副本写入.

第二种方式避免冲突.如何避免?就是实现逻辑上的单领导复制模型,其实就是将这个改造为逻辑分区架构,每个数据中心都有一份全量的数据,比如南方以及东南地区走IDC-1,北方以及西部区域都走IDC-2; 又或者按照范围分区,或者是hash分区等等,这样实现不同用户有不同的数据中心归属的地方.保证同一个用户不论如何请求都只会路由到在本地数据中心执行.

第三种方式是存储系统层面自动解决,比如基于时间戳按最后写入优先(LWW)或者编号较高或者较低者为准写入,但存在数据丢失风险. 在前面我们讲述了不可靠时钟带来的问题.关于这种我们需要了解对应存储系统的复制模型以及冲突解决机制.一般我们是不能太依赖于存储系统来帮助我们解决所有的事情.

关于自动冲突解决方案,业界也有一些研究方向可以参考:

图片

第四种是自定义冲突解决逻辑,即取决于我们业务应用场景,即采用编写代码逻辑来解决,也就是我们可以通过写入检测到复制日志与写入数据冲突并通知冲突处理程序保存多个版本,然后当读取时返回多个版本给用户让用户解决冲突.

图片

多主复制数据传播路径

如果我们把双主复制模型扩展到多主复制模型,那么这个每个leader需要将其写入操作发送到其他数据中心的leader,即数据复制通信路径.那么在多主复制模型中存在以下3种通信路径,我们可以采用复制拓扑结构来进行描述如下:

图片

• All-to-All拓扑: 最通用的拓扑结构是All-to-All方式,即每个领导者将其写入操作发送给其他所有的领导者.
• Circular拓扑: 在这种通信路径中,每个节点从另一个节点接收写入操作,并将这些写入操作加上自身的任何写入操作转发给另一个节点.
• Star 拓扑: 也称之树形拓扑, 一个指定的root节点将写入操作转发给其他所有节点.

对于Star以及Circular拓扑结构,一次写入操作可能需要经过几个节点才能到达所有副本节点,因此节点需要转发它们从其他节点收到的数据变更.但是为防止无限复制循环,每个节点都被赋予一个唯一标识符,比如节点自身的ID,那么在复制日志中每次写入操作都标记有它所经过的所有节点标识符.这样当一个节点接收到其他节点数据变更日志带有自身的标识将自动忽略,表示已处理过.

对于Star以及Circular还存在一个问题是如果仅有一个节点发生故障就有可能中断整个复制日志流,因此需要手动配置绕过故障节点.而对于All-to-All拓扑结构则容错性更好可以沿着不同的路径进行传播,避免单点故障.

但是对于All-to-All结构,也存在一个数据跳跃问题,即下面的leader节点更新到数据value=2,但是由于网络延迟原有的value=1还未同步到leader2,也就是还未进行insert动作就操作了update导致数据出错,也许这里出错可能过一会再做重试可以解决.

图片

但是如果这里的insert是改成update操作呢, 那么这个时候leader2节点就会执行update更新数据导致数据错乱,在这里我们识别会存在一个一致性前缀读,也就是存在因果关系,那么这个时候我们可以考虑采用版本向量来标记每个操作的顺序,其中版本向量具备单调且唯一性,这个时候我们复制数据更新就可以通过重试+版本向量解决数据冲突问题.

至此我们已介绍多主复制模型,可以看到实现这样的复制模型要考虑的点不仅仅是数据一致性问题,还需要考虑写入冲突以及消息传播结构,在共识算法中实现消息传播的协议就是我们熟悉的Gossip协议.通过Gossip协议来修复我们的数据一致性问题.同时Gossip协议也将是接下来解决我们无领导复制模型数据一致性的重要手段.关于无领导复制模型留着下次再讲.

总结

今天主要讲述基于领导者复制算法模型及其可能存在的问题,当我们要基于存储系统做高可用数据复制架构的时候, 那么我们就需要关注对应的复制算法模型优缺点以及可能带来的复杂度问题,这样当我们落地的时候就能过结合对应的存储系统文档更加全面地去测试我们的存储系统,以确保它能够提供具备我们认为的保障.