浅析分布式系统中的 Linearizability

简介:

在分布式系统里,出于可靠性(reliability)或者性能的考虑,数据通常会被复制为多个副本。因此,系统需要定义一组协议,来规定用户读写多副本时的行为。这组协议称之为 consistency model
最终一致性(eventually consistency),linearizability(atomic consistency)是不同类型的一致性模型。下图是最终一致性模型的示例,用户 B/C 在读取不同的副本时看到了不同的 x 的值。请注意,用户A,B,C的操作是完全串行执行的,即操作在时间轴上没有重叠。C 读取操作发生在 B 之后,却读到了过期的值。可见,最终一致性是一个较弱的一致性模型,用户需要自己解决读取到过期数据的问题。

eventually_consistency

接下来,让我们看看一个中间状态的一致性模型,它比最终一致性强,但是比 linearizability 弱。从时间轴上可以看到,B0 发生在 A0 之前,读取到的 x 值为0。B2 发生在 A0 之后,读取到的 x 值为1。而读操作 B1,C0,C1 与写操作 A0 在时间轴上有重叠,因此他们可能读取到旧的值0,也可能读取到新的值1。注意,C1 发生在 B1 之后(二者在时间轴上没有重叠),但是 B1 看到 x 的新值,C1 反而看到的是旧值。即对用户来说,x 的值发生了回跳。

casual_consistency

Linearizability,则提供了更强的一致性保证。注意下图中的 C1 和 B1 操作,C1 发生在 B1 之后,但是与 A0 并行。在 Linearizable 系统中,如果 B1 看到的 x 值为1,则 C1 看到的值也一定为1。而在前两种一致性模型中,同样的场景,C1 看到的 x 值既可能是0,也可能是1。在 Linearizable 的系统中,任何操作在该系统生效的时刻都对应时间轴上的一个点。如果我们把这些时刻连接起来,如下图中紫线所示,则这条线会一直沿时间轴向前,不会反向回跳。所以,在 Linearizable 系统中,任何操作都可以互相比较决定谁发生在前,谁发生在后。例如 B1 发生在 A0 前,C1 发生在 A0 后。而在前面较弱的一致性模型中,我们无法比较诸如 B1 和 A0 的先后关系。对这个性质更正式的表述是:在 Linearizable 系统中,我们可以获得操作的全序(total order)。而在提供较弱一致性的系统中,我们只能获得操作的偏序(partial order)。

linearizability

注意:

由于网络延时以及系统本身执行请求的不确定性,请求发起得早不意味着在服务端被执行得早。例如 A0 比 B1 在客户端发起得早,但 A0 在存储系统生效晚于 B1。反之,在服务端被执行得早的请求也有可能很晚客户端才收到结果,例如 C0。

需要 Linearizability 语义的一个典型场景是实现分布式锁。例如当一个锁被 client A获取后,则希望后续看到该锁的状态都是被A locked,而不是其他状态。

附录

A. Linearizability 与 Serializability 的差别

关于二者的差别,可以参考这一篇文章

目录
相关文章
|
JavaScript 前端开发 UED
JS:如何获取浏览器窗口尺寸?
JS:如何获取浏览器窗口尺寸?
633 1
|
Linux Go iOS开发
掌握Go语言:配置环境变量、深入理解GOPATH和GOROOT(1)
掌握Go语言:配置环境变量、深入理解GOPATH和GOROOT(1)
2318 0
|
8月前
|
数据采集 机器学习/深度学习 算法框架/工具
Python:现代编程的瑞士军刀
Python:现代编程的瑞士军刀
459 104
|
小程序
【01】微信支付商户申请下户到配置完整流程-微信商户申请-资料准备以及提交-微信商户密钥申请-申请+配置完整流程-优雅草卓伊凡
【01】微信支付商户申请下户到配置完整流程-微信商户申请-资料准备以及提交-微信商户密钥申请-申请+配置完整流程-优雅草卓伊凡
629 2
【01】微信支付商户申请下户到配置完整流程-微信商户申请-资料准备以及提交-微信商户密钥申请-申请+配置完整流程-优雅草卓伊凡
|
前端开发 Java 关系型数据库
基于ssm的社区物业管理系统,附源码+数据库+论文+任务书
社区物业管理系统采用B/S架构,基于Java语言开发,使用MySQL数据库。系统涵盖个人中心、用户管理、楼盘管理、收费管理、停车登记、报修与投诉管理等功能模块,方便管理员及用户操作。前端采用Vue、HTML、JavaScript等技术,后端使用SSM框架。系统支持远程安装调试,确保顺利运行。提供演示视频和详细文档截图,帮助用户快速上手。
546 17
|
人工智能 Java 物联网
没有好的学历,Java开发未来的路应该怎么走?
在数字化时代,Java开发者即使没有高学历,也能通过拥抱新兴技术(如大模型应用与鸿蒙系统开发)、积累实战经验、持续学习新技能等途径实现职业突破。从参与开源项目到关注行业动态,再到规划技术专家或管理路线,建立人脉网络并利用教育平台提升能力,开发者可拓宽技术边界,适应日新月异的技术需求,在未来发展中占据一席之地。
|
机器学习/深度学习 人工智能 编解码
【AI系统】Transformer 模型小型化
本文介绍了几种轻量级的 Transformer 模型,旨在解决传统 Transformer 参数庞大、计算资源消耗大的问题。主要包括 **MobileVit** 和 **MobileFormer** 系列,以及 **EfficientFormer**。MobileVit 通过结合 CNN 和 Transformer 的优势,实现了轻量级视觉模型,特别适合移动设备。MobileFormer 则通过并行结构融合了 MobileNet 和 Transformer,增强了模型的局部和全局表达能力。
1224 8
【AI系统】Transformer 模型小型化
|
关系型数据库 MySQL 数据库
MySQL GTID 主从复制错误修复方法
GTID 复制错误修复方法
9667 0
|
存储 负载均衡 NoSQL
一文让你搞懂 zookeeper
一文让你搞懂 zookeeper
20053 16