Logging API revamp

[Andreas Ericsson]

Andreas Ericsson wrote:
> Ethan Galstad wrote:
>> Andreas Ericsson wrote:
>>> So, I started looking into revamping the event queue logic, but ended up
>>> with a migraine from the cumbersome way logging is done, so I decided to
>>> try doing something about it, and the attached 3-patch series is the
>>> result from it.
>>>
>>> It compiles alright, both for nagios and the cgi's. I haven't done much
>>> in the way of checking past that though, so testing would be welcome.
>>>
>>> Given that the patches don't change much in the way of logic, they
>>> shouldn't really affect anything in significant way.
>>>
>> [snip]
>>
>> Thanks for the patches - they are excellent ideas.  I'll get them 
>> implemented when I get back to the US later this week.
>>
> 
> Anytime. I guess the conference spurred some Nagios-hackativity into
> me ;-)
> 
>> For the event queue, I was thinking that a skip list structure might be 
>> best for efficiency (http://en.wikipedia.org/wiki/Skip_list).  The event 
>> queue is used in primarily two situations:
>>
>> 1. Popping events from the head of the list to be executed
>> 2. Inserting events into the list (mid- or endpoint).
>>
>> #1 is very efficient with a linked list, but performance with #2 can be 
>> quite bad in large lists.  Since a check event usually appears for each 
>> host/service that is defined, this can lead to bad performance - O(n^2) 
>> I believe - with large installations.  A skip list would bring the 
>> performance closer to O(log n).
>>
>> Anyone have comments/experiences they care to share about the 
>> performance of skip lists and/or better alternatives?
>>
> 
> A skiplist would probably do wonders. I've been experimenting with one
> now, actually using the timestamp for when next to execute <action>

Scratch that. I only glossed the skiplist page you linked, and
misunderstood completely. I've been experimenting with a hash, except
the time used for input is the key. Implementation is trivial and
performance improvement should be fairly close to or better than a
skip-list.

In particular, I'm worried about this snippet:

---%<---%<---%<---
Insertions and deletions are implemented much like the corresponding
linked-list operations, except that "tall" elements must be inserted
into or deleted from more than one linked list.
---%<---%<---%<---

I'm sure it'd be good if one gets it completely right, but it sounds
non-trivial, and with a large object base (100k list-nodes or more),
I'm guessing that "inserted into or delete from more than one
linked list" will eat up the performance gains, unless one sacrifices
lots of memory to keep a very large number of "buckets", although I
fail to see how that would help, since one would then have to walk
a larger number of lists in order to find the right one.

Hmm... I'll have to read that article top to bottom (and when it's
not 2AM), it seems.

-- 
Andreas Ericsson                   andreas.ericsson at op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems?  Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/