先记住这个答案
顺序一致性(sequential consistency)要求多进程上的所有操作存在一个全局顺序,且该顺序与每个进程的程序顺序一致。但它允许该全局顺序与真实时间无关。线性一致性(linearizability)在顺序一致性基础上增加实时约束:每个操作必须在调用(invocation)和返回(response)之间的某个点生效,因此全局顺序必须与实时顺序兼容。若操作A在真实时间先于B完成,则A必须排在B前。这带来更强的可验证性:任何客户端用时钟就能判断观察到的事件序列是否合法。
- 顺序一致性只约束程序序,不约束实时序
- 线性一致性要求操作在调用-返回区间内生效
- 需要真实时间顺序的分布式算法必须用线性一致性
机制:全局序与实时序的分裂
顺序一致性由Lamport提出,要求各进程的操作按程序序排列,并存在一个全局线性序,使读操作返回该序中最近一次写的结果。这个全局序不需要与物理时间吻合,因此真实时间上先完成的后写可以被排到先写之前,只要所有进程观察到同一个次序。
线性一致性由Herlihy和Wing提出,它额外规定:如果操作A在操作B开始之前已返回,那么A必须排在B前。每个操作都在调用与返回间有一个线性化点,全局序由这些点的先后决定。该条件让客户端可以用时钟验证历史是否符合规范,而顺序一致性缺乏这种可判定性。
场景:两个写后的交叉读
设进程P先写x=1并返回,稍后进程Q写x=2并返回,之后P读x得到2,Q读x得到1。真实时间上P写返回早于Q写返回,且两次读都在Q写返回之后。顺序一致性下可构造全局序:P写1、Q写2、P读2、Q读1,各进程内读在写后,所以合法。
线性一致性下该结果非法。因为P写返回先于Q写开始,实时序要求P写在Q写前生效。Q读在自身写之后,且P写在Q写之前,所以Q读应看到Q写的2而非1。要Q读1,P写必须覆盖Q写,但P写早已返回,无法覆盖。因此只能用线性一致性才可排除这种倒序。
适用边界与失效条件
当应用依赖操作绝对先后时,顺序一致性会失效。例如分布式锁的获取与释放,若后发的写先被其他进程看到,可能使两个节点同时认为持锁。计费扣款、唯一编号生成也要求“A一旦返回,后续操作必见A的效果”,否则会重复扣款或编号冲突。
工程上,线性一致性通常通过Raft/Paxos等共识实现,每次写需多数派确认,延迟为网络往返。顺序一致性可让副本异步传播,例如Cassandra指定一致性等级,但无实时保障。若不能容忍顺序倒流,必须放弃部分可用性换取线性一致性;业务不敏感时可退化为顺序一致性提升吞吐。
容易答错的地方
- 认为顺序一致性就是每个进程内部有序
- 顺序一致性还要求存在一个全局总序,各进程的操作在该总序中与程序序一致。仅仅保证单进程顺序不构成分布式一致性,必须定义跨进程的读-写关系,否则无法形式化并发操作的结果。
- 把线性一致性等价于强一致读己之写
- 线性一致性涵盖所有操作间的实时顺序,不仅是读己之写。它要求如果操作A在B前返回,则A必须在B前生效,因此也禁止旧读,并保证交叉操作可按时钟排序。只保证写后读新值是不够的。
面试官还会怎么问?
顺序一致性下,两个并发写最终以什么顺序生效?
顺序一致性没有定义真实时间顺序,只要存在一个全局序即可。两个写操作如果没有额外的同步约束,外部无法判断谁先谁后,只能依据每个进程的逻辑顺序推断。
线性一致性是否要求每个操作都瞬时完成?
不要求,允许操作在调用和返回之间的任意时刻原子生效,即线性化点。实际系统中可通过共识或物理时钟实现这一点,但线性化点不必是单个瞬间。
实现线性一致性的系统也满足顺序一致性吗?
是的,线性一致性是顺序一致性的严格强化。任何线性一致性的执行历史都满足顺序一致性,但反之不成立,这也是线性一致性更昂贵的原因。
参考资料
示例用于理解所注明的运行环境与边界;延伸学习可结合原文中的更多案例。