数据库设计：一致性和 CAP 定理
数据库设计：一致性和 CAP 定理
在分布式系统中，数据一致性是一个核心问题。本文将深入探讨数据库设计中的一致性概念，以及著名的CAP定理。通过理解这些概念，开发者可以更好地设计和优化分布式系统。
数据库设计：一致性和 CAP 定理
如果没有复制，则不需要考虑一致性问题。 复制需要在多台计算机上维护相同数据的多个拷贝（或副本），而一致性在多个客户端/进程中提供系统范围的副本的一致视图/状态。 如前所述，主要出于两个原因复制数据项：性能和可靠性。 对于性能而言，如果系统需要在数量（主要是私有云和公有云中的存储）和地理区域（通常是公有云中的存储）方面缩放，则复制至关重要。 例如，如果有越来越多的进程必须访问由单个存储服务器管理的数据，则可以通过跨多台服务器（而不是仅使用一台服务器）复制数据，然后在多台服务器之间分配工作来提高性能。 这种划分允许并发处理请求，因而可加快系统速度。 与之相反，可以通过在请求进程附近复制数据副本来最大程度地缩短数据访问时间，从而确保跨地理区域进行复制（例如，如 Azure 所应用）。 对于可靠性，可借助复制提供更好的容错能力，以防止数据损坏和丢失，这是云上的一项关键要求。 具体而言，如果某个副本丢失或损坏，则可以改为访问另一个有效副本（如有维护）。
复制会生成多个数据副本，而一致性可确保这些副本保持一致，以便不同的进程可以访问（即读取和写入）它们。 具体而言，当集合中的副本看起来与并发访问进程相同时，它们被视为一致。 在处理副本上的并发操作的同时保持一致性的能力是常规分布式存储（特别是云存储）的基础。 本单元在对分布式数据存储中的共享副本执行的读写操作的上下文中讨论一致性（见图 13）。 分布式数据存储可以是 DFS、并行文件系统或分布式数据库。 可通过采用一致性模型来实现一致性。 我们将一致性模型定义为进程与分布式数据存储之间的协定。 此定义意味着，如果进程同意遵守特定规则，则分布式数据存储承诺强制实施这些规则。 以下视频介绍多个一致性模型。
我们在本单元中详细讨论三个一致性模型：顺序一致性、因果一致性和最终一致性。
图 13：分布式数据存储，可以是分布式文件系统、并行文件系统或分布式数据库，并跨分布式存储磁盘维护副本
顺序一致性
顺序一致性也称为强一致性或严格一致性，其要求立即将更新传播到所有副本。 这通常需要在单个原子操作或事务中对相关副本应用更新。 实际上，在大型分布式数据存储中跨分布范围很广的副本实现原子性本身就困难重重，特别是在需要快速完成更新的情况下。 困难源于底层存储网络带来的不可预测的访问延迟以及缺少可用于快速、准确地对操作排序的全局时钟。 若要解决此问题，可以放宽以原子操作的形式执行更新的要求。 放宽一致性要求意味着副本不需要总是在所有位置都相同。 是否可接受放宽一致性要求取决于在分布式数据存储上运行的应用程序。 具体而言，放宽一致性要求取决于应用程序的读写访问模式以及使用副本的目的。 例如，浏览器和 Web 代理通常配置为将网页存储在本地缓存中（这是一种复制类型，因为为同一网页维护了多个副本），以减少将来引用所需的访问时间。 在某些情况下，只要最终能够足够快地将网页升级为实际 Web 服务器上可用的最新版本，就可以接受让用户接收过时的网页。 最终一致性是适合此类方案的模型的示例。
图 14：(a) 顺序一致的分布式数据存储，以及 (b) 非顺序一致的分布式数据存储
如果所有进程在并发访问副本时看到的读写操作交错相同，则该分布式数据存储被视为顺序一致。 图 14 演示了两个分布式数据存储：顺序一致的数据存储（见图14[a]）和非顺序一致的数据存储（见图 14[b]）。 符号 W(x)a 和 R(x)b 分别表示对副本 x 写入的 a 值和从副本 x 读取的 b 值。 该图显示了在对应于数据项 x 的副本上运行的四个进程。 在图 14(a) 中，进程 P1 将 a 写入 x，之后（在绝对时间内），进程 P2 将 b 写入 x。 随后，进程 P3 和 P4 在读取 x 时先接收值 b，然后再接收值 a。 因此，进程 P2 所携带的写入操作看似已在 P1 的写入操作以及进程 P3 和 P4 的写入操作之前发生。 尽管如此，图 14(a) 仍然表示顺序一致的分布式数据存储，因为进程 P3 和 P4 遇到相同的操作交错（即先读取 b，再读取 a）。 与之相反，图 14(b) 中的进程 P3 和 P4 看到了不同的操作交错，因而违反了顺序一致性的条件。
因果一致性
因果一致性模型是顺序一致性模型的较弱变体。 首先，因果关系意味着，如果操作 b 由之前的操作 a 引起或受其影响，则访问分布式数据存储的每个进程都应先看到 a，然后再看到 b。 因果一致的分布式数据存储仅在可能因果相关的操作中强制实施一致性。 没有潜在因果关系的操作可以出现在任何交错的进程中，并表示为并发操作。 图 15 显示了两个因果一致的分布式数据存储（图 15[a] 和 15[c]）以及一个非因果一致的分布式数据存储（图 15[b]）。 在图 15(a) 中，由进程 P2 执行的 W(x)b 可能取决于进程 P1 携带的 W(x)a，因为 b 可能是涉及在写入 b（即 W[x]b）之前由进程 P2 读取的 a 的计算的结果。 因此，分别由 P1 和 P2 执行的写入操作 W(x)a 和 W(x)b 的结果应该在每个读取进程中以相同的顺序出现。 因为进程 P3 和 P4 首先读取 a，然后再读取 b，所以将它们视为遵守因果关系条件，底层分布式数据存储因此因果一致。 与之相反，图 15(b) 中的进程 P3 不遵守因果关系条件（即，它先读取 b，然后再读取 a），底层分布式数据存储因而非因果一致。 最后，图 15(c) 显示因果一致的分布式数据存储，原因在于 W(x)a 和 W(x)b 是并发操作；因此，它们的结果（即 R[x]a 和 R[x]b）可以在读取进程中以任何顺序出现，进程 P3 和 P4 就是这种情况。
图 15：(a) 因果一致的分布式数据存储，(b) 非因果一致的分布式数据存储，以及 (c) 因果一致的分布式数据存储
最终一致性
最终一致性模型被视为顺序一致性模型和因果一致性模型的较弱形式。 最终一致性意味着，某个副本上的写入操作无需立即传播到所有其他副本，并且在应用程序接受的情况下可以延迟传播（有时根本不传播）。 具体而言，如果进程 P 访问特定副本 R，频率为每分钟 $N$ 次，且 R 每分钟更新 $M$ 次，那么，如果应用程序的读写比率很低（即 $N << M$），则 P 将永远不会访问副本的许多更新，这让所有这些更新和所需的网络通信变得毫无意义。 在这种情况下，最好应用弱一致性模型，从而仅在 R 被 P 访问时才更新 R。也就是说，以推迟方式传播更新更为高效，读取进程因而仅会在更新发生后并过去了一段时间时才会看到更新（不会立即看到，因为这是严格一致性的要求）。 如果很少或永远不会发生因两个操作试图对相同数据进行写入而导致的冲突（即写-写冲突），则通常可以接受推迟更新的传播。 数据库系统很少发生冲突，它们通常采用最终一致性。 我们会在下一部分中详细讨论数据库系统。 请注意，我们仅介绍了有关一致性模型的一部分内容。 另一部分内容与如何实现此类模型有关。 在本单元中，我们仅关注这些模型是什么及其对云存储系统的适用性。 尽管如此，我们粗略指出了顺序一致性在实践中很难实现，并且其可伸缩性很差。 通常情况下，顺序一致性要求使用同步机制，例如事务和锁。 与之相反，实现因果一致性涉及生成依赖项关系图，该图捕获因果相关的操作并在访问进程中强制执行这些操作。 实现此类模型的一种方法是使用矢量时间戳。 可通过将读入操作分组为会话并使用矢量时间戳来实现最终一致性。
数据库中的 ACID 属性
数据库可以提供事务属性。 事务由在数据库管理系统（或类似系统）内针对数据库执行的工作单元组成。 使用与其他事务无关的一致且可靠的方式处理事务。 数据库环境中的事务有两个主要目的：
提供可靠的工作单元，以便能够从故障中正确恢复并使数据库保持一致，即使在发生执行停止（完全或部分）且对数据库执行的许多操作仍未完成并状态不明的系统故障时，也是如此。
在并发访问数据库的程序之间提供隔离。 如果不提供此隔离，程序的结果可能出错。
为了更好地理解数据库中的事务需求，以在两个银行帐户 A 和 B 中进行的以下金融交易为例。假设用户要将 $100 从帐户 A 转至帐户 B。此转移可表示为两个步骤：
从帐户 A 中扣除 $100。
将 $100 存入帐户 B。
假设数据库故障在操作 1 和 2 之间发生：可能已从帐户 A 中扣除 $100，但未存入帐户 B 中。 帐户及数据库本身都会处于不一致的状态。
若要解决此问题，可以将操作定义为事务，如下所示：
开始交易。
从帐户 A 中扣除 $100。
将 $100 存入帐户 B。
结束交易。
现在，数据库应负责确保此事务的原子性，即确保事务完全成功（已提交）或根本没有执行（回滚）。 数据库应在事务完成后保持一致；也就是说，数据库应在提交事务后处于有效状态，并且不应违反为数据库中的记录定义的所有规则（例如，储蓄帐户不能拥有负余额）。 帐户中并发发生的所有事务都不得互相干扰，从而提供隔离。 最后，事务必须可持续，这意味着将事务保存到数据库后，在事务中执行的操作应保持不变。 原子性、一致性、隔离性和持久性属性统称为事务的 ACID 属性，且用于事务处理的大多数 RDBMS 都应遵循这些属性。 以下视频概要介绍数据库中的 ACID 属性：
原子性：事务不可分割，要么将事务中的所有语句都应用于数据库，要么都不应用。
一致性：数据库在事务执行前后保持一致状态。
隔离性：尽管多个事务可由一个或多个用户同时执行，但一个事务不应看到其他并发事务的影响。
持续性：将事务保存到数据库（在数据库编程中称为提交的操作）后，其更改预期将保持不变。
为什么不能全部拥有：CAP 定理
1999 年，Brewer1提出了一个描述分布式数据存储限制的定理，称为 CAP 定理。 CAP 定理指出，任何具有共享数据的分布式存储系统都最多只能具有三个所需属性中的两个：
一致性：一致性是一种每个节点在任何给定时刻都始终会看到相同数据的状态（严格一致性）。
可用性：对每个请求都会收到有关成败与否的响应的保证是一种可用性保证。
分区容错性：网络分区指分布式系统的节点无法相互联系的情况。 分区容错性意味着系统在任意消息丢失或系统部分故障的情况下仍可继续正常运行。
理解 CAP 的最简单方法是假设一个分布式存储系统的两个节点位于网络分区的两侧（图 16）。 允许至少一个节点更新状态将导致节点变得不一致，因此会放弃一致性 (C)。同样，如果选择保持一致性，则分区的一侧必须表现为不可用，因此会放弃可用性 (A)。仅当节点通信时才能保持一致性和可用性，因此会放弃分区容错性 (P)。
举例来说，假设有一个传统的单节点 RDBMS。 在此方案中，可以保证一致性和可用性，但分区容错性的概念不存在，因为数据库位于单个节点上。
如果 Microsoft 之类的公司要设计大型数据库用于为数百万客户提供服务，全天候可用性是关键所在，因为即使是几分钟的停机时间也意味着损失收入。 将分布式共享数据系统缩放为成百上千台计算机时，一个或多个节点发生故障（从而创建网络分区）的可能性大幅增加。 因此，根据 CAP 定理，为了在可用性和分区容错性方面获得强保证，必须牺牲大型高性能分布式数据库的严格一致性。
图 16：CAP 定理图解
参考资料
- Eric Brewer (2000)。面向可靠的分布式系统年度 ACM 分布式计算原理研讨会论文集