通过棒球解释的复制数据一致性

Doug Terry
微软研究院硅谷分部
MSR 技术报告
2011年10月

摘要

一些云存储服务，例如 Windows Azure，通过复制数据为客户提供强一致性，而其他服务，例如 Amazon，为了获得更好的性能和可用性，选择了最终一致性。对于读取共享数据的客户，可以（也许应该）提供更广泛的一致性保证。在一场棒球比赛中，不同的参与者（记分员、裁判、体育记者等）在读取当前比分时受益于六种不同的一致性保证。最终一致性对大多数参与者来说是不够的，但强一致性也不是必需的。

1. 引言

面向云的复制存储系统为读取数据的应用程序提供了不同的一致性保证。某些系统（如微软的 Azure）仅为其应用程序提供强一致性存储服务。这确保了 Windows Azure 存储的客户始终可以看到某个数据对象的最新值。尽管在数据中心内提供强一致性是理想且合理的，但当系统开始提供跨多个大陆多个数据中心的地理复制服务时，这种一致性引发了一些担忧。

另一些系统，例如 Amazon 的简单存储服务（S3），基于强一致性在大型系统中代价过高的考量，仅提供弱一致性。设计者选择牺牲一致性以获得更好的性能和可用性。在这种系统中，客户端的读取操作可能会返回陈旧的数据。读取操作返回的数据是某一时刻对象的值，但不一定是最新值。这种情况发生在读取操作定向到尚未接收到其他副本所接受的所有写入操作的副本时。这样的系统称为最终一致的。

一些近期的系统认识到需要支持不同类型的应用程序，因而提供了访问存储的多种操作选择。例如，Amazon 的 SimpleDB 提供了最终一致性读取和一致性读取两种模式，后者读取延迟更高且读取吞吐量有所降低（尽管系统文档并未量化其额外成本）。类似地，Google App Engine Datastore 增加了最终一致性读取，以补充其默认的强一致性。PNUTS（支持 Yahoo 的许多网络服务）提供了三种读取操作（读任意副本、关键读取、最新读取）和两种写入操作（写入和测试并设置写入）。

在过去的三十年里，研究社区提出了多种分布式和复制系统的一致性模型。这些模型提供的保证在强一致性和最终一致性之间。例如，一个系统可能保证客户端看到的数据最多滞后5分钟，或客户端始终能观察到其自身写入的结果。实际上，有些一致性模型甚至比最终一致性还要弱，但我会忽略那些实用性较差的模型。探索不同一致性模型的原因在于一致性、性能和可用性之间存在基本的权衡。提供更强的一致性通常会导致读取或写入的性能降低和可用性下降。每种提出的一致性模型都占据了权衡空间中的某一点。

但不同的一致性在实际中是否有用？应用程序开发者能否应对最终一致性？云存储系统是否应该提供比 Amazon SimpleDB 的一致性和最终一致性读取更多的选择？

本文试图至少部分地回答这些问题，通过一个示例（显然是虚构的）应用场景：棒球比赛。特别地，我探讨了不同访问比赛比分的人的需求，包括记分员、裁判、广播记者、体育记者和统计员。假设比分存储在基于云的复制存储服务中，我展示了最终一致性对大多数参与者来说不够，但也不需要强一致性。大多数参与者从某种中间的一致性保证中受益。

本文的结构如下。下一节定义了六种可能的读取一致性保证。第3节提出了一个模拟棒球比赛的算法，指出数据的写入和读取位置，并表明在不同保证下读取比分时可能返回的结果。第4节则分析了各个访问棒球比分的角色及其所需的一致性保证。最后，我从这一简单示例中总结出结论。

2. 读取一致性保证

尽管过去 30 年来复制系统提供了多种类型的数据一致性，计算机科学研究社区也探索了多种一致性模型，但许多模型都与特定实现绑定。通常情况下，理解一个系统提供的一致性以及适用的情况需要了解系统的运行方式，这给基于此类存储系统开发应用程序的人带来了不小的负担。

我在本节中倡导的六种一致性保证可以用一种简单且独立于实现的方式描述。这不仅能使应用程序开发者受益，还允许底层存储系统在设计、操作和演变上具有更大的灵活性。

这些一致性保证基于一个简单的模型，其中客户端对数据存储执行读写操作。数据在一组服务器间复制，但复制协议的细节对客户端是隐藏的。写操作按顺序进行，最终在所有服务器上按相同顺序完成。此顺序与客户端提交写操作的顺序一致。读取操作返回先前写入的一个或多个数据对象的值，但不一定是最新值。每个读取操作可以请求一致性保证，该保证规定了允许的返回值范围。每种保证通过定义读取操作可见的先前写入集合来描述。表 1 总结了这六种一致性保证。

表 1. 六种一致性保证

强一致性特别容易理解。它保证读取操作返回给定对象的最后写入值。如果写操作能够修改或扩展数据对象的部分内容（例如将数据追加到日志），那么读取会返回对该对象应用所有写入后的结果。换句话说，读取观察到所有已完成写入的效果。

最终一致性是最弱的保证，意味着它允许最大的可能返回值集合。对于整个对象的写入，最终一致性读取可以返回过去写入的任何数据对象的值。更一般而言，此类读取可以从接收到数据对象任意写入子集的副本中返回结果。

通过请求一致前缀，读取者可以确保观察到从数据对象的第一次写入开始的有序写入序列。例如，读取可以由一个按顺序从主副本接收写入的副本来响应，但尚未接收到无限数量的最近写入。换句话说，读取者看到的是某一过去时间点主副本中的数据存储版本。这类似于许多数据库管理系统提供的“快照隔离”一致性。

有界陈旧性确保读取结果不会过于过时。通常，陈旧性通过时间段 T（例如 5 分钟）来定义。存储系统保证读取操作将返回任何 T 分钟前写入的值或更近写入的值。或者，一些系统根据缺失写入的数量或数据值的不准确程度来定义陈旧性。我发现时间限制的陈旧性对于应用程序开发者而言是最自然的概念。

单调读取是一种适用于给定存储系统客户端执行的一系列读取操作的特性。因此，它通常被称为“会话保证”。在单调读取中，客户端可以像在最终一致性下一样读取任意陈旧的数据，但保证观察到的数据存储随时间逐渐更新。特别地，如果客户端发起一个读取操作，然后对同一对象再次发起读取，则第二次读取将返回相同的值或更晚写入的结果。

自己写入可见性（Read My Writes）是适用于单个客户端执行的一系列操作的特性。它保证了客户端执行的所有写入操作的效果在其后续读取操作中是可见的。如果客户端为数据对象写入一个新值，然后读取该对象，则读取将返回该客户端最后写入的值（或由其他客户端稍后写入的某个值）。（注：在其他论文中，这一特性通常被称为“读自己的写入”（Read Your Writes），但我选择改名，以更准确地从客户端的视角描述这一保证。）

最后四种读取保证都属于一种形式的最终一致性，但比 Amazon 等系统中通常提供的最终一致性模型更强。这四种保证之间没有严格的强弱关系，也就是说，每种保证可能会导致读取操作返回不同的值。在某些情况下，如稍后所示，应用程序可能希望请求多个此类保证。例如，客户端可以请求单调读取和自己写入可见性，从而观察到符合其自身操作一致性的数据存储。

本文中用于棒球比分的数据存储是一种传统的键值存储，由“noSQL”运动普及。写入操作（也称为 put）修改与给定键相关联的值。读取操作（也称为 get）返回某个键的值。不过，这些保证同样适用于其他类型的复制数据存储及其他类型的读写操作，例如文件系统和关系型数据库。

表 2 显示了每种一致性保证通常相关的性能和可用性。表格中将三个属性按“差”到“优”进行了评分。例如，强一致性在一致性方面是理想的，但由于通常需要从多数副本中读取，因此性能和可用性最差。另一方面，最终一致性允许客户端从任意副本读取，但提供的保证是最弱的一致性。每种保证在一致性、性能和可用性之间提供了独特的组合。对表格中每个单元格的标注并非精确的科学（我甚至可以为这个主题专门撰写一篇论文）。有些人可能认为标为“普通”的条目应标为“良好”或相反，实际上这些特性在一定程度上依赖于实现、部署和操作细节。不过，对各种一致性保证之间的总体比较在质量上是准确的。选择特定复制方案及一致性模型时需要在各方面作出实质性权衡。

尽管没有提供任何证据，我断言所有这些保证都可以在同一存储系统中作为选择提供。事实上，我和硅谷微软研究院的同事已经构建了这样的系统原型（但这是另一个话题）。在我们的系统中，请求不同一致性保证的客户端在读取共享数据时会体验到不同的性能和可用性。本文中，假设存在一个存储系统为其客户提供了这六种读取保证的选择。接下来，我将展示它们在棒球比赛中的使用方式。

表 2. 一致性、性能和可用性的权衡

3. 棒球作为示例应用程序

对于不熟悉棒球但喜欢阅读代码的读者，图 1 展示了一场 9 局棒球比赛的基础知识。比赛开始时比分为 0-0。客队首先击球，直到他们出现三次出局，然后主队击球，直到出现三次出局。如此往复，直至完成九局。当然，这忽略了许多棒球爱好者（包括我在内）所热爱的细节，但这足以解释本文所需的内容。

我们假设比赛的比分记录在一个键值存储中，有两个对象，一个记录“客队”得分，另一个记录“主队”得分。当一支球队得分时，首先读取其当前得分，将返回的值加 1，然后将新值写回键值存储。

Write (“visitors”, 0);
Write (“home”, 0);
for inning = 1 .. 9
    outs = 0;
    while outs < 3
        visiting player bats;
        for each run scored
            score = Read (“visitors”);
            Write (“visitors”, score + 1);
    outs = 0;
    while outs < 3
        home player bats;
        for each run scored
            score = Read (“home”);
            Write (“home”, score + 1);
end game;

图 1. 简化的棒球比赛

作为一个具体示例，考虑图 2 中示例比赛的写入日志。在该比赛中，主队首先得分，随后客队追平，然后主队再得两分，依此类推。

Write (“home”, 1)
Write (“visitors”, 1)
Write (“home”, 2)
Write (“home”, 3)
Write (“visitors”, 2)
Write (“home”, 4)
Write (“home”, 5)

图 2. 示例比赛的写入序列

这一写入序列可能来自图 3 中显示的逐局比分的棒球比赛。假设该比赛目前进行到第七局的中段（俗称“第七局休息”），主队以 5-2 领先。

图 3. 示例比赛的逐局得分

假设记录客队和主队得分的键值存储位于云端，并在多个服务器之间进行复制。不同的读取保证可能导致客户端读取到该进行中的比赛的不同比分。表 3 列出了使用六种一致性保证读取客队和主队得分时可能返回的所有比分集。请注意，客队得分在前，不同的可能返回值用逗号分隔。

表 3. 各一致性保证的可能比分读取结果

强一致性读取只能返回一个结果，即当前比分，而最终一致性读取可能返回 18 种不同的比分。注意，其中许多比分并不是实际出现过的比分。一致前缀限制了返回结果，使其只能为曾经存在过的比分。有界陈旧性读取的可能结果显然取决于所需的界限。表 3 显示的是一局之内滞后的可能比分，即最多滞后一局的比分；在此示例中，如果界限为 7 局或更长，则结果集与最终一致性相同。实际上，系统不太可能以“局”为单位来表示陈旧性界限。因此，假设读者请求的界限为 15 分钟，而上一局正好持续了该时间。对于单调读取，可能的返回值取决于过去的读取情况；而对于自己写入，则取决于谁在向键值存储写入数据。

4. 参与者的读取需求

现在，让我们分析参与棒球比赛的各类人员的读取一致性需求，他们都希望读取比分。当然，每个人都可以执行强一致性读取来获取客队和主队的比分。在这种情况下，如上一节所指出的，只会返回一个可能的值：当前比分。然而，如表 2 所示，请求强一致性读取的读者可能会面临较长的响应时间，甚至可能因为临时服务器故障或网络中断而无法获取数据。本节的目的是评估每个参与者所需的最小一致性。通过请求比强一致性更弱的读取保证，这些客户端可能会获得性能上的提升。

4.1 官方记分员

官方记分员负责通过将比分写入持久性键值存储来维护比赛比分。图 4 展示了每次客队得分时记分员所采取的步骤；当主队得分时的操作类似。请注意，此代码片段来自图 1 中展示的棒球比赛总体代码的一部分。

score = Read (“visitors”);
Write (“visitors”, score + 1);

Figure 4. Role of the Scorekeeper

记分员的读取操作需要什么一致性呢？毫无疑问，记分员需要读取最新的先前比分，然后在其基础上加 1 得出新的比分。否则，记分员可能会写入错误的比分，从而破坏比赛，更别提激怒大量的棒球迷了。假设主队之前得了五分，而刚刚得了第六分。执行最终一致性读取时，如表 3 所示，可能会返回从零到五之间的任意分数。或许记分员很幸运，能够在读取中获得正确的比分，但他不应对此抱有希望。

有趣的是，虽然记分员需要强一致的数据，但他不需要执行强一致性读取。由于记分员是唯一更新比分的人，他可以请求“自己写入”一致性保证，从而获得与强一致性读取相同的效果。本质上，记分员利用应用特定的知识，获得了较弱一致性读取的性能优势，而不会失去一致性。

这看似一个细微的区别，但在实践中可能相当重要。在处理强一致性读取时，存储系统必须假设世界上某个客户端刚刚更新了数据，因此系统必须访问大多数服务器（或固定的一组服务器）以确保读取操作访问到最新写入的数据。另一方面，在提供“自己写入”保证时，系统只需记录客户端之前执行的写入集合，并找到已经看到所有这些写入的某个服务器。在棒球比赛中，之前得分（即记分员执行的先前写入）可能已经发生在几分钟甚至几个小时前。在这种情况下，几乎任何服务器都已收到之前的写入，能够回答下一个请求“自己写入”保证的读取操作。

4.2 裁判

裁判是从本垒后方主持棒球比赛的人。裁判通常不在意比赛的当前比分，唯一的例外是在第 9 局上半场之后，也就是客队完成击球，主队即将上场击球的时刻。因为这是最后一局（且得分不会为负数），如果主队领先，他们已经赢得比赛，因此在某些比赛中主队可以跳过最后的击球机会。裁判用于判断这一情况的代码见图 5。

if first half of 9th inning complete then
  vScore = Read (“visitors”);
  hScore = Read (“home”);
  if vScore < hScore
    end game;

Figure 5. Role of the Umpire

在第 9 局访问比分时，裁判确实需要读取当前比分，否则如果错误地认为主队领先，他可能会提前结束比赛，或让主队不必要地进行击球。与记分员不同，裁判从不写入比分；他只是读取官方记分员所写入的分值。因此，为了获得最新的信息，裁判必须执行强一致性读取。

4.3 广播记者

在美国的大部分地区，电台定期播报正在进行或已经完成的比赛比分。例如，在旧金山地区，KNBR 电台每 30 分钟报道一次体育新闻。广播记者执行图 6 所示的步骤。一个类似的、或许更现代的例子是，当观众观看 ESPN 时，电视屏幕底部滚动显示的体育比分。

do {
  vScore = Read (“visitors”);
  hScore = Read (“home”);
  report vScore and hScore;
  sleep (30 minutes);
}

Figure 6. Role of the Radio Sports Reporter

如果广播记者播报的比分不是最新的，那也没关系。人们习惯于接受旧新闻。因此，某种形式的最终一致性对他执行的读取操作是可以接受的。但有哪些保证是理想的呢？

如表 3 所示，具有最弱保证的最终一致性读取可能返回从未实际出现过的比分。对于图 3 给出的示例比分，这种读取可能返回客队以 1-0 领先的比分，尽管客队从未实际领先过。广播记者不希望报道这种虚构的比分。因此，记者希望他的读取在持有记分员写入的一致前缀的服务器上进行。这允许记者读取某个时刻存在的比分，而不必读取当前比分。

但读取一致前缀还不够。对于图 3 中的比分，记者可以读取到当前比分 2-5，但 30 分钟后却读取到 1-3 的比分。这种情况可能发生，例如记者先从主服务器读取，之后从可能与主服务器断开连接、尚未收到最新写入的远程数据中心的服务器读取。由于众所周知棒球比分是单调递增的，连续的新闻报道中出现 2-5 和 1-3 的比分会让记者看起来很荒谬。如果记者在请求一致前缀的同时请求单调读取保证，则可以避免这种情况。注意，单独请求其中任何一种保证都不够。

或者，记者可以通过请求有界陈旧性来获得与单调读取相同的效果，陈旧性界限小于 30 分钟即可。这将确保报道的比分最多滞后 30 分钟。由于记者每 30 分钟读取一次数据，他会接收到逐渐更新的比分。当然，记者可以要求更紧的界限，例如 5 分钟，以获得更为及时的比分。

4.4 体育记者

另一位有趣的参与者是体育记者，他会观看比赛并撰写文章，发布在早报或某些网站上。不同的体育记者可能有不同的行为，但根据我的观察（作为一名前体育记者），他们的行为往往如图 7 所示。

While not end of game {
  drink beer;
  smoke cigar;
}
go out to dinner;
vScore = Read (“visitors”);
hScore = Read (“home”);
write article;

Figure 7. Role of the Sportswriter

体育记者可能并不急于撰写文章。在此例中，他可能先去悠闲地吃顿晚餐，再回来总结比赛。他肯定想确保报道的比赛最终比分是正确的，因此他希望获得强一致性读取的效果。然而，他不需要为此支付代价。如果体育记者知道自己在比赛结束后花了一小时吃饭，那么他也知道比分已至少一个小时未被更新。因此，一小时有界陈旧性读取足以确保他读取到最终比分。实际上，任何服务器都应该能够回答这样的读取请求。事实上，一小时后进行最终一致性读取也很可能返回正确的比分，但请求有界陈旧性是体育记者 100% 确保获取到最终比分的唯一方法。

4.5 统计员

球队统计员负责追踪球队和球员在整个赛季中的数据统计。例如，统计员可能统计本赛季球队的总得分。假设这些统计数据也保存在持久性键值存储中。如图 8 所示，在每场比赛结束后，主队统计员会将比赛得分添加到赛季总得分中，并将新值写回数据存储。

Wait for end of game;
score = Read (“home”);
stat = Read (“season-runs”);
Write (“season-runs”, stat + score);

Figure 8. Role of the Statistician

在读取当天的球队得分时，统计员希望确保获得最终得分，因此她需要执行强一致性读取。如果统计员在比赛结束后等待了一段时间，那么有界陈旧性读取也可以达到相同的效果（如 4.4 节中针对体育记者所讨论的）。

在读取赛季的当前统计数据时（即图 8 中的第二次读取操作），统计员同样需要强一致性。如果返回旧统计数据，那么写回的更新值会导致球队总得分被低估。由于统计员是唯一向数据存储写入统计数据的人，她可以使用自己写入保证来获取最新的值（如 4.1 节中记分员的讨论）。

4.6 统计数据观察者

其他定期查看球队赛季统计数据的人通常满足于最终一致性。统计数据每天只更新一次，略微过时的数据是可以接受的。例如，如图 9 所示，查询本赛季球队总得分的球迷可以执行最终一致性读取，以获得一个合理的答案。

do {
  stat = Read (“season-runs”);
  discuss stats with friends;
  sleep (1 day);
}

Figure 9. Role of the Stat Watcher

5. 结论

显然，存储棒球比分并不是云存储系统的“杀手级”应用。我们也应谨慎对待从一个简单示例中得出的结论，但或许可以从中学到一些经验。

表 4 总结了上一节讨论的各类棒球参与者所需的一致性保证。请记住，列出的保证并非唯一可接受的选择。特别是，每个参与者都可以接受强一致性，但通过放宽读取请求的一致性要求，他们可能会获得更好的性能和可用性。此外，存储系统在处理弱一致性读取请求时有更多选择服务器的灵活性，从而可能更好地平衡服务器之间的读取负载。

表 4. 棒球参与者的读取保证

这些参与者可以视为不同的应用程序，它们访问的是共享数据：棒球比分。在某些情况下，例如记分员和体育记者，读取者基于特定的应用知识，即使通过使用“自己写入”或“有界陈旧性”保证发起弱一致性读取，也能获得强一致的数据。在其他情况下，例如广播记者，需要组合多个保证才能满足读取需求。再者，对于统计员，来自同一客户端的不同读取请求需要不同的一致性保证。

从这次分析中，我得出以下四个主要结论：

• 所有六种一致性保证都是有用的。请注意，每种保证在表 4 中至少出现一次。仅提供最终一致性的系统无法满足除一个以外的所有客户端的需求，而仅提供强一致性的系统在除两种情况外的所有场景下可能表现不佳。
• 不同客户端在访问相同数据时可能希望不同的一致性。通常，系统会为特定数据集或数据类别绑定特定一致性。例如，人们普遍认为银行数据必须强一致，而购物车数据仅需最终一致性。棒球示例表明，所需的一致性不仅取决于数据类型，还取决于读取数据的人。
• 即使是简单的数据库也可能有多样的用户，且需求不同。棒球比分是最简单的数据库之一，仅由两个数字组成，但它有效地展示了不同一致性选项的价值。
• 客户端应能够选择其所需的一致性。系统无法预测或确定某个应用程序或客户端所需的一致性。所需的一致性通常取决于数据的使用方式。此外，了解谁在写入数据或数据最后的写入时间，有时可以使客户端在保持最新数据的同时进行放宽一致性读取并获得相关优势。

关于最终一致性的代价呢？反对提供最终一致性时的主要观点是，这增加了应用程序开发者的负担。这可能确实如此，但额外负担不一定会过多。第一步是定义开发者可以理解的一致性保证；请注意，表 1 中的六种保证每一种都可以用几个词描述。通过让存储系统以严格顺序执行写入操作，应用开发者可以避免处理来自并发写入的更新冲突的复杂性。这样开发者的任务仅是选择所需的读取一致性。此选择需要对应用程序语义的深刻理解，但无需改变程序的基本结构。上一节中的代码片段无需额外代码来专门处理陈旧数据。

那么云存储提供商应提供什么呢？像 Windows Azure Storage 这样提供强一致性的系统，使开发者可以更轻松地编写正确的程序，但可能会错失放宽一致性所带来的优势。这在地理复制服务日益增多的背景下可能具有实际意义，因为一致性、性能和可用性之间的权衡是明显的，且可能会更加突出。这表明云存储系统至少应考虑提供更多的读取一致性选择。Amazon 已在其 SimpleDB 服务中提供了两种读取操作，Google App Engine 也是如此，但本文表明 Amazon 的弱最终一致性可能并不适用于许多应用程序。允许云存储客户端从不同的副本中选择一致性保证读取，不仅可能有助于广泛的应用程序，还可能带来更好的资源利用和成本节省。

6. 拓展阅读

1. W. Vogels. “Eventually Consistent.” Communications of the ACM, January 2009.
   解释了 Amazon 为什么选择最终一致性来支持其大规模、可靠的基础设施服务。

2. B. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, 和 R. Yerneni. PNUTS: Yahoo!’s Hosted Data Serving Platform. 发表在 国际大型数据库会议 (VLDB)，2008年8月。
   描述了 Yahoo! 分布式数据库系统所采用的松弛一致性模型(relaxed consistency model)，该系统支持 Yahoo! 的众多网络应用程序。

3. D. Terry, A. Demers, K. Petersen, M. Spreitzer, M. Theimer, 和 B. Welch. Session Guarantees for Weakly Consistent Replicated Data. 发表在 IEEE 国际并行与分布信息系统会议，1994年。
   定义了“读取自己写入”、“单调读取”等会话保证，并展示了如何在最终一致性系统中实现这些保证。

4. T. Kraska, M. Hentschel, G. Alonso, 和 D. Kossmann. Consistency Rationing in the Cloud: Pay Only When It Matters. 发表在 国际大型数据库会议 (VLDB)，2009年8月。
   在 Amazon S3 的基础上构建了云数据库系统，展示了放宽一致性能够显著降低事务成本并提高性能。

5. H. Wada, A. Fekete, L. Zhao, K. Lee, 和 A. Liu. Data Consistency Properties and the Trade-offs in Commercial Cloud Storages: The Consumers’ Perspective. 发表在 CIDR，2011年1月。
   分析了 Amazon SimpleDB，指出该服务常提供陈旧数据，且未能提供读取自己写入或单调读取保证，而最终一致性读取的实际性能并不优于同一服务的强一致性读取。

6. E. Anderson, X. Li, M. Shah, J. Tucek, 和 J. Wylie. What Consistency Does Your Key-value Store Actually Provide? 发表在 Usenix 系统可靠性热点研讨会 (HotDep)，2010年。
   测量了最终一致性键值存储实际提供强一致性的频率，并报告一致性违规事件很少发生。