Re: scalable event scheduling

On 01/30/2013 09:30 AM, Rainer Weikusat wrote:
> Alex Rousskov <rousskov_at_measurement-factory.com> writes:
>> On 01/28/2013 03:29 PM, Rainer Weikusat wrote:
>>> so easy that even using the STL implementation wouldn't be worth the
>>> effort
>>
>> Can you clarify why we should not just use one of the STL queues
>> instead?
>
> I agree with your opinion that "the STL doesn't contain an 'obviously
> good' choice for a priority queue implementation in the given
> context".

I am glad we agree on this, but I think that STL must be seriously
considered before we add something custom. The overhead of making that
decision was one of the reasons why I considered optimizing event queue
a stand-alone, non-trivial project.

I see no reason to optimize Squid event queue now, but if the consensus
is that it should be optimized, I think we should evaluate usability of
standard STL queues as the first step.

>>> the event scheduler will store a value at the
>>> pointed-to location which can be passed to eventDelete to cancel a pending
>>> event 'safely' in logarithmic time, meaning, even if the event was
>>> possibly already put onto the async queue.

> The purpose of the eventDelete routine is not to cancel a call the
> event scheduler already put onto the async call queue but to prevent
> such a call from being put onto this queue if this is still
> possible. And I didn't intend change that.

Noted, but I am still missing something: Why add a new event tag API if
the existing eventDelete() code can already cancel events outside the
async queue?

[ If the new tag API is needed, and if the cancellation API is
documented, please clarify that only events currently outside the async
queue can be canceled.]

I do not think such "occasionally working" cancellation is a good idea
though. The caller code would have to take different actions depending
on whether the event was actually canceled or not. And, in some cases,
the correct "not canceled" action would be difficult to implement as the
ConnOpener use case shows.

I also think that the need for explicit destruction of the event "tag"
by the caller is a serious downside because it increases the risk of
memory leaks.

FWIW, here is how I think the event cancellation should be supported
instead:

1. Another form of eventAdd() should be added to accept caller's async
call. New code, especially async jobs, should use that form (jobs will
and avoid call wrappers that way). Old code that wants to cancel events
should use this new form as well.

2. The caller may store and cancel that async call at any time prior to
its firing, just like any other async callback.

3. When the event is ready for the async queue, the event scheduler
should put the same async call from #1 into the async queue.

The current event scheduler already creates an async call object for
nearly all events anyway, so this does not add CPU overhead. The only
overhead is that we will consume the same [small] amount of RAM sooner.
In exchange, we get guaranteed call cancellation, job protection, and
improved debugging.

Alex.
P.S. I have also considered the following alternative, but rejected it
because to use event cancellation new caller code would have to be
written anyway, so we do not need to preserve the current eventAdd()
parameters for that new code:

1. eventAdd() should create, store, and return an async call.

2. The caller may store and cancel the returned async call at any time
prior to its firing, just like any other async callback.

3. When the event is ready for the async queue, the event scheduler
should put the stored async call into the async queue.
Received on Wed Jan 30 2013 - 17:29:01 MST