Redis의 공통 전류 제한 알고리즘의 원리와 구현 방법은 무엇입니까?

소개

속도 제한이라고도 하는 속도 제한은 지정된 이벤트만 시스템에 들어갈 수 있도록 허용되며 초과하는 경우 서비스가 거부되거나 대기되거나 다운그레이드됩니다.

일반적인 속도 제한 체계는 다음과 같습니다. 다음은 다음과 같습니다.

고정 시간 창

고정 시간 창은 가장 일반적인 전류 제한 알고리즘 중 하나입니다. 창의 개념은 전류 제한 시나리오의 전류 제한 시간 단위에 해당합니다.

원칙

• 타임라인은 여러 개의 독립적인 고정 크기 창으로 나뉩니다.

• 각 시간 창에 속하는 요청은 카운터를 1씩 증가시킵니다.

• 카운터가 현재 제한 임계값을 초과합니다. , 이 기간 내에 해당하는 후속 요청은 거부됩니다. 그러나 시간이 다음 시간 창에 도달하면 카운터는 0으로 재설정됩니다.

설명 예

지침: 위에 표시된 장면은 흐름을 초당 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;
   }

Test

 @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의 고정 창과 유사하며 하위 창의 크기를 동적으로 조정할 수 있습니다.

구현 원리

• 단위 시간을 여러 간격으로 나누고 일반적으로 여러 개의 작은 기간으로 균등하게 나눕니다.

• 각 간격마다 카운터가 있고 요청은 그 간격 내에 속합니다. 간격은 1씩 증가합니다.

• 기간이 지날 때마다 시간 창은 한 칸 오른쪽으로 이동하여 가장 오래된 간격을 버리고 새 간격을 통합합니다.

• 전체 시간 창에서 모든 시간 세그먼트의 카운터가 누적됩니다. 총 개수가 제한을 초과하면 이 창의 모든 요청이 삭제됩니다.

예시 설명

지침: 예를 들어 위 사진의 장면은 분당 100회로 제한됩니다. 각 하위 창의 시간 차원은 1초로 설정되므로 1분 창에는 60개의 하위 창이 있습니다. 이런 식으로 요청이 올 때마다 이 창을 동적으로 계산할 때 최대 60번까지 찾아야 합니다. 시간 복잡도는 선형 수준에서 상수 수준으로 변경되었으며, 시간 복잡도는 상대적으로 낮아졌습니다.

특정 구현

슬라이딩 타임 윈도우 구현에 관해서는 센티넬을 사용할 수 있습니다. 센티넬 사용에 대해서는 나중에 자세히 설명하겠습니다.

Leaky Bucket Algorithm

Funnel 알고리즘은 유입되는 물의 양이 배출되는 물의 양을 초과하면 깔때기에 먼저 물을 채운 후 고정된 속도로 흘러나오는 것입니다. 요청량이 현재 제한 임계값을 초과하면 서버 큐는 누출 버킷처럼 작동합니다. 따라서 추가요청에 대해서는 서비스가 거부됩니다. Leaky Bucket 알고리즘은 큐를 이용하여 구현되는데, 이를 통해 트래픽의 접근 속도를 고정된 비율로 제어하고 트래픽의 평활화를 달성할 수 있습니다. ” 비어 있는.

큐가 가득 차면 중복 요청은 바로 거부됩니다

특정 구현

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("请求频繁");
                    }
                }
            });
        }
    }

토큰 버킷 알고리즘

• 토큰 버킷 알고리즘은 버킷에서 토큰이 누출되는 것을 기반으로 개선된 버전입니다. 현재 시스템에서 허용되는 요청의 상한선을 나타내며 토큰은 일정한 속도로 버킷에 저장됩니다. 버킷이 가득 차면 새 토큰이 폐기됩니다.
  Principle

• 토큰은 고정된 비율로 생성되어 토큰 버킷에 넣습니다.

• 如果令牌桶满了则多余的令牌会直接丢弃，当请求到达时，会尝试从令牌桶中取令牌，取到了令牌的请求可以执行；

• 如果桶空了,则拒绝该请求。

具体实现

@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个是请求频繁的。

小结

• 固定窗口：实现简单，适用于流量相对均匀分布，对限流准确度要求不严格的场景。

• 滑动窗口：适用于对准确性和性能有一定的要求场景，可以调整子窗口数量来权衡性能和准确度

• 漏桶：适用于流量绝对平滑的场景

• 令牌桶：适用于流量整体平滑的情况下，同时也可以满足一定的突发流程场景

위 내용은 Redis의 공통 전류 제한 알고리즘의 원리와 구현 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!