干货写在前面

协程的概念就不详细介绍了,不清楚的同学可以自己google,windows和unix like系统
本身就提供了协程的支持,windows下叫fiber,unix like系统下叫ucontext.

协程是一种用户态的轻量级线程。本篇主要研究协程的 C/C++ 的实现。
首先我们可以看看有哪些语言已经具备协程语义：

• 比较重量级的有 C#、erlang、golang*
• 轻量级有 python、lua、javascript、ruby
• 还有函数式的 scala、scheme 等。

c/c++ 不直接支持协程语义，但有不少开源的协程库，如：
Protothreads：一个 “蝇量级” C 语言协程库
libco: 来自腾讯的开源协程库 libco 介绍，官网
coroutine: 云风的一个 C 语言同步协程库, 详细信息

目前看到大概有四种实现协程的方式：

• 第一种：利用 glibc 的 ucontext 组件 (云风的库)
• 第二种：使用汇编代码来切换上下文 (实现 c 协程)
• 第三种：利用 C 语言语法 switch-case 的奇淫技巧来实现（Protothreads)
• 第四种：利用了 C 语言的 setjmp 和 longjmp（ 一种协程的 C/C++ 实现, 要求函数里面使用 static local 的变量来保存协程内部的数据）

本篇主要使用 ucontext 来实现简单的协程库。

. . .

分布式系统

分布式系统的就准备:

• CAP理论
• BASE理论
• 分布式事务
• 分布式锁
• 限流
• 熔断
• 一致性选举算法
• 主从架构
• 集群架构
• 异地多活
• 负载均衡
• 分层架构
• 微服务, 服务治理
• …

共识

consensus 准确的翻译是共识，即多个提议者达成共识的过程，例如 Paxos，Raft 就是共识算法，paxos 是一种共识理论，分布式系统是他的场景，一致性是他的目标。

一致性（Consistency）的含义比共识（consensus）要宽泛，一致性指的是多个副本对外呈现的状态。包括顺序一致性、线性一致性、最终一致性等。而共识特指达成一致的过程，但注意，共识并不意味着实现了一致性，一些情况下他是做不到的。

一致性的类别

提到分布式架构就一定绕不开 “一致性” 问题，而 “一致性” 其实又包含了数据一致性和事务一致性两种情况，本节主要讨论数据一致性（事务一致性指 ACID）。复制是导致出现数据一致性问题的唯一原因。

关于强和弱的定义，可以参考剑桥大学的 slide.

• Strong consistency – ensures that only consistent state can be seen:
  • All replicas return the same value when queried for the attribute of an object * All replicas return the same value when queried for the attribute of an object. This may be achieved at a cost – high latency.
• Weak consistency – for when the “fast access” requirement dominates:
  • update some replica, e.g. the closest or some designated replica
  • the updated replica sends up date messages to all other replicas.
  • different replicas can return different values for the queried attribute of the object the value should be returned, or “not known”, with a timestamp
  • in the long term all updates must propagate to all replicas …….

一致性的详细分类:

• 强一致性
  强一致性集群中，对任何一个节点发起请求都会得到相同的回复，但可能会产生相对高的延迟
  • 线性一致性(Linearizability consistency, 也叫原子一致性, 大多数时候我们说强一致性其实是指线性一致性)
  • 顺序一致性(Sequential consistency, 比线性一致性稍弱, 但也算是强一致性的一种)
• 弱一致性
  弱一致性具有更低的响应延迟，但可能会回复过期的数据, 导致各个节点拿到的数据不一致。
  • 最终一致性(Eventual consistency)
    • 含义: 系统会保证在一定时间内，能够达到一个数据一致的状态。这里之所以将最终一致性单独提出来，是因为它是弱一致性中非常推崇的一种一致性模型，也是业界在大型分布式系统的数据一致性上比较推崇的模型。
  • 因果一致性(Causal consistency)
    • 含义: 如果一系列写入按某个逻辑顺序发生，那么任何人读取这些写入时，会看见它们以正确的逻辑顺序出现。
    • 实现: 一种方案是应用保证将问题和对应的回答写入相同的分区
  • 读写一致性:
    • 含义: 它可以保证，如果用户刷新页面，他们总会看到自己刚提交的任何更新。它不会对其他用户的写入做出承诺，其他用户的更新可能稍等才会看到，但它保证用户自己提交的数据能马上被自己看到。
  • 单调读:
    • 含义: 如果先前读取到较新的数据，后续读取不会得到更旧的数据.
    • 实现: 实现单调读取的一种方式是确保每个用户总是从同一个节点进行读取（不同的用户可以从不同的节点读取），比如可以基于用户 ID 的哈希值来选择节点，而不是随机选择节点。

线性一致性

etcd 读写都做了线性一致，即 etcd 是标准的强一致性保证。

线性一致性又被称为强一致性、严格一致性、原子一致性。是程序能实现的最高的一致性模型，也是分布式系统用户最期望的一致性。CAP 中的 C 一般就指它
顺序一致性中进程只关心大家认同的顺序一样就行，不需要与全局时钟一致，线性就更严格，从这种偏序（partial order）要达到全序（total order）

要求是：

• 任何一次读都能读到某个数据的最近一次写的数据。
• 系统中的所有进程，看到的操作顺序，都与全局时钟下的顺序一致。

以下图讨论,

B1 看到 x 的新值，C1 反而看到的是旧值。即对用户来说，x 的值发生了回跳。

在线性一致的系统中，如果 B1 看到的 x 值为 1，则 C1 看到的值也一定为 1。任何操作在该系统生效的时刻都对应时间轴上的一个点。如果我们把这些时刻连接起来，如下图中紫线所示，则这条线会一直沿时间轴向前，不会反向回跳。所以任何操作都需要互相比较决定，谁发生在前，谁发生在后。例如 B1 发生在 A0 前，C1 发生在 A0 后。而在前面顺序一致性模型中，我们无法比较诸如 B1 和 A0 的先后关系。

顺序一致性

举例说明1

下面的图满足了顺序一致，但不满足线性一致。

• x 和 y 的初始值为 0
• Write(x,4) 代表写入 x=4，Read(y,2) 为读取 y =2

从图上看，进程 P1，P2 的一致性并没有冲突。因为从这两个进程的角度来看，顺序应该是这样的：

Write(y,2), Read(x,0), Write(x,4), Read(y,2)

这个顺序对于两个进程内部的读写顺序都是合理的，只是这个顺序与全局时钟下看到的顺序并不一样。在全局时钟的观点来看，P2 进程对变量 X 的读操作在 P1 进程对变量 X 的写操作之后，然而 P2 读出来的却是旧的数据 0

举例说明2

假设我们有个分布式 KV 系统，以下是四个进程 对其的操作顺序和结果:
-- 表示持续的时间，因为一次写入或者读取，客户端从发起到响应是有时间的，发起早的客户端，不一定拿到数据就早，有可能因为网络延迟反而会更晚。
情况 1：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,1)-   --R(x,2)-
D:                 -R(x,1)-      --R(x,2)--

情况 2：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,2)-   --R(x,1)-
D:                 -R(x,2)-      --R(x,1)--

上面情况 1 和 2 都是满足顺序一致性的，C 和 D 拿的顺序都是 1-2，或 2-1，只要 CD 的顺序一致，就是满足顺序一致性。只是从全局看来，情况 1 更真实，情况 2 就显得” 错误 “了，因为情况 2 是这样的顺序

B W(x,2) -> A W(x,1) -> C R(x,2) -> D R(x,2) -> C R(x,1) -> D R(x,1)

不过一致性不保证正确性，所以这仍然是一个顺序一致。再加一种情况 3：
情况 3：

A: --W(x,1)----------------------
B:  --W(x,2)----------------------
C:                      -R(x,2)-   --R(x,1)-
D:                 -R(x,1)-      --R(x,2)--

情况 3 就不属于顺序一致了，因为 C 和 D 两个进程的读取顺序不同了。

举例说明3

这也是顺序一致的, 但是可能不满足产品经理要求.

从时间轴上可以看到，B0 发生在 A0 之前，读取到的 x 值为 0。B2 发生在 A0 之后，读取到的 x 值为 1。而读操作 B1，C0，C1 与写操作 A0 在时间轴上有重叠，因此他们可能读取到旧的值 0，也可能读取到新的值 1。注意，C1 发生在 B1 之后（二者在时间轴上没有重叠），但是 B1 看到 x 的新值，C1 反而看到的是旧值。即对用户来说，x 的值发生了回跳。

CAP理论

一个分布式系统不可能同时满足以下三个基本需求，最多只能同时满足其中两项:

• 一致性（C：Consistency, CAP的C指的是强一致性）
  在分布式环境下，一致性是指数据在多个副本之间能否保持一致的特性。在一致性的需求下，当一个系统在数据一致的状态下执行更新操作后，应该保证系统的数据仍然处于一致的状态。

  对于一个将数据副本分布在不同分布式节点上的系统来说，如果对第一个节点的数据进行了更新操作并且更新成功后，却没有使得第二个节点上的数据得到相应的更新，于是在对第二个节点的数据进行读取操作时，获取的依然是老数据（或称为脏数据），这就是典型的分布式数据不一致的情况。在分布式系统中，如果能够做到针对一个数据项的更新操作执行成功后，所有的用户都可以读取到其最新的值，那么这样的系统就被认为具有强一致性。

• 可用性（A：Availability）
  可用性是指系统提供的服务必须一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。这里的重点是 “有限时间内” 和 “返回结果”。

  “有限时间内” 是指，对于用户的一个操作请求，系统必须能够在指定的时间内返回对应的处理结果，如果超过了这个时间范围，那么系统就被认为是不可用的。另外，”有限的时间内” 是指系统设计之初就设计好的运行指标，通常不同系统之间有很大的不同，无论如何，对于用户请求，系统必须存在一个合理的响应时间，否则用户便会对系统感到失望。

  “返回结果” 是可用性的另一个非常重要的指标，它要求系统在完成对用户请求的处理后，返回一个正常的响应结果。正常的响应结果通常能够明确地反映出队请求的处理结果，即成功或失败，而不是一个让用户感到困惑的返回结果。

• 分区容错性（P：Partition tolerance）
  系统应该能持续提供服务，即使系统内部有消息丢失（分区）。

  网络分区是指在分布式系统中，不同的节点分布在不同的子网络（机房或异地网络）中，由于一些特殊的原因导致这些子网络出现网络不连通的状况，但各个子网络的内部网络是正常的，从而导致整个系统的网络环境被切分成了若干个孤立的区域。 需要注意的是，组成一个分布式系统的每个节点的加入与退出都可以看作是一个特殊的网络分区。

cap通俗而精准的解释

一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中。这就叫分区。

当你一个数据项只在一个节点中保存，那么分区出现后，和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。

提高分区容忍性的办法就是一个数据项复制到多个节点上，那么出现分区之后，这一数据项就可能分布到各个区里。容忍性就提高了。

然而，要把数据复制到多个节点，就会带来一致性的问题，就是多个节点上面的数据可能是不一致的。要保证一致，每次写操作就都要等待全部节点写成功，而这等待又会带来可用性的问题。总的来说就是，数据存在的节点越多，分区容忍性越高，但要复制更新的数据就越多，一致性就越难保证。为了保证一致性，更新所有节点数据所需要的时间就越长，可用性就会降低。

cap的一些组合例子

既然一个分布式系统无法同时满足一致性、可用性、分区容错性三个特点，所以我们就需要抛弃一个：

需要明确的一点是，对于一个分布式系统而言，分区容错性是一个最基本的要求。因为既然是一个分布式系统，那么分布式系统中的组件必然需要被部署到不同的节点，否则也就无所谓分布式系统了，因此必然出现子网络。而对于分布式系统而言，网络问题又是一个必定会出现的异常情况，因此分区容错性也就成为了一个分布式系统必然需要面对和解决的问题。因此系统架构师往往需要把精力花在如何根据业务特点在 C（一致性）和 A（可用性）之间寻求平衡。

BASE 理论

BASE 是

• Basically Available（基本可用）
• Soft state（软状态, 即中间状态)
• Eventually consistent（最终一致性）

三个短语的缩写。BASE 理论是对 CAP 中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的总结， 是基于 CAP 定理逐步演化而来的。BASE 理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。接下来看一下 BASE 中的三要素：

• 基本可用
  基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。注意，这绝不等价于系统不可用。比如：
  • 响应时间上的损失。正常情况下，一个在线搜索引擎需要在 0.5 秒之内返回给用户相应的查询结果，但由于出现故障，查询结果的响应时间增加了 1~2 秒
  • 系统功能上的损失：正常情况下，在一个电子商务网站上进行购物的时候，消费者几乎能够顺利完成每一笔订单，但是在一些节日大促购物高峰的时候，由于消费者的购物行为激增，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。
• 软状态
  软状态指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。
• 最终一致性
  最终一致性强调的是所有的数据副本，在经过一段时间的同步之后，最终都能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

总的来说，BASE 理论面向的是大型高可用可扩展的分布式系统，和传统的事物 ACID 特性是相反的，它完全不同于 ACID 的强一致性模型，而是通过牺牲强一致性来获得可用性，并允许数据在一段时间内是不一致的，但最终达到一致状态。但同时，在实际的分布式场景中，不同业务单元和组件对数据一致性的要求是不同的，因此在具体的分布式系统架构设计过程中，ACID 特性和 BASE 理论往往又会结合在一起。

服务治理

服务治理主要包括:

• 服务注册发现
• 限流
• 监控
• 网关
• 负载均衡
• 日志采集
• 链路追踪

详细如下图:

分布式锁

主要有:

• etcd/zookeeper(严谨)
• redis(遭到质疑, 极限情况有可能有问题, 但因为性能较高且极限情况不容易发生, 也有人用)

分布式锁过期时间到了但业务没执行完怎么办

注册一个定时任务，每隔一定时间就去延长锁超时时间

基于etcd的分布式锁

因为 etcd 使用 Raft 算法保持了数据的强一致性，某次操作存储到集群中的值必然是全局一致的，所以很容易实现分布式锁。锁服务有两种使用方式，一是保持独占，二是控制时序。

保持独占即所有获取锁的用户最终只有一个可以得到。etcd 为此提供了一套实现分布式锁原子操作 CAS（CompareAndSwap）的 API。通过设置prevExist值，可以保证在多个节点同时去创建某个目录时，只有一个成功。而创建成功的用户就可以认为是获得了锁。

基于redis的分布式锁

• 利用setnx+expire命令 (错误的做法): setnx和expire是分开的两步操作，不具有原子性
• 使用Lua脚本（包含setnx和expire两条指令）
• 使用 set key value [EX seconds][PX milliseconds][NX|XX] 命令 (正确做法, 接下来介绍这种)

Redis 在 2.6.12 版本开始，为 SET 命令增加一系列选项：

SET key value\[EX seconds\]\[PX milliseconds\]\[NX|XX\]

• EX seconds: 设定过期时间，单位为秒
• PX milliseconds: 设定过期时间，单位为毫秒
• NX: 仅当 key 不存在时设置值
• XX: 仅当 key 存在时设置值

value 必须要具有唯一性，我们可以用 UUID 来做，设置随机字符串保证唯一性，至于为什么要保证唯一性？假如 value 不是随机字符串，而是一个固定值，那么就可能存在下面的问题：

1. 客户端 1 获取锁成功
2. 客户端 1 在某个操作上阻塞了太长时间
3. 设置的 key 过期了，锁自动释放了
4. 客户端 2 获取到了对应同一个资源的锁
5. 客户端 1 从阻塞中恢复过来，因为 value 值一样，所以执行释放锁操作时就会释放掉客户端 2 持有的锁，这样就会造成问题

所以通常来说，在释放锁时，我们需要对 value 进行验证

释放锁时需要验证 value 值，也就是说我们在获取锁的时候需要设置一个 value，不能直接用 del key 这种粗暴的方式，因为直接 del key 任何客户端都可以进行解锁了，所以解锁时，我们需要判断锁是否是自己的，基于 value 值来判断, 这里使用 Lua 脚本的方式，尽量保证原子性。

致命缺陷:
使用 set key value [EX seconds][PX milliseconds][NX|XX] 命令 看上去很 OK，实际上在有 Redis 主从结构的时候也会出现问题，比如说 A 客户端在 Redis 的 master 节点上拿到了锁，但是这个加锁的 key 还没有同步到 slave 节点，master 故障，发生故障转移，一个 slave 节点升级为 master 节点，B 客户端也可以获取同个 key 的锁，但客户端 A 也已经拿到锁了，这就导致多个客户端都拿到锁。

RedLock

参考: https://zhuanlan.zhihu.com/p/100140241#RedLock

使用了多个 Redis 实例来实现分布式锁，这是为了保证在发生单点故障时仍然可用。

• 尝试从 N 个互相独立 Redis 实例获取锁；
• 计算获取锁消耗的时间，只有时间小于锁的过期时间，并且从大多数（N / 2 + 1）实例上获取了锁，才认为获取锁成功；
• 如果获取锁失败，就到每个实例上释放锁

分布式锁的高并发优化

先说一个超卖问题的情景, 假设订单系统部署两台机器上，不同的用户都要同时买10台iphone，分别发了一个请求给订单系统。
接着每个订单系统实例都去数据库里查了一下，当前iphone库存是12台。
俩大兄弟一看，乐了，12台库存大于了要买的10台数量啊！
于是乎，每个订单系统实例都发送SQL到数据库里下单，然后扣减了10个库存，其中一个将库存从12台扣减为2台，另外一个将库存从2台扣减为-8台。
现在完了，库存出现了负数！泪奔啊，没有20台iphone发给两个用户啊！这可如何是好。

用分布式锁如何解决库存超卖问题: 只有一个订单系统实例可以成功加分布式锁，然后只有他一个实例可以查库存、判断库存是否充足、下单扣减库存，接着释放锁。
释放锁之后，另外一个订单系统实例才能加锁，接着查库存，一下发现库存只有2台了，库存不足，无法购买，下单失败。不会将库存扣减为-8的。

分布式锁的方案在高并发场景下有什么问题？ 分布式锁一旦加了之后，对同一个商品的下单请求，会导致所有客户端都必须对同一个商品的库存锁key进行加锁。比如，对iphone这个商品的下单，都必对“iphone_stock”这个锁key来加锁。这样会导致对同一个商品的下单请求，就必须串行化，一个接一个的处理,
假设加锁之后，释放锁之前，查库存 -> 创建订单 -> 扣减库存，这个过程性能很高吧，算他全过程20毫秒，这应该不错了。那么1秒是1000毫秒，只能容纳50个对这个商品的请求依次串行完成处理。效率低下.

假如下单时，用分布式锁来防止库存超卖，但是是每秒上千订单的高并发场景，如何对分布式锁进行高并发优化来应对这个场景？
解决方案: 分段加锁

其实说出来也很简单，相信很多人看过java里的ConcurrentHashMap的源码和底层原理，应该知道里面的核心思路，就是分段加锁！

在某些情况下我们可以将锁分解技术进一步扩展为一组独立对象上的锁进行分解，这成为分段锁。其实说的简单一点就是：容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

比如：在ConcurrentHashMap中使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16，其中第N个散列桶由第（N mod 16）个锁来保护。假设使用合理的散列算法使关键字能够均匀的分部，那么这大约能使对锁的请求减少到越来的1/16。也正是这项技术使得ConcurrentHashMap支持多达16个并发的写入线程。

假如你现在iphone有1000个库存，那么你完全可以给拆成20个库存段，要是你愿意，可以在数据库的表里建20个库存字段，比如stock_01，stock_02，类似这样的，也可以在redis之类的地方放20个库存key。
总之，就是把你的1000件库存给他拆开，每个库存段是50件库存，比如stock_01对应50件库存，stock_02对应50件库存。
接着，每秒1000个请求过来了，好！此时其实可以是自己写一个简单的随机算法，每个请求都是随机在20个分段库存里，选择一个进行加锁。
这样就好了，同时可以有最多20个下单请求一起执行，每个下单请求锁了一个库存分段，然后在业务逻辑里面，就对数据库或者是Redis中的那个分段库存进行操作即可，包括查库存 -> 判断库存是否充足 -> 扣减库存。

有一个坑大家一定要注意：如果某个下单请求，咔嚓加锁，然后发现这个分段库存里的库存不足了，此时咋办？
这时你得自动释放锁，然后立马换下一个分段库存，再次尝试加锁后尝试处理。这个过程一定要实现。

分布式事务解决方案(本文这些都不好, 现在一般用Saga)

参考:

• https://www.cnblogs.com/mayundalao/p/11798502.html
• https://zhuanlan.zhihu.com/p/88226625
• https://xiaomi-info.github.io/2020/01/02/distributed-transaction/
• https://zhuanlan.zhihu.com/p/183753774

事务有两种:

• 刚性事务：遵循ACID原则，强一致性。
• 柔性事务：遵循BASE理论，最终一致性；与刚性事务不同，柔性事务允许一定时间内，不同节点的数据不一致，但要求最终一致。

二阶段提交2PC

大致的流程：

• 第一阶段（prepare）：事务管理器向所有本地资源管理器发起请求，询问是否是 ready 状态，所有参与者都将本事务能否成功的信息反馈发给协调者；
• 第二阶段 (commit/rollback)：事务管理器根据所有本地资源管理器的反馈，通知所有本地资源管理器，步调一致地在所有分支上提交或者回滚。

缺点:

• 同步阻塞：当参与事务者存在占用公共资源的情况，其中一个占用了资源，其他事务参与者就只能阻塞等待资源释放，处于阻塞状态。
• 单点故障：一旦事务管理器出现故障，整个系统不可用
• 数据不一致：在阶段二，如果事务管理器只发送了部分 commit 消息，此时网络发生异常，那么只有部分参与者接收到 commit 消息，也就是说只有部分参与者提交了事务，使得系统数据不一致。
• 不确定性：当协事务管理器发送 commit 之后，并且此时只有一个参与者收到了 commit，那么当该参与者与事务管理器同时宕机之后，重新选举的事务管理器无法确定该条消息是否提交成功。

实战:
目前支付宝使用两阶段提交思想实现了分布式事务服务 (Distributed Transaction Service, DTS) ，它是一个分布式事务框架，用来保障在大规模分布式环境下事务的最终一致性。具体可参考支付宝官方文档：https://tech.antfin.com/docs/2/46887

TCC

关于 TCC（Try-Confirm-Cancel）的概念，最早是由 Pat Helland 于 2007 年发表的一篇名为《Life beyond Distributed Transactions:an Apostate’s Opinion》的论文提出。 TCC 事务机制相比于上面介绍的 XA，解决了其几个缺点：

• 解决了协调者单点，由主业务方发起并完成这个业务活动。业务活动管理器也变成多点，引入集群。
• 同步阻塞：引入超时，超时后进行补偿，并且不会锁定整个资源，将资源转换为业务逻辑形式，粒度变小。
• 数据一致性，有了补偿机制之后，由业务活动管理器控制一致性

TCC(Try Confirm Cancel)

1. Try 阶段：尝试执行，完成所有业务检查（一致性）, 预留必须业务资源（准隔离性）
2. Confirm 阶段：确认执行真正执行业务，不作任何业务检查，只使用 Try 阶段预留的业务资源，Confirm 操作满足幂等性。要求具备幂等设计，Confirm 失败后需要进行重试。
3. Cancel 阶段：取消执行，释放 Try 阶段预留的业务资源 Cancel 操作满足幂等性 Cancel 阶段的异常和 Confirm 阶段异常处理方案基本上一致。

在 Try 阶段，是对业务系统进行检查及资源预览，比如订单和存储操作，需要检查库存剩余数量是否够用，并进行预留，预留操作的话就是新建一个可用库存数量字段，Try 阶段操作是对这个可用库存数量进行操作。
基于 TCC 实现分布式事务，会将原来只需要一个接口就可以实现的逻辑拆分为 Try、Confirm、Cancel 三个接口，所以代码实现复杂度相对较高。

缺点:
TCC 需要事务接口提供 try, confirm, cancel 三个接口，提高了编程的复杂性。依赖于业务方来配合提供这样的接口，推行难度大，所以一般不推荐使用这种方式。

实战:
一般来说和钱相关的支付、交易等相关的场景，也可以用TCC，严格严格保证分布式事务要么全部成功，要么全部自动回滚，严格保证资金的正确性!

本地消息表

本地消息表这个方案最初是 ebay 架构师 Dan Pritchett 在 2008 年发表给 ACM 的文章。该方案中会有消息生产者与消费者两个角色，假设系统 A 是消息生产者，系统 B 是消息消费者，其大致流程如下：

1. 当系统 A 被其他系统调用发生数据库表更操作，首先会更新数据库的业务表，其次会往相同数据库的消息表中插入一条数据，两个操作发生在同一个事务中, 如果本步骤发生操作失败, 则直接事务回滚
2. 系统 A 的脚本定期轮询本地消息往 mq 中写入一条消息，如果消息发送失败会进行重试
3. 系统 B 消费 mq 中的消息，并处理业务逻辑。如果本地事务处理失败，会在继续消费 mq 中的消息进行重试，如果业务上的失败，可以通知系统 A 进行回滚操作

本地消息表实现的条件：

• 消费者与生成者的接口都要支持幂等
• 生产者需要额外的创建消息表
• 需要提供补偿逻辑，如果消费者业务失败，需要生产者支持回滚操作

此方案的核心是将需要分布式处理的任务通过消息日志的方式来异步执行。消息日志可以存储到本地文本、数据库或消息队列，再通过业务规则自动或人工发起重试。人工重试更多的是应用于支付场景，通过对账系统对事后问题的处理。

缺点:
最大的问题就在于严重依赖于数据库的消息表来管理事务,这个会导致高并发场景无力,难以扩展,一般很少用

实战:
跨行转账可通过该方案实现。
用户 A 向用户 B 发起转账，首先系统会扣掉用户 A 账户中的金额，将该转账消息写入消息表中，如果事务执行失败则转账失败，如果转账成功，系统中会有定时轮询消息表，往 mq 中写入转账消息，失败重试。mq 消息会被实时消费并往用户 B 中账户增加转账金额，执行失败会不断重试。

小米海外商城用户订单数据状态变更，会将变更状态记录消息表中，脚本将订单状态消息写入 mq，最终消费 mq 给用户发送邮件、短信、push 等。

可靠消息最终一致性

大致流程如下：

1. A 系统先向 mq 发送一条 prepare 消息，如果 prepare 消息发送失败，则直接取消操作
2. 如果消息发送成功，则执行本地事务
3. 如果本地事务执行成功，则向 mq 发送一条 confirm 消息，如果发送失败，则发送回滚消息
4. B 系统定期消费 mq 中的 confirm 消息，执行本地事务，并发送 ack 消息。如果 B 系统中的本地事务失败，会一直不断重试，如果是业务失败，会向 A 系统发起回滚请求
5. mq 会定期轮询所有 prepared 消息调用系统 A 提供的接口查询消息的处理情况，如果该 prepare 消息本地事务处理成功，则重新发送 confirm 消息，否则直接回滚该消息

该方案与本地消息最大的不同是去掉了本地消息表，其次本地消息表依赖消息表重试写入 mq 这一步由本方案中的轮询 prepare 消息状态来重试或者回滚该消息替代。其实现条件与容错方案基本一致。

实战:
目前市面上实现该方案的只有阿里的 RocketMq。

尽最大努力通知

最大努力通知其实就是定期校对, 是最简单的一种柔性事务，适用于一些最终一致性时间敏感度低的业务，且被动方处理结果 不影响主动方的处理结果。

业务活动的主动方，在完成业务处理之后，向业务活动的被动方发送消息，允许消息丢失。主动方可以设置时间阶梯型通知规则，在通知失败后按规则重复通知，直到通知N次后不再通知。主动方提供校对查询接口给被动方按需校对查询，用于恢复丢失的业务消息。业务活动的被动方如果正常接收了数据，就正常返回响应，并结束事务。如果被动方没有正常接收，根据定时策略，向业务活动主动方查询，恢复丢失的业务消息

最大努力通知方案的特点:

• 用到的服务模式：可查询操作、幂等操作。
• 被动方的处理结果不影响主动方的处理结果；适用于对业务最终一致性的时间敏感度低的系统, 比如适合跨企业的系统间的操作，或者企业内部比较独立的系统间的操作，比如银行通知、商户通知等；

这个方案的大致意思就是：

1. 系统 A 本地事务执行完之后，发送个消息到 MQ；
2. 会有个专门消费 MQ 的服务 notify_service(即最大努力通知服务) ，这个服务会消费 MQ 并调用系统 B 的接口；
3. 要是系统 B 执行成功就 ok 了；要是系统 B 执行失败了，那么 notify_service (即最大努力通知服务)就定时尝试重新调用系统 B, 反复 N 次，最后还是不行就放弃。

实战:
小米海外商城目前除了支付回调外，最常用的场景是订单数据同步。例如系统 A、B 进行数据同步，当系统 A 发生订单数据变更，先将数据变更消息写入小米 notify 系统（作用等同 mq），然后 notify 系统异步处理该消息来调用系统 B 提供的接口并进行重试到最大次数。

负载均衡算法有哪些

1. 轮询法
   　　将请求按顺序轮流地分配到后端服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。
2. 随机法
   通过系统的随机算法，根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问。由概率统计理论可以得知，随着客户端调用服务端的次数增多，
   其实际效果越来越接近于平均分配调用量到后端的每一台服务器，也就是轮询的结果。
3. 源地址哈希法
   源地址哈希的思想是根据获取客户端的 IP 地址，通过哈希函数计算得到的一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是客服端要访问服务器的序号。采用源地址哈希法进行负载均衡，同一 IP 地址的客户端，当后端服务器列表不变时，它每次都会映射到同一台后端服务器进行访问。
4. 加权轮询法
   　　不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同。给配置高、负载低的机器配置更高的权重，让其处理更多的请；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好地处理这一问题，并将请求顺序且按照权重分配到后端。加权轮询算法的结果，就是要生成一个服务器序列。每当有请求到来时，就依次从该序列中取出下一个服务器用于处理该请求。比如针对c权重4, b权重2, a权重1的例子，加权轮询算法会生成序列{c, c, b, c, a, b, c}也有可能是{a, a, a, a, a, b, c}, 有可能不均匀, 前五个请求都会分配给服务器a。在Nginx源码中，实现了一种叫做平滑的加权轮询（smooth weighted round-robin balancing）的算法，它生成的序列更加均匀。比如前面的例子，它生成的序列为{ a, a, b, a, c, a, a}，转发给后端a的5个请求现在分散开来，不再是连续的。这样，每收到7个客户端的请求，会把其中的1个转发给后端a，把其中的2个转发给后端b，把其中的4个转发给后端c。收到的第8个请求，重新从该序列的头部开始轮询。
   • 普通加权轮询法
   • 平滑加权轮询法
5. 加权随机法
   与加权轮询法一样，加权随机法也根据后端机器的配置，系统的负载分配不同的权重。不同的是，它是按照权重随机请求后端服务器，而非顺序。
6. 最小连接数法
   最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将负责合理地分流到每一台服务器。

负载均衡的平滑加权轮询算法怎么实现

当我们需要把一份数据发送到一个Set中的任意机器的时候，很容易想到的一个问题是，如何挑Set中的机器作为数据的接收方？显然算法需要符合以下要求：

• 支持加权，以便在机器故障时可以降低其权重
• 在加权的前提下，尽可能地把请求平摊到每台机器上

第一点很好理解，而第二点的意思是，比如说我们现在有a, b, c三个选择，权重分别是5, 1, 1，我们希望输出的结果是类似于a, a, b, a, c, a, a，而不是a, a, a, a, a, b, c。

从Github上面可以看到，Nginx以前也是使用和LVS类似的算法，并在某一次提交中修改为当前的算法，该算法大致思想如下：

Upstream: smooth weighted round-robin balancing.

For edge case weights like { 5, 1, 1 } we now produce { a, a, b, a, c, a, a }
sequence instead of { c, b, a, a, a, a, a } produced previously.

Algorithm is as follows: on each peer selection we increase current_weight
of each eligible peer by its weight, select peer with greatest current_weight
and reduce its current_weight by total number of weight points distributed
among peers.

In case of { 5, 1, 1 } weights this gives the following sequence of
current_weight's:

     a  b  c
     0  0  0  (initial state)

     5  1  1  (a selected)
    -2  1  1

     3  2  2  (a selected)
    -4  2  2

     1  3  3  (b selected)
     1 -4  3

     6 -3  4  (a selected)
    -1 -3  4

     4 -2  5  (c selected)
     4 -2 -2

     9 -1 -1  (a selected)
     2 -1 -1

     7  0  0  (a selected)
     0  0  0

该算法除了有权重weight，还引入了另一个变量current_weight，在每一次遍历中会把current_weight加上weight的值，并选择current_weight最大的元素，对于被选择的元素，再把current_weight减去所有权重之和。

假设有 N 台服务器 S = {S0, S1, S2, …, Sn}，默认权重为 W = {W0, W1, W2, …, Wn}，当前权重为 CW = {CW0, CW1, CW2, …, CWn}。在该算法中有两个权重，默认权重表示服务器的原始权重，当前权重表示每次访问后重新计算的权重，当前权重的出初始值为默认权重值，当前权重值最大的服务器为 maxWeightServer，所有默认权重之和为 weightSum，服务器列表为 serverList，算法可以描述为：

1. 找出当前权重值最大的服务器 maxWeightServer；
2. 计算 {W0, W1, W2, …, Wn} 之和 weightSum；
3. 将 maxWeightServer.CW = maxWeightServer.CW - weightSum；
4. 重新计算 {S0, S1, S2, …, Sn} 的当前权重 CW，计算公式为 Sn.CW = Sn.CW + Sn.Wn
5. 返回 maxWeightServer

服务发现是怎么实现的

参考

我们可以考虑用etcd来做,
服务发现要解决的也是分布式系统中最常见的问题之一，即在同一个分布式集群中的进程或服务，要如何才能找到对方并建立连接。本质上来说，服务发现就是想要了解集群中是否有进程在监听 udp 或 tcp 端口，并且通过名字就可以查找和连接。要解决服务发现的问题，需要有下面三大支柱，缺一不可。

1. 一个强一致性、高可用的服务存储目录。基于 Raft 算法的 etcd 天生就是这样一个强一致性高可用的服务存储目录。
2. 一种提供方的注册服务。提供方可以在 etcd 中注册服务，并且对注册的服务设置key TTL，定时保持服务的心跳以达到监控健康状态的效果, 比如每隔 30s 发送一次心跳设置一下这个key使代表该机器存活的节点继续存在，否则当etcd 没有检测到心跳这个key的ttl到了过期了就会把这个键值对删了
3. 需求方可以即时更新提供方服务状态的机制.需求方通过watch机制监听自己需要用到的提供方信息的改动，提供方相关信息有变动的时候需求方就会收到消息,在接收到信息变动的时候立即从etcd获取相应最新的信息即可, 实现方式通常是这样：不同系统都在 etcd 上对同一个目录进行注册，同时设置 Watcher 观测该目录的变化（如果对子目录的变化也有需要，可以设置递归模式），当某个系统更新了 etcd 的目录，那么设置了 Watcher 的系统就会收到通知，并作出相应处理。
   
   

下面我们来看服务发现对应的具体场景。
微服务协同工作架构中，服务动态添加。随着 Docker 容器的流行，多种微服务共同协作，构成一个相对功能强大的架构的案例越来越多。透明化的动态添加这些服务的需求也日益强烈。通过服务发现机制，在 etcd 中注册某个服务名字的目录，在该目录下存储可用的服务节点的 IP。在使用服务的过程中，只要从服务目录下查找可用的服务节点去使用即可。

熔断是怎么实现的

什么是服务熔断呢？ 服务熔断：当下游的服务因为某种原因突然变得不可用或响应过慢，上游服务为了保证自己整体服务的可用性，不再继续调用目标服务，直接返回，快速释放资源。如果目标服务情况好转则恢复调用。 需要说明的是熔断其实是一个框架级的处理，那么这套熔断机制的设计，基本上业内用的是断路器模式:

• 最开始处于closed状态，一旦检测到错误到达一定阈值，便转为open状态；
• 这时候会有个 reset timeout，到了这个时间了，会转移到half open状态；
• 尝试放行一部分请求到后端，一旦检测成功便回归到closed状态，即恢复服务；

业内目前流行的熔断器很多，例如阿里出的 Sentinel, 以及最多人使用的 Hystrix 在 Hystrix 中，对应配置如下

//滑动窗口的大小，默认为20
circuitBreaker.requestVolumeThreshold 
//过多长时间，熔断器再次检测是否开启，默认为5000，即5s钟
circuitBreaker.sleepWindowInMilliseconds 
//错误率，默认50%
circuitBreaker.errorThresholdPercentage

每当 20 个请求中，有 50% 失败时，熔断器就会打开，此时再调用此服务，将会直接返回失败，不再调远程服务。直到 5s 钟之后，重新检测该触发条件，判断是否把熔断器关闭，或者继续打开。
这些属于框架层级的实现，我们只要实现对应接口就好！

服务降级

• 降级的本质:
  • 降级就是为了解决资源不足和访问量增加的矛盾
  • 在有限的资源情况下，为了能抗住大量的请求，就需要对系统做出一些牺牲，有点“弃卒保帅”的意思。放弃一些功能，保证整个系统能平稳运行
• 降级牺牲的是:
  • 强强一致性变成最终一致性
    • 大多数的系统是不需要强一致性的。
    • 强一致性就要求多种资源的占用，减少强一致性就能释放更多资源
    • 这也是我们一般利用消息中间件来削峰填谷，变强一致性为最终一致性，也能达到效果
  • 干掉一些次要功能
    • 停止访问不重要的功能，从而释放出更多的资源
    • 举例来说，比如电商网站，评论功能流量大的时候就能停掉，当然能不直接干掉就别直接，最好能简化流程或者限流最好简化功能流程。把一些功能简化掉
• 降级的注意点:
  • 对业务进行仔细的梳理和分析
    • 哪些是核心流程必须保证的，哪些是可以牺牲的
  • 什么指标下能进行降级
    • 吞吐量、响应时间、失败次数等达到一个阈值才进行降级处理
• 如何降级:
  • 降级最简单的就是在业务代码中配置一个开关或者做成配置中心模式，直接在配置中心上更改配置，推送到相应的服务。

限流

限流就是通过对并发访问进行限速。限流的实现方式:

• 计数器:
  最简单的实现方式 ，维护一个计数器，来一个请求计数加一，达到阈值时，直接拒绝请求。
  一般实践中用 ngnix + lua + redis 这种方式，redis 存计数值
• 漏斗模式:
  流量就像进入漏斗中的水一样，而出去的水和我们系统处理的请求一样，当流量大于漏斗的流出速度，就会出现积水，水多了会溢出,
  漏斗很多是用一个队列实现的，当流量过多时，队列会出现积压，队列满了，则开始拒绝请求。
• 令牌桶:
  看图例，令牌通和漏斗模式很像，主要的区别是增加了一个中间人，这个中间人按照一定的速率放入一些token，然后，处理请求时，需要先拿到token才能处理，如果桶里没有token可以获取，则不进行处理。

熔断-降级-限流三者的关系

• 熔断强调的是服务之间的调用能实现自我恢复的状态；
• 限流是从系统的流量入口考虑，从进入的流量上进行限制，达到保护系统的作用；
• 降级，是从系统内部的平级服务或者业务的维度考虑，流量大了，可以干掉一些，保护其他正常使用；

熔断是降级方式的一种；
降级又是限流的一种方式；
三者都是为了通过一定的方式去保护流量过大时，保护系统的手段。

id生成器如何实现全局递增

参考

介绍一下美团在用的工业级 Leaf-snowflake 方案。

• 41-bit的时间是毫秒级时间, 可以表示(1L<<41)/(1000L*3600*24*365)=69年的时间，
• 10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。
• 12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s，

• 这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的

• 优点：

  • 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
  • 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
  • 可以根据自身业务特性分配bit位，非常灵活。
• 缺点：强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

解决时钟回拨问题

解决方案:

• 由于强依赖时钟，对时间的要求比较敏感，在机器工作时 NTP 同步也会造成秒级别的回退，建议可以直接关闭 NTP 同步。
• 在时钟回拨的时候直接不提供服务直接返回 ERROR_CODE，等时钟追上即可
• 偏差在5秒之内, 比如就等待2倍的偏差时间(比如比上次的还小3秒, 那我就等6秒)。然后做一层重试, 如果还是小于上次的时间, 就上报报警系统
• 更或者是发现有时钟回拨之后自动摘除本身节点并报警

代码如下：

//发生了回拨，此刻时间小于上次发号时间
if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
          //时间偏差大小小于5ms，则等待两倍时间
            wait(offset << 1);//wait
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                //还是小于，抛异常并上报
                throwClockBackwardsEx(timestamp);
              }    
        } catch (InterruptedException e) {  
            throw  e;
        }
    } else {
        //throw
        throwClockBackwardsEx(timestamp);
    }
}
 //分配ID

从上线情况来看，在 2017 年闰秒出现那一次出现过部分机器回拨，由于 Leaf-snowflake 的策略保证，成功避免了对业务造成的影响。
Leaf 在美团点评公司内部服务包含金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。目前 Leaf 的性能在 4C8G 的机器上 QPS 能压测到近 5w/s，TP999 1ms，已经能够满足大部分的业务的需求。每天提供亿数量级的调用量，作为公司内部公共的基础技术设施，必须保证高 SLA 和高性能的服务，我们目前还仅仅达到了及格线，还有很多提高的空间。

C++

参考: 看之前一个哥们总结的c++要点 https://interview.huihut.com/

• new 和 delete 为什么要配对用:

  • class A{ //... }; A *pa = new A(); A *pas = new A[NUM]();

  • delete []pas; //详细流程: delete[] pas 用来释放pas指向的内存！！还逐一调用数组中每个对象的destructor！！

  • delete []pa; //会发生什么, 答案是调用未知次数的A的析构函数. 因为delete[]会去通过pa+offset找一个基于pa的偏移量找一个内存里的数据, 他假定这个内存里放了要调用析构的次数n这个数据, 而这个内存里到底是多少是未知的.
  • delete pas; //哪些指针会变成野指针, 答案是pas和A[0]中的指针会变成野指针. 因为只有这两个指针指向的内存被释放了, 也就是说, 仅释放了pas指针指向的这个数组的全部内存空间, 以及只调用了a[0]对象的析构函数
• cqq vec set map list
  • vector和string的内存分配与使用注意点
  • stl关联容器的特性
• map的[]和insert的区别?
  • insert 含义是：如果key存在，则插入失败，如果key不存在，就创建这个key－value。实例: map.insert((key, value))
  • 利用下标操作的含义是：如果这个key存在，就更新value；如果key不存在，就创建这个key－value对 实例：map[key] = value
• vector的resize和reserve的区别?
  • 总结:
    • resize既分配了空间，也创建了对象，可以通过下标访问。当new_size大于原size, 则resize既修改capacity大小，也修改size大小。否则只修改size大小.
    • reserve只分配了空间, 也就是说它只修改capacity大小，不修改size大小, 若 new_cap 小于等于当前的 capacity(), 它啥也不干.
  • resize: 重设容器大小以容纳 count 个元素。
    若当前大小大于 count ，则减小容器为其首 count 个元素。
    若当前大小小于 count:
    • 则后附额外的默认插入的元素
    • 则后附额外的 value 的副本
  • reserve: 增加 vector 的容量到大于或等于 new_cap 的值。若 new_cap 大于当前的 capacity() ，则分配新存储，否则该方法不做任何事。reserve() 不更改 vector 的 size 。若 new_cap 大于 capacity() ，则所有迭代器，包含尾后迭代器和所有到元素的引用都被非法化。否则，没有迭代器或引用被非法化。
• 字节对齐
  • 对象模型之内存对齐基础

• 定位new

  • #include <iostream> using namespace std; int main() { char buffer[512]; //chunk of memory内存池 int *p2, *p3; //定位new: p2 = new (buffer) int[10]; p2[0] = 99; p2[1] = 88; cout << "buffer = " <<(void *)buffer << endl; //内存池地址 cout << "p2 = " << p2 << endl; //定位new指向的地址 cout << "p2[0] = " << p2[0] << endl; p3 = new (buffer) int[2]; p3[0] = 1; p3[1] = 2; cout << "p3 = " << p3 << endl; cout << "p2[0] = " << p2[0] << endl; cout << "p2[1] = " << p2[1] << endl; cout << "p2[2] = " << p2[2] << endl; cout << "p2[3] = " << p2[3] << endl; return 0; }

    结果发现p3和p2还有buffer都是使用同样的内存地址，符合指定地址的内存块，而且p3在指定位置覆盖了p2的前两处的值。

• c++一个空类会生成什么 (答: 默认构造/析构(非虚)/赋值运算符/默认拷贝/取地址/const取地址)

• 虚函数（virtual）可以是内联函数（inline）吗？

  • 虚函数可以是内联函数，内联是可以修饰虚函数的，但是当虚函数表现多态性的时候不能内联。
  • 内联是在编译器建议编译器内联，而虚函数的多态性在运行期，编译器无法知道运行期调用哪个代码，因此虚函数表现为多态性时（运行期）不可以内联。
  • inline virtual 唯一可以内联的时候是：编译器知道所调用的对象是哪个类（如 Base::who()），这只有在编译器具有实际对象而不是对象的指针或引用时才会发生。
    虚函数内联使用:

    // 此处的虚函数 who()，是通过类（Base）的具体对象（b）来调用的， // 编译期间就能确定了，所以它可以是内联的， // 但最终是否内联取决于编译器。 Base b; b.who(); // 此处的虚函数是通过指针调用的，呈现多态性， // 需要在运行时期间才能确定，所以不能为内联。 Base *ptr = new Derived(); ptr->who();

• 虚函数指针、虚函数表

  • 虚函数指针：在含有虚函数类的对象中，指向虚函数表，在运行时确定。
  • 虚函数表：在程序内存的只读数据段（.rodata section，见：CPP目标文件内存布局），存放虚函数指针，如果派生类实现了基类的某个虚函数，则在虚表中覆盖原本基类的那个虚函数指针，在编译时根据类的声明创建。
  • virtual修饰符:
    如果一个类是局部变量则该类数据存储在栈区，如果一个类是通过new/malloc动态申请的，则该类数据存储在堆区。
    如果该类是virutal继承而来的子类，则该类的虚函数表指针和该类其他成员一起存储。虚函数表指针指向只读数据段中的类虚函数表，虚函数表中存放着一个个函数指针，函数指针指向代码段中的具体函数。
  • 

• 内存泄漏的工具 vargrid..? 还有啥工具

• 了解ASAN查找内存越界问题
• cpp找找冰川, 大梦龙图的面试题，网上常用题
• gdb怎么切换线程
• C++ 的动态多态怎么实现的？
• C++ 的构造函数可以是虚函数吗？
• 无锁队列原理是否一定比有锁快?(不一定, 如果临界区小因为有上下文切换则mutex慢, 再来看lockfree的spin，一般都遵循一个固定的格式：先把一个不变的值X存到某个局部变量A里，然后做一些计算，计算/生成一个新的对象，然后做一个CAS操作，判断A和X还是不是相等的，如果是，那么这次CAS就算成功了，否则再来一遍。如果上面这个loop里面“计算/生成一个新的对象”非常耗时并且contention很严重，那么lockfree性能有时会比mutex差。另外lockfree不断地spin引起的CPU同步cacheline的开销也比mutex版本的大。关于ABA问题)

编译过程

1. 预处理(Preprocessing): 做一些类似于将所有的#define删除，并且展开所有的宏定义的操作, 然后生成hello.i
2. 编译(Compilation): 编译过程就是把预处理完的文件进行一系列的词法分析，语法分析，语义分析及优化后生成相应的汇编代码。得到hello.a
3. 汇编(Assembly): 汇编器是将汇编代码转变成机器可以执行的命令，每一个汇编语句几乎都对应一条机器指令。汇编相对于编译过程比较简单，根据汇编指令和机器指令的对照表一一翻译即可。得到hello.o
4. 链接(Linking): 通过调用链接器ld来链接程序运行需要的一大堆目标文件，以及所依赖的其它库文件，最后生成可执行文件
   • 静态链接: 指在编译阶段直接把静态库加入到可执行文件中去，这样可执行文件会比较大
   • 动态链接: 指链接阶段仅仅只加入一些描述信息，而程序执行时再从系统中把相应动态库加载到内存中去。

目标文件

编译器编译源代码后生成的文件叫做目标文件。目标文件从结构上讲，它是已经编译后的可执行文件格式，只是还没有经过链接的过程，其中可能有些符号或有些地址还没有被调整。

可执行文件（Windows 的 .exe 和 Linux 的 ELF）、动态链接库（Windows 的 .dll 和 Linux 的 .so）、静态链接库（Windows 的 .lib 和 Linux 的 .a）都是按照可执行文件格式存储（Windows 按照 PE-COFF，Linux 按照 ELF）

目标文件格式:

• Windows 的 PE（Portable Executable），或称为 PE-COFF，.obj 格式
• Linux 的 ELF（Executable Linkable Format），.o 格式
• Intel/Microsoft 的 OMF（Object Module Format）
• Unix 的 a.out 格式
• MS-DOS 的 .COM 格式

PE 和 ELF 都是 COFF（Common File Format）的变种

CPP目标文件内存布局

Linux内存管理

为什么需要虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

MMU工作原理

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分:

• 一部分存储页面号，
• 一部分存储偏移量。

上图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。

主机字节序

主机字节序又叫 CPU 字节序，其不是由操作系统决定的，而是由 CPU 指令集架构决定的。主机字节序分为两种：

• 记忆技巧: 低序地址存了高序字节就叫大端, 反之就小端
• 大端字节序（Big Endian）：高序字节存储在低位地址，低序字节存储在高位地址, 目前主要是ARM/PowerPC在用
• 小端字节序（Little Endian）：低序字节存储在低位地址, 高序字节存储在高位地址，目前主要是Intel在用

存储方式:
32 位整数 0x12345678 是从起始位置为 0x00 的地址开始存放，则：

网络字节序

网络字节顺序是 TCP/IP 中规定好的一种数据表示格式，它与具体的 CPU 类型、操作系统等无关，从而可以保证数据在不同主机之间传输时能够被正确解释。

网络字节顺序采用：大端（Big Endian）排列方式。

Linux虚拟地址空间如何分布

Linux 使用虚拟地址空间，大大增加了进程的寻址空间，由低地址到高地址(下图中从下到上即为从低到高)分别为(口诀: 文初堆栈)：

• 文本段(只读段)：该部分空间只能读，不可写；(包括：代码段、rodata 段(C常量字符串和#define定义的常量) )
• 数据段(初始化数据段与未初始化数据段)：保存初始化了的与未初始化的全局变量、静态变量的空间；
• 堆 ：就是平时所说的动态内存， malloc/new 大部分都来源于此。其中堆顶的位置可通过函数 brk 和 sbrk 进行动态调整。
• 文件映射区域 ：如动态库、共享内存等映射物理空间的内存，一般是 mmap 函数所分配的虚拟地址空间。
• 栈：用于维护函数调用的上下文空间，一般为 8M ，可通过 ulimit –s 查看。
• 内核虚拟空间：用户代码不可见的内存区域，由内核管理(页表就存放在内核虚拟空间)。上图是 32 位系统典型的虚拟地址空间分布(来自《深入理解计算机系统》)。

brk函数

先了解：brk()和sbrk()函数

int brk( const void *addr )
void* sbrk ( intptr_t incr );

这两个函数的作用主要是扩展heap的上界brk。第一个函数的参数为设置的新的brk上界地址，如果成功返回0，失败返回-1。第二个函数的参数为需要申请的内存的大小，然后返回heap新的上界brk地址。如果sbrk的参数为0，则返回的为原来的brk地址。

mmap

虚拟内存系统通过将虚拟内存分割为称作虚拟页 (Virtual Page，VP) 大小固定的块，一般情况下，每个虚拟页的大小默认是 4096 字节。同样的，物理内存也被分割为物理页(Physical Page，PP)，也为 4096 字节。

在 LINUX 中我们可以使用 mmap 用来在进程虚拟内存地址空间中分配地址空间，创建和物理内存的映射关系。

映射关系可以分为两种

1. 文件映射
   磁盘文件映射进程的虚拟地址空间，使用文件内容初始化物理内存。
2. 匿名映射
   初始化全为 0 的内存空间。

而对于映射关系是否共享又分为

1. 私有映射 (MAP_PRIVATE)
   多进程间数据共享，修改不反应到磁盘实际文件，是一个 copy-on-write（写时复制）的映射方式。
2. 共享映射 (MAP_SHARED)
   多进程间数据共享，修改反应到磁盘实际文件中。

因此总结起来有 4 种组合

1. 私有文件映射
   多个进程使用同样的物理内存页进行初始化，但是各个进程对内存文件的修改不会共享，也不会反应到物理文件中
2. 私有匿名映射
   mmap 会创建一个新的映射，各个进程不共享，这种使用主要用于分配内存 (malloc 分配大内存会调用 mmap)。
   例如开辟新进程时，会为每个进程分配虚拟的地址空间，这些虚拟地址映射的物理内存空间各个进程间读的时候共享，写的时候会 copy-on-write。
3. 共享文件映射
   多个进程通过虚拟内存技术共享同样的物理内存空间，对内存文件 的修改会反应到实际物理文件中，他也是进程间通信 (IPC) 的一种机制。
4. 共享匿名映射
   这种机制在进行 fork 的时候不会采用写时复制，父子进程完全共享同样的物理内存页，这也就实现了父子进程通信 (IPC).

这里值得注意的是，mmap 只是在虚拟内存分配了地址空间，只有在第一次访问虚拟内存的时候才分配物理内存。
在 mmap 之后，并没有在将文件内容加载到物理页上，只上在虚拟内存中分配了地址空间。当进程在访问这段地址时，通过查找页表，发现虚拟内存对应的页没有在物理内存中缓存，则产生 “缺页”，由内核的缺页异常处理程序处理，将文件对应内容，以页为单位 (4096) 加载到物理内存，注意是只加载缺页，但也会受操作系统一些调度策略影响，加载的比所需的多。

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

这里要注意的是fd参数，fd为映射的文件描述符，如果是匿名映射，可以设为-1；

• mmap函数第一种用法是映射磁盘文件到内存中；而malloc使用的是mmap函数的第二种用法，即匿名映射，匿名映射不映射磁盘文件，而是向映射区申请一块内存。
• munmap函数是用于释放内存，第一个参数为内存首地址，第二个参数为内存的长度。接下来看下mmap函数的参数。

由于brk/sbrk/mmap属于系统调用，如果每次申请内存，都调用这三个函数中的一个，那么每次都要产生系统调用开销（即cpu从用户态切换到内核态的上下文切换，这里要保存用户态数据，等会还要切换回用户态），这是非常影响性能的；其次，这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果低地址的内存没有被释放，高地址的内存就不能被回收。

malloc和free原理

malloc:

• 当申请小内存的时，malloc使用sbrk分配内存
• 当申请大内存时，使用mmap函数申请内存
• 但是这只是分配了虚拟内存，还没有映射到物理内存，当访问申请的内存时，才会因为缺页异常，内核分配物理内存。
• 将所有空闲内存块连成链表，每个节点记录空闲内存块的地址、大小等信息
• 分配内存时，找到大小合适的块，切成两份，一分给用户，一份放回空闲链表
• free时，直接把内存块返回链表
• 解决外部碎片：将能够合并的内存块进行合并

malloc函数的实质体现在：它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到连接表上。

这里注意，malloc找到的内存块大小一定是会大于等于我们需要的内存大小，下面会提到如果所有的内存块都比要求的小会怎么办？

调用free函数时，它将用户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的小内存片段，如果这时用户申请一个大的内存片段，那么空闲链上可能没有可以满足用户要求的片段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空闲块合并成较大的内存块。

在对内存块进行了 free 调用之后，我们需要做的是诸如将它们标记为未被使用的等事情，并且，在调用 malloc 时，我们要能够定位未被使用的内存块。因此， malloc返回的每块内存的起始处首先要有这个结构：

这就解释了，为什么在程序中free之后，但是堆的内存还是没有释放。

内存控制块结构定义

struct mem_control_block {
    int is_available;
    int size;
};

现在，您可能会认为当程序调用 malloc 时这会引发问题 —— 它们如何知道这个结构？答案是它们不必知道；在返回指针之前，我们会将其移动到这个结构之后，把它隐藏起来。这使得返回的指针指向没有用于任何其他用途的内存。那样，从调用程序的角度来看，它们所得到的全部是空闲的、开放的内存。然后，当通过 free() 将该指针传递回来时，我们只需要倒退几个内存字节就可以再次找到这个结构。

关于 malloc 获得虚存空间的实现，与 glibc 的版本有关，但大体逻辑是：

• 若分配内存小于 128k ，调用 sbrk() ，将堆顶指针向高地址移动，获得新的虚存空间。
• 若分配内存大于 128k ，调用 mmap() ，在文件映射区域中分配匿名虚存空间。

接着： VSZ为虚拟内存 RSS为物理内存

• VSZ 并不是每次 malloc 后都增长，是与上一节说的堆顶没发生变化有关，因为可重用堆顶内剩余的空间，这样的 malloc 是很轻量快速的。
• 但如果 VSZ 发生变化，基本与分配内存量相当，因为 VSZ 是计算虚拟地址空间总大小。
• RSS 的增量很少，是因为 malloc 分配的内存并不就马上分配实际存储空间，只有第一次使用，如第一次 memset 后才会分配。
• 由于每个物理内存页面大小是 4k ，不管 memset 其中的 1k 还是 5k 、 7k ，实际占用物理内存总是 4k 的倍数。所以 RSS 的增量总是 4k 的倍数。
• 因此，不是 malloc 后就马上占用实际内存，而是第一次使用时发现虚存对应的物理页面未分配，产生缺页中断，才真正分配物理页面，同时更新进程页面的映射关系。这也是 Linux 虚拟内存管理的核心概念之一。

vmalloc和kmalloc和malloc的区别

• kmalloc和vmalloc是分配的是内核的内存,malloc分配的是用户的内存
• kmalloc保证分配的内存在物理上是连续的,vmalloc保证的是在虚拟地址空间上的连续,malloc不保证任何东西(这点是自己猜测的,不一定正确)
• kmalloc能分配的大小有限,vmalloc和malloc能分配的大小相对较大
• 内存只有在要被DMA访问的时候才需要物理上连续
• vmalloc比kmalloc要慢

对于提供了MMU（存储管理器，辅助操作系统进行内存管理，提供虚实地址转换等硬件支持）的处理器而言，Linux提供了复杂的存储管理系统，使得进程所能访问的内存达到4GB。

进程的4GB内存空间被人为的分为两个部分–用户空间与内核空间。用户空间地址分布从0到3GB(PAGE_OFFSET，在0x86中它等于0xC0000000)，3GB到4GB为内核空间。

内核空间中，从3G到vmalloc_start这段地址是物理内存映射区域（该区域中包含了内核镜像、物理页框表mem_map等等），比如我们使用 的 VMware虚拟系统内存是160M，那么3G～3G+160M这片内存就应该映射物理内存。在物理内存映射区之后，就是vmalloc区域。对于 160M的系统而言，vmalloc_start位置应在3G+160M附近（在物理内存映射区与vmalloc_start期间还存在一个8M的gap 来防止跃界），vmalloc_end的位置接近4G(最后位置系统会保留一片128k大小的区域用于专用页面映射)

一般情况下，只有硬件设备才需要物理地址连续的内存，因为硬件设备往往存在于MMU之外，根本不了解虚拟地址；但为了性能上的考虑，内核中一般使用kmalloc(),而只有在需要获得大块内存时才使用vmalloc，例如当模块被动态加载到内核当中时，就把模块装载到由vmalloc（）分配的内存上。

• kmalloc:
  kmalloc申请的是较小的连续的物理内存，内存物理地址上连续，虚拟地址上也是连续的，使用的是内存分配器slab的一小片。申请的内存位于物理内存的映射区域。其真正的物理地址只相差一个固定的偏移。而且不对获得空间清零。可以查看slab分配器
• kzalloc:
  用kzalloc申请内存的时候， 效果等同于先是用 kmalloc() 申请空间 , 然后用 memset() 来初始化 ,所有申请的元素都被初始化为 0.
• vmalloc:
  vmalloc用于申请较大的内存空间，虚拟内存是连续。申请的内存的则位于vmalloc_start～vmalloc_end之间，与物理地址没有简单的转换关系，虽然在逻辑上它们也是连续的，但是在物理上它们不要求连续。
• malloc:
  malloc分配的是用户的内存。除非被阻塞否则他执行的速度非常快，而且不对获得空间清零。

Buddy（伙伴）分配算法

参考: https://zhuanlan.zhihu.com/p/149581303

伙伴系统用于管理物理页，主要目的在于维护可用的连续物理空间，避免外部碎片。所有关于内存分配的操作都会与其打交道，buddy是物理内存的管理的门户

Linux 内核引入了伙伴系统算法（Buddy system），什么意思呢？就是把相同大小的页框块用链表串起来，页框块就像手拉手的好伙伴，也是这个算法名字的由来。

具体的，所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。

伙伴系统:
因为任何正整数都可以由 2^n 的和组成，所以总能找到合适大小的内存块分配出去，减少了外部碎片产生 。

分配实例:
比如：我需要申请4个页框，但是长度为4个连续页框块链表没有空闲的页框块，伙伴系统会从连续8个页框块的链表获取一个，并将其拆分为两个连续4个页框块，取其中一个，另外一个放入连续4个页框块的空闲链表中。释放的时候会检查，释放的这几个页框前后的页框是否空闲，能否组成下一级长度的块。

Slab分配器

伙伴系统和slab不是二选一的关系，slab 内存分配器是对伙伴分配算法的补充

slab的目的在于避免内部碎片。从buddy系统获取的内存至少是一个页，也就是4K，如果仅仅需要8字节的内存，显然巨大的内部碎片无法容忍。

slab从buddy系统申请空间，将较大的连续内存拆分成一系列较小的内存块。

用户申请空间时从slab中获取大小最相近的小块内存，这样可以有效减少内部碎片。在slab最大的块为8K，slab中所有块在物理上也是连续的。

上面说的用于内存分配的slab是通用的slab，主要用于支持kmalloc分配内存。

slab还有一个作用就是用作对象池，针对经常分配和回收的对象比如task_struct，可以分配一个slab对象池对其优化。这种slab是独立于通用的内存分配slab的，在内核中有很多这样的针对特定对象的slab。

在内核中想要分配一段连续的内存，首先向slab系统申请，如果不满足（超过两个页面，也就是8K），直接向buddy系统申请。如果还不满足（超过4M，也就是1024个页面），将无法获取到连续的物理地址。可以通过vmalloc获取虚拟地址空间连续，但物理地址不连续的更大的内存空间。

malloc是用户态使用的内存分配接口，最终还是向buddy申请内存，因为buddy系统是管理物理内存的门户。申请到大块内存后，再像slab一样对其进行细分维护，根据用户需要返回相应内存的指针。

fork内存语义

• 共享代码段, 子指向父 : 父子进程共享同一代码段, 子进程的页表项指向父进程相同的物理内存页(即数据段/堆段/栈段的各页)
• 写时复制(copy-on-write) : 内核会捕获所有父进程或子进程针对这些页面(即数据段/堆段/栈段的各页)的修改企图, 并为将要修改的页面创建拷贝, 将新的页面拷贝分配给遭内核捕获的进程, 从此父/子进程可以分别修改各自的页拷贝, 不再相互影响.

虽然fork创建的子进程不需要拷贝父进程的物理内存空间, 但是会复制父进程的空间内存页表. 例如对于10GB的redis进程, 需要复制约20MB的内存页表, 因为此fork操作耗时跟进程总内存量息息相关

零拷贝

参考 https://juejin.im/post/6844903949359644680

“先从简单开始，实现下这个场景：从一个文件中读出数据并将数据传到另一台服务器上？”
大概伪代码如下:

File.read(file, buf, len);
Socket.send(socket, buf, len);

可以看出, 这样效率是很低的.

下图分别对应传统 I/O 操作的数据读写流程，整个过程涉及 2 次 CPU 拷贝、2 次 DMA 拷贝总共 4 次拷贝，以及 4 次上下文切换，下面简单地阐述一下相关的概念。

• 上下文切换：当用户程序向内核发起系统调用时，CPU 将用户进程从用户态切换到内核态；当系统调用返回时，CPU 将用户进程从内核态切换回用户态。
• CPU拷贝：由 CPU 直接处理数据的传送，数据拷贝时会一直占用 CPU 的资源。
• DMA拷贝：由 CPU 向DMA磁盘控制器下达指令，让 DMA 控制器来处理数据的传送，数据传送完毕再把信息反馈给 CPU，从而减轻了 CPU 资源的占有率。

传统读操作

当应用程序执行 read 系统调用读取一块数据的时候，如果这块数据已经存在于用户进程的页内存中，就直接从内存中读取数据；如果数据不存在，则先将数据从磁盘加载数据到内核空间的读缓存（read buffer）中，再从读缓存拷贝到用户进程的页内存中。

read(file_fd, tmp_buf, len);

复制代码基于传统的 I/O 读取方式，read 系统调用会触发 2 次上下文切换，1 次 DMA 拷贝和 1 次 CPU 拷贝，发起数据读取的流程如下：

1. 用户进程通过 read() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
2. CPU利用DMA控制器将数据从主存或硬盘拷贝到内核空间（kernel space）的读缓冲区（read buffer）。
3. CPU将读缓冲区（read buffer）中的数据拷贝到用户空间（user space）的用户缓冲区（user buffer）。
4. 上下文从内核态（kernel space）切换回用户态（user space），read 调用执行返回。

传统写操作

当应用程序准备好数据，执行 write 系统调用发送网络数据时，先将数据从用户空间的页缓存拷贝到内核空间的网络缓冲区（socket buffer）中，然后再将写缓存中的数据拷贝到网卡设备完成数据发送。

write(socket_fd, tmp_buf, len);

复制代码基于传统的 I/O 写入方式，write() 系统调用会触发 2 次上下文切换，1 次 CPU 拷贝和 1 次 DMA 拷贝，用户程序发送网络数据的流程如下：

1. 用户进程通过 write() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
2. CPU 将用户缓冲区（user buffer）中的数据拷贝到内核空间（kernel space）的网络缓冲区（socket buffer）。
3. CPU 利用 DMA 控制器将数据从网络缓冲区（socket buffer）拷贝到网卡进行数据传输。
4. 上下文从内核态（kernel space）切换回用户态（user space），write 系统调用执行返回。

sendfile

sendfile 系统调用在 Linux 内核版本 2.1 中被引入，目的是简化通过网络在两个通道之间进行的数据传输过程。sendfile 系统调用的引入，不仅减少了 CPU 拷贝的次数，还减少了上下文切换的次数，它的伪代码如下：

sendfile(socket_fd, file_fd, len);

复制代码通过 sendfile 系统调用，数据可以直接在内核空间内部进行 I/O 传输，从而省去了数据在用户空间和内核空间之间的来回拷贝。与 mmap 内存映射方式不同的是， sendfile 调用中 I/O 数据对用户空间是完全不可见的。也就是说，这是一次完全意义上的数据传输过程。

基于 sendfile 系统调用的零拷贝方式，整个拷贝过程会发生 2 次上下文切换，1 次 CPU 拷贝和 2 次 DMA 拷贝，用户程序读写数据的流程如下：

1. 用户进程通过 sendfile() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
2. CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间（kernel space）的读缓冲区（read buffer）。
3. CPU 将读缓冲区（read buffer）中的数据拷贝到的网络缓冲区（socket buffer）。
4. CPU 利用 DMA 控制器将数据从网络缓冲区（socket buffer）拷贝到网卡进行数据传输。
5. 上下文从内核态（kernel space）切换回用户态（user space），sendfile 系统调用执行返回。

相比较于 mmap 内存映射的方式，sendfile 少了 2 次上下文切换，但是仍然有 1 次 CPU 拷贝操作。sendfile 存在的问题是用户程序不能对数据进行修改，而只是单纯地完成了一次数据传输过程。

“这样确实改善了很多，但还没达到零拷贝的要求（还有一次cpu参与的拷贝），还有其它黑技术？”
“对的，如果底层网络接口卡支持收集(gather)操作的话，就可以进一步的优化。”
“怎么说？”
“继续看下一小节”

sendfile + DMA gather copy

Linux 2.4 版本的内核对 sendfile 系统调用进行修改，如果底层网络接口卡支持收集(gather)操作的话, 为 DMA 拷贝引入了 gather 操作。它将内核空间（kernel space）的读缓冲区（read buffer）中对应的数据描述信息（内存地址、地址偏移量）记录到相应的网络缓冲区（ socket buffer）中，由 DMA 根据内存地址、地址偏移量将数据批量地从读缓冲区（read buffer）拷贝到网卡设备中，这样就省去了内核空间中仅剩的 1 次 CPU 拷贝操作，sendfile 的伪代码如下：

sendfile(socket_fd, file_fd, len);

复制代码在硬件的支持下，sendfile 拷贝方式不再从内核缓冲区的数据拷贝到 socket 缓冲区，取而代之的仅仅是缓冲区文件描述符和数据长度的拷贝，这样 DMA 引擎直接利用 gather 操作将页缓存中数据打包发送到网络中即可，本质就是和虚拟内存映射的思路类似。

基于 sendfile + DMA gather copy 系统调用的零拷贝方式，整个拷贝过程会发生 2 次上下文切换、0 次 CPU 拷贝以及 2 次 DMA 拷贝，用户程序读写数据的流程如下：

1. 用户进程通过 sendfile() 函数向内核（kernel）发起系统调用，上下文从用户态（user space）切换为内核态（kernel space）。
2. CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间（kernel space）的读缓冲区（read buffer）。
3. CPU 把读缓冲区（read buffer）的文件描述符（file descriptor）和数据长度拷贝到网络缓冲区（socket buffer）。
4. 基于已拷贝的文件描述符（file descriptor）和数据长度，CPU 利用 DMA 控制器的 gather/scatter 操作直接批量地将数据从内核的读缓冲区（read buffer）拷贝到网卡进行数据传输。
5. 上下文从内核态（kernel space）切换回用户态（user space），sendfile 系统调用执行返回。

sendfile + DMA gather copy 拷贝方式同样存在用户程序不能对数据进行修改的问题，而且本身需要硬件的支持，它只适用于将数据从文件拷贝到 socket 套接字上的传输过程。

Linux进程管理

读者-写者问题

定义： 允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

解决方案：

• 读者优先
  读进程只要看到有其他读进程正在访问文件，就可以继续作读访问；写进程必须等待所有读进程都不访问时才能写文件，即使写进程可能比一些读进程更早提出申请。
• 读者写者公平竞争，老实排队
  因为读者优先的方案如果在读访问非常频繁的场合，有可能造成写进程一直无法访问文件的局面….为了避免这种情况的产生，读者写者请求都老实排队， 排到谁就执行谁， 不准读者插队
• 写者优先
  如果有写者申请写文件，那么在申请之前已经开始读取文件的可以继续读取，但是如果再有读者申请读取文件，则不能够读取，只有在所有的写者写完之后才可以读取

哲学家就餐问题

5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）

所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。

设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。

显而易见，如果不小心处理会有死锁现象， 比如：当每个科学家都同时拿起了左边的筷子时候死锁发生了，都想拿自己右边的筷子，但是科学家每个人左手都不松手。导致都吃不了饭

参考
解决方案：

• 规定奇数号科学家先拿左边的筷子，然后拿右边的筷子。偶数号科学家先拿右边的筷子，然后那左边的筷子。导致0，1科学家竞争1号筷子，2，3科学家竞争3号筷子。四号科学家无人竞争。最后总有一个科学家能获得两只筷子。
• 仅当科学家左右两只筷子都能用的时候，才允许他进餐，代码里的用trylock来实现
• 至多允许四个哲学家同时去拿左边的筷子，最终保证至少有一个科学家能进餐，并且用完之后释放筷子，从而使更多的哲学家能够拿到筷子。

活锁

在某种情形下，轮询（忙等待）可用于进入临界区或存取资源。采用这一策略的主要原因是，相比所做的工作而言，互斥的时间很短而挂起等待的时间开销很大。考虑一个原语，通过该原语，调用进程测试一个互斥信号量，然后或者得到该信号量或者返回失败信息。

现在假设有一对进程使用两种资源。每个进程需要两种资源，它们利用轮询原语enter_region去尝试取得必要的锁，如果尝试失败，则该进程继续尝试。如果进程A先运行并得到资源1，然后进程2运行并得到资源2，以后不管哪一个进程运行，都不会有任何进展，但是哪一个进程也没有被阻塞。结果是两个进程总是一再消耗完分配给它们的CPU配额，但是没有进展也没有阻塞。因此，没有出现死锁现象（因为没有进程阻塞），但是从现象上看好像死锁发生了，这就是活锁（livelock）。

死锁

参考

必要条件

(口诀互占不还？233):

• 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
• 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
• 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
• 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

死锁处理方法大纲

主要有以下四种方法：

• 鸵鸟策略
• 死锁检测与死锁恢复
• 死锁预防
• 死锁避免

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。
因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

每种类型一个资源的死锁检测

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。（当然也可以用拓扑排序思路来检测哈）

每种类型多个资源的死锁检测

上图中，有三个进程四个资源，每个数据代表的含义如下：

• E 向量：资源总量
• A 向量：资源剩余量
• C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
• R 矩阵：每个进程请求的资源数量

进程 P₁ 和 P₂ 所请求的资源都得不到满足，只有进程 P₃ 可以，让 P₃ 执行，之后释放 P₃ 拥有的资源，此时 A = (2 2 2 0)。P₂ 可以执行，执行后释放 P₂ 拥有的资源，A = (4 2 2 1) 。P₁ 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

1. 寻找一个没有标记的进程 P_i，它所请求的资源小于等于 A。
2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
3. 如果没有这样一个进程，算法终止。

死锁恢复

• 利用抢占恢复
• 利用回滚恢复
• 通过杀死进程恢复

死锁预防

在程序运行之前预防发生死锁。

• 破坏互斥条件
  例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
• 破坏占有和等待条件
  一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
• 破坏不可抢占条件
• 破坏环路等待
  给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

在程序运行时避免发生死锁。避免死锁的主要算法是基于一个安全状态的概念。在描述算法前，我们先讨论有关安全的概念。

安全状态的检测

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

安全状态的定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

单个资源的银行家算法

Dijkstra（1965）提出了一种能够避免死锁的调度算法，称为银行家算法（banker’s algorithm），
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

客户们各自做自己的生意，在某些时刻需要贷款（相当于请求资源）。在某一时刻，具体情况如图b所示。这个状态是安全的，由于保留着2个单位，银行家能够拖延除了C以外的其他请求。因而可以让C先完成，然后释放C所占的4个单位资源。有了这4个单位资源，银行家就可以给D或B分配所需的贷款单位，以此类推。

考虑假如向B提供了另一个他所请求的贷款单位，如图b所示，那么我们就有如图c所示的状态，该状态是不安全的。如果忽然所有的客户都请求最大的限额，而银行家无法满足其中任何一个的要求，那么就会产生死锁。不安全状态并不一定引起死锁，由于客户不一定需要其最大贷款额度，但银行家不敢抱这种侥幸心理。

银行家算法就是对每一个请求进行检查，检查如果满足这一请求是否会达到安全状态。若是，那么就满足该请求；若否，那么就推迟对这一请求的满足。为了看状态是否安全，银行家看他是否有足够的资源满足某一个客户。如果可以，那么这笔投资认为是能够收回的，并且接着检查最接近最大限额的一个客户，以此类推。如果所有投资最终都被收回，那么该状态是安全的，最初的请求可以批准。

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

多个资源的银行家算法

可以把银行家算法进行推广以处理多个资源

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

• 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
• 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
• 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

linux进程调度

参考 https://juejin.im/post/6844903568613310477

在Linux中，线程和进程一视同仁，所以讲到进程调度，也包含了线程调度。

调度分两种:

• 非抢占式多任务
  除非任务自己结束，否则将会一直执行。
• 抢占式多任务（Linux用的是这种)
  这种情况下，由调度程序来决定什么时候停止一个进程的运行，这个强制的挂起动作即为抢占。采用抢占式多任务的基础是使用时间片轮转机制来为每个进程分配可以运行的时间单位。

Linux有两种不同的进程优先级范围:

• 使用nice值：越大的nice值意味着更低的优先级。 (-19 ~ 20之间)
• 实时优先级：可配置(通过实时调度API)，越高意味着进程优先级越高。

任何实时的进程优先级都高于普通的进程，因此上面的两种优先级范围处于互不相交的范畴。

时间片：Linux中并不是以固定的时间值(如10ms)来分配时间片的，而是将处理器的使用比作为“时间片”划分给进程。这样，进程所获得的实际CPU时间就和系统的负载密切相关。

Linux内核有两个调度类：

• CFS(完全公平调度器Completely Fair Scheduler)
• 实时调度类。

公平调度CFS

举个例子来区分Unix调度和CFS, 有两个运行的优先级相同的进程:

• 在Unix中可能是每个各执行5ms，执行期间完全占用处理器，但在“理想情况”下，应该是，能够在10ms内同时运行两个进程，每个占用处理器一半的能力。
• CFS的做法是：CFS 调度程序并不采用严格规则来为一个优先级分配某个长度的时间片, 在所有可运行进程的总数上计算出一个进程应该运行的时间，nice值不再作为时间片分配的标准，而是用于处理计算获得的处理器使用权重。

现在我们来看一个简单的例子，假设我们的系统只有两个进程在运行，一个是文本编辑器（I/O消耗型），另一个是视频解码器（处理器消耗型）。
理想的情况下，文本编辑器应该得到更多的处理器时间，至少当它需要处理器时，处理器应该立刻被分配给它（这样才能完成用户的交互），这也就意味着当文本编辑器被唤醒的时候，它应该抢占视频解码程序。
按照普通的情况，OS应该分配给文本编辑器更大的优先级和更多的时间片，但在Linux中，这两个进程都是普通进程，他们具有相同的nice值，因此它们将得到相同的处理器使用比（50%）。
但实际的运行过程中会发生什么呢？CFS将能够注意到，文本编辑器使用的处理器时间比分配给它的要少得多（因为大多时间在等待I/O），这种情况下，要实现所有进程“公平”地分享处理器，就会让文本编辑器在需要运行时立刻抢占视频解码器（每次都是如此）。

实时调度

Linux还实现了 POS1X实时调度扩展。这些扩展允许应用程序精确地控制如何分配CPU
给进程。运作在两个实时调度策略

• SCHED RR （循环）
• SCHED FIFO （先入先出）

下的进程的优先级总是高于运作在非实时策略下的进程。实时进程优先级的取值范围为1 （低）〜99
（高）。只有进程处于可运行状态，那么优先级更高的进程就会完全将优先级低的进程排除在
CPU之外。运作在SCHED_FIFO策略下的进程会互斥地访问CPU直到它执行终止或自动释放
CPU或被进入可运行状态的优先级更高的进程抢占。类似的规则同样适用于SCHED RR策略,
但在该策略下，如果存在多个进程运行于同样的优先级下，那么CPU就会以循环的方式被这
些进程共享。

实时调度采用 SCHED_FIFO 或 SCHED_RR 实时策略来调度的任何任务，与普通（非实时的）任务相比，具有更高的优先级。

Linux 采用两个单独的优先级范围，一个用于实时任务，另一个用于正常任务。实时任务分配的静态优先级为 0〜99，而正常任务分配的优先级为 100〜139。

这两个值域合并成为一个全局的优先级方案，其中较低数值表明较高的优先级。正常任务，根据它们的nice值，分配一个优先级；这里 -20 的nice值映射到优先级 100，而 +19 的nice值映射到 139。下图显示了这个方案。

linux轻量级进程LWP

对于Linux操作系统而言，它对Thread的实现方式比较特殊。在Linux内核中，其实是没有线程的概念的，它把所有的线程当做标准的进程来实现，也就是说Linux内核，并没有为线程提供任何特殊的调度语义，也没有为线程实现特定的数据结构。取而代之的是，线程只是一个与其他进程共享某些资源的进程。每一个线程拥有一个唯一的task_struct结构，Linux内核它仅仅把线程当做一个正常的进程，或者说是轻量级进程，LWP(Lightweight processes)。

Linux线程与进程的区别，主要体现在资源共享、调度、性能几个方面，首先看一下资源共享方面。上面也提到，线程其实是共享了某一个进程的资源，这些资源包括：

• 内存地址空间
• 进程基础信息
• 大部分数据
• 打开的文件
• 信号处理
• 当前工作目录
• 用户和用户组属性
• …

哪些是线程独自拥有的呢？

• 线程ID
• 一系列的寄存器
• 栈的局部变量和返回地址
• 错误码 errno
• 信号掩码
• 优先级
• …

这里说一个黑科技，线程拥有独立的调用栈，除了栈之外共享了其他所有的段segment。但是由于线程间共享了内存，也就是说一个线程，理论上是可以访问到其他线程的调用栈的，可以用一个指针变量，去访问其他线程的局部栈帧，以访问其他线程的局部变量。

LWP如何创建出来

那么Linux中线程是如何创建出来的呢？上面也提到，在Linux中线程是一种资源共享的方式，可以在创建进程的时候，指定某些资源是从其他进程共享的，从而在概念上创建了一个线程。在Linux中，可以通过clone系统调用来创建一个进程，它的函数签名如下：

#include <sched.h>
int clone(int (*fn)(void *), void *child_stack, int flags, void *arg, ...);

我们在使用clone创建进程的过程中，可以指明相应的参数，来决定共享某些资源，比如:

clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0);

这个clone系统调用的行为类似于fork，不过新创建出来的进程，它的内存地址、文件系统资源、打开的文件描述符和信号处理器，都是共享父进程的。换句话说，这个新创建出来的进程，也被叫做Linux Thread。从这个例子中，也可以看出Linux中，线程其实是进程实现资源共享的一种方式。

在内核中，clone调用经过参数传递和解释后会调用do_fork，这个核内函数同时也是fork、vfork系统调用的最终实现：

int do_fork(unsigned long clone_flags, unsigned long stack_start, struct pt_regs* regs,unsigned long stack_size);

在do_fork中，不同的clone_flags将导致不同的行为（共享不同的资源），下面列举几个flag的作用。

• CLONE_VM
  如果do_fork时指定了CLONE_VM开关，创建的轻量级进程的内存空间将会和父进程指向同一个地址，即创建的轻量级进程将与父进程共享内存地址空间。
• CLONE_FS
  如果do_fork时指定了CLONE_FS开关，对于轻量级进程则会与父进程共享相同的所在文件系统的根目录和当前目录信息。也就是说，轻量级进程没有独立的文件系统相关的信息，进程中任何一个线程改变当前目录、根目录等信息都将直接影响到其他线程。
• CLONE_FILES
  如果do_fork时指定了CLONE_FILES开关，创建的轻量级进程与父进程将会共享已经打开的文件。这一共享使得任何线程都能访问进程所维护的打开文件，对它们的操作会直接反映到进程中的其他线程。
• CLONE_SIGHAND
  如果do_fork时指定了CLONE_FILES开关，轻量级进程与父进程将会共享对信号的处理方式。也就是说，子进程与父进程的信号处理方式完全相同，而且可以相互更改。

尽管linux支持轻量级进程，但并不能说它就支持内核线程，因为linux的”线程”和”进程”实际上处于一个调度层次，共享一个进程标识符空间，这种限制使得不可能在linux上实现完全意义上的POSIX线程机制，因此众多的linux线程库实现尝试都只能尽可能实现POSIX的绝大部分语义，并在功能上尽可能逼近。

多核CPU是否能同时执行多个进程？

多核的作用就是每个CPU可以调度不同的任务“并行”执行。注意，这里说的是“并行”，而不是“并发”，所以问题的回答是“能”。

第二个问题，“同时最多执行几个进程“?
这里你想描述的“同时”的意思，是某一个特定时刻吗？如果是，很明显，在某一特定时刻，每个核只能调度一个任务执行，所以有多少个核最多就可以调度多少个进程（或者说成线程比较准确些）。但在一段时间之内，每个核可以“并发”调度多个任务执行。如何“并发”，这就是由不同操作系统的进程调度策略规定的了，比如常见Linux的CFS调度算法和Windows的抢占式调度算法。

创建守护进程的步骤

(两fork一set, u工文dev)
最关键的三步骤:

1. 调用fork，然后使父进程exit。
   虽然子进程继承了父进程的进程组ID，但获得了一个新的进程ID，这就保证了子进程不是一个进程组的组长进程。这是下面将要进行的setsid调用的先决条件。

2. 调用setsid创建一个新会话。
   使调用进程：(a)成为新会话的首进程，(b)成为一个新进程组的组长进程．(c)没有控制终端。也可概括为 : 开启一个新会话并释放它与控制终端之间的所有关联关系

3. 再次fork并杀掉首进程.
   这样就确保了子进程不是一个会话首进程， 根据linux中获取终端的规则（只有会话首进程才能请求一个控制终端）， 这样进程永远不会重新请求一个控制终端

                   会      话
                 /     |      \
               /       |       \
             /         |         \
     前台进程组     后台进程组1     后台进程组2 ...
   /    |   \     /    |   \      /    |   \
进程1 进程2 ...  进程3 进程4 ...       ...

进程组

进程组就是一系列相互关联的进程集合，系统中的每一个进程也必须从属于某一个进程组；每个进程组中都会有一个唯一的 ID(process group id)，简称 PGID；PGID 一般等同于进程组的创建进程的 Process ID，而这个进进程一般也会被称为进程组先导 (process group leader)

会话

会话（session）是一个若干进程组的集合，同样的，系统中每一个进程组也都必须从属于某一个会话；一个会话只拥有最多一个控制终端（也可以没有），该终端为会话中所有进程组中的进程所共用。一个会话中前台进程组只会有一个，只有其中的进程才可以和控制终端进行交互；除了前台进程组外的进程组，都是后台进程组；和进程组先导类似，会话中也有会话先导 (session leader) 的概念，用来表示建立起到控制终端连接的进程。在拥有控制终端的会话中，session leader 也被称为控制进程(controlling process)，一般来说控制进程也就是登入系统的 shell 进程(login shell)；

杀死进程组或会话中的所有进程

我们可以使用该 PGID，通过 kill 命令向整个进程组发送信号：

kill -SIGTERM -- -19701

我们用一个负数 -19701 向进程组发送信号。如果我们传递的是一个正数，这个数将被视为进程 ID 用于终止进程。如果我们传递的是一个负数，它被视为 PGID，用于终止整个进程组。
负数来自系统调用的直接定义。

杀死会话中的所有进程与之完全不同。有些系统没有会话 ID 的概念。即使是具有会话 ID 的系统，例如 Linux，也没有提供系统调用来终止会话中的所有进程。你需要遍历 /proc 输出的进程树，收集所有的 SID，然后一一终止进程。
Pgrep 实现了遍历、收集并通过会话 ID 杀死进程的算法。使用以下命令：

pkill -s <SID>

SIGHUP

SIGHUP 会在以下 3 种情况下被发送给相应的进程：

• 终端关闭时，该信号被发送到 session 首进程以及作为 job 提交的进程（即用 & 符号提交的进程）；
• session 首进程退出时，该信号被发送到该 session 中的前台进程组中的每一个进程；
• 若父进程退出导致进程组成为孤儿进程组，且该进程组中有进程处于停止状态（收到 SIGSTOP 或 SIGTSTP 信号），该信号会被发送到该进程组中的每一个进程。

例如：在我们登录 Linux 时，系统会分配给登录用户一个终端 (Session)。在这个终端运行的所有程序，包括前台进程组和后台进程组，一般都属于这个 Session。当用户退出 Linux 登录时，前台进程组和后台有对终端输出的进程将会收到 SIGHUP 信号。这个信号的默认操作为终止进程，因此前台进程组和后台有终端输出的进程就会中止。
此外，对于与终端脱离关系的守护进程，正常情况下是永远都收不到这个信号的, 所以可以人为的发SIGHUP信号给她用于通知它做一些想要的自定义的操作, 比较常见的如重新读取配置文件操作。 比如 xinetd 超级服务程序。

SIGCHLD与僵死进程

SIGCHLD信号,子进程结束时, 父进程会收到这个信号。如果父进程没有处理这个信号，也没有等待(waitpid)子进程，子进程虽然终止，但是还会在内核进程表中占有表项，这时的子进程称为僵尸进程。这种情 况我们应该捕捉它，或者wait它派生的子进程，或者父进程先终止，这时子进程的终止自动由init进程 来接管

SIGPIPE

在网络编程中，SIGPIPE 这个信号是很常见的。当往一个写端关闭的管道或 socket 连接中连续写入数据时会引发 SIGPIPE 信号, 引发 SIGPIPE 信号的写操作将设置 errno 为 EPIPE。在 TCP 通信中，当通信的双方中的一方 close 一个连接时，若另一方接着发数据，根据 TCP 协议的规定，会收到一个 RST 响应报文，若再往这个服务器发送数据时，系统会发出一个 SIGPIPE 信号给进程，告诉进程这个连接已经断开了，不能再写入数据。

因为 SIGPIPE 信号的默认行为是结束进程，而我们绝对不希望因为写操作的错误而导致程序退出，尤其是作为服务器程序来说就更恶劣了。所以我们应该对这种信号加以处理，在这里，介绍处理 SIGPIPE 信号的方式：

一般给 SIGPIPE 设置 SIG_IGN 信号处理函数，忽略该信号:

signal(SIGPIPE, SIG_IGN);

前文说过，引发 SIGPIPE 信号的写操作将设置 errno 为 EPIPE,。所以，第二次往关闭的 socket 中写入数据时, 会返回 - 1, 同时 errno 置为 EPIPE. 这样，便能知道对端已经关闭，然后进行相应处理，而不会导致整个进程退出.

内核态与用户态的区别

• 内核态：cpu可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu也可以将自己从一个程序切换到另一个程序。
• 用户态：只能受限的访问内存，且不允许访问外围设备，占用cpu的能力被剥夺，cpu资源可以被其他程序获取。

从用户态到内核态切换可以通过三种方式：

• 系统调用: 其实系统调用本身就是中断，但是软件中断，跟硬中断不同。
• 异常：如果当前进程运行在用户态，如果这个时候发生了异常事件，就会触发切换。例如：缺页异常。
• 外设中断：当外设完成用户的请求时，会向CPU发送中断信号。

参考:

• https://zhuanlan.zhihu.com/p/142794794
• https://zhuanlan.zhihu.com/p/32553477

本文主要介绍 QUIC 协议产生的背景和核心特性。

写在前面

如果你的 App，在不需要任何修改的情况下就能提升 15% 以上的访问速度。特别是弱网络的时候能够提升 20% 以上的访问速度。

如果你的 App，在频繁切换 4G 和 WIFI 网络的情况下，不会断线，不需要重连，用户无任何感知。如果你的 App，既需要 TLS 的安全，也想实现 HTTP2 多路复用的强大。

如果你刚刚才听说 HTTP2 是下一代互联网协议，如果你刚刚才关注到 TLS1.3 是一个革命性具有里程碑意义的协议，但是这两个协议却一直在被另一个更新兴的协议所影响和挑战。

如果这个新兴的协议，它的名字就叫做 “快”，并且正在标准化为新一代的互联网传输协议。

你愿意花一点点时间了解这个协议吗？你愿意投入精力去研究这个协议吗？你愿意全力推动业务来使用这个协议吗？

QUIC 概述

Quic 全称 quick udp internet connection [1]，“快速 UDP 互联网连接”，（和英文 quick 谐音，简称 “快”）是由 google 提出的使用 udp 进行多路并发传输的协议。

Quic 相比现在广泛应用的 http2+tcp+tls 协议有如下优势 [2]：

1. 减少了 TCP 三次握手及 TLS 握手时间。
2. 改进的拥塞控制。
3. 避免队头阻塞的多路复用。
4. 连接迁移。
5. 前向冗余纠错。

TCP的缺陷

从上个世纪 90 年代互联网开始兴起一直到现在，大部分的互联网流量传输只使用了几个网络协议。使用 IPv4 进行路由，使用 TCP 进行连接层面的流量控制，使用 SSL/TLS 协议实现传输安全，使用 DNS 进行域名解析，使用 HTTP 进行应用数据的传输。

而且近三十年来，这几个协议的发展都非常缓慢。TCP 主要是拥塞控制算法的改进，SSL/TLS 基本上停留在原地，几个小版本的改动主要是密码套件的升级，TLS1.3[3] 是一个飞跃式的变化，但截止到今天，还没有正式发布。IPv4 虽然有一个大的进步，实现了 IPv6，DNS 也增加了一个安全的 DNSSEC，但和 IPv6 一样，部署进度较慢。

随着移动互联网快速发展以及物联网的逐步兴起，网络交互的场景越来越丰富，网络传输的内容也越来越庞大，用户对网络传输效率和 WEB 响应速度的要求也越来越高。

一方面是历史悠久使用广泛的古老协议，另外一方面用户的使用场景对传输性能的要求又越来越高。如下几个由来已久的问题和矛盾就变得越来越突出。

1. 协议历史悠久导致中间设备僵化。
2. 依赖于操作系统的实现导致协议本身僵化。
3. 建立连接的握手延迟大。
4. 队头阻塞。

这里分小节简单说明一下：

中间设备的僵化

可能是 TCP 协议使用得太久，也非常可靠。所以我们很多中间设备，包括防火墙、NAT 网关，整流器等出现了一些约定俗成的动作。

比如有些防火墙只允许通过 80 和 443，不放通其他端口。NAT 网关在转换网络地址时重写传输层的头部，有可能导致双方无法使用新的传输格式。整流器和中间代理有时候出于安全的需要，会删除一些它们不认识的选项字段。

TCP 协议本来是支持端口、选项及特性的增加和修改。但是由于 TCP 协议和知名端口及选项使用的历史太悠久，中间设备已经依赖于这些潜规则，所以对这些内容的修改很容易遭到中间环节的干扰而失败。

而这些干扰，也导致很多在 TCP 协议上的优化变得小心谨慎，步履维艰。

依赖于操作系统的实现导致协议僵化

TCP 是由操作系统在内核西方栈层面实现的，应用程序只能使用，不能直接修改。虽然应用程序的更新迭代非常快速和简单。但是 TCP 的迭代却非常缓慢，原因就是操作系统升级很麻烦。

现在移动终端更加流行，但是移动端部分用户的操作系统升级依然可能滞后数年时间。PC 端的系统升级滞后得更加严重，windows xp 现在还有大量用户在使用，尽管它已经存在快 20 年。

服务端系统不依赖用户升级，但是由于操作系统升级涉及到底层软件和运行库的更新，所以也比较保守和缓慢。

这也就意味着即使 TCP 有比较好的特性更新，也很难快速推广。比如 TCP Fast Open。它虽然 2013 年就被提出了，但是 Windows 很多系统版本依然不支持它。

建立连接的握手延迟大

不管是 HTTP1.0/1.1 还是 HTTPS，HTTP2，都使用了 TCP 进行传输。HTTPS 和 HTTP2 还需要使用 TLS 协议来进行安全传输。这就出现了两个握手延迟：

1.TCP 三次握手导致的 TCP 连接建立的延迟。

2.TLS 完全握手需要至少 2 个 RTT 才能建立，简化握手需要 1 个 RTT 的握手延迟。

对于很多短连接场景，这样的握手延迟影响很大，且无法消除。

队头阻塞

队头阻塞主要是 TCP 协议的可靠性机制引入的。TCP 使用序列号来标识数据的顺序，数据必须按照顺序处理，如果前面的数据丢失，后面的数据就算到达了也不会通知应用层来处理。

另外 TLS 协议层面也有一个队头阻塞，因为 TLS 协议都是按照 record 来处理数据的，如果一个 record 中丢失了数据，也会导致整个 record 无法正确处理。

概括来讲，TCP 和 TLS1.2 之前的协议存在着结构性的问题，如果继续在现有的 TCP、TLS 协议之上实现一个全新的应用层协议，依赖于操作系统、中间设备还有用户的支持。部署成本非常高，阻力非常大。

所以 QUIC 协议选择了 UDP，因为 UDP 本身没有连接的概念，不需要三次握手，优化了连接建立的握手延迟，同时在应用程序层面实现了 TCP 的可靠性，TLS 的安全性和 HTTP2 的并发性，只需要用户端和服务端的应用程序支持 QUIC 协议，完全避开了操作系统和中间设备的限制。

0RTT建立连接

现如今，高速且安全的网络接入服务已经成为人们的必须。传统 TCP+TLS 构建的安全互联服务，升级与补丁更新时有提出（如 TCP Fastopen，新的 TLS 1.3），但是由于基础设施僵化，升级与应用困难。为解决这个问题，Google 另辟蹊径在 UDP 的基础上实现了带加密的更好的 TCP–QUIC（Quick UDP Internet Connection), 一种基于 UDP 的低时延的互联网传输层协议。近期成立了 Working Group 也将 QUIC 作为制定 HTTP 3.0 的标准的基础, 说明 QUIC 的应用前景美好。本文单独就网络传输的建连问题展开了分析, 浅析了建连时间对传输的影响, 以及 QUIC 的 0-RTT 建连是如何解决建连耗时长的问题的。在此基础上, 结合 QUIC 的源码, 浅析了 QUIC 的基本实现, 并描述一种可供参考的分布式环境下的 0-RTT 的落地实践方案。

以一次简单的 HTTPS 请求（example.com）为例（假设访问 example.com 时返回的内容较小，server 端可以在一个数据包里返回响应），为获取请求资源。需要经过以下 4 个步骤：

1. DNS 查询 example.com 获取 IP。DNS 服务一般默认是由你的 ISP 提供，ISP 通常都会有缓存的，这部分时间能适当减少；
2. TCP 握手，我们熟悉的 TCP 三次握手需要需要 1 个 RTT；
3. TLS 握手，以目前应用最广泛的 TLS 1.2 而言，需要 2 个 RTT。对于非首次建连, 可以选择启用会话重用 (Session Resumption)，则可缩小握手时间到 1 个 RTT；
4. HTTP 业务数据交互，假设 example.com 的数据在一次交互就能取回来。那么业务数据的交互需要 1 个 RTT； 经过上面的过程分析可知，要完成一次简短的 HTTPS 业务数据交互，需要经历：

• 新连接：4RTT + DNS。
• 会话重用：3RTT + DNS

尤其对于小数据量的交互而言，抛开 DNS 查询时间, 建连时间占剩下的总时间的 2/3 至 3/4 不等，影响不可小觑。加之如果用户网络不好，RTT 延时大的话，建连时间可能耗费数百毫秒至数秒不等，这将极大的影响用户体验。究其原因一方面是 TCP 和 TLS 分层设计导致的：分层的设计需要每个逻辑层次分别建立自己的连接状态。另一方面是 TLS 的握手阶段复杂的密钥协商机制导致的。要降低建连耗时，需要从这两方面着手。

针对 TLS 的握手阶段复杂的密钥协商机问题, TLS 1.3 精简了握手交互过程, 实现了 1-RTT 握手。在会话重用类似的理念的基础上, 对非首次握手会话, 可以进一步实现 0-RTT 握手 (在刚开始 TLS 密钥协商的时候，就能附送一部分经过加密的数据传递给对方)。由于 TLS 是建立在 TCP 之上的, 0-RTT 没有计算 TCP 层的握手开销, 因而对用户来说, 发送数据之前还是要经历 TCP 层的 1RTT 握手, 因而不是真正的 0-RTT 握手。

TLS 1.3 为实现 0-RTT，需要双方在刚开始建立连接的时候就已经持有一个对称密钥，这个密钥在 TLS 1.3 中称为 PSK（Pre-Shared-Key）。PSK 是 TLS 1.2 中的会话重用 (Session Resumption) 机制的一个升级，TLS 1.3 握手结束后，服务器可以发送一个 NST（New-Session-Ticket）的报文给客户端，该报文中记录 PSK 的值、名字和有效期等信息，双方下一次建立连接可以使用该 PSK 值作为初始密钥材料。因为 PSK 是从以前建立的安全信道中获得的，只要证明了双方都持有相同的 PSK，不再需要证书认证，就可以证明双方的身份(因此 PSK 也是一种身份认证机制)。TLS 1.3 新加了 Early Data 类型的报文, 用于在 0-RTT 的握手阶段传递应用层数据, 实现了握手的同时就能附带加密的应用层数据从而实现 0-RTT。

TLS 1.3 的 0-RTT 特性不能防止重放攻击, 需要业务在使用时评估是否有重放攻击风险。如有相关风险的话, 可能需要酌情考虑禁用 0-RTT 特性。

下图对比了 TLS 各版本与场景下的延时对比:

TLS 各版本与场景下的耗时

从对比我们可以看到, 即使用上了 TLS 1.3, 精简了握手过程, 最快能做到 0-RTT 握手 (首次是 1-RTT), 但是对用户感知而言, 还要加上 1RTT 的 TCP 握手开销。 Google 有提出 Fastopen 的方案来使得 TCP 非首次握手就能附带用户数据, 但是由于 TCP 实现僵化, 无法升级应用, 相关 RFC 到现今都是 experimental 状态。这种分层设计带来的延时, 有没有办法进一步降低呢? QUIC 通过合并加密与连接管理解决了这个问题, 我们来看看其是如何实现真正意义上的 0-RTT 的握手, 让与 server 进行第一个数据包的交互就能带上用户数据。

QUIC 为规避 TCP 协议僵化的问题，将 QUIC 协议建立在了 UDP 之上。考虑到安全性是网络的必备选项，加密在 QUIC 里强制的。传输方面参考 TCP 并充分优化了 TCP 多年发现的缺陷和不足, 实现了一套端到端的可靠加密传输。通过将加密和连接管理两层合二为一，消除了当前 TCP+TLS 的分层设计传输引入的时延。

同 TLS 的握手一样, QUIC 的加密握手的核心在于协商出一个加密会话数据的对称密钥。QUIC 的握手使用了 DH 密钥协商算法来协商一个对称密钥。DH 密钥协商算法简单来讲, 需要通信双方各自生成自己的非对称公私钥对, 双发各自保留自己的私钥, 将公钥发给对方, 利用对方的公钥和自己的私钥可以运算出同一个对称密钥。详细的原理这里不展开叙述, 有专业的密码学书籍对其原理有详细的论述, 网上也有很多好的教程对其由深入浅出的总结, 如这一篇。

如上所述, DH 密钥协商需要通行双方各自生成自己的非对称公私钥对。server 端与客户端的关系是 1 对 N 的关系, 明显 server 端生成一份公私钥对, 让 N 个客户端公用, 能明显减少生成开销, 降低管理的成本。server 端的这份公私钥对就是专门用于握手使用的, 客户端一经获取, 就可以缓存下来后续建连时继续使用, 这个就是达成 0-RTT 握手的关键, 因此 server 生成的这份公钥称为 0-RTT 握手公钥。真正的握手过程是这样 (简化了实现细节):

1. server 端在握手开始前，server 端需要首先生成 (或加载使用上次保存下来的) 握手公私钥对, 该份公私钥对是所有客户端共享的。
2. client 端首次握手时, client 对 server 一无所知, 需要 1 个 RTT 来询问 server 端的握手公钥 (实际的握手交互还会发送诸如版本等其他数据) 并缓存下来。本步骤只在首次建连时发生(0-RTT 握手公钥的过期也会导致需要重走这一步), 但这种情况很少发生, 影响很小(也没办法避免)。
3. client 收到 server 端返回这份握手公钥后，生成自己的临时公私钥对后, 计算出共享的对称密钥后, 加密好数据, 并连同 client 的公钥一并发给 server 端。照 DH 密钥协商的原理, 此处已经可以协商出每条会话不一样的会话密钥了 (因为每个 client 生成的公私钥是不同的), 是不是拿这个来加密会话数据就行了呢? 真实的情况不是这样的!
4. server 端会再次生成一份临时的公私钥对，使用这份临时的私钥与客户端的公钥运算出最终的会话对称密钥。接下来 server 会拿这个最终的会话密钥加密应用层数据, 连同这份临时的 server 端公钥一并发给 client 端, client 端收到后可以按照 DH 的原理依瓢画葫会恢复出最终的会话对称密钥。后续所有的数据都是用最终的会话对称密钥进行加密。server 侧这个动作是不是多此一举呢? 不是的, 这么做的目的是为了获取所谓的前向安全特性: 因为 server 端的后面生成的这份公私钥是临时生成的, 不会保存下来，也就杜绝了密钥泄漏导致会话数据被恶意收集后的被解密掉的风险。

首次握手要多一个 RTT 询问 server 端的 0-RTT 握手公钥, 此询问过程不携带任何应用层数据, 因此是 1-RTT 握手。在首次握手完成后, client 端可以缓存下第一次询问获知的 server 端的公钥信息, 后续的连接过程可以跳过询问，直接使用缓存的 server 端的公钥。公钥信息在 QUIC 的实现里是保存在握手数据包里的 SCFG 中的 (Server Config), 获取 0-RTT 握手公钥就是要获取 SCFG, 后续均以获取 SCFG 代替。详细的握手过程, 可以参见 dog250 博客文章的详细叙述。

从上面的分析可知，0-RTT 握手的首次交互，server 端使用的是保存下来的握手密钥，因而没有无法做到前向安全，不能防止重放攻击, 需要业务在使用时评估是否有重放攻击风险。

QUIC 0-RTT 握手

上文简述了 QUIC 握手的密钥协商过程，首次需要询问一次 Server 以获取 SCFG, 从而获取存储于其中的 0-RTT 握手公钥。这一交互过程中 client 和 server 在 QUIC 的握手协议发送的报文中分别叫 Inchoate Client hello message (inchoate CHLO) 和 Rejection message (REJ)。因而包含 server 端的握手公钥的 SCFG 是在 REJ 报文中发给客户端的。有了 SCFG，接下来就能发起 0-RTT 握手。这一过程中 client 和 server 端在 QUIC 的握手协议发送的报文中分别叫 Full Client Hello message (full CHLO) 和 Server Hello message (SHLO)。下图摘自 Google QUIC 握手协议的官方文档，详细叙述了握手过程 client 侧的处理流程：

QUIC 握手客户端侧处理流程

0RTT的重放攻击风险

0-RTT连接恢复并非那么简单，它会带来许多意外风险及警告，这正是为什么有些默认程序不启用0-RTT连接恢复的原因。用户必须提前考虑所涉及的风险，并做出决定是否使用此功能。可以在应用程序层面使用预防措施来减轻这种情况。

首先，0-RTT连接恢复是不提供forwardsecrecy的，针对连接的secret parameters的妥协将微不足道地允许恢复新连接0-RTT阶段期间，发送applicationdata 进行特定的妥协。

在0-RTT阶段之后、或握手之后发送的数据，仍然是安全的。这是因为TLS1.3 (及QUIC)还是会对handshakecompletion之后发送的数据执行normal key exchange algorithm (这是forwardsecret) 。

值得注意的是，在0-RTT期间发送的applicationdata 可以被路径上的on-path attacker 捕获，然后多次重播到同一个服务器。这个在大部分情况下也许不是问题，因为attacker无法解密数据，0-RTT连接恢复还是非常有用的。在其他的情况下，这可能会引起出乎意料的风险。

举个比例，假设一家银行允许authenticated user (e.g using HTTPcookie, 或其他HTTP身份验证机制)通过specificAPI endpoint发出HTTP请求将资金从其账户发送到另一个用户。

如果attacker能够在使用0-RTT连接恢复时捕获该请求，他们将无法看到plaintext并且获取用户的凭据，原因是因为他们不知道用于加密数据的secretkey；但是他们仍然有可能一直散发重复性地请求，耗尽该用户的银行账户里的钱。

改进的拥塞控制

TCP 的拥塞控制实际上包含了四个算法：慢启动，拥塞避免，快速重传，快速恢复 [22]。

QUIC 协议当前默认使用了 TCP 协议的 Cubic 拥塞控制算法 [6]，同时也支持 CubicBytes, Reno, RenoBytes, BBR, PCC 等拥塞控制算法。

从拥塞算法本身来看，QUIC 只是按照 TCP 协议重新实现了一遍，那么 QUIC 协议到底改进在哪些方面呢？主要有如下几点：

可插拔

什么叫可插拔呢？就是能够非常灵活地生效，变更和停止。体现在如下方面：

1. 应用程序层面就能实现不同的拥塞控制算法，不需要操作系统，不需要内核支持。这是一个飞跃，因为传统的 TCP 拥塞控制，必须要端到端的网络协议栈支持，才能实现控制效果。而内核和操作系统的部署成本非常高，升级周期很长，这在产品快速迭代，网络爆炸式增长的今天，显然有点满足不了需求。
2. 即使是单个应用程序的不同连接也能支持配置不同的拥塞控制。就算是一台服务器，接入的用户网络环境也千差万别，结合大数据及人工智能处理，我们能为各个用户提供不同的但又更加精准更加有效的拥塞控制。比如 BBR 适合，Cubic 适合。
3. 应用程序不需要停机和升级就能实现拥塞控制的变更，我们在服务端只需要修改一下配置，reload 一下，完全不需要停止服务就能实现拥塞控制的切换。

STGW 在配置层面进行了优化，我们可以针对不同业务，不同网络制式，甚至不同的 RTT，使用不同的拥塞控制算法。

单调递增的 Packet Number

TCP 为了保证可靠性，使用了基于字节序号的 Sequence Number 及 Ack 来确认消息的有序到达。

QUIC 同样是一个可靠的协议，它使用 Packet Number 代替了 TCP 的 sequence number，并且每个 Packet Number 都严格递增，也就是说就算 Packet N 丢失了，重传的 Packet N 的 Packet Number 已经不是 N，而是一个比 N 大的值。而 TCP 呢，重传 segment 的 sequence number 和原始的 segment 的 Sequence Number 保持不变，也正是由于这个特性，引入了 Tcp 重传的歧义问题。

如上图所示，超时事件 RTO 发生后，客户端发起重传，然后接收到了 Ack 数据。由于序列号一样，这个 Ack 数据到底是原始请求的响应还是重传请求的响应呢？不好判断。

如果算成原始请求的响应，但实际上是重传请求的响应（上图左），会导致采样 RTT 变大。如果算成重传请求的响应，但实际上是原始请求的响应，又很容易导致采样 RTT 过小。

由于 Quic 重传的 Packet 和原始 Packet 的 Pakcet Number 是严格递增的，所以很容易就解决了这个问题。

如上图所示，RTO 发生后，根据重传的 Packet Number 就能确定精确的 RTT 计算。如果 Ack 的 Packet Number 是 N+M，就根据重传请求计算采样 RTT。如果 Ack 的 Pakcet Number 是 N，就根据原始请求的时间计算采样 RTT，没有歧义性。

但是单纯依靠严格递增的 Packet Number 肯定是无法保证数据的顺序性和可靠性。QUIC 又引入了一个 Stream Offset 的概念。

即一个 Stream 可以经过多个 Packet 传输，Packet Number 严格递增，没有依赖。但是 Packet 里的 Payload 如果是 Stream 的话，就需要依靠 Stream 的 Offset 来保证应用数据的顺序。如错误! 未找到引用源。所示，发送端先后发送了 Pakcet N 和 Pakcet N+1，Stream 的 Offset 分别是 x 和 x+y。

假设 Packet N 丢失了，发起重传，重传的 Packet Number 是 N+2，但是它的 Stream 的 Offset 依然是 x，这样就算 Packet N + 2 是后到的，依然可以将 Stream x 和 Stream x+y 按照顺序组织起来，交给应用程序处理。

不允许 Reneging

什么叫 Reneging 呢？就是接收方丢弃已经接收并且上报给 SACK 选项的内容 [8]。TCP 协议不鼓励这种行为，但是协议层面允许这样的行为。主要是考虑到服务器资源有限，比如 Buffer 溢出，内存不够等情况。

Reneging 对数据重传会产生很大的干扰。因为 Sack 都已经表明接收到了，但是接收端事实上丢弃了该数据。

QUIC 在协议层面禁止 Reneging，一个 Packet 只要被 Ack，就认为它一定被正确接收，减少了这种干扰。

更多的 Ack 块

TCP 的 Sack 选项能够告诉发送方已经接收到的连续 Segment 的范围，方便发送方进行选择性重传。

由于 TCP 头部最大只有 60 个字节，标准头部占用了 20 字节，所以 Tcp Option 最大长度只有 40 字节，再加上 Tcp Timestamp option 占用了 10 个字节 [25]，所以留给 Sack 选项的只有 30 个字节。

每一个 Sack Block 的长度是 8 个，加上 Sack Option 头部 2 个字节，也就意味着 Tcp Sack Option 最大只能提供 3 个 Block。

但是 Quic Ack Frame 可以同时提供 256 个 Ack Block，在丢包率比较高的网络下，更多的 Sack Block 可以提升网络的恢复速度，减少重传量。

Ack Delay 时间

Tcp 的 Timestamp 选项存在一个问题 [25]，它只是回显了发送方的时间戳，但是没有计算接收端接收到 segment 到发送 Ack 该 segment 的时间。这个时间可以简称为 Ack Delay。

这样就会导致 RTT 计算误差。如下图：

• 可以认为 TCP 的 RTT 计算：RTT = timestamp2 - timestamp1
• 而 Quic 计算如下：RTT = timestamp2 - timestamp1 - AckDelay

当然 RTT 的具体计算没有这么简单，需要采样，参考历史数值进行平滑计算，参考如下公式

SRTT = SRTT + α(RTT - SRTT)
RTO = μ * SRTT + δ*DevRTT

基于 stream 和 connecton 级别的流量控制

QUIC 的流量控制 [22] 类似 HTTP2，即在 Connection 和 Strea6 级别提供了两种流量控制。为什么需要两类流量控制呢？主要是因为 QUIC 支持多路复用。

1. Stream 可以认为就是一条 HTTP 请求。
2. Connection 可以类比一条 TCP 连接。多路复用意味着在一7 Connetion 上会同时存在多条 Stream。既需要对单个 Stream 进行控制，又需要针对所有 Stream 进行总体控制。

QUIC 实现流量控制的原理比较简单：

通过 window_update 帧告诉对端自己可以接收的字节数，这样发送方就不会发送超过这个数量的数据。

通过 BlockFrame 告诉对端由于流量控制被阻塞了，无法发送数据。

QUIC 的流量控制和 TCP 有点区别，TCP 为了保证可靠性，窗口左边沿向右滑动时的长度取决于已经确认的字节数。如果中间出现丢包，就算接收到了更大序号的 Segment，窗口也无法超过这个序列号。

但 QUIC 不同，就算此前有些 packet 没有接收到，它的滑动只取决于接收到的最大偏移字节数。

• 针对 Stream：可用窗口 = 最大窗口数 - 接收到的最大偏移数
• 针对 Connection：可用窗口 = stream1可用窗口 + stream2可用窗口 + ... + streamN可用窗口

同样地，STGW 也在连接和 Stream 级别设置了不同的窗口数。

最重要的是，我们可以在内存不足或者上游处理性能出现问题时，通过流量控制来限制传输速率，保障服务可用性。

没有队头阻塞的多路复用

QUIC 的多路复用和 HTTP2 类似。在一条 QUIC 连接上可以并发发送多个 HTTP 请求 (stream)。但是 QUIC 的多路复用相比 HTTP2 有一个很大的优势。

QUIC 一个连接上的多个 stream 之间没有依赖。这样假如 stream2 丢了一个 udp packet，也只会影响 stream2 的处理。不会影响 stream2 之前及之后的 stream 的处理。

这也就在很大程度上缓解甚至消除了队头阻塞的影响。

多路复用是 HTTP2 最强大的特性 [7]，能够将多条请求在一条 TCP 连接上同时发出去。但也恶化了 TCP 的一个问题，队头阻塞 [11]，如下图示：

HTTP2 在一个 TCP 连接上同时发送 4 个 Stream。其中 Stream1 已经正确到达，并被应用层读取。但是 Stream2 的第三个 tcp segment 丢失了，TCP 为了保证数据的可靠性，需要发送端重传第 3 个 segment 才能通知应用层读取接下去的数据，虽然这个时候 Stream3 和 Stream4 的全部数据已经到达了接收端，但都被阻塞住了。

不仅如此，由于 HTTP2 强制使用 TLS，还存在一个 TLS 协议层面的队头阻塞 [12]。

Record 是 TLS 协议处理的最小单位，最大不能超过 16K，一些服务器比如 Nginx 默认的大小就是 16K。由于一个 record 必须经过数据一致性校验才能进行加解密，所以一个 16K 的 record，就算丢了一个字节，也会导致已经接收到的 15.99K 数据无法处理，因为它不完整。

那 QUIC 多路复用为什么能避免上述问题呢？

1. QUIC 最基本的传输单元是 Packet，不会超过 MTU 的大小，整个加密和认证过程都是基于 Packet 的，不会跨越多个 Packet。这样就能避免 TLS 协议存在的队头阻塞。
2. Stream 之间相互独立，比如 Stream2 丢了一个 Pakcet，不会影响 Stream3 和 Stream4。不存在 TCP 队头阻塞。

当然，并不是所有的 QUIC 数据都不会受到队头阻塞的影响，比如 QUIC 当前也是使用 Hpack 压缩算法 [10]，由于算法的限制，丢失一个头部数据时，可能遇到队头阻塞。

总体来说，QUIC 在传输大量数据时，比如视频，受到队头阻塞的影响很小。

加密认证的报文

TCP 协议头部没有经过任何加密和认证，所以在传输过程中很容易被中间网络设备篡改，注入和窃听。比如修改序列号、滑动窗口。这些行为有可能是出于性能优化，也有可能是主动攻击。

但是 QUIC 的 packet 可以说是武装到了牙齿。除了个别报文比如 PUBLIC_RESET 和 CHLO，所有报文头部都是经过认证的，报文 Body 都是经过加密的。

这样只要对 QUIC 报文任何修改，接收端都能够及时发现，有效地降低了安全风险。

如下图所示，红色部分是 Stream Frame 的报文头部，有认证。绿色部分是报文内容，全部经过加密。

连接迁移

一条 TCP 连接 [17] 是由四元组标识的（源 IP，源端口，目的 IP，目的端口）。什么叫连接迁移呢？就是当其中任何一个元素发生变化时，这条连接依然维持着，能够保持业务逻辑不中断。当然这里面主要关注的是客户端的变化，因为客户端不可控并且网络环境经常发生变化，而服务端的 IP 和端口一般都是固定的。

比如大家使用手机在 WIFI 和 4G 移动网络切换时，客户端的 IP 肯定会发生变化，需要重新建立和服务端的 TCP 连接。

又比如大家使用公共 NAT 出口时，有些连接竞争时需要重新绑定端口，导致客户端的端口发生变化，同样需要重新建立 TCP 连接。

针对 TCP 的连接变化，MPTCP[5] 其实已经有了解决方案，但是由于 MPTCP 需要操作系统及网络协议栈支持，部署阻力非常大，目前并不适用。

所以从 TCP 连接的角度来讲，这个问题是无解的。

那 QUIC 是如何做到连接迁移呢？很简单，任何一条 QUIC 连接不再以 IP 及端口四元组标识，而是以一个 64 位的随机数作为 ID 来标识，这样就算 IP 或者端口发生变化时，只要 ID 不变，这条连接依然维持着，上层业务逻辑感知不到变化，不会中断，也就不需要重连。

由于这个 ID 是客户端随机产生的，并且长度有 64 位，所以冲突概率非常低。

其他亮点

此外，QUIC 还能实现前向冗余纠错，在重要的包比如握手消息发生丢失时，能够根据冗余信息还原出握手消息。

QUIC 还能实现证书压缩，减少证书传输量，针对包头进行验证等。

限于篇幅，本文不再详细介绍，有兴趣的可以参考文档 [23] 和文档 [4] 和文档 [26]。

TCP

包头长度 20个字节

三次握手

如果第三次握手的ack丢失了咋办

当客户端收到服务端的SYNACK应答后，其状态变为ESTABLISHED，并会发送ACK包给服务端，准备发送数据了。如果此时ACK在网络中丢失（如上图所示），过了超时计时器后，那么服务端会重新发送SYNACK包，重传次数根据/proc/sys/net/ipv4/tcp_synack_retries来指定，默认是5次。如果重传指定次数到了后，仍然未收到ACK应答，那么一段时间后，Server自动关闭这个连接。

问题就在这里，客户端已经认为连接建立，而服务端则可能处在SYN-RCVD或者CLOSED，接下来我们需要考虑这两种情况下服务端的应答：

• 服务端处于CLOSED，当接收到连接已经关闭的请求时，服务端会返回RST 报文，客户端接收到后就会关闭连接，如果需要的话则会重连，那么那就是另一个三次握手了。
• 服务端处于SYN-RCVD，此时如果接收到正常的ACK 报文，那么很好，连接恢复，继续传输数据；如果接收到写入数据等请求呢？注意了，此时写入数据等请求也是带着ACK 报文的，实际上也能恢复连接，使服务器恢复到ESTABLISHED状态，继续传输数据。

SYN-Flood与SYN-Cookie

所谓SYN-Flood(SYN 洪泛攻击)，就是利用SYNACK 报文的时候，服务器会为客户端请求分配缓存，那么黑客（攻击者），就可以使用一批虚假的ip向服务器大量地发建立TCP 连接的请求，服务器为这些虚假ip分配了缓存后，处在SYN_RCVD状态，存放在半连接队列中；另外，服务器发送的请求又不可能得到回复（ip都是假的，能回复就有鬼了），只能不断地重发请求，直到达到设定的时间/次数后，才会关闭。

服务器不断为这些半开连接分配资源，导致服务器的连接资源被消耗殆尽，不过所幸，我们可以使用SYN Cookie进行稍微的防御一下。

所谓的SYN Cookie防御系统，与前面接收到SYN 报文就分配缓存不同，此时暂不分配资源；同时利用SYN 报文的源和目的地IP和端口，以及服务器存储的一个秘密数，使用它们进行散列，得到server_isn作为服务端的初始 TCP 序号，也就是所谓的SYN cookie, 然后将SYNACK 报文中发送给客户端，接下来就是对ACK 报文进行判断，如果其返回的ack里的确认号正好等于server_isn + 1，说明这是一个合法的ACK，那么服务器才会为其生成一个具有套接字的全开的连接。(有点类似于JWT那一套机制哈)

缺点:

• 增加了密码学运算, 增大了cpu消耗
• 因为没有保存半连接状态, 所以无法存储一些比如大窗口/sack等信息

四次挥手

timewait的意义

• 2msl之后网络中的数据分节全部消失, 防止影响到复用了原端口ip的新连接
• 如果b没收到最后一个ack, b就会重发fin, a如果不维护一个timewait却收到了一个fin会感觉莫名其妙然后响应一个rst, 然后b就会解释为一个错误

timewait和closewait太多咋办

• timewait太多咋办?
  • net.ipv4.tcp_tw_reuse = 1 表示开启重用。允许将TIME-WAIT sockets重新用于新的TCP连接，默认为0，表示关闭；
  • net.ipv4.tcp_tw_recycle = 1 表示开启TCP连接中TIME-WAIT sockets的快速回收，默认为0，表示关闭。
  • net.ipv4.tcp_fin_timeout这个时间可以减少在异常情况下服务器从FIN-WAIT-2转到TIME_WAIT的时间。
• closewait太多咋办?
  • 解决方案只有: 查代码. 因为如果一直保持在CLOSE_WAIT状态，那么只有一种情况，就是在对方关闭连接之后服务器程序自己没有进一步发出fin信号。换句话说，就是在对方连接关闭之后，程序里没有检测到，或者由于什么逻辑bug导致服务端没有主动发起close, 或者程序压根就忘记了这个时候需要关闭连接，于是这个资源就一直被程序占着。

tcp拥塞控制

• 快速重传:
  报文段1成功接收并被确认ACK 2，接收端的期待序号为2，当报文段2丢失，报文段3失序到来，与接收端的期望不匹配，接收端重复发送冗余ACK 2。这样，如果在超时重传定时器溢出之前，接收到连续的三个重复冗余ACK（其实是收到4个同样的ACK，第一个是正常的，后三个才是冗余的），发送端便知晓哪个报文段在传输过程中丢失了，于是重发该报文段，不需要等待超时重传定时器溢出，大大提高了效率。这便是快速重传机制。
• 快速恢复
• 慢启动
• 拥塞避免

tcp滑动窗口

每个TCP连接的两端都维护一组窗口：发送窗口结构（send window structure）和接收窗口结构（receive window structure）。TCP以字节为单位维护其窗口结构。TCP头部中的窗口大小字段相对ACK号有一个字节的偏移量。发送端计算其可用窗口，即它可以立即发送的数据量。可用窗口（允许发送但还未发送）计算值为提供窗口（即由接收端通告的窗口）大小减去在传（已发送但未得到确认）的数据量。图中P1、P2、P3分别记录了窗口的左边界、下次发送的序列号、右边界。

如上图所示， 随着发送端接收到返回的数据ACK，滑动窗口也随之右移。发送端根据接收端返回的ACK可以得到两个重要的信息：一是接收端期望收到的下一个字节序号；二是当前的窗口大小（再结合发送端已有的其他信息可以得出还能发送多少字节数据）。

需要注意的是：发送窗口的左边界只能右移，因为它控制的是已发送并受到确认的数据，具有累积性，不能返回；右边界可以右移也可以左移（能左移的右边界会带来一些缺陷，下文会讲到）。

接收端也维护一个窗口结构，但比发送窗口简单（只有左边界和右边界）。该窗口结构记录了已接收并确认的数据，以及它能够接收的最大序列号，该窗口能保证接收数据的正确性（避免存储重复的已接收和确认的数据，以及避免存储不应接收的数据）。由于TCP的累积ACK特性，只有当到达数据序列号等于左边界时，窗口才能向前滑动。

零窗口与TCP持续计时器

Zero Window

上图，我们可以看到一个处理缓慢的Server（接收端）是怎么把Client（发送端）的TCP Sliding Window给降成0的。此时，你一定会问，如果Window变成0了，TCP会怎么样？是不是发送端就不发数据了？是的，发送端就不发数据了，你可以想像成“Window Closed”，那你一定还会问，如果发送端不发数据了，接收方一会儿Window size 可用了，怎么通知发送端呢？

解决这个问题，TCP使用了Zero Window Probe技术，缩写为ZWP，也就是说，发送端在窗口变成0后，会发ZWP的包给接收方，让接收方来ack他的Window尺寸，一般这个值会设置成3次，第次大约30-60秒（不同的实现可能会不一样）。如果3次过后还是0的话，有的TCP实现就会发RST把链接断了。

ACK延迟确认机制

接收方在收到数据后，并不会立即回复ACK,而是延迟一定时间。一般ACK延迟发送的时间为200ms，但这个200ms并非收到数据后需要延迟的时间。系统有一个固定的定时器每隔200ms会来检查是否需要发送ACK包。这样做有两个目的。

• 这样做的目的是ACK是可以合并的，也就是指如果连续收到两个TCP包，并不一定需要ACK两次，只要回复最终的ACK就可以了，可以降低网络流量。
• 如果接收方有数据要发送，那么就会在发送数据的TCP数据包里，带上ACK信息。这样做，可以避免大量的ACK以一个单独的TCP包发送，减少了网络流量。

Linux定时器实现原理

时间轮定时器-低分辨率实现

Linux 2.6.16之前，内核只支持低精度时钟，内核定时器的工作方式：

1. 系统启动后，会读取时钟源设备(RTC,HPET，PIT…)，初始化当前系统时间。
2. 内核会根据HZ(系统定时器频率，节拍率)参数值，设置时钟事件设备，启动tick(节拍)中断。HZ表示1秒种产生多少个时钟硬件中断，tick就表示连续两个中断的间隔时间。
3. 设置时钟事件设备后，时钟事件设备会定时产生一个tick中断，触发时钟中断处理函数，更新系统时钟,并检测timer wheel，进行超时事件的处理。

在上面工作方式下，Linux 2.6.16 之前，内核软件定时器采用timer wheel多级时间轮的实现机制，维护操作系统的所有定时事件。timer wheel的触发是基于系统tick周期性中断。所以说这之前，linux只能支持ms级别的时钟，随着时钟源硬件设备的精度提高和软件高精度计时的需求，有了高精度时钟的内核设计。

所谓低分辨率定时器，是指这种定时器的计时单位基于jiffies值的计数，也就是说，它的精度只有1HZ，假如你的内核配置的HZ是1000，那意味着系统中的低分辨率定时器的精度就是1ms。早期的内核版本中，内核并不支持高精度定时器，理所当然只能使用这种低分辨率定时器, 后来随着时钟源硬件设备的精度提高和软件高精度计时的需求，才有了高精度时钟的内核设计

. . .