我的编程空间,编程开发者的网络收藏夹
学习永远不晚

如何验证线性一致性

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

如何验证线性一致性

线性一致性(Linearizability)是分布式系统中常见的一致性保证。那么如何验证系统是否正确地提供了线性一致性服务呢?本文希望从‘什么是线性一致性’,‘如何验证线性一致性’,问题复杂度,常见的通用算法,以及工程实现五个部分,直观、易懂地回答这个问题。

什么是线性一致性

MAURICE P. HERLIHY 和 JEANNETTE M. WING曾在“ Linearizability: A Correctness Condition for Concurrent Objects ” 中对线性一致性给出了形式化的定义和证明,对分布式系统来说,简单的讲就是即使发生网络分区或机器节点异常,整个集群依然能够像单点一样提供一致的服务,即依次原子地执行每一条操作。假如我们可以站在最终操作执行的视角,将整个系统看做一个整体,一个保证线性一致性的服务应该如下图所示进行服务:
如何验证线性一致性

由于每条操作是依次、原子的执行,相互之间没有重叠,为了方便理解,可以把一个操作在图上简化为一个点。如下图所示:

如何验证线性一致性

然而,实际情况中,分布式系统通常是很多节点作为一个整体对外提供服务,并在内部处理网络或节点异常,我们无法站在上帝视角看到其执行序列。同时,我们真正关心的也是其作为一个整体对外的表现,而不是其中的每个单独节点。我们所能做的是站在客户端的角度,通过读写事件的发起和结束来感知整个系统。正如站在地球上仰望星空,通过光来感知天体,看到的每一次闪烁,可能真正发生在上万年之前。因此,下图才是真正可以看到的情况:
如何验证线性一致性

上图,展示了在每个客户端看来,其请求从发起到结束的时间点。因此,我们希望通过一系列客户端的执行和返回序列来判断系统是否正确提供了线性一致性服务。

如何验证线性一致性

为了判断系统是否正确提供了线性一致性,首先在运行过程中获得一系列不同的执行历史,接着验证每组历史是否满足线性一致性,只要有一个不满足,便可以说系统不满足线性一致性。但如果没有发现不满足的历史,也不证明系统一定正确。然而,在工程中通过对大量的执行历史的验证,使得我们对自己的系统更充满信心,这就足够了。那么现在的问题转变为:如何验证一组执行历史是否满足线性一致性

通过客户端可以看到一个读写请求的发起和结束时间,而其真正在服务端的执行可能发生在开始和结束中间的任意一点。因此,验证线性一致性的关键就是找到一组依次执行的序列,如果这组执行序列存在,则可以说这组执行历史是满足线性一致的,如下图所示:
如何验证线性一致性
明显的,存在这么一组序列,因此我们说这组执行历史是符合线性一致性的。再来看一个不符合线性一致性的例子,如下图,可以看出,由于Client 3已经读到1,说明在Client 3请求结束前Client 2已经写成功,而又没有其他请求再次修改x的值,因此Client 4不应该在之后读到0。
如何验证线性一致性
实践中,通常会通过在频繁注入异常的情况下,随机生成请求序列,收集执行的发起和结束历史,并寻找合理的线性执行序列,如Jespen。

问题复杂度

直观来看,这个问题是一个排序问题,极端情况下的时间复杂度为O(N!)。事实上,Phillip B. Gibbons和Ephraim Korach在Testing Shared Memories中已经证明其是一个NP-Complete问题。虽然Gavin Lowe在Testing for Linearizability中给出了一些特殊限制下的多项式甚至是线性复杂度的算法,但在通用场景下,判定线性一致性并不是一个容易解决的问题,其搜索空间会随着执行历史的规模急速膨胀。

通用算法

虽然判定线性一致性的复杂度极高,但我们还是能够通过一些技巧,在大多数场景下,在工程可接受的时间内给出结果,这里介绍三个常见的,且一脉相承的通用算法。在此之前,先对算法面临的问题进行抽象,以下图执行历史为例,给出算法的输入和期待的输出:

如何验证线性一致性

Input: 调用历史

1,Client1: Invoke Put x=0
2,Client2: Invoke Put x=1
3,Client1: Return Put x=0
4,Client3: Invoke Get x
5,CLient4: Invoke Get x
6,Client3: Return Get 1
7,Client4: Return Get 0
8,Client2: Return Put x=1

Output: 执行序列

Client1 Put x=0
Client4 Get 0
Client2 Put x=1
Client3 Get 1
1,WG算法

请求的调用历史中,存在着一种偏序关系:Prev,如果一个请求的Return发生时间早于另一请求的Invoke,我们便称其Prev另一个请求。显而易见,这种偏序关系是一致性验证算法必须要保留的。祸兮福所倚,也正是这种对偏序关系的保留,给了算法加速的可能。WG算法的思路非常简单:从调用历史中找出没有Prev的项,将其对应的请求执行并取出,之后对剩下的调用历史重复该算法,直到没有更多的调用历史或执行结果不满足。

如上述例子中,“Client1 Put x=0” 和 “Client2 Put x=1” 由于其Invoke前没有任何请求Return,可以首先被取出。假如选择“Client1 Put x=0”,将其对应的Invoke和Return从调用历史中取出,得到新的历史:

2,Client2: Invoke Put x=1
4,Client3: Invoke Get x
5,CLient4: Invoke Get x
6,Client3: Return Get 1
7,Client4: Return Get 0
8,Client2: Return Put x=1

和一条已经序列化的请求:

Client1 Put x=0

此时可以看到剩余的历史中,每一个请求的Invoke前都没有其他请求的Return,因此都可以作为下一个取出的选择。假设这次选择Client3 Get 1,然而,明显这个时候执行Get得到应该是0,与该请求的实际执行结果返回1不同,此时,需要回退并尝试其他取出策略。可以看出WG算法其实是树的深度优先搜索,其搜索树如下图,其中每个节点标识的是本次尝试序列化的请求对应的调用历史中的Invoke序号:

由于找到一个线性序列便可以停止,因此其中虚线部分是不会被实际执行的。

2,WGL算法

WGL算法由Gavin Lowe在WG算法的基础上进行改进,其改进的方式主要是对搜索树的剪枝:通过缓存已经见过的配置,来减少重复的搜索。缓存配置有两部分组成:

  • 当前已经序列化的请求

  • 当前x值

由上面的搜索过程可知,如果当前序列化的请求和当前的x值完全相同,则后续的搜索过程一定一致,因此可以略过。

3,P-compositionality算法

P-compositionality算法利用了线性一致性的Locality原理,即如果一个调用历史的所有子历史都满足线性一致性,那么这个历史本身也满足线性一致性。因此,可以将一些不相关的历史划分开来,形成多个规模更小的子历史,转而验证这些子历史的线性一致性,例如kv数据结构中对不同key的操作。上面提到了算法的计算时间随着历史规模的增加急速膨胀,P-compositionality相当于用分治的办法来降低历史规模,这种方法在可以划分子问题的场景下会非常有用。

为什么Solitaire

工程实践中,不只分布式系统,还包括需要并行访问的系统,都可能需要验证系统对外暴露的线性一致性功能。当然也有不少验证线性一致性的工具,比如大名鼎鼎的Jespen使用的Knossos,是一个Clojure版本的WGL的算法实现;Porcupine是一个Go版本的P-compositionality实现;linearizability-checker是P-compositionality算法作者自己实现的一个样例。但使用中还有几个问题没有解决:

  • 计算速度慢:由于上面提到的复杂度,一致性算法验证时间通常是相关测试中的瓶颈。尽可能的加快其计算速度,可以在相同时间内验证更多的历史,对发现系统中的潜在问题至关重要。

  • 数据模型单一:大多数的验证工具面向的都是KV接口,这就要求使用者将千差万别的系统实际接口转化为KV接口使用,而这层转换会掩盖系统中的众多复杂性,比如将Device接口转化为KV后会丢失对相互覆盖操作的验证。

  • 具体问题具体分析:对一些数据模型来说,可能存在多项式甚至是线性复杂度的算法,那么针对这些数据模型使用通用的WGL算法就舍近求远了。

Solitaire(https://github.com/CatKang/Solitaire)是一个C++实现,更快速,支持多数据模型的线性一致性检测工具,致力于解决上述问题。其命名来源于上世纪著名的Windows桌面纸牌游戏,要求玩家在保证大小先序关系的限制下,将打乱的扑克牌整理为有序。可以说与我们的线性一致性验证工作非常契合了。

参考

  • Linearizability: A Correctness Condition for Concurrent Objects

  • Testing for Linearizability

  • Faster linearizability checking via P -compositionality

  • Testing Distributed Systems for Linearizability

  • Testing Shared Memories

  • 线性一致性理论

  • Solitaire: 一个更快的,适配更多数据模型的一致性验证工具

  • knossos: Jespen所使用的一致性验证工具,WGL算法实现

  • porcupine: go版本P-compositionality算法实现

  • linearizability-checker: P-compositionality算法实现

  • Jespen

原文链接:https://mp.weixin.qq.com/s/calyZj0-ZfiYuDlJWQoHaA

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

如何验证线性一致性

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

redis如何保证数据一致性

Redis 保证数据一致性的方法主要有以下几种:主从复制:Redis 支持主从复制机制,通过将主节点的数据复制到备用的从节点上,保证数据的一致性。当主节点发生故障时,从节点可以顶替主节点继续提供服务。数据持久化:Redis 支持将内存中的数
redis如何保证数据一致性
2024-05-10

Cassandra如何保证数据一致性

Cassandra 使用了一系列机制来保证数据一致性,包括:同步复制:Cassandra 采用多节点复制策略,将数据同时复制到多个节点上。这样即使某个节点出现故障,仍可以通过其他节点获取数据,保证数据的可靠性和一致性。Quorum 一致性级
Cassandra如何保证数据一致性
2024-04-09

redis和mysql如何保证一致性

保证 redis 和 mysql 一致性的方法有直接写入 mysql 和事务补偿机制:直接写入 mysql:通过触发器将 mysql 数据变更同步到 redis,保证一致性但性能较低;事务补偿机制:先写入 redis,同时记录补偿事务,容忍
redis和mysql如何保证一致性
2024-04-20

rabbitmq如何保证数据的一致性

RabbitMQ 通过以下方式来保证数据的一致性:事务: RabbitMQ 支持事务机制,可以将多条消息发送到队列中原子操作。如果事务中的任何一个步骤失败,整个事务会回滚,确保数据的一致性。确认机制: RabbitMQ 提供了消息确认机制,
2023-10-26

并发扣款,如何保证一致性?

同一个用户在并发“查询,逻辑计算,扣款”的情况下,余额可能出现不一致,有什么优化方法么?今天和大家聊一聊这个问题。

Cassandra如何保证数据的一致性

Cassandra 通过以下几种方法来保证数据的一致性:Quorum Consistency Level:Cassandra 使用 Quorum 一致性级别来确保数据的一致性。在写入和读取数据时,至少需要超过半数的节点确认操作,才能认为操作
Cassandra如何保证数据的一致性
2024-04-09

Teradata如何保证数据的一致性和完整性

Teradata通过以下方式保证数据的一致性和完整性:ACID事务: Teradata使用ACID(原子性、一致性、隔离性和持久性)事务来确保数据操作的一致性和完整性。这意味着数据操作要么完全成功,要么完全失败,以确保数据始终处于一致的状态
Teradata如何保证数据的一致性和完整性
2024-04-09

Prometheus如何保证数据的精确性和一致性

Prometheus 通过以下方式保证数据的精确性和一致性:数据采集方式:Prometheus 使用 Pull 模型来采集数据,即通过定期向各个目标服务发送HTTP请求来获取数据。这种方式可以确保数据的实时性和准确性,避免了由于网络延迟等因
Prometheus如何保证数据的精确性和一致性
2024-03-04

详解Spring多线程下如何保证事务的一致性

我们先来大概的了解下Spring事务的工作原理,核心技术是通过AOP实现,将获取的Connection对象绑定到当前线程上下文中(ThreadLocal)。

如何保证 Java mutator 的数据一致性?(如何确保java mutator的数据一致性)

在Java编程中,mutator方法(也称为setter方法)用于设置对象的属性值。确保mutator方法的数据一致性是非常重要的,因为它直接影响到对象的状态和业务逻辑的正确性。以下是一些确保Javamutator数据一致性的步骤:一、遵循命
如何保证 Java mutator 的数据一致性?(如何确保java mutator的数据一致性)
Java2024-12-13

Java etcd 究竟如何确保数据一致性?(Java etcd如何保证数据一致性 )

在分布式系统中,数据一致性是一个至关重要的问题。而Javaetcd作为一个分布式键值存储系统,在保证数据一致性方面有着独特的机制和策略。etcd是CoreOS团队开发的一个高可用的键值存储系统,用于共享配置和服务发现。它基于Raft一致性算法,能够在分布式环境中
Java etcd 究竟如何确保数据一致性?(Java etcd如何保证数据一致性  )
Java2024-12-16

下单时如何保证数据一致性?

通过本篇博客,我们详细探讨了Redis中的事务和管道机制,了解了它们如何在实际应用中保证数据一致性和优化性能。无论是强调一致性还是追求性能,都可以根据业务需求选择合适的机制来达到最佳效果。

MySQL和Redis如何保证数据一致性

MySQL与Redis都是常用的数据存储和缓存系统。为了提高应用程序的性能和可伸缩性,很多应用程序将MySQL和Redis一起使用,其中MySQL作为主要的持久存储,而Redis作为主要的缓存。在这种情况下,应用程序需要确保MySQL和Re
2023-08-22

Redis 和 MySQL 如何保证数据一致性?

启动一个订阅程序去订阅数据库的binlog,获得需要操作的数据。在应用程序中,另起一段程序,获得这个订阅程序传来的信息,进行删除缓存操作。

如何保证NFS文件锁的一致性?

在存储系统中, NFS(Network File System,即网络文件系统)是一个重要的概念,已成为兼容POSIX语义的分布式文件系统的基础。它允许在多个主机之间共享公共文件系统,并提供数据共享的优势,从而最小化所需的存储空间。本文将通

redis和数据库如何保证一致性

redis 与数据库之间的数据一致性可以通过以下机制实现:1. 主从复制机制,通过异步复制实现一致性;2. 双写机制,同时向 redis 和数据库写入数据保持同步;3. 乐观锁,通过版本号或时间戳控制并发访问保证一致性;4. 事务补偿机制,
redis和数据库如何保证一致性
2024-04-20

编程热搜

目录