Bob Balaban's Blog

     
    alt

    Bob Balaban

     

    TokenBucket 2.0!

    Bob Balaban  February 7 2015 05:07:16 PM
    Greetings, Geeks!

    I went back and looked at the code I posted here several months ago for doing time-based access counting. I realized that it could be improved and cleaned up just a bit, so I'm sharing a revised version with you here.


    import java.util.Date;
    import java.util.LinkedList;

    public class TimeBasedAccessList {

         // This is the list of time values. New entries are always
         // added at the "tail", so the "head" is always the oldest value.
         // This collection is a little bit more efficient than using (for
         // example) a TreeSet, which will sort new entries into the tree.
         private LinkedList timeSet = new LinkedList();
         private int nCalls;                        // count of allowed calls
         private long timeWindow;        // in millisec
         
         public TimeBasedAccessList(int N, long M) {
                 nCalls = N;
                 timeWindow = M;
         }

         public synchronized boolean isCallOK() {
                 long now = new Date().getTime();
                 long earliest = now - this.timeWindow;
                 
                 // remove entries older than "earliest"
                 // can't use "for" loop with removals inside
                 while (!this.timeSet.isEmpty()) {
                         Long L = this.timeSet.peekFirst();         // "lowest" valued element is earliest timestamp
                         if (L.longValue() <= earliest) {
                                 this.timeSet.remove(L);
                         }
                         else {
                                 // no more entries out of window
                                 break;
                         }
                 } // end for
                 
                 // see how many entries there are
                 if (this.timeSet.size() >= this.nCalls) {
                         return false;
                 }
                 
                 // add new entry at the end of the list
                 this.timeSet.add(new Long(now));
                 return true;
         } // end isCallOK
         
    } // end class

    I really only made 3 changes:
    1) removed "volatile" declaration on the member timeSet. Since this member variable is only ever set one time (at object construction time), there's no point in making it volatile.

    2) I changed the data structure used to store the list of date/time values from a TreeSet to a somewhat simpler LinkedList, which in this application is a bit more efficient. The reason is that with a TreeSet, every time you add a new element, the TreeSet evaluates the "ordinary value" of that element to see where it should sit in the (sorted) tree. We don't really need that functionality here, because we know for sure that newer elements (later time values) are going to be larger than any earlier ones (because time marches on, naturally). So we just add new elements to the end of the list, and examine and/or remove older elements (smaller time values) from the front or head of the list.

    3) Use the LinkedList specific method peekFirst() to look at (but not remove) the element at the head of the list. Note that the remove() and add() methods don't change, they exist in both classes.

    So, there you have it. Enjoy, and Geek ya Later!

    Follow me on Twitter @LooseleafLLC
    This article ┬ęCopyright 2015 by Looseleaf Software LLC, all rights reserved. You may link to this page, but may not copy without prior approval.

    Comments

    1David Hablewitz  2/19/2015 9:21:23 AM  TokenBucket 2.0!

    Bob, miss you at the Ask IBM session (Ask the Developers, Ask the Product Managers) at IBM ConnectED 2015 (Lotusphere).