分布式应用CAP定理BASE理论

1985年Lynch证明了异步通信中不存在任何一致性的分布式算法(FLP Impossibility),2002年Lynch等人证明了Eric Brewer2000年提出的CAP猜想。

以下是Ebay架构师Dan Pritchett对BASE的理论。

在分区场景的数据库中,为可用性降低一些一致性,能显著提高可伸缩性。在过去的十年中,Web应用越来越受欢迎。无论是为普通用户,还是专为开发者构建的应用,都希望的应用伴随着业务的增长得到广泛的使用,如果应用依赖于持久化,那么数据存储就会成为瓶颈。

扩展应用有两种策略,垂直扩展和水平扩展。垂直扩展相对比较简单,将应用程序部署到更大型的计算机上,垂直扩展对数据而言很合理,但有几个局限性,最明显是超出了现有系统的最大容量,垂直扩展成本很昂贵,业务量增加通常需要购买更大型的计算机系统,通常还会因为厂商锁定,而进一步增加成本。

水平扩展提供了相当的灵活性,但也更加复杂。数据水平扩展可以从两方面入手,扩展涉及按功能划分数据,和按数据库划分功能;按功能划分数据,会跨多个数据库或分片(sharding),图1展示了数据水平扩展的策略。

An-Acid-Alternative

如图所示,应用程序水平扩展的两种方法可以同时使用。用户、产品和业务可以位于不同的库中。另外,每个功能分区,可根据业务量拆分成多个数据库。如图上所示,每个功能分区可以彼此独立扩展。

功能分区(Functional Partitioning)

功能划分对实现高度可伸缩性非常重要。所以,好的数据库架构都支持按功能划分表。如:按用户、产品、业务、通讯等进行功能划分。通常利用数据库中的一些概念(如外键),保持这些功能分区间的一致性。

依靠数据库约束来确保,跨区域各组功能的一致性,这种模式会引发数据库部署策略上的耦合。使用这种约束,所有的表只能驻留在单机数据库服务器上,随着业务量的增长,水平扩展的问题会突显。

通常情况下,最容易做到的水平扩展,是将数据按功能划分,离散存放到多台数据库服务器上。将不同功能的数据,存放在不同的数据库服务器上,可以满足极高业务量的要求。这就需要把数据约束,从数据库转移到应用程序上,因此,就有了本文后面讨论的几个挑战。

CAP理论(CAP Theorem)

加州大学伯克利分校的教授,Inktomi的联合创始人兼首席科学家:埃里克·布鲁尔(Eric Brewer)猜测,Web服务无法同时满足以下三个属性。

一致性(Consistency):

客户端感觉一次就完成了一系列的操作。

The client perceives that a set of operations has occurred all at once.

可用性(Availability):

所有的操作必需在预期的响应中结束。

Every operation must terminate in an intended response.

分区容差/容错(Partition tolerance)

所有的操作都应完成,即使个别组件不可用。

Operations will complete, even if individual components are unavailable.

按理讲,一个基于数据库设计的Web应用,最多只能够支持以上两种特性,很明显,所有的水平扩展策略,都基于数据分区(any horizontal scaling strategy is based on data partitioning),所以,设计者们只能在一致性,与可用性之间做选择。

ACID解决方案(ACID Solutions)

数据库事务ACID,大大简化了应用程序开发者的工作。正如首字母缩写那样,ACID事物提供了以下保证:

原子性:

事务中的所有操作要么全被完成,要么一个也不执行。

一致性:

数据库中的状态与事务开始和结束时保持一致。

隔离性:

事务会表现为当前运行在数据库上的操作只有一个。

持久性:

基于事物的操作,在事物完成后不能被推翻。

2PC(两阶段提交)

数据库供应商很早就认识到,需要对数据库进行分区,并引入了一种称为2PC(两阶段提交)的技术,用于跨多个数据库实例提供ACID保证。该协议分为两个阶段:

1、一阶段,事物协调者询问每个涉及到预提交操作的数据库,是否可以进行提交,如果所有的数据库都同意提交,则开始第二个阶段。

2、二阶段,事物协调者要求每个数据库提交数据。

如果任何一个数据库否决了当前提交,所有数据库涉及到的这部分事物都会被要求回滚。

缺点

获得了跨分区(across  partitions)的一致性。

We are getting consistency across partitions

如果Brewer是正确的,那么,必然影响可用性,但这怎么可能呢?任何一个系统的可用性,直接影响到一个操作过程中,所牵涉到的组件的可用性。

该声明的最后部分极为重要,组件可能会被调用,但不是必然被调用,则不会削弱系统的可用性。在一个汲及到多数据库的两阶段提交的事物中,这里的可用性直接关系到每个数据库的可用性。

例如,假设每个数据库的可用性为99.9%,那么事务的总体可用性变为99.8%,等同于每月会停机43分钟。

ACID的替代方案(An ACID Alternative)

如果ACID为分区数据库提供了一致性选择,那么,如何实现可用性呢?

答案就是BASE(基本可用,弱一致,最终一致)。

BASE与ACID截然相反,悲观的ACID,强制每个操作结束时的一致性。

乐观的BASE所接受的数据库一致性,是从不断变动的状态中演变而来。虽然这听起来不可思议,实际上它相当好管理,并且可扩展性达到了前所未有的高度,是ACID无法企及的。

BASE的可用性定义建立在,把局部失败排出在整个系统的失败之外来达成的。

这里有个简单的例子,如果用户分区跨越5个数据库,BASE设计,鼓励以这样的方式进行分解操作:

一个用户数据库的失败,仅影响20%的用户(只有运行在那台服务上的用户受影响)。没有过多复杂的魔法,但这样做确实提高了系统的可用性,所以,现在把数据分解到各个功能分组中,并把最繁忙的分组,分成跨多个数据库。

如何把BASE应用到程序中,相对于典型地ACID常规的操作,BASE需要做更深入的分析。应该寻找什么呢? 以下部分提供了一些方向。

一致性模式(Consistency Patterns)

按照Brewer的推测,如果,BASE允许在分区数据库中提供可用性,可以确定的是,必须从放宽一致性入手,这通常很困难,因为,业务干系人和开发人员,都倾向主张一致性才是应用程序成功的关键,不能对用户隐藏短暂的不一致性,所以,开发者与产品负责人,必需投身到放宽一致性的PK中。

图2是一个简单的模式,演示了BASE中一致性所应注意的事项。

An-Acid-Alternative-fig2

这张用户表,包含了当前用户的信息和进出账的汇总。这些是运行总计,交易表保存了每笔交易,所涉及的卖方和买方以及交易金额。这些是对真实表的简化,但足以表达关于一致性方面的必需元素。

通常,放宽各个功能组间的一致性,比在功能组内更容易。示例模式中有两个功能组:用户和交易。每次销售商品时,都会在交易表中新增一行,并更新买家和卖家的钱。

使用ACID方式的事务,SQL如图3所示。

An-Acid-Alternative-fig3

出入账的信息在用户表中,可识为是业务表的缓存。这是为提高系统的效率。鉴于此,可放宽对一致性的约束,一次交易中,不立即显示买方和卖方交易账户中的余额,这并不罕见,事实上人们经常见到,在交易和余额之间的这种延迟(例如,ATM取款和手机通话)。

如何修改SQL语句以放宽一致性,取决于如何定义余额(running balances)。如果,它们只是个大概,这意味着可能会遗漏一些交易,这样的改动就相当简单,如图4所示:

An-Acid-Alternative-fig4

现在我们成功把这个更新,从用户表和业务表中分离出来,表之间的一致性已经不能保证。事实上,第一个事物与第二个事物之间的失败,会导致用户表的中的结果开始出现不一致。但是按事前的约定,这个活动的总额是一个估计值,基于这一点这就够了。但如果估计值不可接受怎么办?怎么能解耦用户和交易之间的更新呢?

引入一个持久化的消息队列,可以解决此问题,实现持久性消息有多种选择,但最关键的因素是队列的实现,无论如何,需要确保是建立在像数据库这样的,具有持久性为后盾的基础上,这就必需要求队列的事物提交,不是一个两阶段的提交(2PC)。现在SQL操作看起来有点不同,如图5所示:

An-Acid-Alternative-fig5

这个例子采取了比较宽泛的语法,和相对简化的逻辑来说明这个概念。

在一个insert操作的事物中,用一个队列把消息做了持久化,此消息包含了更新用户账户余额(running balances)所需要的信息。该事务包含一个单机数据库实例,因此,不会削弱系统的可用性。消息处理单元将每条消息从队列中取出,然后,更新用户表。

该示例似乎解决了所有问题,但是,有一个问题,这个消息是基于本地事物,从而避免了两阶段提交。如果,消息被消费时包含一个事物,涉及用户表所在的主机,仍然会有2PC情况发生。

一种针对2PC的解决方案,消息处理组件什么都不做,把更新操作扔给一个后端组件去做,以保证对公开组件的可用性。消息处理器的较低可用性,对于业务需求是能够接受的。但如果2PC在系统中根本不可接受,该如何解决呢?

首先,需要了解幂等性的概念,如果一个操作,可以应用一次或多次但结果相同,那就么这个操作,就被认为是具有幂等性的。

幂等操作是有效的,因为它们允许部分失败,重复应用它们不会改变系统中的最终状态。在谈到幂等性问题时,选择这样一个示例是有问题的,更新操作很少会是幂等的,示例中增加余额的地方,不止一次的操作明显会让余额不正确。

即便是简单的值更新操作,在操作顺序方面也不是幂等的,如果,系统不能保证按接收顺序进行更新,则系统中的最终状态将会不正确,稍后会详细介绍。

在余额更新这个案例中,需要一个方法跟踪哪些更新操作是成功的,哪些是未完成的,一种技巧是使用一张表,记录已经处理的事物。图6中的表,展示已经被更新了的业务ID以及用户ID和余额,

An-Acid-Alternative-fig6

图7是示例的伪代码。

An-Acid-Alternative-fig7

这个示例,基于队列中可以查看到的消息,并在成功处理后删除,如有必要,可使用两个独立的事务来完成:一个用于消息队列,另一个用于用户表的数据,除非数据库操作成功提交,否则,队列操作不会提交。

该算法支持部分失败,并提供事务保证,而无需借助两阶段提交(2PC)。如果,只关注顺序,有一个简单的技巧用于幂等更新,稍微改变一下示例模式,来举例说明所遇到的挑战和解决方案(参见图8)

An-Acid-Alternative-fig8

假设还想跟踪用户的最后一次销售/购买日期,可以采用类似的方案来更新日期,但有一个问题。假设在短时间内发生了两次购买,消息系统无法确保订购操作。现在面临的情况是,根据消息的处理顺序,将导致last_purchase的值不正确,幸运的是,可以通过对SQL的一个小修改来处理这种更新,如图9所示:

An-Acid-Alternative-fig9

这里不允许last_purchase等于当下要操作的时间,这样更新就不再依赖于顺序,还可以使用此方法来保护更新,免受无序更新的影响。作为时间的替代方案,还可以尝试用自增的事务ID。

消息队列的顺序(Ordering of Message Queues)

这一小节与消息的投递顺序有关,消息系统提供了确保消息按接收顺序递送的能力。这种支持代价很大,并且不一定需要,实际上有时会给人一种虚假的安全感。这里的示例,展示了如何降低对消息顺序的依赖,并且保持数据库层面的一致性。

上面提到的降低对顺序的依赖是微不足道的,大多消息系统很少强制顺序。此外,无论交互方式如何,Web应用程序,在语义上都是事件驱动的系统,客户端请求以任意顺序到达系统,每个请求所需的处理时间不同,整个系统组件的请求调度是不确定的,从而导致消息队列的不确定性,要求保留顺序会产生虚假的安全感,简单来说不明确的输入导致不明确的输出。

弱一致和最终一致(Soft State/Eventually Consistent)

到目前为止,一直在关注交易一致性中的可用性,接下的部分,是理解弱一致和最终一致对应用设计的影响。作为软件工程师,更倾向于将系统视为闭环,考虑其给定的输入产生预期的输出,这种可预测性,是创建正确软件系统的必要条件。好消息是,很多使用BASE的闭环系统中,并没有改变其可预测性,但这需要从系统整体状态的角度来看。一个简单的例子可以帮助说明这一点。

考虑一个资产转移的系统,资产的类型无关紧要,它可以是游戏中的金钱或物品。对于这个例子,假设已经对两个操作进行了解耦,即从一个用户那里拿走资产,通过消息队列,转给另一个用户的动作,这时,系统就出现了不确定性问题。

在一段时间内会出现,资产已经离开一个用户,而没有到达另一个用户,该时间窗口的大小,由消息传递系统设计决定。不管怎样,在开始与结束的状态之间会产生一个滞后,而表现出来的是两个用户都没拥有这个资产。

如果从用户的角度去考虑会怎样,这种滞后就可能是无关紧要的,甚至是不得而知的。接收的用户和发送的用户,都不知道资产何时到达,如果,发送和接收之间的延迟是几秒钟,对于用户来说,它将是不可见的,或是可以容忍的。在这种情况下,系统行为被认为是一致的,并且,是用户可接受的,即使用弱一致和最终一致性去实现。

事件驱动的架构(Event-Driven Architecture)

如果需要知道状态在何时会变成一致该怎么做?

可能需要一种算法,并把它用到状态上,仅在它与传入请求达成一致状态时。有一个简单的办法是,在状态变成一致时生成事件。

如果需要通知用户资产已到达,该怎么做?

在用户收到资产的(commits)事物中创建一个事件,提供一种机制一旦状态到达就执行。

Creating an event within the transaction that commits the asset to the receiving user provides a mechanism for performing further processing once a known state has been reached. 

EDA(事件驱动架构)可以在可伸缩性,和架构解耦方面提供显着改进。关于EDA应用的进一步讨论超出了本文的范围。

结论(Conclusion)

将系统的事物搞的有声有色,需要一种新的思维方式来规划资源,当需要把负载分布在大量组件上,传统的事务模型是有问题的。对操作进行解耦并依次执行它们,提高了可用性和扩展性,但也牺牲了一致性,BASE提供对这种解耦模型的思考。