分布式系统之CAP

上篇

  CAP理论是指在Consistency一致性 Availability可用性和分区性之间只能三取二,因为分布式系统本身就是具有分区性特性,因此在分布式系统设计中,就只能在一致性和可用性中进行二选一了。

可用性是衡量操作的成功频率,一致性模型是统管什么操作会发生以及什么时候会发生,强一致性模型通常会有性能损失和可用性的牺牲。

可用性Availability

  • 可用性是衡量操作是否成功?无论是写操作或读操作。

整体可用性

  • 幼稚观点: 分布式系统中每个操作都会成功
  • 实际可能: 在无失败节点上的操作每个操作会成功
    • 如果节点失败,你什么也做不了。

高粘度可用性Sticky availability

  • 非失败节点的每个操作会成功
    • 需要客户端前后一直和同样的节点服务器通讯,也就是粘住这台服务器,比如通过Session粘住。

高可用性

  • 如果系统不是分布式的情况比较好。比如关系数据库
  • 容忍失败,但不会太多
  • 也许一些操作会失败

大多数可用

  • 如果在一个集群中,一个节点和集群中大多数节点能正常通讯,那么这个节点上的操作会成功。
  • 少数节点操作会失败

量化可用性Quantifying availability

  • 我们谈论的是"uptime"
    • 如果没有人使用系统,系统是否还在运行?
    • 在繁忙时间系统是否更糟糕以至于当机?
    • 能否测量某个时间窗口中请求数目?
    • 在不同时间点的窗口上这些请求的情况?
    • 时间刻度会影响输出报告的uptime
  • Apdex
    • 不是所有成功都是平等的
    • 将操作分类为"OK", "无聊meh", 和 "可怕"
    • Apdex = P(OK) + P(无聊)/2
    • 年报表可以这么写
      • "今年完成了99.999 apdex "

一致性Consistency

  • 一致性模型是系统中事件的历史集合

单调读Monotonic Reads

  • 任何读操作都将返回当时状态或读操作发生后的那个值。

单调写Monotonic Writes

  • 任何写操作都能接着上一个写操作成功后再次操作成功。

读写Read Your Writes

  • 任何读操作读能读取到写操作的结果

写跟着读Writes Follow Reads

  • 一旦我读某个操作,其后的写操作会在我读以后发生。

串行化Serializability

  • 所有操作 (事务) 看上去以原子方式执行,好像一个操作一样
  • 有一些顺序
    • 对于顺序是什么没有约束
    • 完全立即可以读取过去的值。

因果一致性Causal consistency

  • 操作是被代表因果关系DAG联接。
    • 一个写操作跟着一个读操作,表示这是有因果关系的。
      • 假设处理节点不会向外抛出读操作的数据
    • 没有被DAG相联接的操作就是并发同时发生
  • 约束: 在一个处理节点服务器能执行一个操作之前,这个操作的所有前面操作都必须在这个节点已经执行完毕。
  • 并发操作能被自由重排序。

顺序一致性Sequential consistency

  • 类似因果一致性, 对可能的顺序有约束
  • 所有操作好像以单个原子操作执行
  • 每个处理服务器都同意操作的次序
    • 来自给定处理节点服务器的操作总是顺序的发生。
    • 但是节点可以延后滞后

线性化Linearizability

  • 所有操作好像以单个原子操作执行
  • 每个处理服务器都同意操作的次序
  • 每个操作好像发生在其被调用和完成之间之内
  • 实时,让我们能够建立一个强一致性系统

ACID隔离级别

  • ANSI SQL的 ACID隔离级别是让人会感到奇怪
    • 基本是集成了现有关系数据库厂商的实现效果
    • 规定定义是含糊不清的
  • Adya 1999: 弱一致性Weak Consistency: 分布式事务的一个泛化和优化的实现
    • 未提交读Read Uncommitted
      • 需要防止脏读
        • w1(x) ... w2(x)
        • 在另外一个事务提交之前是不能覆盖其再进行写操作的。
      • 当另外一个事务还在修改时能够读数据
      • 也能读取被事务回滚以后的数据
    • 提交读Read Committed
      • 防止脏读
        • w1(x) ... r2(x)
        • 不能读一个事务还没有提交的数据,不管这个事务在修改或其他写操作
    • 可重复读Repeatable Read
      • 防止: fuzzy reads
        • r1(x) ... w2(x)
        • 一旦一个事务读数据,直至这个事务提交之前,这个数据一直不会改变
    • 串行化Serializable
      • 防止: 幻影phantoms
        • 给定预期P
        • r1(P) ... w2(y in P)
        • 一旦一个事务读取满足查询的元素集合,这个集合在事务提交前都不会改变。
        • 不只是数据值,数据值参与的其他值也包括
    • 游标稳定性Cursor Stability
      • 事务有一个游标集合
        • 一个游标指向被事务访问的一个对象
      • 读锁一直保留到游标被移除或提交
        • 在提交时间,游标被升级为写锁
      • 能阻止lost-update
    • 快照隔离Snapshot Isolation
      • 事务总是能读取提交后的数据的一个快照,这些数据可以是在事务开始之前抓取准备好。
      • 只有没有任何其他提交的事务被写入到任何我们想写的对象时,新的提交才能发生。
        • 首次提交赢First-committer-wins

平衡Tradeoffs

  • 理性情况我们需要整体可用性和线性化
  • 一致性需要协调
    • 如果每个次序被运行,我们就不必做任何工作
    • 如果我们要不允许一些事件次序,我们得交换消息
  • 协调会带来成本
    • 更多一致性要求会导致性能慢
    • 更多一致性其实是更多直觉
    • 更多一致性会导致较低的可用性

可用性和一致性

  • CAP 理论: 线性Linearizability 或整体可用性两者选一
  • 但是还有更多细节
    • Bailis 2014: 高可用性事务: 美德与限制(Virtues and Limitations)
    • 下面理论是不允许整体可用性或高粘度的可用性.
      • 强串行性Strong serializable
      • 串行性Serializable
      • 可重复读Repeatable Read
      • 游标稳定性Cursor Stability
      • 快照隔离Snapshot Isolation
    • 下面可以有高粘度可用性
      • 因果Causal
      • PRAM
      • 读你自己的写
    • 下面能有整体可用性
      • 未提交读Read Uncommitted
      • 提交的读Read Committed
      • 单调原子视图Monotonic Atomic View
      • 写跟着读Writes Follow Reads
      • 单调读Monotonic Reads
      • 单调写Monotonic Writes

Harvest 和 Yield

  • 来自Fox & Brewer, 1999: Harvest, Yield, Scalable Tolerant Systems
    • Yield: 完成一个请求的可能性
    • Harvest: 代表响应中少量数据
    • 举例
      • 搜索引擎一个节点失败会导致一些结果丢失
      • 更新也许只反映在一些节点上,而其他节点没有更新。
        • 在分区partition情况下考虑AP
        • 你能写一些其他人不能读的数据
      • 流式视频会降级比如分辨率以保护更低的延时,也就是降低分辨率提高性能
    • 这不能成为违背你的业务安全一致性的借口
      • 只是帮助你量化你能超出偏离安全一致性多少限度。
      • 比如. "在时间的99% 中,, 你能读取先前写操作的90%"
    • 非常依赖于工作负载, HW, topology, 等
    • 对于每个请求能够在harvest与 yield之间微调
    • "尽可能在10毫秒以内"
    • "我需要每件事情,并且我理解你也许可能无法答应"

 

下篇

CAP原理和BASE思想

如何打败CAP定理?

ACID和CAP的详尽比较

ACID中C与CAP定理中C的区别

事件溯源

线性化与串行化比较

Twitter的分布式日志DistributedLog