[GistNoesis]

How bad is the code I want to write even though I know it is wrong :

initialize : double credit = N

At every request :

penalty = (elapsedTime / window_size) - (1/N)

gain = N* (elapsedTime / window_size)

credit = min( credit + gain - (penalty<0) , N)

if( credit < 0 ) throw exception

[gsliepen]

I wouldn't call it penalty, but cost, and if credit = N, then I assume the cost of one call would just be 1. So:

    gain = N * (elapsedTime / window_size);
    credit = min(credit + gain, N);
    if (credit >= 1) {
        credit--;
        log(...);
    } else {
        return; /* not enough credits */
    }

Your approach has the nice property that after the initial burst, you get regularly spread out log messages, whereas the linked list approach will stay bursty.

[GistNoesis]

I was trying to express the sliding window constraint as a violation of the pigeon-hole principle : to violate the constraint you have to have at least N+1 intervals that are shorter than window_size/N over the window_size.

But I'm not really sure of the value it adds over simply taking a cost of 1 as you suggest. When time beween requests are spreaded more than window_size/N they don't cost credit. This mean you have a smaller number of "hot" clients (clients who are not full credit) to monitor.

The second idea that often occurs in problems with sliding windows is the telescoping sum which is hiding implicitly in the sum of elapsed Times.