On lease expiration

[Stephen Morris]

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