[bind10-dev] new in-memory zone data design

[Joao Damas]

On 20 Jun 2012, at 12:49, Michal 'vorner' Vaner wrote:

> Hello
> 
> On Wed, Jun 20, 2012 at 09:41:29AM +0000, Francis Dupont wrote:
>>> I've had a look and I have few questions:
>>> * It seems to be taken as a fact that it'll be a red-black tree. Is
>>>   there a reason for that? Are we able to reuse our implementation?
>>>   If not, we might want to consider different kinds of trees (2-3
>>>   tree, 2-4 tree or AVL), since they can have benefits we might
>>>   like.
>> 
>> => according to experts (i.e., guys D. Knuth nods to when he sees them)
>> the red-black tree is the best (known) data structure for this kind of
>> things, in particular its dynamic performance is pretty good. So I
>> support Junmei in his choice!
> 
> Well, that's the point. Dynamic performance means it is fast with updates.
> However, we have much more lookups than updates. AVL trees are somewhat slower,
> but they are better balanced, so they trade the update speed to get better
> lookup speed. So I think AVL tree might be better for that reason.

Yes, but there is a need to support updates and they are slow like hell.
In the future, we can have an option for zones that are known to be static (by the administrator) and use a different data structure. In that case, a fully  balanced would be a better choice but we would probably also do pre-compilation of answers ala NSD.
I believe Jinmei started work on one such backend in Year 2 of the project before an external interrupt failed to be masked.
> 
> What I fear is, somebody decided to use RB tree because it is generally the good
> choice (without really thinking about specific needs) and then everybody uses
> them because everybody uses them. We never had a discussion about what tree we
> want to use.

well, because it is the best for the general case. One goal of BIND 10 is to support more than the general case, as per above, but we can't do that right now. Nonetheless I am looking forward to the day when we can, in 12 months time or so.

> And there are many more choices. For example, a radix tree might make sense,

a radix tree might be the best choice for zones in reverse DNS, indeed.

> since the names are effectively strings. Or, we could have (sometime in future)
> a version that does not support updates, only complete rebuilds (then it is
> reasonable to build a perfectly balanced tree instead), or one that doesn't
> support DNSSEC (therefore it does not have to be a tree at all).
> 
> With regards
> 
> -- 
> Einstein argued that there must be simplified explanations of nature, because
> God is not capricious or arbitrary.  No such faith comforts the software
> engineer.
>                -- Fred Brooks
> 
> Michal 'vorner' Vaner
> _______________________________________________
> bind10-dev mailing list
> bind10-dev at lists.isc.org
> https://lists.isc.org/mailman/listinfo/bind10-dev