wiki:LeaseExpirationDesign

Design for Lease Expiration in Kea 1.0

Scope

This is a design document for the Lease Expiration in Kea 1.0. It fulfills the requirements listed in the Requirements for Lease Expiration in Kea 1.0. Kea versions beyond 1.0 are likely to introduce optimizations to the lease expiration mechanism, but these optimizations are out of scope for this document. Nevertheless, since this is the first implementation of the lease expiration, this document is meant to introduce the extensible code structures, so the future optimizations don't require re-structuring the code.

Terminology

In addition to the terminology introduced in the Requirements for Lease Expiration in Kea 1.0, the following terminology is used throughout this document:

  • Most expired lease: a lease which has expired earlier than any other lease from the particular group of leases. Note that the leases reclamation is the periodic process, thus it doesn't handle the event of a lease expiration right after it occurs. Some leases expire earlier than other and the server must order leases from "most expired" to "least expired", and handle the former in a first place.
  • Least expired lease: a lease which has expired later than any other lease from the particular group of leases.

Design Goals

The following are the design goals which had been originally included in the Requirements, but were later considered them unmeasurable and untestable. They are still valid design goals, though.

Performance

  • P1. SHOULD minimize the impact on the server's responsiveness caused by bulk processing of the expired leases
  • P2. SHOULD minimize the number of calls/queries to the lease database

Implementation

  • I1. SHOULD be agnostic to the lease database backend used
  • I2. MUST use common code base for DHCPv4 and DHCPv6 servers, where possible

Concurrency

Current Kea implementation is single-threaded. Leases reclamation is somewhat independent from the DHCP server operation, involving processing of the incoming DHCP messages. Therefore, it's been considered and discussed that leases reclamation could potentially be performed in a dedicated thread. However, there is the number of areas in which this thread would have to interact with the main thread. One of the areas is the lease allocation, where both threads may access the lease database concurrently. Neither lease allocation nor reclamation is atomic. Lease allocation or renewal often involves multiple queries to the database to check if the lease is available, reusable, renewable etc. The results of these queries are later used by Kea to make allocation decisions. The other areas where concurrency may cause conflicts between the threads are: access to D2 client, Statistics Manager, Logger etc.

Given the potential complexity of the multi-threaded solution for the lease expiration, neither Requirements nor this document puts requirements on the lease expiration implementation for Kea 1.0 to support multi-threaded solution. However, the lease expiration implementation should not preclude or make it difficult to implement the multi-threaded solution in the future. Ideally, the lease reclamation routine, running all the operations performed for a single cycle, should be structured in the way that allows for running it in a separate thread, i.e. lease expiration specific tasks should not be stitched in the message processing code.

The decision about porting the leases reclamation mechanism into the multi-threaded model will be made based on the results from the experiments, involving the checks for the possible performance gain. Even if the decision is made to migrate to the multi-threaded model, this should not preclude falling back to the single-threaded model when indicated by the server configuration or when the particular environment doesn't support concurrency well, e.g. on poor VM with a single CPU. The implementation should also account for such flexibility.

Updates to Lease Database Backends

Kea supports switchable lease database backends, which are responsible for adding, updating and retrieving leases from persistent storages of different kind. Each backend exposes the API derived from the LeaseMgr interface. This interface was designed to operate on the leases belonging to a single DHCP client. It facilitates adding, updating and deleting a single lease for a client as well as retrieval of all leases belonging to the client. As it stands, the LeaseMgr operates usually on a single lease at the time, because most of the clients would acquire a single lease.

In case of processing the expired leases, the bulks of leases must be retrieved from the database periodically, and each of them must be reclaimed individually. As previous performance measurements demonstrate, issuing queries to the lease database is one of the most critical factors influencing the server's performance. Hence, retrieving the data from the lease database should ideally result in a single query (not multiple) to obtain all expired leases to be processed in the particular cycle. This is especially important for the SQL lease databases (currently: MySQL and PostgreSQL) where inter-process communication is involved for each SQL query issued.

In order to improve efficiency of the database queries the appropriate indexing (by the expiration time) must be introduced.

The LeaseMgr API must be extended with new abstract methods to retrieve the expired leases. All existing and future backends must implement these methods.

Lease 'state' Field

One of the functions typically implemented in the DHCP servers is the lease affinity. It provides means for the server to allocate the same lease to the returning client after client's lease has expired as a result of client's inactivity. For example: if I shut down my computer for a longer period of time my current DHCP lease will expire. When I turn it on again, the client may either request the lease it had before (if it remembers it) or it may perform the 4-way exchange. In both cases, the server supporting lease affinity would determine what lease the client used previously and try to allocate the same lease. Note that lease affinity doesn't guarantee that the same lease will be allocated for the client each time. Another client may be allocated this lease if it asks for it. The lease affinity should rather be perceived as maintaining associations between the clients and their leases which MAY be used by the server as a hint to make allocation decisions.

Note: The address affinity term is frequently used to name the feature described above. However it is not precise, because this mechanism can well be implemented for IPv6 prefixes too. Admittedly, the re-allocation of the same prefix may not be desired if the returning client is requesting a larger prefix that it had previously. In such case, the new (larger) prefix should be allocated if possible.

A server supporting lease affinity maintains the previous lease of the client for a configurable period of time after the lease expires. When this time elapses the lease is removed from the lease database and thus its association with the client is removed. However, between time when the lease's valid lifetime expires and when it is removed, the lease remains expired and it must be acted upon. This mostly includes DNS update and hooks execution for each expired lease. This is performed through the lease reclamation routine. To avoid repeated reclamation of the same lease the reclaimed lease must be marked as such. This need is a major motivation for introducing a new "state" field into the lease database, which would hold various states of leases. In Kea 1.0.0 release, this field will hold an enumeration encoding the following lease states:

  • default (0) - default state of the lease, each lease is created in this state initially,
  • declined (1) - lease has been declined by the client,
  • expired-reclaimed (2) - expired lease has been reclaimed by the server and it is now held in the lease database to facilitate lease affinity.

Note that there is no "expired" state enumeration to represent a lease which has been expired but not reclaimed yet. Expired leases are determined by comparing values in the "expire" column of the lease database with the current time.

New Methods in LeaseMgr

The two new methods are required for gathering expired leases for the DHCPv4 and DHCPv6 server: getExpiredLeases4 and getExpiredLeases6. These abstract methods will be declared in the LeaseMgr and all database backends must implement them. Since the algorithm is likely to be the same for both methods, the specific backend implementations should call a common private function to obtain expired leases of the appropriate type from the lease database.

The new functions will have the following declarations:

virtual void getExpiredLeases4(Lease4Collection& expired_leases, const size_t max_leases) const = 0;

and

virtual void getExpiredLeases6(Lease6Collection& expired_leases, const size_t max_leases) const = 0;

The "max_leases" parameter specifies the maximum number of leases to be retrieved. Restricting this value is useful in the single threaded environment where the server must interrupt processing new DHCP messages for a period of time when the lease reclamation is performed. The less leases are reclaimed in a single cycle, the shorter interruption will be for the server. The special value of 0 indicates "no limit", i.e. all expired leases are retrieved.

What should the backend return for various values of "max_leases" is presented in the table below.

max_leasesleases returned
0All expired leases from all subnets.
10Up to 10 most expired leases from all subnets, ordered from the most expired to the least expired one.

The returned leases must be sorted from the most expired, to the least expired lease. This facilitates reclaiming the leases in the order of their expiration.

The implementation of the lease affinity requires two additional functions to remove leases in the "expired-reclaimed" state after a configurable time since the lease has expired. The respective functions for the DHCPv4 and DHCPv6 case will have the following signatures:

virtual void deleteExpiredReclaimedLeases4(const uint32_t secs) = 0;

and

virtual void deleteExpiredReclaimedLeases6(const uint32_t secs) = 0;

The "secs" parameter specifies the minimum number of seconds since the lease expiration. Leases which have expired less than "secs" ago will not be deleted from the database.

Changes to the Memfile Backend

This section describes in detail how the new functions should be implemented in the Memfile_LeaseMgr.

The new indexes must be added to the declarations of both Lease6Storage and Lease4Storage, to search for the expired and not reclaimed leases. These are the composite indexes comprising the 32-bit "state" field and the lease expiration time, calculated as the sum of the client last transmission time (cltt) and the valid lifetime. The indexed vaues are ordered by the "state" value , then by the sum of the expiration time from the lowest to the highest value.

The following is the declaration of the index for the Lease6Storage class (see src/lib/dhcpsrv/memfile_lease_storage.h):

boost::multi_index::ordered_non_unique<
    boost::multi_index::composite_key<
        Lease6,
        boost::multi_index::const_mem_fun<Lease, bool, &Lease6::stateExpiredReclaimed>,
        boost::multi_index::const_mem_fun<Lease, int64_t,
                                          &Lease::getExpirationTime>
        >
    >
>

The two new methods must be added to the Lease structure. The Lease::getExpirationTimewill return the lease expiration time:

int64_t Lease::getExpirationTime() const {
    return (cltt_ + valid_lft_);
}

The stateExpiredReclaimed function will return the boolean value indicating if the lease has already been reclaimed:

bool Lease::stateExpireReclaimed() const {
    return (state_ == STATE_EXPIRED_RECLAIMED);
}

where "STATE_EXPIRED_RECLAIMED" is a non default state, which is only set on the lease when it gets processed by the lease reclamation routine.

Similar index (with the Lease4, rather than Lease6 type used for the composite index) must be added to the Lease4Storage container definition.

The following is the example implementation of the Memfile_LeaseMgr::getExpiredLeases6, which uses indexes created above:

void
Memfile_LeaseMgr::getExpiredLeases6(Lease6Collection& expired_leases,
                                    const size_t max_leases) const {
    typedef Lease6Storage::nth_index<2>::type SearchIndex2;

    const SearchIndex2& idx = storage6_.get<2>();
    SearchIndex2::iterator ub = idx.upper_bound(boost::make_tuple(false,
                                                                  time(NULL)));
    for (SearchIndex2::const_iterator lease = idx.begin();
         (lease != ub) && (std::distance(idx.begin(), lease) < max_leases);
         ++lease) {
        expired_leases.push_back(Lease6Ptr(new Lease6(**lease)));
    }
}

The implementation of the Memfile_LeaseMgr::getExpiredLeases4 will look almost identical and thus it is not presented here.

Changes to the MySQL Backend

The MySQL bakckend must be extended to implement new abstract functions declared in the LeaseMgr (see New Methods in LeaseMgr for details). For that matter, the new composite index must be added comprising the "state" and "expire" field.

Also, the MySQL schema must be extended to include the new "state" 32-bit bitfield.

The schema version will be promoted to the version 4.0 and the suitable "upgrade" and "lease dump" scripts have to be added to src/bin/admin/scripts.

Changes to the PostgreSQL Backend

PostgreSQL backend requires the same set of changes as described in Changes to the MySQL Backend.

Leases Reclamation Routine

The leases reclamation routines (one for DHCPv4, one for DHCPv6) will be executed periodically, with a frequency specified by the server's administrator. Each routine execution will processes a subset of the expired leases from all subnets.

The following parameters will be configurable and will be passed as arguments to the leases reclamation routine:

  • max_leases, holding the maximum number of leases to be processed by the routine,
  • timeout, maximum amount of time that the routine may be processing expired leases, expressed in seconds.
  • remove_lease, a boolean value indicating if the lease should be removed when it is reclaimed (if true) or it should be left in the database in the "expired-reclaimed" state (if false). This value will be configured indirectly, i.e. it will be set to true when the "lease affinity" is disabled.
  • max_unwarned_cycles, specifies a number of consecutive runs of lease reclamation routine after which a warning should be issued if there are still expired (and not reclaimed) leases in the lease database. This warning is an indication to the administrator that the leases reclamation may need to be reconfigured to be executed more frequently or the maximum number of reclaimed leases should be increased.

The first parameter will be used as an input to the LeaseMgrFactory::instance().getExpiredLeases{4|6} to retrieve expired leases to be reclaimed. This value may be set to 0 to indicate that all leases must be retrieved. See the New Methods in LeaseMgr for details.

The value passed as the second parameter is compared with the total time spent in the routine so far, after reclamation of every lease. When the total time exceeds the "timeout", the routine returns. In this case, some of the leases may not be reclaimed in this cycle, if the "max_leases" value is too high. It is allowed to specify 0 as a "timeout" value, in which case the routine will not be interrupted until "max_leases" are reclaimed, or until all leases are reclaimed if the "max_leases" value is also set to 0. The isc::util::Stopwatch class will be used to measure accumulated time spent in the leases expiration routine.

The lease reclamation routines will be implemented as public methods within the AllocEngine class and will generally perform the following operations:

  1. retrieve expired (and not reclaimed) leases to be reclaimed from a database,
  2. execute lease expiration hook for each reclaimed lease,
  3. send removal name change request to D2 for each reclaimed lease when DDNS updates are enabled,
  4. mark each processed lease reclaimed in the lease database, i.e. remove the lease if indicated by the "remove_lease" parameter or leave in "expired-reclaimed" state otherwise,
  5. log summary information about the number of reclaimed leases,
  6. update statistics concerning expired leases

According to the Decline Design, the declined leases will remain in the lease database and have their valid lifetime set to a time when the declined lease should be returned to the pool. As a result, the declined leases will be returned by the queries for expired leases when their valid lifetime elapses. Such leases will require special action. In particular: the dedicated hook will be executed for each of them and the declined leases will be removed from the database. The DNS updates will not be triggered. See the Decline Design for details.

The following are the declarations of the leases reclamation routines for DHCPv4 and DHCPv6 respectively:

void reclaimExpiredLeases4(const size_t max_leases, const uint16_t timeout,
                           const bool remove_lease,
                           const uint16_t max_unwarned_cycles);

and

void reclaimExpiredLeases6(const size_t max_leases, const uint16_t timeout,
                           const bool remove_lease,
                           const uint16_t max_unwarned_cycles);

Issues with the Unexpected Shutdown

When a lease is marked "expired-reclaimed" in the lease database,i.e. it becomes available for the assignment to the clients, it will not be returned in the queries for the expired leases. If the unexpected server shut down occurs after the lease has been marked reclaimed, but unprocessed leases exist, the process will resume from the point of failure when the server is back online, because the leases are processed from the most to the least expired one. If the shutdown occurs right after marking the lease "expired-reclaimed", there is no guarantee that the logging traces for this lease are preserved in the log file or that the statistics have been updated for this lease. However, these are considered minor issues, because log file truncation may occur for almost any operation performed by the DHCP server in case of the power failure. Also, since the statistics is not persisted it is lost with the server shutdown anyway.

The more problematic case occurs when the server shutdown takes place before the lease is marked "reclaimed", and after the callouts are executed. The lease hasn't been fully reclaimed and the server will try to reclaim it again when it is back online. As a result, the callouts for this lease will be executed twice. As there seem to be no reliable (and efficient) way to defend the system against such a condition, the mitigation strategy will be to document this issue in the Guide for the Hooks Developers with the statement that "the hooks developers must be prepared that the callouts may be called multiple times for some leases and hooks must handle this situation gracefully". The Kea Administrator Reference Manual must also be updated with a description of such a possibility.

Retrieving Expired Leases

The lease reclamation routines will use the new methods in LeaseMgr, described in Changes To the Memfile Backend section, to retrieve a given number of expired leases from the database. For example:

Lease6Collection leases;
LeaseMgrFactory::instance().getExpiredLeases6(leases, max_leases);

New Hook Points

The following new hook points must be registered in the AllocEngine for the DHCPv4 and DHCPv6 lease reclamation respectively:

  • lease4_expire, with the Lease4Ptr argument holding a pointer to the DHCPv4 lease being reclaimed
  • lease6_expire, with the Lease6Ptr argument holding a pointer to the DHCPv6 lease being reclaimed

Any callout executed for these hook points may set the skip flag, which indicates that the lease reclamation routine must cease lease reclamation for the particular lease. As a result, the routine will not send name change requests to D2, nor mark the lease "expired-reclaimed". However, the routine will update the relevant statistics in the StatsMgr as if the lease has been reclaimed. The routine will also log summary information for the number of expired leases processed, regardless if the "skip" flag is set for any of them. In other words, the routine treats all leases for which the "skip" flag has been set, as reclaimed.


Discussion: If any callout in the "lease4_expire" or "lease6_expire" hook sets the "skip" flag, the lease expiration routine will not mark the lease as "expired-reclaimed" in the database. The responsibility for doing it is on the callout. If the callout doesn't mark the lease as "expired-reclaimed", the lease will be processed again when the lease reclamation routine is executed next time. The expired leases will pile up in the database, which will effectively break the lease reclamation process. Therefore, the documentation should discourage the use of the "skip" flag for these hook points and warn about the possible malfunction of the lease reclamation process if the lease is not marked "reclaimed".

Alternatively, we could change the behavior of the lease reclamation process to always mark lease as "expired-reclaimed" in the database, regardless of the "skip" flag value. In this case, the "skip" flag would only cause the routine to not send the name change requests to the D2.

In the course of the discussions and reviews of this document, it has been decided that setting the "skip" flag by the hook application should mean that the application has taken the "full responsibility" for the lease reclamation, including marking it as "reclaimed" in the database. All implications of hook failing to do it should be well documented in the Developer's Guide.


The #3499 proposes extending the signaling from the hooks with additional indicators, e.g. "drop". The "lease4_expire" and "lease6_expire", as opposed to other hook points, is not associated with a packet, so the behavior for the "drop" indicator would be interpreted differently. It would cause the server to interrupt the leases reclamation routine.

Sending Name Change Requests

When the lease is being reclaimed, the name change requests for this lease may either be sent from the lease reclamation routine or from the callout. In the latter case, the callout should set the "skip" flag to indicate that the callout has taken responsibility for reclaiming the lease and the lease reclamation routine will not send the name change request.

From the callout implementor's standpoint it will be useful to have a convenience method, which would send appropriate name change request for the particular Lease4 or Lease6 object, representing an expired lease. The same method would be used by the lease reclamation routine to send the name change requests if the "skip" flag wasn't set by the callout. Using the same method would guarantee the consistency of the code sending the name change requests for the expired leases, regardless if sent from the callout or from the lease reclamation routine.

These methods will be implemented in the common place and will have the following signatures:

void queueNCR(const dhcp_ddns::NameChangeType& type, const Lease4Ptr& lease);

and

void queueNCR(const dhcp_ddns::NameChangeType& type, const Lease6Ptr& lease);

These methods will have to compute DHCID from the FQDN information held in the lease, and from the unique identifier of the client, i.e. DUID in the DHCPv6 case, and client identifier (if present) or HW address in the DHCPv4 case. Note that the type argument is not required for the lease expiration because it should always be set to CHG_REMOVE in this case. However, these methods may also be used for other purposes in the future, for which the type may be required.

Marking a Lease as "expired-reclaimed"

The expired lease becomes "expired-reclaimed" when it is deleted from the lease database or when its state is set to "expired-reclaimed" in the "state"field. The lease is reclaimed after the callouts have been executed and the name change requests have been generated for it. The lease database backend doesn't require any updates to support it. The lease reclamation routine will call the existing methods to delete or update the lease (including its state). For example:

...

LeaseMgrFactory::instance().deleteLease(lease->addr_);

...

where lease is the pointer to the expired lease, represented by the Lease4Ptr or Lease6Ptr.

In case when lease affinity is required, the lease state will be updated instead, e.g.

...

lease->state_ = Lease::STATE_EXPIRED_RECLAIMED;
LeaseMgrFactory::instance().updateLease(lease);

...

Statistics for Reclaimed Leases

The lease reclamation routine will use the following new statistics:

  • reclaimed-leases, holding the total number of leases reclaimed
  • subnet[id].reclaimed-leases, holding the total number of leases reclaimed for the subnet, identified by the "id"

The values above will be increased for each reclaimed lease.

In addition, the following existing statistics will be used (decreased) for the reclaimed lease:

  • DHCPv4:
    • subnet[id].assigned-addresses, always decreased for the DHCPv4 lease
  • DHCPv6:
    • subnet[id].assigned-nas, decreased when the expired lease is for a non-temporary address (NA lease)
    • subnet[id].assigned-pds, decreased when the expired lease is for a prefix (PD lease)

The subnet identifier will be retrieved from the object representing the expired lease.

Logging

The lease reclamation routine will use the following new messages for the DHCPv6 server.

MessageSeverityDescription
ALLOC_ENGINE_V6_LEASES_RECLAMATION_STARTDEBUGTrace used to log that the leases reclamation is starting
ALLOC_ENGINE_V6_LEASE_RECLAIMDEBUGTrace used to log that a particular lease is being reclaimed.
ALLOC_ENGINE_V6_LEASES_RECLAMATION_COMPLETEDEBUGTrace used to log that the single cycle of the lease reclamation has completed. It will include the number of the leases reclaimed in this cycle and the execution time.
ALLOC_ENGINE_V6_LEASE_RECLAMATION_FAILEDERRORError message indicating that the reclamation of a particular lease failed
ALLOC_ENGINE_V6_LEASE_RECLAMATION_TIMEOUTDEBUGTrace used to indicate that the user-defined timeout occurred for the lease reclamation routine. The reclamation processing will terminate to enable the server to continue processing incoming DHCP messages. The reclamation of expired leases will continue when the leases reclamation routine starts again.

Similar messages will be added for the DHCPv4 lease reclamation routine, e.g. ALLOC_ENGINE_V4_LEASES_RECLAIMED instead of ALLOC_ENGINE_V6_LEASES_RECLAIMED.

Periodically Executing Tasks

The DHCP servers' architecture is based on the synchronous processing model, using a single thread. The main loop includes the blocking call to select() function (through the IfaceMgr object), with the default timeout of 1000ms to receive the data from the open sockets. While this model performs well for the DHCP messages processing, it makes it difficult to implement the execution of the periodic tasks, such as Lease File Cleanup or leases reclamation.

Execution of the periodic tasks in the main loop requires the invocation of the select function to be interrupted at the given time, when the task needs to be executed. The current approach, used for the Lease File Cleanup, is to use the timeout value for the select function equal to the interval at which the LFC should be executed. However, this approach is not considered extensible for the cases when multiple tasks must be performed periodically, at different rates.

There have been two alternative approaches considered for this design, which involve the use of the "worker thread" to asynchronously execute the periodic tasks. Both approaches are described further down.

Approach 1

Periodic tasks are scheduled according to the server configuration. Each task is handled by an instance of the IntervalTimer object. Every IntervalTimer object is initialized with the same common instance of the IOService. The IOService should be declared in the Deamon class, from which all the servers derive. The timers may be created independently in the different modules of Kea, e.g. LFC timer may be created in the Memfile_LeaseMgr, and the timer for the lease reclamation routine may be created in the Dhcpv4Srv class. The only requirement is that all timers share the same IOService object.

The server spawns a worker thread which runs concurrently with the main thread the entire time, and ends when the server shuts down. Worker thread uses the common instance of the IOService object and simply runs ready handlers, i.e. executes io_service_.run(). The thread ends if it detects that the server shutdown is in progress. The main thread waits for the worker thread to return before exiting.

By running the run() function, the worker thread executes the callback functions associated with the installed timers, i.e. LFC kick in, or leases reclamation routine. In order to prevent possible race conditions in accessing shared objects, such as AllocEngine, the mutex is used in both callback functions executed by the worker thread and the main thread. The worker thread locks the mutex when the callback starts, because this call may execute periodic tasks like leases reclamation routine. When the callback returns, the mutex is unlocked.

The main thread unlocks the mutex for the time when it is waiting for new DHCP messages to be received over the sockets, i.e. roughly for the time it performs select(). It locks the mutex when the select() returns. If the worker thread is still executing periodic tasks while the select() has returned, the main thread waits on the mutex until these tasks are completed and the mutex is unlocked. As a result, the periodic tasks are only performed concurrently with an attempt to receive the data over the socket.

The advantage of this approach is its simplicity, i.e. the worker thread implementation is very simple and timers must only be associated with a common instance of the IOService object. However, this approach has the following downsides:

  • lease expiration routine, including the "lease4_expire" and "lease6_expire" callouts, is executed concurrently with the packets reception over the sockets. Although it looks harmless, we're not able to tell what user-defined applications (a.k.a. hooks) will be doing, and whether or not they will cause race conditions with the packet reception attempts.
  • it is going to be tricky to implement the concurrent lease reclamation routine running concurrently with the lease allocation in the main thread, as it would require spawning a new thread from the worker thread.

Approach 2

This approach is similar to the Approach 1, but it guarantees that the IntervalTimer handlers are executed from the main thread, rather than from the worker thread. This prevents the potential race conditions between the lease reclamation routine and the packet reception operation.

To implement this approach a new class is needed: TimerMgr. This is a singleton class, available from different places in the code, which creates the IntervalTimer instances, for which handlers (callbacks) are to be executed periodically in the main thread. Each created instance of the timer is mapped to a different WatchSocket object (currently in src/lib/dhcp_ddns and to be moved to utilities). The instances of the created timers are associated with a generic callback function, implemented within the TimerMgr class. This function is executed with a single argument: timer_name, which identifies the timer.

Each created timer is associated with an instance of the WatchSocket object. This object is registered in the IfaceMgr as an external socket with the appropriate callback function. The generic callback function picks the appropriate WatchSocket to use and marks it "ready". This causes the transfer of data over the socket, which interrupts the select() function in the main thread and triggers the execution of the callback associated with this socket, e.g. lease file cleanup or leases reclamation routine. If the socket is marked "ready" while the server is NOT waiting on the blocking call to the select(), the callbacks will be executed as soon as the server reaches select() and invokes handlers registered for the external sockets.

This approach is more complex than Approach 1 in that, it requires the implementation of the new class and signaling between the worker thread and the main thread. However, it provides more thread safety. Therefore, the Approach 2 has been chosen for the implementation.

Class Diagram

The class diagram for the TimerMgr is depicted below.

Each timer operates in one of the two modes: ONE_SHOT or REPEATING. In the former mode, the timer is scheduled and its handler is executed only once. In the latter mode, the timer is executed repeatedly until it is cancelled. The advantage of using the "one shot" timer for repeated tasks, like leases reclamation, is that it is possible to schedule the next execution of the lease reclamation routine when the previous execution has ended and thus ensure a certain period (configured by the administrator) between two consecutive runs of the lease reclamation routine.

If the routine was executed at the fixed time periods it would be possible that the handler hasn't completed, the next timer interval has elapsed and new ready handler has been queued. The ready handlers would pile up and the lease reclamation routine would be repeatedly executed with no idle period.

When using the "one shot" timer, the handler for this timer is executed only once for each call of the setup function. The callback function executed for this timer is responsible for re-scheduling the timer right before the callback returns. For example:

void reclaimExpiredLeases6(const size_t max_leases, const uint32_t timeout,
                           const bool remove_lease) {

    Lease6Collection expired_leases;
    LeaseMgr::instance().getExpiredLeases6(expired_leases, max_leases);
    for (Lease6Collection::const_iterator lease = expired_leases.begin();
         lease != expired_leases.end(); ++lease) {
        // perform lease reclamation here
    }

    // Re-schedule the timer.
    TimerMgr::instance().setup("lease-reclaim-timer");
}

assuming that the "lease-reclaim-timer" is a unique name for the timer executing the lease reclamation routine.

The timer should be created and scheduled for the first time, using the following code:

// Create the timer.
TimerMgr& timer_mgr = TimerMgr::instance();
timer_mgr.registerTimer("lease-reclaim-timer",
                        boost::bind(&AllocEngine::reclaimExpiredLeases6,
                        this, max_leases, reclaim_timeout, remove_lease),
                        reclaim_interval,
                        IntervalTimer::ONE_SHOT);

The TimerMgr owns the worker thread which is executing IOService::run to spawn ready handlers. The thread is explicitly started and stopped using the TimerMgr::startThread and TimerMgr::stopThread accordingly.

Removing Reclaimed Leases

If the lease affinity is enabled the leases reclamation routine will not remove expired leases from the database. It will merely set their state to "expired-reclaimed". After a configurable amount of time these leases should be however removed from the database to avoid gathering an excessive number of unused (expired) leases and thus database bloat.

The removal of the "expired-reclaimed" leases is performed periodically, using the dedicated interval timer. The timer is setup in the same way as the timer for lease reclamation routine, but may be executed according to a different interval. The function performing periodic removal of the "expired-reclaimed" leases (recycling function) will remove only those leases for which a specified amount of time elapsed since they have expired. All "expired-reclaimed" leases for which less time has elapsed since expiration will be left in the lease database.

The interval at which the recycling function is executed may be set to 0, in which case the timer is not setup and the function is not executed. This configuration yields no lease affinity. The expired leases are never left in the "expired-reclaimed" state. In this case the lease reclamation routine becomes responsible for removing expired leases.

The recycling function will use the LeaseMgr::deleteExpiredReclaimedLeases{4,6} functions to remove the leases in the "expired-reclaimed" state. The "secs" parameter of these functions will be obtained from the server configuration.

Reclaiming Allocated Lease

The current allocation strategy allows for "reusing" an expired lease when the client is requesting the lease acquisition. The reused lease may belong to this or any other client. As we introduce the expired leases processing, the "reuse" of expired leases should occur more rarely, but will not be completely eliminated due to the periodic nature of the leases reclamation routines. Hence, the allocation engine must be extended to facilitate the reclamation of a single lease, when this lease is being reused. Since the allocation engine already handles the DNS updates for the reused leases, this change will be mostly about adding the the "lease4_expire" and "lease6_expire" hooks invocations. To avoid code duplication, the code handling the reclamation of a single lease should be enclosed in a function. This function should provide the parameters indicating if the reclaimed lease should be only marked "reclaimed" or reused. In the latter case, the lease replacing the expired lease should be provided.

Configuration Structure

This section of the requirements document explicitly lists the parameters to control the behavior of the system, with respect to expired leases processing. These parameters are specified in the configuration file, in the "expired-leases-processing" map structure:

"expired-leases-processing": {
    "reclaim-timer-wait-time": 1,
    "flush-reclaimed-timer-wait-time": 2,
    "hold-reclaimed-time": 1800,
    "max-reclaim-leases": 100,
    "max-reclaim-time": 300,
    "unwarned-reclaim-cycles": 5
}

where:

  • reclaim-timer-wait-time is the time between two cycles of processing expired leases, expressed in seconds, i.e. the time between the end of one cycle and the beginning of the next cycle. If this value is 0, the expired leases are not processed.
  • flush-reclaimed-timer-wait-time is the time between two cycles of recycling "expired-reclaimed" leases, expressed in seconds. If this value is 0, the expired leases are removed by the leases reclamation routine rather than recycling function. The recycling function is not executed and the value of the "hold-reclaimed-time" is ignored.
  • hold-reclaimed-time is the time for which "expired-reclaimed" leases are held in the lease database in the "expired-reclaimed" state after they expire. If this time is set to 0, the recycling function is not executed and the value of the "recycle-timer-wait-time" is ignored.
  • max-reclaim-leases is the maximum number of leases to be processed in a single cycle. If this value is 0, all expired leases are processed in a single cycle, unless the maximum processing time (configured with the "max-time") parameter elapses first.
  • max-reclaim-time is the maximum time that a single processing cycle may last, expressed in milliseconds. If this value is 0, there is no limitation for the maximum processing time.
  • unwarned-reclaim-cycles is the number of consecutive processing cycles of expired leases, after which the system issues a warning if there are still expired leases in the database. If this value is 0, the warning is never issued.

This map will be placed at the top level of the configuration and will affect all subnets.

New Server Command

The new command will be implemented to allow for triggering the leases reclamation manually. This command will have the following JSON structure:

{
    "command": "leases-reclaim",
    "arguments": { "remove": bool }
}

where "remove" value indicates if leases should be removed on reclamation (if true) or left in the "expired-reclaimed" state (if false).

Implementation Tasks

The following is the list of tasks required to implement Lease Expiration in Kea 1.0:

  • #3965 - Extend Memfile Backend to support queries for expired leases
  • #3966 - Extend MySQL backend to support queries for expired leases
  • #3967 - Provide upgrade scripts to the 4.0 MySQL schema version
  • #3968 - Extend PostgreSQL backend to support queries for expired leases
  • #3969 - Provide upgrade scripts to the 4.0 PostgreSQL schema version
  • #3970 - Implement TimerMgr.
  • #3971 - Use TimerMgr for lease file cleanup scheduling.
  • #3972 - Implement "lease4_expire" and "lease6_expire" hooks
  • #3973 - Implement lease reclamation routines for DHCPv4 and DHCPv6
  • #3974 - Extend servers' configuration to support lease expiration specific parameters
  • #3975 - Schedule lease reclamation and recycling depending on the configuration parameters (include extensive unit tests)
  • #3976 - Extend lease reclamation routine to act upon declined leases
  • #3977 - Extend allocation engine to reclaim "reused" lease
  • #3978 - Implement "leases-reclaim" command.
  • #3979 - Document lease expiration processing in the Kea Guide, including statistics.
  • #3980 - Update Design and Requirements with modifications introduced during the implementation and "lessons learned".
Last modified 23 months ago Last modified on Jan 7, 2016, 8:16:21 PM

Attachments (1)

Download all attachments as: .zip