亲宝软件园·资讯

展开

Redis限流算法

剑圣无痕​​​​​​​ 人气:0

前言

在高并发系统中,我们通常需要通过各种手段来提供系统的可以用性,例如缓存、降级和限流等,本文将针对应用中常用的限流算法进行详细的讲解。

简介

限流简称流量限速(Rate Limit)是指只允许指定的事件进入系统,超过的部分将被拒绝服务、排队或等待、降级等处理.

常见的限流方案如下:

固定时间窗口

固定时间窗口是最常见的限流算法之一。其中窗口的概念,对应限流场景当中的限流时间单元。

原理

示例说明

说明:如上图场景是每秒钟限流10次,窗口的大小为1秒,每个方块代表一个请求,绿色的方块代表正常的请求,红色的方法代表被限流的请求,在每秒10次的场景中,从左往右当来看,当进入10个请求后,后面的请求都被会被限流。

优缺点

优点:

缺点:

窗口切换时无法保证限流值。

相关实现

固定时间窗口的具体实现,可以采用Redis调用lua限流脚本来实现。

限流脚本

local key = KEYS[1]
local count = tonumber(ARGV[1])
local time = tonumber(ARGV[2])
local current = redis.call('get', key)
if current and tonumber(current) > count then
    return tonumber(current)
end
current = redis.call('incr', key)
if tonumber(current) == 1 then
    redis.call('expire', key, time)
end
return tonumber(current)

具体实现

   public Long ratelimiter(String key ,int time,int count) throws IOException
   {
       Resource resource = new ClassPathResource("ratelimiter.lua");
       String redisScript = IOUtils.toString(resource.getInputStream(), StandardCharsets.UTF_8);
       List<String> keys = Collections.singletonList(key);
       List<String> args = new ArrayList<>();
       args.add(Integer.toString(count));
       args.add(Integer.toString(time));

       long result = redisTemplate.execute(new RedisCallback<Long>() {
           @Override
           public Long doInRedis(RedisConnection connection) throws DataAccessException {
               Object nativeConnection = connection.getNativeConnection();
               if (nativeConnection instanceof Jedis) 
               {
                   return (Long) ((Jedis) nativeConnection).eval(redisScript, keys, args);
               }
               return -1l;
           }
       });
       return result;
   }

测试

 @RequestMapping(value = "/RateLimiter", method = RequestMethod.GET)
    public String RateLimiter() throws IOException 
    {
         int time=3;
         int count=1;
         String key="redis:ratelimiter";
         Long number=redisLockUtil.ratelimiter(key, time, count);
         logger.info("count:{}",number);
         Map<String, Object> map =new HashMap<>();
         if(number==null || number.intValue()>count)
         {
             map.put("code", "-1");
             map.put("msg", "访问过于频繁,请稍候再试");
         }else{
             map.put("code", "200");
             map.put("msg", "访问成功");
         }
         return JSON.toJSONString(map);
    }

说明:测试为3秒钟访问1次,超过了次数会提示错误。

滑动时间窗口

滑动时间窗口算法是对固定时间窗口算法的一种改进,在滑动窗口的算法中,同样需要针对当前的请求来动态查询窗口。但窗口中的每一个元素,都是子窗口。子窗口的概念类似于方案一中的固定窗口,子窗口的大小是可以动态调整的。

实现原理

示例说明

说明:比如上图中的场景是每分钟限流100次。每一个子窗口的时间维度设置为1秒,那么一分钟的窗口有60个子窗口。这样每当一个请求来了之后,我们去动态计算这个窗口的时候,我们最多需找60次。时间复杂度,从线性变成常量级了,时间的复杂度相对来说也会更低了。

具体实现

关于滑动时间窗的实现,可以采用sentinel,关于sentinel的使用后续将详细进行讲解。

漏桶算法

漏桶算法是水先进入到漏桶里,漏桶再以一定的速率出水,当流入水的数量大于流出水时,多余的水直接溢出。把水换成请求来看,漏桶相当于服务器队列,但请求量大于限流阈值时,多出来的请求就会被拒绝服务。漏桶算法使用队列实现,可以以固定的速率控制流量的访问速度,可以做到流量的平整化处理。

原理

说明:

具体实现

long timeStamp = System.currentTimeMillis(); //当前时间
    long  capacity = 1000;// 桶的容量
    long  rate = 1;//水漏出的速度
    long  water = 100;//当前水量
    public boolean leakyBucket()
    {
        //先执行漏水,因为rate是固定的,所以可以认为“时间间隔*rate”即为漏出的水量
        long  now = System.currentTimeMillis();
        water = Math.max(0, water -(now-timeStamp) * rate);
        timeStamp = now;
        // 水还未满,加水
        if (water < capacity)
        {
            water=water+100;
            return true;
        }
        //水满,拒绝加水
        else
        {
          return false;
        }
    }
    @RequestMapping(value="/leakyBucketLimit",method = RequestMethod.GET)
    public void leakyBucketLimit() 
    {
        for(int i=0;i<20;i++) {
            fixedThreadPool.execute(new Runnable() 
            {
                @Override
                public void run() 
                {
                    if(leakyBucket()) 
                    {
                        logger.info("thread name:"+Thread.currentThread().getName()+" "+sdf.format(new Date()));
                    }
                    else 
                    {
                       logger.error("请求频繁");
                    }
                }
            });
        }
    }

令牌桶算法

令牌桶算法是基于漏桶之上的一种改进版本,在令牌桶中,令牌代表当前系统允许的请求上限,令牌会匀速被放入桶中。当桶满了之后,新的令牌就会被丢弃

原理

具体实现

@RequestMapping(value="/ratelimit",method = RequestMethod.GET)
    public void ratelimit()
    {
        //每1s产生0.5个令牌,也就是说接口2s只允许调用1次
        RateLimiter rateLimiter=RateLimiter.create(0.5,1,TimeUnit.SECONDS);

        for(int i=0;i<10;i++) {
            fixedThreadPool.execute(new Runnable() 
            {
                @Override
                public void run() 
                {
                    //获取令牌最大等待10秒
                    if(rateLimiter.tryAcquire(1,10,TimeUnit.SECONDS)) 
                    {
                        logger.info("thread name:"+Thread.currentThread().getName()+" "+sdf.format(new Date()));
                    }
                    else 
                    {
                       logger.error("请求频繁");
                    }
                }
            });
        }
    }

执行结果:

-[pool-1-thread-3] ERROR 请求频繁
[pool-1-thread-2] ERROR  请求频繁
[pool-1-thread-1] INFO   thread name:pool-1-thread-1 2022-08-07 15:44:00
[pool-1-thread-8] ERROR []  - 请求频繁
[pool-1-thread-9] ERROR []  - 请求频繁
[pool-1-thread-10] ERROR [] - 请求频繁
[pool-1-thread-7] INFO  []  - thread name:pool-1-thread-7 2022-08-07 15:44:03
 [pool-1-thread-6] INFO  [] - thread name:pool-1-thread-6 2022-08-07 15:44:05
[pool-1-thread-5] INFO  []  - thread name:pool-1-thread-5 2022-08-07 15:44:07
[pool-1-thread-4] INFO  []  - thread name:pool-1-thread-4 2022-08-07 15:44:09

说明:接口限制为每2秒请求一次,10个线程需要20s才能处理完,但是rateLimiter.tryAcquire限制了10s内没有获取到令牌就抛出异常,所以结果中会有5个是请求频繁的。

小结

总结

加载全部内容

相关教程
猜你喜欢
用户评论