令牌桶算法和漏桶算法以及流量控制浅谈

    ​    ​在双十一等大促环节，系统需要限流，外部需要在我制定的速率限制来调用（超出的流量直接挡掉，系统不进行处理），有没有理论依据呢？这里看了两个算法

约定访问速率是流量管理中比较常用的方法之一，令牌桶算法，是目前最常用的流量限制的方法。

    ​  

        ​​什么是令牌桶算法？

    ​    ​令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

    ​    ​令牌桶：网络设备中的内部存储池

    ​    ​令牌：给定速率填充令牌桶的虚拟信息包

    ​    ​通俗的理解，令牌桶是一个水桶，而令牌是通过一根水管流到水桶中的水

    ​    ​令牌桶的填满时间，是由桶的自身容量、令牌漏出速率（桶下面的水管）、超过平均速率的突发流量持续的时间三个方面共同决定的。如果突发流量的时间比较短，令牌桶不会溢出，在通信流上不会受到影响，如果突发流量比较大，时间比较长，那令牌桶就会溢出，多余的通信流就会被限制。

    ​    

        ​什么是漏桶算法？

    ​    ​主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。

    ​  

        ​令牌桶算法和漏桶算法的区别在哪里？

    ​    ​主要区别在于“漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输速率外，还允许某种程度的突发传输。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。

    ​  

       ​如何利用令牌桶算法来实现互联网系统的限流呢？

    ​    ​这里大体YY了一下组件，大体可以分为计数器、限流器、阀值配置、阀值更新、令牌桶检验几个组件。

    ​    ​计数器：实时的统计接口的调用速率，例如时间单位是秒，那就是一秒调用多少次

    ​    ​阀值配置：配置一下时间窗口（就是统计信息和限流的时间周期，可以是1秒，也可以是1毫秒），平均速率以及突发情况下允许的最大速率

    ​    ​阀值更新：这里为啥要单独拿出来说一下呢，因为阀值的配置不可能是写死的，需要实时更新，有一个组件去获取最新的配置，然后在系统中做更新

    ​    ​限流器：当令牌桶中令牌已经无法放入，也就是溢出了，需要限流，采取怎么样的限流策略，需要限流器去做处理

    ​    ​令牌桶处理：需要有一个类，根据配置的时间窗口、平均速率、突发最大速率来模拟向桶中放置令牌的操作，如果溢出了，则触发限流器做相应的操作

    ​    ​

        这里受到的启发是啥？

    ​    ​相当于用传统网络流量限制中的一个算法，来解决互联网流量控制的一个问题，具体的实现可能有多种。这里打开了一个思路，以前觉得互联网中的问题是新鲜的，但是可能就是遇到的问题是相通的，也许在多年前已经有理论存在并且有实际应用了，例如传统的一个行业中，或者一个书本中存在已久的算法，再或者一个物流现象。

    ​    ​程序员也需要关注除了程序本身之外的世界，有些可能会影响到程序哦。

    ​    ​

        这里再补充一篇文章，关于流控的：http://iamzhongyong.iteye.com/blog/1742829 

 

       参考文章：

http://blog.163.com/liu_sheng_han/blog/static/190591372201241563016108/