2023-12-03
阅读:(35)
评论(0)

职场定律｜CAP定理（布鲁尔定理）CPA Theorem (Brewer’s Theorem)

HR人事应知应会的定理 – 职场定律｜CAP定理（布鲁尔定理）CPA Theorem (Brewer’s Theorem)

定义

在理论计算机科学中，CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer’s theorem），它指出对于一个分布式计算系统来说，不可能同时满足以下三点

选项	具体意义
一致性（Consistency）	所有节点访问同一份最新的数据副本
可用性（Availability）	每次请求都能获取到非错的响应，但是不保证获取的数据为最新数据
分区容错性（Partition tolerance）	分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障

而CAP指的就是上述三个指标的首字母

分别解释每个指标

一致性（Consistency）

这里指的是强一致性，而最终一致性后续讨论
在写操作完成后开始的任何读操作都必须返回该值，或者后续写操作的结果
也就是说，在一致性系统中，一旦客户端将值写入任何一台服务器并获得响应，那么之后client从其他任何服务器读取的都是刚写入的数据

用如下系统进行解释

客户端向G1写入数据v1，并等待响应
此时，G1服务器的数据为v1，而G2服务器的数据为v0，两者不一致
接着，在返回响应给客户端之前，G2服务器会自动同步G1服务器的数据，使得G2服务器的数据也是v1
一致性保证了不管向哪台服务器（比如这边向G1）写入数据，其他的服务器（G2）能实时同步数据
G2已经同步了G1的数据，会告诉G1，我已经同步了
G1接收了所有同步服务器的已同步的报告，才将“写入成功”信息响应给client
client再发起请求，读取G2的数据
此时得到的响应是v1，即使client从未写入数据到G2

可用性（Availability）

系统中非故障节点收到的每个请求都必须有响应
在可用系统中，如果我们的客户端向服务器发送请求，并且服务器未崩溃，则服务器必须最终响应客户端，不允许服务器忽略客户的请求

分区容错性（Partition tolerance）

允许网络丢失从一个节点发送到另一个节点的任意多条消息，即不同步
也就是说，G1和G2发送给对方的任何消息都是可以放弃的，也就是说G1和G2可能因为各种意外情况，导致无法成功进行同步，分布式系统要能容忍这种情况。

CAP三者不可能同时满足

假设确实存在三者能同时满足的系统

那么我们要做的第一件事就是分区我们的系统，由于满足分区容错性，也就是说可能因为通信不佳等情况，G1和G2之间是没有同步

接下来，我们的客户端将v1写入G1，但G1和G2之间是不同步的，所以如下G1是v1数据，G2是v0数据。

由于要满足可用性，即一定要返回数据，所以G1必须在数据没有同步给G2的前提下返回数据给client，如下

接下去，client请求的是G2服务器，由于G2服务器的数据是v0，所以client得到的数据是v0

很明显，G1返回的是v1数据，G2返回的是v0数据，两者不一致。
其余情况也有类似推导，也就是说CAP三者不能同时出现。

CAP三者如何权衡

三选二利弊如何

CA (Consistency + Availability)：关注一致性和可用性，它需要非常严格的全体一致的协议，比如“两阶段提交”（2PC）。CA 系统不能容忍网络错误或节点错误，一旦出现这样的问题，整个系统就会拒绝写请求，因为它并不知道对面的那个结点是否挂掉了，还是只是网络问题。唯一安全的做法就是把自己变成只读的。
CP (consistency + partition tolerance)：关注一致性和分区容忍性。它关注的是系统里大多数人的一致性协议，比如：Paxos 算法 (Quorum 类的算法)。这样的系统只需要保证大多数结点数据一致，而少数的结点会在没有同步到最新版本的数据时变成不可用的状态。这样能够提供一部分的可用性。
AP (availability + partition tolerance)：这样的系统关心可用性和分区容忍性。因此，这样的系统不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本。Dynamo 就是这样的系统。

如何进行三选二

权衡三者的关键点取决于业务
放弃了一致性，满足分区容错，那么节点之间就有可能失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会容易导致全局数据不一致性。对于互联网应用来说（如新浪，网易），机器数量庞大，节点分散，网络故障再正常不过了，那么此时就是保障AP，放弃C的场景，而从实际中理解，像门户网站这种偶尔没有一致性是能接受的，但不能访问问题就非常大了。

对于银行来说，就是必须保证强一致性，也就是说C必须存在，那么就只用CA和CP两种情况，当保障强一致性和可用性（CA），那么一旦出现通信故障，系统将完全不可用。另一方面，如果保障了强一致性和分区容错（CP），那么就具备了部分可用性。实际究竟应该选择什么，是需要通过业务场景进行权衡的（并不是所有情况都是CP好于CA，只能查看信息但不能更新信息有时候还不如直接拒绝服务）

参考

CAP原则(CAP定理)、BASE理论
 分布式理论(一) – CAP定理
 CAP定理
 An Illustrated Proof of the CAP Theorem
分布式系统的一致性协议之 2PC 和 3PC

———————————————

The CAP Theorem (defined by Eric Brewer) states that for a distributed data store only two out of the following three guarantees (at most) can be made:

Consistency: when reading data, every request receives the most recent data or an error is returned
Availability: when reading data, every request receives a non error response, without the guarantee that it is the most recent data
Partition Tolerance: when an arbitrary number of network requests between nodes fail, the system continues to operate as expected

The core of the reasoning is as follows. It is impossible to guarantee that a network partition will not occur (see The Fallacies of Distributed Computing). Therefore in the case of a partition we can either cancel the operation (increasing consistency and decreasing availability) or proceed (increasing availability but decreasing consistency).

The name comes from the first letters of the guarantees (Consistency, Availability, Partition Tolerance). Note that it is very important to be aware that this does not relate to ACID, which has a different definition of consistency. More recently, PACELC theorem has been developed which adds constraints for latency and consistency when the network is not partitioned (i.e. when the system is operating as expected).

Most modern database platforms acknowledge this theorem implicitly by offering the user of the database the option to choose between whether they want a highly available operation (which might include a ‘dirty read’) or a highly consistent operation (for example a ‘quorum acknowledged write’).

Real world examples:

Inside Google Cloud Spanner and the CAP Theorem – Goes into the details of how Cloud Spanner works, which appears at first to seem like a platform which has all of the guarantees of CAP, but under the hood is essentially a CP system.

欢迎投稿职场/创业方向. 邮箱wangfzcom(AT)163.com：王夫子社区 » 职场定律｜CAP定理（布鲁尔定理）CPA Theorem (Brewer’s Theorem)

CAP定理

王夫子