可串行化和可线性化有什么区别？

Question

我对这两种一致性模型感到非常困惑。请给出一些时间线示例并进行解释。 http://en.wikipedia.org/wiki/Consistency_model

Answer 1

很难找到有关此主题的信息。然而，在某个时候我发现了一个解释得很清楚的说法：

• 线性化在操作级别提供隔离，而串行化在事务级别提供隔离。

（从深入描述中总结可在此处找到）

举个例子：

这里，A、B、C 是同时运行的三个不同的事务。 r(varname) 表示当前事务正在访问 varname 中的值，w(varname) 表示当前事务正在向 varname 中写入某个值。

现在，为了创建这些事件的线性历史记录，我们必须确保没有两个操作同时发生。当另一个操作已经开始时已经开始的操作应该出现在第一个操作的后面。

在这种情况下：

Log1: A.r(x), B.r(X), B.r(Y), A.w(X), C.r(Y)

要创建这些事件的序列化历史记录，必须将事务 A、B 和 C 的所有操作分开，这样就不会与其他事务交错操作。

从我们的示例来看，这可能会导致：

Log2: A.r(x), A.w(x), B.r(X), B.r(Y), C.r(Y)

Answer 2

请观看此视频：https://www.youtube.com/watch?v=noUNH3jDLC0&t

Martin Kleppmann 是《设计数据密集型应用程序》的作者，这是一本很棒的书，我强烈推荐给对可串行化或线性化感兴趣的人。

Answer 3

假设您有一个可以对其进行操作的对象。将

transaction

定义为您希望在此对象上执行的一组操作。

令 H 为进程 A、B 和 C 在对象上执行的事务调用和响应的以下历史记录。

H = {A.inv, B.inv, B.res, C.inv, C.res, A.res}
Process A transaction:     |---------------------------|
Process B transaction:           |-----|
Process C transaction:                     |-----|

您可以直观地看到进程 A、B 和 C 正在对对象执行并发操作事务。

如果您假设每个事务在执行过程中的某个固定点“生效”，则可以将此并发执行“分解”为顺序历史记录。有多种可能的组合： 您可以将事务 B 移至 A 之前或 A 之后。您可以将事务 C 移至 A 之前或 A 之后。您还可以使 B 在 C 之前发生，或 C 在 B 之前发生.

Possible sequential histories: ABC or ACB or BAC or BCA or CAB or CBA

如果这些连续历史记录中至少有一个对于正在操作的对象来说是valid，例如，您最终不会从只放入一项的队列中弹出两项，那么现在的连续valid历史记录是 H 的序列化，并且 H 被称为是可序列化。

请注意，在原始历史记录 H 中，虽然 A 和 B 是并发的，并且 A 和 C 是并发的，但 B 和 C 是“不”并发的：事务 B 严格在事务 C 开始之前完成。只有在这样的情况下，即一笔交易在另一笔交易开始之前完成，我们可以在历史记录中定义一个订单：B 如果我们上面列出的可能序列化之一是< C.

有效

并且还保留这个顺序，那么我们说该序列化是H的严格序列化，并且H是严格可序列化。 Possible sequential histories that preserve the order: ABC, BAC, BCA

这些是 H 的

严格序列化

，因为在所有这些中都是 B 在所有事务（在本例中为 A、B 和 C）中只有一个操作的< C.

特殊情况

中，则严格序列化称为线性化，并且 H 被称为可线性化。我们之所以给这种特殊情况起一个自己的名字，是因为它具有一些一般严格可串行性所不具备的特殊独特属性：

1) Linearizations are local properties. If a history of operations on 
   object x is linearizable, and a history on object y is linearizable, 
   then a history containing operations on both x and y is linearizable. 
   This means we only need to determine linearizability on a per-object 
   basis, which makes the system modular.

2) Linearizability does not require blocking. No process needs to block 
   to achieve linearizability.

请注意，严格可串行性意味着可线性化，但反之则不然。

---

请注意，始终要求生成的顺序历史对于正在操作的对象有效。

请注意，对于给定的历史 H，可以有多种可能的序列化、严格序列化或线性化。

请注意，在本次对话中，我们仅确定特定给定历史 H 的可序列化/线性化。证明特定历史是否可序列化或可线性化很容易。证明某些并发系统中某个对象上的

任何

历史 H 始终是可序列化或线性化的非常困难。