天道酬勤,学无止境

Leaky Bucket

漏桶算法 Leaky Bucket (令牌桶算法 Token Bucket)学习笔记

具体问题 网站的访问ip中,找出进行频繁连接的ip,并对这些ip的访问频率进行限制。 解决方案 Leak Bucket / Token Bucket 学习资料 http://en.wikipedia.org/wiki/Leaky_bucket 概述 将上述的寻找频繁访问ip的问题提升到一个更高的抽象层次,就是网站的流量控制。Leaky Bucket就是一种可以辅助实现流量控制的算法。 在我看来,Leaky Bucket是一个抽象层次略高的算法。它的作用,是通过一种模型(即桶),建立了一种合理地判断流量是否异常的算法。 至于在判断出异常流量后,要触发怎样的操作——抛弃?放入等待队列暂缓发送?——仍然要交给算法的实现者根据具体需求作出选择。这并不是Leaky Bucket的管辖范畴。 根据wiki上的介绍,Leaky Bucket实际上有两种不同的含义。 1)as a meter(作为计量工具) 2)as a queue(作为调度队列) 其中,第一种含义和Token Bucket是等价的,只是表述的角度不同。更有趣的是,第二种含义其实是第一种的特例。这些对比和区别在后面再谈,先整体看一下Leaky Bucket。 Leaky Bucket整体思想 Leaky Bucket的核心抽象模型就如字面意思:一个会漏水的桶。 如图,桶本身具有一个恒定的速率往下漏水,而上方时快时慢地会有水进入桶中

2021-06-02 18:59:44    分类:博客    Leaky Bucket    Token Bucket   网络