tuning for maximum dhcp performance

[David W. Hankins]

On Thu, May 08, 2008 at 09:18:25PM -0500, Frank Bulk - iNAME wrote:
> This may be a dumb question, but why not calculate an optimal hash size at
> the first start, update it and store it in the dhcpd.leases file while the
> dhcpd process runs, and then read it from the dhcpd.leases file and use it
> every time the process starts up?

we should totally do that;

| at some point in some future revision, we'll make the tables scale
| themselves upwards as needed (size and allocate the tables after
| loading config, then put all the leases in them).

no need to store it in dhcpd.leases.  we can count the number of
leases in config after loading dhcpd.conf but before processing
dhcpd.leases (just keep a list of all the requested dynamic ranges),
allocate a hash table of a specific size, and "instantiate" the raw
config into the optimally-sized table, then process the lease db
normally.

it was just too much of a stretch to do all this in 3.1.0's timeline.


note however that making the table sizes different for different
purposes wasn't the only improvement to the system in 3.1.0; in
particular there were only two key->hash algorithms (do_case_hash
for caseless strings, and do_hash() for all other opaque binary
fields) in 3.0.x, and both those functions operated very much like;

	accum = 0;

	for (i = len ; i != 0 ; i--) {
		accum <<= 1;
		accum += *(s++):
	}

	return accum % table_size;

except that do_case_hash() adds a tolower().

since there are only 4 octets in an IPv4 address, note that this
uses at most from index 0 to index 3825 (where 255.255.255.255 will
hash), which never approached 3.0.x's default table size of 9973, and
likely, you will find your leases in a "bell curve" at some point of
that range...all clustered together.  "most pessimal."

in 3.1.0, we also added some functions, trying something new and
different with hardware/client-id's, and treating ipv4 addresses
and dhcp option codes both as 32-bit integers (so we take addr %
table-size or code % table-size directly), which should have a
significantly better "spread" than treating them the same as in
the above function.

i also tried to come up with something clever for text strings, but
gave up on it by 3.1.0's release time, so the above unfortunate
accumulator is still in there.


and by the way.

for our next trick we will switch to heaps instead of sorted linear
lists for maintaining "the next lease to process" for each lease
state (expiration/active, free, etc).  this should be a much smaller
improvement, but should be substantial on large installations.

-- 
David W. Hankins	"If you don't do it right the first time,
Software Engineer		you'll just have to do it again."
Internet Systems Consortium, Inc.	-- Jack T. Hankins