Apakah algoritma pengehadan semasa yang biasa di Jawa?

01 Tetingkap tetap

Tetingkap tetap, juga dikenali sebagai tetingkap tetap (juga dikenali sebagai algoritma pembilang, Tetingkap Tetap) algoritma pengehadan semasa, ialah algoritma pengehadan arus yang paling mudah Ia dikawal oleh pembilang yang dikekalkan dalam a unit masa. Bilangan maksimum lawatan dalam satu unit masa.

Dengan mengandaikan bahawa bilangan permintaan seminit adalah terhad kepada tidak lebih daripada 60, tetapkan kaunter Apabila permintaan tiba, jika kaunter mencapai ambang, permintaan akan ditolak, jika tidak, kaunter akan dinaikkan. dengan 1; kaunter akan ditetapkan semula kepada 0 setiap minit. Kod tersebut dilaksanakan seperti berikut:

public class CounterRateLimiter extends MyRateLimiter {
    /**
     * 每秒限制请求数
     */
    private final long permitsPerSecond;
    /**
     * 上一个窗口的开始时间
     */
    public long timestamp = System.currentTimeMillis();
    /**
     * 计数器
     */
    private int counter;

    public CounterRateLimiter(long permitsPerSecond) {
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 窗口内请求数量小于阈值，更新计数放行，否则拒绝请求
        if (now - timestamp < 1000) {
            if (counter < permitsPerSecond) {
                counter++;
                return true;
            } else {
                return false;
            }
        }
        // 时间窗口过期，重置计数器和时间戳
        counter = 0;
        timestamp = now;
        return true;
    }
}

Kelebihan terbesar tetingkap tetap ialah ia mudah dilaksanakan dan jejak memori adalah kecil, kita hanya perlu menyimpan kiraan dalam tetingkap masa; memastikan bahawa lebih banyak permintaan terkini diproses, dan tidak akan disebabkan oleh Pengumpulan permintaan lama menyebabkan permintaan baharu mati kelaparan. Sudah tentu, ia juga menghadapi masalah kritikal Apabila dua tingkap bertemu, trafik serta-merta mungkin 2n.

Tetingkap Gelongsor 02

Untuk mengelakkan trafik serta-merta, tetingkap tetap boleh dibahagikan lagi kepada berbilang grid dan setiap kali ia bergerak ke belakang grid kecil, bukannya menetapkan saiz tetingkap, ini ialah Tetingkap gelongsor (Sliding Window).

Sebagai contoh, setiap minit boleh dibahagikan kepada 6 sel selama 10 saat Satu pembilang dikekalkan dalam setiap sel, dan tetingkap meluncur ke hadapan satu sel pada satu masa. Setiap kali permintaan tiba, permintaan itu boleh dikeluarkan selagi jumlah kiraan semua sel dalam tetingkap tidak melebihi ambang. Penghantaran paket data dalam protokol TCP juga menggunakan tingkap gelongsor untuk kawalan aliran.

dilaksanakan seperti berikut:

public class SlidingWindowRateLimiter extends MyRateLimiter {
    /**
     * 每分钟限制请求数
     */
    private final long permitsPerMinute;
    /**
     * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters;

    public SlidingWindowRateLimiter(long permitsPerMinute) {
        this.permitsPerMinute = permitsPerMinute;
        this.counters = new TreeMap<>();
    }

    @Override
    public synchronized boolean tryAcquire() {
        // 获取当前时间的所在的子窗口值； 10s一个窗口
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / 10 * 10;
        // 获取当前窗口的请求总量
        int currentWindowCount = getCurrentWindowCount(currentWindowTime);
        if (currentWindowCount >= permitsPerMinute) {
            return false;
        }
        // 计数器 + 1
        counters.merge(currentWindowTime, 1, Integer::sum);
        return true;
    }
    /**
     * 获取当前窗口中的所有请求数（并删除所有无效的子窗口计数器）
     *
     * @param currentWindowTime 当前子窗口时间
     * @return 当前窗口中的计数
     */
    private int getCurrentWindowCount(long currentWindowTime) {
        // 计算出窗口的开始位置时间
        long startTime = currentWindowTime - 50;
        int result = 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 {
                result += entry.getValue();
            }
        }
        return result;
    }
}

Tingkap gelongsor menyelesaikan masalah puncak trafik serta-merta di kaunter Sebenarnya, algoritma kaunter juga merupakan jenis tetingkap gelongsor, tetapi tingkap itu tidak dibahagikan kepada unit berbutir halus. Membandingkan kaunter, dapat dilihat bahawa apabila butiran pembahagian tingkap lebih halus, kawalan aliran lebih tepat dan ketat.

Walau bagaimanapun, apabila trafik dalam tetingkap mencapai ambang, trafik akan terputus serta-merta dalam aplikasi sebenar, kesan mengehadkan aliran yang kita inginkan selalunya bukan untuk memotong trafik sekaligus, tetapi untuk membolehkan trafik memasuki sistem dengan lancar.

03 Algoritma Baldi Bocor

Bagaimana untuk mengehadkan arus dengan lebih lancar? Mari kita lihat algoritma Leaky Bucket yang disuntik ke dalam baldi bocor pada sebarang kelajuan seperti air, dan baldi akan membocorkan air pada kadar tetap apabila kelajuan suntikan terus lebih besar daripada kelajuan kebocoran, baldi bocor akan menjadi penuh , pada masa ini permintaan yang baru masuk akan dibuang. Pengehadan dan pembentukan semasa ialah dua keupayaan teras bagi algoritma baldi bocor.

Pelaksanaan adalah seperti berikut:

public class LeakyBucketRateLimiter extends MyRateLimiter {
    // 桶的容量
    private final int capacity;
    // 漏出速率
    private final int permitsPerSecond;
    // 剩余水量
    private long leftWater;
    // 上次注入时间
    private long timeStamp = System.currentTimeMillis();

    public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) {
        this.capacity = capacity;
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        //1. 计算剩余水量
        long now = System.currentTimeMillis();
        long timeGap = (now - timeStamp) / 1000;
        leftWater = Math.max(0, leftWater - timeGap * permitsPerSecond);
        timeStamp = now;
        
        // 如果未满，则放行；否则限流
        if (leftWater < capacity) {
            leftWater += 1;
            return true;
        }
        return false;
    }
}

Ini bukan pelaksanaan lengkap algoritma baldi bocor Kod di atas hanya menyemak sama ada trafik akan ditinggalkan, iaitu, tryAcquire kembali benar kepada menunjukkan baldi bocor belum penuh, jika tidak, bermakna baldi bocor sudah penuh dan permintaan dibuang.

Jika anda ingin membocorkan trafik pada kadar yang tetap, anda biasanya harus melaksanakannya dengan baris gilir FIFO Apabila tryAcquire mengembalikan benar, permintaan akan dibariskan, dan kemudian permintaan akan dikeluarkan dari baris gilir pada. frekuensi tetap untuk pemprosesan. Kod sampel adalah seperti berikut:

@Test
public void testLeakyBucketRateLimiter() throws InterruptedException {
    ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
    ExecutorService singleThread = Executors.newSingleThreadExecutor();

    LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(20, 20);
    // 存储流量的队列
    Queue<Integer> queue = new LinkedList<>();
    // 模拟请求  不确定速率注水
    singleThread.execute(() -> {
        int count = 0;
        while (true) {
            count++;
            boolean flag = rateLimiter.tryAcquire();
            if (flag) {
                queue.offer(count);
                System.out.println(count + "--------流量被放行--------");
            } else {
                System.out.println(count + "流量被限制");
            }
            try {
                Thread.sleep((long) (Math.random() * 1000));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    });
  
    // 模拟处理请求 固定速率漏水
    scheduledExecutorService.scheduleAtFixedRate(() -> {
        if (!queue.isEmpty()) {
            System.out.println(queue.poll() + "被处理");
        }
    }, 0, 100, TimeUnit.MILLISECONDS);

    // 保证主线程不会退出
    while (true) {
        Thread.sleep(10000);
    }
}

Tujuan algoritma baldi bocor adalah terutamanya untuk melicinkan trafik pecah dan menyediakan mekanisme untuk memastikan trafik pecah dalam rangkaian disepadukan ke dalam trafik yang lancar dan stabil.

Walau bagaimanapun, kerana baldi bocor mengawal trafik terlalu ketat, sumber sistem tidak boleh digunakan sepenuhnya dalam sesetengah senario, kerana kadar kebocoran baldi bocor adalah tetap, walaupun hiliran boleh mengendalikan trafik yang lebih besar pada masa tertentu, Bocor baldi juga tidak membenarkan trafik pecah melalui.

04 Token Baldi

Bagaimana untuk membenarkan trafik pecah sambil mengehadkan kadar trafik? Ketahui tentang algoritma baldi token! Algoritma baldi token menghantar token ke baldi token pada kadar yang tetap Apabila permintaan tiba, ia cuba mendapatkan token daripada baldi token Hanya apabila token diperolehi boleh ia dikeluarkan, jika tidak, ia akan ditolak.

Timba token mempunyai ciri-ciri berikut:

1 Token dikeluarkan pada kadar tetap dengan mengandaikan bahawa kadar had semasa ialah v/s, ini bermakna satu token dikeluarkan setiap 1 /v saat

2. Andaikan kapasiti baldi token adalah b. Jika baldi token penuh, token baharu akan dibuang

3 ialah baldi token Terdapat token dalam

Terdapat dua parameter yang patut diberi perhatian dalam algoritma baldi token, iaitu kadar had semasa v/s dan kapasiti baldi token b, kadar a mewakili had semasa daripada pengehad semasa dalam keadaan biasa, dan b ialah singkatan letusan, menunjukkan trafik letusan maksimum yang dibenarkan oleh pengehad semasa.

Sebagai contoh, b=10 apabila baldi token penuh, terdapat 10 token yang tersedia Pada masa ini, 10 permintaan dibenarkan melalui pengehad aliran pada masa yang sama (darjah trafik tertentu pecah dibenarkan). 10 permintaan ini Selepas token digunakan serta-merta, trafik berikutnya hanya boleh melalui pengehad aliran pada kadar r.

Pelaksanaannya adalah seperti berikut:

public class TokenBucketRateLimiter extends MyRateLimiter {
    /**
     * 令牌桶的容量「限流器允许的最大突发流量」
     */
    private final long capacity;
    /**
     * 令牌发放速率
     */
    private final long generatedPerSeconds;
    /**
     * 最后一个令牌发放的时间
     */
    long lastTokenTime = System.currentTimeMillis();
    /**
     * 当前令牌数量
     */
    private long currentTokens;

    public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
        this.generatedPerSeconds = generatedPerSeconds;
        this.capacity = capacity;
    }

    /**
     * 尝试获取令牌
     *
     * @return true表示获取到令牌，放行；否则为限流
     */
    @Override
    public synchronized boolean tryAcquire() {
          /**
           * 计算令牌当前数量
           * 请求时间在最后令牌是产生时间相差大于等于额1s（为啥时1s？因为生成令牌的最小时间单位时s），则
           * 1. 重新计算令牌桶中的令牌数
           * 2. 将最后一个令牌发放时间重置为当前时间
           */
        long now = System.currentTimeMillis();
        if (now - lastTokenTime >= 1000) {
            long newPermits = (now - lastTokenTime) / 1000 * generatedPerSeconds;
            currentTokens = Math.min(currentTokens + newPermits, capacity);
            lastTokenTime = now;
        }
        if (currentTokens > 0) {
            currentTokens--;
            return true;
        }
        return false;
    }
}

Apa yang perlu difikirkan ialah pelaksanaan yang sangat mudah untuk difikirkan ialah corak pengeluar-pengguna untuk kerap menambah; token kepada baris gilir menyekat, dan cuba untuk Benang yang melepasi pengehad semasa bertindak sebagai utas pengguna, dan hanya dibenarkan melepasi pengehad semasa jika ia memperoleh token daripada baris gilir menyekat.

Disebabkan ketidakpastian penjadualan benang, ralat pemasa adalah sangat besar dalam senario konkurensi tinggi Pada masa yang sama, pemasa itu sendiri akan mencipta urutan penjadualan, yang juga akan menjejaskan prestasi sistem.

05 Log gelongsor

Log gelongsor ialah algoritma pengehadan semasa yang agak "tidak popular" tetapi sangat berguna. Algoritma pengehadan kadar log gelongsor perlu merekodkan cap masa permintaan, yang biasanya disimpan menggunakan koleksi tersusun Kami boleh menjejaki semua permintaan pengguna dalam tempoh masa dalam satu koleksi tertib.

假设我们要限制给定T时间内的请求不超过N，我们只需要存储最近T时间之内的请求日志，每当请求到来时判断最近T时间内的请求总数是否超过阈值。

实现如下：

public class SlidingLogRateLimiter extends MyRateLimiter {
    /**
     * 每分钟限制请求数
     */
    private static final long PERMITS_PER_MINUTE = 60;
    /**
     * 请求日志计数器, k-为请求的时间（秒），value当前时间的请求数量
     */
    private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();

    @Override
    public synchronized boolean tryAcquire() {
        // 最小时间粒度为s
        long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
        // 获取当前窗口的请求总数
        int currentWindowCount = getCurrentWindowCount(currentTimestamp);
        if (currentWindowCount >= PERMITS_PER_MINUTE) {
            return false;
        }
        // 请求成功，将当前请求日志加入到日志中
        requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
        return true;
    }

    /**
     * 统计当前时间窗口内的请求数
     *
     * @param currentTime 当前时间
     * @return -
     */
    private int getCurrentWindowCount(long currentTime) {
        // 计算出窗口的开始位置时间
        long startTime = currentTime - 59;
        // 遍历当前存储的计数器，删除无效的子窗口计数器，并累加当前窗口中的所有计数器之和
        return requestLogCountMap.entrySet()
                .stream()
                .filter(entry -> entry.getKey() >= startTime)
                .mapToInt(Map.Entry::getValue)
                .sum();
    }
}

滑动日志能够避免突发流量，实现较为精准的限流；同样更加灵活，能够支持更加复杂的限流策略，如多级限流，每分钟不超过100次，每小时不超过300次，每天不超过1000次，我们只需要保存最近24小时所有的请求日志即可实现。

灵活并不是没有代价的，带来的缺点就是占用存储空间要高于其他限流算法。

06分布式限流

以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到限流的目的，但是由于机器性能，流量分布不均以及计算数量动态变化等问题，单机限流在分布式场景中的效果总是差强人意。

分布式限流最简单的实现就是利用中心化存储，即将单机限流存储在本地的数据存储到同一个存储空间中，如常见的Redis等。

当然也可以从上层流量入口进行限流，Nginx代理服务就提供了限流模块，同样能够实现高性能，精准的限流，其底层是漏桶算法。

Atas ialah kandungan terperinci Apakah algoritma pengehadan semasa yang biasa di Jawa?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!