限速之令牌桶理解

限速的目的是防止有人恶意占用带宽，在保证用户正常业务前提下，保证整个网络不发生拥塞，提升整个网络的服务质量。

在高并发的场景下，我们的优化和保护系统的方式通常有：多级缓存、资源隔离、熔断降级、限流等等。

网络限速有很多种方式，比如网卡(接口)限速，队列限速，meter表限速。其中meter表限速是颇具代表性的限速方式。

常用的流量限速有两种技术：

可以监督不同流量进入网络的速率，对超出部分的流量进行“惩罚”，使进入的流量被限制在一个合理的范围之内，从而保护整个网络资源和用户的利益。

对于网络传输而言，丢包带来的成本是很高的，因为一些重要的数据包丢失后，是需要 “重传” 的，而 “重传” 太多，来回反复会增加了数据传输的延时，也会进一步恶化网络负荷，最终极大地降低了传输的效率。

需要从根本上尽可能地减少 “丢包” 的产生，简单来说，就是控制单位时间内送入网络传输的数据量，尽量平滑且不要超过网络带宽承载能力。

为了避免丢包，我们需要尽可能地将数据 “平滑” 地送入网络中，因此，“流量整形” 在此派上了用场，它作用于 “发送模块”，目标是调整数据传输的平均速率，防止突发性的流量暴增导致网络拥塞和丢包。

流量整形通常是为了使报文速率与下游设备相匹配。当从高速链路向低速链路传输数 据或发生突发流量时，带宽会在低速链路出口处出现瓶颈，导致数据丢失严重。这种 情况下，需要在进入低速链路的设备出口处进行流量整形；所以流量整形是一种主动调整流量输出速率的措施，其作用是限制流量与突发，使这类报文以比较均匀的速率向外发送。

流量整形是用于限制某个或某些队列的输出速率，超速的报文不是直接丢弃，而是暂时存在缓存里，等空闲了还是会输出，只有缓存满了之后才会丢弃。流量整形将上游不规整的流量进行削峰填谷，使流量输出比较平稳，从而解决下游设备的拥塞问题。

单速单桶技术的基于流的队列整形；流量整形通常使用缓冲区和令牌桶来完成：

具体处理流程如下：

使用流量整形的效果

通过在上游设备的接口出方向配置流量整形，将上游不规整的流量进行削峰填谷， 输出一条比较平整的流量（如图 2-23），从而解决下游设备的瞬时拥塞问题。

流量监管和流量整形的对比

对于流量监管技术，当流量速率达到所配置的最大速率时，将丢弃（或重新标记）超额流量。其结果是，输出速率显示为带有波峰和波谷的锯齿状。相对于比较重要的突发流量，如果采用令牌桶技术可能导致重要数据的丢失；

采用流量整形技术，将超出的流量来不及转发的数据存放起来，在端口有带宽时再转发。流量整形在队列中保留额外的数据包，然后对额外的数据包进行调度，以便随时间的增加稍后传输。流量整形的结果是一个平滑的数据包输出速率。

既然要限速，那首先要解决测量速度的问题。以下介绍测试方法。

QoS是网络中提供差异化服务的重要方法，它通过区分不同的流量和优先级，为不同的应用和使用者提供不同质量的网络服务，比如，金融网络，可能购买了专线，要求延迟小，更不能忍受丢包，自然优先级就高些；又比如网络直播和游戏，对于网络的延迟要求非常高，而普通的上网用户则没有这么高的要求；

计数器算法

计数器算法简单粗暴，设置 1s 内的请求数阈值 qps。比如 qps = 100，从第一个请求进来开始计时，并将计数值置 0，在接下来的1s 内，每来一个请求，就把计数值加 1，如果计数值达到100，那后面的请求就全部拒绝。等到 1s 结束，把计数恢复为 0，重新开始计数。

缺点:

如果在某个 1s 内的前 10ms，已经通过了100个请求，那后面的 990ms，就只能眼巴巴的把请求拒绝。这种现象被称为突刺现象。

漏桶算法

为了消除突刺现象，可以设置一个漏桶(漏斗)。漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出；

请求进来，相当于水倒入漏桶，然后从下面小口缓慢匀速的流出，不管上面的流量多大，下面流量始终不变。

所以我们需要设置两个参数：桶最大容量 cap 和漏出速率 r。若当前进来的请求数达到 cap，即漏桶满了，那后面进来的请求就拒绝掉；若 r = 50，则表示每秒处理 50 个请求，即 20ms 处理一个请求。

实现的话，可以用队列作为漏桶，然后拿另外一个线程以速率 r 从队列中拿请求来处理。一次可以拿多个请求实现并发。

缺点

无法应对短时间的突发流量。漏桶算法的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉（也就是所谓的溢出）。

令牌桶算法生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。

令牌桶算法

令牌桶算法中想象了一种令牌和令牌桶。令牌桶容量为 b，令牌以速率 r 产生，比如 r = 2 表示每秒产生 2 个令牌，即每 500ms 产生一个。当大量请求进来时，每个请求会消耗一个令牌，当令牌被消耗时，让后面的请求处于等待状态或直接将其拒绝掉。是不是很简单？实现的话，不需要实现令牌，也不需要实现令牌桶，只需要有一个变量记录令牌数，当请求进来时，判断令牌数是否为零，来决定处理还是拒绝，若处理的话要让令牌数 -1。另外需要一个线程来只要令牌数小于 b 就以 r 的速率让令牌数 +1。

令牌桶（Token-Bucket）是目前最常采用的一种流量测量方法，用来评估流量速率是否超过了规定值。这里的令牌桶是指网络设备的内部存储池，而令牌则是指以给定速率填充令牌桶的虚拟信息包。

令牌桶可以看作是一个存放令牌的容器，预先设定一定的容量。

系统按设定的速度向桶中放置令牌，当桶中令牌满时，多余的令牌溢出。

说明：

令牌桶只是一种流量测量方法，并不能对流量进行过滤或采取某种措施，比如说丢弃数据包等，这些操作由其他功能完成。

令牌桶中装的是令牌而不是分组。

如上所示，匀速的产生令牌，往桶里面丢；每次请求来，看是否有多余的令牌。如果有，获取令牌执行正常业务；如没有，丢包限速。

令牌桶算法测速限速的原理就是：每个符合规则的报文，只有在从桶中拿到令牌后才能发送出去。拿不到令牌，则丢弃；

1）桶中的令牌是怎么来的呢？

可以自己设置桶中令牌生成的速度，也就是通过设置生成令牌的生成速度来定义发送数据包的速度。

通常为了解决数据包突发性问题等，会使用2个令牌桶，根据他们各自生成令牌的速度，分为单速三色标记和双速三色标记。

RFC 中定义了两种令牌桶算法：

单速率三色标记（single rate three color marker，srTCM，RFC2697定义，或称为单速双桶算法）算法，主要关注报文尺寸的突发。 双速率三色标记（two rate three color marker，trTCM，RFC2698定义，或称为双速双桶算法）算法，主要关注速率的突发。

两种算法的评估结果都是为报文打上红、黄、绿三种颜色的标记，所以称为“三色标记”。这两种算法都允许流量在一定程度上突发，但单速率三色标记关注报文尺寸的突发，而双速率三色标记则关注速率上的突发。单速率较双速率实现简单，成为目前业界比较常用的流量评估方式。

QoS 会根据报文的颜色，设置报文的丢弃优先级；两种算法都可以工作于色盲模式和色敏模式下。

令牌桶算法，顾名思义，系统按照一定的投放方式向桶中放置令牌，当桶中令牌满时，多出的令牌溢出，桶中令牌不再增加。如下图所示。

当有需要限速的数据包通过的时候，依据数据报文的长度算出需要取走的令牌数N（比如 限速的bps值和桶中的令牌数N对应）。

如果桶中的令牌数量大于N，那么此数据包就顺利过了限速测试。

反之，此数据包就没有通过限速测试，于是就将报文进行丢弃处理（大多数情况下是如此，也可以进行其他处理，依赖用户程序的设计）。

系统按照一定的投放方式向桶中放置令牌，当桶中令牌满时，多出的令牌溢出，桶中令牌不再增加。存在2种投放方式去投放桶中令牌：

1）方式一：设置定时器，在定时器的回调函数中周期性的放入令牌。

周期性的添加，定时器的时间间隔就是令牌桶的容量与添加速率的比值：△t=CBS/CIR，每次添加的令牌数为 CBS 个。

解析： 可以利用dpdk的定时器，比如设置每1秒，call以下回调函数，放入令牌1 * N个令牌。

缺陷1： 如果在这一秒钟内，如果前0.5秒的突发流量将令牌都消耗完了，那么后0.5秒的报文不就全部丢掉了。有人说，可以将这个间隔设置小一点啊，比如每1/1000秒放入N/1000个令牌。但是问题在于，这个间隔到底是多少好呢？

比如，粒度细化到 每隔 1s/CIR 时间添加一个令牌;(1s可以转化为 cycles，即每个n个cycles往令牌桶中添加一个令牌；)

缺陷2： 无法处理突发流量，原因见方式3。

注：其实也没有必要单独搞一个真的定时器，或者一个单独的线程进行投放令牌；只需要在每次数据包过桶前，判断下当前时间和上次投放桶令牌时间的差值diff_cycles 是否满足 period_cycles 即可，来决定是否投放令牌；

2）方式2： 按时间间隔放入

一次性添加，添加令牌的数量是△t×CIR(△t 是当前时间与上次添加令牌的时间之差)，且是一次添加完毕，并不是按照一定速率添加。

解析： 按时间间隔放入，假设当前报文和上一个报文的时间间隔为1ms秒，那么放入1/1000 * N 个令牌。这种方式的好处在于针对于每个数据包的处理前都会放入令牌，分散令牌的放入。

缺陷： 无法处理突发流量，原因见方式3

初始化桶内的令牌数为N，限速为 rate Bps， 即对应关系为 N1：rate1 = N2: rate2;

一个数据包，包长为 len：则 N1:rate1 = N2: len, 所以 N2 = len * (N1/rate1)

3) 方式2改进

背景： 方式1和方式2都面临一个问题，如果有突发流量，那么可能在极短的时间内消耗全部的令牌；前期短期内大量的流量被放行，从而对系统造成威胁；后续的时间内，集中丢包。

解析： 当出现丢包后，那么在接下来的200us内的前64个报文都会被丢弃（即200us内丢弃的是64个包，而不是大量的包）。对于200us和64这个值都是经验值，可以在真实场景中进行调优。

缺陷： 这个方式降低了突发流量对系统的威胁，但是会对限速的准确性有一定的影响，通过测试可以证明。

注：方式2和方式3可以协作运行，比如用方式3先进行防攻击限速，然后再用方式2进行精确限速。

什么是CAR

流量监管采用承诺访问速率CAR（Committed Access Rate）来对流量进行控制。CAR利用令牌桶来衡量每个数据报文是超过还是遵守所规定的报文速率。

CAR主要有两个功能：

流量速率限制：通过使用令牌桶对流经端口的报文进行度量，使得在特定时间内只有得到令牌的流量通过，从而实现限速功能。

流分类：通过令牌桶算法对流量进行测量，根据测量结果给报文打上不同的流分类内部标记（包括服务等级与丢弃优先级）。

CAR的处理流程

当报文到来时，首先检查端口的匹配规则，如果匹配上了，则进行速率控制，报文进入令牌桶中进行流量速率评估。

令牌桶评估后，报文被标记为红、黄、绿三种颜色。红色表示报文速率过大，不符合规定；黄色表示虽然不符合规定但允许临时的突发，绿色表示符合规定。

报文标为红色的直接丢弃，黄色则重新标记后转发，绿色则直接转发。

CAR的报文标记过程

CAR中令牌添加方式是报文触发，添加令牌的数量是CIR×当前时间与上次添加令牌的时间之差。向桶内注入令牌后，再判断桶内的令牌数是否满足传送该报文的要求。

CAR支持单速单桶、单速双桶、双速双桶的标记方式。

单速双桶采用RFC2697定义的单速三色标记器srTCM（Single Rate Three Color Marker）算法对流量进行测评，根据评估结果为报文打颜色标记，即绿色、黄色和红色。

如上图所示，为方便描述将两个令牌桶称为C桶和E桶（意为Excess超额桶），用Tc和Te表示桶中的令牌数量。

CIR（Committed Information Rate）：承诺信息速率，单位是 bit/s，表示向C桶中投放令牌的速率；

CBS（Committed Burst Size）：承诺突发尺寸，单位是 bit，即为令牌桶的容量（深度），即C桶瞬间能够通过的承诺突发流量，用来定义在部分流量速率超 过CIR之前的最大突发流量；承诺突发尺寸必须大于报文的最大长度（最大时一个分组可以领取桶中的全部令牌）。CBS越大，表示所允许的突发量越大。

EBS（Excess Burst Size）：超额突发尺寸，表示E桶的容量，即E桶瞬间能够通过的超出突发流量，用来定义在所有流量速率超过CIR之前的 最大突发量；

B: 对于到达的报文，用B表示报文的大小：

C 桶容量为CBS， E 桶容量为EBS，总容量是CBS+EBS。如果不允许有突发流量，EBS 则设置成 0。

当 EBS≠0 时，称为单速双桶。

当 EBS=0，E桶的令牌数始终为 0，相当于只使用了一个令牌桶——C桶，这种情况也称为单速单桶。

单速双桶令牌添加方式比较简单，先以CIR的速率往C桶中添加令牌，当C桶容 量到达 CBS 后（C桶满了），再以相同的速率往E 桶中添加令牌（E 桶的令牌用做 以后临时超过CIR的突发流量），当E桶容量到达 EBS 后（E 桶也满了），则新产 生的令牌将会被丢弃。 初始状态下，C 桶和 E桶都是满的。

系统按照CIR速率向桶中投放令牌：

若Tccir == 0) || ((params->cbs == 0) && (params->ebs == 0))) { return -2; } /* Initialize srTCM run-time structure */ hz = rte_get_tsc_hz(); m->time = rte_get_tsc_cycles(); m->tc = m->cbs = params->cbs; m->te = m->ebs = params->ebs; rte_meter_get_tb_params(hz, params->cir, &m->cir_period, &m->cir_bytes_per_period); RTE_LOG(INFO, METER, "Low level srTCM config: \n" "\tCIR period = %" PRIu64 ", CIR bytes per period = %" PRIu64 "\n", m->cir_period, m->cir_bytes_per_period); return 0; } /* 每隔 1s/CIR 时间添加一个令牌; 1s可以转化为 cycles，即每个n个cycles往令牌桶中添加一个令牌； 一个令牌可以理解为1B; */ static void rte_meter_get_tb_params(uint64_t hz, uint64_t rate, uint64_t *tb_period, uint64_t *tb_bytes_per_period) { double period = ((double) hz) / ((double) rate); if (period >= RTE_METER_TB_PERIOD_MIN) { *tb_bytes_per_period = 1; *tb_period = (uint64_t) period; } else { *tb_bytes_per_period = (uint64_t) ceil(RTE_METER_TB_PERIOD_MIN / period); *tb_period = (hz * (*tb_bytes_per_period)) / rate; } } PARAMS： struct rte_meter_srtcm_params app_srtcm_params[] = { {.cir = 1000000 * 46, .cbs = 2048, .ebs = 2048}, }; 桶中添加令牌以及流量过桶

针对每个包，都会进行颜色判断，色盲模式的判断比较简单，对应的函数如下：

多线程处理的基本思想，如下图所示：

详细流程

下面将用流程图的形式来描述多线程令牌桶的实现。在最后会介绍这种令牌桶算法可能存在的问题。

主要涉及到 

1）报文平滑优化；通过借贷方式

2）dpdk 除法的优化；

3）引入扩大因子 解决 CIR太大时 cir_period 过小的问题

参见：https://blog.csdn.net/armlinuxww/article/details/70212790

平滑策略，如下所示

背景：

比如一条长连接，由于限速，后续长时间（比如200ms），没有一个包可以通过；这样会流量不太平滑；

解决：

理想状态，比如对于一个长连接，每隔200ms，尽可能的保证至少有一个数据包可以通过；

那么就可以基于连接的五元组进行hash，然后以hash值在bitmap中查找；

没有找到，则首次运行通过，不检查 pkt_len 和 tc，tc-= pkt_len；

查找到，则判断 pkt_len 和 tc 的大小关系，决定是否通过；

每隔200ms，将 bitmap 清空；

注：bitmap标志位需要定期清理的；

背景：第一个包被丢弃，client重传，有可能继续被丢弃，可以设置重传的包可以通过；

解决：基于五元组+seq进行hash，然后设置bitmap的标志位，如果该标志位设置过了，则允许通过；注：bitmap标志位需要定期清理的；

解决：基于五元组进行hash，查看bitmap，没有设置，则允许通过；注：bitmap标志位需要定期清理的；

限流规则包含三个部分：时间粒度，接口粒度，最大限流值。限流规则设置是否合理直接影响到限流是否合理有效。

我们既可以选择 1 秒钟不超过 1000 次，也可以选择 10 毫秒不超过 10 次，还可以选择 1 分钟不超过 6 万次；

虽然看起这几种限流规则都是等价的，但过大的时间粒度会达不到限流的效果，比如限制 1 分钟不超过 6 万次，就有可能 6 万次请求都集中在某一秒内；

相反，过小的时间粒度会削足适履导致误杀很多本不应该限流的请求，因为接口访问在细时间粒度上随机性很大。

所以，尽管越细的时间粒度限流整形效果越好，流量曲线越平滑，但也并不是越细越合适。

对于访问量巨大的接口限流，比如秒杀，双十一，这些场景下流量可能都集中在几秒内，QPS 会非常大，几万甚至几十万，需要选择相对小的限流时间粒度。相反，如果接口 QPS 很小，建议使用大一点的时间粒度，比如限制 1 分钟内接口的调用次数不超过 1000 次；

基于DPDK的多核令牌桶算法

单速双桶、双速双桶原理

CAR

流量评估与令牌桶技术

QoS 技术白皮书

QOS-HCIE 知乎