Quantum Leaps Discussion Forum

Glenn McAllister

Dec 9, 07 - 7:38 PM

Large number of timers

I have a system I'm trying to prototype that will have to support a large number of timers. Specifically, I need a single active object to manage a large number of session statecharts (typical use of the "Orthogonal Component" recipe). Each "session" object will have several timeouts associated with it. The natural approach is to create a timer that can identify the session statechart (i.e., create a new timer subtype with the identifying information) so the parent active object can pass the timeout event to the child statechart. So far so good.

The concern I have involves the sheer number of session objects to be supported. The requirements state that the system needs to support 200,000 concurrent sessions. Now don't worry about memory, etc. This app would be running on a fairly beefy Linux server and will likely fit quite comfortably. Also, sessions aren't "active" in the sense you would normally think of. These sessions are used to authenticate users of the system, hold a little bit of configuration data about them, and "do the right thing" when the sessions expire (kill the session, reauthenticate, etc.).

My concern is that if all 200,000 session statecharts have active timers, running through the list of timers during the call to QF_tick() might simply take too long. Or am I worried about nothing and should simply try it and see if anything blows up?

Miro Samek

Dec 10th, 2007 - 7:06 AM

Re: Large number of timers

Glenn,

Let me start with a general comment. Maybe by coincidence, I had recently a few questions regarding big-scale applications of QP. The concern was that QP is “embedded”, so perhaps not suitable for “big jobs”. As it turns out, the “embedded” approach of being efficient both in time and space, is actually critical for both extremes of the application spectrum -- the tiny ones and the mammoth-big ones. The big-jobs have simply astronomical numbers of components, so the efficiency per-component matters a lot. It turns out that the event-driven approach easily scales up to 1 million components and beyond, unlike other approaches (such as a thread-per-component).

Now, back to your problem. Normally I would agree that the standard way of subclassing the time event (TimeEvt) to add the session-id would be the right way to go, just as you describe in the first paragraph.

But you’re doing things on such a massive scale... With 200K session components and several time events per session we’re easily talking about 1 million of time events.

Now, I understand that memory is not a big deal. (A TimeEvt costs some 20 bytes on a 32-bit machine, which is merely 20MB of RAM for 1M of them -- “nothing” by your standard, right?)

But the problem is that in the brute force solution all framework elements must scale up. For example, the event queue of the Container active object must be also 1M entries deep. (Consider a very “unlucky” time tick, when *all* timers fire simultaneously.)

A more sensible approach would be to move processing of all these timers into the Container active object task-level. It seems to me that your “sessions” will have longer timeouts that will be mostly active (e.g., you’re talking of session expiration or re-authentication timeouts). So, the Container can arm just one periodic time event to deliver as infrequent timeouts as your “sessions” can tolerate (this would be the granularity of the timeouts for the sessions.) Upon arrival of this timeout, the Container will essentially re-implement the QF::tick() with different algorithm. Here is how this code might look like:



class Session : public QHsm {  // Session orthogonal component

    uint16_t expiration_timer;        // down-counter

    uint16_t authentication_timer;    // down-counter

    . . .



    friend class SessionContainer;

};





// somewhere in the SessionContainer state machine ...

. . .

case SESSION_TICK_SIG: {

    for (n = 0; n < NUM_SESSIONS; ++n) {  // for all sessions

        Session *s = &me->session[n]; // Sessions are preallocated in a big array



        if (s->expiration_timer != 0) { // session active ?

            --s->expiration_timer;

            if (s->expiration_timer == 0) {

                static QEvent const expEvt = { SESSION_EXPIRED_SIG, 0 };

                s->dispatch(&expEvt); // synchronously dispatch session expired evt

            }

        }



        if (s->authentication_timer != 0) {

            --s->authentication_timer;

            if (s->authentication_timer == 0) {

                static QEvent const authEvt = { SESSION_AUTHENTICATE_SIG, 0 };

                s->dispatch(&authEvt); // synchronously dispatch session authenticate evt

            }

        }



        // handle other session timers 



    }



}

. . .

In this simple example, local session timers are just the down-counters (so cost just 2 bytes for 65K counts dynamic range). The timer is inactive if its count is zero, otherwise it’s ticking. It expires when it reaches zero. (Such timers are actually used in QP-nano.) Please note that you dispatch the timeout events to Session component synchronously, so you don’t use event queues.

The method is unsophisticated, because you simply iterate through all sessions every time. (But I assume that most of them are active). The biggest savings come from down-scaling the ticking rate to the SESSION_TICK period (this is done by the TimeEvt timer inside the SessionContainer). The rate could be, say 1Hz, which is 1/100 of the original ticking rate.

Miro

Glenn McAllister

Dec 10th, 2007 - 8:05 AM

Re: Large number of timers

I agree completely about the use of an efficient system in large applications is extremely important. I don't have problems getting people to agree with that here, just about the mechanism for doing so. :-)

The problem with the event queue did occur to me but I was less concerned with that than the consequence of taking too long in QF_tick().

Using the parent container to manage the session timeouts as you've suggested seems like the simplest and most effective way to deal with the problem. Thanks for the prompt response and for such a great product.

Author	Comment
Glenn McAllister Dec 9, 07 - 7:38 PM	Large number of timers I have a system I'm trying to prototype that will have to support a large number of timers. Specifically, I need a single active object to manage a large number of session statecharts (typical use of the "Orthogonal Component" recipe). Each "session" object will have several timeouts associated with it. The natural approach is to create a timer that can identify the session statechart (i.e., create a new timer subtype with the identifying information) so the parent active object can pass the timeout event to the child statechart. So far so good. The concern I have involves the sheer number of session objects to be supported. The requirements state that the system needs to support 200,000 concurrent sessions. Now don't worry about memory, etc. This app would be running on a fairly beefy Linux server and will likely fit quite comfortably. Also, sessions aren't "active" in the sense you would normally think of. These sessions are used to authenticate users of the system, hold a little bit of configuration data about them, and "do the right thing" when the sessions expire (kill the session, reauthenticate, etc.). My concern is that if all 200,000 session statecharts have active timers, running through the list of timers during the call to QF_tick() might simply take too long. Or am I worried about nothing and should simply try it and see if anything blows up? Email: glenn@somanetworks.com
Miro Samek Dec 10th, 2007 - 7:06 AM	Re: Large number of timers Glenn, Let me start with a general comment. Maybe by coincidence, I had recently a few questions regarding big-scale applications of QP. The concern was that QP is “embedded”, so perhaps not suitable for “big jobs”. As it turns out, the “embedded” approach of being efficient both in time and space, is actually critical for both extremes of the application spectrum -- the tiny ones and the mammoth-big ones. The big-jobs have simply astronomical numbers of components, so the efficiency per-component matters a lot. It turns out that the event-driven approach easily scales up to 1 million components and beyond, unlike other approaches (such as a thread-per-component). Now, back to your problem. Normally I would agree that the standard way of subclassing the time event (TimeEvt) to add the session-id would be the right way to go, just as you describe in the first paragraph. But you’re doing things on such a massive scale... With 200K session components and several time events per session we’re easily talking about 1 million of time events. Now, I understand that memory is not a big deal. (A TimeEvt costs some 20 bytes on a 32-bit machine, which is merely 20MB of RAM for 1M of them -- “nothing” by your standard, right?) But the problem is that in the brute force solution all framework elements must scale up. For example, the event queue of the Container active object must be also 1M entries deep. (Consider a very “unlucky” time tick, when all timers fire simultaneously.) A more sensible approach would be to move processing of all these timers into the Container active object task-level. It seems to me that your “sessions” will have longer timeouts that will be mostly active (e.g., you’re talking of session expiration or re-authentication timeouts). So, the Container can arm just one periodic time event to deliver as infrequent timeouts as your “sessions” can tolerate (this would be the granularity of the timeouts for the sessions.) Upon arrival of this timeout, the Container will essentially re-implement the QF::tick() with different algorithm. Here is how this code might look like: class Session : public QHsm { // Session orthogonal component uint16_t expiration_timer; // down-counter uint16_t authentication_timer; // down-counter . . . friend class SessionContainer; }; // somewhere in the SessionContainer state machine ... . . . case SESSION_TICK_SIG: { for (n = 0; n < NUM_SESSIONS; ++n) { // for all sessions Session s = &me->session[n]; // Sessions are preallocated in a big array if (s->expiration_timer != 0) { // session active ? --s->expiration_timer; if (s->expiration_timer == 0) { static QEvent const expEvt = { SESSION_EXPIRED_SIG, 0 }; s->dispatch(&expEvt); // synchronously dispatch session expired evt } } if (s->authentication_timer != 0) { --s->authentication_timer; if (s->authentication_timer == 0) { static QEvent const authEvt = { SESSION_AUTHENTICATE_SIG, 0 }; s->dispatch(&authEvt); // synchronously dispatch session authenticate evt } } // handle other session timers } } . . . In this simple example, local session timers are just the down-counters (so cost just 2 bytes for 65K counts dynamic range). The timer is inactive if its count is zero, otherwise it’s ticking. It expires when it reaches zero. (Such timers are actually used in QP-nano.) Please note that you dispatch the timeout events to Session component synchronously, so you don’t use event queues. The method is unsophisticated, because you simply iterate through all sessions every time. (But I assume that most of them are active). The biggest savings come from down-scaling the ticking rate to the SESSION_TICK period (this is done by the TimeEvt timer inside the SessionContainer). The rate could be, say 1Hz, which is 1/100 of the original ticking rate. Miro Email:* miro@quantum-leaps.com Website: http://www.quantum-leaps.com
Glenn McAllister Dec 10th, 2007 - 8:05 AM	Re: Large number of timers I agree completely about the use of an efficient system in large applications is extremely important. I don't have problems getting people to agree with that here, just about the mechanism for doing so. :-) The problem with the event queue did occur to me but I was less concerned with that than the consequence of taking too long in QF_tick(). Using the parent container to manage the session timeouts as you've suggested seems like the simplest and most effective way to deal with the problem. Thanks for the prompt response and for such a great product. Email: glenn@somanetworks.com

	Quantum Leaps Discussion Forum Search the Forum for answers or post your questions to the Quantum Leaps community
Return to Website