Send kea-dev mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
https://lists.isc.org/mailman/listinfo/kea-dev
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of kea-dev digest..."
Today's Topics:
1. Re: On lease expiration (Stephen Morris)
2. Re: On lease expiration (about multi-thread vs multi-process)
(Francis Dupont)
3. Re: On lease expiration (Shawn Routhier)
4. Re: On lease expiration (Tomek Mrugalski)
----------------------------------------------------------------------
Message: 1
Date: Tue, 22 Jul 2014 15:37:39 +0100
From: Stephen Morris <[email protected]>
To: Tomek Mrugalski <[email protected]>, [email protected]
Subject: Re: On lease expiration
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On 08/07/14 21:36, Tomek Mrugalski wrote:
> How this could work? There are couple possible approaches: a)
> Implement house-keeping process that runs in the background. It
> will be periodically sweeping the database and will pick expired
> leases. The biggest advantage of this approach is its relative
> simplicity. Implementation is not related to any existing code, so
> the likelihood of any side effects are minimal. It seems easy to
> implement, but in fact it is quite complex, as it will need to
> implement its own configuration parser. Once we decide to go
> multi-process, it would be reasonable to have a single
> house-keeping process. These are all benefits I can think of.
> Unfortunately, there are numerous disadvantages. First, it would
> be inherently incompatible with memfile, our default backend. This
> is a big problem for me as I think that memfile will also be the
> most popular backend due to its installation simplicity. Second,
> stand alone process would call all external actions in a separate
> process, so users writing hook libraries will need to develop
> multiprocess capabilities, even if we have only one Kea server.
> Third, I have no idea how to implement failover with stand alone
> house keeper. It will have to notify somehow the Kea server that a
> lease expired and its partner must be notified (or other failover
> actions must take place). So we're talking about inter-process
> notification protocol here on top of failover. Finally, this is a
> new process that needs to be maintained (new makefiles, new man
> page, new binaries to install, new documentation etc.). The bottom
> line for me is that if we decide to do stand-alone process, we're
> getting short term benefits, but we'll pay for it with much larger
> development and maintenance costs in the long term.
Taking the points one by one:
1. "in fact it is quite complex, as it will need to implement its own
configuration parser."
I don't know exactly how the standalone configuration parser has been
implemented, but if adding configuration items is a big hurdle, we
need to schedule some time to re-engineer it: it will provide a
significant impediment to extending Kea in the future.
Ideally we should be able to add any new process to Kea with minimum
effort, so this means that adding items to the configuration file (and
parsing it) should be as easy as possible.
2. "First, it would be inherently incompatible with memfile, our
default backend."
This is probably the main drawback. Unless memfile is significantly
re-engineered, it is incompatible with a multi-process Kea. (This is
discussed below.)
3. "Second, stand alone process would call all external actions in a
separate process, so users writing hook libraries will need to develop
multiprocess capabilities, even if we have only one Kea server."
That is not really a major problem unless users want some application
that needs to link lease expirations with other lease events and needs
to keep the details in memory while it runs. Even then, the difficulty
of implementation depends on what needs to be done.
4. "Third, I have no idea how to implement failover with stand alone
house keeper."
Consider it a research project :-)
5. "Finally, this is a new process that needs to be maintained (new
makefiles, new man page, new binaries to install, new documentation
etc.)."
Compared with writing the code, this overhead is small. We should not
let it deter us from any particular solution.
> b) implement house-keeping as part of the existing process. There
> would be a configuration parameter that would tell the server to
> trigger the routine every X seconds. The server would call select()
> for at most X seconds, run house-keeping and then call select()
> again. This approach seems very flexible. If you really need a
> notification the very second when the lease expires, set X to 1. If
> you're experiencing an event where extra performance is needed, set
> it to some large value, so expiration will be checked upon the next
> day. Of course, there are tradeoffs. The longer value set means
> that, although the procedure will not happen that often, each
> house-keeping will take longer as it will have more leases to
> process. The benefit of this approach is that logging, hooks, ddns
> happen in the same process, so no multi-process hassles for us and
> for hook lib developers. Also, failover does not become more
> complicated. It is easy to implement as the whole design of
> existing code is ready for this (calculating timeout + calling
> select() with that timeout).
My only concern with this is that this means that expiration is
competing with the allocation of leases, something that will limit
performance. Also, if all leases that have expired in the interval are
processed together, there is a risk of "bursty" performance - the
server refusing to handle new leases for a period because it is
processing expirations.
> c) that's really b) + extra capability of being able to disable
> house-keeping, at least during normal operation. House-keeping
> would be called during startup and shutdown. So if you really need
> the absolute max performance and intermediate pauses needed for
> house-keeping are a problem for you, use this. You will get the
> lease expiration notification after some time ("Least A expired Y
> minutes ago"), but that's ok if max performance is your goal.
Not quite.
If an expired lease is reused, you would need to do the lease
expiration processing prior to reassigning the lease. (An alternative
would be to log the expired lease to a journal file and have the file
included in the lease expiration housekeeping.)
On reflection, this consideration impacts all solutions to the lease
expiration problem. If we were to go for an external process to do
the house keeping, the DHCP server process could not reuse expired
leases - it would have to wait until they were cleaned up by the
housekeeper.
> d) That's b) + an optimization. When assigning or updating a lease,
> we can keep the timestamp to the shortest expiration event and
> dynamically set X to that value. So if there are no leases, we'll
> select() for MAX_UINT. If there are 1000s of leases, we'll select()
> until the shortest (or oldest) one expires. This is how expiration
> is implemented in Dibbler. Seems to be working fine.
Does Dibbler keep the leases ordered by expiration time? For Kea, we'd
have to add an index on that field to the lease database to allow
selection of the lease with the next expiration time.
> Solutions b) and c) have a small disadvantage when we decide to
> enable Kea to run multiple instances. That will mean that if you
> have X processes, the house-keeping will be run X times. In
> principle that's not optimal, but it isn't that bad. Although there
> will be multiple checks run, but on average each routine will have
> to only process X times less leases. Also, this can be easily
> solved by having a designated process (e.g. only the first instance
> runs house-keeping, additional instances have house-keeping
> disabled).
See below.
> e) Over time, we will also need to implement a new command:
> lease-expire or db-cleanup. It would add extra capability for
> admins who tweaked something in the DB and want Kea to process the
> changes. Also, some admins would possibly want to use their
> external scripts to do lease expirations, e.g. during low traffic
> at 3am.
>
> Actual house-keeping routine implementation is lease database
> specific. For SQL-based backends, we'll probably implement a query
> that returns expired lease. For memfile, we'll either add an index
> or will have to traverse the leases. It would be good if we could
> do that using bisection. I haven't looked at what's available in
> multi-index containers.
>
> Thoughts? Comments?
Ultimately, the best method for lease expiration processing depends
whether we want to expand Kea beyond its single-thread implementation
to embrace parallel processing; and if we do, what model we use.
The BIND 10 approach to parallel processing was to go for a
multi-process approach. One of the reasons for this was that should
there be an error (e.g. BIND crashing on a malformed name), it was
likely that only one of the processes would fall over, not the entire
package. As a result, BIND 10 would be more resilient to such errors.
The focus of Kea effort was to get a working DHCP server, so the
discussions about parallel processing never got into any detail; when it
was discussed, it was always assumed that the BIND 10 multi-process
model would be preferred over a multi-threaded one. However, that was
when the only lease database under discussion was one based on an
external database. The addition of the memfile database makes this
approach awkward: to share the data between processes in shared memory
requires that the pointers in the structure be relative pointers, not
absolute pointers. This can be done, but will take a lot of effort and
is complex - the BIND 10 DNS group had the same problem and spent a lot
of time on it.
As Kea is now a standalone package, we have two choices for parallelism:
1. Make Kea multi-threaded. This will work for all databases, including
memfile.
2. Make Kea multi-process, disabling this capability for the memfile
database.
If we do (1), then Tomasz's suggestion of handling lease expiration in
the same process as the lease allocation is natural: it is just one more
thread.
If we go for (2), I argue that the case against having the lease
expiration in a separate process disappears. If we have multiple
processes, either the housekeeping function runs in all of them, or one
process is marked as special and it runs in that. The former seems
unattractive as the code is repeatedly executed: runs of the code in
different processes could clash (which would have to be handled).
Alternatively if one instance ran immediately after another, the
second might have no work to do. If we go for the latter option - a
single process - there seems no advantage having the housekeeping code
in the same process as the DHCP server - it might as well be a separate
process.
Coming down to the problem in hand - what do we do for Kea post 0.9 -
the main task is to write the lease expiration code. We must make this
as modular as possible: that allows for flexibility. We could - for
example - put the code in both a housekeeper process and in the main
DHCP server, using the former with an SQL database (so obtaining
paralellism) and the latter with memfile.
Stephen
------------------------------
Message: 2
Date: Tue, 22 Jul 2014 14:59:01 +0000
From: Francis Dupont <[email protected]>
To: Stephen Morris <[email protected]>
Cc: [email protected]
Subject: Re: On lease expiration (about multi-thread vs multi-process)
Message-ID: <[email protected]>
Multi-threading for scaling is a dead end. To summary from
a single-thread to a multiple-thread application you begin
to loose half of the speed, so to get back the performance
you need two threads. With 3 you go at the same speed than 2
(aka the 3 bug :-). With 4 you have better speed but with more
than 4 you win no more and usually you become slower.
This is not a rule without exceptions (some particular cases show
overspeedup, i.e., an improvement in performances higher than
the number of threads) but it is true enough to affect most
of the multi-threaded applications, including BTW bind9.
So my advince is to try multi-process which is on the paper scalable
without bounds.
BTW if you rewrite/deploy bind9 today, you won't try to improve the
performance of one server, but anycast it into multiple servers in the
cloud.
Regards
Francis Dupont <[email protected]>
------------------------------
Message: 3
Date: Tue, 22 Jul 2014 10:26:45 -0700
From: Shawn Routhier <[email protected]>
To: Stephen Morris <[email protected]>
Cc: [email protected]
Subject: Re: On lease expiration
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Jul 22, 2014, at 7:37 AM, Stephen Morris wrote:
> <snip>
>
>> d) That's b) + an optimization. When assigning or updating a lease,
>> we can keep the timestamp to the shortest expiration event and
>> dynamically set X to that value. So if there are no leases, we'll
>> select() for MAX_UINT. If there are 1000s of leases, we'll select()
>> until the shortest (or oldest) one expires. This is how expiration
>> is implemented in Dibbler. Seems to be working fine.
>
> Does Dibbler keep the leases ordered by expiration time? For Kea, we'd
> have to add an index on that field to the lease database to allow
> selection of the lease with the next expiration time.
Just for completeness I believe that in ISC DHCP we do this two different ways
in v4 we use an ordered list
in v6 we use a heap
In v6 we also have some other features that cause the expiration
and cleanup of a lease to be delayed.
------------------------------
Message: 4
Date: Tue, 22 Jul 2014 13:58:16 -0400
From: Tomek Mrugalski <[email protected]>
To: Stephen Morris <[email protected]>, [email protected]
Subject: Re: On lease expiration
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On 22/07/14 10:37, Stephen Morris wrote:
> On 08/07/14 21:36, Tomek Mrugalski wrote:
>
> Taking the points one by one:
>
> 1. "in fact it is quite complex, as it will need to implement its own
> configuration parser."
>
> I don't know exactly how the standalone configuration parser has been
> implemented, but if adding configuration items is a big hurdle, we
> need to schedule some time to re-engineer it: it will provide a
> significant impediment to extending Kea in the future.
You won't get any objections from me on this one. The current parser is
a nefarious contraption that should be eradicated. It was just something
I was told to implement "just like auth" and didn't have enough
assertiveness to point out radical differences between configuration
data in auth and dhcp servers.
> 2. "First, it would be inherently incompatible with memfile, our
> default backend."
>
> This is probably the main drawback. Unless memfile is significantly
> re-engineered, it is incompatible with a multi-process Kea. (This is
> discussed below.)
No, I think memfile should be left as is. What we should do instead is
to provide a way for DB backend to report its capabilities. For now, it
would be "multi-process capable", but in the short term there may be
other capabilities (e.g. "context-capable").
> 3. "Second, stand alone process would call all external actions in a
> separate process, so users writing hook libraries will need to develop
> multiprocess capabilities, even if we have only one Kea server."
>
> That is not really a major problem unless users want some application
> that needs to link lease expirations with other lease events and needs
> to keep the details in memory while it runs. Even then, the difficulty
> of implementation depends on what needs to be done.
Right now implementing hooks library is a relatively straightforward
process. When we tell developers than they need to have
multi-threading/multi-process aware hooks, we'll raising the bar
significantly. This is some I'd like to avoid.
> 4. "Third, I have no idea how to implement failover with stand alone
> house keeper."
>
> Consider it a research project :-)
Is it a one with a dedicated time budget and reasonable financing? Then
I'm all in :-)
> 5. "Finally, this is a new process that needs to be maintained (new
> makefiles, new man page, new binaries to install, new documentation
> etc.)."
>
> Compared with writing the code, this overhead is small. We should not
> let it deter us from any particular solution.
>> b) implement house-keeping as part of the existing process. There
>> would be a configuration parameter that would tell the server to
>> trigger the routine every X seconds. The server would call select()
>> for at most X seconds, run house-keeping and then call select()
>> again. This approach seems very flexible. If you really need a
>> notification the very second when the lease expires, set X to 1. If
>> you're experiencing an event where extra performance is needed, set
>> it to some large value, so expiration will be checked upon the next
>> day. Of course, there are tradeoffs. The longer value set means
>> that, although the procedure will not happen that often, each
>> house-keeping will take longer as it will have more leases to
>> process. The benefit of this approach is that logging, hooks, ddns
>> happen in the same process, so no multi-process hassles for us and
>> for hook lib developers. Also, failover does not become more
>> complicated. It is easy to implement as the whole design of
>> existing code is ready for this (calculating timeout + calling
>> select() with that timeout).
>
> My only concern with this is that this means that expiration is
> competing with the allocation of leases, something that will limit
> performance. Also, if all leases that have expired in the interval are
> processed together, there is a risk of "bursty" performance - the
> server refusing to handle new leases for a period because it is
> processing expirations.
>
>
>> c) that's really b) + extra capability of being able to disable
>> house-keeping, at least during normal operation. House-keeping
>> would be called during startup and shutdown. So if you really need
>> the absolute max performance and intermediate pauses needed for
>> house-keeping are a problem for you, use this. You will get the
>> lease expiration notification after some time ("Least A expired Y
>> minutes ago"), but that's ok if max performance is your goal.
>
> Not quite.
>
> If an expired lease is reused, you would need to do the lease
> expiration processing prior to reassigning the lease. (An alternative
> would be to log the expired lease to a journal file and have the file
> included in the lease expiration housekeeping.)
This is something we do already. When the allocation picks a lease
candidate and discovers that the lease is expired, it is reused.
That is working fine so far. If it isn't broken, don't fix it.
> On reflection, this consideration impacts all solutions to the lease
> expiration problem. If we were to go for an external process to do
> the house keeping, the DHCP server process could not reuse expired
> leases - it would have to wait until they were cleaned up by the
> housekeeper.
So we're talking about race conditions here. I can imagine displeased
users who discover that the server claims to be out of leases, while
there are expired leases available.
>> d) That's b) + an optimization. When assigning or updating a lease,
>> we can keep the timestamp to the shortest expiration event and
>> dynamically set X to that value. So if there are no leases, we'll
>> select() for MAX_UINT. If there are 1000s of leases, we'll select()
>> until the shortest (or oldest) one expires. This is how expiration
>> is implemented in Dibbler. Seems to be working fine.
>
> Does Dibbler keep the leases ordered by expiration time? For Kea, we'd
> have to add an index on that field to the lease database to allow
> selection of the lease with the next expiration time.
No, Dibbler doesn't. A new index would be useful if we wanted to pick
the the lease that will expire first. We'll need to have a call similar
to getAllExpiredLeases(). It would be helpful if we could get all leases
in the expiration time order. The could would process leases one by one
until it hits a lease that is not expired yet.
>> e) Over time, we will also need to implement a new command:
>> lease-expire or db-cleanup. It would add extra capability for
>> admins who tweaked something in the DB and want Kea to process the
>> changes. Also, some admins would possibly want to use their
>> external scripts to do lease expirations, e.g. during low traffic
>> at 3am.
>>
>> Actual house-keeping routine implementation is lease database
>> specific. For SQL-based backends, we'll probably implement a query
>> that returns expired lease. For memfile, we'll either add an index
>> or will have to traverse the leases. It would be good if we could
>> do that using bisection. I haven't looked at what's available in
>> multi-index containers.
>>
>> Thoughts? Comments?
>
> Ultimately, the best method for lease expiration processing depends
> whether we want to expand Kea beyond its single-thread implementation
> to embrace parallel processing; and if we do, what model we use.
I my opinion there's no such thing as a the "best" method. It will
depend on the deployment scale. The "best" method will likely to be
different if you're running your home office with 5 computers and when
you run multi-million users network. That's why I think that the
house-keeping routine (I call it routine and not process or function to
not skew the perception in any way) independent, so it could be called
both from the main process and also from a dedicated house-keeping process.
> As Kea is now a standalone package, we have two choices for parallelism:
>
> 1. Make Kea multi-threaded. This will work for all databases, including
> memfile.
>
> 2. Make Kea multi-process, disabling this capability for the memfile
> database.
> If we do (1), then Tomasz's suggestion of handling lease expiration in
> the same process as the lease allocation is natural: it is just one more
> thread.
>
> If we go for (2), I argue that the case against having the lease
> expiration in a separate process disappears. If we have multiple
I don't think the choice between (1) and (2) is a management decision.
The best action would be to implement prototypes and measure their
performance. It will be more work in the short term, but will let us
pick the right solution that will stick with us for many years.
> Coming down to the problem in hand - what do we do for Kea post 0.9 -
> the main task is to write the lease expiration code. We must make this
> as modular as possible: that allows for flexibility. We could - for
> example - put the code in both a housekeeper process and in the main
> DHCP server, using the former with an SQL database (so obtaining
> paralellism) and the latter with memfile.
That's what I was planning.
Tomek
------------------------------
_______________________________________________
kea-dev mailing list
[email protected]
https://lists.isc.org/mailman/listinfo/kea-dev
End of kea-dev Digest, Vol 4, Issue 3
*************************************
