分布式系统之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)
- 一旦一个事务读数据,直至这个事务提交之前,这个数据一直不会改变
- 防止: fuzzy reads
- 串行化Serializable
- 防止: 幻影phantoms
- 给定预期P
- r1(P) ... w2(y in P)
- 一旦一个事务读取满足查询的元素集合,这个集合在事务提交前都不会改变。
- 不只是数据值,数据值参与的其他值也包括
- 防止: 幻影phantoms
- 游标稳定性Cursor Stability
- 事务有一个游标集合
- 一个游标指向被事务访问的一个对象
- 读锁一直保留到游标被移除或提交
- 在提交时间,游标被升级为写锁
- 能阻止lost-update
- 事务有一个游标集合
- 快照隔离Snapshot Isolation
- 事务总是能读取提交后的数据的一个快照,这些数据可以是在事务开始之前抓取准备好。
- 只有没有任何其他提交的事务被写入到任何我们想写的对象时,新的提交才能发生。
- 首次提交赢First-committer-wins
- 未提交读Read Uncommitted
平衡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