速率限制器不能正常工作

Question

我正在寫一個算法，它接收消息，然後確定它們是否符合建立的消息速率。

例如，在任何50秒的窗口中不會發送超過5條消息。因此，這個窗口必須是一個滾動窗口。

我已經從this post.實現了這個令牌桶算法但是，我不能一致地工作。它通過了一些測試用例，但不通過其他測試用例，這讓我認爲這裏隱藏着一個邏輯問題。

這是我到目前爲止有：

public class Messaging { 
//times in millis 
double time_before; 
double time_now; 
double now; 
double time_passed; 

double allowance; 

//constants 
static double per = 50000; // 50 seconds 
static double rate = 5; //5 messages 

public Messaging(){ 
    time_before = System.currentTimeMillis(); 
    allowance = rate; 
} 

public void onEvent(){ 
    time_now = System.currentTimeMillis(); 
    time_passed = time_now - time_before; 
    time_before = time_now; 

    allowance += time_passed * (rate/per); 

    if (allowance > rate){ 
     allowance = rate; 
     System.out.println("Reset Allowance"); 
    } 

    if (allowance < 1.0){ 
     System.out.println("Discard"); 
    }else{ 
     System.out.println("Forward message"); 
     allowance -= 1.0; 
    } 


} 

這不工作，雖然！

public static void main(String[] args) { 
    Messaging orders = new Messaging(); 
    for (int i = 0; i < 10; i++) { 
     orders.onEvent(); 
     try { 
      Thread.sleep(5000); 
     } catch (Exception ex) { 

     }   
    } 
} 

運行上面的代碼中給出了這樣的：

Forward message. Time: 1469830426910 
Forward message. Time: 1469830431912 
Forward message. Time: 1469830436913 
Forward message. Time: 1469830441920 
Forward message. Time: 1469830446929 
Forward message. Time: 1469830451937 
Forward message. Time: 1469830456939 
Forward message. Time: 1469830461952 
Forward message. Time: 1469830466962 
Discard. Time: 1469830471970 
Total time passed: 50067 

爲什麼只被丟棄的最後一條消息？不應該允許遞減到第5條消息後自動失效嗎？

我希望能幫助您解決這個問題。實際的實現將採用沒有隊列的專有語言等。

Answer 1

對於速率受限的滑動窗口，您需要排隊每條消息以及它的時間戳。這樣，當隊列已滿時，您只需丟棄任何新消息。當隊列末尾的消息已經超過分配的時間時，他們離開隊列，並且有更多新消息的空間。

class MessageBuffer { 
    class Message { 
     double timestamp; 
     String value; // Can be any type you need it to be 

     public Message(double timestamp, String value) { 
      this.timestamp = timestamp; 
      this.value = value; 
     } 
    } 

    static final double WINDOW_SIZE = 5; 
    static final double TIME_LIMIT = 50000; 

    Queue<Message> messages = new ArrayDeque<>(WINDOW_SIZE); 

    public void onEvent(String message) { 
     double now = System.currentTimeMillis(); 

     // If the queue has messages in them that are no longer in the sliding window, 
     // remove them from the queue 
     while (messages.size() > 0 
      && messages.peek().timestamp + TIME_LIMIT > now) 
      messages.remove(); 

     // If there is room in the queue, process this message, otherwise discard it 
     if (messages.size() < WINDOW_SIZE) { 
      System.out.println("Forward message: " + message); 
      messages.add(new Message(now, message)); 
     } else { 
      System.out.println("Discard message: " + message); 
     } 
    } 
} 

沒有這個時間戳信息，當消息離開滑動窗口，你看不出來，所以你無法知道你的窗口是否已滿。僅供參考，您鏈接的示例只是一個近似值，實際上可以在50秒內將您限制爲少於5條消息。

兩個小NIT-精選：

• 在面向對象的世界裏，類事情，不行動。在大多數情況下，你的類名應該是一個名詞，它描述了是（MessageBuffer），而不是描述它做什麼的動詞（消息傳遞）。
• 變量now不應該是一個成員變量 - 當你第一次分配它時，它確實代表當前時間，但是一旦該方法結束，並且調用另一個方法，則該值是陳舊的 - 它不會實際上代表當前時間。

Answer 2

您正在使用的算法是一種近似值 - 平均而言，它會給出您要查找的比率。在original post，作者聲稱：

「津貼」的速度增長最多5/8單位每秒，即最多五個單位每八秒。每個轉發的消息會扣除一個單位，因此每8秒鐘不能發送超過五條消息。

這並不完全正確 - 如果允許值開始於最大值（例如5），則會以每秒5/8單位增長，然後對於每條發送的消息，都會扣除1。因此津貼以每秒3/8單位的速度縮小，從5開始，我們可以在節流發生之前發送大約10條消息。

如果你有一段時間你的信息沒有像你的油門速度一樣快，那麼它會增加配額。然後，當這些消息加快速度時，您有一個短暫的時間段，在節流開始之前，您最終可能會處理2 * rate消息。如果您將循環更改爲執行20次迭代而不是10次，那麼最終會看到節流確實表現得如你所期望的那樣。或者，如果您將津貼設置爲0開始，而不是速率，它將立即調節。