重庆网站建设咨询,电脑经销部开具网站建设费,wordpress sae 上传,yanderedev.wordpress下面对常见的限流算法进行讨论。目前#xff0c;常用的限流算法主要有三种#xff1a;计数器法、滑动窗口算法、漏桶算法和令牌桶算法。下面分别介绍其原理。
1. 计数器法
计数器法是通过计数对到来的请求进行选择性处理。如系统限制一秒内最多有X个请求#xff0c;则在该…下面对常见的限流算法进行讨论。目前常用的限流算法主要有三种计数器法、滑动窗口算法、漏桶算法和令牌桶算法。下面分别介绍其原理。
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模型使用了RSVPResource 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.1pIP报文使用DSCPMPLS报文使用EXP。 2流量监管、流量整形和接口限速 流量监管和流量整形可以将业务流量限制在特定的带宽内当业务流量超过额定带宽时超过的流量将被丢弃或缓存。其中将超过的流量丢弃的技术称为流量监管将超过的流量缓存的技术称为流量整形。接口限速分为基于接口的流量监管和基于接口的流量整形。 3拥塞管理和拥塞避免 拥塞管理在网络发生拥塞时将报文放入队列中缓存并采取某种调度算法安排报文的转发次序。而拥塞避免可以监督网络资源的使用情况当发现拥塞有加剧的趋势时采取主动丢弃报文的策略通过调整流量来解除网络的过载。
小结
优点缺点Best-Effort实现机制简单对不同业务流不能进行区分对待IntServ可提供端到端QoS服务并保证带宽、延迟需要跟踪和记录每个数据流的状态实现较复杂且扩展性较差带宽利用率较低DiffServ不需跟踪每个数据流状态资源占用少扩展性较强且能实现对不同业务流提供不同的服务质量, 需要在端到端每个节点都进行手工部署对人员能力要求较高
