Performance improvement ideas
This page lists performance improvements to be considered in upcoming Kea 1.7. Some of them are quite radical, other may not work or provide little improvement. Do not expect all of them to be implemented and released.
For some input on performance requirements, see the following small survey conducted on kea-users https://www.surveymonkey.com/results/SM-RWNVL7SFV/ . The data itself is available if you have any further questions, just ask Vicky.
Master ticket: #874 (closed)
As of 1.6, Kea is mostly single threaded. There are threads doing some side tasks, but the primary heavy duty work is done in one thread. We could make Kea use multiple threads. The intention here is to use more than one CPU core. It is clear that the increase of performance will not be a linear function of number of cores.
This is the most complex task. There are many races that will have to be addressed.
One of things that would need to be done would be to support pools of connections to things like lease and host DBs.
Another possibility is to look at multiple processes. Although not a complete solution, it should require less work, although the result would only be applicable to certain deployments. Specific points that come to mind:
- It may not work with raw sockets. (With UDP sockets, multiple processes should be able to share the port using SO_REUSEPORT.)
- Sharing a memfile database requires shared memory or a dedicated memfile server (similar to memcached)). However, sharing a database backend just requires each process to have its own connection to the database.
- The lease allocation algorithm will need to be changed to ensure that the multiple processes are not all trying to allocate a lease for the same address at the same time.
MN comment: what actually would be run in threads? requests would be processed in parallel or maybe some other side jobs?
Lease database improvements
Master issue: #875
Stored procedures to return empty lease
As of 1.6, we have iterative allocator, which tries leases one by one. It's very fast if the pool utilization is small and there are relatively many addresses available. However, it slows down dramatically when most addresses are already allocated. For example, if there's a /24 subnet and we have 250 addresses allocated, finding the next free may take up to 250 queries. This can be extremely slow.
This idea alleviates the problem by calling a stored procedure once, the procedure finds the lease and returns it. This should be much faster as it requires just one call and the processing is done locally on MySQL/pgsql
A potential SQL query that might optimise this given e.g. an
addr int(4) unsigned field that holds IPv4 addresses in integer format is this:
SELECT addr + 1 FROM lease WHERE addr + 1 NOT IN (SELECT addr FROM lease);
It is insufficient by itself because it cannot fill the start of the lease table - if there are no leases at all it returns an empty result. It also only allocates spare addresses that are found in gaps after existing leases (or after the final lease). A similar query could be used to fill downwards from gaps if the first query fails.
Single query returning all unexpired leases in a pool/subnet (lease cache)
This is another approach to avoid many queries about lease availability. Instead of repeatedly asking "is X free?" , "is X+1 free?", we would ask "give us all currently allocated leases for a pool/subnet". Kea would then know which are used and try to allocate only those that are not used.
This should improve performance dramatically for high pool utilization scenarios. However, it wouldn't really work for multiple instances connected to the same DB.
Keep free leases in a database
The current lease model assumes that we keep only the currently used leases in the database. SQL does not provide ability to query for non-existent data, so we can't ask for a free lease, can only ask if address X is available or not. If we change the model to keep available leases in db, we could simply ask give me the first available address". The downside is that technique would make the DB bigger, even when few (or none) addresses are allocated. The flip side is it should improve lease allocation dramatically.
Do not delete expired leases
Typically, allocation will only be a problem if a pool starts getting full. So an alternative strategy that may help is not to delete expired leases. Instead, when a pool's usage rises above a certain percentage, the allocation engine first searches for an expired lease. Only if there are no expired leases does it search through the pool for an address with no lease associated with it.
Never use all addresses in a pool
The performance problem when searching for leases arises when a poll is nearly full. In these cases, a lot of addresses may need to be checked before a free address is found. This idea sets a maximum pool occupancy; if the pool usage exceeds this figure, the pool is skipped when searching for an available address. It of course has the downside that there will be wasted addresses.
Warn administrators when a pool is getting full
Log a warning message when a pool starts getting full. ISC DHCP has this feature - see the documentation for the
Improve next address selection algorithm
Right now kea uses iterative algorithm. It starts with the first address in a pool and asks the DB "is this address available?" if the answer is yes, it is assigned to a client. If not, Kea asks about the next address. This is a simple algorithm that is very fast if your address space is mostly empty. However, if the pool utilization is large, its performance degrades greatly. Also, in principle the algorithm allows multiple instances to use common database. However, there's a tendendency to synchronize the address to be tried next, so all instances are stomping over each other.
One trivial improvement here is for case of 2 instances: make the other instance walk backwards. For n>2 we need something smarter. We need an algorithm that traverses the whole address space, visiting all addresses in some order.
Permitting DISCOVER/SOLICIT to actually allocate a leases
Master issue: #877
Permit the servers to do an actual allocation on DISCOVER/SOLICIT (i.e. fake-allocation flag = NO) - ISC DHCP assigns a shortened life-time (120 seconds) to leases when they are first offered. This keeps them from being offered to any other client. At first blush, it might seem like this would would slow down our response rate, but then again it might actually make us faster overall. Requests end up being treated more like renewing/returning clients. It would also make it far easier for multiple Kea instances (or even threads), to share the same address space.
Adapt host cache to work with MySQL and PgSQL
Master issue: #556 (closed)
Our current (1.6) host cache backend was originally developed for RADIUS and currently works with RADIUS only. We could make it more generic and in principle it should be able to work with MySQL, PgSQL or even Cassandra. Any caching mechanism would be difficult or even impossible to use in scenarios where there are multiple instances using the same DB.
Tweak congestion control
Master issue: #285 (closed)
While congestion control will never be able to improve performance, it is a feature designed to deal with overload scenarios better. After 1.5 went out the door, we never had time to tweak is properly. We never reached a consensus on the default queue size (or a way to set it properly, one proposal was to measure performance in leases/sec and set the queue size to 80% of that value, so you'd buffer at most 800ms, which is below 1000ms, a value that triggers first retransmissions). Also, for some unknown reason the performance is roughly 15% lower when congestion control is enabled. The reason for this is unclear (in general, there should not be any degradation).
Improve build procedure
Master issue: #304
Currently autotools are employed for doing Kea build. It works in recursive manner. This approach is pretty slow as 1) it requires traversing all folders, 2) when given folder is being build even in parallel during compiling last files in this directory and then linking .a library not all CPUs are utilized.
Another issue with recursive approach is that it does not support dependencies between subdirectories.
Modern approach for these issues is non-recursive, flat builds. It utilizes all CPUs all the time and allows defining dependencies between subirectories/components. One of tools that support this pretty well is Meson. POC with Meson for Kea is in progress.
Implement avalanche mode in perfdhcp. Done. But it's not documented yet: #876 (closed)
Implement torture test - gradually increase generated traffic until Kea is not able to keep up: #60
Handle malformed packets better - #477 (closed)
perfdhcp should better scrutinize received packets - #572 (closed)
perfdhcp sends a bit too many packets - #662 (closed)
Master issue: #878
- Restructure MySQL backend to have one method that runs all queries. That way we could run some logging there.
When dealing with performance issues, such as recently reported by a customer, who experienced 14 leases/sec with mysql, we don't have any effective means to pinpoint the problem. In principle, the DB interaction is split into two phases: host reservation lookups and lease lookups. It would be useful to have easy to use statistics that would let us figure out what area is causing problems. Things like:
- looking for reservations took X us,
- looking for leases took Y us.
- Z queries per packet were conducted.
- W total queries performed by backend, average response time was A.
- possibly stats by query type (getLease4byHWAddr, getLease4ByAddr, etc.)
- possibly query by SQL type (A number of SELECTs, B number of INSERTs, C number of DELETEs)