Re: [Nagios-devel] Skiplists
Posted: Mon Oct 15, 2007 1:55 pm
John P. Rouillard wrote:
> In message ,
> Andreas Ericsson writes:
>
>> John P. Rouillard wrote:
>>> In message ,
>>> Andreas Ericsson writes:
>>>
>>>> Andreas Ericsson wrote:
>>>>> Ethan Galstad wrote:
>>>>>> 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 even
>> t
>>>>>> 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
>>>> 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.
>>> Hmm, maybe I am missing something, but if I have an element with a
>>> known key, I see how a hash table pointing into a conventional linked
>>> list will speed up access. But doesn't case 2 take the form:
>>>
>>> insert node X that should run at time t into the linked list
>>>
>>> mean a sequential scan of the linked list? How do you know what time
>>> to hash to find the node before time t?
>> It's a sequential scan of a small part of the linked list, just like
>> any non-perfect hash. Since perfect hashes aren't available for this,
>> we'll have to use a non-perfect one.
>>> E.G. I want node X inserted at 10:24:33, how do I know if the prior
>>> node is at 10:24:32, or 10:14:32?
>>>
>> With a 60 buckets in the hash-array, you wouldn't be able to tell the
>> difference without comparing the timestamp of the other scheduled items
>> in the list. With more than 600 buckets, they'd end up in separate lists.
>>
>> However, we won't ever have to walk through *all* the lists, we just have
>> to find the right "end" of things.
>>
>> Assume for a moment that the highest normal_check_interval you have for
>> your services is 15 minutes. 1024 buckets will hold your 15 minutes, with
>> 2.067 minutes to spare. Now let's say you want to schedule a service-check
>> x seconds into the future.
>>
>> slot = time(NULL) + x;
>> if (x > num_buckets) {
>> walk_from_tail(event_array[slot]);
>> }
>> else {
>> walk_from_head(event_array[slot]);
>> }
>
> Ah ok your hash function is the timestamp. So all items scheduled for
> time X are in the same bucket if the number of buckets exceeds the
> number of seconds from now till the maximum future time you have in
> the list.
>
> This works because the hash function preserves the order of the keys
> rather than randonly distributing them like a normal has table. I.E.
>
> key1 = timestamp1
> key2 = timestamp2
>
> and
>
> hash(key1) > hash(key2) if key1 > key2
>
> so walking the buckets is the same as skipping across the linked list
> in order.
>
>> Since we're not likely to schedule checks several hours away,
>
> I have a few checks that run every couple of hours, so I would just
> have a larger hash table, or would you need to have a seperate bin
> that gets the entries that aren't schedulable in the normal hash
> table, and it filters them in on a regular basis.
>
1 out of 3 scenarios, basically.
1. You'd have a normal-sized hash-table and take the performance-penalty
of sometimes having to walk those checks to reach the case where you
want to schedule a
...[email truncated]...
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]
> In message ,
> Andreas Ericsson writes:
>
>> John P. Rouillard wrote:
>>> In message ,
>>> Andreas Ericsson writes:
>>>
>>>> Andreas Ericsson wrote:
>>>>> Ethan Galstad wrote:
>>>>>> 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 even
>> t
>>>>>> 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
>>>> 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.
>>> Hmm, maybe I am missing something, but if I have an element with a
>>> known key, I see how a hash table pointing into a conventional linked
>>> list will speed up access. But doesn't case 2 take the form:
>>>
>>> insert node X that should run at time t into the linked list
>>>
>>> mean a sequential scan of the linked list? How do you know what time
>>> to hash to find the node before time t?
>> It's a sequential scan of a small part of the linked list, just like
>> any non-perfect hash. Since perfect hashes aren't available for this,
>> we'll have to use a non-perfect one.
>>> E.G. I want node X inserted at 10:24:33, how do I know if the prior
>>> node is at 10:24:32, or 10:14:32?
>>>
>> With a 60 buckets in the hash-array, you wouldn't be able to tell the
>> difference without comparing the timestamp of the other scheduled items
>> in the list. With more than 600 buckets, they'd end up in separate lists.
>>
>> However, we won't ever have to walk through *all* the lists, we just have
>> to find the right "end" of things.
>>
>> Assume for a moment that the highest normal_check_interval you have for
>> your services is 15 minutes. 1024 buckets will hold your 15 minutes, with
>> 2.067 minutes to spare. Now let's say you want to schedule a service-check
>> x seconds into the future.
>>
>> slot = time(NULL) + x;
>> if (x > num_buckets) {
>> walk_from_tail(event_array[slot]);
>> }
>> else {
>> walk_from_head(event_array[slot]);
>> }
>
> Ah ok your hash function is the timestamp. So all items scheduled for
> time X are in the same bucket if the number of buckets exceeds the
> number of seconds from now till the maximum future time you have in
> the list.
>
> This works because the hash function preserves the order of the keys
> rather than randonly distributing them like a normal has table. I.E.
>
> key1 = timestamp1
> key2 = timestamp2
>
> and
>
> hash(key1) > hash(key2) if key1 > key2
>
> so walking the buckets is the same as skipping across the linked list
> in order.
>
>> Since we're not likely to schedule checks several hours away,
>
> I have a few checks that run every couple of hours, so I would just
> have a larger hash table, or would you need to have a seperate bin
> that gets the entries that aren't schedulable in the normal hash
> table, and it filters them in on a regular basis.
>
1 out of 3 scenarios, basically.
1. You'd have a normal-sized hash-table and take the performance-penalty
of sometimes having to walk those checks to reach the case where you
want to schedule a
...[email truncated]...
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]