BIND - sorting of reverse domain.

[Mark_Andrews at isc.org]

> 
> On 6 Jul 2002 Mark_Andrews at isc.org wrote:
> >> On 4 Jul 2002 Mark_Andrews at isc.org wrote:
> >> >> On 3 Jul 2002, Kevin Darcy wrote:
> >> >> >"D. Stussy" wrote:
> >> >> >> Older versions of BIND did not.  However, BIND-9 does - but someone 
> els
> >> e
> >> >> >> indicated that this is a side effect of its memory image of the data
>  an
> >> d n
> >> >> ot
> >> >> >> intentionally done.  If truly not intentional, that could moot my qu
> est
> >> ion
> >> >> .
> >> >> >>
> >> >> >> I do note that someone also indicated that BIND arranges the data in
> >> >> >> alphabetical/machine order so as to abort early with an NXDOMAIN err
> or
> >> if
> >> >> it
> >> >> >> passes the point where the target query name would be.  Such a searc
> h i
> >> s
> >> >> >> potentially an O(n/2) on the average - while a balanced binary tree 
> sea
> >> rch
> >> >>  would
> >> >> >> be O(log2(n)) (and the worst case unbalanced tree - O(n/2)).  Except
>  fo
> >> r n
> >> >> =1 or
> >> >> >> n=2, log2(n) < (n/2) for postive integers, so why choose a non-optim
> al
> >> sea
> >> >> rch?
> >> >> >> [This goes beyond my original question/comment, so responses aren't 
> nec
> >> ess
> >> >> ary.]
> >> >> >
> >> >> >BIND stores zone data in memory in a hashed structure which has little
>  or
> >>  no
> >> >>  relationship to the format in which it writes out
> >> >> >zonefiles.
> >> >>
> >> >> If true, then it must actively sort the zone file in order for it to be
>  wr
> >> itt
> >> >> en
> >> >> 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
> >>  no
> >> >> t
> >> >> write out the reverse domain files in numerical order where possible?  
> [We
> >> 're
> >> >> back to my original question!]
> >> >>
> >> >	BIND 8 uses a hash.
> >>
> >> Nor did it have this behavior.
> >>
> >> >	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 h
> ave
> >> 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 wi
> th
> pointers, or have a hashed index to direct it to a reduced sub-list; the actu
> al
> 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.

	At that point you also have the node that immediately preceeds the
	node you were looking for if you cared to save it as you traversed
	the tree.  Try it with any binary tree.  You either hit the node
	you are looking for, you traverse the node immediately preceeding
	it or there is no preceeding node.  The same can be said for the
	node after the one you were looking up.

> >	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.

	You have been told that many times.  What do you think
	"named needs the zone in DNSSEC order" means?  It definitely
	doesn't need it in dnssec order on disk.

> >> >	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 tha
> t 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 f
> act
> that it has clearly demonstrates why software engineering documentation has t
> o
> be so "anal" in its description and specification.

	Named could just have easily output the zone in reverse order.
 
> 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 sound
> s
> as if this concept is beyond your capability of understanding.

	Have you ever looked at the DNS protocol.  Type and class are
	transmitted as 16 bit numbers.  It's perfectly natural for a
	nameserver to convert them to numbers when they are loaded and
	as we are talking about the result of a zone transfer this is
	how they are received.  Nameservers don't transmit master files.

	Early version of BIND 9 did not put the SOA first.  It confused
	those early adoptors.  We re-orded the first node to make the
	SOA come out first and the NSs second.
 
> I'm not here to bash anyone.  I expect an INTELLIGENT conversation.  It's cle
> ar
> that I'm not getting one.
> 

	Mark
--
Mark Andrews, Internet Software Consortium
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: Mark.Andrews at isc.org