江苏龙网

  1. 主页 > 生活百科 > >

详解限流算法，图示漏桶算法与令牌桶算法

限流算法

前言分布式环境下应对高并发保证服务稳定几招，按照个人理解，优先级从高到低分别为缓存、限流、降级、熔断，每招都有它的作用，本文重点就讲讲限流这部分 。
坦白讲，其实上面的说法也不准确，因为服务降级、熔断本身也是限流的一种，因为它们本质上也是阻断了流量进来，但是本文希望大家可以把限流当做一个单纯的名词来理解，看一下对请求做流控的几种算法及具体实现方式 。
为什么要限流其实很好理解的一个问题，为什么要限流，自然就流量过大了呗，一个对外服务有很多场景都会流量增大：

  • 业务用户量不断攀升
  • 各种促销
  • 网络爬虫
  • 恶意刷单
注意这个"大"，1000QPS大吗？5000QPS大吗？10000QPS大么？没有答案，因为没有标准，因此，"大"一定是和正常流量相比的大 。流量一大，服务器扛不住，扛不住就挂了，挂了没法提供对外服务导致业务直接熔断 。怎么办，最直接的办法就是从源头把流量限制下来，例如服务器只有支撑1000QPS的处理能力，那就每秒放1000个请求，自然保证了服务器的稳定，这就是限流 。
下面看一下常见的两种限流算法 。
漏桶算法漏桶算法的原理比较简单，水（请求）先进入到漏桶里，人为设置一个最大出水速率，漏桶以<=出水速率的速度出水，当水流入速度过大会直接溢出（拒绝服务）：
详解限流算法，图示漏桶算法与令牌桶算法

文章插图
 
因此，这个算法的核心为：
  • 存下请求
  • 匀速处理
  • 多于丢弃
因此这是一种强行限制请求速率的方式，但是缺点非常明显，主要有两点：
  • 无法面对突发的大流量----比如请求处理速率为1000，容量为5000，来了一波2000/s的请求持续10s，那么后5s的请求将全部直接被丢弃，服务器拒绝服务，但是实际上网络中突发一波大流量尤其是短时间的大流量是非常正常的，超过容量就拒绝，非常简单粗暴
  • 无法有效利用网络资源----比如虽然服务器的处理能力是1000/s，但这不是绝对的，这个1000只是一个宏观服务器处理能力的数字，实际上一共5秒，每秒请求量分别为1200、1300、1200、500、800，平均下来qps也是1000/s，但是这个量对服务器来说完全是可以接受的，但是因为限制了速率是1000/s，因此前面的三秒，每秒只能处理掉1000个请求而一共打回了700个请求，白白浪费了服务器资源
所以，通常来说利用漏桶算法来限流，实际场景下用得不多 。
 
令牌桶算法
令牌桶算法是网络流量整形（Traffic Shaping）和限流（Rate Limiting）中最常使用的一种算法，它可用于控制发送到网络上数据的数量并允许突发数据的发送 。
从某种意义上来说，令牌桶算法是对漏桶算法的一种改进，主要在于令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用，来看下令牌桶算法的实现原理：
详解限流算法，图示漏桶算法与令牌桶算法

文章插图
 
整个的过程是这样的：
  • 系统以恒定的速率产生令牌，然后将令牌放入令牌桶中
  • 令牌桶有一个容量，当令牌桶满了的时候，再向其中放入的令牌就会被丢弃
  • 每次一个请求过来，需要从令牌桶中获取一个令牌，假设有令牌，那么提供服务；假设没有令牌，那么拒绝服务
那么，我们再看一下，为什么令牌桶算法可以防止一定程度的突发流量呢？可以这么理解，假设我们想要的速率是1000QPS，那么往桶中放令牌的速度就是1000个/s，假设第1秒只有800个请求，那意味着第2秒可以容许1200个请求，这就是一定程度突发流量的意思，反之我们看漏桶算法，第一秒只有800个请求，那么全部放过，第二秒这1200个请求将会被打回200个 。
注意上面多次提到一定程度这四个字，这也是我认为令牌桶算法最需要注意的一个点 。假设还是1000QPS的速率，那么5秒钟放1000个令牌，第1秒钟800个请求过来，第2~4秒没有请求，那么按照令牌桶算法，第5秒钟可以接受4200个请求，但是实际上这已经远远超出了系统的承载能力，因此使用令牌桶算法特别注意设置桶中令牌的上限即可 。
总而言之，作为对漏桶算法的改进，令牌桶算法在限流场景下被使用更加广泛 。
RateLimiter使用上面说了令牌桶算法在限流场景下被使用更加广泛，接下来我们看一下代码示例，模拟一下每秒最多过五个请求：
public class RateLimiterTest {private static final SimpleDateFormat FORMATTER = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");private static final int THREAD_COUNT = 25;@Testpublic void testRateLimiter1() {RateLimiter rateLimiter = RateLimiter.create(5);Thread[] ts = new Thread[THREAD_COUNT];for (int i = 0; i < THREAD_COUNT; i++) {ts[i] = new Thread(new RateLimiterThread(rateLimiter), "RateLimiterThread-" + i);}for (int i = 0; i < THREAD_COUNT; i++) {ts[i].start();}for (;;);}public class RateLimiterThread implements Runnable {private RateLimiter rateLimiter;public RateLimiterThread(RateLimiter rateLimiter) {this.rateLimiter = rateLimiter;}@Overridepublic void run() {rateLimiter.acquire(1);System.out.println(Thread.currentThread().getName() + "获取到了令牌，时间 = " + FORMATTER.format(new Date()));}}}


推荐阅读


上一篇：用户实测成功：Win7/8.1仍可免费升级Win10

下一篇：用了路由器这么久，是时候了解的WIFI 基础的这些事儿了