分布式一致性

分布式一致性

数据一致性的概念源于数据系统中的概念,我们可以简单的把一致性理解为正确性或者完整性,那么数据一致性通常指关联数据之间的逻辑关系是否正确和完整。在数据库系统中通常用事务,即访问并可能更新数据库中各种数据项的一个程序执行单元,来保证数据的一致性和完整性。在分布式系统中,为了保证数据的可靠性与性能,我们不可避免的对数据进行复制与多节点存储,而数据一致性主要为了解决分布式多个存储节点情况下怎么保证逻辑上相同的副本能够返回相同的数据。

分布式系统的设计核心之一就在一致性的实现和妥协,我们需要选择合适的算法来保证不同节点之间的通信和数据达到无限趋向一致性。实际情况下,保证不同节点在充满不确定性网络环境下能达成相同副本的一致性是非常困难的,我们需要从分布式时钟,分布式事务与一致性算法等不同的方面进行考虑。

一致性问题

由于采用多机器进行分布式部署的方式提供服务,必然存在着数据的复制。分布式系统的数据复制需求主要来源于以下两个原因:

  • 可用性:将数据复制到分布式部署的多台机器中,可以消除单点故障。防止系统由于某台(些)机器宕机导致的不可用。

  • 性能:通过负载均衡技术,能够让分布在不同地方的数据副本全都对外提供服务。有效提高系统性能。

在分布式系统引入复制机制后,不同的数据节点之间由于网络延时等原因很容易产生数据不一致的情况。复制机制的目的是为了保证数据的一致性。但是数据复制面临的主要难题也是如何保证多个副本之间的数据一致性。如何能既保证数据一致性,又保证系统的性能,是每一个分布式系统都需要重点考虑和权衡的。

在实际的分布式系统中,我们常常会面临以下具体的场景:

  • 比如在集中式系统中,有一些关键的配置信息,可以直接保存在服务器的内存中,但是在分布式系统中,如何保存这些配置信息,又如何保证所有机器上的配置信息都保持一致,又如何保证修改一个配置能够把这次修改同步到所有机器中,就是存在的问题。

  • 在集中式系统中,进行一个同步操作要写同一个数据的时候,可以直接使用事务+锁来管理保证数据的 ACID。但是,在分布式系统中如何保证多台机器不会同时写同一条数据。

一致性模型

分布式系统常常通过数据的复制来提高系统的可靠性和容错性,并且将数据的副本存放到不同的机器上,由于多个副本的存在,使得维护副本一致性的代价很高。因此,许多分布式系统都采用弱一致性或者是最终一致性,来提高系统的性能和吞吐能力,这样不同的一致性模型也相继被提出。

强一致性/原子一致性/线性一致性

所谓的强一致性(Strict Consistency),也称为原子一致性(Atomic Consistency)或者线性(Linearizability)。 它对一致性的要求两个:

  • 任何一次读都能读到某个数据的最近一次写的数据。

  • 系统中的所有进程,看到的操作顺序,都和全局时钟下的顺序一致。

强一致性要求无论数据的更新操作是在哪个副本上执行,之后所有的读操作都要能够获取到更新的最新数据。对于单副本的数据来说,读和写都是在同一份数据上执行,容易保证强一致性,但对于多副本数据来说,若想保障强一致性,就需要等待各个副本的写入操作都执行完毕,才能提供数据的读取,否则就有可能数据不一致,这种情况需要通过分布式事务来保证操作的原子性,并且外界无法读到系统的中间状态。

显然这强一致性对全局时钟有非常高的要求。强一致性,只是存在理论中的一致性模型,比它要求更弱一些的,就是顺序一致性。

顺序一致性

顺序一致性(Sequential Consistency),也同样有两个条件,其一与前面强一致性的要求一样,也是可以马上读到最近写入的数据,然而它的第二个条件就弱化了很多,它允许系统中的所有进程形成自己合理的统一的一致性,不需要与全局时钟下的顺序都一致。这里的第二个条件的要点在于:

  • 系统的所有进程的顺序一致,而且是合理的,就是说任何一个进程中,这个进程对同一个变量的读写顺序要保持,然后大家形成一致。

  • 不需要与全局时钟下的顺序一致。

可见,顺序一致性在顺序要求上并没有那么严格,它只要求系统中的所有进程达成自己认为的一致就可以了,即错的话一起错,对的话一起对,同时不违反程序的顺序即可,并不需要个全局顺序保持一致。

  • 图 a 是满足顺序一致性,但是不满足强一致性的。原因在于,从全局时钟的观点来看,P2 进程对变量 X 的读操作在 P1 进程对变量 X 的写操作之后,然而读出来的却是旧的数据。但是这个图却是满足顺序一致性的,因为两个进程 P1,P2 的一致性并没有冲突。从这两个进程的角度来看,顺序应该是这样的:Write(y,2) , Read(x,0) , Write(x,4), Read(y,2),每个进程内部的读写顺序都是合理的,但是显然这个顺序与全局时钟下看到的顺序并不一样。

  • 图 b 满足强一致性,因为每个读操作都读到了该变量的最新写的结果,同时两个进程看到的操作顺序与全局时钟的顺序一样,都是 Write(y,2) , Read(x,4) , Write(x,4), Read(y,2)。

  • 图 c 不满足顺序一致性,当然也就不满足强一致性了。因为从进程 P1 的角度看,它对变量 Y 的读操作返回了结果 0。那么就是说,P1 进程的对变量 Y 的读操作在 P2 进程对变量 Y 的写操作之前,这意味着它认为的顺序是这样的:write(x,4) , Read(y,0) , Write(y,2), Read(x,0),显然这个顺序又是不能被满足的,因为最后一个对变量 x 的读操作读出来也是旧的数据。因此这个顺序是有冲突的,不满足顺序一致性。

弱一致性

弱一致性指的是系统的某个数据被更新后,后续对该数据的读取操作,取到的可能是更新前的值,也可能是更新后的值,全部用户完全读取到更新后的数据,需要经过一段时间,这段时间称作“不一致性窗口”。

系统并不保证续进程或者线程的访问都会返回最新的更新过的值。系统在数据写入成功之后,不承诺立即可以读到最新写入的值,也不会具体的承诺多久之后可以读到。但会尽可能保证在某个时间级别(比如秒级别)之后,可以让数据达到一致性状态。

最终一致性

弱一致性的特定形式,系统保证用户最终能够读取到某个操作对系统的更新。在没有故障发生的前提下,不一致窗口的时间主要受通信延迟,系统负载和复制副本的个数影响。DNS 是一个典型的最终一致性系统。

最终一致性同样存在着很多的变种,最终一致性的不同方式可以进行组合,例如单调读一致性和读己之所写一致性就可以组合实现。并且从实践的角度来看,这两者的组合,读取自己更新的数据,和一旦读取到最新的版本不会再读取旧版本,对于此架构上的程序开发来说,会少很多额外的烦恼。

Casual Consistency | 因果一致性

如果 A 进程在更新之后向 B 进程通知更新的完成,那么 B 的访问操作将会返回更新的值。如果没有因果关系的 C 进程将会遵循最终一致性的规则。因果一致性(Casual Consistency)在一致性的要求上,又比顺序一致性降低了:它仅要求有因果关系的操作顺序得到保证,非因果关系的操作顺序则无所谓。

因果相关的要求是这样的:

  • 本地顺序:本进程中,事件执行的顺序即为本地因果顺序。

  • 异地顺序:如果读操作返回的是写操作的值,那么该写操作在顺序上一定在读操作之前。

  • 闭包传递:和时钟向量里面定义的一样,如果 a->b,b->c,那么肯定也有 a->c。

  • 图 a 满足顺序一致性,因此也满足因果一致性,因为从这个系统中的四个进程的角度看,它们都有相同的顺序也有相同的因果关系。

  • 图 b 满足因果一致性但是不满足顺序一致性,这是因为从进程 P3、P4 看来,进程 P1、P2 上的操作因果有序,因为 P1、P2 上的写操作不存在因果关系,所以它们可以任意执行。不满足一致性的原因,同上面一样是可以推导出冲突的情况来。

其他一致性模型

读己所写一致性

因果一致性的特定形式。一个进程总可以读到自己更新的数据。

会话一致性

读己所写一致性的特定形式。进程在访问存储系统同一个会话内,系统保证该进程读己之所写。

单调读一致性

如果一个进程已经读取到一个特定值,那么该进程不会读取到该值以前的任何值。

单调写一致性

系统保证对同一个进程的写操作串行化。

一致性保障

实现分布式系统一致性,首先需要考虑的就是分布式时钟,我们需要解决不同节点之间的标准时间问题。从最初的网络时间协议(NTP)到逻辑时钟到向量时钟,较好地解决了不同节点间的顺序问题。CALM 原则的全称是 Consistency and Logical Monotonicity,主要描述的是分布式系统中单调逻辑与一致性的关系:

  • 在分布式系统中,单调的逻辑都能保证最终一致性,这个过程中不需要依赖中心节点的调度。

  • 任意分布式系统,如果所有的非单调逻辑都有中心节点调度,那么这个分布式系统就可以实现最终一致性。

接下来我们需要考虑合适的数据结构进行节点间的数据同步与合并,这也是一致性算法的前提,设计良好的数据结构加上精妙的算法可以高效的解决现实的问题。分布式系统的数据结构 CRDT(Conflict-Free Replicated Data Types) 即是分布式系统中被广泛采用的数据结构:

  • 基于状态(state-based):即将各个节点之间的 CRDT 数据直接进行合并,所有节点都能最终合并到同一个状态,数据合并的顺序不会影响到最终的结果。

  • 基于操作(operation-based):将每一次对数据的操作通知给其他节点。只要节点知道了对数据的所有操作(收到操作的顺序可以是任意的),就能合并到同一个状态。

最后需要来关注一下分布式系统的一些重要的协议 HATs(Highly Available Transactions),ZAB(Zookeeper Atomic Broadcast),这些往往是基于业界主流的一致性算法,譬如 Paxos, Raft 以及 Gossip 等。

链接