esniff
BAN USERUse a RingBuffer of Size 3600, each element of the buffer is an int (or maybe an AtomicInt) and represents a counter for one second.
We'll have a variable for the current postion in the buffer, this will be used by readers to figure out where to start reading. And by the writer to know when it's advanced and needs to set the current position's counter to 1.
On each update calculate the current postion: requests_time/1000 % 3600
class RequestCounter{
int[] ring = new int[3600]; // this could be an AtmoicInt array to be thread safe.
long currentPos = 0;
public void increment(long requestTs){
writePos = requestTs/1000 % 3600;
if(writePos == currentPos){
ring[writePos]++;
}else{
ring[writePos] = 1;
currentPos = writePos;
}
}
public int getCountForLast(int seconds){
if(seconds > 3600) //Error?
seconds = 3600;
int count = 0;
int stopAt = currentPos-seconds;
for(pos = currentPos; pos > stopAt ; pos--){
count += ring[pos%3600] ;
}
return count;
}
//below write methods that call getCountForLast with 1, 60, 3600
}
Added benefit : RingBuffers will better utilize cache lines and avoid False Sharing.
- esniff June 20, 2013
@slbb Your right. And it could be solved by recalculating the current position at read time by having the reader pass in a timestamp or taking one in the read method. Then resetting each counter between the old current_position and the new current_position. In fact you'll need to do that on writes too, when the counter resets.
- esniff June 20, 2013Also I failed to mention that if you need to go the thread safe route with atomic ints, you'll also need to add double checked locks around the reseting of the counters. Personally this should be avoided, maybe by having an Actors own this, so only one thread is updating the ring.