mysql大流量，高并发问题——令牌桶算法

mysql 大流量，高并发问题

由于mysql是一个连接给一个线程，当并发高的时候，每秒需要几百个甚至的线程，其中创建和销毁线程还好说，大不了多耗费点内存，线程缓存命中率下降还有创建销毁线程的性能增加问题---这个问题不是特别大，重点是mysql底层瞬间处理这几百个线

mysql大流量，高并发问题——令牌桶算法

mysql大流量，高并发问题——令牌桶算法

什么是漏桶算法和令牌桶算法

什么是令牌桶

在我们讨论突发数据量之前，我们首先要理解令牌桶的概念。令牌桶本身没有丢弃

和优先级策略，

令牌桶是这样工作的：

1． 令牌以一定的速率放入桶中。

2． 每个令牌允许源发送一定数量的比特。

3． 发送一个包，流量调节器就要从桶中删除与包大小相等的令牌数。

4． 如果没有足够的令牌发送包，这个包就会等待直到有足够的令牌（在整形

器的情况下）或者包被丢弃，也有可能被标记更低的DSCP（在策略者的情况下）。

5． 桶有特定的容量，如果桶已经满了，新加入的令牌就会被丢弃。因此，在

任何时候，源发送到网络上的突发数据量与桶的大小成比例。令牌桶允许突发，

但是不能超过限制。

Cisco IOS 流量策略（Traffic Polrs）

IOS支持两种流量策略：

1． 传统的Cisco流量策略：CAR承诺接入速率，使用命令

Router(config-if)#rate-limit {input | output} CIR (bps)

Bc（burst-normal） Be(burst-max) conform-action action exceed-action action

2． 新型的Cisco流量策略：基于类的策略（Class-based polr），使用模

块化Qos CLI（MQC）语法。可以使用MQC命令建立流量策略并把策略应用到接口。

一个流量策略包括一个流量类（traffic class）和一个或多个Qos特性。Policy

命令用来执行流量策略特性，它指定了一个流量类所需要的速率，超过这个速

率Qos系统会立刻执行一个作，标准的作是丢弃或重置包头的DSCP字段。Policy

命令的语法是：

pol cir Bc Be conform exceed

violate

理解Bc和Be

对于超额的数据包，流量策略并不会把它们缓存稍候转发，只有整形器（shaper）

会这样做。流量策略只执行一个发送或不发送的策略。因为不能缓存数据包，所以

在发生拥塞时，所能做的的方法就是通过配置适当的超额突发数据量Be来不那

么过分的丢弃数据包。这一点对理解流量策略使用Bc和Be来保证达到CIR是非常

重要的。

超额参数模仿路由器的通用缓存规则。The rule recommends configuring buffering

equal to the round-trip time bitrate to accommodate the outstanding TCP

windows of all connections in times of congestion.

突发参数 目的 公式

普通突发 · 执行标准的令牌桶 · 设置数量的令牌(尽管如

果Be>Bc的话可以借到令牌). · 决定令牌桶有多大，因为如果桶已经满了那么令

牌将被丢弃而不会再加入到桶中。 CIR [bps] (1 byte)/(8 bits) 1.5

seconds Note: 1.5 seconds is the typical round trip time.

超额突发 · 为令牌桶提供超额突发能力 · 如果Bc = Be那么不

支持超额突发 · 当Bc = Be，流量调节器就不能借令牌，当令牌不够时只能丢弃数

据包 两倍的Bc

对TCP流量的测试表明，Bc 和Be的数值应该近似等于配置的平均速率在两秒钟内

的流量。如果你想限制流量在1Mb，应该把Bc 设置在1-2Mb，Be在2-4Mb。

举个例子，如果我们想把输出速率限制在1.5Mbps，我们可以做一下步骤：

1． 把承诺速率从比特转换成字节，因为突发数据量的单位为字节。

1500000 bits / 8 bits = 187500 bytes

2． 使用标准的1.5秒往返时间（round-trip time）计算Bc

187500 bytes 1.5秒 = 281 bytes

3． 两倍的Bc为Be

281 bytes 2 = 560 bytes

使用命令

rate-limit input 1500000 281 560 conform-action {action}

exceed-action {action}

超额突发数据量

当数据包到达时可用的令牌数目小于包的大小，就可以使用超额突发数据量。包会

请求借用令牌。可以通过配置大于Bc的Be的数值来为令牌桶提供超额突发能力。

可以通过下面两个例子来理解Be。

个例子说明怎样配置CAR策略来允许所有的IP流量。在T3线路上提供

了便宜的20Mbps的子速率服务。用户只花费子速率带宽的金额，也可以按需要增加

带宽。CAR限制了用户可用的流量速率，用户只能使用规定的速率加上承诺的突发

数据量。可以适当的设置Be=32000。

intece hssi 0/0/0

rate-limit output 20000000 24000 32000 conform-action tranit

exceed-action drop

下一个例子，用户只能发送24000字节的突发数据量，所有超过限制的数据包都要

被丢弃，因为设置Bc=Be，数据包流不能通过超额突发能力来借用令牌。

intece Hssi0/0/0

rate-limit output 20000000 24000 24000 conform-action tranit

exceed-action drop

正确设置突发数据量的重要性

策略以字节为单位指定了突发数据量，基于类的策略（class-based polr）支持

小的突发数据量为1000字节，包括第二层包头。

突发数据量的目的是逐渐的丢弃数据包，就像RED那样，并且避免尾丢弃。设置足

够高的突发数据量对保证良好的吞吐量是非常重要的。

设置突发数据量时，考虑一下内容：

1． 如果突发数据量设置的过低，数据到达的速率将远远低于配置的速率。

2． 惩罚暂时突发对TCP流的吞吐量来说是相当不利的，具体情况请察看RFC

2001 and Random Early Detection (RED) gateways for Congestion Avoidance。

设置突发数据量来允许路由器容纳暂时突发。

3． 对离开接口的数据包的处理基于包的大小和桶中剩余的令牌数。

4． 在基于类的策略中，流量测量器不论接口是否拥塞都是激活的。每个包都

会经过令牌桶测量系统来决定是否符合配置的参数。

5． 如果数据突发量非常大而且非常突然，那么配置较高的超额突发数据量可

以保证超额令牌桶中存放较多的令牌。而且可以调整接口的MTU等于或大于突发数

据量大小。

允许的突发数据量数值

初，包括IOS12.0，rate-limit命令支持承诺和超额的突发数据量的范围是：

Router1(config-if)#rate-limit input 18000000 ?

<8000-2000000> Normal burst bytes

Router1(config-if)#rate-limit input 18000000 2000000 ?

<8000-8000000> Maximum burst bytes

Router1(config-if)#rate-limit input 18000000 2000000

IOS12.1增加了突发数据量的值：

7500-107(config)#intece atm 1/0/0

7500-107(config-if)#rate-limit output ?

<8000-2000000000> Bits per second

access-group Match access list

qos-group Match qos-group ID

Golang中的限速器 time/rate

在高并发的系统中，限流已作为必不可少的功能，而常见的限流算法有：计数器、滑动窗口、令牌桶、漏斗(漏桶)。其中滑动窗口算法、令牌桶和漏斗算法应用为广泛。

这里不再对计数器算法和滑动窗口作介绍了，有兴趣的同学可以参考其它相关文章。

非常很好理解，就像有一个漏斗容器一样，漏斗上面一直往容器里倒水(请求)，漏斗下方以 固定速率 一直流出(消费)。如果漏斗容器满的情况下，再倒入的水就会溢出，此时表示新的请求将被丢弃。可以看到这种算法在应对大的突发流量时，会造成部分请求弃用丢失。

可以看出漏斗算法能强行限制数据的传输速率。

令牌桶算法

从某种意义上来说，令牌算法是对漏斗算法的一种改进。对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突况。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。

令牌桶算法是指一个固定大小的桶，可以存放的令牌的个数也是固定的。此算法以一种 固定速率 不断的往桶中存放令牌，而每次请求调用前必须先从桶中获取令牌才可以。否则进行拒绝或等待，直到获取到有效令牌为止。如果桶内的令牌数量已达到桶的允许上限的话，则丢弃令牌。

Golang标准库中的限制算法是基于令牌桶算法(Token Bucket) 实现的，库名为对于限流器的消费方式有三种，分别为 Allow()、 Wait()和 Reserve()。前两种内部调用的都是Reserve() ,每个都对应一个XXXN()的方法。如Allow()是AllowN(t, 1)的简写方式。

主要用来限速控制并发，采用令牌池算法实现。

使用 NewLimiter(r Limit, b int) 函数创建限速器，令牌桶容量为b。初始化状态下桶是满的，即桶里装有b 个令牌，以后再以每秒往里面填充 r 个令牌。

允许声明容量为0的限速器，此时将会拒绝所有作。

// As a special case, if r == Inf (the infinite rate), b is ignored.

有一种特殊情况，就是 r == Inf 时，此时b参数将被忽略。

Limiter 提供了三个主要函数 Allow, Reserve, 和 Wait. 大部分时候使用Wait。其中 AllowN, ReserveN 和 WaitN 允许消费n个令牌。

每个方法都可以消费一个令牌，当没有可用令牌时，三个方法的处理方式不一样

AllowN方法表示，截止在某一时刻，目前桶中数目是否至少为n个。如果条件满足，则从桶中消费n个token，同时返回true。反之不消费Token，返回false。

使用场景：一般用在如果请求速率过快，直接拒绝请求的情况

输出

当使用Wait方法消费Token时，如果此时桶内Token数量不足(小于N)，那么Wait方法将会阻塞一段时间，直至Token满足条件。否则直接返回。

// 可以看到Wait方法有一个context参数。我们可以设置context的Deadline或者Timeout，来决定此次Wait的长时间。

输出

// 此方法有一点复杂，它返回的是一个Reservation类型，后续作主要针对的全是这个类型

// 判断限制器是否能够在指定时间提供指定N个请求令牌。

// 如果Reservation.OK()为true，则表示需要等待一段时间才可以提供，其中Reservation.Delay()返回需要的延时时间。

// 如果Reservation.OK()为false,则Delay返回InfDuration, 此时不想等待的话，可以调用 Cancel()取消此次作并归还使用的token

输出

限流算法介绍

高并发的处理有三个比较常用的手段，缓存，限流和降级。缓存的使用相信很多开发者都很了解了，诸如redis，memcache等工具都会活跃在我们的系统当中。但是如在某一时间段内出现了远超预想的流量访问到系统，例如在搞秒杀活动之类的，这样一来我们应该如何保护业务系统呢？

在参加一些秒杀活动的时候，我们可以看到，有时候会有 系统繁忙，请稍后再试

或者 请稍等 的提示，那这个系统就很可能是使用了限流的手段。

限流是限制系统的输入和输出流量，以达到保护系统的目的。而限流的实现主要是依靠限流算法，限流算法主要有4种：

1、固定时间窗口（计数器）；

2、滑动时间窗口；

3、令牌桶算法；

4、漏桶算法；

计数器就是统计记录单位时间内进入系统或者某一接口的请求次数，在限定的次数内的请求则正常接收处理，超过次数的请求则拒绝掉，或者改为异步处理。

设我们设定单位时间内进入系统的的请求数为100，如果有超过100个请求集中在刷新计数器的临界点前后进入系统，而且单位时间的粒度比较粗的话，那就容易误伤很多正常请求。

这个名称要跟TCP的窗口滑动区分开来，但是理解之后会发现其实也是有点相似。

计数器算法对流量的限制比较粗放，而滑动时间窗口的算法则是对流量进行更加平稳的控制。上面的计数器的单位时间是1分钟，而在使用滑动时间窗口，可以把1分钟分成6格，每格时间长度是10s，每一格又各自管理一个计数器，单位时间用一个长度为60s的窗口描述。一个请求进入系统，对应的时间格子的计数器便会+1，而每过10s，这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限，便会拒绝后面的请求。

漏桶算法，又称leaky bucket。下图是wiki上的漏桶图解：

一个系统处理请求，就像一个固定容量的水桶去溜进来的水，同时也让水流出去，但是它无法预见有多少水流进来和水流进来的速度，它只能够控制从桶底水流出去的速度，多出来的水，就只好让它从桶边流出去了。这个从桶底流出去的水就是系统正常处理的请求，从旁边流出去的水就是系统拒绝掉的请求。如此一来，我们只要系统单位时间内处理请求的速率就可以了，速率超过上限后的请求都给拒绝掉就可以了。

继续wiki图解。

令牌桶即是以一定速率生成token并放入桶中，请求进入系统需要先拿到token才能进行业务处理，无token的请求则拒绝掉。令牌桶算法实际上跟漏桶算法很相似，而实际使用中其实也不需要另起线程生成token，只需要把握好token生成速率和当前应该剩余的token数量即可。

在时间点刷新的临界点上，只要剩余token足够，令牌桶算允许对应数量的请求通过，而后刷新时间因为token不足，流量也会被限制在外，这样就比较好的控制了瞬时流量。因此，令牌桶算法也被广泛使用。

GTS的通用流量整形

流量整形(traffic shaping)典型作用是限制流出某一网络的某一连接的流量与突发，使这类报文以比较均匀的速度向外发送。流量整形通常使用缓冲区和令牌桶来完成，当报文的发送速度过快时，首先在缓冲区进行缓存，在令牌桶的控制下再均匀地发送这些被缓冲的文。