系统日报-20220125(Linearizability 和 Serializability 傻傻分不清？)

《系统日报》持续关注分布式系统、AI System，数据库、存储、大数据等相关领域文章。每天以摘要的形式精选不超过三篇系统文章分享给大家。 如果你有好文章推荐，或者有其他任何想法，欢迎在 Articles Weekly Repo[1]提 issue。

Linearizability 和 Serializability 傻傻分不清？

两者对比

来源：http://www.bailis.org/blog/linearizability-versus-serializability/[2]

摘要：Peter Bailis[3] 用简短的篇幅介绍了两者的区别。这两个概念本属于不同领域，其中可串行化（Serializability ）出自数据库领域，而可线性化（Linearizability）出自分布式系统和并发编程领域，近年来这两个词被越来越多的放在一块考量，大抵是因为分布式数据库越来火吧。

这两个概念描述的都是一种理想状态，在实际工程中，我们的数据库大概率很难保证严格的串行化，同时，我们的分布式系统甚至多核系统也大概率难以保证线性化执行。因为这样做实在是太伤性能了，但在一些确定性要求极高的领域，比如金融，这些保证又十分重要。

那它们描述的到底是一种怎样的理想状态呢？

可线性化（Linearizability）是针对单个对象上（比如一个全局变量）的单个操作（比如读或者写），所有操作都能够被原子的、全局有序的完成。粗略来讲，就是一个值一旦被写入，后面的读都能读到此值，直到其再次被修改；一个值一旦被读到，后面的读都会读到同样的值，直到其被修改。可线性化其实是原子一致性 （atomic consistency） 的别称，也即 CAP 中的 C（Consistency，一致性）。无论是单机多核，还是多机，在物理上，本质上都是多个执行流，当其进行协作时，如果不进行通信，很难保证对某个对象操作的全局有序。但要保证严格线性化，势必会引入过多通信，从而大大降低性能。

由于有真实时间线作为参照，Linearizability 是可组合的（composable），即如果系统中针对每个对象的操作是可线性化的，则系统中（针对所有对象）所有的操作，都是可线性化的。

可串行化（Serializability）是针对多个对象上的多个操作组成的事务，所有事务都能够被串行执行，不过顺序不一定确定，即，允许多种可能的顺序。可以形象的理解为，在逻辑时间线上，所有的事务会坍缩成一个点（原子性），并且按照一定顺序进行排列，可能有多种排列方式，但它们一定是有序的。这其实是 ACID 中 I（Isolation，隔离性），当初是为了保证数据库的正确性而引入的。如果数据库中所有单个事务都能保证正确性，即事务执行前后的一致性，ACID 中的 C，（即要维持某种事务前后的不变性，比如转账前后，账户款项总和是确定的），那么一组事务串行化执行后，数据库仍能保证正确性。

由于没有一个绝对参考系，Serializability 是不可组合的，即多机中的的事务是难以进行全局排序的。

结合 Linearizability 与 Serializability，我们得到了严格的串行化（strict serializability），即确定的串行化，所有事务串行化执行，并按真实时间有序。举个例子，首先开始一个事务 T1，更新变量 x；之后再开启一个事务 T2，会读取变量 x；在严格串行化的系统中，T2 一定能读到 T1 更新的 x 的值；但是在普通串行化系统中，T2 有可能被重排到 T1 前面，即和事务的真实起始时间并不完全一致。

参考资料

[1]任何想法都欢迎来提 issue: https://github.com/DistSysCorp/ArticleListWeekly/issues

[2]Peter Bailis: Linearizability versus Serializability: http://www.bailis.org/blog/linearizability-versus-serializability/

[3]Peter Bailis: http://bailis.org/