Apakah prinsip algoritma pengehadan arus biasa Redis dan cara melaksanakannya

Pengenalan

Had Kadar merujuk kepada hanya membenarkan peristiwa tertentu memasuki sistem. Lebihan akan dinafikan perkhidmatan, beratur atau menunggu, diturunkan taraf, dsb.

Arus biasa. skim pengehadan adalah seperti berikut:

Tetingkap masa tetap

Tetingkap masa tetap ialah salah satu daripada algoritma pengehadan semasa yang paling biasa. Konsep tetingkap sepadan dengan unit masa pengehad semasa dalam senario pengehad semasa.

Prinsip

• Garis masa dibahagikan kepada berbilang tetingkap bebas dan saiz tetap

• jatuh dalam setiap tetingkap masa Untuk permintaan, kaunter akan dinaikkan sebanyak 1;

• Jika kaunter melebihi ambang had semasa, permintaan berikutnya yang termasuk dalam tetingkap ini akan ditolak. Tetapi apabila masa mencapai tetingkap masa seterusnya, kaunter akan ditetapkan semula kepada 0.

Contoh penerangan

Arahan: Seperti yang ditunjukkan di atas, adegan dihadkan kepada 10 kali sesaat , dan tetingkap Saiznya ialah 1 saat, setiap segi empat sama mewakili permintaan, segi empat sama hijau mewakili permintaan biasa, dan kaedah merah mewakili permintaan terhad semasa Dalam senario 10 kali sesaat, apabila dilihat dari kiri ke kanan , apabila memasuki Selepas 10 permintaan, permintaan seterusnya akan dikurangkan.

Kebaikan dan Kelemahan

Kelebihan:

• Logik yang mudah dan kos penyelenggaraan yang agak rendah; 🎜 >

Kelemahan:

Nilai had semasa tidak boleh dijamin apabila menukar tetingkap.

Pelaksanaan berkaitan

Pelaksanaan khusus tetingkap masa tetap boleh dilaksanakan dengan menggunakan Redis untuk memanggil skrip pengehad semasa Lua.

Skrip mengehadkan kadar

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)

Pelaksanaan khusus

   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;
   }

Ujian

 @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);
    }

Nota:

Ujian diakses sekali setiap 3 saat. Jika bilangan melebihi, ralat akan digesa.

Tetingkap masa gelongsor

Algoritma tetingkap masa gelongsor ialah penambahbaikan pada algoritma tetingkap masa tetap Dalam algoritma tetingkap gelongsor, anda juga perlu menanyakan tetingkap secara dinamik untuk permintaan semasa. Tetapi setiap elemen dalam tetingkap adalah tetingkap kanak-kanak. Konsep sub-tetingkap adalah serupa dengan tetingkap tetap dalam Penyelesaian 1, dan saiz sub-tetingkap boleh dilaraskan secara dinamik.

Prinsip Pelaksanaan

Bahagikan masa unit kepada berbilang selang, biasanya dibahagikan sama rata kepada beberapa tempoh masa kecil; ialah pembilang dalam setiap selang Jika permintaan berada dalam selang ini, pembilang dalam selang ini akan ditambah dengan satu; ke kanan, buang selang tertua, dan masukkan selang baharu

• Apabila mengira jumlah bilangan permintaan dalam tetingkap masa keseluruhan, semua permintaan akan terkumpul Jika jumlah bilangan; daripada kaunter dalam segmen masa melebihi had, semua permintaan dalam tetingkap ini akan dibuang.

• Contoh penerangan
• Arahan:

  Sebagai contoh, adegan dalam gambar di atas adalah terhad kepada 100 kali seminit. Dimensi masa setiap sub-tetingkap ditetapkan kepada 1 saat, jadi tetingkap satu minit mempunyai 60 sub-tetingkap. Dengan cara ini, setiap kali permintaan datang, apabila kita mengira tetingkap ini secara dinamik, kita perlu mencarinya sehingga 60 kali. Kerumitan masa telah berubah daripada tahap linear ke tahap malar, dan kerumitan masa akan menjadi lebih rendah.

Pelaksanaan khusus

Mengenai pelaksanaan tetingkap masa gelongsor, anda boleh menggunakan sentinel Penggunaan sentinel akan diterangkan secara terperinci kemudian.

Algoritma Baldi Bocor

Algoritma Corong ialah mengisi corong dengan air terlebih dahulu dan kemudian mengalir keluar pada kadar tetap Apabila jumlah air yang masuk melebihi air yang keluar, air yang berlebihan akan menjadi dibuang. Apabila volum permintaan melebihi ambang had semasa, baris gilir pelayan bertindak seperti baldi bocor. Oleh itu, permintaan tambahan akan dinafikan perkhidmatan. Algoritma baldi bocor dilaksanakan menggunakan baris gilir, yang boleh mengawal kelajuan akses trafik pada kadar tetap dan mencapai kelancaran trafik.

Prinsip

Penjelasan:

Letakkan setiap permintaan ke dalam saiz tetap baris gilir

baris gilir permintaan aliran keluar pada kadar tetap dan berhenti mengalir keluar jika baris gilir kosong.

Jika baris gilir penuh, lebihan permintaan akan ditolak terus

• Pelaksanaan terperinci

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

• Algoritma Token Bucket
  Algoritma baldi token ialah versi yang dipertingkatkan berdasarkan baldi bocor Dalam baldi token, token mewakili had atas permintaan yang dibenarkan oleh sistem semasa, dan token akan dimasukkan ke dalam baldi pada kelajuan seragam. Apabila baldi penuh, token baharu akan dibuang
• Prinsip

Token dijana dan dikeluarkan pada kadar tetap Ke dalam baldi token;

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

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

具体实现

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

小结

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

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

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

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

Atas ialah kandungan terperinci Apakah prinsip algoritma pengehadan arus biasa Redis dan cara melaksanakannya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!