BIND - sorting of reverse domain.

[Kevin Darcy]

"D. Stussy" wrote:

> On 8 Jul 2002, Andris Kalnozols wrote:
> >Since this thread has gotten rather large (22 replies at last count),
> >I'll insert a few quotes before making my point.
> >
> >Original post:
> >
> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> It appears that BIND (I have version 9.2.1) sorts all its domain
> >> entries in the files it stores alphabetically ("machine sort order").
> >> That's fine for the forward domain file where domain/hostnames are
> >> usually alphabetic.  However, for the reverse domain file, it makes
> >> more sense to sort it in NUMERICAL value order, thus keeping adjacent
> >> IP addresses nearer to each other.  (Of course, I don't care what
> >> named does internally with the zone as a memory image ....)
> >
> >Selected replies:
> >
> >> Mark Andrews <mark_andrews at isc.org> replied:
> >> The order is DNSSEC order.  To support returning signed NXDOMAIN
> >> responses the namserver needs to know the node that appears
> >> immediately before the name in the query.  To do this it sorts the
> >> zone when it loads it into DNSSEC order.  When named writes out the
> >> zone it just walks the zone which results in records being emitted
> >> in DNSSEC order.
> >
> >> > Mark Andrews <mark_andrews at isc.org> replied:
> >> > BIND 9 sorts in DNSSEC order because it *needs* the zone to be
> >> > sorted this way to able to find the correct NXT record to be
> >> > returned with a NXDOMAIN response.
> >>
> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> Perhaps in the current implementation, but such need not be the case.
> >
> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> If true, then it must actively sort the zone file in order for
> >> it to be written out in alphabetical order (which is occuring
> >> with this version).  It is obviously bothering to take the time
> >> to do this, so while we're at it, why not write out the reverse
> >> domain files in numerical order where possible?  [We're back to
> >> my original question!]
> >
> >> D. Stussy <kd6lvw at bde-arc.ampr.org> wrote:
> >> ...How the RR records are ordered for a zone name is of no
> >> consequence whatsoever when determining whether or not the
> >> name EXISTS or not.  I couldn't care less about that - it is
> >> not relevent to the original question.
> >>
> >> My question was not one of how it IS coded - but one of how
> >> it MAY be coded.  How the current source code is actually
> >> written isn't of consequence because if the preference I asked
> >> about were to be accepted, the source program would have to be
> >> changed anyway.
> >>
> >> You all are too worried about the actual implementation while
> >> I'm talking about conceptual design - a separate step.
> >
> >After reading your comments, I get the distinct impression that
> >when DNSSEC is mentioned, you are not making the connection to
> >RFC-2535, the specification that implements it.  Here's what it
> >requires as a sort order:
> >
> >  8.2 Canonical DNS Name Order
> >
> >    For purposes of DNS security, the canonical ordering of owner names
> >    is to sort individual labels as unsigned left justified octet strings
> >    where the absence of a octet sorts before a zero value octet and
> >    upper case letters are treated as lower case letters.  Names in a
> >    zone are sorted by sorting on the highest level label and then,
> >    within those names with the same highest level label by the next
> >    lower label, etc. down to leaf node labels.  Within a zone, the zone
> >    name itself always exists and all other names are the zone name with
> >    some prefix of lower level labels.  Thus the zone name itself always
> >    sorts first.
> >
> >    Example:
> >          foo.example
> >          a.foo.example
> >          yljkjljk.a.foo.example
> >          Z.a.foo.example
> >          zABC.a.FOO.EXAMPLE
> >          z.foo.example
> >          *.z.foo.example
> >          \200.z.foo.example
> >
> >Since BIND 9 strives for strict compliance with IETF standards,
> >changing the internal sort order when a zone is loaded is not
> >an option if DNSSEC is to be implemented efficiently.
> >
> >To implement what you are asking means that the code for writing
> >out a zone to disk must first traverse the red-black tree to see
> >if the relative domain names consist solely of digits and, if so,
> >traverse the tree once again and resort the data numerically before
> >writing the disk file.  With all the essential work that name servers
> >(and BIND maintainers) have to do, do you still think that your idea
> >would be a good use of resources?
>
> Incorrect.  I have made that connection.  Note that this only talks about the
> name component, which is what I limited my query to.  DNSSEC order also takes
> into account the RR-set (a secondary sort key) order for a zone, and that falls
> OUTSIDE my query (by going beyond it).  Furthermore, the RFC requires an order
> for the MEMORY IMAGE, but again, that isn't relevent to the FILE image I queried
> about.
>
> Since others said that a zone ISN'T stored in alphabetical/machine order, but is
> written out as such, I properly concluded that before writing, an additional
> sort of the zone names was occuring so as to make the file listing of the zone
> appear in a human readable pattern.  It wasn't until later that they finally
> admitted that it was a side-effect of their tree-traversal (which
> coincidentally, did traverse the tree in machine order to write the file) -
> which means that it IS in fact sorted in machine order to begin with.  Beyond my
> query, my assertions were as a result of their false statements.
>
> However, there was also the contradiction.  At least one said that when
> searching for a zone by name, the search terminates when one hits a value
> greater (in machine order) than the target.  That only happens with a certain
> structure (a list) and is complete nonsense to others (e.g. a tree).  They then
> accuse me of misunderstanding.  That statement was clear but false once again.
>
> Had these responders to my query had not made these false statements, my
> question would have been mooted at the first response.  Their incorrect
> statements implied actions such as an additional sort before exportation to a
> file of the data.  I simply asked, if that's what you're doing (presumedly to
> make the file human readable), then why not make this adjustment (where both
> text values are completely numerical, compare on the numerical values) while
> performing this sort (which now I know doesn't exist).
>
> My follow-up question, once I overcame their falsehoods, then was:  Why was it
> chosen to save the file in machine order when that requires a tree-rebalance
> performance penalty when reading it back in (upon restart)?  If it is saved in
> this other tree traversal order, the rebalance penalty is completely avoided (as
> long as the zone file hadn't been tampered with in the meantime).  I still await
> an answer to that one.

No-one really cares about squeezing an ounce of performance out of the zone-loading
process, especially if it has the potential to harm the human-readability of zone
files. There are much bigger fish to fry in the DNS world.

If you want to send a patch to ISC, send a patch. Or subscribe yourself to
bind9-workers. bind-users is for *users* of BIND, and this discussion is off-topic
here. I intend this to be my last message in the thread.


- Kevin