[bind10-dev] initial memo on recursive server performance research

[Jerry Scharf]

Jinmei,

On your second point.

Would it be possible to do the analysis for the actual cache hit rate 
rather than just the name appearing? Many of the popular web sites use 
short ttls (30-300s) for the main target. which reduces the 
effectiveness of caching.

I really like the idea of a fast L1 cache per auth. The idea of an added 
a hast test/ttl check and L1 cache store to misses in return for not 
walking the tree/rebuilding the answer for popular queries seems like it 
would be a big win. All you need to do is fix the ttls and wrapper and 
it's ready to go. You will have to think a little bit about victim 
selection when a new cache entry comes in. You would like to victimize 
entries that have no hits before google.com gets replaced. When you get 
to views, you will need an L1 per view.

I wish I had thought of this when I was working on the trend recursive 
server. It may be a cheap 20% increase in performance.

jerry

On 07/03/2012 11:41 PM, JINMEI Tatuya / 神明達哉 wrote:
> I've been working on some experiments about recursive server
> performance (as Shane reported here a few days ago).  I don't have any
> exciting results yet, but here are a couple of initial results.
>
> 1. Performance of an "ideal" implementation
>
> I've written an imaginary "ideal" server implementation that basically
> does nothing except for network I/O, and measured its max possible QPS
> on a test machine.  The "server" is useful for any practical purposes,
> but its performance would be still informative in that it would be the
> possible highest performance of our real implementation.  The server
> still somehow behaves "recursive DNS server like" - it checks the
> first byte of receiving "queries", and either immediately sends a
> given size of response or "forwards" it to a pre-specified address.
> It opens another socket for receiving "responses" to the forwarded
> packets, and, like the case of queries, it either responds to the
> "original client" or repeats the "forwarding".  By controlling the
> content of test packets, we can control the imaginary "cache hit rate"
> or the number of "recursion" needed when cache miss happens.
>
> Since the resulting throughput was very high, it seemed mostly
> impossible to measure the max possible QPS with a usual tool like
> queryperf (partly because other hosts I can use as the "client" is
> much less powerful than the server box).  So I gradually increased
> the query/response rate until the server clearly started dropping
> queries (ignoring some intermediate minor margins).
>
> This graph summarizes the result of this experiment:
> http://bind10.isc.org/~jinmei/rec-max-qps.png
> ("n iter" means the server would need to do n recursions when cache
> miss happens).
>
> It just seems something predictable, but I think it's still
> informative in that it highlights the point that the cost of each
> recursive transaction matters (i.e., if we need more
> recursions/transactions on cache miss, that could affect the overall
> performance substantially).  In some sense it's obvious from simple
> math even without running experiments, but I guess we were not really
> aware of this in the previous discussions.  And, this means, for
> example:
> - attempts that lead to increase the number external transaction may
>    not really be a good idea, at least for throughput.  Those include
>    querying multiple authoritative servers at the same time and trying
>    very hard to identify EDNS availability.
> - anything that helps reduce the number of transaction may provide
>    substantial performance improvement.  For example, it may make sense
>    to keep delegation information at a higher priority (or separately)
>    than other cached records even if the former is not used so often
>    (and can be easy target of pursing due to a simple LRU-based
>    algorithm).
>
> 2. popularity of queries
>
> I've analyzed an old (about 5 years ago) but real query sample taken
> on a busy recursive server in terms of "query popularity", i.e., which
> queries were asked more and how often.
>
> The result is summarized in this graph:
> http://bind10.isc.org/~jinmei/query-popularity.png
> The query sample consists of about 2.49M queries containing 290K
> unique queries.  This summary graph should read the most "popular"
> query occupies 4.71% of the total of the 2.49M queries, the top 10
> consume 10.62%, and so on.  Not so surprisingly, the distribution is
> pretty heavy tailed.  The top 10,000 (about top 1/30) occupies about
> 80% of the entire queries.
>
> While the data are too old and this is only one data point (next steps
> of this work includes getting and analysing more recent samples and
> from multiple points), if it still holds today and commonly for busy
> servers (which I guess is quite likely), it suggests it's promising to
> introduce optimization approaches like multi-layer caches.  We could
> even let separate thread or process running on different CPU cores
> have their own "layer 1" cache in the most efficient form for faster
> response (like pre-rendered response).
>
> These are just speculation at the moment though.  We need more
> intensive research, which will be our next steps.
>
> ---
> JINMEI, Tatuya
> _______________________________________________
> bind10-dev mailing list
> bind10-dev at lists.isc.org
> https://lists.isc.org/mailman/listinfo/bind10-dev