当前位置：文江博客话题详情

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

发布于 2024-12-17 02:18:02 字数 166 浏览 5 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

无需解释 2024-12-24 02:18:02

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

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

（根据此处的深入描述进行总结）

举个例子：

enter image description here

这里，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)

It was hard to find information about this subject. However, At some point I found a statement that explained it clearly:

Linearizability gives isolation at the level of operations, while Serializability gives isolation at the level of transactions.

(summarized from the in-depth description found here)

As an example:

enter image description here

Here, A, B and C are three different transactions running at the same time. r(varname) means that the current transaction is accessing the value inside varname, and w(varname) means that the current transaction is writing a certain value in varname.

Now, to create a linearized history of these events, we have to make sure that no two operations are happening at the same time. An operation that has started while another operation already started should appear behind the first operation.

In this case:

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

To create a Serialized history of these events, one has to separate all the operations of the transactions A, B and C so there are no interleaved operations from other transactions.

From our example this could result in:

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

回复收藏 0 原文

萌辣 2024-12-24 02:18:02

假设您有一个可以对其进行操作的对象。将事务定义为您希望对此对象执行的一组操作。

令 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

这些连续历史记录中至少有一个对于正在操作的对象有效，例如，您最终不会从只放入一项的队列中弹出两项，那么该连续历史记录。是序列化 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 < C.

在所有事务（在本例中为 A、B 和 C）中只有一个操作的特殊情况中，则严格的序列化称为线性化 strong>，并且 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 始终是可序列化或线性化的相当困难。

Assume you have an object that you can do operations on. Define transaction to be a group of operations you wish to perform on this object.

Let H be the following history of transaction invocations and responses performed on your object by processes A, B, and C.

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

You can visually see processes A, B, and C are executing concurrent transactions of operations on the object.

If you assume that each transaction 'takes effect' at some fixed point in it's execution, you can 'break' apart this concurrent execution into a sequential history. There are multiple possible combinations for this: You can move transaction B to occur before A, or after A. You can move transaction C to occur before A, or after A. You can also make B happen before C, or C happen before B.

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

If at least one of these sequential histories is valid for the object being operated on, for example you don't end up popping two items from a queue you only put one item into, then that sequential history is a serialization of H, and H is said to be serializable.

Notice that in the original history H, while A and B were concurrent, and A and C were concurrent, B and C were not concurrent: transaction B finished strictly before transaction C started. Only in such a case, where a transaction finished before another one started, we can define an order on the history: B < C.

If one of the possible serializations we listed above is valid and also preserves this order, then we say that that serialization is a strict serialization of H, and H is strictly serializable.

Possible sequential histories that preserve the order: ABC, BAC, BCA

These are the strict serializations of H because in all of them B < C.

In the special case that all of the transactions (in this case A, B, and C) only have a single operation in them, then the strict serialization is called a linearization, and H is said to be linearizable. The reason we give this special case it's own name is because it has some special unique properties that general strict-serializability does not have:

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.

Notice that strict-serializability implies linearizability, but not the other way around.

Notice that it is always a requirement that the resulting sequential history is valid for the object being operated on.

Notice that for a given history H, there can be many possible serializations, strict serializations, or linearizations.

Notice that in this conversation we are only determining serializability/linearizability for a specific given history H. Proving that a specific history is or isn't serializable or linearizable is easy. Proving that any history H in some concurrent system on some object will always be serializable or linearizable is substantially harder.

回复收藏 0 原文