目錄

一、漏桶（Leaky Bucket）

簡易實現：

效果：

二、令牌桶算法

簡易實現：

效果：

兩種算法對比：

一、漏桶（Leaky Bucket）

????????算法思路簡單，水（請求）先進入到漏桶中，漏桶以一定的速度出水（接口有響應速率），當水流速度過大直接溢出（訪問頻率超過接口響應頻率），然后就拒絕請求，可以看出漏桶算法能強制限制數據的傳輸速率。

假設我們有一個桶，我們希望以隨機的速率向桶中倒水，并以恒定的速率從桶中取水。因此我們需要在桶底部打一個固定大小的洞，這樣來保證水流處的速率是恒定的。由于桶的體積有限，因此倒滿后就停止。

水流入的速率可以改變，但輸出的速率是恒定的。這種平滑輸出流量的方法稱為漏桶技術。突發進入的流量存儲在桶中，并以穩定的速率輸出。

簡易實現：

package com.suanfa;

public class test2 {
    //漏桶算法
    public static void main(String[] args) {
        //t1,t2線程每1秒往桶里添加一個請求
        Bucket bucket=new Bucket(0);
        Thread t1=new Thread(bucket);
        Thread t2=new Thread(bucket);
        //t3線程恒定速度處理請求
        Thread t3=new Thread(new Handle(bucket));

        t1.start();
        t2.start();
        t3.start();
    }
}
class Bucket implements Runnable{
    int max=20;//桶的最大容量
    int num;//請求數
    Bucket(int num){
        this.num=num;
    }
    @Override
    public void run() {
        while (true){
            synchronized (this){
                if (num>=max){
                    System.out.println("桶的容量滿了，該請求被丟失");
                }else {
                    num++;
                    System.out.println("往桶里添加一個請求，目前有"+num+"個請求");
                }
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}
//處理請求
class Handle implements Runnable{
    Bucket b;
    Handle(Bucket b){
        this.b=b;
    }
    @Override
    public void run() {
        while (true){
            synchronized (b){
                if (b.num>0){
                    b.num--;
                    System.out.println("已處理一個請求，目前還剩"+b.num+"個請求");
                }else {
                    System.out.println("桶已空，不需要處理請求");
                }
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

效果：

? ? ? ? 桶中請求數有限制，滿了則丟棄，桶以一定速度處理請求

二、令牌桶算法

????????令牌桶算法的原理是系統會以一個恒定的速度往桶里放入令牌，而如果請求需要被處理，則需要先從桶里獲取一個令牌，當桶里沒有令牌可取時，則拒絕服務。

令牌桶算法和漏桶算法不同的是，有時后端能夠處理一定的突發情況，只是為了系統穩定，一般不會讓請求超過正常情況的60%，給容災留有余地。但漏桶算法中后端處理速度是固定的，對于短時的突發情況，后端不能及時處理，和實際處理能力不匹配。

令牌算法是以固定速度往一個桶內增加令牌，當桶內令牌滿了后，就停止增加令牌。上游請求時，先從桶里拿一個令牌，后端只服務有令牌的請求，所以后端處理速度不一定是勻速的。當有突發請求過來時，如果令牌桶是滿的，則會瞬間消耗桶中存量的令牌。如果令牌還不夠，那么再等待發放令牌（固定速度），這樣就導致處理請求的速度超過發放令牌的速度。
?

簡易實現：

package com.suanfa;

public class test{

    //令牌桶算法

    public static void main(String[] args) {
        Token t=new Token(20);//初始20個
        //t1每秒往桶里放令牌
        Thread t1=new Thread(t);

        //t3,t4模擬請求，處理一個請求需要從桶里獲取一個
        // 令牌，沒有令牌，就丟棄
        Thread t3=new Thread(new Use("a",t));
        Thread t4=new Thread(new Use("b",t));

        t1.start();
        t3.start();
        t4.start();


    }
}
//往桶里放令牌
class Token implements Runnable {
    //令牌數
    int token;
    Token(int token){
        this.token=token;
    }
    @Override
    public void run() {
        while(true){
            synchronized (this){

                token++;
                System.out.println("往桶里放一個令牌,目前共有"+token+"個令牌");

                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }


}
class Use implements Runnable {
    //請求名
    String name;
    Token t;
    Use(String name,Token t){
        this.t=t;
        this.name=name;
    }
    @Override
    public void run() {
        while(true){
            synchronized (t){
                if (t.token>0){
                    t.token--;
                    System.out.println(name+"在桶里獲取1個令牌，還剩"+t.token+"個令牌");
                }else {
                    System.out.println("目前桶里無令牌，請求失效");
                }
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

效果：

? ? ? ? 處理請求需要令牌，沒有令牌則丟棄該請求

兩種算法對比：

????????漏桶算法通?？梢杂糜谙拗圃L問外部接口的流量，保護其他人系統，比如我們請求銀行接口，通常要限制并發數。

????????令牌桶算法生成令牌的速度是恒定的，而請求去拿令牌是沒有速度限制的。這意味，面對瞬時大流量，該算法可以在短時間內請求拿到大量令牌，可以處理瞬時流量，而且拿令牌的過程并不是消耗很大的事情。令牌桶算法通?？梢杂糜谙拗票辉L問的流量，保護自身系統。