Tuesday, 24 December 2013

Peak Number of Concurrent Sessions Count Algorithm - Sheer Geniousness

So its been a while since someone asked me to generate reports for a web application and in particular, be able to profile the load on the server via different metrics. Metrics like longest running session, response times per service/request all seemed pretty easy...until I got stumped by peak number of concurrent sessions.

Why you might ask? Because the problem is more complex than what meets the eye. You need a clever way to determine overlaps between sessions and then count the maximum overlap per day.

Oh and did I mention I wanted to solve this all at the database level? If you'd want to solve this programmatically, the solution isn't all that difficult. A simple O(n^2) algorithm would be:

for (session1 in sessions) {
  for (session2 in sessions) {
    //determine if there is an overlap
    if (session1 != session2 && session1.startTime <= session2.endTime && session1.endTime >= session2.startTime) {

//find the session with the max overlap
sessionWithMaxConcurrents = sessions.find {session -> max(session.concurrentSessionCount)}

//Add one to the overlap to include the current session
return sessionWithMaxConcurrents.concurrentSessionCount + 1

Very easy. But as I mentioned before this is O(n^2) - not very sexy. And loading all sessions into memory - well lets just say I'm not a fan.

Turns out there is a very neat approach. It does however require Windows or Analytics functions in the database. Hey you can't get everything right?

Okay so lets set up data. Our table looks like so:

Our application records the time when the user logs in and out. BTW - I should point out that not all users may log out of your application.... so how do you record a session expiry? I'll post that in a seperate post. For now, lets move on.

The first thing that we want to do, is assign a row_number to every row that corresponds to a log_in, pretty straight forward:

And now we just union all our log_out:

But this isn't good. We want to put our logins and logouts in the order they were done in our application; this means we need to sort it by the date, no problem:

Much better...and now for the magic!

No comments:

Post a Comment