异常检测的N种方法

转载自:https://mp.weixin.qq.com/s/w7SbAHxZsmHqFtTG8ZAXNg

异常点检测(Outlier detection),又称为离群点检测,是找出与预期对象的行为差异较大的对象的一个检测过程。这些被检测出的对象被称为异常点或者离群点。异常点检测在生产生活中有着广泛应用,比如信用卡反欺诈、工业损毁检测、广告点击反作弊等。

异常点(outlier)是一个数据对象,它明显不同于其他的数据对象。如下图1所示,N1、N2区域内的点是正常数据。而离N1、N2较远的O1、O2、O3区域内的点是异常点。

图1.异常点示例

异常检测的一大难点是缺少ground truth。常见的方法是先用无监督方法挖掘异常样本,再用有监督模型融合多个特征挖掘更多作弊。

近期使用多种算法挖掘异常点,下面从不同视角介绍异常检测算法的原理及其适用场景,考虑到业务特殊性,本文不涉及特征细节。

1.时间序列

1.1 移动平均(Moving Average,MA)

移动平均是一种分析时间序列的常用工具,它可过滤高频噪声和检测异常点。根据计算方法的不同,常用的移动平均算法包括简单移动平均、加权移动平均、指数移动平均。假设移动平均的时间窗口为T,有一个时间序列:

1.1.1 简单移动平均(Simple Moving Average,SMA)

从上面的公式容易看出可以用历史的值的均值作为当前值的预测值,在序列取值随时间波动较小的场景中,上述移动均值与该时刻的真实值的差值超过一定阈值则判定该时间的值异常。

适用于:

a.对噪声数据进行平滑处理,即用移动均值替代当前时刻取值以过滤噪声;

b.预测未来的取值。

1.1.2 加权移动平均(Weighted Moving Average, WMA)

由于简单移动平均对窗口内所有的数据点都给予相同的权重,对近期的最新数据不够敏感,预测值存在滞后性。按着这个思路延伸,自然的想法就是在计算移动平均时,给近期的数据更高的权重,而给窗口内较远的数据更低的权重,以更快的捕捉近期的变化。由此便得到了加权移动平均和指数移动平均。

加权移动平均比简单移动平均对近期的变化更加敏感,加权移动平均的滞后性小于简单移动平均。但由于仅采用线性权重衰减,加权移动平均仍然存在一定的滞后性。

1.1.3 指数移动平均(Exponential Moving Average, EMA)

指数移动平均(Exponential Moving Average, EMA)和加权移动平均类似,但不同之处是各数值的加权按指数递减,而非线性递减。此外,在指数衰减中,无论往前看多远的数据,该期数据的系数都不会衰减到 0,而仅仅是向 0 逼近。因此,指数移动平均实际上是一个无穷级数,即无论多久远的数据都会在计算当期的指数移动平均数值时,起到一定的作用,只不过离当前太远的数据的权重非常低。在实际应用中,可以按如下方法得到t时刻的指数移动平均:

其中表示权重的衰减程度,取值在0和1之间。越大,过去的观测值衰减得越快。

1.2 同比和环比

图2.同比和环比

同比和环比计算公式如图2所示。适合数据呈周期性规律的场景中。如:1.监控APP的DAU的环比和同比,以及时发现DAU上涨或者下跌;2.监控实时广告点击、消耗的环比和同比,以及时发现变化。当上述比值超过一定阈值(阈值参考第10部分)则判定出现异常。

1.3 时序指标异常检测(STL+GESD)

STL是一种单维度时间指标异常检测算法。大致思路是:


(1)先将指标做STL时序分解,得到seasonal,trend,residual成分,如图3所示;
(2)用GESD (generalized extreme studentized deviate)算法对trend+residual成分进行异常检测;
(3)为增强对异常点的鲁棒性,将GESD算法中的mean,std等统计量用median, MAD(median absolute deviation)替换;
(4)异常分输出:abnorm_score = (value – median)/MAD, value为当前值,median为序列的中位数。负分表示异常下跌,正分表示异常上升。

图3.STL分解示例


2.统计

2.1 单特征且符合高斯分布

如果变量x服从高斯分布:,则其概率密度函数为:

我们可以使用已有的样本数据来预测总体中的,计算方法如下:


2.2 多个不相关特征且均符合高斯分布

假设n维的数据集合形如:。

且每一个变量均符合高斯分布,那么可以计算每个维度的均值和方差

,具体来说,对于,可以计算:

如果有一个新的数据,可以计算概率如下:


2.3 多个特征相关,且符合多元高斯分布

假设n维的数据集合,且每一个变量均符合高斯分布,可以计算n维的均值向量的协方差矩阵:

如果有一个新的数据,可以计算概率:


2.4 马氏距离(Mahalanobis distance)

对于一个多维列向量的数据集合D,假设是均值向量,那么对于数据集D中的任意对象,从到的马氏距离是:

其中是协方差矩阵。可以对数值进行排序,如果数值过大,那么就可以认为点是离群点。

2.5 箱线图

箱线图算法不需要数据服从特定分布,比如数据分布不符合高斯分布时可以使用该方法。该方法需要先计算第一四分位数Q1(25%)和第三四分位数Q3(75%)。令IQR=Q3-Q1,然后算出异常值边界点Q3+λ*IQR和Q1- λ*IQR,通常λ取1.5(类似于正态分布中的,如下图4所示:

图4.箱线图算法示意图


3.距离

3.1、基于角度的异常点检测

图5.点集和角度

如上图5所示,现在有三个点X,Y,Z,和两个向量,如果对任意不同的点Y,Z,角度变化都较小,则点X是异常点。通过余弦夹角公式易得角度:

D是点集,则对于任意不同的点,点X的所有角度的方差为:

异常点的上述方差较小。该算法的时间复杂度是,适合数据量N较小的场景。

3.2 基于KNN的异常点检测

D是点集,则对于任意点,计算其K近邻的距离之和Dist(K,X)。Dist(K,X)越大的点越异常。时间复杂度是,其中N是数据量的大小。

4.线性方法(矩阵分解和PCA降维)

基于矩阵分解的异常点检测方法的主要思想是利用主成分分析(PCA)去寻找那些违反了数据之间相关性的异常点。为了找到这些异常点,基于主成分分析的算法会把数据从原始空间投影到主成分空间,然后再从主成分空间投影回原始空间。对于大多数的数据而言,如果只使用第一主成分来进行投影和重构,重构之后的误差是较小的;但是对于异常点而言,重构之后的误差相对较大。这是因为第一主成分反映了正常点的方差,最后一个主成分反映了异常点的方差。


假设X是一个p维的数据集合,有N个样本,它的协方差矩阵是。那么协方差矩阵就可以分解为:。

其中P是一个维正交矩阵,它的每一列都是的特征向量。D是一个维对角矩阵,包含了特征值。在图形上,一个特征向量可以看成2维平面上的一条线,或者高维空间里面的一个平面。特征向量所对应的特征值反映了这批数据在这个方向上的拉伸程度。通常情况下,将特征值矩阵D中的特征值从大到小的排序,特征向量矩阵P的每一列也进行相应的调整。

数据集X在主成分空间的投影可以写成Y=XP,注意可以只在部分的维度上做投影,使用top-j的主成分投影之后的矩阵为:。

其中是矩阵P的前j列,也就是说是一个维的矩阵。是矩阵Y的前j列,是一个维的矩阵。按同样的方式从主成分空间映射到原始空间,重构之后的数据集合是 。

其中是使用top-j的主成分重构之后的数据集,是一个维的矩阵。如图6所示:

图6.矩阵变换示意图

定义数据的异常值分为:

其中表示的是top-j主成分占所有主成分的比例,特征值是按照从大到小的顺序排列的。因此是递增的,这就意味着j越大,越多的方差就会被算到中,因为是从 1 到 j 的求和。在这个定义下,偏差最大的第一个主成分获得最小的权重,偏差最小的最后一个主成分获得了最大的权重1。根据 PCA 的性质,异常点在最后一个主成分上有着较大的偏差,因此会有更大的异常分。

5.分布

即对比基准流量和待检测流量的某个特征的分布。

5.1 相对熵(KL散度)

相对熵(KL散度)可以衡量两个随机分布之间的距离,当两个随机分布相同时,它们的相对熵为零,当两个随机分布的差别增大时,它们的相对熵也会增大。所以相对熵可以用于比较两个分布的相似度。设是两个概率分布的取值,则对应相对熵为。


5.2 卡方检验

卡方检验通过检验统计量来比较期望结果和实际结果之间的差别,然后得出实际结果发生的概率。其中O代表观察值,E代表期望值。这个检验统计量提供了一种期望值与观察值之间差异的度量办法。最后根据设定的显著性水平查找卡方概率表来判定。

6.树(孤立森林)

图7.iForest检测结果

孤立森林(Isolation Forest)假设我们用一个随机超平面来切割数据空间, 每切一次便可以生成两个子空间。接着继续用一个随机超平面来切割每个子空间,循环下去,直到每个子空间里面只有一个数据点为止。那些密度很高的簇是需要被切很多次才能让子空间中只有一个数据点,但是那些密度很低的点的子空间则很快就被切割成只有一个数据点。如图7所示,黑色的点是异常点,被切几次就停到一个子空间;白色点为正常点,白色点聚焦在一个簇中。孤立森林检测到的异常边界为图7中红色线条,它能正确地检测到所有黑色异常点。

如图8所示,用iForest切割4个数据,b和c的高度为3,a的高度为2,d的高度为1,d最先被孤立,它最有可能异常。

图8.iForest切割过程


7.图

7.1 最大联通图

在无向图G中,若从顶点A到顶点B有路径相连,则称A和B是连通的;在图G中存在若干子图,其中每个子图中所有顶点之间都是连通的,但不同子图间不存在顶点连通,那么称图G的这些子图为最大连通子图。


如图9所示,device是设备id,mbr是会员id,节点之间有边表示设备上有对应的会员登录过,容易看出device_1、device_2、device_3、device_4是同人,可以根据场景用于判断作弊,常用于挖掘团伙作弊。

图9.最大联通图结果

最大联通图的前提条件是每条边必须置信。适用场景:找所有连通关系。当数据中存在不太置信的边时,需要先剔除脏数据,否则会影响最大联通图的效果。

7.2 标签传播聚类

标签传播图聚类算法是根据图的拓扑结构,进行子图的划分,使得子图内部节点的连接较多,子图之间的连接较少。标签传播算法的基本思路是节点的标签依赖其邻居节点的标签信息,影响程度由节点相似度决定,通过传播迭代更新达到稳定。图10中的节点经标签传播聚类后将得2个子图,其中节点1、2、3、4属于一个子图,节点5、6、7、8属于一个子图。

图10.标签传播聚类算法的图结构

标签传播聚类的子图间可以有少量连接。适用场景:节点之间“高内聚低耦合”。图10用最大联通图得1个子图,用标签传播聚类得2个子图。

8.行为序列(马尔科夫链)

如图11所示,用户在搜索引擎上有5个行为状态:页面请求(P),搜索(S),自然搜索结果(W),广告点击(O),翻页(N)。状态之间有转移概率,由若干行为状态组成的一条链可以看做一条马尔科夫链。

图11.用户行为状态图

统计正常行为序列中任意两个相邻的状态,然后计算每个状态转移到其他任意状态的概率,得状态转移矩阵。针对每一个待检测用户行为序列,易得该序列的概率值,概率值越大,越像正常用户行为。

9.有监督模型

上述方法都是无监督方法,实现和理解相对简单。但是由于部分方法每次使用较少的特征,为了全方位拦截作弊,需要维护较多策略;另外上述部分方法组合多特征的效果取决于人工经验。而有监督模型能自动组合较多特征,具备更强的泛化能力。

9.1 机器学习模型GBDT

样本:使用前面的无监督方法挖掘的作弊样本作为训练样本。如果作弊样本仍然较少,用SMOTE或者GAN生成作弊样本。然后训练GBDT模型,用转化数据评估模型的效果。

9.2 深度学习模型Wide&Deep

Wide&Deep通过分别提取wide特征和deep特征,再将其融合在一起训练,模型结构如图12所示。wide是指高维特征和特征组合的LR。LR高效、容易规模化(scalable)、可解释性强。出现的特征组合如果被不断加强,对模型的判断起到记忆作用。但是相反的泛化性弱。

deep则是利用神经网络自由组合映射特征,泛化性强。deep部分本质上挖掘一些样本特征的更通用的特点然后用于判断,但是有过度泛化的风险。

算法通过两种特征的组合去平衡记忆(memorization)和泛化( generalization)。

为了进一步增加模型的泛化能力,可以使用前面的无监督方法挖掘的作弊样本作为训练样本,训练Wide&Deep模型识别作弊。

图12.Wide&Deep模型


10.其他问题

10.1 常用选择阈值的思路

上述各种方法都需要计算异常阈值,可以用下述思路先选阈值,再用转化数据验证该阈值的合理性。

a.无监督方法:使用分位点定阈值、找历史数据的分布曲线的拐点;

b.有监督模型:看验证集的准召曲线


10.2 非高斯分布转高斯分布

有些特征不符合高斯分布,那么可以通过一些函数变换使其符合高斯分布,以便于使用上述统计方法。常用的变换函数:,其中c为非负常数;,c为0-1之间的一个分数。

参考文献:

[1] Charu C, Aggarwal, et al. Outlier Analysis Second Edition, Springer.2016

[2] Varun Chandola, Arindam Banerjee, et al. Anomaly Detection: A survey,ACM Computing Surveys. 2009

[3] Kalyan Veeramachaneni, Ignacio Arnaldo, et al. AI2: Training abig data machine to defend, In Proc. HPSC and IDS. 2016

[4] Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou, et al. Isolationforest, ICDM. 2008

[5] Cheng H T, Koc L, Harmsen J, et al. Wide & Deep Learning forRecommender Systems, ACM Computing Surveys. 2016

[6] SMOTE: Synthetic Minority Over-sampling Technique, JAIR. 2002

科普:QUIC协议原理分析

转载自:https://zhuanlan.zhihu.com/p/32553477

作者介绍:罗成,腾讯资深研发工程师。目前主要负责腾讯 stgw(腾讯安全云网关)的相关工作,整体推进腾讯内部及腾讯公有云,混合云的七层负载均衡及全站 HTTPS 接入。对 HTTPS,SPDY,HTTP2,QUIC 等应用层协议、高性能服务器技术、云网络技术、用户访问速度、分布式文件传输等有较深的理解。

本文主要介绍 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. 前向冗余纠错。

为什么需要 QUIC

从上个世纪 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 协议,完全避开了操作系统和中间设备的限制。

QUIC 核心特性连接建立延时低

0RTT 建连可以说是 QUIC 相比 HTTP2 最大的性能优势。那什么是 0RTT 建连呢?这里面有两层含义。

  1. 传输层 0RTT 就能建立连接。
  2. 加密层 0RTT 就能建立加密连接。
图 1 HTTPS 及 QUIC 建连过程

比如上图左边是 HTTPS 的一次完全握手的建连过程,需要 3 个 RTT。就算是 Session Resumption[14],也需要至少 2 个 RTT。

而 QUIC 呢?由于建立在 UDP 的基础上,同时又实现了 0RTT 的安全握手,所以在大部分情况下,只需要 0 个 RTT 就能实现数据发送,在实现前向加密 [15] 的基础上,并且 0RTT 的成功率相比 TLS 的 Sesison Ticket[13] 要高很多。

改进的拥塞控制

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 重传的歧义问题。

图 2 Tcp 重传歧义性

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

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

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

图 3 Quic 重传没有歧义性

如上图所示,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 按照顺序组织起来,交给应用程序处理。

图 4 Stream Offset 保证有序性

不允许 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 计算:

而 Quic 计算如下:

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

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

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

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

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

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

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

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

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

图 5 Quic Flow Control

针对 Stream:

针对 Connection:

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

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

没有队头阻塞的多路复用

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

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

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

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

图 6 HTTP2 队头阻塞

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

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

图 7 TLS 队头阻塞

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 队头阻塞。
图 8 QUIC 多路复用时没有队头阻塞的问题

当然,并不是所有的 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]。

参考线索

[1]. https://www.chromium.org/quic

[2]. https://docs.google.com/document/d/1gY9-YNDNAB1eip-RTPbqphgySwSNSDHLq9D5Bty4FSU/edit

[3]. E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.3”, draft-ietf-tls-tls13-21, https://tools.ietf.org/html/draft-ietf-tls-tls13-21, July 03, 2017

[4]. Adam Langley,Wan-Teh Chang, “QUIC Crypto”,https://docs.google.com/document/d/1g5nIXAIkN_Y-7XJW5K45IblHd_L2f5LTaDUDwvZ5L6g/edit, 20161206

[5]. https://www.multipath-tcp.org/

[6]. Ha, S., Rhee, I., and L. Xu, “CUBIC: A New TCP-Friendly High-Speed TCP Variant”, ACM SIGOPS Operating System Review , 2008.

[7]. M. Belshe,BitGo, R. Peon, “Hypertext Transfer Protocol Version 2 (HTTP/2)”, RFC 7540, May 2015

[8]. M. Mathis,J. Mahdavi,S. Floyd,A. Romanow,“TCP Selective Acknowledgment Options”, rfc2018, https://tools.ietf.org/html/rfc2018, October 1996

[9]. V. Paxson,M. Allman,J. Chu,M. Sargent,“Computing TCP’s Retransmission Timer”, rfc6298, https://tools.ietf.org/html/rfc6298, June 2011

[10]. R. Peon,H. Ruellan,“HPACK: Header Compression for HTTP/2”,RFC7541,May 2015

[11]. M. Scharf, Alcatel-Lucent Bell Labs, S. Kiesel, “Quantifying Head-of-Line Blocking in TCP and SCTP”, https://tools.ietf.org/id/draft-scharf-tcpm-reordering-00.html, July 15, 2013

[12]. Ilya Grigorik,“Optimizing TLS Record Size & Buffering Latency”, https://www.igvita.com/2013/10/24/optimizing-tls-record-size-and-buffering-latency/, October 24, 2013

[13]. J. Salowey,H. Zhou,P. Eronen,H. Tschofenig, “Transport Layer Security (TLS) Session Resumption without Server-Side State”, RFC5077, January 2008

[14]. Dierks, T. and E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.2”, RFC 5246, DOI 10.17487/RFC5246, August 2008, <http://www.rfc-editor.org/info/rfc5246>.

[15]. Shirey, R., “Internet Security Glossary, Version 2”, FYI , RFC 4949, August 2007

[16]. 罗成,“HTTPS性能优化”, http://www.infoq.com/cn/presentations/performance-optimization-of-https,February.2017

[17]. Postel, J., “Transmission Control Protocol”, STD 7, RFC793, September 1981.

[18]. J. Postel,“User Datagram Protocol”, RFC768,August 1980

[19]. Q. Dang, S. Santesson,K. Moriarty,D. Brown.T. Polk, “Internet X.509 Public Key Infrastructure: Additional Algorithms and Identifiers for DSA and ECDSA”,RFC5758, January 2010

[20]. Bassham, L., Polk, W., and R. Housley, “Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile”, RFC 3279, April 2002

[21]. D.Cooper,S.Santesson, S.Farrell,S. Boeyen,R. Housley,W.Polk, “Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile”, RFC5280, May 2008

[22]. M. Allman,V. Paxson,E. Blanton, “TCP Congestion Control”,RFC5681, September 2009

[23]. Robbie Shade, “Flow control in QUIC”, https://docs.google.com/document/d/1F2YfdDXKpy20WVKJueEf4abn_LVZHhMUMS5gX6Pgjl4/edit#, May, 2016,

[24]. ianswett , “QUIC fec v1”, https://docs.google.com/document/d/1Hg1SaLEl6T4rEU9j-isovCo8VEjjnuCPTcLNJewj7Nk/edit#heading=h.xgjl2srtytjt, 2016-02-19

[25]. D.Borman,B.Braden,V.Jacobson,R.Scheffenegger, Ed. “TCP Extensions for High Performance”,rfc7323, https://tools.ietf.org/html/rfc7323,September 2014

[26]. 罗成,“WEB加速,协议先行”, https://zhuanlan.zhihu.com/p/27938635,july, 2017