Josh Bryan

I just thought I’d announce that today, one of the projects I’ve been working on recently went live. Yo Journal is an online personal journal that allows you to keep track of daily entries, categorize those entries, and also keep track of specific types of data like weight, movies, and books. To read more about Yo Journal, you should visit the about page, or the tour. There is a free edition as well as an expanded version for pay that adds features like file uploads and categories.

In several current projects I have been working on AJAXifying old systems and building new systems with AJAX components.  Though I have tried to take advantage of open libraries such as prototype.js and Open Rico, I have yet to find a good framework that incorporates both the server-side and client-side programming needs.  So, upon hearing news about the Open Ajax coalition of BEA, Borland, the Dojo Foundation, Eclipse Foundation, Google, Laszlo Systems, Mozilla, Novell, Openwave, Oracle, Red Hat, Yahoo, Zend, and Zimbra, naturally I got excited.

This could finally lend the kind of stability and formality to the technology that would aleviate many of my current headaches as a developer and many of the criticisms from users.  The awesome thing about AJAX is that it is built on non-proprietary technologies unlike any of the other leading rich client technologies; thus, if it could be developed in a manner that gives it the same formality and maturity of other web standards, such as HTML and XML, it would go a long way toward simplifying development, cutting costs, and improving user’s experiences.  I believe the companies backing it have the experience and sway to make it happen.

For a recent project I was working on in Java, I needed to have a function to keep statistics about how often a particular event occurred. In particular, I wanted to know the average rate of events over the last t seconds. It is fairly straight forward to calculate the average rate of events over the life of the process (sum events and divide by uptime), however, calculating a moving average seems to be a little less intuitive.

In order to calulate the average rate for the past t seconds requires keeping track of the number of events that occurred in that amount of time, which means somehow expiring events after the interval t. This would mean having some list of timestamps to search and remove only the ones that are too old. This approach has the drawback that the number of comparisons required by the CPU for a given time period t would scale exponentially to the number of events in the same time period t (assuming the average is computed each time the event occurs). This is because as the number of events increases, the number of events to expire increases proportionately.

I soon reallized that for my purposes, all I really needed was an approximate, noise smoothed, indicator of the activity over the last several minutes. After a quick review of statistics, I remembered a exponentially smoothed moving average formula:

A_t = A_t-1 + .1(M_t – A_t-1) where A_t is the average, and M_t is the weight given to t‘s value. (a good explanation can be found here)

This particular equation is designed to be used to calculate an average at a specific interval. However, I want to calculate an average at the time of the event. Sure, I could set up a separate thread that monitors the number of events that took place at a specific interval, but it would be a little more straight forward and useful to me if the calculation occurred in the same thread. This is partly because the time between events can vary greatly (10 minutes to 10 milleseconds), and if I set the interval for the monitoring thread at too low of a resolution, I don’t get an accurate reading if the number of events suddenly spiked. Similarly, if I set it too high, I use a lot of unnecessary cpu during the longer waits.

The solution I finally settled on was to use the above equation, but define M_t in terms of the interval i since the last event. I reasoned that the greater the interval i, the greater M_t should be. I want to count a large number of closely occurring events should adjust the moving average less than one event that occurred 5 minutes ago. The result is that I scaled M linearly such that an interval of 0 has a weight of 0, and an interval of 5 minutes (the time window I’m interested in) has a weight of 1. This is the only part of this calculation I feel I may have not fairly reasoned, as it results in a formula that, for a constant rate of events, will constantly approach, but never reach, the actual rate. Furthermore, a high rate of events will approach it’s limit slower than a low rate of events.

Despite these drawbacks, this calculation did serve it’s purpose fairly well. As one watches the moving average, it approaches the actual rate with a capacitive attack and decay, and it gives a fairly reasonable indication of how the system performs. Below is code I used. Feel free to study it, use, and most of all critique it. Any feedback I get on how to do this better would be appreciated.

public class Statistics {
    /**
     * * Number of events that occurred.
     * */
    private long events = 0;
    
    /**
     * * The last time a connection was borrowed.
     * */
    private long lastEventTime = System.currentTimeMillis();
    /**
     * * The last computed moving load average.
     * */
    private double lastMovingLoadAvg = 0.0;
    
    /**
     * * Increments the event count and recomputes the movingLoadAverage.
     * */
    public synchronized void registerEvent( ) {
        //increment number borrowed
        this.events++;
        
        //calculate the load average
        lastMovingLoadAvg = getMovingLoadAverage();
        
        //log the last borrow time
        this.lastEventTime = System.currentTimeMillis();
    }
    
    /**
     * * Calculates the moving load average as a variation of an
     * exponentially smoothed average.
     * * It approximates the number borrowed in the last 5 minutes using a
     * variably weighted
     * * time since the last event occured to adjust the average.
     * */
    public double getMovingLoadAverage() {
        //current time
        long now = System.currentTimeMillis();
        
        //time since last borrow
        long timeSinceLast = now - lastEventTime;
        
        //weight closely occuring events less than distant ones (closely
        //occuring events provide more samples, or
        //are anomolies. We make our window of relevance = 5 mins (300000ms).
        double weight = timeSinceLast / 300000D;
        weight = (weight < 1) ? weight : 1;
        
        //calculate rate
        double delta = 0;
        if (timeSinceLast > 0) //avoid div by 0
            delta = (60000D / timeSinceLast) - lastMovingLoadAvg; //newrate - last avg rate
                
        return lastMovingLoadAvg + (delta * weight);
    }
}

Soon, I’ll try to post up a small applet that demonstrates this class. If i get any great suggestions, i’ll probably incorporate them as well.

Ben Bryan is a Chicago area photographer, and my brother, who has recently launched a website for his business, Aerosol Wax Photography. Though most of the site has been designed by him, I am currently working with him as consultant / backend engineer to expand the site into the world of e-commerce.

As an artist, Ben has a broad spectrum of experience ranging from fine art cinematography to event photography. His current business is focused on pet photography and wedding photography, but will soon branch out to include online sales of some of his fine art pieces.