Calculating bytes per second (the smooth way)

问题:

I am looking for a solution to calculate the transmitted bytes per second of a repeatedly invoked function (below). Due to its inaccuracy, I do not want to simply divide the transmitted bytes by the elapsed overall time: it resulted in the inability to display rapid speed changes after running for a few minutes.

The preset (invoked approximately every 50ms):

function uploadProgress(loaded, total){
    var bps = ?;
    $('#elem').html(bps+' bytes per second');
};

• How to obtain the average bytes per second for (only) the last n seconds and is it a good idea?
• What other practices for calculating a non-flickering but precise bps value are available?

回答1:

Your first idea is not bad, it's called a moving average, and providing you call your update function in regular intervals you only need to keep a queue (a FIFO buffer) of a constant length:

var WINDOW_SIZE = 10;
var queue = [];

function updateQueue(newValue) {
    // fifo with a fixed length
    queue.push(newValue);
    if (queue.length > WINDOW_SIZE)
        queue.shift();
}

function getAverageValue() {

    // if the queue has less than 10 items, decide if you want to calculate
    // the average anyway, or return an invalid value to indicate "insufficient data"

    if (queue.length < WINDOW_SIZE) {

        // you probably don't want to throw if the queue is empty, 
        // but at least consider returning an 'invalid' value in order to
        // display something like "calculating..."

        return null;
    }

    // calculate the average value
    var sum = 0;
    for (var i = 0; i < queue.length; i++) {
        sum += queue[i];
    }
    return sum / queue.length;
}

// calculate the speed and call `updateQueue` every second or so
var updateTimer = setInterval(..., 1000);

An even simpler way to avoid sudden changes in calculated speed would be to use a low-pass filter. A simple discrete approximation of the PT1 filter would be:

Where u[k] is the input (or actual value) at sample k, y[k] is the output (or filtered value) at sample k, and T is the time constant (larger T means that y will follow u more slowly).

That would be translated to something like:

var speed = null;
var TIME_CONSTANT = 5;

function updateSpeed(newValue) {    
    if (speed === null) {
        speed = newValue;
    } else {
        speed += (newValue - speed) / TIME_CONSTANT;
    }
}

function getFilteredValue() {
    return speed;
}

Both solutions will give similar results (for your purpose at least), and the latter one seems a bit simpler (and needs less memory).

Also, I wouldn't update the value that fast. Filtering will only turn "flickering" into "swinging" at a refresh rate of 50ms. I don't think anybody expects to have an upload speed shown at a refresh rate of more than once per second (or even a couple of seconds).

回答2:

A simple low-pass filter is ok for just making sure that inaccuracies don't build up. But if you think a little deeper about measuring transfer rates, you get into maintaining separate integer counters to do it right.

If you want it to be an exact count, note that there is a simplification available. First, when dealing with rates, arithmetic mean of them is the wrong thing to apply to bytes/sec (sec/byte is more correct - which leads to harmonic mean). The other problem is that they should be weighted. Because of this, simply keeping int64 running totals of bytes versus observation time actually does the right thing - as stupid as it sounds. Normally, you are weighting by 1/n for each w. Look at a neat simplification that happens when you weigh by time:

(w0*b0/t0 + w1*b1/t1 + w2*b2/t2 + ...)/(w0+w1+w2+...)

totalBytes/totalWeight

(b0+b1+b2+...)/(w0+w1+w2+...)

So just keep separate (int64!) totals of bytes and milliseconds. And only divide them as a rendering step to visualize the rate. Note that if you instead used the harmonic mean (which you should do for rates - because you are really averaging sec/byte), then that's the same as the time it takes to send a byte, weighted by how many bytes there were.

1 / (( w0*t0/b0 + w1*t1/b0 + ... )/(w0+w1+w2+...)) = totalBytes/totalTime

So arithmetic mean weighted by time is same as harmonic mean weighted by bytes. Just keep a running total of bytes in one var, and time in another. There is a deeper reason that this simplistic count actually the right one. Think of integrals. Assuming no concurrency, this is literally just total bytes transferred divided by total observation time. Assume that the computer actually takes 1 step per millisecond, and only sends whole bytes - and that you observe the entire time interval without gaps. There are no approximations.

Notice that if you think about an integral with (msec, byte/msec) as the units for (x,y), the area under the curve is the bytes sent during the observation period (exactly). You will get the same answer no matter how the observations got cut up. (ie: reported 2x as often).

So by simply reporting (size_byte, start_ms,stop_ms), you just accumulate (stop_ms-start_ms) into time and accumulate size_byte per observation. If you want to partition these rates to graph in minute buckets, then just maintain the (byte,ms) pair per minute (of observation).

Note that these are rates experienced for individual transfers. The individual transfers may experience 1MB/s (user point of view). These are the rates that you guarantee to end users.

You can leave it here for simple cases. But doing this counting right, allows for more interesting things.

From the server point of view, load matters. Presume that there were two users experiencing 1MB/s simultaneously. For that statistic, you need to subtract out the double-counted time. If 2 users do 1MB/s simultaneously for 1s, then that's 2MB/s for 1s. You need to effectively reconstruct time overlaps, and subtract out the double-counting of time periods. Explicitly logging at the end of a transfer (size_byte,start_ms,stop_ms) allows you to measure interesting things:

• The number of outstanding transfers at any given time (queue length distribution - ie: "am I going to run out of memory?")
• The throughput as a function of the number of transfers (throughput for a queue length - ie: "does the website collapse when our ad shows on TV?")
• Utilization - ie: "are we overpaying our cloud provider?"

In this situation, all of the accumulated counters are exact integer arithmetic. Subtracting out the double-counted time suddenly gets you into more complicated algorithms (when computed efficiently and in real-time).

回答3:

Use a decaying average, then you won't have to keep the old values around.

UPDATE: Basically it's a formula like this:

average = new_value * factor + average_old * (100 - factor);

You don't have to keep any old values around, they're all in the there at smaller and smaller proportions. You have to choose a value for factor that are appropriate to the mix of new and old values you want, and how often the average gets updated.

This is how the Unix "load average" is calculated I believe.