线性化与串行化

线性化和串行化都是数据库和分布式系统中操作交错的重要属性，很容易混淆。这篇文章对两者之间的差异进行了简短、简单且实用的概述。

线性化：单操作、单对象、实时排序

线性化是对单个对象的单个操作的保证。它为单个对象（例如分布式寄存器或数据项）上的一组单个操作（通常是读取和写入）的行为提供实时（即挂钟）保证。

在简单的英语中，在线性化下，写入应该是瞬时的。不准确地说，一旦写入完成，所有后续读取（其中“稍后”由挂钟开始时间定义）应该返回该写入的值或稍后写入的值。一旦读取返回特定值，所有后续读取都应返回该值或后续写入的值。

读写操作的线性化与术语“原子一致性”同义，是Gilbert and Lynch 对 CAP 定理的证明中的“C”或“一致性” 。我们说线性化是可组合的 （或“局部的”），因为如果对系统中每个对象的操作都是线性化的，那么系统中的所有操作都是线性化的。

可序列化：多操作、多对象、任意全序

可序列化性是对事务或对一个或多个对象的一个​​或多个操作组的保证。它保证在多个项目上执行一组事务（通常包含读取和写入操作）等效于事务的某些串行执行（总排序）。

可串行化是ACID中传统的“I”或隔离。如果用户的事务每个都保持应用程序的正确性（“C”或 ACID 中的一致性），那么可序列化的执行也保持正确性。因此，可串行化是保证数据库正确性的一种机制。¹

与线性化不同，可串行化本身不会对事务的排序施加任何实时约束。可序列化性也不是可组合的。可串行化并不意味着任何类型的确定性顺序——它只是要求存在一些等效的串行执行。

严格的可序列化性：为什么我们不能两者兼得？

结合可串行化和线性化产生严格的可串行化：事务行为相当于一些串行执行，串行顺序对应实时。例如，假设我开始并提交事务 T1，它写入项目x，然后您开始并提交事务 T2，它从x读取。为这些事务提供严格可串行化的数据库将在串行排序中将 T1 置于 T2 之前，并且 T2 将读取 T1 的写入。提供可序列化（但不是严格的可序列化）的数据库可以在 T1 之前排序 T2。²

正如Herlihy 和 Wing所指出的，“线性化可以被视为严格串行化的一种特殊情况，其中事务被限制为由应用于单个对象的单个操作组成。”

协调成本和实际部署

如果没有协调，就无法实现线性化和串行化。也就是说，我们无法在异步网络下提供可用性保证（即 CAP “AP”）。³

在实践中，您的数据库不太可能提供可串行化，并且您的多核处理器不太可能提供线性化——至少在默认情况下是这样。正如上述理论所暗示的，实现这些特性需要大量昂贵的协调。因此，实际系统通常使用实现成本更低且通常更难理解的模型。这种效率和可编程性之间的权衡代表了一个迷人且具有挑战性的设计空间。

关于术语的注释和更多阅读

这些定义如此混乱的原因之一是线性化来自分布式系统和并发编程社区，而串行化来自数据库社区。今天，几乎每个人都使用分布式系统和数据库，这常常导致术语过载（例如，“一致性”、“原子性”）。

对这些概念有许多更精确的处理。我喜欢这本书，但互联网上有大量免费、简洁且（通常）准确的材料，例如这些笔记。

笔记

1. 但这不是唯一的机制！诚然，可串行化（或多或少）是维护数据库正确性的最通用方法。HT Kung和Christos Papadimitriou在 1979 年的 SIGMOD 中发表了一篇关于“数据库并发控制的最优理论”的论文，这正在成为我最喜欢的“地下”（即相对较少被引用的）参考文献之一。在其中，它们基本上表明，如果您拥有的只是事务对数据库状态的句法修改（例如，读取和写入）并且没有关于应用程序逻辑的信息，可序列化性在某种意义上是“最佳的”：实际上，不可序列化的调度可能会以某种方式修改数据库状态，从而导致某些（任意）正确性概念不为数据库。但是，如果您对用户的正确性概念了解更多（例如，您就是用户！），您通常可以在并发控制方面做更多事情，并且可以规避由可序列化性强加的许多基本开销。认识到何时不需要可序列化（并随后利用这一事实）是我所知道的“击败 CAP”的最佳方式。↩
2. 请注意，某些可串行化的实现（例如具有长写锁和长读锁的两阶段锁定）实际上提供了严格的可串行化。正如Herlihy 和 Wing所指出的，其他实现（例如一些 MVCC 实现）可能不会。那么，为什么定义可串行化的早期论文没有引起人们对这种实时排序的关注呢？从某种意义上说，实时并不重要：所有可序列化的调度在保持数据库正确性方面都是等效的！但是，有一些奇怪的边缘情况：例如，响应每个只读事务返回 NULL 是可序列化的（假设我们从一个空数据库开始），但没有帮助。对于这种遗漏，一个非常合理的理论是，早在 1970 年代，当可序列化理论被发明时，每个人都在单站点系统上运行，所以线性化本质上是“免费的”。但是，我认为这种理论不太可能：例如，数据库先驱Phil Bernstein早在 1977 年就已经在研究他的 SDD-1 系统中的分布式事务执行（并且还有更早的参考资料）。即使在这项早期工作中，伯恩斯坦（和公司）也小心地强调“实际上可能有几个这样的等价序列”[强调他们的]。为了进一步搁置这一理论，Papadimitriou 在其开创性的1979 年 JACM中阐明了这一点他熟悉分布式环境中固有的问题的文章。（如果你想被文献所震撼，看看在 1980 年代初期完成了多少并发控制的基础工作。）↩
3. 对于分布式系统的新人：实现读写的线性化，在正式意义上，比串行化“更容易”实现。这可能值得再发一篇文章（感谢鼓励！），但这里有一些直觉：终止原子寄存器读/写操作在故障停止模型中是可以实现的。然而，原子承诺——这是执行多站点可序列化事务所必需的（想想：AC 之于 2PC，就像共识之于 Paxos）——不是：FLP 结果表明共识在故障停止模型中是无法实现的（因此使用一个错误进程）和（非阻塞）原子承诺比共识“更难”（另见）。另外，请记住 read-modify-write 的线性化比线性化读/写更难。（线性化读/写《共识》原子承诺）