BIND - sorting of reverse domain.

Danny Mayer mayer at gis.net
Mon Jul 8 02:23:21 UTC 2002


At 04:36 PM 7/6/02, D. Stussy wrote:
> >> >    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.
> >>
> >> Perhaps in the current implementation, but such need not be the 
> case.  I have
> >> already indicated why this is inefficient.
> >
> >       Did you really think the zone was stored as single array?
>
>You said that it has to arrange the zone in alphabetical/machine order so 
>as to
>know when to stop by having gone past the target name.  That is a list, 
>pure and
>simple.  It could be implemented as an array or as a dynamicly linked list 
>with
>pointers, or have a hashed index to direct it to a reduced sub-list; the 
>actual
>implementation doesn't matter.  However, the operation you describe is NOT
>intrinisic to a binary tree arrangement, so per your description, it can't be
>that.  Binary trees know that they haven't found an element by hitting a leaf
>(i.e. literally, a NULL pointer when trying to get the next node), not the
>"next" element that would be in machine order.
>
> >       You get told why the order is as it is, yet you still persist
> >       in saying that it is deliberately sorted on output.  It is not.
> >       You are looking at simple tree traversal.  This is true for both
> >       BIND 8 and BIND 9.  BIND 8 is a tree of hashes.
>
>As I said, if it is merely a side effect of the INTERNAL sort, no one has
>affirmatively confirmed that.

Mark has affirmatively confirmed that.  Mark deals with the internals of
the code every day, so unless you have read and understood the code,
you can't make any statements whatsoever about its internal workings.

> >> >    Both BIND 8 and BIND 9 dump zones in internal order though they
> >> >    do put the SOA and NS RRsets for the zone first.
> >>
> >> Placing the SOA record first is obvious.  As compared to the other entries
> >> within the domain, it effectively has a <null> name because all the other
> >> entries have at least one more name element.
> >
> >       Actually putting the SOA first is NOT obvious as it doesn't
> >       sort first when sorting a zone in DNSSEC order.  The A
> >       records come first (type = 1).  As for BIND 8 there is no order
> >       to the records at a node.
>
>Obviously, someone who needs remedial English.  It should have been clear 
>that I
>addressed ONLY the domain name component of the sort and that the RR type
>ordering isn't even being discussed because that is not relevent to the sort
>order of the NAMES.  My statement cannot be interpreted any other way - 
>the fact
>that it has clearly demonstrates why software engineering documentation has to
>be so "anal" in its description and specification.

If you had read Mark's reply carefully, you would realise that the whole tree
is in internal sort order and not just the domain name component. The
internal organization is optimized for speedy retrieval of responses and
specifically DNSSEC order. Dumping the contents of the tree does not
require a sort and it comes out in the order that it retrieves the records.

>Furthermore, the translation of RR type names into integers (or any other
>transformation) is clearly an artificial operation.  It could just as 
>easily be
>an index or pointer into a list of known types (with unknown types handled
>specially) with a comparison as to index or pointer order.  If in such a list,
>the "SOA" string is placed at the head, the natural sort operation using this
>index would put the SOA RR first.  Therefore, any such transformation is
>meaningless in itself (cf. "The A records come first (type = 1).").  It sounds
>as if this concept is beyond your capability of understanding.
>
>I'm not here to bash anyone.  I expect an INTELLIGENT conversation.  It's 
>clear
>that I'm not getting one.

It would help if you had read the code first. Zone files of the slave server
can't be modified, so why worry about the order they are put onto disk?
On the other hand, this can help in loading since it won't have much work
to do in sorting them into the internal order and it will load a large zone
faster. If you want intelligent conversation, read the code first and then ask
questions.

Danny



More information about the bind-users mailing list