Sunday, February 10, 2008

Throttling requests - C++/Windows

In a post a few days ago I posted a problem - ensure that a service/API/resource is not called more than N times in any fixed interval. Here's the solution in C-ish C++.

For more discussion (and for perl implementation - I don't read perl so I can't vouch for its correctness though), see this post and comments: http://1-800-magic.blogspot.com/2008/02/throttling-service-requests-puzzle.html.


#include <windows.h>
#include <stdio.h>
#include <assert.h>

// Class that throttles requests. Ensures that
// the StartRequest cannot be called more than
// a given amount of time in any given interval.
//
// StartRequest blocks until this requirement
// is satisfied.
//
// TryStartRequest returns 0 if the request was
// cleared, or a non-0 number of milliseconds to
// sleep before the next attempt.
//
// Simple usage, 10 requests per second:
//
// Throttler *t = new Throttler(10, 1000);
// ...
// ServiceRequest(Throtter *t, ...) {
// t->StartRequest();
// .. do work ..
//
class Throttler {
private:
DWORD *ticks;
int max_requests;

DWORD interval;

int tick_next;
int tick_last;

CRITICAL_SECTION cs;

int Next(int tick) {
int next = tick + 1;
return next == max_requests ? 0 : next;
}

// Removes all expired entried from the queue.
// cs should be held.
void PopExpired(DWORD tick_now) {
assert(cs.OwningThread ==
(HANDLE)GetCurrentThreadId());

while (tick_last != tick_next) {
if (tick_now - ticks[tick_last] < interval)
break;
tick_last = Next(tick_last);
}
}

public:
Throttler(int number_of_requests,
DWORD interval_ms) throw(char *) {
// leave one extra space for sentinel
max_requests = number_of_requests + 1;
ticks = new DWORD[max_requests];
if (!ticks)
throw "Out of memory";

interval = interval_ms;

tick_next = tick_last = 0;

InitializeCriticalSection(&cs);
}

~Throttler() {
delete [] ticks;
DeleteCriticalSection(&cs);
}

DWORD TryStartRequest(void) {
DWORD result = 0;
EnterCriticalSection(&cs);

DWORD now = GetTickCount();
PopExpired(now);

int next = Next(tick_next);
if (next != tick_last) {
// We have space.
ticks[tick_next] = now;
tick_next = next;
} else {
// We've filled the queue. Calculate the
// wait time.
result = interval - (now - ticks[tick_last]);
assert(result <= interval); // no overflow
}
LeaveCriticalSection(&cs);
return result;
}

void StartRequest(void) {
while (DWORD sleep = TryStartRequest()) {
Sleep(sleep);
}
}
};

No comments: