[bind10-dev] NSEC3 serving performance optimization: pre-calculate hashes

[JINMEI Tatuya / 神明達哉]

I know it's probably too premature to discuss details of performance
optimization for NSEC3 serving even before starting basic performance
optimization work, but the latter will start quite soon, so I thought
it's at least worth mentioning.

There was a comment at the BIND 10 open day in last August about NSEC3
serving performance:

"BIND9 DNSSEC performance with NSEC3 30k - 60k qps. Compared to NSD,
BIND9 has really degraded performance when increase the number of
hashes/iterations. Would like BIND10 to address this (NSD does
pre-calculations)."
(from http://bind10.isc.org/wiki/August11OpenDayNotes)

I'm not so sure about "the number of hashes" part, but it's at least
not surprising that BIND 9 degrades performance in terms of qps when
the hash iteration is increased, because BIND 9 always calculate the
hash for any internal NSEC3 lookup run-time.

If I understand the code correctly, NSD (previously) made shortcut
pointers from each ordinary name in a zone to the corresponding NSEC3
(some of which are matching NSEC3, others are covering NSEC3 if the
zone is opt out), thereby avoiding run-time hash calculation and NSEC3
lookup in many cases.

But maintaining shortcuts for covering NSEC3s is expensive when a
small change is made to the zone because adding/deleting a NSEC3 could
potentially affect any ordinary names that were covered by an NSEC3.
So an incremental zone update could lead to a whole-zone
reorganization (I guess this is what Shane mentioned last week?).

NSD 3.2.9 seems to partially stop using the full shortcuts - if
specified so at the configure time, it only maintains shortcuts for
matching NSEC3 and always calculates hash and searches for covering
NSEC3s.  I don't know the quantitative effect of this, but I wouldn't
be surprised if it has significant adversely effect in practice,
considering it will hit two major cases for main NSEC3 users (i.e.,
TLDs): for the name error (NXDOMAIN) case in finding no wildcard proof
and for the insecure delegation (+ opt out) case in finding a covering
NSEC3 of the next closer name.

So, I'd suggest a bit different approach: maintain calculated hash
values for each ordinary name (even if it's opt-outed).  If we do this
for both the name itself (like foo.example) and a wildcard name that
is an immediate child of that name (like *.foo.example), we can avoid
calculating most of the hash values in the above two major cases.  I
suspect it's not that expensive to actually search for the NSEC3 once
the key (hashed name) is identified - due to its characteristics we
could optimize comparison logic (e.g. not as domain names but as
normal binary data comparable by memcmp), and for a heavily opt-outed
zone the number of NSEC3 would be relatively smaller compared to the
zone size.

Keeping a copy of calculated hashes has disadvantageous in terms of
memory footprint, but I think we can also optimize that in various
ways: we could actually have shortcuts to matching NSEC3s (which
inevitably has the hashed value anyway), and it would also be
effective in practice to only maintain the hash for the wildcard
directly under the apex (like *.example for the "example" zone, but
not for *.foo.example, etc), because I guess for many TLDs the closest
enclosure of NXDOMAIN cases is actually the zone apex.

Anyway, these are just unproved ideas, not even checking with a quick
hack implementation and artificial data.  So it probably doesn't make
sense to discuss too many details of this right now, but if I
completely misunderstand something I'd be happy to be corrected.

---
JINMEI, Tatuya