@Lenciel

分布式系统介绍

基础设施团队在招聘工程师的JD上一般会有下面几项:

  • 对于分布式系统关键特征和术语能基本掌握
  • 对于分布式领域常见的算法和理论有基本认知
  • 对于分布式系统在生产环境的常见问题有简单了解

那怎么看一个人是不是具备了这方面的能力呢?本座面试时总会从“什么是分布式系统”问起,大多数时候还是会听到各种稀奇古怪的答案,甚至屋子里一下子就安静了。

最怕世界突然安静。

年后又招人了,并且要开始做内部培训。这里梳理一下分布式系统的一些基础知识。参考了aphyr的基础培训课程和Dan Creswell的分布式系统必读指南,非常基础,非常必读,no rocket science。

Let’s go。

1.0 什么是“分布式系统”?

Lamport, 1987:

A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.

  • 大多数物理服务器都运行着 *nix 系统,通过TCP或者UDP进行进程间的通信:
    • 可以是云上的虚拟机
    • 也可以是通过InfiniBand通信的系统
    • 可以是局域网里面,隔着几米的距离
    • 也可以是广域网,隔着几千公里距离
  • 大多数移动App也是一个分布式系统里的一部分
    • 移动App工作的网络环境比服务器端更加恶劣
    • 其他桌面系统的浏览器以此类推的,也属于分布式系统
    • 所以并不是服务器才属于分布式系统,大部分客户端也是
  • 更一般地来说,分布式系统涵盖:
    • 由相互之间需要通信的部件构成的
    • 通信速度“慢”
    • 通信还常常“不稳定”
    • 的任何系统
  • 比如:
    • 飞机上冗余的CPU
    • ATM机和POS机终端
    • 空间站
    • 支付系统
    • 技术会议里的参会者
    • 喝醉了之后发微信的朋友
    • 写了情书让你帮忙寄出去的基友立

1.1 节点和网络

  • 分布式系统里面的单个组成部分被称为node:“节点
    • 文献里看到的processesagents或者actors,多半也是描述同样的东西

1.1.1 节点

  • 延迟特性
    • 节点内部的操作“很快”
    • 节点之间的操作“很慢”
    • 快和慢是相对的,度量标准取决于系统完成什么样的工作
  • 可靠性
    • 可以失效,但失效的时候作为整体单元失效
    • 失效时是可以被感知的
    • 状态是连贯一致
    • 状态迁移是有序,优雅的
    • 通常是以单线程的状态机模型建模的
  • 一个节点本身也有可能是一个分布式系统
    • 但只要对外作为一个整体,这个节点提供高速、一致的可操作接口,我们就认为它是一个节点
  • 进程的形式化模型
    • Communicating Sequential Processes
    • Pi-calculus
    • Ambient calculus
    • Actor model
  • 节点失效的形式化模型
    • Crash-stop
    • Crash-recover
    • Crash-amnesia
    • Byzantine

1.1.2 以消息流(message flow)的方式来思考网络(network)

  • 节点之间通过网络进行交互
    • 人类通过语音相互沟通
    • 粒子通过场相互沟通
    • 计算机通过IP、UDP、SCTP等相互沟通
  • 我们把这些交互建模为节点之间发送的离散的消息
  • 消息需要时间来传播
    • 这就是分布式系统里面“慢”的那部分
    • 我们称其为“延迟”
  • 消息常常都会丢
    • 这是分布式系统“不稳定”的又一个因素
  • 网络不是同质的,资源均匀的
    • 有些网络连接比其他的连接要慢、带宽要窄、稳定性要差

1.1.3 因果图

  • 我们可以把节点和它们之间的交互关系表示为一个视图
    • 时间轴是从左到右,或者从上到下的
    • 节点可以抽象为时间轴方向上的线段(它们在一个时间段内一直存在)
    • 消息是连接这些节点线段的有方向的路径

1.1.4 同步网络

  • 节点执行是按时序来的:每个节点之间距离都是1
  • 消息延迟是有边界的
  • 有一个完美的全局时钟
  • 很容易被证明的一件事情是
    • 同步网络几乎没法构造出来,你的系统多半不是

1.1.5 半同步网络

  • 和同步网络类似,但是时钟不是固定距离为1,而是一个范围,比如 [c, 1]

1.1.6 异步网络

  • 独立执行,互不依赖
  • 消息的时延没有可控边界
  • 没有全局时钟
  • 比半同步或者同步网络要脆弱
  • IP网络肯定是异步的
    • 但在实际操作中并没有发生真正的pathological stuff
    • 大多数网络都可以在几秒到几周内恢复,不会永远down掉
      • 相反的, 人类的时间维度是从几秒到几周的
      • 因此我们不能假装问题不存在

1.2 当网络出问题时

  • 异步网络允许发生
    • Duplicate
    • Delay
    • Drop
    • Reorder
  • 丢包和时延是难以分辨的
  • 拜占庭将军问题
    • 包括对内容重写
    • 在真实网络里面大都不会发生
      • 我只是说大都…

1.3 底层协议

1.3.1 TCP

  • TCP一般就够用了
    • 如不确定,先用TCP
    • 但不完美,虽然可以对它进行加速
    • 但知道怎么做以及什么时候才需要做很关键
  • 虽然单个TCP连接实际上有自带的duplicate和reorder治理
    • 但很可能会有多个连接打开
    • 而TCP连接总会失败
    • 当这种情况发生时,要不就会丢消息,要不就需要重试
    • 所以应该在TCP上自定义一个增量的序列号来编码,从而对乱掉的时序进行重建

1.3.2 UDP

  • 和TCP相同的寻址规则,但是没有stream invariants
  • 很多人使用UDP为了“更快的速度”
    • 不要认为路由器和节点会被丢弃
    • 不要认为包会重传
    • 或者重新排序
    • “But at least it’s unbiased right?”
      • 并不是
    • 这些都造成一些破坏,比如在收集metrics的时候
    • 要debug也是非常的困难
    • TCP提供了流控,并且把logical messages重新打包成packets
      • UDP下需要自己来实现流控和背压
    • “TLS over UDP”是可以做的,但是开发难度很高
  • UDP在TCP的FSM的overhead成本过于高昂的时,是有用的
    • 内存压力
    • 大量的生命周期很短的连接和socket的重用
  • 在best-effort delivery已经能够很好地满足系统目标的时候特别好用
    • 语音通话:当对方听不清时,用户自己会道歉然后重传
    • 游戏: 延迟和卡顿,但会重新对齐
    • 高层的协议在底层已经乱掉的情况下仍然会继续工作假装什么都没有发生

1.4 时钟

  • 当系统分割成多个独立部分的时候,我们仍然希望事件一定程度上是有序
  • 时钟帮助我们对事件进行排序:先这个,后那个

1.4.1 系统时钟

  • 理论上,操作系统的时钟可以给系统产生的事件带来顺序
    • 然并卵: NTP可能没有你以为的工作那么理想
    • 然并卵: 在两个节点间的同步完成得并不好
    • 然并卵: 硬件也会有漂移
    • 然并卵: 大数还会带来问题
    • 然并卵: POSIX 时钟从设计上就不是单调的
      • Cloudflare 2017: 因为leap second造成的问题
      • 其实就是当时 Go 还不提供 CLOCK_MONOTONIC 的接口
      • 在计算出一个负的duration然后把它交给 rand.int63n() 后,就驾崩了
      • 造成了DNS解析失败: 1% 的 HTTP 访问被影响了好几个小时
    • 然并卵: The timescales you want to measure may not be attainable
    • 然并卵: 线程会睡
    • 然并卵: 运行时会跪
    • 然并卵: OS会退
    • 然并卵: 硬件会醉
  • 怀疑人生了吧?

1.4.2 Lamport时钟

  • Lamport 1977: “Time, Clocks, and the Ordering of Events in a Distributed System
    • 每个进程一个逻辑时钟
    • 每次状态迁移的时候单调递增: t' = t + 1
    • 每次消息发送的操作时间戳+1并带上改时间戳
    • 每次接收消息的操作:t' = max(t, t_msg + 1)
  • 只要对所有的进程进行排序,我们就可以知道消息的顺序
    • 但是这个序列号看起来非常不直观
    • 并且无法表示同时发生的消息

1.4.3 向量时钟

  • 把所有进程的时钟放到一个向量里
  • t_i' = max(t_i, t_msg_i)
  • 每次处理完内部事件,把向量里自己进程的逻辑时钟加1
  • 向量时钟记录了逻辑时钟没有的因果关系,也就是偏序
    • 两个事件的因果关系为:
      • A < B 意味着A在B后发生
      • B < A 意味着B在A后发生
      • 否则两者就是没有因果关系的
    • 如果所有的 A_i <= B_i,且至少有一个A_i < B_i,那么 A < B
    • 如果A和B比起来有的分量大,有的分量小,则可能是同时发生
  • 棒棒棒: the past is shared; the present is independent
    • 当下各个节点的状态需要被保留
    • 过去的状态可以被丢弃
    • 如何对过去的状态做GC
  • 向量空间里面有n个进程
    • GC的时候需要协调顺序
    • 或者不做GC,牺牲掉正确性,直接删掉旧的状态
  • 变种:分布式系统中数据一般存在多个副本,多个副本的时钟可能被同时更新,引起副本间数据不一致

1.4.4 GP