线性化和可串行化之间有什么区别？ [英] What is the difference between linearizability and serializability?
问题描述
线性化和可串行化（在Java中）有什么区别？
What is the difference between linearizability and serializability (in the context of Java)? Can you please explain the difference between these with an example or provide a good reference?
推荐答案
两者之间的主要区别是： 可序列化是一个 global 属性；整个操作/交易历史的属性。 可线性化是本地属性；单个操作/交易的属性。另一个区别是线性化包含实时的概念，而串行化却不包括：操作的线性化点必须位于调用和响应时间之间。 （请参阅Tim Harris：事务存储，第二版。请参见
The central distinction between the two is that serializability is a global property; a property of an entire history of operations/transactions. Linearizability is a local property; a property of a single operation/transaction. Another distinction is that linearizability includes a notion of real-time, which serializability does not: the linearization point of an operation must lie between its invocation and response times. (See Tim Harris: Transactional Memory, 2ed. See Herlihy's slides from The Art of Multiprocessor Programming, the section on Linearizability, which are available here, for some examples and proofs.
这两个属性都针对同一目标：顺序一致性。从Herlihy的论文中得出：
Both properties are aimed at the same goal: sequential consistency. From Herlihy's paper:
数据库和分布式系统使用可串行化性作为并发计算的基本正确性条件，在此模型中，事务是控制线程，它将有限的原始操作序列应用于与其他事务共享的一组对象。等价于事务似乎按顺序执行（即没有交织）的事务。可以在非重叠事务对上定义（部分）优先顺序明显的方式。如果事务在顺序历史记录中的顺序与它们的优先顺序兼容，则该历史记录可以严格序列化...
Much work on databases and distributed systems uses serializability as the basic correctness condition for concurrent computations. In this model, a transaction is a thread of control that applies a finite sequence of primitive operations to a set of objects shared with other transactions. A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving. A (partial) precedence order can be defined on non-overlapping pairs of transactions in the obvious way. A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order...
...可线性化可以看作是严格可序列化的特殊情况，其中事务限于由应用于单个对象的单个操作组成。然而，这种单一操作的限制具有深远的实际和形式上的后果，使线性化计算与可序列化的计算具有不同的风格。一个直接的实际结果就是，适合串行化的并发控制机制通常不适合线性化，因为它们引入了不必要的开销并对并发施加了不必要的限制。
...Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object. Nevertheless, this single-operation restriction has far-reaching practical and formal consequences, giving linearizable computations a different flavor from their serializable counterparts. An immediate practical consequence is that concurrency control mechanisms appropriate for serializability are typically inappropriate for linearizability because they introduce unnecessary overhead and place unnecessary restrictions on concurrency.
-
Harris，Tim，James Larus和Ravi Rajwar：交易记忆，第2版。计算机体系结构综合讲座。莫格Claypool，2010年。ISBN9781608452354. URL： http：//www.morganclaypool .com / doi / abs / 10.2200 / S00272ED1V01Y201006CAC011？journalCode = cac
References:
Harris, Tim, James Larus, and Ravi Rajwar: Transactional Memory, 2ed. Synthesis Lectures on Computer Architecture. Morgn & Claypool, 2010. ISBN 9781608452354. URL: http://www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011?journalCode=cac
Herlihy，Maurice和Jeanette Wing：线性化：并发对象的正确性条件。 ACM Trans。编郎和系统。卷1990年7月12日第3期，第463-492页。 URL
http：//www.cs.brown。 edu /〜mph / HerlihyW90 / p463-herlihy.pdfHerlihy, Maurice and Jeanette Wing: Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Prog. Lang. and Sys. Vol. 12, No. 3, July 1990, Pages 463-492. URL http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
Papadimitriou，Christos：并行数据库的可序列化性更新。 ACM杂志第26卷。第4期，1979年10月，第631-653页。网址 http://publications.csail.mit .edu / lcs / pubs / pdf / MIT-LCS-TR-210.pdf
Papadimitriou, Christos: The Serializability of Concurrent Database Updates. Journal of the ACM Vol 26. No 4. October 1979, pp 631-653. URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf
Herlihy，Maurice和Nir Shavit ：多处理器编程的艺术。 Elsevier，2008年。ISBN978-0-12-370591-4。网址： http://www.elsevier.com/wps/ find / bookdescription.cws_home / 714091 / description＃description 关于线性化的PPT幻灯片位于： http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx
Herlihy, Maurice and Nir Shavit: The Art of Multiprocessor Programming. Elsevier, 2008. ISBN 978-0-12-370591-4. URL: http://www.elsevier.com/wps/find/bookdescription.cws_home/714091/description#description PPT slides on linearizability are here: http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx
Attiya，Hagit和Jennifer Welch：顺序一致性与线性化。 ACM交易计算机系统上。 1994年5月12日第2期，第91-122页。 URL http：// citeseerx .ist.psu.edu / viewdoc / download？doi = 10.1.1.133.4969& rep = rep1& type = pdf
Attiya, Hagit and Jennifer Welch: Sequential Consistency versus Linearizability. ACM Transactions on Computer Systems Vol. 12, No. 2, May 1994, Pages 91-122. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf
如果您真的很在意，请阅读介绍定义的文章。对于线性化，这是 线性化：并行对象的正确性条件，Herlihy和Wing 。它很密集，但值得关注。请注意，在软件事务存储社区中，线性化是否是正确的目标/属性是一个悬而未决的问题。
If you really care about this, read the paper that introduced the definitions. For linearizability, that's Linearizability: A Correctness Condition for Concurrent Objects, Herlihy and Wing. It's dense, but worth the attention. Note that in the software transactional memory community, it's an open question whether linearizability is the right goal / property to aim for.
可序列化是关于线性化的结果操作/系统集合可以表示为所有操作的特定顺序（好像执行是按特定顺序执行的...）。线性化是系统中操作的单个子集的属性...如果一个操作/一组操作在其他操作中看起来像是相对于其他操作在（逻辑）时间的特定时刻出现，则它们是线性的。此处的规范论文为 Papadimitriou，并发数据库更新的可序列化性 。
Serializability is about the outcome of a collection of operations/the "system" being expressible as a specific ordering ("as if execution took place in a specific order...") of all the operations. Linearizability is a property of a single subset of operations in the system... an operation/set of operations are linearizable if they appear to the other operations as if they occurred at a specific instant in (logical) time with respect to the others. The canonical paper here is Papadimitriou, The Serializability of Concurrent Database Updates.
考虑原子操作；当您考虑线性化时。当一组（一组）操作（似乎）相对于系统的其他部分原子地发生时，它们是线性的。常见的表述是提供每个操作在其调用和响应之间即刻生效的错觉。 linearizability 的表述是由于 Herlihy ，它强调这是局部属性，而其他类型的顺序一致性属性（例如可序列化这是全球性的。
Think "atomic operation" when you're thinking about "linearizable." A (set of) operations are linearizable when they (appear to) occur atomically with respect to other parts of the system. A common formulation is "provide the illusion that each operation takes effect instantaneously between its invocation and response." The formulation of linearizability is due to Herlihy, which emphasizes that this is a local property, vs. other kinds of sequential consistency properties like "serializability" which are global.
这篇关于线性化和可串行化之间有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
