一致性模型规定客户端能看到什么

本讲从 KV 存储的读写历史讨论一致性。单个操作各自执行正确,仍然可能组合出应用无法接受的结果:副本落后、缓存过期、换主和请求重试,都可能改变多个客户端看到的顺序。

线性一致性(Linearizability)先给每个对象规定顺序执行时的行为,再要求并发历史能够解释成某种合法顺序。每个操作都可以在调用与返回之间找到一个线性化点,所有点组成的顺序既满足对象语义,也保留没有重叠的操作之间的真实时间先后关系。

赞助商

怎样检查一个并发历史

寄存器读写历史中,读到新值后又读到旧值的差别

图中的横线表示调用到返回的区间,W(1) 是写入 1,R(1) 是读取返回 1。并发读写允许多个合法结果,因为它们的线性化点可能有不同顺序;但选择一个顺序后,后续读的结果仍要与它一致。

例如初值为 0,写 1 还没有返回时,读 A 返回 1,之后才开始的读 B 返回 0。即使写仍在执行,这个历史也无法线性化:A 读到 1,迫使写在线性顺序中排在 A 之前;真实时间又要求 A 在 B 之前,于是 B 不能回到 0,除非中间确实有另一次写 0。

线性化点是一种解释客户端历史的证明工具,不要求服务器真的在那个瞬间执行所有内部步骤。检查历史时,应先找时间约束,再找返回值对顺序施加的约束,判断是否存在同时满足它们的排列。

完成的写不能因换主而消失

客户端完成写 1 后,另一客户端才开始读,读就必须看到该写或更晚的更新。系统不能以读者“不知道发生过写”为理由返回旧副本。主备切换后忘记已回复的操作,也会违反这一要求。

请求重试同样影响历史。一次写在重试中被执行两遍,可能把已经出现的新值覆盖回旧值。要提供线性一致的调用语义,服务需要把同一次调用的重传合并,而不是把每一条网络报文都当成独立操作。

线性一致不等于多对象事务

线性一致可以描述读、写、原子递增或比较交换等单个操作。跨账户转账还需要把多个对象上的一组操作组合成事务;分别线性一致地更新两个账户,仍可能让并发审计看到只完成一半的转账。

串行化关注事务能否解释成某种串行执行;严格可串行化进一步保留事务的真实时间顺序。讨论这些概念时,必须先说明操作对象和事务边界,不能把“强一致”当成不需要定义的统一保证。

一致性的通信代价

如果西海岸的写已经完成,东海岸随后读取就必须获知这次更新。这个约束决定系统不能永久只依靠互不通信的本地副本;网络分区时,也不能要求分区两侧都持续返回线性一致结果。

最终一致允许副本后台同步,改善本地访问和分区期间的可用性,但应用可能看到旧值、顺序变化和冲突。它不是所有业务都能接受的替代方案。课程后面的 ZooKeeper、缓存和 Spanner,将分别展示怎样在明确的保证下选择不同设计。

参考资料