[bind10-dev] recursor cache requirements - input required

[Michal 'vorner' Vaner]

Hello

On Thu, Dec 09, 2010 at 09:54:57AM -0800, Jerry Scharf wrote:
> We are not talking about a log(n) tree here. We are talking about a 
> query with 6 labels being unusual. You build the hashes of children at 
> each node. With fanouts of at least 50-100 and exceeding 1,000,000, the 
> hashes are still quite effective.

They may be, but it's still 6 lookups vs 1. And I'm not saying how the internal
structure should look like, I'm saying that the requirement shouldn't enforce
too much internal layout if it isn't needed. If it turns out that walking it
from the top is faster, then be it. But I'm not sure we want to restrict to
walking from the top if there would be no benefit. So I asked about the benefit.

> I once again recommend you make the basic code work first. It is in my 
> experience half an order of magnitude harder on the recursive side than 
> the authoritative side.

Well, the plan is to do minimal cache for now (some kind of std::map wrapped
into something) so the rest of the recursor can evolve. But when we are talking
and designing, it would be nice not to shut down the door for optimisations
later on. Currently, we need to figure out the probable interface mostly.

> Second, if you look at the people who have made recursive servers go 
> fast (Nominum) they didn't do that by looking for percentage gains by 
> caching more information at nodes. They did the really hard job of 
> making it so it can be efficient on multiprocessor/multicore machines. 
> Adding all sorts of extra caching up front makes getting the multiaccess 
> and multiupdater cache working that much harder.

Well, it depends. If adding of some flags (which are small and in the same
region of consecutive memory, therefore really cheap to get) under the same lock
would lower the number of requests for other parts of the things, then it would
make the cache work faster on both uni and multi processors. But we are talking
about hard-to-guess stuff without any numbers. We'll really need to implement
something and then measure it.

My point was, enforcing some kind of internal layout now will make less room
later, when we measure it. The requirements probably should say what we need
from the cache (eg. identify the kind of queries we will do against it), and
leave the how for later.

With regards

-- 
All flame and insults will go to /dev/null (if they fit)

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/20101209/440b4e27/attachment.bin>