限流算法

下面对常见的限流算法进行讨论。目前，常用的限流算法主要有三种：计数器法、滑动窗口算法、漏桶算法和令牌桶算法。下面分别介绍其原理。

1. 计数器法

计数器法是通过计数对到来的请求进行选择性处理。如系统限制一秒内最多有X个请求，则在该秒时间内对到来的请求进行计数，当计数达到X后，拒绝所有后续请求。直到下一秒开始，对计数器进行清空。该方法的主要弊端是会造成所谓的“突刺现象”：若请求的产生并不均匀（如在某一秒的前0.01秒内就产生了X个请求），则会造成在后续的大部分时间内无法处理新的请求。

2. 滑动窗口算法

将时间窗口划分为多个子窗口，每个子窗口内限定请求的数量，例如每秒钟最多允许处理100个请求，每0.1秒钟内最多允许处理10个请求。这种算法可以更平滑地限制请求的数量。

3. 漏桶算法

漏桶算法是在计数器算法的基础上，为了处理“突刺现象”提出的一种限流算法。该算法将所有到来的请求保存入一个队列（漏桶）中，并以恒定的速率从该队列中获取请求并加以执行。当队列大小达到限制（桶满）后，则拒绝后续请求。其示意图如下。

可以看出，该算法的核心思想是利用能够临时存储请求的“漏桶”，对请求的序列进行整形，从而对“突刺现象”进行处理。该算法的整形能力由漏桶的大小限制，当累计堆积的请求数量过多，超过漏桶大小时，整形就会失效，造成后续时间内到来的请求无法得到处理。此外，由于漏出的速率固定，漏桶算法在突发特性的流量场景下无法充分利用资源。

4. 令牌桶算法

令牌桶算法与漏桶算法看起来十分近似。该算法以恒定的速率创建令牌，并放入指定大小的队列（令牌桶）中，若令牌桶已满，则丢弃令牌。每个请求到来时，需要从令牌桶中尝试获取令牌，若拿到令牌，则消耗令牌进行操作；否则将该请求阻塞，直到获取到令牌。其原理图如下。

令牌桶具有“先消费后生产”的性质：当请求到来时，可以先使用令牌桶中初始已有的令牌进行操作，而后再生产令牌对令牌桶进行补充。
与漏桶算法相比，令牌桶算法对突发特性的流量具有更好的处理能力。由于其“先消费后生产”的性质，只要令牌桶中存在令牌，就可以进行对突发的请求进行处理，充分利用资源。此外，令牌桶算法可以通过改变令牌生成的速率，方便地对限流效果进行调节。

小结

漏桶算法与令牌桶算法看似相似，但设计思路与性能均存在较大差别。漏桶算法将请求作为桶的生产方，通过限制桶桶漏出的速度实现限流。令牌桶算法则是将请求作为桶的消费方，通过控制桶的注入速度而实现限流。两者各有特点，均被广泛使用，没有一定的优劣之分。
下表总结了两者的差异：

	限流思路	优点	缺点
漏桶算法	限制桶的流出速度	能够严格控制请求处理速率上限	在存在突发特性流量时可能无法充分利用系统资源
令牌桶算法	限制桶的输入速度	可处理具有突发特性流量易于调节	无法严格控制瞬时请求处理速率

5. QoS

有三大主流QoS模型，Best-Effort服务模型、IntServ预留资源模型、DiffServ差分服务模型‘

5.1 Best-Effort

Best-Effort是最简单的QoS服务模型，用户可以在任何时候，发出任意数量的报文，而且不需要通知网络。提供Best-Effort服务时，网络尽最大的可能来发送报文，但对时延、丢包率等性能不提供任何保证。Best-Effort服务模型适用于对时延、丢包率等性能要求不高的业务，是现在Internet的缺省服务模型，它适用于绝大多数网络应用，如FTP、E-Mail等

5.2 IntServ

IntServ模型是指用户在发送报文前，需要通过信令（Signaling）向网络描述自己的流量参数，申请特定的QoS服务。网络根据流量参数，预留资源以承诺满足该请求。在收到确认信息，确定网络已经为这个应用程序的报文预留了资源后，用户才开始发送报文。用户发送的报文应该控制在流量参数描述的范围内。网络节点需要为每个流维护一个状态，并基于这个状态执行相应的QoS动作，来满足对用户的承诺。
IntServ模型使用了RSVP（Resource Reservation Protocol）协议作为信令，在一条已知路径的网络拓扑上预留带宽、优先级等资源，路径沿途的各网元必须为每个要求服务质量保证的数据流预留想要的资源，通过RSVP信息的预留，各网元可以判断是否有足够的资源可以使用。只有所有的网元都给RSVP提供了足够的资源，“路径”方可建立。

5.3 DiffServ

DiffServ模型的基本原理是将网络中的流量分成多个类，每个类享受不同的处理，尤其是网络出现拥塞时不同的类会享受不同级别的处理，从而得到不同的丢包率、时延以及时延抖动。同一类的业务在网络中会被聚合起来统一发送，保证相同的时延、抖动、丢包率等QoS指标。
Diffserv模型中，业务流的分类和汇聚工作在网络边缘由边界节点完成。边界节点可以通过多种条件（比如报文的源地址和目的地址、ToS域中的优先级、协议类型等）灵活地对报文进行分类，对不同的报文设置不同的标记字段，而其他节点只需要简单地识别报文中的这些标记，即可进行资源分配和流量控制。
与Intserv模型相比，DiffServ模型不需要信令。在DiffServ模型中，应用程序发出报文前，不需要预先向网络提出资源申请，而是通过设置报文的QoS参数信息，来告知网络节点它的QoS需求。网络不需要为每个流维护状态，而是根据每个报文流指定的QoS参数信息来提供差分服务，即对报文的服务等级划分，有差别地进行流量控制和转发，提供端到端的QoS保证。DiffServ模型充分考虑了IP网络本身灵活性、可扩展性强的特点，将复杂的服务质量保证通过报文自身携带的信息转换为单跳行为，从而大大减少了信令的工作，是当前网络中的主流服务模型。

5.4 基于DiffServ模型的QoS组成

基于Diffserv模型的QoS业务主要分为以下几大类：
（1）报文分类和标记
要实现差分服务，需要首先将数据包分为不同的类别或者设置为不同的优先级。报文分类即把数据包分为不同的类别，可以通过MQC配置中的流分类实现。报文标记即为数据包设置不同的优先级，可以通过优先级映射和重标记优先级实现。不同的报文使用不同的QoS优先级，例如VLAN报文使用802.1p，IP报文使用DSCP，MPLS报文使用EXP。
（2）流量监管、流量整形和接口限速
流量监管和流量整形可以将业务流量限制在特定的带宽内，当业务流量超过额定带宽时，超过的流量将被丢弃或缓存。其中，将超过的流量丢弃的技术称为流量监管，将超过的流量缓存的技术称为流量整形。接口限速分为基于接口的流量监管和基于接口的流量整形。
（3）拥塞管理和拥塞避免
拥塞管理在网络发生拥塞时，将报文放入队列中缓存，并采取某种调度算法安排报文的转发次序。而拥塞避免可以监督网络资源的使用情况，当发现拥塞有加剧的趋势时采取主动丢弃报文的策略，通过调整流量来解除网络的过载。

小结

	优点	缺点
Best-Effort	实现机制简单	对不同业务流不能进行区分对待
IntServ	可提供端到端QoS服务，并保证带宽、延迟	需要跟踪和记录每个数据流的状态，实现较复杂，且扩展性较差，带宽利用率较低
DiffServ	不需跟踪每个数据流状态，资源占用少，扩展性较强	且能实现对不同业务流提供不同的服务质量, 需要在端到端每个节点都进行手工部署，对人员能力要求较高