Skip to content
GitLab

Lease Limiting and Rate Limiting Design · Changes

Page history
rename designs to Designs authored by Andrei Pavel's avatar Andrei Pavel
Hide whitespace changes
Inline Side-by-side
Designs/Lease-Limiting-and-Rate-Limiting-Design.md 0 → 100644
View page @ e3c1f9fd
[[_TOC_]]
# Lease Limiting and Rate Limiting
Lease limiting and rate limiting are applicable to clients identified through client classification
or through subnet ID. Spawning classes, spawned classes and regular classes can all be used to limit
leases or rate. This offers uncompromising flexibility.
Limits apply to each individual client class. If at least one class has reached the limit, the
packet is not honored.
## Action to Take on Limit Surpassing
If the limit criteria is surpassed, packets could be either silently discarded or replied to with a
DHCPv4 NAK and a DHCPv6 reply with the UnspecFail status code, respectively. Onto DHCPv6, the
following excerpt from RFC3315 describes a convenient measure to convenience the client to lower the
rate. Per the RFC, the client MUST implement. It helps lower congestion in the network, which is one
of the possible end results that the user aimed for, at least when configuring rate limiting.
> If the client receives a Reply message with a Status Code containing
> UnspecFail, the server is indicating that it was unable to process
> the message due to an unspecified failure condition. If the client
> retransmits the original message to the same server to retry the
> desired operation, the client MUST limit the rate at which it
> retransmits the message and limit the duration of the time during
> which it retransmits the message.
There is no equivalent DHCPv4 mechanism documented in RFCs. As it stands, with the goal of lowering
the strain on lease limiting and rate limiting, it seems that the proper reaction to a packet
passing the limit, is assymetric: a silent discard for DHCPv4, a reply with UnspecFail status code
for DHCPv6. Alternatively, there could be a boolean knob called `"discard-packet"` configurable in
the hook library's parameters. But the problem of what is a proper default arises and, if efficiency
is what we're after, assymetric defaults might have to be implemented: `true` for DHCPv4, `false`
for DHCPv6. Please leave your comments if you can help with this decision.
## Configuring limits
The lease limiting configuration knob is unambiguous as an integer. It can be left as such since it
will be needed as integer for comparison with the lease counter retrieved from the backend.
For rate limiting, with flexibility and intuiteveness in mind, suggesting a string of the format
`"<p> packets per <time-unit>"`. `<p>` is any number that can be represented by an `unsigned int`.
`<time-unit>` can be any of `second`, `minute`, `hour`, `day`, `week`, `month`, `year`. `month` is
considered 30 days for simplicity. This syntax covers a high range of rates from one lease per year
to four billion leases per second.
The configured value of 0 packets can be a convenient way of disabling packet processing for certain
clients entirely. As such, it means its literary value and is not a special value for disabling
lease limiting, and rate limiting, respectively, but on the contrary enforcing it to the extreme.
Disabling is achieved by removing the leaf configuration entry, the map around it or the entire hook
library.
For easier configuration, multiple classes or multiple subnets can be associated with one limit. The
classes and subnets need to be completely disjunctive from one another. The parser will check this.
```json
{
"DhcpX": {
"hooks-libraries": [
{
"library": "/usr/local/lib/libdhcp_limits.so",
"parameters": {
"limits": [
{
"client-classes": ["spawned-class", "regular-class"],
"lease-limit": 2,
"rate-limit": "512 packets per hour"
},
{
"client-classes": ["spawning-class2", "spawned-class2"],
"lease-limit": 4,
"rate-limit": "128 packets per minute"
},
{
"client-classes": ["spawning-class3"],
"lease-limit": 8,
"rate-limit": "32 packets per second"
},
{
"client-classes": ["spawned-class4", "regular-class4"],
"lease-limit": 16
},
{
"client-classes": ["regular-class5"],
"rate-limit": "8 packets per second"
},
{
"subnet-ids": [1, 2],
"rate-limit": "4 packets per second"
}
]
}
}
]
}
}
```
* Or classes and subnets as keys.
```json
{
"DhcpX": {
"hooks-libraries": [
{
"library": "/usr/local/lib/libdhcp_limits.so",
"parameters": {
"limits": {
"spawned-class": {
"lease-limit": 2,
"rate-limit": "512 packets per hour"
},
"subnet-id[1]": {
"rate-limit": "4 packet per second"
},
"subnet-id[2]": {
"rate-limit": "2 packets per second"
}
}
}
}
]
}
}
```
* Or to avoid accidental changes of client class names or subnet IDs while forgetting to change the
limits: keep the limits colocated with the definitions of client classes and subnets.
```json
{
"DhcpX": {
"client-classes": [
{
"name": "gold",
"test": "option[123].hex == 0x0001",
"lease-limit": 8192,
"rate-limit": "1024 packets per second"
}
],
"hooks-libraries": [
{
"library": "/usr/local/lib/libdhcp_limits.so"
}
],
"shared-networks": [
{
"subnetX": [
{
"subnet": "10.0.0.0/8",
"lease-limit": 128,
"rate-limit": "16 packets per second"
}
]
}
],
"subnetX": [
{
"subnet": "192.168.0.0/24",
"lease-limit": 16,
"rate-limit": "2 packets per second"
}
]
}
}
```
* Or limits inside the user context of client classes and subnets.
```json
{
"DhcpX": {
"client-classes": [
{
"name": "gold",
"test": "option[123].hex == 0x0001",
"user-context": {
"lease-limit": 8192,
"rate-limit": "1024 packets per second"
}
}
],
"hooks-libraries": [
{
"library": "/usr/local/lib/libdhcp_limits.so"
}
],
"shared-networks": [
{
"subnetX": [
{
"subnet": "10.0.0.0/8",
"user-context": {
"lease-limit": 128,
"rate-limit": "16 packets per second"
}
}
]
}
],
"subnetX": [
{
"subnet": "192.168.0.0/24",
"user-context": {
"lease-limit": 16,
"rate-limit": "2 packets per second"
}
}
]
}
}
```
## Rate Limiting Implementation
The interest is to limit the packet as early as possible, so, based on the earliest hook point that
provides the necessary data, the `pkt[46]_receive` hook point is used when client class is used as
an identification criterion and the `subnet[46]_select` hook point is used for subnet ID.
Populating containers, shifting elements, checking the packet limit are all done in each hook point.
Best further expressed in v4 pseudocode. v6 is left to the reader's extrapolation.
```cpp
/// @brief List of times at which packets were admitted based on class or subnet ID
/// @{
std::unordered_map<ClienClass, std::list<std::time_t>> clocked_in_times_by_class_;
std::unordered_map<SubnetID, std::list<std::time_t>> clocked_in_times_by_subnet_id_;
/// @}
/// @brief A single rate-limiting configuration entry
struct RateLimit {
/// @brief The configured limit
unsigned int allowed_packets_;
/// @brief 1 time unit in seconds
std::time_t time_unit_;
};
using RateLimitPtr = std::unique_ptr<RateLimit>;
int pkt4_receive(CalloutHandle& handle) {
Pkt4Ptr pkt;
handle.getArgument("query4", pkt);
for (ClientClass const& class : pkt->getClasses()) {
RateLimitPtr const& limit(config_->getLimit(class)->rateLimit());
if (!limit) {
// No checking, but also no keeping track of it. Rate limiting is not persistent-critical.
continue;
}
std::list<std::time_t>& list_of_times(clocked_in_times_by_class_[class]);
std::time_t now(std::time(nullptr));
// TODO: potential optimization based on the guarantee that times are sorted in the list, so it
// can stop at the first one that has not surpassed the limit.
list_of_times.remove_if([](std::time_t t) { return t + limit->time_unit_ < now; });
if (limit->allowed_packets_ < list_of_times.size()) {
limit_surpassed(pkt); // Probably drop.
}
list_of_times.emplace_back(now);
}
}
int subnet4_select(CalloutHandle& handle) {
Subnet4Ptr subnet;
handle.getArgument("subnet4", subnet);
SubnetID const subnet_id(subnet->getID());
RateLimitPtr const& limit(config_->getLimit(subnet_id)->rateLimit());
if (!limit) {
// No checking, but also no keeping track of it. Rate limiting is not persistent-critical.
continue;
}
std::list<std::time_t>& list_of_times(clocked_in_times_by_subnet_id_[subnet_id]);
std::time_t now(std::time(nullptr));
// TODO: potential optimization based on the guarantee that times are sorted in the list, so it
// can stop at the first one that has not surpassed the limit.
list_of_times.remove_if([](std::time_t t) { return t + limit->time_unit_ < now; });
if (limit->allowed_packets_ < list_of_times.size()) {
limit_surpassed(pkt); // Probably drop.
}
list_of_times.emplace_back(now);
}
```
## Rate Limiting Alternative Considerations
Following are a few ideas that were ruled out, but maybe they seem appealing to the reader.
> **_NOTE_**: Thought has been given to allow `"<l> leases per <time-unit>"`. It would mean favoring
> packets that don't get any leases as they would pass the filter, not to mention allowing for
> unlimited discovers and solicits when rapid commit is disabled. It is unlikely to be a desirable
> configuration.
> **_NOTE_**: Thought has been given to add an optional `with <d> data points` to the syntax where
> `<d>` is the number of time periods to consider in the calculated time series with a default value
> of 1. The context under which it was thought of, was with the false impression that the resolution
> at which the rate is checked is `<time-unit>` e.g. for `minute`, Kea allows however many packets
> until the minute mark, and only at that time Kea checks if the limit was reached. That design is
> undesirable and might even be inefficient in performance, as opposed to imposing the limit on each
> packet which seems perfectly plausible. However, if the design restricted the resolution to
> `<time-unit>`, the data points would have made sense. It would have been a great tool against
> frequent and aggressive flooders. Imagine a rate limit of 20 per minute and 1000 packets sent
> under the first minute for them to be stopped only after the minute has passed. Before the second
> minute passes, the 1000 packets would have already been forgotten. It would have made sense to
> look into past minutes to keep track of past flooders. Increasing the number of data points would
> have been more punishing towards flooding clients. The formula that would have been respected is
> `packets received in the last min(d, t) < p * min(d, ceil(t)) packets` where `t` is the fractional
> amount of `<time-unit>`s passed since Kea has started. However, since it is possible, with the
> implementation that is presented in the previous section, to look exactly one minute in the past
> for each packet, the 1000-packet flooders are efficiently stopped at the 20th packet.
## Lease Limiting Implementation
This section addresses the case of lease limiting being persistent-critical where leases awarded
prior to Kea startup, and also prior to configuring Kea with the limits hook library, need to be
taken into account in order to provide precise limiting functionality.
For this reason, Kea needs to be able to lookup in the persistent lease storage - the number of
leases that were awarded to clients of the same class or subnet. Subnet IDs are already colocated
with lease data which makes limiting by subnet ID a low hanging fruit. The new challenge is in
storing client classes with lease data. A rather difficult precondition is that a packet may belong
to multiple client classes at the moment of lease assignment. To minimize changes done to the CSV
header and to the database schemas, the user context field could hold the list of assigned client
classes at the moment of allocation.
```json
{
"ISC": {
"client-classes": ["ALL", "KNOWN", "bar", "foo"],
"limits": {
"client-classes": [
{
"name": "foo",
"address-limit": 2,
"prefix-limit": 1
},
{
"name": "bar",
"address-limit": 4
}
],
"subnet": {
"id": 1,
"address-limit": 2,
"prefix-limit": 1
}
}
}
}
```
Expired leases should be excluded from the counting.
The general workflow for processing a packet that is relevant to lease limiting is the following.
1. On `lease[46]_select`, the client classes assigned to the packet along with the configured limits
are placed in the lease's user context in the format shown above.
> **_NOTE_**: The client classes will end up being stored persistently in the lease storage. The
> limits don't need to be stored in any persistent storage, they just use the user context as a
> temporary medium of communication between the premium hook library and core Kea until they are
> checked against the lease count. Not all the limits have to be written. For brevity, only the
> limits for the client classes assigned to the packet can be specified.
2. `LeaseMgr::addLease()` or `LeaseMgr::updateLeaseX()` gets called. The mutex at the lease manager
scope gets locked.
3. The number of non-expired leases for each client class and subnet ID is checked against their
respective lease limits.
> **_NOTE_**: For SQL databases, it is best to have before-triggers. This way, they can provide an
> accurate number of non-expired leases that doesn't suffer from race conditions. For memfile, under
> the protection of the lease manager mutex, a newly implemented
> `LeaseMgr::checkLeaseLimit(UserContext const&)` could be called to check the non-expired lease
> counts against the limits. Instead of checking against the expiration time, which cannot be
> efficiently cached, and thus would need full-scan round-trip calls to the lease storage, the lease
> state can be leveraged. This has already been done for the lease statistics tables.
4a. If any of the lease limits is surpassed, the packet is not honored and a message is logged
with some packet details, the criteria that identified it - client class or subnet ID and what limit
was reached. Processing stops here. Steps 4b, 5 and 6 don't apply.
4b. Conversely, if the lease counts are within limits, the `"limits"` map is removed from the user
context, and the insert or update is carried out.
5. Update the lease counts for all the client classes assigned to the honored packet and for its
subnet ID.
> **_NOTE_**: This will generally consist of increments of the lease count, or decrements in the
> case of a RELEASE message. SQL after-triggers on INSERT and UPDATE statements allow for atomic
> updates on both the lease table and the lease count tables. Memfile updates whatever storage was
> checked in step 3 and needs to worry less of race conditions since it benefits from the mutex.
6. The lease manager mutex is unlocked.
The workflow of lease reclamation is separate. It can result in the update of the lease with a
valid expiration time, or with the deletion of the lease. For the update, the workflow above for
`LeaseMgr::updateLeaseX()` covers it. For deletion, `LeaseMgr::deleteLease()` gets called which
should also decrement the lease count. In SQL, that could be done with a DELETE after-trigger.
In an HA lease update scenario, it's worth considering whether we want both peers to do the check.
We might be able to squeeze some performance by letting only one peer do the check. An additional
mechanism for detecting that the updates are coming from an HA peer would be needed.
For `leaseX-add` commands, there is little incentive to check the limits. They should not normally
have the limits inserted in the user context. It should be a good workaround that should enable
users to do so, if they so wish. This workaround could be documented.
### Lease Limiting with a SQL Backend
Additional tables hold a lease count indexed by client class assigned to the packet in the moment of
allocation or by the subnet ID. Before and after-triggers on the lease table update these secondary
tables on INSERT, UPDATE and DELETE. Selecting is done in before-triggers that have not been
sketched for brevity.
See [Appendix A. SQL triggers for updating a secondary table holding lease count](#appendix-a-sql-triggers-for-updating-a-secondary-table-holding-lease-count).
Alternatively, the `lease[46]_stat` tables could be reused in lieu of `lease[46]_count_by_subnet_id`.
It holds the lease state on top of the other two columns. `lease[46]_stat_by_client_class` tables
would still exist, but would follow the same pattern of holding the lease state. It could be that
the additional state column simplifies the logic inside the triggers.
See [Appendix B. SQL triggers for updating a secondary table holding lease count and state](#appendix-b-sql-triggers-for-updating-a-secondary-table-holding-lease-count-and-state).
#### ACID compliance of triggers
The (INSERT/UPDATE/DELETE + after-trigger) aggregates are ACID compliant as the MySQL and
PostgreSQL documentations state, see below. Because of this, the lease table and the lease count
tables are in sync and always provide a consistent view of the data they hold.
https://dev.mysql.com/doc/refman/8.0/en/trigger-syntax.html
> For transactional tables, failure of a statement should cause rollback of all changes performed by
> the statement. Failure of a trigger causes the statement to fail, so trigger failure also causes
> rollback. For nontransactional tables, such rollback cannot be done, so although the statement
> fails, any changes performed prior to the point of the error remain in effect.
InnoDB tables are transactional tables by default. Autocommit needs to be left enabled, which is
also by default in InnoDB, and also already a requirement for the statistics triggers to work
correctly.
---
https://www.postgresql.org/docs/current/trigger-definition.html#TRIGGER-DEFINITION
> The execution of an AFTER trigger can be deferred to the end of the transaction, rather than the
> end of the statement, if it was defined as a constraint trigger. In all cases, a trigger is
> executed as part of the same transaction as the statement that triggered it, so if either the
> statement or the trigger causes an error, the effects of both will be rolled back.
---
The before-triggers have one or multiple SELECT statements that need the updated number of leases up
until the point that the INSERT or UPDATE actions that the triggers precede, complete. In other
words, dirty reads have to be avoided. This is done by using proper isolation level in the database
which should be `REPEATABLE READ` in this case, meaning any selected rows are locked until the
transaction ends.
Fortunately, MySQL uses the **REPEATABLE READ** isolation level by default.
https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html#isolevel_repeatable-read
> REPEATABLE READ
>
> This is the default isolation level for InnoDB. Consistent reads within the same transaction read
> the snapshot established by the > first read. This means that if you issue several plain
> (nonlocking) SELECT statements within the same transaction, these SELECT statements are consistent
> also with respect to each other. See Section 15.7.2.3, “Consistent Nonlocking Reads”.
---
PostgreSQL, however, uses the looser `READ COMMITTED` by default.
https://www.postgresql.org/docs/current/transaction-iso.html#id-1.5.12.5.11.3
> Read Committed is the default isolation level in PostgreSQL. When a transaction uses this
> isolation level, a SELECT query (without a FOR UPDATE/SHARE clause) sees only data committed
> before the query began; it never sees either uncommitted data or changes committed during query
> execution by concurrent transactions. In effect, a SELECT query sees a snapshot of the database as
> of the instant the query begins to run. However, SELECT does see the effects of previous updates
> executed within its own transaction, even though they are not yet committed. Also note that two
> successive SELECT commands can see different data, even though they are within a single
> transaction, if other transactions commit changes after the first SELECT starts and before the
> second SELECT starts.
> The Repeatable Read isolation level only sees data committed before the transaction began; it
> never sees either uncommitted data or changes committed during transaction execution by concurrent
> transactions. (However, the query does see the effects of previous updates executed within its own
> transaction, even though they are not yet committed.) This is a stronger guarantee than is
> required by the SQL standard for this isolation level, and prevents all of the phenomena described
> in Table 13.1 except for serialization anomalies. As mentioned above, this is specifically allowed
> by the standard, which only describes the minimum protections each isolation level must provide.
It does seem like `SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;` is required to make the limit
check foolproof. This command is set per transaction. This might mean that we need explicit
`START TRANSACTION`, `COMMIT` statements, maybe through the use of `PgSqlTransaction`, added to
all actions that are done on the PostgreSQL lease table.
---
### Lease Limiting with a Memfile Backend
If `multi_index_container` is smart enough to have an index that returns the number of valid leases
by client class or subnet ID in O(1) time, we can use that. See [the alternative solution for
memfile further below](#x-alternative-idea-for-lease-limiting-with-a-memfile-backend) for an attempt
at this that is far less efficient.
In absence of that, additional maps could be implemented in memory to provide the lease count as
`std::unordered_map<SubnetID, unsigned int>` and `std::unordered_map<ClientClass, unsigned int>`
respectively. They are updated on the `addLease`, `updateLease4`, `updateLease6`, `deleteLease`
methods of `LeaseMgr` which are all protected by a global mutex. Only leases with state 0 are
added in the maps.
Lease syncing for HA also goes through the methods above so these maps are also maintained in sync
between the peers.
Lease loading from a CSV file, however, does not go through the methods, so there needs to be a
separate step of updating these maps after the leases were loaded, before starting the DHCP service.
To keep an organized similarity between memfile and SQL backends, and to keep the logic for lease
limiting well isolated into the hook code, and to make this behavior hot-pluggable, `LeaseMgr` can
gain the ability to register and unregister functions to be called before and after deletion,
insertion, and update. Here's an example for the insert triggers:
```c++
class LeaseMgr {
registerBeforeInsertionTrigger(std::string const& key, std::function<bool(Lease)> f) {
before_insertion_triggers_.emplace(key, f);
}
unregisterBeforeInsertionTrigger(std::string const& key) {
before_insertion_triggers_.remove(key);
}
registerAfterInsertTrigger(std::string const& key, std::function<void(Lease)> f) {
before_insertion_triggers_.emplace(key, f);
}
unregisterAfterInsertTrigger(std::string const& key) {
after_insertion_triggers_.remove(key);
}
private:
std::unordered_map<std::string, std::function<bool(Lease)>> before_insertion_triggers_;
std::unordered_map<std::string, std::function<void(Lease)>> after_insertion_triggers_;
};
// They would be called only in the memfile implementation, or alternatively called in all
// implementation or a generic implementation of `addLeaseInternal()` and filtered by backend
// type in the load function, see further below. It is expected that any before or after insertion
// trigger for SQL backends are created through SQL instead of through C++ code.
bool
Memfile_LeaseMgr::addLeaseInternal(const Lease4Ptr& lease) {
for (std::function<bool(Lease)> f : before_insertion_triggers_) {
if (!f(lease)) {
return false;
}
}
<body>
for (std::function<void(Lease)> f : after_insertion_triggers_) {
f(lease);
}
}
// They would be registered on hook load and unregistered on hook unload.
int
load(isc::hooks::LibraryHandle& handle) {
if (LeaseMgrFactory::instance().getType() == "memfile") {
LeaseMgrFactory::instance().registerBeforeInsertionTrigger("LEASE_LIMIT", [](Lease4Ptr& lease) {
bool result(false);
if (lease.checkLeaseCount()) {
result = true;
}
lease.removeLimitDataFromUserContext();
return result;
});
}
return 0;
}
int
unload(isc::hooks::LibraryHandle& handle) {
LeaseMgrFactory::instance().unregisterBeforeInsertionTrigger("LEASE_LIMITS");
return 0;
}
```
### Avoiding the performance impact that features have on lease allocation
It's possible that the triggers will incur a non-negligible performance impact on lease allocation
for administrators who are not actively using lease limiting.While the memfile triggers can be
promptly registered and unregistered, SQL triggers are usually static and part of the versioned
schema. In the lease limiting case, the extra cost would consist of increments and decrements done
in secondary tables, as well as selects done on these tables as part of the limit check.
The more costly version of these updates could be used only if the lease limiting hook library is
loaded. Kea could create the triggers dynamically at the moment the hook library is loaded. Or it
could `SET @@GLOBAL.lease_limiting = ON;` which could be checked inside the triggers. Once created
or global variable set, these would not be undone on hook library unload or ever. Only an explicit
delete from the database could undo it. The reason is if someone has used the limits hook library in
the past, there is a chance they might want to do it again in the future. If the triggers or the
global variable did not exist prior, a recount would also be needed for the secondary tables. To be
considered if the minor performance benefit is worth the inconvenience of recounting and the
complexity of this approach. The selects mentioned in the previous paragraph would only be done if
there are any limits configured. No limits would reduce the before insert triggers to just some user
context parsing.
Idea could also be applied to lease statistics which also has an overhead on lease allocation,
although it would first need a knob to enable/disable statistics in the first place.
### The Case for a Preemptive Lease Limit Check
On top of the lease limit check that is tightly coupled with the insertion or update of the lease, and not
excluding it, there could be, for performance reasons, another preemptive check that happens sooner.
The place where this check could take place, on client classes at least, depends on how advanced the class
evaluation process needs to be. The preemptive check would, ideally happen in a hook callout registered by
the limits library. The performance impact of such a preemptive check is also to be considered. If the
measured cost is too high, it shouldn't be done. The performance gain itself for preventing a packet from
being further processed, also depends on how further along in the processing process is the check done.
The places where client classes are evaluated and re-evaluated, relative to hook points, are depicted in
the diagram below.
![classification](uploads/ec5944ae2378d900a04131e0748a6f22/classification.png)
On the hook point that is considered right, Kea looks up how many leases are allocated for each
configured limit that has a client class in common with the ones assigned to the packet.
If the limit has been reached for any of them, further checking of limits is abandoned and the
packet is not honored.
Preemptive limiting by subnet ID can be done as early as `subnet[46]_select` and not earlier, there is no
ambiguity there, except with regard to whether the performance gain is worth the overhead.
![image](uploads/298c8d438788df377b51759544bea54c/image.png)
# Appendices
## Appendix A. SQL triggers for updating a secondary table holding lease count
```sql
-- Create tables that contain the number of leases. --
CREATE TABLE lease4_count_by_client_class (
client_class VARCHAR(512) NOT NULL PRIMARY KEY,
leases INT UNSIGNED NOT NULL
) ENGINE = InnoDB;
CREATE TABLE lease6_count_by_client_class (
client_class VARCHAR(512) NOT NULL PRIMARY KEY,
leases INT UNSIGNED NOT NULL
) ENGINE = InnoDB;
CREATE TABLE lease4_count_by_subnet_id (
subnet_id INT UNSIGNED NOT NULL PRIMARY KEY,
leases INT UNSIGNED NOT NULL
) ENGINE = InnoDB;
CREATE TABLE lease6_count_by_subnet_id (
subnet_id INT UNSIGNED NOT NULL PRIMARY KEY,
leases INT UNSIGNED NOT NULL
) ENGINE = InnoDB;
-- Triggers --
-- The insert trigger for v4. Can be extrapolated for v6.
DELIMITER $$
CREATE TRIGGER trigger_lease_count4_insert AFTER INSERT ON lease4 FOR EACH ROW BEGIN
-- Update lease counts by subnet ID.
IF NEW.state = 2 THEN
-- Decrement the lease count if the record exists.
UPDATE lease4_count_by_subnet_id SET leases = leases - 1
WHERE subnet_id = NEW.subnet_id;
ELSE
-- Upsert to increment the lease count.
UPDATE lease4_count_by_subnet_id SET leases = leases + 1
WHERE subnet_id = NEW.subnet_id;
IF ROW_COUNT() <= 0 THEN
INSERT INTO lease4_count_by_subnet_id VALUES (subnet_id, 1);
END IF;
END IF;
DECLARE client_classes VARCHAR(1024);
DECLARE comma_count INT;
DECLARE i INT;
SET client_classes = JSON_EXTRACT(NEW.user_context, '$.ISC.client-classes');
SET comma_count = LENGTH(client_classes) - LENGTH(REPLACE(client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(client_classes, ',', i), ',', -1)
IF NEW.state = 2 THEN
-- Decrement the lease count if the record exists.
UPDATE lease4_count_by_client_class SET leases = leases - 1
WHERE client_class = client_class;
ELSE
-- Upsert to increment the lease count.
UPDATE lease4_count_by_client_class SET leases = leases + 1
WHERE client_class = client_class;
IF ROW_COUNT() <= 0 THEN
INSERT INTO lease4_count_by_client_class VALUES (client_class, 1);
END IF;
END IF;
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
-- The update trigger for v4. Same as the insert trigger except we only update the lease counts if
-- state has changed and we also have to account for changes in subnet IDs and client classes.
-- Can be extrapolated for v6.
DELIMITER $$
CREATE TRIGGER trigger_lease_count4_update AFTER UPDATE ON lease4 FOR EACH ROW BEGIN
DECLARE old_client_classes VARCHAR(1024);
DECLARE new_client_classes VARCHAR(1024);
SET old_client_classes = JSON_EXTRACT(OLD.user_context, '$.ISC.client-classes');
SET new_client_classes = JSON_EXTRACT(NEW.user_context, '$.ISC.client-classes');
IF OLD.state == NEW.state AND NEW.state = 0 THEN
-- If a non-expired lease changed its subnet ID, update lease counts.
IF OLD.subnet_id != NEW.subnet_id THEN
UPDATE lease4_count_by_subnet_id SET leases = leases - 1
WHERE subnet_id = OLD.subnet_id;
UPDATE lease4_count_by_subnet_id SET leases = leases + 1
WHERE subnet_id = NEW.subnet_id;
IF ROW_COUNT() <= 0 THEN
INSERT INTO lease4_count_by_subnet_id VALUES (NEW.subnet_id, 1);
END IF;
END IF;
-- If a non-expired lease added a client class, increment the lease count for the new class.
DECLARE comma_count INT;
DECLARE i INT;
SET comma_count = LENGTH(new_client_classes) - LENGTH(REPLACE(new_client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(new_client_classes, ',', i), ',', -1)
IF old_client_classes NOT LIKE CONCAT('%,', client_class, ',%') THEN
UPDATE lease4_count_by_client_class SET leases = leases + 1
WHERE client_class = client_class;
END IF;
SET i = i + 1;
END WHILE label;
-- If a non-expired lease removed a client class, decrement the lease count for the new class.
DECLARE comma_count INT;
DECLARE i INT;
SET comma_count = LENGTH(old_client_classes) - LENGTH(REPLACE(old_client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(old_client_classes, ',', i), ',', -1)
IF new_client_classes NOT LIKE CONCAT('%,', client_class, ',%') THEN
UPDATE lease4_count_by_client_class SET leases = leases - 1
WHERE client_class = client_class;
END IF;
SET i = i + 1;
END WHILE label;
ELSE
-- Update lease count by subnet ID.
IF OLD.state = 0 THEN
-- leased -> expired or declined
-- Decrement the lease count if the record exists. Use the old subnet ID because that's
-- the one that had been incremented on an insert or on a previous update. If the subnet
-- ID changed at the same time, no change needs to happen for the new subnet ID, because
-- it had not been incremented in the first place for the new subnet ID.
UPDATE lease4_count_by_subnet_id SET leases = leases - 1
WHERE subnet_id = OLD.subnet_id;
ELIF NEW.state = 0 THEN
-- expired or declined -> leased
-- Upsert to increment the lease count. If the subnet ID changed at the same time, no
-- change needs to happen for the old subnet ID, because it had not been incremented in
-- the first place for the old subnet ID.
UPDATE lease4_count_by_subnet_id SET leases = leases + 1
WHERE subnet_id = NEW.subnet_id;
IF ROW_COUNT() <= 0 THEN
INSERT INTO lease4_count_by_subnet_id VALUES (NEW.subnet_id, 1);
END IF;
END IF;
DECLARE comma_count INT;
DECLARE i INT;
SET comma_count = LENGTH(new_client_classes) - LENGTH(REPLACE(new_client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(new_client_classes, ',', i), ',', -1)
IF OLD.state = 0 THEN
-- leased -> expired or declined
-- Decrement the lease count if the record exists.
UPDATE lease4_count_by_client_class SET leases = leases - 1
WHERE client_class = client_class;
ELIF NEW.state = 0 THEN
-- expired or declined -> leased
-- Upsert to increment the lease count.
UPDATE lease4_count_by_client_class SET leases = leases + 1
WHERE client_class = client_class;
IF ROW_COUNT() <= 0 THEN
INSERT INTO lease4_count_by_client_class VALUES (client_class, 1);
END IF;
END IF;
SET i = i + 1;
END WHILE label;
END IF;
END $$
DELIMITER ;
-- The delete trigger for v4. Can be extrapolated for v6.
DELIMITER $$
CREATE TRIGGER trigger_lease_count4_delete AFTER DELETE ON lease4 FOR EACH ROW BEGIN
UPDATE lease4_count_by_subnet_id SET leases = leases - 1
WHERE subnet_id = OLD.subnet_id;
DECLARE old_client_classes VARCHAR(1024);
DECLARE new_client_classes VARCHAR(1024);
DECLARE comma_count INT;
DECLARE i INT;
SET client_classes = JSON_EXTRACT(OLD.user_context, '$.ISC.client-classes');
SET comma_count = LENGTH(client_classes) - LENGTH(REPLACE(client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(client_classes, ',', i), ',', -1)
-- Decrement the lease count if the record exists.
UPDATE lease4_count_by_client_class SET leases = leases - 1
WHERE client_class = client_class;
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
-- This is how the lease count is checked. These queries are not used freely, but as part of BEFORE
-- triggers for INSERT and UPDATE statements.
SELECT leases FROM lease4_stat WHERE subnet_id = ?;
SELECT leases FROM lease4_count_by_client_class WHERE client_class = ?;
```
## Appendix B. SQL triggers for updating a secondary table holding lease count and state
```sql
-- Add client_classes column. Needed by triggers. --
-- Create tables that contain the number of leases. --
CREATE TABLE lease4_stat_by_client_class (
client_class VARCHAR(512) NOT NULL,
state INT UNSIGNED NOT NULL,
leases INT UNSIGNED NOT NULL,
PRIMARY KEY (client_class, state)
) ENGINE = InnoDB;
CREATE TABLE lease6_stat_by_client_class (
client_class VARCHAR(512) NOT NULL,
state INT UNSIGNED NOT NULL,
leases INT UNSIGNED NOT NULL,
PRIMARY KEY (client_class, state)
) ENGINE = InnoDB;
-- The insert trigger for v4. Can be extrapolated for v6.
DELIMITER $$
CREATE TRIGGER trigger_lease_stat4_insert AFTER INSERT ON lease4 FOR EACH ROW BEGIN
DECLARE client_classes VARCHAR(1024);
DECLARE comma_count INT;
DECLARE i INT;
SET client_classes = JSON_EXTRACT(NEW.user_context, '$.ISC.client-classes');
SET comma_count = LENGTH(client_classes) - LENGTH(REPLACE(client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(client_classes, ',', i), ',', -1);
-- Check both states to be consistent with lease4_stat? Only state 0 needs to be updated in reality.
IF NEW.state = 0 OR NEW.state = 1 THEN
-- Upsert to increment the lease count.
UPDATE lease4_count_by_client_class SET leases = leases + 1
WHERE state = NEW.state AND client_class = client_class;
IF ROW_COUNT() <= 0 THEN
INSERT INTO lease4_count_by_client_class VALUES (client_class, NEW.state, 1);
END IF;
END IF;
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
-- The update trigger for v4. Same as the insert trigger except we only update the lease counts if
-- state has changed and we also have to account for changes in subnet IDs and client classes.
-- Can be extrapolated for v6.
DELIMITER $$
CREATE TRIGGER trigger_lease_count4_update AFTER UPDATE ON lease4 FOR EACH ROW BEGIN
IF OLD.state != NEW.state THEN
DECLARE client_classes VARCHAR(1024);
DECLARE comma_count INT;
DECLARE i INT;
IF OLD.state = 0 OR OLD.state = 1 THEN
SET client_classes = JSON_EXTRACT(OLD.user_context, '$.ISC.client-classes');
SET comma_count = LENGTH(new_client_classes) - LENGTH(REPLACE(client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(client_classes, ',', i), ',', -1)
-- Decrement the lease count if the record exists.
UPDATE lease4_count_by_client_class SET leases = leases - 1
WHERE state = OLD.state AND client_class = client_class;
SET i = i + 1;
END WHILE label;
ELIF NEW.state = 0 OR NEW.state = 1 THEN
SET client_classes = JSON_EXTRACT(NEW.user_context, '$.ISC.client-classes');
SET comma_count = LENGTH(new_client_classes) - LENGTH(REPLACE(new_client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(client_classes, ',', i), ',', -1)
-- Upsert to increment the lease count.
UPDATE lease4_count_by_client_class SET leases = leases + 1
WHERE state = NEW.state AND client_class = client_class;
IF ROW_COUNT() <= 0 THEN
INSERT INTO lease4_count_by_client_class VALUES (client_class, NEW.state, 1);
END IF;
SET i = i + 1;
END WHILE label;
END IF;
END IF;
END $$
DELIMITER ;
-- The delete trigger for v4. Can be extrapolated for v6.
DELIMITER $$
CREATE TRIGGER trigger_lease_count4_delete AFTER DELETE ON lease4 FOR EACH ROW BEGIN
DECLARE client_classes VARCHAR(1024);
DECLARE comma_count INT;
DECLARE i INT;
SET client_classes = JSON_EXTRACT(OLD.user_context, '$.ISC.client-classes');
SET comma_count = LENGTH(client_classes) - LENGTH(REPLACE(client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(client_classes, ',', i), ',', -1)
-- Decrement the lease count if the record exists.
UPDATE lease4_count_by_client_class SET leases = leases - 1
WHERE state = OLD.state AND client_class = client_class;
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
-- This is how the lease count is checked. These queries are not used freely, but as part of BEFORE
-- triggers for INSERT and UPDATE statements.
SELECT leases FROM lease4_stat WHERE subnet_id = ? AND state = 0;
SELECT leases FROM lease4_count_by_client_class WHERE client_class = ? AND state = 0;
```
# Obsolete ideas
### :x: Alternative Idea for Lease Limiting with a Memfile Backend
Getting the lease count for memfile might be achievable through `lower_bound` or `upper_bound` calls
on a `multi_index_container` index. For that to happen, the index needs to be sortable on all the
criteria we want to filter by. The lease state, expiration time, and subnet IDs are easily sortable.
For client classes, filtering by the contents at a certain location of a user context might be
difficult. For this reason, we could store the client classes as `ClientClasses` or a different
structure in the `Lease` class. We would call the `lower_bound` or `upper_bound` on a
`ClientClasses`, or similar structure, that would have the `operator<` defined as an inclusion
operator. If all the client classes in `this` container (a single client class for our cause) belong
to the `other` container, then `*this < other`.
```c++
bool ClientClasses::operator<(ClientClasses const& other) const {
for (ClientClass i : container_) {
if (other.contains(i)) {
return true;
}
}
return false;
}
```
The indexes would therefore be composite keys containing subnet ID + lease state + expiration time,
or client classes + lease state + expiration time respectively.
```c++
boost::multi_index::ordered_non_unique<boost::multi_index::tag<NonExpiredSubnetIdIndexTag>,
// This is a composite index that will be used to search for non-expired leases that
// have a given subnet ID.
boost::multi_index::composite_key<
Lease6,
// Subnet ID
boost::multi_index::member<Lease, isc::dhcp::SubnetID, &Lease::subnet_id_>,
// The boolean value specifying if lease is reclaimed or not
boost::multi_index::const_mem_fun<Lease, bool, &Lease::stateExpiredReclaimed>,
// Lease expiration time
boost::multi_index::const_mem_fun<Lease, int64_t, &Lease::getExpirationTime>
>
>
boost::multi_index::ordered_non_unique<boost::multi_index::tag<NonExpiredClientClassIndexTag>,
// This is a composite index that will be used to search for non-expired leases that
// have a given client class.
boost::multi_index::composite_key<
Lease6,
// Client classes
boost::multi_index::member<Lease, ClientClasses, &Lease::client_classes_>,
// The boolean value specifying if lease is reclaimed or not
boost::multi_index::const_mem_fun<Lease, bool, &Lease::stateExpiredReclaimed>,
// Lease expiration time
boost::multi_index::const_mem_fun<Lease, int64_t, &Lease::getExpirationTime>
>
>
```
All the leases could then be filtered by e.g. `boost::make_tuple(1, false, time(NULL))`, or
`boost::make_tuple(ClientClasses("foo"), false, time(NULL))` respectively. The size would be
retrieved
```
auto comparison_tuple(boost::make_tuple(ClientClasses("foo"), false, time(NULL)));
Lease6StorageClientClassIndex::const_iterator lower_bound(
storage6_.get<NonExpiredClientClassIndexTag>().lower_bound(comparison_tuple));
Lease6StorageClientClassIndex::const_iterator upper_bound(
storage6_.get<NonExpiredClientClassIndexTag>().upper_bound(comparison_tuple));
for (auto it = lower_bound; it != upper_bound; ++it) {
consume(*it);
}
```
### :x: Alternative Idea 1 for Lease Limiting with a SQL Backend. SELECT COUNT() with LIKE clause
Updating has near-zero extra overhead since it is done with the usual update. Retrieving the lease
count per class is one `SELECT` statement per class, each involving `COUNT()` and `LIKE` string
comparison, so quite computationally intensive. To ensure exact matching as part of the `LIKE`
clause, the values are in CSV format with an extra leading comma and an extra trailing comma.
```sql
-- First lease has near-zero overhead.
INSERT INTO lease[46] (address, client_classes) VALUES (?, ',ALL,gold,central_zone,paying_customer,');
-- Updating a lease has near-zero overhead.
UPDATE lease[46] SET client_classes = ',ALL,gold,central_zone,paying_customer,' WHERE address = ?;
-- Reclamation has near-zero overhead.
DELETE FROM lease[46] WHERE address = ?;
-- Retrieving the current lease count by class is expensive. This example assumes all of the
-- following classes are lease limited.
SELECT COUNT(*) FROM lease[46] WHERE client_classes LIKE '%,ALL,%' AND expire < NOW();
SELECT COUNT(*) FROM lease[46] WHERE client_classes LIKE '%,gold,%' AND expire < NOW();
SELECT COUNT(*) FROM lease[46] WHERE client_classes LIKE '%,central_zone,%' AND expire < NOW();
SELECT COUNT(*) FROM lease[46] WHERE client_classes LIKE '%,paying_customer,%' AND expire < NOW();
```
:white_check_mark: Works with HA out of the box.
:white_check_mark: To reduce the number of database roundtrips, the INSERT leaseX and UPDATE leaseX
statements could be prefixed by the SELECT statements above inside a function or procedure.
:warning: Requires a shift of the lease allocation process to become transactional, but it's
something that we can't get away from anyway.
### :x: Alternative Idea 2 for Lease Limiting with a SQL Backend. Inserts and updates with selects as subqueries
This is a spin-off from the previous idea with the change that the SELECT statements are incorporated as subqueries in the mutation statements, which themselves are changed, at least partially, from INSERT and UPDATE to `REPLACE INTO`. A `CASE WHEN` clause is used on the `expire` column to conditionally update the row only when the limit is not surpassed. `old_expire` is used as value when it is surpassed which makes the update not happen according to the docs: https://dev.mysql.com/doc/refman/8.0/en/update.html#idm45389242659712
> If you set a column to the value it currently has, MySQL notices this and does not update it.
MySQL statements would look like this:
```sql
-- Can be extrapolated for lease6. The variables preceded by dollar $ are input.
INSERT INTO lease4 SELECT $address, $hwaddr, $client_id, $valid_lifetime, $expire, $subnet_id, $fqdn_fwd, $fqdn_rev, $hostname, $state, $user_context WHERE (
(SELECT COUNT(*) AS count FROM lease4 WHERE client_classes LIKE '%,ALL,%' AND expire < NOW()) UNION ALL
(SELECT COUNT(*) AS count FROM lease4 WHERE client_classes LIKE '%,gold,%' AND expire < NOW()) UNION ALL
(SELECT COUNT(*) AS count FROM lease4 WHERE client_classes LIKE '%,central_zone,%' AND expire < NOW()) UNION ALL
(SELECT COUNT(*) AS count FROM lease4 WHERE client_classes LIKE '%,paying_customer,%' AND expire < NOW())
ORDER BY count ASC LIMIT 1
) < $limit
-- Same WHERE clause in the UPDATE
UPDATE lease[46] SET ...
WHERE address = ? AND expire = ? AND (
(SELECT COUNT(*) AS count FROM lease[46] WHERE client_classes LIKE '%,ALL,%' AND expire < NOW()) UNION ALL
(SELECT COUNT(*) AS count FROM lease[46] WHERE client_classes LIKE '%,gold,%' AND expire < NOW()) UNION ALL
(SELECT COUNT(*) AS count FROM lease[46] WHERE client_classes LIKE '%,central_zone,%' AND expire < NOW()) UNION ALL
(SELECT COUNT(*) AS count FROM lease[46] WHERE client_classes LIKE '%,paying_customer,%' AND expire < NOW()) UNION ALL
ORDER BY count ASC LIMIT 1
) < $limit
END;
-- Reclamation is the same.
DELETE FROM lease[46] WHERE address = ?;
```
Postgres should be similar.
:warning: Due to the the varying number of client classes in each query, preparing statements up front is a less tractable task than with other statements. The structure of prepared statements requires one for each number of client classes inside the subquery. There could be prepared statements with 0-4 classes or similar heuristical numbers from the server startup and just hope nobody uses more than that number of classes per packet. Statements could also be prepared on the fly on first use. Statements could also be executed raw. It's a performance optimization problem that is best tested at implementation time.
:warning: This does not fit the workflow above. Point 3 is skipped entirely and the mutexes in point 4 are not required.
:white_check_mark: Works with HA out of the box.
:white_check_mark: No transactions needed
### :x: Alternative Idea 3 for Lease Limiting with a SQL Backend. Triggers to keep a secondary table indexed by client class as key
Have a table that matches classes to expire times. Addresses are also added, but only to treat
duplicate `<class, expire>` pairs as separate. Lease updates have significant overhead of deleting
extra rows beforehand. The cardinality of SELECT statements is the same and the `LIKE` clause on
non-keys is replaced with equality on keys, so they should be faster at the expense of significant
updating cost. Worth considering here is the idea mentioned before that faster SELECT statements
result in a faster packet processing on average.
```sql
CREATE TABLE client_classes4 (
client_class TEXT NOT NULL,
expire TIMESTAMP NOT NULL,
address INT UNSIGNED NOT NULL,
PRIMARY KEY (client_class, expire, address)
) ENGINE = InnoDB;
CREATE TABLE client_classes6 (
client_class TEXT NOT NULL,
expire TIMESTAMP NOT NULL,
address VARCHAR(39) NOT NULL,
PRIMARY KEY (client_class, expire, address)
) ENGINE = InnoDB;
DELIMITER $$
CREATE TRIGGER trigger_client_classes4_insert AFTER INSERT ON lease4 FOR EACH ROW BEGIN
DECLARE comma_count INT;
DECLARE i INT;
SET comma_count = LENGTH(NEW.client_classes) - LENGTH(REPLACE(NEW.client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(NEW.client_classes, ',', i), ',', -1)
INSERT INTO client_classes4 (client_class, expire, address) VALUES (client_class, NEW.expire, NEW.address);
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
DELIMITER $$
CREATE TRIGGER client_classes6_insert AFTER INSERT ON lease6 FOR EACH ROW BEGIN
DECLARE comma_count INT;
DECLARE i INT;
SET comma_count = LENGTH(NEW.client_classes) - LENGTH(REPLACE(NEW.client_classes, ',', ''));
SET i = 1;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(NEW.client_classes, ',', i), ',', -1)
INSERT INTO client_classes6 (client_class, expire, address) VALUES (client_class, NEW.expire, NEW.address);
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
DELIMITER $$
CREATE TRIGGER trigger_client_classes4_update AFTER UPDATE ON lease4 FOR EACH ROW BEGIN
DECLARE comma_count INT;
DECLARE i INT;
SET comma_count = LENGTH(NEW.client_classes) - LENGTH(REPLACE(NEW.client_classes, ',', ''));
SET i = 1;
DELETE FROM client_classes4 WHERE address = OLD.address;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(NEW.client_classes, ',', i), ',', -1)
INSERT INTO client_classes4 (client_class, expire, address) VALUES (client_class, NEW.expire, NEW.address);
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
DELIMITER $$
CREATE TRIGGER trigger_client_classes6_update AFTER UPDATE ON lease6 FOR EACH ROW BEGIN
DECLARE comma_count INT;
DECLARE i INT;
SET comma_count = LENGTH(NEW.client_classes) - LENGTH(REPLACE(NEW.client_classes, ',', ''));
SET i = 1;
DELETE FROM client_classes6 WHERE address = OLD.address;
label: WHILE i < comma_count DO
SET client_class = SUBSTRING_INDEX(SUBSTRING_INDEX(NEW.client_classes, ',', i), ',', -1)
INSERT INTO client_classes6 (client_class, expire, address) VALUES (client_class, NEW.expire, NEW.address);
SET i = i + 1;
END WHILE label;
END $$
DELIMITER ;
DELIMITER $$
CREATE TRIGGER trigger_client_classes4_delete AFTER DELETE ON lease4 FOR EACH ROW BEGIN
DELETE FROM client_classes4 WHERE address = OLD.address;
END $$
DELIMITER ;
DELIMITER $$
CREATE TRIGGER trigger_client_classes6_delete AFTER DELETE ON lease6 FOR EACH ROW BEGIN
DELETE FROM client_classes6 WHERE address = OLD.address;
END $$
DELIMITER ;
-- First lease has O(n) overhead where n is the number of client classes.
INSERT INTO lease[46] (address, client_classes) VALUES (?, ',ALL,gold,central_zone,paying_customer,');
-- Updating a lease has O(n) overhead. One of the statements is a DELETE which is known to sometimes
-- mess with the usual workflow of databases.
UPDATE lease[46] SET client_classes = ',ALL,gold,central_zone,paying_customer,' WHERE address = ?;
-- Reclamation has an overhead of an extra DELETE statement.
DELETE FROM lease[46] WHERE address = ?;
-- Retrieving the current lease count by class is more efficient because of the string equality
-- comparison on keys rather than LIKE clause on non-keys. This example assumes all of the following
-- classes are lease limited.
SELECT COUNT(*) FROM client_classes[46] WHERE client_class = 'ALL' AND expire < NOW();
SELECT COUNT(*) FROM client_classes[46] WHERE client_class = 'gold' AND expire < NOW();
SELECT COUNT(*) FROM client_classes[46] WHERE client_class = 'central_zone' AND expire < NOW();
SELECT COUNT(*) FROM client_classes[46] WHERE client_class = 'paying_customer' AND expire < NOW();
```
### :x: The Case For a Lease Limiting Cache
To alleviate the performance impact of database statements on client classes, a cache can be
implemented. `MemfileLeaseMgr` can be derived in order to reuse `storage4_` and `storage6_`
containers. Alternatively, a simpler `boost::multi_index_container` that keeps only client classes
and expire times can be created, and again maybe addresses too, to treat duplicate `<class, expire>`
pairs as separate entries.
The cache is pull-through.
1. Packet is received.
2. For any client class assigned to the packet that is also lease limited, check if the class is in
the cache.
3. If it is in the cache, take the lease count directly from the cache.
4. If it is not in the cache, get all the leases under the respective class from the database. After
retrieval, fill the cache for respective class. This cache update only happens one time per class.
5. After the lease was assigned and updated in the database, update the cache. This cache update
happens every time.
The cache needs to live in core Kea libraries because of the time proximity it needs to have to the
lease update, mentioned in the workflow at the beginning of this section, involving the addition of
mutexes or of a critical section.
It is guaranteed that in time, all client classes will be validated or in-sync with the database,
and so no expensive SELECT statements will be issued to the database. The cache is only invalidated,
only on hook reload i.e. reconfiguration.
:warning: The cache cannot be used with idea 2 of lease limiting above where the SELECT statements
are not separate but incorporated as subqueries into the UPDATE statement. The cache is meant to be
used with separate SELECT statements in an environment protected by mutexes and transactions.
:warning: Hot-standby HA also needs to invalidate this cache on failover.
:warning: Load-balancing HA probably cannot make use of this cache. If it did, it would
need to sync the cache with its peer which would probably make it more costly than benefitting.
### :x: The Case For Non-Persistent Lease Limiting
The inconvenience that presents itself if we don't take leases awarded prior to Kea startup into
consideration is the possibility of clients losing leases. The scenario is along the following
lines:
1. 2 leases from clients A and B classified as `"gold"` are in the lease backend.
2. Kea starts with a `"lease-limit": 4` assigned to client class `"gold"`.
3. Clients C, D, E, F classified as `"gold"` successfully get a lease.
4. When attempting to renew, clients A and B are denied a lease because limit has been reached.
5. Leases for clients A and B expire.
On top of that, another disadvantage is that the lease count temporarily exceeds the lease limit.
Few arguments in favor of the non-persistent approach:
* The explicit intent of the administrator, when lease limiting was configured, was to prevent
devices from getting leases. Whether it is A and B or E and F, and whether the clients had
connectivity before may not be of interest to the administrator. The intended message is the same,
probably use less devices or upgrade subscription.
* The limiting does catch up to the lease database in at most (most of the times significantly less
than) the maximum configured valid lifetime, assuming well behaved clients that take lifetimes into
consideration.
* Allowing leases for more clients can be easily achieved by increasing the limit, or classifying
packets more granularly.
* The lease count temporarily exceeding the lease limit is not an event which can be controlled at
client-level. It happens only as a result of the rare server-side event of reconfiguration.
* The implicit performance benefit is substantial.
# Comments
* In the section, "Action to Take on Limit Surpassing" you quote RFC -specified client behavior upon receipt of an UnspecFail. Keep in mind that there is no shortage of non-compliant clients in the world, and it is not behavior that we can rely on, whatsoever. (@tmark)
* In #4 under "Lease Limiting Implementation" you state: "One other note: if the `ALL` class is also considered, the mutexes might just as well be turned into a critical section." I'm assuming you mean that allowing limits to be specified on the ALL class is tantamount to creating a critical section. Configuration parsing should probably not allow limits to be placed on certain (if not all) built-in classes. I'm assuming you know this, but to be clear, limit checking must not introduce new critical sections, doing so would likely reduce MT performance to probably worse than ST. (@tmark)
* "Lease Limiting Implementation" - both ideas 1 and 2 use sub-selects to recount leases per class. If I'm not mistaken, each of these sub-selects are going to require full tables scans. On top of that each scan is a string search of column. Even if you indexed the client-classes column, that index would be far from efficient. We already use triggers to maintain the existing leaseX_stat tables. Seems to me we should expand on this. Those triggers already account for lease expiration, as changing the lease state requires updating the lease table and thus fires the appropriate trigger. I do not understand why you say "HA sync" is required, Changes due to HA updates cause the triggers to fire like any other lease change. If you want to look at the impact of full table scans of large lease tables, look back at the MySql performance testing before we changed the reclamation query to use indexing. Every time reclamation kicked in Kea virtually stopped. It should be pretty straight forward to setup some performance tests with just the schema and some canned data. Also, I assume you included counts of "ALL" just as an example, but of course counting these would be of no value. The limit triggers could be enabled/disabled via a session variable similar to CB audit-revision logic (SET @disable_audit = 1;). Lease managers could be extended to support turning such a value on/off, and when the limits hook loads it can turn it on. This minimizes impact to those not using the limits hook. We could also explore, making the limit counting portions of the schema something that has to be installed along with the hook. (@tmark)