Title: Data structure for keeping track of past X hours of data
Tags: performance;algorithm;caching
Question: I am getting a stream of user event logs in real-time (about 100 logs per second, userbase 10M+). Each log has a timestamp and a username attached. For each username, I want to keep track of the number of events for the past X hours. What would be an efficient data structure for doing this? And how could it be stored?
I am thinking about a moving average algorithm, but not sure how to limit the window to X hours?
Any help appreciated.
So what I really need is a cache of sorts which quickly allows me to look up the number of events for each user during the specified time period. Not sure how expensive calculations I can afford.
The purpose is anomaly detection, and to look up the number for each incoming log message/username, and then check if that user is below/above a certain threshold.
Implementation
Based on the suggested solution from @Dgrin91, here is a working implementation in Java. Even though it is quite specific for my usecase, perhaps someone else might find it useful.
https://gist.github.com/anonymous/9931570
Comment: Chunk the raw events into buckets (say 1 minute, 10 seconds, whatever works for your situation) containing counts, then keep the buckets in a circular buffer adding up to X hours, calculate the average on demand. Without more detail about what you'll be using it for it's hard to be more specific.

Comment: A `LinkedHashMap` would keep track of user's log entries and preserve the order in which they arrived. A cache of sorts.

Comment: @JimGarrison I've provided some more details above. However, chunking the raw events into 10 second buckets seems like a possible approach. But how expensive do you think the calculations will be? I need to get the average for every single log message.

Here is the accepted answer: If you dont mind building it on your own, here is a quick solution I thought of -
Maintain two arrays each element of the array will represent a unit of time (lets say 1 minute). Each array will be of size X (the length of time you want to store). All messages from a certain minute go into the corresponding element (per your favorite datastruct). You start by filling one array. Every minute you switch to the next element. When you hit the end of the first array you move onto the second. However you now start deleting elements off the front of the first array (preparing it for the next cycle). By the time you reach the end of the second array, your first array will be clear and ready for messages. The cycle can continue forever.
As far as efficiency, this seems very good. Its basically just an array lookup, which is O(1). The space efficiency is also minimal. You aren't actually storing 2 full arrays, the "garbage collector" you implement keeps it down to 1 at all times.
Mockup code -
Array Arr1 = new Array(X);
Array Arr2 = new Array(X);
Time startTime = CurrentTime();
int count = 0;
Set users = new Set();
void OnMessageRecieved(Message message){
Users.get(message.user).insert(message);
void insert(Message m){
Time currentTime = CurrentTime();
int iter = currentTime-startTime;
if(iter&gt;2*X){
startTime=CurrentTime;
iter=0;
if(iter&gt;X){
iter-=X;
arr2[iter]+=message;
else{
arr1[iter]+=message;
count++;
And then have a separate cleanup thread for the old logs. The core code of the thread will be something like -
void run(){
while(true){
Time currentTime = CurrentTime();
int size = currentArray[currentTime-x].size;
currentArray[currentTime-x].reset();
count-=size;
sleep(60);
Comment for this answer: @hamohl Oh, I didnt realize I need to keep a message count per user, so I didnt put that into my allenphilip@example.net. I suppose you could just do some extra parsing in the `OnMessageRecieved()` function I made
Comment for this answer: @hamohl Ok, so this time I actually read it, I promise :). You could just have a Map of users to the data struct I made up. In `OnMessageRecieved` you just feed it in per user. The datastruct could maintain a count easily.
Comment for this answer: @hamohl Im confused about what you mean by average. Do you just mean the message count for a specific user for the past X hours?
Comment for this answer: @hamohl Ok, I updated the code. Now it stores an instant access count (excluding possible thread locking issues, but the garbage collector is so small it shouldn't matter).
Comment for this answer: @hamohl This is per user. Im being a bit lazy with my code, but the implication here is that there are two classes: a 'Logger' class that handles the `OnMessageRecieved`, and a 'Container' class that actually has the arrays and handles the insertion/deletion. You instantiate one instance of 'Container' per user.
Comment for this answer: I do not mind building it, interesting approach. How would you suggest keeping track of the message count per user? With the scale of the situation, iterating the arrays on each message feels way expensive..
Comment for this answer: Yeah, currently I have Memcached set up for the Map functionality. The problem I see it is calculating the average on every single OnMessageReceived() as it could approach O(n^2). But perhaps it is the only solution
Comment for this answer: Sorry, yep, the message count is what I mean.
Comment for this answer: Thanks. However, the count needs to be per user, not an aggregate. Sorry for not making it obvious! So basically I need a Cache
Comment for this answer: Alright, I will try this out. The 2-array approach is pretty creative, thanks for the effort.


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 3, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2014:00:03/27/14', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<performance><algorithm><caching>', 'Title': 'Data structure for keeping track of past X hours of data', 'ViewCount': 580, 'id': 22698172, 'user_AboutMe': "<p>I enjoy any type of engineering challenge that can be solved with software, with an emphasis on web development. My approach is nothing's impossible!</p>\n", 'user_AccountId': 955556.0, 'user_DisplayName': 'hampusohlsson', 'user_Reputation': 9939.0, 'user_Views': 392.0, 'user_id': 980929.0}}