2008 年 7 月 28 日
第 6 卷，第 3 期

Base：一种 ACID 的替代方案

在分区数据库中，为了可用性而牺牲一些一致性可以显著提高可扩展性。

Dan Pritchett，Ebay

在过去的十年中，Web 应用程序的普及程度不断提高。无论您是为最终用户还是应用程序开发人员（即服务）构建应用程序，您最希望的是您的应用程序能够被广泛采用——并且随着广泛采用，交易量也会随之增长。如果您的应用程序依赖于持久性，那么数据存储可能会成为您的瓶颈。

扩展任何应用程序都有两种策略。第一种，也是迄今为止最简单的一种，是垂直扩展：将应用程序迁移到更大的计算机上。垂直扩展对于数据来说效果相当好，但也有一些限制。最明显的限制是超出可用最大系统的容量。垂直扩展也很昂贵，因为增加事务处理能力通常需要购买下一个更大的系统。垂直扩展通常会造成供应商锁定，进一步增加成本。

水平扩展提供了更大的灵活性，但也复杂得多。水平数据扩展可以沿两个向量执行。功能性扩展涉及按功能对数据进行分组，并将功能组分散到各个数据库中。在功能区域内跨多个数据库拆分数据，或分片¹，为水平扩展增加了第二个维度。图 1 中的图表说明了水平数据扩展策略。

如图 1 所示，水平扩展的两种方法可以同时应用。用户、产品和交易可以在不同的数据库中。此外，每个功能区域可以跨多个数据库进行拆分，以实现事务处理能力。如图所示，功能区域可以彼此独立地进行扩展。

功能分区

功能分区对于实现高度可扩展性至关重要。任何良好的数据库架构都会将模式分解为按功能分组的表。用户、产品、交易和通信是功能区域的示例。利用外键等数据库概念是维护这些功能区域之间一致性的常用方法。

依赖数据库约束来确保跨功能组的一致性，会将模式与数据库部署策略耦合起来。为了应用约束，表必须驻留在单个数据库服务器上，从而随着事务率的增长而排除水平扩展。在许多情况下，最简单的横向扩展机会是将功能数据组移动到离散的数据库服务器上。

可以扩展到非常高的事务量的模式会将功能上不同的数据放在不同的数据库服务器上。这需要将数据约束从数据库中移出并移入应用程序中。这也引入了将在本文后面讨论的几个挑战。

CAP 定理

加州大学伯克利分校教授、Inktomi 的联合创始人兼首席科学家 Eric Brewer 提出了一个猜想，即 Web 服务无法同时确保以下所有三个属性（用首字母缩略词 CAP 表示）：²

一致性。 客户端感知到一组操作已同时发生。

可用性。 每个操作都必须以预期的响应终止。

分区容错性。 即使单个组件不可用，操作也会完成。

具体来说，对于任何数据库设计，Web 应用程序最多只能支持这三个属性中的两个。显然，任何水平扩展策略都基于数据分区；因此，设计人员被迫在一致性和可用性之间做出选择。

ACID 解决方案

ACID 数据库事务极大地简化了应用程序开发人员的工作。顾名思义，ACID 事务提供以下保证

原子性。 事务中的所有操作都将完成，或者都不完成。

一致性。 数据库在事务开始和结束时都将处于一致状态。

隔离性。 事务的行为就好像它是对数据库执行的唯一操作。

持久性。 事务完成后，操作将不会被撤销。

数据库供应商很久以前就认识到分区数据库的需求，并引入了一种称为 2PC（两阶段提交）的技术，用于在多个数据库实例之间提供 ACID 保证。该协议分为两个阶段

首先，事务协调器要求每个涉及的数据库预提交操作，并指示提交是否可能。如果所有数据库都同意可以进行提交，则阶段 2 开始。
事务协调器要求每个数据库提交数据。

如果任何数据库否决提交，则要求所有数据库回滚其事务部分。缺点是什么？我们正在跨分区获得一致性。如果 Brewer 是正确的，那么我们一定是在影响可用性，但这怎么可能呢？

任何系统的可用性都是操作所需组件的可用性的乘积。该声明的最后一部分最重要。系统可能使用但非必需的组件不会降低系统可用性。涉及两个数据库的 2PC 提交的事务的可用性将是每个数据库的可用性的乘积。例如，如果我们假设每个数据库的可用性为 99.9%，那么事务的可用性将变为 99.8%，或者每月额外停机 43 分钟。

ACID 的替代方案

如果 ACID 为分区数据库提供了一致性选择，那么您如何实现可用性呢？一种答案是 BASE（基本可用、软状态、最终一致性）。

BASE 与 ACID 完全相反。ACID 是悲观的，并在每个操作结束时强制执行一致性，而 BASE 是乐观的，并接受数据库一致性将处于不断变化的状态。虽然这听起来难以应对，但实际上它是非常可管理的，并且可以实现 ACID 无法获得的可扩展性水平。

BASE 的可用性是通过支持部分故障而不是完全系统故障来实现的。这是一个简单的示例：如果用户分布在五个数据库服务器上，BASE 设计鼓励以这样一种方式设计操作，即用户数据库故障仅影响该特定主机上 20% 的用户。没有涉及任何魔法，但这确实提高了系统的感知可用性。

因此，既然您已将数据分解为功能组，并将最繁忙的组分区到多个数据库中，您如何在应用程序中集成 BASE 呢？与通常应用于 ACID 的情况相比，BASE 需要对逻辑事务中的操作进行更深入的分析。您应该寻找什么？以下部分提供了一些方向。

一致性模式

根据 Brewer 的猜想，如果 BASE 允许分区数据库中的可用性，那么必须识别出放宽一致性的机会。这通常很困难，因为业务利益相关者和开发人员的趋势都是断言一致性对于应用程序的成功至关重要。时间上的不一致性无法对最终用户隐藏，因此工程和产品负责人必须都参与选择放宽一致性的机会。

图 2 是一个简单的模式，说明了 BASE 的一致性考虑因素。用户表保存用户信息，包括总销售额和购买额。这些都是运行总计。事务表保存每个事务，关联卖方和买方以及事务金额。这些是对真实表的粗略简化，但包含说明一致性几个方面所需的元素。

一般来说，跨功能组的一致性比功能组内的一致性更容易放宽。示例模式有两个功能组：用户和事务。每次出售商品时，都会向事务表添加一行，并更新买方和卖方的计数器。使用 ACID 风格的事务，SQL 语句如图 3 所示。

用户表中的总购买额和总销售额列可以被视为事务表的缓存。它的存在是为了提高系统效率。鉴于此，可以放宽对一致性的约束。可以设置买方和卖方的期望，以便他们的运行余额不会立即反映交易结果。这并不罕见，事实上，人们经常遇到交易与其运行余额之间的延迟（例如，ATM 取款和手机通话）。

如何修改 SQL 语句以放宽一致性取决于如何定义运行余额。如果它们只是估计值，意味着可能会遗漏一些交易，则更改非常简单，如图 4 所示。

我们现在已将对用户表和事务表的更新解耦。表之间的一致性无法保证。事实上，第一次和第二次事务之间的失败将导致用户表永久不一致，但如果合同规定运行总计是估计值，这可能是足够的。

如果估计值不可接受怎么办？您如何仍然解耦用户和事务更新？引入持久消息队列可以解决这个问题。实现持久消息有多种选择。但是，实现队列最关键的因素是确保后备持久性与数据库位于同一资源上。这是必要的，以便允许队列在事务上提交，而无需涉及 2PC。现在 SQL 操作看起来有点不同，如图 5 所示。

此示例在语法上做了一些简化，并过度简化了逻辑以说明概念。通过在与插入相同的事务中排队持久消息，已捕获更新用户运行余额所需的信息。事务包含在单个数据库实例上，因此不会影响系统可用性。

单独的消息处理组件将取消队列每个消息，并将信息应用于用户表。该示例似乎解决了所有问题，但存在一个问题。消息持久性位于事务主机上，以避免在排队期间出现 2PC。如果在涉及用户主机的事务中取消队列消息，我们仍然会遇到 2PC 情况。

消息处理组件中 2PC 的一种解决方案是什么都不做。通过将更新解耦到单独的后端组件中，您可以保留面向客户的组件的可用性。消息处理器的较低可用性可能对于业务需求是可以接受的。

但是，假设 2PC 在您的系统中根本不可接受。如何解决这个问题？首先，您需要了解幂等性的概念。如果一个操作可以应用一次或多次，结果相同，则该操作被认为是幂等的。幂等操作很有用，因为它们允许部分失败，因为重复应用它们不会更改系统的最终状态。

在寻找幂等性时，所选示例存在问题。更新操作很少是幂等的。该示例就地递增余额列。显然，多次应用此操作将导致不正确的余额。然而，即使只是设置值的更新操作，在操作顺序方面也不是幂等的。如果系统无法保证更新将按照接收顺序应用，则系统的最终状态将不正确。稍后会详细介绍这一点。

在余额更新的情况下，您需要一种方法来跟踪哪些更新已成功应用，哪些更新仍在待处理。一种技术是使用一个表来记录已应用的事务标识符。

图 6 所示的表跟踪事务 ID、已更新的余额以及应用余额的用户 ID。现在我们的示例伪代码如图 7 所示。

此示例依赖于能够查看队列中的消息并在成功处理后将其删除。如果需要，这可以使用两个独立的事务来完成：一个在消息队列上，一个在用户数据库上。除非数据库操作成功提交，否则队列操作不会提交。该算法现在支持部分失败，并且仍然提供事务性保证，而无需诉诸 2PC。

如果唯一关注的是排序，则有一种更简单的技术可以确保幂等更新。让我们稍微更改一下我们的示例模式，以说明挑战和解决方案（参见图 8）。假设您还想跟踪用户的最后销售和购买日期。您可以依赖类似的方案，使用消息更新日期，但存在一个问题。

假设在短时间内发生了两次购买，并且我们的消息系统不保证有序操作。您现在会遇到这样一种情况，即根据消息的处理顺序，您将获得不正确的 last_purchase 值。幸运的是，这种更新可以通过对 SQL 进行少量修改来处理，如图 9 所示。

通过简单地不允许 last_purchase 时间倒退，您使更新操作与顺序无关。您也可以使用此方法来防止任何更新免受乱序更新的影响。作为使用时间的替代方法，您也可以尝试单调递增的事务 ID。

消息队列的排序

关于有序消息传递的简短旁注是相关的。消息系统提供了确保消息按照接收顺序传递的能力。支持这一点可能很昂贵，而且通常是不必要的，事实上，有时会给人一种虚假的安全感。

此处提供的示例说明了如何放宽消息排序，并且仍然最终提供数据库的一致性视图。放宽排序所需的开销很小，并且在大多数情况下远小于在消息系统中强制执行排序的开销。

此外，Web 应用程序在语义上是一个事件驱动的系统，无论交互风格如何。客户端请求以任意顺序到达系统。每个请求所需的处理时间各不相同。整个系统组件的请求调度是不确定的，导致消息的非确定性排队。要求保留顺序会给人一种虚假的安全感。简单的现实是，非确定性输入将导致非确定性输出。

软状态/最终一致性

到目前为止，重点一直放在为了可用性而牺牲一致性上。另一方面是了解软状态和最终一致性对应用程序设计的影响。

作为软件工程师，我们倾向于将我们的系统视为闭环。我们根据可预测的输入产生可预测的输出来考虑其行为的可预测性。这对于创建正确的软件系统是必要的。在许多情况下，好消息是使用 BASE 不会改变系统作为闭环的可预测性，但它确实需要从整体上看待行为。

一个简单的例子可以帮助说明这一点。考虑一个用户可以将资产转移给其他用户的系统。资产类型无关紧要——它可以是金钱或游戏中的物品。对于此示例，我们将假设我们已将从一个用户获取资产和使用消息队列将其给予另一个用户的两个操作解耦，以提供解耦。

立即，这个系统感觉不确定且有问题。存在一个时间段，在此期间资产已离开一个用户，但尚未到达另一个用户处。此时间窗口的大小可以由消息传递系统设计确定。无论如何，在开始状态和结束状态之间存在滞后，在此期间，似乎没有用户拥有该资产。

但是，如果我们从用户的角度来看待这个问题，这种滞后可能是不相关的，甚至是不为人知的。接收用户和发送用户都可能不知道资产何时到达。如果发送和接收之间的滞后是几秒钟，那么对于直接就资产转移进行通信的用户来说，这将是不可见的，或者肯定是可容忍的。在这种情况下，即使我们在实现中依赖于软状态和最终一致性，系统行为也被认为是与用户一致且可接受的。

事件驱动架构

如果您确实需要知道状态何时变得一致怎么办？您可能有一些算法需要应用于状态，但仅当状态已达到与传入请求相关的一致状态时才应用。简单的方法是依赖于在状态变得一致时生成的事件。

继续前面的示例，如果您需要通知用户资产已到达怎么办？在将资产提交给接收用户的事务中创建事件，可以为在已知状态达到后执行进一步处理提供机制。EDA（事件驱动架构）可以显着提高可扩展性和架构解耦。关于 EDA 应用的进一步讨论超出了本文的范围。

结论

将系统扩展到极高的事务率需要一种关于管理资源的新思维方式。当负载需要分散到大量组件时，传统的事务模型存在问题。解耦操作并依次执行它们可以在牺牲一致性的情况下提高可用性和规模。BASE 提供了一种思考这种解耦的模型。
问

参考文献

DAN PRITCHETT 是 eBay 的技术研究员，在过去的四年中，他一直是架构团队的成员。在此职位上，他与 eBay 市场、PayPal 和 Skype 的战略、业务、产品和技术团队进行对接。Pritchett 在 Sun Microsystems、Hewlett-Packard 和 Silicon Graphics 等科技公司拥有 20 多年的经验，在技术方面拥有深厚的经验，范围从网络级协议和操作系统到系统设计和软件模式。他拥有密苏里大学罗拉分校的计算机科学学士学位。

最初发表于 Queue 第 6 卷，第 3 期—
在数字图书馆中评论本文

更多相关文章

Pat Helland - 关注您的状态以保持您的心态
随着应用程序进入分布式和可扩展的世界，它们经历了有趣的演变。同样，存储及其表亲数据库也与应用程序并肩发展。许多时候，存储和应用程序的语义、性能和故障模型都在微妙地跳舞，因为它们会随着不断变化的业务需求和环境挑战而变化。在混合中添加规模确实激起了波澜。本文着眼于其中的一些问题及其对系统的影响。

Alex Petrov - 现代存储系统背后的算法
本文仔细研究了现代数据库中常用的大多数存储系统设计方法（读取优化的 B 树和写入优化的 LSM（日志结构合并）树），并描述了它们的使用案例和权衡。

Mihir Nanavati, Malte Schwarzkopf, Jake Wires, Andrew Warfield - 非易失性存储
对于大多数执业计算机科学家的整个职业生涯来说，一个基本观察结果始终成立：CPU 的性能和成本都明显高于 I/O 设备。CPU 可以极高的速率处理数据，同时为多个 I/O 设备提供服务，这一事实对各种规模系统的硬件和软件设计产生了广泛的影响，几乎与我们构建它们的时间一样长。

Thanumalayan Sankaranarayana Pillai, Vijay Chidambaram, Ramnatthan Alagappan, Samer Al-Kiswany, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau - 崩溃一致性
数据的读取和写入是任何冯·诺依曼计算机最基本的方面之一，但却出奇地微妙且充满细微差别。例如，考虑在具有多个处理器的系统中访问共享内存。虽然一种称为强一致性的简单直观方法对于程序员来说最容易理解，但许多较弱的模型已被广泛使用（例如，x86 总存储顺序）；这些方法提高了系统性能，但代价是使关于系统行为的推理更加复杂且容易出错。