レートリミッタが正しく動作しない

Question

メッセージを取り込んで、確立されたメッセージングレートに準拠しているかどうかを判断するアルゴリズムを作成しています。

たとえば、ANY 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; 
    } 


} 

しかしこれは動作しません！唯一の最後のメッセージが破棄されているのはなぜ

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 

：上記のコードを実行する

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) { 

     }   
    } 
} 

はこれを提供しますか？ 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では、作家が主張：

は「手当」は8秒あたり最大5台で、すなわち最大で秒間あたりの速度で5/8単位を成長します。転送されるすべてのメッセージは1つのユニットを差し引くため、8秒ごとに5つ以上のメッセージを送信することはできません。

これはあまり真実ではありません。許容量が最大値である5から始まり、1秒あたり5/8単位で増加し、送信されたすべてのメッセージについて1が差し引かれます。したがって、手当は3/8単位/秒の割合で縮小しており、5から開始して、調整が行われる前に約10件のメッセージを送信することができます。

あなたのメッセージがあなたのスロットル率と同じ速さで来ていない期間があれば、それは手当を積み上げます。その後、メッセージがペースを上がれば、スロットルが始まる前にメッセージ2 * rateが処理されることがあります。10回ではなく20回繰り返すようにループを変更すると、最終的にスロットリングあなたが期待するように行動します。また、料金の代わりに手当を0に設定すると、すぐにスロットルがスローされます。