[bind10-dev] More ideas about high-performance data-source backend (warning: long text)

[Michal 'vorner' Vaner]

Hello

On Fri, Oct 08, 2010 at 01:59:10AM +0900, JINMEI Tatuya / 神明達哉 wrote:
> I don't think my experimental code is so useful for your purpose
> because
> - it has other features (such as offset-based pointers to support
>   mmap-based loading), which would be just noisy for you
> - other than that, the tree structure itself is a simpler port of BIND
>   9's rbt.  so you might rather want to see the original
>   implementation.

I didn't mean the tree itself, but the other parts ‒ the pointers between RR
sets, name compression hints, bindings to the data source API and so on.

> As for cooperation, I'm generally happy about that.  How much we can
> spend for the cooperation will depend on overall project plans,
> though.

I was asked to join the R-team now, so there won't be much cooperation right
now. But hopefully sometime in future.

> - but in terms of overall server performance, it also depends on how
>   many times we need to perform lookups for a single query.  if we can
>   minimize that (NSD and BIND 9's "acache" take that approach) the
>   lookup bottleneck would become relatively minor.

I think the tree structure is completely ortogonal to the optimisations you
mentioned, like the hints for compression and pointers between RRsets you
mentioned in the presentation.

> As for your specific proposal, I think we need a figure:-)

By figure, you mean a picture of it or some numbers? The first probably can be
done easily, the second would mean a lot of guessing and computing, what I
proposed is based partly on some experience, gut feeling and guesswork.

> One quick thought that occurred to me is whether we can (efficiently)
> update this DB without keeping the good property of locality.

Like you ask how hard it would be to make an update? Well, I think it is
possible, but it would be less efficient than with normal rb tree or something
like that. But there should be a lot less updates than queries anyway I guess.

If there's space in the vertex when we add, it is OK like in normal b-tree. If
not, we still can do the tricks like try to push something to neighbor. If we
really need to split, then the harder part comes and I would need to find an
empty small vertex in the big one, which means traversing the whole page. If
there's need to split the big one, we split the root of it and copy half of the
vertices/branches into another one, which means traversing the page 1.5 times
(but it still should stay in the case, one page fits).

Do you think it makes sense to put it somewhere on wiki, or it is enough I
remember it?

Thanks

Have a nice day

-- 
Work with computer has 2 phases. First, computer waits for the user to tell it what 
to do, then the user waits for the computer to do it. Therefore, computer work 
consists mostly of waiting.

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20101008/d1b78dd6/attachment.bin>