谭浩的博客

Simple is beauty.

分布式系统 —— BASE、拜占庭问题以及CAP

不要让完美成了好的敌人

ACID 语义需要大量的努力和沟通。当我们的结果需要绝对正确时这是值得的,但是有一些情况,我们可以容忍一些陈旧和不一致。

例如一个在线商城的例子,如果需要购买一个或者两个商品,那么告诉你具体有450还是452个可售商品关系大吗?在这种情况下,稍有陈旧的值影响不大。但是当你需要结账的时候正确性就很重要,如果他们拿走了你的钱,那么你最好也要拿走的你的货。在这种情况下,大多数的查询允许有点陈旧,但是在最终时刻,我们需要正确的答案。

一个好的想法是我们可以在正确性和时间、精力以及可用性之间做权衡。对于不同的应用程序来说,不惜一切代价地采取完全正确和一致性可能是不必要的极端。

BASE(ACID的反面)

Good Enough

  • 基本可用(Basically Avaiable )意味者小的故障不会产生大的系统不可用。它和”soft failure vs hard failure”有相同的想法,但是强调在大规模系统中一些小的故障不应该真正被关注。
  • 软状态(Soft state )允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性。即允许系统在不同节点的数据副本之间进行的数据同步过程存在延时。
  • 最终一致性(Eventual consistency)传达的想法是, 尽管系统在更新后的一段时间内可能不一致, 但它最终会收敛到一致性。

BASE 理论通常和 ACID 形成对比。传统的ACID语义是非常悲观的会做许多工作,假设任何不一致都会被注意到, 并导致灾难。相反,BASE 是非常乐观的,假设不一致不太可能在被最终修复之前导致灾难。

两个经典的问题:在故障下达成一致并不容易

两军问题和拜占庭将军问题分别描述了通讯故障和处理器故障。它们帮助我们更多地了解我们能力的局限性, 在这些情况下, 管理处理器或通信故障。

两军问题

考虑战斗中的两支部队,红军和蓝军。蓝色军队正在一个山谷里露营。红军虽然规模更大、更强大, 但却被分为两组, 躲在周围的山上。

two armies

如果两支红军在同一时间攻击蓝军,那么他们将获胜。他们等待的时间越长, 对蓝军攻击的渴望就会越大。但如果他们等得太久, 就会耗尽物资, 变得虚弱, 挨饿。时机至关重要。但如果不协调好, 肯定会失败。他们必须同时进攻。

时机成熟时, R1 会派一个信使到 R2, 说:”黎明时分进攻”。但 R1 可能会担心 R2 没有得到信息, 因此不攻击。如果出现这种情况,R2 将被击败。或者, R2 可能会担心 R1 处在担心的状态, 所以他们可能不会攻击, 让 R1 在孤独中被击败。

如果 R2 同意消息,R2 将会返回一个 ACK 给发信者R1。但这仅仅是单边的连接。R2可能会担心ACK 消息没有传达从而不进攻。或者 R1 可能担心 R2 处于担心状态而选择不攻击。这个问题无法通过ACK-ACK 甚至 ACK-ACK-ACK…更多的ACK消息只是增加了更多层的单边连接,但是问题依然存在。

另一个可能的问题是假消息。如果蓝军派了一个冒名顶替者给 R2 传递一个信息, 告诉他们过早进攻呢?如果他们跟着假消息走, 就会被打败。但是, 如果他们不服从信息, 因为担心他们是骗子, 即使在通知 R2 之后,R1 将被击败时(他们确实攻击了) 。这种恐惧也可能促使军队对完全有效的信息不采取行动。

这个故事的寓意是如果通讯媒介不可靠的话,该问题将没有解决方案。请注意, 我说的是媒介, 而不是协议。这是一个重要的区别。不可靠的媒体上方的可靠协议可以保证最终消息被转达, 当然前提是收件人最终可以准备好并可访问。但任何协议都不能保证消息会在有限的时间内传递–错误条件可能会持续很长一段时间和不确定的时间。

拜占庭将军问题

土耳其苏丹率领一支军队入侵拜占庭帝国拜。皇帝有几支较小的军队来保卫帝国,这些军队的领导人需要仔细协调, 以便保卫这座城市不受土耳其人的攻击。为了采取适当的行动, 他们需要经常收到关于其他军队实力的最新情况。

他们意识到导致红军失败的通信问题, 所以他们用仔细的加密和纠错来交换信息。但他们遇到了一个新问题–叛徒。拜占庭人怀疑他们的一名将军是叛徒, 为了破坏他们的防守, 他们会对自己军队的实力撒谎。

为了解决这个问题并检测叛徒, 他们建立了一个交换消息的协议:

  1. 每个将军都应该使用可靠的信使将他的军队力量传递给每一个其他将军。
  2. 一旦每个将军都收集了这些信息, 他就应该把它发给其他将军。一旦发生这种情况, 每个将军都知道其他将军对每一支军队实力的看法。
  3. 然后, 每个将军都应该通过将每位将军关于该军队实力的报告视为军队规模的投票来确定每支军队的兵力。如果大多数将军都同意特定军队的规模, 那么这个规模就应该被相信。否则, 军队的规模应该被认为是未知的, 不知规模的军队的将军应该被怀疑有背信弃义的罪。

例子

步骤一:每一个将军将自己军队的力量传递给其他每一个将军。

步骤二:每一个将军给其他每一个将军发送一个消息,包含了他自己军队的力量以及其他将军报告的军队力量。每一个将军发送以下消息给其他每一个将军。将军2给每一个其他将军发送了不同的消息。

1
2
3
4
1: <1, x, 3, 4>
2: 每一个将军都不同
3: <1, y, 3, 4>
4: <1, z, 3, 4>

步骤三:每一个将军收集其他将军发过来的消息。每一向量代表一个将军自己军队力量以及其他将军的力量消息。

将军1 将军2 将军3 将军4
2:<a, b, c, d> 1:<1, x, 3, 4> 1:<1, x, 3, 4> 1:<1, x, 3, 4>
3:<1, z, 3, 4> 3:<1, z, 3, 4> 2:<e, f, g, h> 2:<i, j, k, l>
4:<1, y, 3, 4> 4:<1, y, 3, 4> 4:<1, y, 3, 4> 3:<1, y, 3, 4>

步骤四:每一个将军统计信息,决定军队的规模并确认叛徒。

将军1 将军2 将军3 将军4
2:<a, b, c, d> 1:<1, x, 3, 4> 1:<1, x, 3, 4> 1:<1, x, 3, 4>
3:<1, z, 3, 4> 3:<1, z, 3, 4> 2:<e, f, g, h> 2:<i, j, k, l>
4:<1, y, 3, 4> 4:<1, y, 3, 4> 4:<1, y, 3, 4> 3:<1, y, 3, 4>
<1, ?, 3, 4> <1, ?, 3, 4> <1, ?, 3, 4> <1, ?, 3, 4>

拜占庭可以容忍多少个叛徒

这是一个理论发现, 如果有 T 个卖国贼, 必须有 (2T + 1) 忠诚的将军们, 以确定忠诚的军队的规模, 并识别叛徒。

通常情况下, 我们会发现, 我们需要 (T+1) 忠诚的将军投票超过 T 卖国贼。但是, 仔细看一下, 这其实是不正确的。仔细观察向量, 对于每个不忠的将军, 我们都有两种不同类型的向量–由该将军提供的整个向量以及该将军在每一个其他向量中的条目。

因此, 我们需要对这 T 个破坏的的向量和其他向量中的 T 个破碎条目进行投票: (2T + 1)。

同上步骤,只有3个将军,其中有一个叛徒:

将军1 将军2 将军3
2:<a, b, c> 1:<1, x, 3> 1:<1, x, 3>
3:<1, z, 3> 3:<1, z, 3> 2:<e, f, g>

此时发现我们不能有一个清晰的大多数,甚至是忠诚将军的军队力量也无法确定。

这个方法总是可以工作吗?

如果背叛者向所有的将军撒同样的谎言,最终他们将在错误的值达成一致。因此, 基于这个故事, 不可发现的错误 (硬件故障, 而不是错误的通信) 被计算机科学家称为拜占庭错误。

需要怎么做

如果每个将军都被迫在他的信息上签字, 所有的信息都重复给所有的将军–包括签名, 这个问题是可以解决的(只需要存在一个忠诚的将军) 。在这种情况下, 就知道是哪个将军签署了不一致的信息—-解决一致的谎言仍然需要一个侦察任务。(此外, 还要求可以很容易地核实签名的真实性)。

检测失败的成本可能很高–有时是不可能的。这意味着分布式协议可能并不昂贵——也可能是不可能的。有时我们必须付出代价, 有时我们不需要。一个成功的分布式系统的设计和实现取决于了解我们能做什么、和应该做什么。

CAP定理

分布式系统通常需要建立一致性、可用性和分区容忍性。

  • 一致性(Consistency)所有参与系统共享同样的数据视图。例如,一个系统发现值为5,那么其他所有的系统也将如此。
  • 可用性(Availability)系统将能够足够快地响应用户的需要。例如:如果一个网页请求超时,或者用户在看见结果之前选择放弃都是不可用的。
  • 分区容忍性(Partition tolerance)在一些参与者失败或孤立的情况下, 其他参与者可以继续尽力而为。例如, 某些节点的丢失可能需要断开某些客户端的连接或无法返回某些结果,但是不应不必要地干扰正常运行的节点为客户端提供服务并返回结果的能力。

CAP定理指出分布式系统不可能同时保障这三条属性,只能满足其中的两条。

考虑一个拥有一个长队列的系统,我们可以添加更多的系统并将工作切分如下:

以上设计方式拥有了可用性,而且, 在分区的情况下, 可访问的节点仍然可以响应, 因此我们具有分区容差性。不过, 问题是我们已经失去了一致性。每个主机都是独立运行的, 因此, 如果更新不同, 值可能会出现差异。这是 “AP”或”PA” 案例。

为了增加一致性, 我们需要在主机之间进行通信, 以便它们可以同步值:

但是, 请注意发生了什么。我们通过沟通获得了一致性。如果我们中断了这种沟通, 我们就回到了起点。因此, 我们现在有了一致性和可用性, 但没有了分区容性。这是 “CA”/“AC” 案例。

那么对于”CP”/“PC”案例来说,我们如何在没有可用性的情况下具有一致性和分区容差, 至少以任何有意义的方式?一个很好的例子, 是我们允许读取操作, 但不允许更新。现在, 我们已经确定了写入的可用性, 以确保在分区的情况下保持一致性。