Opened 5 years ago

Closed 5 years ago

Last modified 4 years ago

#3965 closed task (complete)

Extend Memfile Backend to support queries for expired leases

Reported by: marcin Owned by: marcin
Priority: high Milestone: Kea1.0-beta
Component: dhcp Version: git
Keywords: expiration Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DHCP Feature Depending on Ticket:
Estimated Difficulty: 0 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no

Description

See Design for the details.

Subtickets

Change History (8)

comment:1 Changed 5 years ago by marcin

  • Owner set to marcin
  • Status changed from new to accepted

comment:2 Changed 5 years ago by marcin

  • Owner changed from marcin to UnAssigned
  • Status changed from accepted to reviewing

I have extended the API of the LeaseMgr with new functions to retrieve expired leases and to delete expired-reclaimed leases. I also had extend the Lease structure to include the new 'state' field. This in turn required modifications to some of the existing unit test and the classes responsible for writing/reading leases from the lease files.

So, the change is quite extensive in terms of number of lines of code changed, but they are pretty straight forward changes.

Proposed ChangeLog entry:

XXX.	[func]		marcin
	Memfile lease database backend has been extended with new
	functions to obtain expired leases and to delete expired
	reclaimed leases.
	(Trac #3965, git abcd)

comment:3 Changed 5 years ago by tomek

  • Owner changed from UnAssigned to tomek

comment:4 follow-up: Changed 5 years ago by tomek

  • Owner changed from tomek to marcin

lease.h
Why do we need STATE_DEFAULT? I can imagine we have constants
designating each bit, with each bit having specific meaning,
like declined or expired-reclaimed. But what does the bit 0
mean? The default state is simply an absence of other bits.
It's shouldn't have a dedicated bit for itself.

If you find it useful to have a constant representing the default,
it should be 0, i.e. all special purpose bits set to 0.

Description of state_ field should explicitly mention the constant
names (STATE_* would do the trick).

There is Lease::stateExpiredReclaimed(), but there's no
Lease::stateDeclined(). It's ok if you don't want to add it
in this ticket. I can take care of it in one of decline tickets.

Since we touched Lease object already, we broke binary compatibility.
That's ok, but since the libs won't be compatible anyway, how about
doing couple clean-ups in this area? We have comments_ that doesn't
seem to be used anywhere. The same is true for fixed_ and ext_.
Do you think it would be ok to remove those fields? Even if we would
decide to use fixed_ field one day, conceptually it should be another
bit in the state_ field, not a separate field.

lease.cc
basicStatesToText() should print numeric value for unknown states.

statesToText() will also have to return complex states (i.e. states
with more than one bit set) one day. It's ok to just add a @todo for
this at this stage. I'd like the statesToText() implementation be
moved from the .h file to .cc.

lease_mgr.h
getExpiredLeases4 and getExpiredLease6() - those two methods should
be implemented as getLeases4InState(..., state) and
getLeases6InState(..., state). That way those calls could be directly
used in decline processing. And by any other future states we may
come up with. If you keep the code in the form it is implemented now,
we'll have to implement very similar calls for declined and any
other states we may define.

There's list-declined-addresses command planned already. It will use
those calls.

I was thinking about other things that could require using another bit
in the state_ field. One thing that came to my mind is port-sets.
Those leases would be odd enough to probably warrant an extra
designation. When doing sanity checks for port-sets, it would
be useful to have a method to return all port-set leases. Hence
another use case for generic approach.

deleteExpiredReclaimedLeases4 and deleteExpiredReclaimedLeases6()
The comment is basically the same as the previous one. Instead of
having methods specific for expired reclaimed, those methods should
be generic and take extra parameter for state. I can imagine
scenarios, where deleting all declined leases may be useful
(e.g. after receiving administrative command).

Do you think it would be useful for deleteExpiredReclaimedLeases{4,6}
to return the number of actual leases deleted? This is something
should be logged in, so returning the number would be useful.

Copyright year should be updated. (Note: it's silly that we're doing
this manually. Especially since BIND9 has a script to do it).

memfile_lease_storage.h
Please update the Lease4Storage and Lease6Storage. The list of
indexed there is outdated. Also, a paragraph explaining why tags
were introduced would be very helpful.

csv_lease_file6.cc
You removed the CSVLeaseFile6::validateHeader() method. That's ok.
But there's another piece of code that tried to read pre-0.9.1
files in readHWAddr(). As I understand the changes here, the
new state column is now mandatory and an attempt to load an old
lease will fail. Hence there's no need to keep the hwaddr-optional
logic there anymore.

memfile_lease_mgr_unittest.cc
If you agree with my suggestion, those tests need to be updated.
Fortunately, it's a mass replace ",1\n" => ",0\n"

Not really relevant to changes in this ticket, but can you remove
a @todo in line 877 (it's no longer applicable as the test seems
to be working just fine).

We need a unit-test that will check how the code handles earlier
lease files. I'm thinking about two unit-tests. One for 0.9
syntax (without hwaddr) and another one for 0.9.1 and 0.9.2 (with
hwaddr). Just a simple check that the code terminates with an
appropriately worded exception that upgrade is needed. It's a
matter of debate whether this piece of work belongs to this ticket
or the memfile upgrade script ticket. Personally, I think it would
better fit this ticket, as people may upgrade to latest master and
be surprised. On the other hand, I presume the the upgrade script
ticket will come in next, so the window of opportunity is small here.
In other words, I won't object if you want to push this piece
to the next ticket.

generic_lease_mgr_unittest.h
Unless you invented a time travel machine, I suggest updating the
copyright date. :)

generic_lease_mgr_unittest.cc
EXPECT_NO_THROW around getExpiredLeases{4,6} would be useful.
It's not strictly required (exception thrown will fail the test
anyway), but we have a convention to add that macro anyway.

testGetExpiredLeases{4,6} should add a sanity check that calculated

index is not out of bounds. Otherwise you can dereference a garbage.

(That's for line 1701).

A comment around line 1690 should explain what the 1000 means.
For the test to be objective, you should repeat the second call
again with 1000. Just by looking at the test, I got the first
impression that the order of leases returned depends on whether you
want all of them or just the first 1000.

In fact, I think testGetExpiredLeases4() should be split into
a number of small unit-tests. It's like 3 or 4 of them stacked
together.

All comments above also apply to testGetExpiredLeases6().


The code compiles and unit-tests pass on Ubuntu 15.04 x64.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by marcin

  • Owner changed from marcin to tomek

Replying to tomek:

lease.h
Why do we need STATE_DEFAULT? I can imagine we have constants
designating each bit, with each bit having specific meaning,
like declined or expired-reclaimed. But what does the bit 0
mean? The default state is simply an absence of other bits.
It's shouldn't have a dedicated bit for itself.

If you find it useful to have a constant representing the default,
it should be 0, i.e. all special purpose bits set to 0.

The default state which every "normal" lease is in is now marked as 0.

Description of state_ field should explicitly mention the constant
names (STATE_* would do the trick).

Added.

There is Lease::stateExpiredReclaimed(), but there's no
Lease::stateDeclined(). It's ok if you don't want to add it
in this ticket. I can take care of it in one of decline tickets.

I think it is a matter for a different ticket. It also relates to your point raised about the Memfile indexes and the LeaseMgr API which we have to discuss below.

Since we touched Lease object already, we broke binary compatibility.
That's ok, but since the libs won't be compatible anyway, how about
doing couple clean-ups in this area? We have comments_ that doesn't
seem to be used anywhere. The same is true for fixed_ and ext_.
Do you think it would be ok to remove those fields? Even if we would
decide to use fixed_ field one day, conceptually it should be another
bit in the state_ field, not a separate field.

Ok, I've done that.

lease.cc
basicStatesToText() should print numeric value for unknown states.

It does, although the unknown state is not really something that we are likely to hit.

statesToText() will also have to return complex states (i.e. states
with more than one bit set) one day. It's ok to just add a @todo for
this at this stage. I'd like the statesToText() implementation be
moved from the .h file to .cc.

It does, doesn't it?

lease_mgr.h
getExpiredLeases4 and getExpiredLease6() - those two methods should
be implemented as getLeases4InState(..., state) and
getLeases6InState(..., state). That way those calls could be directly
used in decline processing. And by any other future states we may
come up with. If you keep the code in the form it is implemented now,
we'll have to implement very similar calls for declined and any
other states we may define.

So this is problematic. The multi_index_container is a bit like SQL database but it is not that capable. At least not without adding some more complexity which is not a part of boost.

First of all, note that whether the lease is expired or not is a function of time, not the state. That's why the queries for expired leases can't just retrieve leases in a certain state (i.e. having a field state_ set to the desired value) but they have to find all leases for which expiration time is lower than the current time. At the same time, the leases must not have been reclaimed. Reclaimed leases are not returned as part of this call. You see how complex it is.

So, the composite index used to search for expired leases has two components: boolean (whether the lease is expired-reclaimed) and the time value. The specific order is also preserved so as we can retrieve leases that has been reclaimed or hasn't been reclaimed using the call to index.upper_bound. The same technique allows us to return leases ordered by the expiration time. If we wanted to use the "state" (uint32_t value) instead of the boolean value this causes trouble.

For the multi_index_container it is important that elements are ordered using a specific value. Ordering by the value of the uint32_t doesn't do any good because we may have leases in multiple states simultaneously. So the lease may be expired reclaimed but may also be in some different state which takes it way higher in the ordering (and effectively outside of the group of leases which are only "expired-reclaimed"). So the call to the index.upper_bound would actually exclude this lease from the results.

One way to achieve what you want is to create a lease index by expiration date (NOT a complex index). If you want expired and not reclaimed leases to be returned you use this index to gather all expired leases using this index. Then iterate over all returned leases and check whether they remain in the desired state or not. That would however result in a full scan of returned expired leases. I am on a fence.

As for the naming of the new functions I think there are some positive sides of having different functions serving different purposes. The point is that if you name the function getLeases4InState does it say that the lease is solely in this state or the lease may also be in other states? Also, when querying for expired leases ... they are not really in the "expired state" because there is no such state defined for the state_ field (and will never be). The meta-state "expired" is determined by the expiration time vs current state. So, I don't really no if this name is appropriate. I think that getExpiredLeases6 is better name. But, it is up for discussion.

We need to determine differences between the queries for decline and lease expiration. If the queries for declined leases are not going to be time-dependent we can't really combine them in a single function as you suggest.

There's list-declined-addresses command planned already. It will use
those calls.

I was thinking about other things that could require using another bit
in the state_ field. One thing that came to my mind is port-sets.
Those leases would be odd enough to probably warrant an extra
designation. When doing sanity checks for port-sets, it would
be useful to have a method to return all port-set leases. Hence
another use case for generic approach.

I think it makes sense to update LeaseMgr all at once. But, this is different use case than expired or declined leases. It requires to only check for leases which state is equal to something (or which bit is set to something) but doesn't depend on time and is not indexed as such. So, it would require a different method anyway. Perhaps another ticket.

deleteExpiredReclaimedLeases4 and deleteExpiredReclaimedLeases6()
The comment is basically the same as the previous one. Instead of
having methods specific for expired reclaimed, those methods should
be generic and take extra parameter for state. I can imagine
scenarios, where deleting all declined leases may be useful
(e.g. after receiving administrative command).

This suffers from similar issue like the previous function. It can still be done by full scan of leases returned relative to a given moment of time. Though, it would introduce some more complexity to the code.

Do you think it would be useful for deleteExpiredReclaimedLeases{4,6}
to return the number of actual leases deleted? This is something
should be logged in, so returning the number would be useful.

We're logging the number of leases deleted in the function itself.

Copyright year should be updated. (Note: it's silly that we're doing
this manually. Especially since BIND9 has a script to do it).

I didn't see it being outdated, though. :-)

memfile_lease_storage.h
Please update the Lease4Storage and Lease6Storage. The list of
indexed there is outdated. Also, a paragraph explaining why tags
were introduced would be very helpful.

Updated the list and added a paragraph as suggested.

csv_lease_file6.cc
You removed the CSVLeaseFile6::validateHeader() method. That's ok.
But there's another piece of code that tried to read pre-0.9.1
files in readHWAddr(). As I understand the changes here, the
new state column is now mandatory and an attempt to load an old
lease will fail. Hence there's no need to keep the hwaddr-optional
logic there anymore.

Removed.

memfile_lease_mgr_unittest.cc
If you agree with my suggestion, those tests need to be updated.
Fortunately, it's a mass replace ",1\n" => ",0\n"

I had to be a bit careful with those changes but yes, I had to do them.

Not really relevant to changes in this ticket, but can you remove
a @todo in line 877 (it's no longer applicable as the test seems
to be working just fine).

Removed.

We need a unit-test that will check how the code handles earlier
lease files. I'm thinking about two unit-tests. One for 0.9
syntax (without hwaddr) and another one for 0.9.1 and 0.9.2 (with
hwaddr). Just a simple check that the code terminates with an
appropriately worded exception that upgrade is needed. It's a
matter of debate whether this piece of work belongs to this ticket
or the memfile upgrade script ticket. Personally, I think it would
better fit this ticket, as people may upgrade to latest master and
be surprised. On the other hand, I presume the the upgrade script
ticket will come in next, so the window of opportunity is small here.
In other words, I won't object if you want to push this piece
to the next ticket.

This is relevant for the ticket which implements upgrade of the memfile.

generic_lease_mgr_unittest.h
Unless you invented a time travel machine, I suggest updating the
copyright date. :)

Fixed.

generic_lease_mgr_unittest.cc
EXPECT_NO_THROW around getExpiredLeases{4,6} would be useful.
It's not strictly required (exception thrown will fail the test
anyway), but we have a convention to add that macro anyway.

Added.

testGetExpiredLeases{4,6} should add a sanity check that calculated

index is not out of bounds. Otherwise you can dereference a garbage.

(That's for line 1701).

I didn't sanity check them because the calculations are based on the assert that the number of leases returned is equal to the size of the initial container divided by two. I don't see how this could fall over.

A comment around line 1690 should explain what the 1000 means.
For the test to be objective, you should repeat the second call
again with 1000. Just by looking at the test, I got the first
impression that the order of leases returned depends on whether you
want all of them or just the first 1000.

Added a comment.

In fact, I think testGetExpiredLeases4() should be split into
a number of small unit-tests. It's like 3 or 4 of them stacked
together.

It could, but there are some interdependencies between some of the cases there so I decided to leave it as is. Another issue is that every new test case in the generic_lease_mgr_unittest is multiplied by 3 (for each backend).

All comments above also apply to testGetExpiredLeases6().

Right.


The code compiles and unit-tests pass on Ubuntu 15.04 x64.

Thanks for the review.

comment:6 in reply to: ↑ 5 Changed 5 years ago by tomek

  • Owner changed from tomek to marcin

Replying to marcin:

Replying to tomek:
The default state which every "normal" lease is in is now marked as 0.

Thanks.

There is Lease::stateExpiredReclaimed(), but there's no
Lease::stateDeclined(). It's ok if you don't want to add it
in this ticket. I can take care of it in one of decline tickets.

I think it is a matter for a different ticket. It also relates to your point raised about the Memfile indexes and the LeaseMgr API which we have to discuss below.

Ok, it will be covered in another ticket. I'll be using this in #3984.
If it's not implemented by the time I get to #3984, I'll implement this.

how about
doing couple clean-ups in this area? We have comments_ that doesn't
seem to be used anywhere. The same is true for fixed_ and ext_.

Ok, I've done that.

Cool. Thanks.

lease_mgr.h
getExpiredLeases4 and getExpiredLease6() - those two methods should
be implemented as getLeases4InState(..., state) and
getLeases6InState(..., state). That way those calls could be directly
used in decline processing. And by any other future states we may
come up with. If you keep the code in the form it is implemented now,
we'll have to implement very similar calls for declined and any
other states we may define.

So this is problematic. The multi_index_container is a bit like SQL database but it is not that capable. At least not without adding some more complexity which is not a part of boost.

First of all, note that whether the lease is expired or not is a function of time, not the state. That's why the queries for expired leases can't just retrieve leases in a certain state (i.e. having a field state_ set to the desired value) but they have to find all leases for which expiration time is lower than the current time. At the same time, the leases must not have been reclaimed. Reclaimed leases are not returned as part of this call. You see how complex it is.

So, the composite index used to search for expired leases has two components: boolean (whether the lease is expired-reclaimed) and the time value. The specific order is also preserved so as we can retrieve leases that has been reclaimed or hasn't been reclaimed using the call to index.upper_bound. The same technique allows us to return leases ordered by the expiration time. If we wanted to use the "state" (uint32_t value) instead of the boolean value this causes trouble.

For the multi_index_container it is important that elements are ordered using a specific value. Ordering by the value of the uint32_t doesn't do any good because we may have leases in multiple states simultaneously. So the lease may be expired reclaimed but may also be in some different state which takes it way higher in the ordering (and effectively outside of the group of leases which are only "expired-reclaimed"). So the call to the index.upper_bound would actually exclude this lease from the results.

One way to achieve what you want is to create a lease index by expiration date (NOT a complex index). If you want expired and not reclaimed leases to be returned you use this index to gather all expired leases using this index. Then iterate over all returned leases and check whether they remain in the desired state or not. That would however result in a full scan of returned expired leases. I am on a fence.

As for the naming of the new functions I think there are some positive sides of having different functions serving different purposes. The point is that if you name the function getLeases4InState does it say that the lease is solely in this state or the lease may also be in other states? Also, when querying for expired leases ... they are not really in the "expired state" because there is no such state defined for the state_ field (and will never be). The meta-state "expired" is determined by the expiration time vs current state. So, I don't really no if this name is appropriate. I think that getExpiredLeases6 is better name. But, it is up for discussion.

We need to determine differences between the queries for decline and lease expiration. If the queries for declined leases are not going to be time-dependent we can't really combine them in a single function as you suggest.

I understand the difficulty of getting the expired leases that have not yet the EXPIRED_RECLAIMED bit set. So let's leave the code as it is now. But we still need a function that would return leases with specific state (e.g. expired-reclaimed). That work probably belongs to some other ticket, but let's conclude this discussion here.

Your explanation that it will be difficult to implement getting leases by state gave me an idea we may consider. Instead of treating state as bitfield (which would require bit operation on every lease to determine whether is matches criteria), we could use specific values: 0 - default, 1 - declined, 2 - expired-reclaimed. 3 would be for the next state or combination of states. That way we could query for it efficiently: use constraint WHERE state == X in SQL and do extra index in memfile. We did discuss this briefly on jabber.

I see there are 3 possible choices here: 1. discard the idea and keep the code as is; 2. implement this proposal in this ticket, 3. implement this idea in additional ticket. Personally, I would prefer (most to least preferred) 3, 2, 1. But I will not insist on it, if you decide otherwise.

There's list-declined-addresses command planned already. It will use
those calls.

I was thinking about other things that could require using another bit
in the state_ field. One thing that came to my mind is port-sets.
Those leases would be odd enough to probably warrant an extra
designation. When doing sanity checks for port-sets, it would
be useful to have a method to return all port-set leases. Hence
another use case for generic approach.

I think it makes sense to update LeaseMgr all at once. But, this is different use case than expired or declined leases. It requires to only check for leases which state is equal to something (or which bit is set to something) but doesn't depend on time and is not indexed as such. So, it would require a different method anyway. Perhaps another ticket.

See my comment above.

Do you think it would be useful for deleteExpiredReclaimedLeases{4,6}
to return the number of actual leases deleted? This is something
should be logged in, so returning the number would be useful.

We're logging the number of leases deleted in the function itself.

But this value could be used also for other purposes, bumping up statistics for example. It's a very simple change, so I insist on it.


Ok, I did review your changes and they're ok. There are two outstanding things above. For both, I leave it up to you whether you want to implement them, discard them or push to another ticket. In any case, feel free to merge it.

Updated code builds fine on Ubuntu 15.04 x64 and all unit-tests pass.

comment:7 Changed 5 years ago by marcin

  • Resolution set to complete
  • Status changed from reviewing to closed

Merged with commit dd5b95453528416f22e961e6ebb3051bc2ae788c

comment:8 Changed 4 years ago by tomek

  • Milestone changed from Kea1.0 to Kea1.0-beta

Milestone renamed

Note: See TracTickets for help on using tickets.