分布式系统大纲

为什么需要分布式?
1. 首先，在托管中心运行*nix 的盒子，进程通过 TCP 或者 UDP 通信。
  1. 或者 EC2, Rackspace 的盒子等等
  2. 也许通过 InfiniBand 通信
  3. 以短距离的局域网分割
  4. 或者以数千公里互联网分割
2. 许多移动应用也参与分布式系统
  1. 通过糟糕的网络进行通信
    1. 桌面 Web 浏览器也是如此
    2. 这不仅仅是服务器 —— 它也是客户端
3. 更一般地说，分布式系统具有如下特征
  1. 由交互的组件构成
  2. 很慢
  3. 不可靠
  4. 无论那些对你意味着什么
4. 还有：
  1. 飞机上的冗余 CPU
  2. ATM 和销售点终端
  3. 太空探测器
  4. 支付账单
  5. 医生进行推荐
  6. 醉酒的朋友试图通过短信制定计划
  7. 每次商务会议
节点和网络
1. 我们将分布式系统中的每个部分叫做节点
  1. 也称之为进程，代理，参与者
2. 节点
  1. 延迟特征
    1. 在一个节点内部的操作很快
    2. 节点之间的操作很慢
    3. 快和慢取决于系统的目的
  2. 节点是可靠的
    1. 作为一个故障单元
    2. 你知道什么时候发生问题
    3. 状态是连贯的
    4. 状态转换以优雅有序的方式进行
    5. 典型的模型是某种类型的单线程状态机
  3. 节点可以自己组成一个分布式系统
    1. 但只要该系统作为一个整体提供“快速，连贯”的操作，我们就可以将其视为单个节点。
  4. 进程模型
    1. 顺序进程通信模型
    2. Pi-演算
    3. Ambient 演算
    4. Actor 模型
  5. 节点故障模型
    1. 故障停止 Crash-stop
    2. 故障恢复 Crash-recover
    3. 故障遗忘 Crash-amnesia
    4. 拜占庭 Byzantine
3. 消息流通的网络
  1. 节点通过网络交互
    1. 人类通过口头语言进行交互
    2. 粒子通过磁场交互
    3. 计算机通过 IP，TCP，UDP，SCTP 或者其它协议交互
  2. 在节点之间发送的离散消息
  3. 消息需要时间来传播
    1. 这是分布式系统中比较慢的部分
    2. 我们称之为延迟
  4. 消息可能会丢失
    1. 这是分布式系统中另一个不可靠的部分。
  5. 网络几乎不会是同构的
    1. 一些连接比其它的连接速度更慢、带宽更小、更容易出错
4. 因果关系图
  1. 我们可以将节点和网络交互表示为图表
    1. 时间从左到右或者从上到下表示
    2. 节点是时间方向上的线（因为它们保持不动）
    3. 消息通过倾斜的路径连接节点
5. 同步网络
  1. 节点以锁步方式执行：节点步骤之间的时间始终为 1
  2. 消息延迟有限
  3. 有效的完美的全球时钟
  4. 易于证明的
    1. 你可能没有
6. 半同步网络
  1. 像同步一样，但时钟只是近似的，例如在 [c，1]
7. 异步网络
  1. 独立执行，无论何时：步进时间在[0,1]中的任何位置
  2. 无限制的消息延迟
  3. 没有全球时钟
  4. 比半同步或同步网络弱
    1. 意味着某些算法效率不高
    2. 意味着某些算法是不可能的
    3. 参见例如 Attiya＆Mavronicolas，“半同步与异步网络的效率“
  5. IP 网络肯定是异步的
    1. 但在实践中真正的病态事情不会发生
    2. 大多数网络在几秒到几周内恢复，而不是“从不”
      1. 相反，人类的时间尺度大约为几秒到几周
      2. 所以我们不能臆想不存在的问题
8. 当网络出错时
  1. 异步网络允许
    1. 重复
    2. 延迟
    3. 丢失
    4. 重排
  2. 丢失和延迟是很难区分的
  3. 拜占庭网络被允许随意乱序
    1. 包括重写内容
    2. 在真实的网络中几乎不会出现
      1. 大多数情况
      2. https://www.pagerduty.com/blog/the-discovery-of-apache-zookeepers-poison-packet/
      3. https://tech.vijayp.ca/linux-kernel-bug-delivers-corrupt-tcp-ip-data-to-mesos-kubernetes-docker-containers-4986f88f7a19
9. 底层协议
  1. TCP
    1. TCP 有效。用它。
      1. 不完美；你可以更快
      2. 但你会知道什么时候是这种情况
    2. 实际上，TCP 可以在单个 TCP 连接中防止重复和重新排序
      1. 但是你可能会打开多个连接
      2. 如果没有其他原因，TCP 连接最终会失败
      3. 当发生这种情况时，你可以 a）错过消息；b）重试
      4. 您可以在 TCP 连接之上构建序列号来保证有序
  2. UDP
    1. 与 TCP 相同的规则，但没有流的不变性
    2. 很多人都希望 UDP “速度”
      1. 不要认为路由器和节点可以并且会随意丢弃数据包
      2. 不要认为他们的包会被重复
      3. 并重新排序
      4. “但至少它是公正的吗？”
      5. 这会导致各种各样的混乱，例如，指标收集
      6. 调试很难
      7. TCP 为您提供流量控制并将逻辑消息重新打包成数据包
      8. 通过基于 UDP 的 TLS 很难
    3. 在 TCP 有限状态机开销过高的情况下，UDP 非常有用
      1. 内存压力
      2. 复用大量短连接和套接字
    4. 在系统目标是尽力传输的场景下尤其有用
      1. 语音通话：人们会道歉并重复自己
      2. 游戏：口吃和滞后，但后来会追上
      3. 更高级别的协议对底层的混乱增加了可靠性
  3. 当一个系统被分割为独立的部分时，我们还期望对事件有某种类型的顺序
  4. 时钟可以帮助我们排序：先是这个，然后是那个
时钟
1. 墙上时钟
  1. 理论上，操作系统的时钟为你提供了系统事件的部分顺序。
    1. 注意事项：NTP 可能没有你想象的那么好
    2. 注意事项：节点之间的同步性并不好
    3. 注意事项：硬件可以漂移
      1. 多份关于超微公司 TSC 导致系统时钟运行速度达到 26ms/s 的报告
      2. https://groups.google.com/forum/#!search/Supermicro$20SYS-1029UX-LL1-S16$20system$20clock$20running$20too$20fast/mechanical-sympathy/oG9vLZVYjVA/DU-T9QpBAgAJ
    4. 注意事项：跨越几个世纪
      1. NTP 不被关注
      2. http://rachelbythebay.com/w/2017/09/27/2153/
    5. 注意事项：NTP 依然可能将时钟向后跳动（默认：delta > 128 ms）。
      1. https://www.eecis.udel.edu/~mills/ntp/html/clock.html
    6. 注意事项：根据定义，POSIX 时间不是单调的
      1. Cloudflare 2017 年。午夜 UTC 的闰秒意味着时间向后流动
      2. 当前 Go 并没有提供对 CLOCK_MONOTONIC 的访问。
      3. 计算出一个负的持续时间，然后将其送入 rand.int63n()，后者惊慌失措。
      4. 导致 DNS 解析失败。1%的 HTTP 请求受到影响，持续数小时
      5. https://blog.cloudflare.com/how-and-why-the-leap-second-affected-cloudflare-dns/
    7. 注意事项：你想测量的时间尺度可能无法实现
    8. 注意事项：线程会休眠
    9. 注意事项：运行时会休眠
    10. 注意事项：操作系统会休眠
    11. 注意事项："硬件"会休眠
    12. 注意事项：管理程序可以对你撒谎
      1. 在 15 分钟内有 16 秒以上的时间延迟！？
      2. https://gist.github.com/sandfox/32e749b5eac861c93f1bbeb8782ae8fd
    13. 不要使用
    14. 至少操作系统的单调时钟是单调的，对吗？
    15. 哦不: https://github.com/rust-lang/rust/blob/eed12bcd0cb281979c4c9ed956b9e41fda2bfaeb/src/libstd/time.rs#L201-L232
2. Lamport 时钟
  1. Lamport 1977：“时间，时钟和分布式系统中事件的排序”
    1. 每个进程一个时钟
    2. 每个状态转换，时间单调递增： t'= t + 1
    3. 包含在发送的每条消息中
    4. t'= max(t，t_msg + 1)
  2. 如果我们有进程的全序，则我们可以对事件实现全序
3. 向量时钟
  1. 将 Lamport 时钟推广到所有进程时钟的向量
  2. t_i'= max(t_i, t_msg_i)
  3. 对于每个操作，在向量中增加该进程的时钟
  4. 提供部分因果顺序
    1. A < B 当且仅当所有 A_i <= B_i，并且至少一个 A_i < B_i
    2. 具体而言，给定一对事件，我们可以确定因果关系
      1. B 的因是 A，则意味着 A < B
      2. A 的因是 B，则意味着 B < A
      3. 否则独立
  5. 务实地：过去是共享的; 现在是独立的
    1. 只有“现在”，需要保留独立状态
    2. 祖先状态可以被丢弃
    3. 让我们对过去做垃圾收集
  6. 空间：O（进程数）
    1. 对于 GC 需要协调
    2. 或者牺牲正确性并修剪旧的 vclock 条目
  7. 变种
    1. 虚线版本矢量 - 用于客户端/服务器系统，对更多的事件排序
    2. 区间树时钟 - 用于进程进入和离开
4. GPS 和原子钟
  1. 比 NTP 好
    1. 毫秒精度的全球分布的全序
    2. 将异步网络提升为半同步网络
    3. 解锁更高效的算法
  2. 当前只有 Google 有这个能力
    1. Spanner：全球分布的强一致事务
    2. 并且他们不共享
  3. 比你想要的要贵
    1. 每个 GPS 几百个接受者
    2. 原子钟用于本地的正确性：很多钱
    3. 需要多个类型的 GPS：供应商可能会出错
      1. https://rachelbythebay.com/w/2015/09/07/noleap/
      2. 混乱的供应商确认框，它将 UTC 校正应用于 GPS 时间
    4. 我不知道是谁在做这件事，但我敢打赌数据中心未来将为有限精度时间提供专用的硬件接口
5. 回顾
  1. 我们已经介绍了分布式系统的基本原理。节点通过网络交换消息，节点和网络都可能以各种方式失败。TCP 和 UDP 等协议为我们提供了原始信道通信流程，我们可以使用时钟排序时间。现在，我们会讨论分布式系统的一些高级属性。
  2. 可用性基本上是尝试成功操作的一部分
可用性
1. 完全可用
  1. 原始想法：每次操作都成功
  2. 一致性：非故障节点上的每个操作都成功
    1. 您无法对故障节点做任何事情
2. 粘性可用
  1. 对于非故障节点每次操作都成功
    1. 约束：客户端总是可以和相同的节点交互
3. 高可用
  1. 最好，如果系统没有被分布。
  2. 例如容忍多达 f 次失败，但不能再多
  3. 也许有些操作失败了
4. 多数可用
  1. 如果操作的节点可以跟集群中的多数通信，则操作可以成功
  2. 操作少数节点会失败
5. 量化可用性
  1. 我们谈论了很多运行时间
    1. 如果没有人用，系统是运行的吗？
    2. 在高峰时期会比宕机更差吗？
    3. 可以 “在时间窗口内满足的请求的比例” 做衡量
    4. 然后在不同时间在窗口上绘制该比例
    5. 时间刻度会影响报告的正常运行时间
  2. Apdex
    1. 不是所有的成功都是等价的
    2. 将操作分为“好，“乏味”和“糟糕”
    3. Apdex = P(OK) + P(meh) / 2
    4. 再次，可以每年报告
      1. 我们实现了 99.999 apdex 在这一年
    5. 并且在更精细的时间尺度上！
      1. “用户服务的 Apdex 刚下降到 0.5;页面操作！”
    6. 理想情况：您的服务提供的整体很好？
  3. 一致性模型是系统中事件的“安全”历史集
一致性
1. 单调读
  1. 一旦我读取了一个值，任何后续读取都将返回该状态或以后的值
2. 单调写
  1. 如果进行写操作，所做的任何后续写操作都将在第一次写入后的值上写入
3. 读自己
  1. 一旦一个值写入后，任何后续的读取都会返回写入的值（或者后续的值）
4. 写后读
  1. 一旦一个值被读取，后续的写入只会在读取后的位置进行
5. 串行化
  1. 所有的操作（事务）都是原子执行的
  2. 以某种顺序
    1. 对顺序没有限制
    2. 例如可以从过去的历史读取也没有问题
6. 因果一致性
  1. 假设操作可以由 DAG 因果关系连接
    1. 例如，读取之后的写入与因果关系有关
      1. 假设进程不只是丢弃读取数据
    2. 该 DAG 中未连接的操作是并发的
  2. 约束：在进程可以执行操作之前，所有之前的操作已经在该节点上执行
  3. 并发操作可以自由重新排序
7. 顺序一致性
  1. 跟因果一致性类似，限制了可能的顺序
  2. 所有操作必须原子执行
  3. 所有进程对操作的顺序达成一致
    1. 对于一个进程而言，操作总是按顺序出现
    2. 但是节点可以落后
8. 线性化
  1. 所有操作必须原子执行
  2. 每个进程对操作顺序达成一致
  3. 每个操作必须在调用和完成时间之间进行
  4. 实时性，玩不的约束可以让我们构建强壮的系统
9. ACID 隔离级别
  1. ANSI SQL 的 ACID 隔离级别是很奇怪的
    1. 基本上是已有厂商实现的效果
    2. 规范中的定义含糊不清
  2. Adya 1999：Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions
    1. 每个 ANSI SQL 隔离级别都禁止出现奇怪的现象
    2. 读未提交
      1. 防止 P0：脏写
      2. w1(x) ... w2(x)
      3. 在提交之前，无法覆盖其他事务的数据
      4. 在事务仍在修改时可以读取数据
      5. 可以读取即将回滚的数据
    3. 读已提交
      1. 防止 P1：脏读
      2. w1(x) ... r2(x)
      3. 不能读取一个事务未提交的值
    4. 可重复读
      1. 防止 P1：模糊读 (update)
      2. r1(x) ... w2(x)
      3. 一旦一个事务读取到一个值，事务在提交之前都不能变
    5. 串行化
      1. 防止 P3：幻读 (select id < 2 from t; insert into t values(1);)
      2. 给出一些条件 P
      3. r1(x) ... w2(y in P)
      4. 一旦读取了满足查询条件的集合，这个集合不能变化，直到事务提交
      5. 不仅仅是值，是那些会参与到集合中的值
    6. 游标稳定
      1. 事务有一个游标的集合
      2. 一个游标引用一个事务访问的对象
      3. 持有读锁，直到游标被释放或者提交
      4. 在提交的时，游标被升级为写锁
      5. 防止丢失更新
    7. 快照隔离
      1. 事务总是从已经提交的快照读取数据，快照从事务开始时获取
      2. 仅当没有其他具有重叠[start..commit]间隔的已提交事务已写入我们编写的任何对象时，才会发生提交
      3. 第一个提交者成功
10. 这实际上有什么关系吗？
  1. 真实世界并不是那样并发的
  2. 很多公司选择读已提交
  3. 但恶意攻击者可以诱导并发
    1. Flexcoin
      1. 比特币交换，允许用户通过在账户之间进行混洗来创造资金
      2. 2014 年遭遇袭击，365,000 英镑被盗
      3. 交易所完全崩溃了
    2. Poloniex
      1. 并发提款被错误地隔离，允许用户超支
      2. 安全审核未发现负余额
      3. 12.3％的外汇资金被盗; 损失在用户之间传播
    3. Warszawski＆Bailis 2017：ACIDrain
      1. 自动识别 Web 应用程序中的一致性违规
      2. 例如购买一张礼品卡，然后无限次使用
      3. 例如购买笔，在结账时添加笔记本电脑到购物车，获得免费的笔记本电脑
      4. 超过 50％的电子商务网站中都存在漏洞
      5. 弱 DB 隔离默认值
      6. 事务范围的不当使用
      7. 未能使用任何事务
      8. Chase Bank's credit card rewards system
      9. 余额之间的并发转账获得了价值 70000 美金的旅行券
      10. 现金可以赎回
  4. 理想情况下，我们需要完全可用性和线性化
  5. 一致性需要协调
    1. 如果允许每个顺序，我们不需要做任何工作！
    2. 如果我们想要禁止某些事件顺序，我们必须交换消息
  6. 协调（通常）都有代价
    1. 更多的一致性更慢
    2. 更多的一致性更直观
    3. 更多的一致性更少的可用性
权衡
1. 可用性和一致性
  1. CAP 理论：线性化或者完全可用
  2. 但是等等，这里还有更多！
  3. Bailis 2014：Highly Available Transactions: Virtues and Limitations
  4. 其他理论不允许完全可用或粘性可用......
    1. 强串行化
    2. 串行化
    3. 可重复读
    4. 游标稳定
    5. 快照隔离
  5. 你可以粘性可用...
    1. 因果关系
    2. PRAM
    3. 读你的写
  6. 你可以完全可用...
    1. 读未提交
    2. 读已提交
    3. 单调原子视图
    4. 写后读
    5. 单调读
    6. 单调写
2. 收获与收益
  1. Fox & Brewer, 1999: Harvest, Yield, and Scalable Tolerant Systems
  2. 收益：请求完成的概率
  3. 收获：响应中反映的数据部分
  4. 例子
    1. 搜索引擎中的节点故障可能导致某些结果丢失
    2. 更新可能反映在某些节点上，但不反映在其他节点上
      1. 考虑一个被分区的 AP 系统
      2. 你可以写入数据一些人不能读取到
    3. 流式视频降级以保持低延迟
  5. 这不是违反安全不变量的借口
    1. 只是帮助您量化您可以超过安全不变量的数量
    2. 例如，99%时间，你可以读取到前面 90%的写入
  6. 强依赖负载，硬件，拓扑，等
  7. 可以根据每个请求调整收获与收益
  8. 尽可能在 10ms 以内
  9. 我需要一切，我理解你可能不会应答
3. 混合系统
  1. 有一系列的选择
    1. 不同部分设施有不同的需求
    2. 选择可以满足你的约束最弱的模型
      1. 但是考虑概率界限，可见性延迟可能会令人望而却步
      2. 请参阅 Dynamo Quorums 中的概率有界陈旧性
  2. 不是所有的数据都是一样的
    1. 大数据通常不是很重要
    2. 小数据通常很重要
    3. 线性化用户的操作，因果关一致性社交信息
4. 回顾
  1. 可用性衡量运营成功的频率。一致性模型是管理可能发生的操作以及何时发生的规则。更强的一致性模型通常以性能和可用性为代价。接下来，我们将讨论构建系统的不同方法，从弱到强一致性。
尽可能避免共识
1. CALM 猜想
  1. Consistency As Logical Monotonicity
    1. 如果你可以证明一个系统是逻辑单调的，则不需要协调
    2. 什么是“协调”？
    3. 什么是“单调”？
  2. 单调性，非正式的，是不会回退的
    1. 从部分信息推论永远不会因为新信息而无效
    2. 没有否定的关系代数和 Datalog 是单调的
  3. Ameloot, et al, 2011: Relational transducers for declarative networking
    1. 理论上，不知道网络范围的无协调网络进程只能计算 Datalog 中的单调查询
      1. 这读起来不容易
    2. 无协调并不意味着没有通信
      1. 即使面对任意水平分区，算法也能成功
  4. 用非常宽松的实际术语
    1. 尝试说明您的问题，以便您只向系统添加新的事实
    2. 当您根据当前已知的事物计算新事实时，您是否可以确保永远不会撤回事实？
    3. 考虑特殊的“密封事实”，将一系列事实标记为完整
    4. 这些“仅增长”算法通常更容易实现
    5. 可能的权衡：不完整的读取
  5. Bloom 语言
    1. 带流分析的无序编程
    2. 可以告诉你哪里要协调
2. Gossip
  1. 消息广播系统
  2. 对于集群管理、服务发现、健康、传感器、CDN 等很有用
  3. 通用的若一致性/高可用
  4. 全球广播
    1. 发送消息给每个其它节点
    2. O(节点数)
  5. 网状网络
    1. 流行病模型
    2. 与邻居接力
    3. 传播时间按最大自由路径的顺序排列
  6. 生成森林
    1. 替代网络，使用树
    2. 跳到连接节点，该节点继续连接到其他连接节点
    3. 减少多余的消息
    4. 减少时延
    5. Plumtree (Leit ̃ao, Pereira, & Rodrigues, 2007: Epidemic Broadcast Trees)
  7. Push-Sum 等
    1. 对您收到数据的每个人的输入求和
    2. 将其广播到随机的同等节点
    3. 最小值，最大值，平均值的扩展
    4. 有助于实时指标，速率限制，路由，识别群集热点
3. CRDTs
  1. 无序的数据类型
    1. 计数器，集合，映射等等
  2. 容忍欺骗，延迟和重新排序
  3. 与顺序一致的系统不同，没有“单一的事实来源”
  4. 但不像天真的最终一致的系统，永远不会丢失信息
    1. 除非你明确让他们丢失信息
    2. 我们称这个属性为“合并”
  5. 在高可用系统中工作的很好
    1. 网页/移动客户端
    2. Dynamo
    3. Gossip
  6. INRIA: Shapiro, Preguiça, Baquero, Zawirski, 2011: "A comprehensive study of Convergent and Commutative Replicated Data Types"
    1. 由数据类型 X 和合并函数 m 组成，是：
      1. 关联：m(x1, m(x2, x3)) = m(m(x1, x2), x3)
      2. 交换：m(x1, x2) = m(x2, x1)
      3. 幂等：m(x1, x1) = m(x1)
  7. 容易构建。容易推理。摆脱各种头痛的问题。
    1. 沟通失败了吗？重试！它会收敛！
    2. 消息是否无序到达？没关系！
    3. 如何同步两个副本？合并！
  8. 缺点
    1. 有些算法需要顺序，不能用 CRDT 表示
    2. 读取可能是任意旧值
    3. 更高的空间成本
4. HATs
  1. Bailis, Davidson, Fekete, et al, 2013: "Highly Available Transactions, Virtues and Limitations"
    1. 从任何副本确保响应
    2. 低延迟（比可序列化协议快 1-3 个数量级！）
    3. 读已提交
    4. 单调原子视图
    5. 非常适用于可交换/单调系统
    6. 多个项更新的外键约束
    7. 有限的唯一性约束
    8. 可以确保给定任意有限延迟的收敛（“最终一致性”）
    9. 地理分布系统的良好候选
    10. 可能最好与更强大的事务系统协调一致
    11. 另见：COPS，Swift，Eiger，Calvin 等
  2. 共识问题
    1. 三种进程类型
      1. 提议者：提出一个值
      2. 接受者：选择一个值
      3. 学习者：读取选择的值
    2. 接受者的分类
      1. N 个接受者
      2. F 个允许失败
      3. M 个恶意的接受者
    3. 三个变体
      1. 非平凡性：只能学习提出的值
      2. 安全性：最多可以学习一个值
      3. 活跃性：如果一个提议者 p，一个学习者 l 和一组 N-F 各接受者没有错误并且可以相互通信，并且如果 p 提出一个值，则 l 最终将学习一个值。
  3. 系统类型与共识问题等价
    1. 所以我们这里的任何证明也适用于那些系统
    2. 锁服务
    3. 排序的日志
    4. 复制状态机
  4. FLP 告诉我们不可能在异步网络中实现共识
    1. 在正确的时间杀死一个进程，你可以打破任何共识算法
    2. 是这样，但情况也不是你想的那样坏
    3. 实际上，网络通常足以达成共识
    4. 此外，FLP 假设确定的进程
      1. 实际的计算机系统不是确定的
      2. Ben-Or 1983: "Another Advantage of free choice"
      3. 非确定性算法可以达成共识
  5. Lamport 2002: tight bounds for asynchronous consensus
    1. 至少有两个提议者或一个恶意提议者，N > 2F + M
      1. 需要大多数
    2. 对于至少 2 个提议者或一个恶意提议者，学习提案至少需要 2 个消息延迟。
  6. 这是一个实用的可操作范围
    1. 在稳定的集群中，可以使用一次往返大多数节点的方式。
    2. 群集转换期间需要更多。
共识
1. Paxos
  1. Paxos 是共识算法的黄金标准
    1. Lamport 1989 - The Part Time Parliament
      1. 对想象中的希腊民主的描述方式来写作
    2. Lamport 2001 - Paxos Made Simple
      1. “用于实现容错分布式系统的 Paxos 算法一直被认为难以理解，也许是因为原始表示对于许多读者来说是希腊语[5]。事实上，它是最简单和最明显的分布式算法之一。最后一节解释了完整的 Paxos 算法，它是通过直接应用协议来建立分布式系统的状态机方法得到的 - 这种方法应该是众所周知的，因为它是最可能的主题。经常被引用的关于分布式系统理论的文章[4]。“
    3. Google 2007 - Paxos Made Live
      1. 来自谷歌锁服务 Chubby 的笔记
    4. Van Renesse 2011 - Paxos Made Moderately Complex
      1. 事实证明你必须优化
      2. 伪代码也会有所帮助
      3. 一个伪代码页 -> 几千行 C ++
  2. 就独立提案达成共识
  3. 通常部署在多数仲裁中，5 或 7 个节点
  4. 几个优化
    1. Multi-Paxos
    2. Fast Paxos
    3. Generalized Paxos
    4. 并不总是清楚使用哪种优化，哪些可以安全地组合
    5. 每种实现都使用略有不同的风格
    6. Paxos 实际上更像是一系列算法，而不是一个描述良好的单一实体
  5. 用于各种生产系统
    1. Chubby
    2. Cassandra
    3. Riak
    4. FoundationDB
    5. WANdisco SVN servers
  6. 新研究：Paxos 法定人数不需要占多数：可以优化快速阶段 2 法定人数 Howard, Malkhi, and Spiegelman
    1. 我们还不确定如何使用它
    2. 持久性仍然需要分发
2. ZAB
  1. ZAB 是 Zookeeper 原子广播协议
  2. Junqueira, Reed, and Serafini 2011 - Zab: High-performance broadcast for primary-backup systems
  3. 与 Paxos 有区别
  4. 提供顺序一致性（可线性化写入，滞后有序读取）
    1. 很有用，因为 ZK 客户端通常需要快速本地读取
    2. 但是还有一个 SYNC 命令可以保证实时可见性
    3. （SYNC + op）允许线性化读取
  5. 仍然是多数派，5 个或者 7 个节点
3. Humming 共识
  1. 用于管理分布式系统重新配置的元数据存储
  2. 看起来有点像 CORFU 的复制日志
  3. 另见：链式复制
4. Viewstamped 复制
  1. 作为复制协议提供，但也是共识算法
  2. 事务处理加视图变更算法
  3. 保证多数达成的值可以将来继续生存
  4. 我不知道任何生产系统，但我确定它们在那里
  5. 与 Paxos 一起以某种方式影响了 Raft
5. Raft
  1. Ongaro & Ousterhout 2014 - In Search of an Understandable Consensus Algorithm
  2. Lamport 说 Paxos 很容易，但我们仍然有各种问题
    1. 如果有一个我们可以理解的一致性算法怎么办？
  3. 当我们想要是状态机时，Paxos 接近独立决策
    1. 改为维护状态机转换的复制日志
  4. 还构建了集群成员转换，这对于真实系统来说是关键
  5. 非常新，但是我们有一个核心算法的 Coq 证明
  6. 可用于顺序或可线性化的状态机
    1. RethinkDB
    2. etcd
    3. Consul
事务
1. 分布式事务
  1. 迭代共识使我们对单一的总操作顺序达成一致
  2. 在可以独立执行的事务之间进行不必要的阻塞
  3. 我们如何提升性能？
  4. Distributed Transaction Architectures
  5. 单个写操作
    1. 所有更新都要经过一个队列，读操作在快照上执行
    2. 通常涉及某种持久性的数据结构
    3. 串行化到严格串行化
    4. Datomic
  6. OK but multiple writers?
  7. 多个写操作
    1. 一般来说，有几个分片，每个分片运行一个有共识支持的 FSM
    2. 某种支持跨分片事务的协议
  8. 独立分片
    1. A sort of halfway-step to general-purpose transactions
    2. 一种为了通用事务的中间步骤
    3. 不允许跨分片事务
    4. 运行一堆独立的共识状态机
    5. Can add a single global consensus group for cross-shard transactions
    6. 可以为跨分片事务加单个全局共识组
      1. 虽然吞吐量有限！
    7. VoltDB
  9. Percolator
    1. 基于线性分片的快照隔离
    2. 时间戳 Oracle 分配连续事务时间戳（使用共识）
    3. 读时间戳，从领导者读，预写, 提交时间戳，提交, 完成
    4. 14 个网络跳跃，可能都是跨数据中心的
    5. TiDB
  10. Spanner
    1. "外部一致性" (严格串行化？)
    2. 通过使用 GPS 和原子钟加速时间戳分配
    3. 基本上是基于 paxos 组的两阶段提交
      1. Locks on Paxos leaders
      2. 在 Paxos 领导上加锁
      3. 选取一个 paxos 组为整个事务提交记录提供服务
    4. 固定延迟底线保证时间戳单调性
    5. Yugabyte DB
    6. CockroachDB
  11. Calvin
    1. Order transactions in a log using consensus
    2. 使用共识算法在日志中记录订单交易
    3. 分片日志为了提高到任意高的吞吐
    4. 定期关闭志窗口并将事务应用到分片
    5. 应用程序不需要沟通！
    6. 严格串性化
    7. 1 次数据中心间往返，更多本地通信跳数
    8. 可扩展的吞吐量
    9. 最低延迟底线
    10. 事务必须是纯粹的，预先声明
    11. 可以与协议的扩展进行交互
    12. Fauna
2. 回顾
  1. 只添加而不是收回的系统需要较少的协调就能构建。我们可以使用 gossip 系统向其他进程广播消息，CRDT 用于合并来自对端的更新，以及用于弱隔离事务的 HAT。可串行化和线性化需要共识，我们可以通过 Paxos，ZAB，VR 或 Raft 获得。现在，我们将讨论分布式系统的不同规模。
  2. 时延不会为 0
    1. 带宽一直在增加，但是正在接近光和电子的物理极限
    2. 延迟预算决定了您的系统设计
      1. 你可以负担多少次网络调用
  3. 对于慢，不同类型的系统有不同的定义
    1. 不同的目标
    2. 不同的算法
时延特征
1. 多核系统
  1. 多核（尤其是 NUMA）架构是类似的分布式系统
    1. 节点不会病态故障，但是消息传递很慢
    2. 同步网络通过一个总线提供（例如，Intel QPI）
    3. 硬件和微代码中的整个复杂的协议集使内存看起来很清晰
    4. 非临时存储指令（例如，MOVNTI）
  2. 提供了屏蔽分布特性的抽象
    1. MFENCE/SFENCE/LFENCE
      1. 引入针对加载/存储指令的序列化点
      2. 延迟特征： ~100 周期 / ~30ns
      3. 依赖硬件，cache，指令等等
    2. CMPXCHG 比较和交换（顺序一致修改内存）
    3. LOCK
      1. 跨核心锁定整个内存子系统
  3. 但是抽象的同时也伴随着开销
    1. HLE 可能会有所帮助，但尚未成熟
    2. Blog: Mechanical Sympathy
    3. 在可能的地方，避免协调
    4. 上下文转换（进程或者线程）代价很高
    5. 处理器固定可以真正改善东西
    6. 当编写多线程程序时，将你的工作切分成独立的块
      1. 尝试将内存屏障与工作单元边界对齐
      2. 允许处理器在工作单元内尽可能多地作弊
    7. See Danica Porobic, 2016: High Performance Transaction Processing on Non-Uniform Hardware Topologies
2. 本地网络
  1. 你通常会在局域网内部部署复制系统
  2. 消息延迟可以低至 100 us
    1. 但是，在任何规模较大的网络（EC2）中，最少在 ms 范围
    2. 又是，包可能会被延迟五分钟
    3. 对这种情况需要做规划
  3. 与未命中缓存的磁盘查找相比，网络在 mega 数量级
    1. 或者更快，在 EC2 中
      1. EC2 磁盘延迟大约是 20ms
      2. 200 ms ?
      3. 20000 ms ?
      4. 但是 EBS 实际是其它计算机
      5. 笑死，如果你认为 EC2 中一切都是真实的
      6. 等等，实际的磁盘也会这样做？
      7. 到底什么是 IO 调度程序？
  4. 但是网络比内存/计算更慢
    1. 如果你的目标是吞吐量，工作单位应该花费超过一毫秒
    2. 但是分布还有其它原因
      1. 资源分片
      2. 故障隔离
3. 地理复制
  1. 全球范围部署的两个原因
    1. 最终用户的延迟
      1. 人类可以探测到 ~10ms 的延迟，容忍 ~100ms 的延迟
      2. SF--Denver: 50ms
      3. SF--Tokyo: 100ms
      4. SF--Madrid: 200ms
    2. 灾难恢复
      1. 数据中心是很好的，但是不是完美的
      2. 飓风是一个问题
      3. 整个亚马逊的区域可能会故障
      4. 是的，是区域，不是可用区(AZ)
  2. 最少一轮的共识
    1. 差的情况下可能需要 4 轮
      1. 如果你有一个糟糕的 Paxos 实现（例如 Cassandra），也许总是 4 轮
    2. 所以如果想在数据中心之间使用 Paxos，准备好应对这种开销
    3. 因为最小的延迟比用户可容忍的延迟还要高
      1. cache cache cache
      2. 写入队列，异步传递
      3. 考虑减少一致性保证以换取低延迟
      4. CRDT 可以保证安全的本地写入
      5. 因果一致性和 HAT 可以成为好的方式
  3. 强一致性呢？
    1. 地理分布的服务具有天然的分裂性
      1. EU 用户在 EU 服务器上；US 用户在 US 的服务器上
      2. 使用共识在不同的数据中心中间迁移用户
    2. 固定/代理更新到所在地数据中心
      1. 很有希望是最近的数据中心
      2. 但也可能不是。我认为 Facebook 仍然将所有写入推送到一个数据中心
    3. 当顺序一致性没问题时，将读取在本地缓存
4. 回顾
  1. 我们讨论了分布式系统的三个特征尺度：与同步网络耦合的多核处理器，由 LAN 链接的计算机，以及通过互联网或专用光纤链接的数据中心。 CPU 的主要后果是性能问题：了解如何最小化协调。在 LAN 上，在用户注意到之前，延迟对于许多网络跃点来说足够短。在地理复制系统中，高延迟最终会推动一致的固定数据中心的解决方案。
常见的分布式系统
1. 外置堆
  1. Redis，memcached，...
  2. 数据适合放到内存中，复杂的数据结构
  3. 当你的数据结构的内置数据结构很慢/丑陋时很有用
  4. 跟缓存一样优秀
  5. 或者作为平台之间共享状态的快速便捷的暂存器
  6. 不是特别安全
2. KV 存储
  1. Riak，Couch，Mongo，Cassandra，RethinkDB，HDFS，...
  2. 通常 1,2,3 维度的键
  3. O(1)访问时间，又是 O(range)根据 ID 的范围扫描
  4. 值之间没有强依赖关系
  5. 对象可以是不透明的或结构化的
  6. 大数据集
  7. 通常是可线性扩展的
  8. 通常没有事务
  9. 一致性模型范围 - 通常是可选的线性化/顺序操作
3. SQL 数据库
  1. Postgres, MySQL, Percona XtraDB, Oracle, MSSQL, VoltDB, CockroachDB, ...
  2. 通过关系代数定义：restrictions of products of records 等
  3. 中等大小的数据集
  4. 通常包含多记录事务
  5. 关系和事务需要协调，减少扩展性
  6. 许多系统是主从切换
  7. 访问代价依赖索引
  8. 典型的强一致性（SI，可串行化，阉割的可串行化）
4. 搜索
  1. Elasticsearch, SolrCloud, ...
  2. 索引引用的文件
  3. 中等到很大的数据集
  4. 使用 O(1)文档访问，日志化的搜索
  5. 很好的扩展性
  6. 典型的弱一致性
5. 协调服务
  1. Zookeeper、ETCD、Consul，...
  2. 典型的强（顺序或者线性化）一致性
  3. 小数据集
  4. 作为无状态服务的协调原语很有用
6. 流系统
  1. Storm、Spark ...
  2. 通常是定制设计、或者使用工具包来构建
  3. 典型的小内存数据容量
  4. 低延迟
  5. 高吞吐
  6. 弱一致性
7. 分布式队列
  1. Kafka, Kestrel, Rabbit, IronMQ, ActiveMQ, HornetQ, Beanstalk, SQS, Celery, ...
  2. 在多个节点将日志写入磁盘来实现冗余
  3. 当您需要立即确认工作，并在以后使用很有用
  4. 在无状态服务之间可靠地发送数据
  5. 我知道的仅有的一个不会在分区时丢失数据的是 Kafka
    1. SQS 也能？
  6. 队列不会提高端到端延迟
    1. 总是更快地立即完成工作
  7. 队列不会提高平均吞吐
    1. 消费者的限制
  8. 当消费者并发时，队列不提供总事件排序
    1. 您的消费者几乎肯定是并发的
  9. 同样，队列不保证异步使用者的事件顺序
    1. 因为消费者的副作用可能无序发生
    2. 所以，不要依赖顺序
  10. 队列不能提供最多一次或者最少一次的递送
    1. 任何声称不这样做的人都试图向你推销一些东西
    2. 恢复一次性递送需要仔细控制副作用
    3. 使您的排队操作具有幂等性
  11. 队列确实提高了突发吞吐量
  12. 分布式队列还提高了容错（如果不丢失数据）
    1. 如果不需要容错或者大缓冲，使用 TCP
    2. 很多人使用具有六个磁盘写入和十五个网络跃点的队列，其中单个套接字 write()可能已经足够
  13. 当您选择了糟糕的运行时时，队列可以让您解脱
8. 回顾
  1. 我们使用数据结构存储作为外置堆：它们是分布式系统的管道磁带。 KV 存储和关系数据库通常被部署为记录系统; KV 存储使用独立 key，不太适合关系数据，但与 SQL 存储相比提供了更好的可伸缩性和部分容错性，SQL 存储提供了丰富的查询和强大的事务保证。分布式搜索和协调服务完善了我们构建应用程序的基本工具包。流系统应用于数据集的连续，低延迟处理，并且往往看起来更像框架而不是数据库。分布式队列专注于消息而不是转换。
  2. 构建分布式系统的一般建议
    1. 来之不易的经历
    2. 重复其他专家告诉我的内容
      1. 在酒桌上
    3. 道听途说
    4. 过度简化
    5. Cargo-culting
    6. 我刚做的东西
    7. 你可能已经从别的渠道听说了
模式语言
1. 不要用分布式
  1. 规则 1：如果不是必须，请不要使用分布式
    1. 本地系统有可靠的原语。锁、线程、队列、事务。
      1. 当你迁移到分布式系统时，你必须从头开始
    2. 这个问题是否很小可以在一个节点上完成？
      1. 我有一个很大的数据问题
      2. Softlayer 将以每箱 5000 美元每月的价格出租一箱 3TB 的内存
      3. Supermicro 将以约 115,000 美元的价格出售 6TB 的盒子
      4. 现代计算机很快
      5. 我所知道的生产 JVM HTTP 服务已经可以支持 50K 请求/秒
      6. 解析 JSON 时间，记日志到磁盘，推送到 S3
      7. 使用 TCP 的协议缓冲区：1000 万/秒的事件
      8. 这项服务能否容忍单个节点的保证？
      9. 如果它奔溃了，我们可以再起来吗？
      10. 手动干预可以取代分布式算法吗？
2. 使用已经存在的分布式系统
  1. 如果必须分布，可以将任务推送到其它软件？
    1. 分布式数据库或者日志怎么样？
    2. 可以给亚马逊付钱让他们来做吗？
    3. 相反，维护费用是多少？
    4. 学习使用/操作该分布式系统多少钱？
3. 永不故障
  1. 购买非常昂贵的硬件
  2. 以受控方式更改软件和硬件
    1. 针对临时环境的试运行部署
  3. 可以构建非常可靠的网络和机器
    1. 以降低成本为代价，购买更昂贵的硬件，寻找人才
    2. 硬件/网络故障仍然发生，但足够罕见 => 低优先级
4. 接受故障
  1. 分布式系统不仅以延迟为特征，但以经常性，部分故障为特征
  2. 我们能接受这种失败并继续我们的生活吗？
    1. 我们的 SLA 是什么？
    2. 可以手动恢复吗？
    3. 可以给人付钱来修复吗？
    4. 保险可以承担损害吗？
    5. 我们可以打电话给客户并道歉吗？
  3. 听起来很傻，但是更加便宜
    1. 我们永远也不能阻止 100%的系统故障
    2. 有意识地选择恢复高于系统的水平
    3. 这就是金融公司和零售商的做法
5. 优先恢复
  1. Assume a failure has just occurred: how will you recover?
  2. 假设一个故障刚刚发生了：你怎么恢复？
  3. Make this recovery the default path of execution
  4. 使这个恢复成为程序的必经之路
  5. 编写恢复优先的代码可以让你避免错误处理
  6. 默认情况下执行恢复代码意味着您知道它有效
  7. 默认情况下恢复意味着您不必担心在真正故障期间的不同语义
  8. 如有必要，引入性能优化的快乐路径
    1. 但是你失去了其中的一些优势
6. 核对环路
  1. 你有一个复杂的、有状态的系统，并想把它迁移到某个地方
  2. 可以制定变更计划，并按顺序应用这些变更
    1. 但是，如果某些更改中断怎么办？你怎么恢复？
  3. 相反，维护一个目标：表示您希望系统成为什么
  4. 接下来，编写一个查看当前状态的函数，并将其与目标进行比较
  5. 使用该差异找到使系统更接近目标的步骤
  6. 无限重复
  7. 抗故障和抗干扰能力强
    1. 如果您的管理员手动调整内容怎么办？
    2. 如果控制系统的两个实例同时运行怎么办？
  8. 在 Borg & Kubernetes 等系统中部署效果显着
  9. 也适用于保持系统之间的数据同步
    1. 例如，确保每个订单都已发货和计费
7. 备份
  1. 备份基本是顺序一致的，但是可能丢失一个操作窗口的数据
    1. 当正确完成时
      1. 一些备份程序没有快照状态，导致文件系统或者数据库损坏
      2. 破坏外键关系，丢失文件等...
    2. 允许恢复到几分钟或者几天前
    3. 但是除了故障恢复，可以让你按时间返回
      1. 从逻辑故障中恢复很有用
      2. 分布式数据库正确完成其任务，但是告诉数据库删除了关键数据
8. 冗余
  1. 好的，所以失败不是一个选择
  2. 希望降低故障的可能性
  3. 在几个节点上进行相同的状态和相同的计算
    1. 我不是主-备的忠实信徒
      1. 备机可能有冷缓存，损坏的磁盘，旧版本等
      2. 备机在变为主机时往往会失败
      3. 尽可能主-主
      4. 效率的可预测性
    2. 我也不是只有两个副本的忠实的粉丝
      1. 节点故障概率太高
      2. 对于不重要的数据还可以
      3. 我一般都想要 3 份数据副本
      4. 对于重要的数据，4 或者 5 分副本
      5. 对于 Paxo 或者其它的多数派系统，3,5,7 很常见
    3. 常见的策略：Paxos 跨越 5 个节点，3 个或者 4 个在本地数据中心
      1. 操作可以在本地节点确认后立即完成;低延迟
      2. 适应单节点故障（虽然延迟会出现峰值）
      3. 但是在另一个 DC 中仍然有一个顺序一致的备份
      4. 所以在最后你失去了整个 DC，一切也都不会丢失
      5. 参见 Camille Fournier 关于 ZK 部署的会谈
  4. 只要故障不相关，冗余就可以提高可用性
    1. 失败并非不相关
    2. 来自同一批次的磁盘同时失败
    3. 当架顶式交换机断开时，同一机架节点出现故障
    4. UPS 断电时，相同 DC 节点发生故障
    5. 查看整个 EC2 AZ 故障
    6. 在每个节点上运行相同的错误计算将中断每个节点
      1. 昂贵的查询
      2. Riak list-keys
      3. Cassandra doomstones
    7. 级联故障
      1. Thundering-herd
      2. TCP incast
9. 分片
  1. 这个问题很大，你忍一下
  2. 将问题分解成足够小的部分以适合节点
    1. 不小：小零件=>高开销
    2. 不太大：需要逐个从节点到节点重新平衡工作单元
    3. 大约 10-100 个工作单位/节点是理想的
  3. 理想的：工作单元相同的大小
    1. 小心热点
    2. 小心随时间变化的工作量
  4. 提前了解你的界限
    1. 压倒一个节点之前单个部分有多大？
    2. 我们如何在它节点上出现之前，如何强制执行该限制？
      1. 然后在系统重新平衡时一个接一个地下沉所有其他节点
  5. 分配分片给节点
    1. 在数据库中内置
    2. 很好的候选，ZK，Etcd 等等
    3. 参见 Boundary's Ordasity
10. 独立的域
  1. 分片是一般模式避免协调的一个特殊场景
    1. 保持尽可能独立
      1. 提高容错
      2. 提高性能
      3. 减少复杂性
    2. 分片提高伸缩性
    3. 通过 CRDT 避免协调
    4. Flake ID：mostly time-ordered identifiers, zero-coordination
      1. 参考： http://yellerapp.com/posts/2015-02-09-flake-ids.html
    5. 部分可用：用户可以继续使用系统的一些部分
    6. 处理队列：更多消费者减少昂贵事件的影响
11. ID 结构
  1. 在我们的世界中，一定需要唯一的标识
    1. 在规模上，ID 结构可以决定你的成败
    2. 考虑下面的开销
      1. 扫描
      2. 排序
      3. 分片
    3. 顺序 ID 需要协调：我们可以避免吗？
      1. Flake ID，UUID
    4. 对于可分片，你的 ID 可以直接映射到一个分片吗？
    5. SaaS 应用：对象 ID 也可以编码客户 ID
    6. Twitter：推特 ID 可以编码用户 ID
12. 不变的值
  1. 从不更改的数据存储起来很简单
    1. 不需要协调
    2. 复制和恢复开销很小
    3. 在磁盘上很小的重新打包代价
  2. 对于 Cassandra，Riak，和 LSM 树 DB 很有用
    1. 或者 kafka 的日志
  3. 原因很简单：要么是存在，要么不存在
    1. 消除各种事务的头痛问题
    2. 非常容易缓存
  4. 高可用和持久性，可调节的写入延迟
    1. 低写入延迟：可以从最近的副本做应答
    2. 对于地理分布尤其有价值
  5. 需要垃圾回收
    1. 但有很好的方法可以做到
13. 可变值
  1. 指向变值的指针
  2. 指针很小！仅元数据
    1. 可以在小 DB 中存储很多的指针
    2. 对于协调服务或者关系 DB，是很好的候选
  3. 典型地，在系统中没有很多指针
    1. 你的全部 DB 可以在用一个指针表示
    2. Datomic 只有 ~5 个标识
  4. 对标识的强一致性操作可以由不可变的 HA 存储支持
    1. 利用 AP 存储延迟和规模
    2. 利用共识系统提供的小数据集的强一致性
    3. 写的可用性受到标识存储的限制
      1. 但是，如果你只需要顺序一致性，就可以读缓存
      2. 如果您只需要序列化就可以更容易
    4. 参见 Rich Hickey 关于 Datomic 架构的演讲
    5. 参见 Pat Helland 在 2013 年关于 Salesforce 存储的 Ricon West 主题演讲
14. 汇合
  1. 与顺序无关的系统更容易构造和推理
  2. 因此，可以避免协调
  3. CRDT 是汇合的，这意味着我们可以应用更新而不必等待
  4. 不变的值通常是汇合的：一旦存在，就固定了
  5. 流媒体系统也可以利用汇合：
    1. 当你知道你已经看到了所有内容时，缓冲事件和计算+刷新
    2. 发出部分结果，以便您现在可以采取操作，例如用于监视
    3. 当完整数据可用时，通过加法或者最大值来合并
    4. 银行分类账（大部分）是汇合的：事务顺序不影响余额
      1. 但当你需要执行一个最小余额时，就不再是汇合了
      2. 结合密封事件（例如当天结束）以恢复汇合
  6. 参考 Aiken, Widom, & Hellerstein 1992, "Behavior of Database Production Rules"
15. 背压
  1. 交互的服务通常通过队列连接
  2. 服务和队列的容量是有限的
  3. 当下游服务无法处理负载时，您如何处理它？
    1. 消耗资源并爆炸
    2. 摆脱负载，开始删除请求
    3. 拒绝请求，忽略任务，应答客户端失败
    4. 给客户端背压，告诉客户端放慢速度
  4. 2-4 允许系统追赶并恢复
  5. 背压取决于生产者的选择：组成成分
    1. 减载系统的客户端被锁定在减载中
      1. 他们没有办法知道系统已被冲洗过
    2. 背压系统的客户端可以将背压应用到他们的客户端
      1. 或卸载，依赖他们选择
    3. 如果你在实现一个异步系统，一定要包括反压力
      1. 你的用户会感谢你
  6. 基本上：边界资源
    1. 请求超时（有界时间）
    2. 指数退避（有界使用）
    3. 有界队列
    4. 有界并发
  7. 参考：Zach Tellman, "Everything Will Flow"
16. 域模型服务
  1. 问题由相互作用的逻辑部分组成
  2. 每个逻辑部分具有不同的代码，性能和存储需求
  3. 单体应用程序基本上是多租户系统
    1. 多租户很难
    2. 但通常可以在同一个过程中运行多个逻辑“服务”
  4. 将您的系统划分为域的离散部分的逻辑服务模型
  5. OO 方法：每个名词是一种服务
    1. 用户服务
    2. 视频服务
    3. 索引服务
  6. 功能方法：每个动词是一项服务
    1. 验证服务
    2. 搜索服务
    3. 调度/路由服务
  7. 我所知道的大多数大型系统都使用混合方式
    1. 名词服务是强制执行数据类型不变量的好方法
    2. 动词服务是强制执行转换不变量的好方法
    3. 所以有一个基本的用户服务，由 Auth 服务使用
  8. 你画线的地方......那很棘手
    1. 服务带来开销：尽可能少
    2. 考虑工作单元
    3. 需要独立扩展的独立服务
    4. 具有严格依赖性和严格延迟预算的服务
    5. 使用补充资源（例如磁盘和 CPU）的协同服务
    6. 手动：在渲染节点上运行 memcache
    7. 较新的商店：Google Borg，Mesos，Kubernetes
  9. 服务应该封装和抽象
    1. 尝试建造树而不是网
    2. 避免让外人直接操纵服务的数据存储
  10. 服务之间的协调需要特殊协议
    1. 必须重新发明事务
    2. 尽可能去通信
    3. 萨加斯
    4. 是为单节点世界编写的：我们必须在分布式环境中聪明一点
    5. 事务必须是幂等的，或者一起回滚
    6. Typhon / Cerberus
    7. 多个数据存储的因果一致性协议
17. 结构遵循社交空间
  1. 制作软件是一种基本的社交工具
  2. 自然对齐：团队或个人拥有特定服务
    1. 乔·弗里曼，“无结构的暴政”
      1. 责任和权力应该是明确的
      2. 通过角色轮换人员以防止领地
      3. 促进信息共享
      4. 但不要经常转换
      5. 软件的增加成本非常高
  3. 随着团队的成长，其使命和思想将正式化
    1. 服务和他们的界限也是如此
    2. 逐渐积累关于与世界的服务关系的假设
    3. 重写以应对不断变化的外部压力
    4. Tushman＆Romanelli，1985：组织演变
  4. 服务可以是库
    1. 最初，您的所有服务应该是库
    2. 完全可以依赖多个服务中的用户库
    3. 具有明确界限的库很容易被提取出来成为服务
  5. 社会结构管理库/服务边界
    1. 由于库的用户很少，或者用户协调紧密，因此更改很容易
    2. 但是在许多团队中，用户有不同的优先级，必须让他们信服
    3. 为什么用户应该做一些工作来升级到新的库版本？
    4. 服务强制通过定义的 API 弃用生命周期进行协调
      1. 您还可以通过代码审查和工具对库强制执行此操作
  6. 服务支持集中控制
    1. 您的性能改进会立即影响每个人
    2. 逐步转换为新的磁盘格式或支持数据库
    3. 在一个地方使用该服务
    4. 更难用库做这些事情
  7. 服务有成本
    1. 网络调用的故障复杂性和延迟开销
    2. 服务依赖的混乱
    3. 很难静态分析代码路径
    4. 您认为库 API 版本很难
    5. 额外的仪器/部署
  8. 服务可以使用良好的客户端库
    1. 该库可能是“打开套接字”或 HTTP 客户端
      1. 利用 HTTP 标头！
      2. 接受标题版本
      3. 对缓存和代理的大量支持
      4. Haproxy 是 HTTP 和 TCP 服务的优秀路由器
    2. 最终，库可能包含模拟 IO
      1. 服务团队负责测试服务是否提供 API
      2. 当已知 API 稳定时，每个客户都可以假设它有效
      3. 无需在测试套件中进行网络呼叫
      4. 大幅减少测试运行时和开发环境的复杂性
18. 跨服务协调
  1. 服务之间的协调需要特殊的协议
    1. 必须重新发明事务
    2. 尽可能交换信息
    3. Sagas
      1. 是为单节点世界编写的：我们必须在分布式环境中保持聪明
      2. 事务须是幂等的，或者可以回滚
    4. Typhon/Cerberus
      1. 基于多个数据存储的因果一致性协议
      2. 例如：如果露皮塔屏蔽了安吉拉小姐，然后发帖，安吉拉小姐就看不到了
      3. Typhon：单个逻辑实体在不同的数据存储中有数据项表示
      4. 假设数据存储是可序列化的或对项目提供原子读取/cas
      5. 访问同一实体且 T1 发生的事务- 在 T2 获得之前
      6. Cerberus：涉及单个实体的事务协议 x
      7. 写入只能影响 x 的一种表示
      8. 跨 x 表示的任意数量的读取
      9. 全局元数据：每个实体的版本向量 (GVV)
      10. 每个表示元数据：
      11. 更新版本向量 (UVV)：上次更新时已知的版本
      12. 读取版本向量 (RVV)：上次读取时已知的版本
      13. 当 GVV < UVV/RVV 时检测到冲突
      14. 两个阶段：
      15. 读
      16. 检查实体 x 的 GVV
      17. 在每个（要求的）表示上执行 x 的读取
      18. 在每个表示中：检查 RVV <= GVV，更新 RVV
      19. 写
      20. 发送写到代表
      21. 检查 UVV <= GVV 和 RVV <= GVV
      22. 提交
      23. 更新表示和 RVV/UVV 确保 RVV/UVV 不变
      24. 通过增加现有 UVV 的第 i 个条目构建的新 UVV
    5. 通用事务
      1. 加尔文
      2. 可序列化（或严格 1SR）事务
      3. 确定性 txns 进入分片全局日志
      4. 日志确保事务顺序
      5. 在副本/分片上的应用不需要进一步的协调
      6. 日志窗口的最小延迟下限
      7. CockroachDB
      8. 可序列化
      9. 假设线性化商店
      10. 假设半同步时钟
      11. 类似于更易于处理的扳手
19. 迁移
  1. 迁移很困难
    1. 没有银弹
    2. 但有些技巧可以让你的生活更轻松
  2. 硬切换
    1. 编写新系统并迁移以将旧数据复制到其中
    2. 让依赖服务与两者对话——但在实践中，只有一个。
    3. 关闭旧系统
    4. 复制数据
    5. 启动新系统
    6. 权衡！
      1. 不必担心传输中的数据
      2. 简单的迁移脚本：只需读取所有数据并写入新的数据存储
      3. 需要与迁移脚本成比例的停机时间
    7. 有时可以一次将其范围限定为单个分片/用户/域
  3. 增量
    1. 编写新系统 B
    2. 与原始 A 一起部署
    3. 依赖服务与两者交谈
      1. 理想：找到所有读者，让每个读者都与 A 和 B 交谈
      2. 然后开始写信给 B
      3. 这让您不必担心只知道 A 的读者
    4. 一致性噩梦；需要追踪所有数据依赖
    5. 权衡！
      1. 减少/无停机时间
      2. 但需要复杂的数据依赖推理
  4. 包装服务
    1. 从操作上讲，查找和更改 A 的所有用户可能很棘手
    2. 所以……不要。引入代理 A 的包装服务 W
    3. 引入 B，并进行更改，以便 W 也与 B 交谈
    4. 当 A 被淘汰时，移除 W 并直接与 B 交谈。
    5. 允许集中度量、错误、行为比较等
  5. 最终的原子性
    1. 假设您将每次更新写入旧服务 A，然后写入新服务 B
    2. 在某些时候，您对 A 的写入会成功，而 B 会失败。然后怎样呢？
    3. 可以使用读修复：读取 A 和 B，填写缺失的更新
      1. 但这需要可合并性：仅适用于 CRDT 之类的东西
    4. 可以使用核对流程
      1. 遍历整个数据库，寻找变化，同时适用于两者。
      2. 还需要像 CRDT 这样的东西
    5. 可以使用 Sage
      1. 所有更新都进入持久队列
      2. 队列工作者重试直到更新应用于 A 和 B
      3. 可能需要订购更新以避免状态分歧
      4. 潜在的全局列化
      5. 注意数据库的一致性模型
  6. 隔离
    1. 想象一下 Jane 将 w1 写入 A，然后写入 B
    2. 同时，Naomi 将 w2 写入 B，然后写入 A
    3. 结果：A = w2，B = w1
    4. 最终的原子性不足以防止分歧
    5. 可以通过选择标准订单来减少问题：总是 A 然后 B（或 B 然后 A）
      1. 但是想象一下
      2. Jane 写 A = w1
      3. Naomi 写 A = w2
      4. Naomi 写 B = w2
      5. 简写 B = w1
      6. 我们又得到了喜忧参半的结果。射击。
    6. 可以使用 CRDT 缓解
    7. 或者，如果 A 和 B 顺序一致，可以使用 CaS 操作来
      1. “如果最后一次写入是 w1，则写入 w2”
    8. 如果操作影响多个键，则必须在该处应用 CaS 逻辑
  7. 增量迁移的有用属性
    1. 决定论
      1. 避免让数据库生成随机数、自动 ID、时间戳
      2. 更容易将更新应用到两个数据存储并获得相同的结果
    2. 幂等性
      1. 让您自由重试更新
    3. 交换性
      1. 无需序列化更新
    4. CRDTs：结合性、交换性、幂等性。
    5. 不变性：平凡的 CRDT
    6. 无状态：无需担心状态！
      1. 确保你以同样的方式与外部有状态的东西交谈
  8. 换出队列怎么样？
    1. 正如我们所提到的，队列系统应该已经被设计为幂等性，
      1. 如果是这样，这（相对）容易
      2. 工作人员从两个队列中消费
      3. 翻转生产者只向新队列发送消息
      4. 等待旧队列耗尽
      5. 解除旧队列
    2. 但我们想要订单？？？
      1. 你将需要重建它
      2. 一种选择：单个生产者与队列紧密耦合
      3. 将每条消息 m 写入 A 和 B；直到双方都确认才继续前进
      4. 这强制 A 和 B 就订单达成一致
      5. 消费者可以一视同仁地对待 A 和 B：只从 A 或 B 中消费
      6. 再次假设幂等性！
      7. 另一种选择：序列号，在客户端重建的顺序
      8. 例如为每个值分配序列号
      9. 使用 A 的队列偏移量？
      10. 使用共识系统？
      11. 客户端读取序列号，存储在内部缓冲区中，按顺序应用 r
20. 回顾
  1. 如果可能，请尝试使用单个节点而不是分布式系统。接受一些失败是不可避免的：SLA 和道歉可能具有成本效益。为了处理灾难性故障，我们使用备份。为了提高可靠性，我们引入了冗余。为了扩展到大的问题域，我们将问题分成片。不可变值易于存储和缓存，并且可以通过可变身份引用，允许我们在大规模上构建强大一致的系统。随着软件的发展，不同的组件必须独立扩展，我们将库分解为不同的服务。服务结构与团队密切配合。
  2. 不仅仅是设计考虑
  3. 证明很重要，但真正的系统需要 IO
生产问题
1. 您的文化支持分布式系统
  1. 理解生产中的分布式系统需要具有多种角色的人员密切合作。
    1. 部署
    2. QA
    3. 操作
  2. 共性问题
    1. 开发需要关注产品
    2. 运行需要关注实现
    3. 好的沟通可以更快地诊断问题
2. 测试一切
  1. 类型系统非常适合防止逻辑错误
    1. 减少了测试负担
  2. 然而，它们在预测或控制运行时性能方面并不是很好
  3. 所以，需要可靠的测试套件
    1. 理想情况下，您需要一个严格不同类型的测试
    2. 几秒钟内运行的快速基于示例的测试
    3. 可以在一夜之间运行的更彻底的基于属性的测试
    4. 能够在进程中模拟整个集群
    5. 控制与模拟网络的并发交织
    6. 自动化的硬件故障
  4. 测试分布式系统比测试本地系统要困难得多
    1. 你从未听说过的大量失败模式
    2. 组合状态空间
    3. 错误只能表现为小大中间时间空间并发
3. “这很慢”
  1. 杰夫霍奇斯：你会听到的最糟糕的错误是“它很慢”
    1. 一直发生，很难本地化
    2. 由于系统是分布式的，因此必须分析多个节点
      1. 为此建立的分析工具并不多
      2. Sigelman 等，2010：Dapper，一种大规模分布式系统跟踪基础设施
      3. Zipkin
      4. 大工具投资
    3. 分析工具擅长发现 CPU 问题
      1. 但高延迟通常是 IO 的标志，而不是 CPU
      2. 磁盘延迟
      3. 网络延迟
      4. GC 延迟
      5. 队列延迟
    4. 尝试使用应用程序级指标本地化问题
      1. 然后深入了解流程和操作系统性能
    5. 执行相同工作的节点之间的延迟差异是一个重要信号
      1. 1/3 节点慢：可能是节点硬件，重新路由
      2. 3/3 节点缓慢：可能是逻辑错误：查看分片大小，工作负载，查询
    6. 扇出工作负载放大了尾部延迟
      1. Jeff Dean，2013：The Tail at Scale
      2. 考虑推测并行性
4. 测量一切
  1. 生产中的缓慢（和彻头彻尾的错误）源于相互作用系统
    1. 为什么？因为您的全面测试套件可能验证了单一系统大多是正确的
    2. 所以我们需要一种方法来了解系统在生产中做了什么
    3. 在某种程度上，良好的监控就像持续测试
      1. 但不是替代品：这些是不同的领域
      2. 两者均可确保您的更改正常
    4. 想要高频监控
      1. 生产行为可以在 1 毫秒的规模上进行
      2. TCP incast
      3. 理想情况下~~ 1ms 分辨率
      4. 在极限情况下，Ops 响应时间与观察延迟呈线性关系
      5. 约 1 秒的端到端延迟
      6. 理想情况下，毫秒级延迟，也可能是 ms 分辨率
      7. 通常成本过高;回到 1 或 10 秒
      8. 有时你可以忍受 60 秒
    5. 对于容量规划，每小时/每日季节性更有用
    6. 测量应与应用程序紧密耦合
      1. 只衡量重要的事情
      2. 回应请求很重要
      3. 节点 CPU 并不重要
      4. 大多数系统的关键指标
      5. Apdex：在延迟 SLA 内使用成功的应答
      6. 延迟分布：0,0.5,0.95,0.99,1
      7. 百分位数，而不是平均数
      8. 顺便说一句，你不能采取百分位数的均值
      9. 总吞吐量
      10. 队列统计
      11. 其他系统延迟/吞吐量的主观体验
      12. 数据库可能认为它很健康，但客户可能会觉得它很慢
      13. 组合爆炸 —— 在深入故障时最好使用它
      14. 您可能必须自己编写此测量
      15. 投资指标库
    7. 开箱即用的监控通常无法衡量真正重要的因素：您的应用程序的行为
      1. 但它在追踪问题原因方面非常有用
      2. 主机指标，如 CPU，磁盘等
      3. 你的应用程序做了一些常见的事情（例如 rails 应用程序）工具，如 New Relic，运作良好
    8. 客户端的分片指标
      1. 当用户具有不同的工作负载时很有用
      2. 可以调整阈值以适应该客户端
      3. 主要客户端分一些，“其余”的另一个桶
    9. 超级工具：分布式跟踪（Zipkin，Dapper 等）
      1. 大量时间投资
      2. 神秘机器
      3. 从跟踪数据自动推断服务之间的因果关系
      4. 识别关键路径
      5. 在实施之前对新算法进行性能建模
5. 日志
  1. 记录在大规模系统上不太有用
    1. 问题可能未本地化到一个节点
      1. 当请求触及更多服务时，必须跟踪许多日志文件
      2. 投资日志收集基础设施
      3. ELK，Splunk，etc
    2. 非结构化信息难以汇总
      1. 记录结构化事件
6. 影子流量
  1. 负载测试仅在模拟负载与实际负载匹配时才有用
  2. 考虑转储生产流量
    1. 太棒了：使用 SIGUSR1 终止一个进程，它会转储五分钟的请求加载
    2. 太棒了：tcpdump / tcpreplay 用于请求的限制
    3. 太棒了：将实时流量映射到您的暂存/ QA 节点
  3. 见 Envoy from Lyft
7. 版本
  1. 据我所知，协议版本控制是一个广泛存在的问题
    1. 包括所有消息的版本标记
    2. 包括兼容性逻辑
    3. 当客户的请求无法处理时通知客户
      1. 并对此进行检测，以便了解哪些系统必须升级
8. 推广
  1. 推广通常是您如何解决问题的方法
  2. 花时间进行自动化，可靠的部署
    1. 放大你做的其他事情
    2. 节点平滑循环以防止流量中断
      1. 这意味着您将同时运行多个版本的软件
      2. 版本控制开的坏头
    3. 通知负载均衡器会退出
    4. 协调以防止级联故障
  3. 仅推出一小部分负载或部分用户
    1. 逐渐增加新软件的用户数量
    2. 当您看到错误时，可以还原或向前回滚
    3. 考虑在生产环境中跟踪流量并比较旧/新版本
      1. 确定新代码是否更快和正确的好方法
9. 自动化控制
  1. 自动化故障处理很不错
  2. 但还不够
    1. "Ironies of Automation", Bainbridge 1983
      1. https://pdfs.semanticscholar.org/0713/bb9d9b138e4e0a15406006de9b0cddf68e28.pdf
10. 特性标志
  1. 我们希望在部署后逐步推出变更集
    1. 逐个引入功能，以了解它们对指标的影响
    2. 逐步将负载从一个数据库转移到另一个数据库
    3. 当推广出错时禁用功能
  2. 我们希望在某些服务降级时获得部分可用性
    1. 禁用代价昂贵的功能以在故障期间加速恢复
  3. 使用高度可用的协调服务来确定要使用的代码路径或多久一次
    1. 此服务应具有最小的依赖性
      1. 不要使用主 DB
  4. 当出现问题时，您可以调整系统的行为
    1. 协调服务停止时，失败安全！
11. 混沌工程
  1. 打破生产中的东西
    1. 迫使工程师适当地现在处理故障，而不是稍后对事件的响应
    2. 识别关键路径中的意外依赖关系
      1. “当新的统计数据服务出现故障时，需要使用 API。是吗？确定那是必要的吗？
    3. 需要良好的仪表和警报，因此您可以衡量事件影响
    4. 爆炸半径有限
      1. 不要每五分钟核对整个数据中心
      2. 但是每季度确实地试一次
      3. 不要破坏复制组中的许多节点
      4. 一次只打破一小部分请求/用户
12. 哦不，队列
  1. 每个队列都是一个可怕的地方，可怕的错误
    1. 没有节点有无限制的内存。你的队列必须有界限
    2. 但有多大？没人知道
    3. 在生产环境中检测你的队列以找出答案
  2. 利特尔定律：平均队列深度 = 平均到达率 * 平均延迟
    1. 这是分布式无关的
  3. 使用队列以平滑负载的波动
    1. 以延迟为代价提高吞吐量
    2. 如果您的负载高于容量，则没有队列可以节省您的费用
      1. 当队列变满时，卸载负荷或施加背压
      2. 测量这个
      3. 当发生卸载负荷时，警铃响起
      4. 背压作为上游延迟可见
    3. 测量队列深度
      1. 高深度是您需要添加节点容量的线索
      2. 端到端队列延迟应小于波动时间尺度
      3. 提高队列大小可能很诱人，但这是一个恶性循环
    4. 所有这一切都很难。我没有你的好答案
      1. 问 Jeff Hodges 为什么这很难：看他 2013 年的 RICON West 谈话
      2. 见 Zach Tellman —— 一切都会流动
13. 回顾
  1. 运行分布式系统需要开发人员，QA 和运营工程师之间的合作。静态分析和包括基于示例和属性的测试的测试套件可以帮助确保程序的正确性，但了解生产行为需要全面的测量和警报。成熟的分布式系统团队经常投资工具：流量阴影，版本控制，增量部署和功能标记。最后，队列需要特别小心。
进一步阅读
1. 线上
  1. Mixu has a delightful book on distributed systems with incredible detail. http://book.mixu.net/distsys/
  2. Jeff Hodges has some excellent, production-focused advice. https://www.somethingsimilar.com/2013/01/14/notes-on-distributed-systems-for-young-bloods/
  3. The Fallacies of Distributed Computing is a classic text on mistaken assumptions we make designing distributed systems. http://www.rgoarchitects.com/Files/fallacies.pdf
  4. Christopher Meiklejohn has a list of key papers in distributed systems. http://christophermeiklejohn.com/distributed/systems/2013/07/12/readings-in-distributed-systems.html
  5. Dan Creswell has a lovely reading list. https://dancres.github.io/Pages/
2. 丛书
  1. Martin Kleppmann 的数据密集型应用设计为从业者提供了分布式系统的全面介绍。
  2. Nancy Lynch 的 "Distributed Algorithms" 更理论的角度对该领域进行了全面概述