The Leaky Bucket Algorithm

On one of our embedded devices there’s the facility to automatically dispatch text messages in response to particular events. To protect against the device sending out a storm of texts — say, from a bug in the event-detection code — we built a little algorithm to limit how many messages it generates in any given period. We borrowed it from the computer-networks field: the leaky bucket.

How does it work?

The metaphor is a bucket that leaks water at a steady rate. When the device wants to do a controlled action — send an SMS — it tries to add a drop to the bucket:

1. addDropToBucket() first checks whether some drops should have leaked out since the last call, and if so, lets them leak.
2. It then checks whether there’s space for a single drop. If there is, it adds the drop and returns true; otherwise it returns false.
3. If the caller gets true it performs the action; otherwise it doesn’t.

The Java code

Here’s the implementation — a bucket of 20 drops that leaks one drop per hour:

/**
 * Leaky bucket algorithm to prevent huge amounts of SMS text messages
 * from being dispatched by any insane processes. Each SMS message
 * sent adds a drop to the bucket which leaks at a constant rate.
 * Once the bucket fills, no message can be sent until a drop has
 * leaked out.
 */
private class LeakyBucketLimiter {

    private int numDropsInBucket = 0;
    private Date timeOfLastDropLeak = null;
    private final int  _BUCKET_SIZE_IN_DROPS = 20;
    private final long _MS_BETWEEN_DROP_LEAKS = 1000 * 60 * 60; // 1 hour

    public synchronized boolean addDropToBucket() {
        Date now = new Date();
        // first of all, let the bucket leak by the appropriate amount
        if (timeOfLastDropLeak != null) {
            long deltaT = now.getTime() - timeOfLastDropLeak.getTime();
            // note round down as part of integer arithmetic
            long numberToLeak = deltaT / _MS_BETWEEN_DROP_LEAKS;
            if (numberToLeak > 0) { // now go and do the leak
                if (numDropsInBucket <= numberToLeak) {
                    numDropsInBucket = 0;
                } else {
                    numDropsInBucket -= (int) numberToLeak;
                }
                timeOfLastDropLeak = now;
            }
        }

        if (numDropsInBucket < _BUCKET_SIZE_IN_DROPS) {
            numDropsInBucket++;
            return true;  // drop added
        }

        return false;     // overflow
    }
}

// here is how you use it
bucketLimiter = new LeakyBucketLimiter();
if (bucketLimiter.addDropToBucket()) {
    // dispatch SMS
}

This might seem excessive — but long-term reliability in our measurement and control devices is a really big thing for us. Each device needs to take care of itself for many years at a time.

Why such care matters

Virtually all of the devices we installed in our first year of operation are still running — most never once touched by a human hand. That obsession with field reliability is exactly what drives our bespoke hardware design and the firmware we ship onto devices, from LoRa motes to MQTT data pipelines.