CAP原则又称CAP定理,指的是在一个分布式系统中,Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可得兼。分布式系统正变得越来越重要,大型网站几乎都是分布式的。分布式系统的最大难点,就是各个节点的状态如何同步。CAP 定理是这方面的基本定理,也是理解分布式系统的起点。

一般来说,分区容错无法避免,因此可以认为 CAP 的 P 总是成立。CAP 定理告诉我们,剩下的 C 和 A 无法同时做到。

Consistency 和 Availability 的矛盾

一致性和可用性,为什么不可能同时成立?答案很简单,因为可能通信失败(即出现分区容错)。

如果保证 G2 的一致性,那么 G1 必须在写操作时,锁定 G2 的读操作和写操作。只有数据同步后,才能重新开放读写。锁定期间,G2 不能读写,没有可用性不。如果保证 G2 的可用性,那么势必不能锁定 G2,所以一致性不成立。

综上所述,G2 无法同时做到一致性和可用性。系统设计时只能选择一个目标。如果追求一致性,那么无法保证所有节点的可用性;如果追求所有节点的可用性,那就没法做到一致性。

使用场景

注重一致性:很多事务型的交易系统都要求具有一致性,如抢车票系统,同一时刻,所有用户看到的必须是最新的车票状态,不能是一部分用户看到有余票,另一部分用户看到无票。

注重可用性:CDN(内容发布网络)服务,网页的更新不是特别强调一致性,短期内,用户浏览到不同版本的网页,但是,最终所有人都能看到最新版本,也就是最终保持了一致性。

参考:

https://blog.csdn.net/mInfoDavid/article/details/115426018

https://cloud.tencent.com/developer/article/2108013

分布式系统的线性一致性

线性一致性的约束有三个,即:

  • 单个节点的事件历史在全局历史上符合程序的先后顺序
  • 全局事件历史在各个节点上一致
  • 如果事件A的开始时间晚于事件B的结束时间,则在全局历史中,B在A之前

其他一致性模型

除了线性一致性外,还有其他一致性模型,比如:

Eventual Consistency(最终一致性):

在最终一致性模型中,系统保证如果没有新的更新操作发生,那么最终所有节点都会收敛到相同的值。这意味着系统可能会在一段时间内出现不一致状态,但最终会达到一致状态。最终一致性通常用于分布式系统中为了提高性能而牺牲一致性的情况。

Causal Consistency(因果一致性):

因果一致性是相对于事件发生的因果关系来保证的一致性模型。如果事件 A 在事件 B 之前发生,那么任何观察到事件 B 的节点都必须也能够观察到事件 A。因此,因果一致性要求对于有因果关系的事件必须保持一致性,而对于无因果关系的事件则允许并发。

Fork Consistency(分支一致性):

分支一致性是一种介于最终一致性和因果一致性之间的模型。它允许系统中的分支出现,即允许有多个不同的历史状态。在分支一致性中,系统保证对于单个分支内部的一致性,并且最终所有分支都会收敛到一致状态。

Serializability(串行化一致性):

串行化一致性是指系统保证所有并发执行的操作按照某种顺序执行时,产生的结果与它们依次顺序执行时的结果相同。这意味着系统能够模拟所有操作按照某个全局顺序执行的效果,从而保证了强一致性。

Sequential Consistency(顺序一致性):

顺序一致性是一种强一致性模型,要求系统中的所有操作必须按照它们发生的顺序进行执行。即使是在分布式系统中,对于每个节点来说,所有操作的执行顺序也必须与它们在全局中发生的顺序相一致。

参考:

https://zhuanlan.zhihu.com/p/527498481

分布式一致性算法Raft

原理

Raft通过选举一个领导人,然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目(log entries),把日志条目复制到其他服务器上,并告诉其他的服务器什么时候可以安全地将日志条目应用到他们的状态机中。

通过领导人的方式,Raft将一致性问题分解成了三个相对独立的子问题:

  • 领导选举: 当现存的领导人发生故障的时候,一个新的领导人需要被选举出来;
  • 日志复制: 领导人必须从客户端接收日志条目(log entries)然后复制到集群中的其他节点,并强制要求其他节点的日志和自己保持一致。
  • 安全性: 主要是状态机安全,如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中,那么其他服务器节点不能再同一日志索引位置应用一个不同的指令。 BRAFT 通过 BRPC 框架实现了强一致性和数据安全性。在日志复制过程中,BRAFT 会确保每个日志条目被大多数节点写入并提交,从而避免了数据不一致的问题。同时,BRAFT 还提供了数据校验机制,确保数据的完整性和正确性。

节点的状态:

  • 领导人Leader: 接收客户端的请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。

  • 跟随者Follower: 接受并持久化Leader同步的日志,在leader说日志可以提交之后,提交日志。

  • 候选人Candidate: leader选举过程中的临时角色。

或者看看下面的理解:

  • 领导者:集群中霸道总裁,一切以我为准,处理写请求、管理日志复制和不断地发送心跳信息。
  • 跟随者:普通成员,处理领导者发来的消息,发现领导者心跳超时,推荐自己成为候选人。
  • 候选人:先给自己投一票,然后请求其他集群节点投票给自己,得票多者成为新的领导者。
  • 任期编号:每任领导者都有任期编号。当领导者心跳超时,跟随者会变成候选人,任期编号 +1,然后发起投票。任期编号小的服从编号大的。
  • 心跳超时:每个跟随者节点都设置了随机心跳超时时间,目的是避免跟随者们同时成为候选人,同时发起投票。
  • 选举超时:每轮选举的结束时间,随机选举超时时间可以避免多个候选人同时结束选举未果,然后同时发起下一轮选举

参考:

https://www.zhihu.com/tardis/bd/art/634693393

https://zhuanlan.zhihu.com/p/362679439

(完)