线性一致性

Introduce

所谓的linearizability其目的在于描述系统的数据,对外看起来就像只有一份,所有针对这部分数据的操作都是原子(Concurrency-atomic)的;在分布式系统领域来讲和CAP-consistent是等价的;在多核并发编程时由于存在CPU-Cache一致性问题,linearizability的概念同样适用。

What

通用的定义(分布式系统 and 多核系统)

every read returns the latest value written into the shared variable preceding that read operation, then the shared object is linearizable

时序角度

对于linearizability 系统,任意的两个操作的顺序都是可以比较的,即存在total order. 考虑:如果数据只有一份拷贝,同时操作又都是atomic的,那么任意两个操作总有先后关系,所以total order必然存在。

对比CAP-consistent

任意的一条读操作R,如果发生在某条写操作W完成之后(或执行过程中),那么R读到的要么是W的内容,要么是W之后的写操作写入的内容

这里的定义与CAP-consistent略有出入,为什么放宽限制为或执行过程中呢?因为定义之中所有的之前之后是否完成都是所谓上帝视角来判定的;对于client而言只有clients之间额外的交流沟通(参考后文),而对于clients之间额外的交流沟通而言,W完成与否也是无法判定的,考虑即使是执行W的client,也只能拿到W完成的响应时间,并不能真正知道server端W完成的时间(中间有网络延迟,物理时钟有误差等),即使利用因果关系进行clients之间额外的交流沟通也无从考证真正完成的时序。因此W是否真的完成并意义不大。

结合图示来看: 一旦有client读取到了写入的值,即使这个写入操作还没有完成,那么后续的读取操作都应该能读到该值或者之后写入的值

Why

  • 对于clients而言,一旦存在额外的交流沟通的渠道,linearizability问题就会凸显,例如:
    • A,B两个人去刷飞机票,A刷到了,B没有刷到(显示全部售光),如果A,B之间没有交流,即使B刷票先于A,则交易看起来也没有什么问题
    • 但如果A,B两个人存在交流,例如B没有刷到票,然后跑去隔壁房间问A,恰巧碰到A正在刷,并且刷票成功(B刷票 happened before A刷票),则交易存在问题
  • 如果能够提供linearizability的分布式系统,则:
    • 可以利用该系统实现分布式锁操作
    • 利用锁操作又可以用进行leader-election
    • 利用锁操作可以达成uniqueness guarantees
    • linearizability sequence number — 可以用来解决total order问题

How

如果可以保证分布式系统的各操作时序可比较(total order),则linearizability可达成;所以linearizability的实现问题可以转换成实现fault-tolent total order

而实现fault-tolent total oerder是一个distributed consensus问题

似乎就是一个循环: 如果实现了linearizability,则实现了linearizability sequence number,从而解决了total order问题,即实现了distributed consensus;而实现linearizability 又依赖通过distributed consensus实现total order

Weakness

linearizability is slow all the time, not only during a network fault(节点间通信达成共识本身就很耗时)

References

  1. Martin Kleppmann. 《Designing Data-Intensive Applications》9.Linearizability

Comments