[bind10-dev] Using AVL tree instead of red-black tree in DomainTree

[JINMEI Tatuya / 神明達哉]

At Wed, 6 Mar 2013 15:14:25 +0530,
Mukund Sivaraman <muks at isc.org> wrote:

> > Although I'm not necessarily opposed to switching to AVL trees per se,
> > if there's specific reason for that, I personally do not necessarily
> > buy this argument either. [...]
> > personally, I'd rather port the BIND 9's RB tree deletion
> > implementation than trying to implement the entire AVL tree logic from
> > the scratch.
> 
> Here, I disagree. I have a reasonable argument for it.

> But we have to understand and maintain any code in the BIND 10 tree
> itself. Even if we migrate the BIND 9 code to the BIND 10 tree as-is, we
> are still responsible for this code. To fix any bugs or even performance
> issues, we will need to be able to work with it reasonably quickly.
> 
> The fact that the RB tree implementation has been tested in the BIND 9
> codebase is a strong point in support of it. But that itself is just one
> point among many that we should consider.

I admit it's not clear how the BIND 9's RBT code was written, so it
could be possible that there's a bug in it.  But it's been running for
about 10 years (I believe the main RBT logic hasn't been modified from
a quite early version) at least without showing a crash-like
disruption or noticeable scalability problems.

And, since the internal data structures are generally compatible
between BIND 9 and (current) BIND 10, it's mostly straightforward to
port the BIND 9 version to BIND 10.  I experimentally did it for the
deletion code and pushed it as jinmei-rtbdel branch and was actually
convinced about that.  Randomly picking up, the following BIND 9 code

		successor = RIGHT(delete);
		while (LEFT(successor) != NULL)
			successor = LEFT(successor);

was ported to BIND 10 as follows:

        DomainTreeNode<T>* successor = node_to_del->getRight();
        while (successor->getLeft()) {
            successor = successor->getLeft();
        }

I suspect it's even possible to auto-port it with some simple script.
So it was provably easy to complete the delete implementation at least
as accurate/inaccurate as BIND 9.

We'll still need to understand the code, not just blindly trust the
BIND 9 implementation, maybe referring to an algorithm textbook.
We'll also have to write tests.  How heavyweight it is may be a
subjective matter, but at least from my experiments of the quick
porting, it didn't seem to be too difficult to be sure that it's a
correct implementation of RBT deletion.

For future maintenance, I have a slightly different view than yours.
I suspect it's quite unlikely we really need to maintain the code in
the same sense we need to maintain DNS query logic once we complete it
with reasonable review and tests, especially if we begin with known
working implementation, because the algorithm is well known and it's
very unlikely we need to enhance that part of the logic (the history
of BIND 9 code proves that).

Further, it's even advantageous if we have compatible implementation
between BIND 9 and BIND 10 because if we ever find an algorithm level
of bug in it we can fix both.

> I spent some time cleaning up the insert code in the current RB tree
> implementation last weekend. A few months back, I rewrote the code to
> delete all nodes. Both implementations (the latter especially) were poor
> code for a fresh developer to randomly pick it up and understand (even
> if they have experience implementing RB trees).

I'm not sure specifically which point of the code you're referring to,
but I'm sorry you needed to deal with it.  The insertion and
delete-all code was actually written from the scratch for some unknown
reason even if I suggested porting the proven workable implementation
of BIND 9.  If the quality was poor, that actually seems to be an
example of why it's generally a bad idea to try to re-implement a
well-known (and complicated) algorithm yourself.

But now that we have workable, tested, and reviewed implementation,
and it's unlikely to touch that basic level of logic any more, and
it's quite easy to port the known-to-work BIND 9 implementation, I
don't see a strong point of re-writing something still complicated
from the scratch, testing and reviewing it.

Repeating myself, if switching to other algorithm has other clear
benefit like substantial performance improvement, it can be a stronger
reason (whether we should implement it from the scratch or try to find
a way to port an established implementation is a different question,
though).  Or, even if there's no clear benefit other than possibly
using a bit simpler algorithm, if we can use a known workable
implementation with a straightforward modification for port, that may
make sense.  But in my understanding so far neither is the case: we
didn't see clear advantage, and my understanding is that what we would
be doing is to test and review yet another from-the-scratch
implementation of AVL tree and its adaptation of other properties of
our domain tree data structure.  That doesn't seem to make sense to
me.

That said...in the end, I guess we just have different views of what
matters more, and it's probably unlikely one can convince the other.
Hopefully someone else can provide their views.

---
JINMEI, Tatuya