Contoh Analisis Algoritma Pengehadan Arus Klasik di Jawa

Apakah itu pengehadan kadar?

Konsep Wikipedia adalah seperti berikut:

Dalam rangkaian komputer, pengehadan kadar digunakan untuk mengawal kadar permintaan yang dihantar atau diterima oleh pengawal antara muka rangkaian. Ia boleh digunakan untuk mencegah serangan DoS dan mengehadkan pengikisan web

Terjemahan mudah: Dalam rangkaian komputer, pengehadan aliran adalah untuk mengawal kadar antara muka rangkaian menghantar atau menerima permintaan. Ia boleh menghalang serangan DoS dan mengehadkan perangkak web.

Penghadan semasa, juga dipanggil kawalan aliran. Ini bermakna apabila sistem berhadapan dengan konkurensi tinggi atau permintaan trafik yang besar, ia mengehadkan akses permintaan baharu kepada sistem, dengan itu memastikan kestabilan sistem. Pengehadan semasa akan menyebabkan beberapa permintaan pengguna diproses sebelum masanya atau ditolak, yang menjejaskan pengalaman pengguna. Oleh itu, secara amnya adalah perlu untuk mengimbangkan antara kestabilan sistem dan pengalaman pengguna. Untuk memberi contoh daripada kehidupan seharian:

★

Sesetengah tarikan pelancong yang popular biasanya mempunyai sekatan ke atas bilangan pelawat harian. Hanya bilangan tiket tetap akan dijual setiap hari, seperti 5,000. Jika anda tiba lewat semasa cuti Hari Mei atau Hari Kebangsaan, tiket untuk hari itu mungkin telah habis dijual dan anda tidak akan dapat masuk dan bermain. Walaupun anda masuk, barisan akan membuat anda meragui kehidupan anda.

”

Algoritma pengehad arus biasa

Algoritma pengehad arus tetingkap tetap

Mula-mula mengekalkan pembilang, layan tempoh masa unit sebagai tetingkap dan pembilang merekodkan penerimaan tetingkap ini Bilangan permintaan

• Apabila nombor kurang daripada had semasa, akses dibenarkan dan kaunter +1

• Apabila bilangan lebih besar daripada had semasa, akses ditolak

• Selepas tetingkap masa semasa berlalu, kaunter dikosongkan

  Anggapkan bahawa masa unit ialah 1 saat Ambang aliran ialah 3. Dalam masa unit 1 saat, pembilang meningkat sebanyak 1 untuk setiap permintaan Jika bilangan kali terkumpul melebihi ambang had aliran 3, semua permintaan seterusnya akan ditolak dan pembilang akan dikosongkan kepada 0 selepas 1 saat Seperti yang ditunjukkan di bawah:

Kod pseudo adalah seperti berikut: <.> 0.8-1s dan 1-1.2s unit masa, walaupun ia tidak melebihi ambang, Tetapi jika anda mengira 0.8-1.2s, bilangan konkurensi adalah setinggi 10, yang mempunyai melebihi takrifan 5 ambang

selama 1 saat setiap unit masa

    /**
     * 固定窗口时间算法
     * @return
     */
    boolean fixedWindowsTryAcquire() {
        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        if (currentTime - lastRequestTime > windowUnit) {  //检查是否在时间窗口内
            counter = 0;  // 计数器清0
            lastRequestTime = currentTime;  //开启新的时间窗口
        }
        if (counter < threshold) {  // 小于阀值
            counter++;  //计数器加1
            return true;
        }

        return false;
    }

algoritma pengehadan arus tetingkap Pengehadan arus tetingkap gelongsor menyelesaikan masalah nilai kritikal tetingkap tetap. . Ia membahagikan tempoh masa unit kepada n tempoh kecil, merekodkan bilangan akses kepada antara muka dalam setiap tempoh kecil, dan meluncurkannya mengikut masa

Sebuah gambar menerangkan algoritma tetingkap gelongsor , seperti berikut:

Dengan mengandaikan bahawa masa unit masih 1s, algoritma tetingkap gelongsor membahagikannya kepada 5 tempoh kecil, iaitu tetingkap gelongsor (unit masa) ialah dibahagikan kepada 5 grid kecil. Setiap grid mewakili 0.2s selepas setiap 0.2s, tetingkap masa akan meluncur ke kanan. Jika permintaan tiba dalam 0.8~1.0s bertambah sebanyak 1.

Mari kita lihat bagaimana tetingkap gelongsor menyelesaikan masalah kritikal

Anggapkan ambang had semasa kami masih 5 permintaan dalam masa 1 saat, dan 5 permintaan masuk dalam masa 0.8~. 1.0s (contohnya, 0.9s), dan jatuh dalam grid kuning selepas titik 1.0s datang dan jatuh dalam grid ungu Jika

ialah algoritma tetingkap tetap, ia tidak akan terhad , tetapi jika

ialah tetingkap gelongsor, ia akan mengalihkan satu ke kanan setiap grid kecil

Selepas melepasi titik 1.0s, ia akan bergerak ke kanan Tempoh masa unit semasa ialah 0.2~ 1.2s. Permintaan dalam kawasan ini telah melebihi had 5, dan had semasa telah dicetuskan Sebenarnya

TIPS:

Semakin banyak tempoh grid terbahagi kepada tetingkap gelongsor. tetingkap gelongsor akan menjadi lebih lancar, dan statistik pengehad semasa akan menjadi lebih tepat. Algoritma tetingkap gelongsorPelaksanaan kod pseudo adalah seperti berikut:

Walaupun algoritma tetingkap gelongsor menyelesaikan masalah kritikal tetingkap tetap

, sebaik sahaja ia mencapai Selepas pengehadan semasa, permintaan akan ditolak secara langsung dan ganas. Jiangzi, kami akan kehilangan sebahagian daripada permintaan, yang sebenarnya tidak begitu mesra produk.

Algoritma Baldi Bocor

Algoritma Baldi Bocor adalah lebih fleksibel apabila berhadapan dengan had semasa, dan tiada penolakan langsung secara kasar.

 /**
     * 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
     */
    private int SUB_CYCLE = 10;

    /**
     * 每分钟限流请求数
     */
    private int thresholdPerMin = 100;

    /**
     * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters = new TreeMap<>();

   /**
     * 滑动窗口时间算法实现
     */
    boolean slidingWindowsTryAcquire() {
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
        int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数

        //超过阀值限流
        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }

        //计数器+1
        counters.get(currentWindowTime)++;
        return true;
    }

   /**
    * 统计当前窗口的请求数
    */
    private int countCurrentWindow(long currentWindowTime) {
        //计算窗口开始位置
        long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
        int count = 0;

        //遍历存储的计数器
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            // 删除无效过期的子窗口计数器
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                //累加当前窗口的所有计数器之和
                count =count + entry.getValue();
            }
        }
        return count;
    }

Prinsipnya sangat mudah, boleh dianggap sebagai proses suntikan dan kebocoran air. Air mengalir ke dalam baldi bocor pada sebarang kadar dan air mengalir keluar pada kadar tetap. Apabila air melebihi kapasiti baldi, ia akan dilimpahi, iaitu dibuang. Kerana kapasiti baldi kekal tidak berubah, kelajuan keseluruhan dijamin.

Titisan air yang masuk boleh dianggap sebagai permintaan untuk mengakses sistem Kadar aliran masuk tidak pasti.

桶的容量一般表示系统所能处理的请求数。

如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）

流出的水滴，是恒定过滤的，对应服务按照固定的速率处理请求。

漏桶算法伪代码实现如下：

 /**
     * 每秒处理数（出水率）
     */
    private long rate;

    /**
     *  当前剩余水量
     */
    private long currentWater;

    /**
     * 最后刷新时间
     */
    private long refreshTime;

    /**
     * 桶容量
     */
    private long capacity;

    /**
     * 漏桶算法
     * @return
     */
    boolean leakybucketLimitTryAcquire() {
        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        long outWater = (currentTime - refreshTime) / 1000 * rate; //流出的水量 =(当前时间-上次刷新时间)* 出水率
        long currentWater = Math.max(0, currentWater - outWater); // 当前水量 = 之前的桶内水量-流出的水量
        refreshTime = currentTime; // 刷新时间

        // 当前剩余水量还是小于桶的容量，则请求放行
        if (currentWater < capacity) {
            currentWater++;
            return true;
        }
        
        // 当前剩余水量大于等于桶的容量，限流
        return false;
    }

在正常流量的时候，系统按照固定的速率处理请求，是我们想要的。但是面对突发流量的时候，漏桶算法还是循规蹈矩地处理请求，这就不是我们想看到的啦。流量变突发时，我们肯定希望系统尽量快点处理请求，提升用户体验嘛。

令牌桶算法

面对突发流量的时候，我们可以使用令牌桶算法限流。

令牌桶算法原理：

• 有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。

• 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。

• 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；

• 如果拿不到令牌，就直接拒绝这个请求。

漏桶算法伪代码实现如下：

    /**
     * 每秒处理数（放入令牌数量）
     */
    private long putTokenRate;
    
    /**
     * 最后刷新时间
     */
    private long refreshTime;

    /**
     * 令牌桶容量
     */
    private long capacity;
    
    /**
     * 当前桶内令牌数
     */
    private long currentToken = 0L;

    /**
     * 漏桶算法
     * @return
     */
    boolean tokenBucketTryAcquire() {

        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌的速率
        currentToken = Math.min(capacity, generateToken + currentToken); // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量
        refreshTime = currentTime; // 刷新时间
        
        //桶里面还有令牌，请求正常处理
        if (currentToken > 0) {
            currentToken--; //令牌数量-1
            return true;
        }
        
        return false;
    }

如果令牌发放的策略正确，这个系统即不会被拖垮，也能提高机器的利用率。Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。

Atas ialah kandungan terperinci Contoh Analisis Algoritma Pengehadan Arus Klasik di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!