Subject: [DNSOP] prefetch (HAMMER_TIME) draft

From: Brian Somers <[email-masked]>
Date: Wed, 6 Nov 2013 13:50:51 -0800

Hi,

I mentioned at the dnsop talk at IETF88 yesterday that I have some (hopefully) useful information regarding W.C.A. Wijngaards' prefetch work.

At OpenDNS, we implemented the same thing some months ago (without knowing about this work) with the following differences:
- Our HAMMER_TIME is set to 3 seconds
- Our STOP is hardwired as HAMMER_TIME + 1

We saw similar non-results in our graphs - at ~50 billion queries per day, prefetch didn't change anything.... However, there were two other issues addressed:
- Under normal circumstances, when a record expires, all clients querying that record suffer (unnecessary) latency while the record is being re-queried upstream.  Fixing this was a convenient benefit.
- Because our resolvers run multiple threads sharing the same cache, previously, a popular record expiration would tend to result in an upstream query from *each* thread.  This was the issue we wanted to address.

You could argue that our implementation should be clever enough to piggy-back the upstream queries from different threads (one query, multiple clients on multiple threads waiting for the response), but having the threads interact/contend against eachother for more than just cache lookups/updates is undesirable at higher loads.

--
Brian Somers
[email-masked]

---

From: Daniel Migault <[email-masked]>
Date: Wed, 6 Nov 2013 23:48:24 +0100

Hi,

Thanks for providing this information.

"- Under normal circumstances, when a record expires, all clients querying
that record suffer (unnecessary) latency while the record is being
re-queried upstream.  Fixing this was a convenient benefit."

Do you have specific metrics to measure/evaluate this benefit?

BR,
Daniel

On Wed, Nov 6, 2013 at 10:50 PM, Brian Somers <[email-masked]> wrote:

> Hi,
>
> I mentioned at the dnsop talk at IETF88 yesterday that I have some
> (hopefully) useful information regarding W.C.A. Wijngaards' prefetch work.
>
> At OpenDNS, we implemented the same thing some months ago (without knowing
> about this work) with the following differences:
> We saw similar non-results in our graphs - at ~50 billion queries per day,
> prefetch didn't change anything.... However, there were two other issues
> addressed:
> - Under normal circumstances, when a record expires, all clients querying
> that record suffer (unnecessary) latency while the record is being
> re-queried upstream.  Fixing this was a convenient benefit.
> - Because our resolvers run multiple threads sharing the same cache,
> previously, a popular record expiration would tend to result in an upstream
> query from *each* thread.  This was the issue we wanted to address.
>
> You could argue that our implementation should be clever enough to
> piggy-back the upstream queries from different threads (one query, multiple
> clients on multiple threads waiting for the response), but having the
> threads interact/contend against eachother for more than just cache
> lookups/updates is undesirable at higher loads.
>
> --
> Brian Somers
> [email-masked]
>
>
>
>
>
> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop
>
>

-- 
Daniel Migault
Orange Labs -- Security
+33 6 70 72 69 58

---

From: Brian Somers <[email-masked]>
Date: Wed, 6 Nov 2013 17:02:50 -0800

Using a sample of our US traffic over a 7 minute period, I see 112,044 lookups of www.facebook.com out of a total of 4,081,834 queries (2.74%).
That's 266 www.facebook.com queries per second.

Doing a lookup where our resolver is only missing star.c10r.facebook.com (which the www.facebook.com CNAME points at; the record with a 60 second TTL) takes 1.6ms.
Doing a lookup where everything's cached, our resolver takes 0.7ms.

Given that our prefetch implementation actually charges the client that first queries the record in the last 3 seconds of its TTL, and given that we now cap our resolvers at 6 threads, this means that in the 7 minute period, we had 7 clients waiting for the upstream rather than 265 times 7 cilents.

This is a relatively big win, but is also a drop in the ocean -- not much more than a second of latency shared among these clients.

The real win for us is that we don't ask facebook the same question 6 times per minute (one per thread).  Instead, we ask once every 57 seconds.  This is bigger in the grand scheme of things because it makes the facebook auth servers happier :)

On Nov 6, 2013, at 2:48 PM, Daniel Migault <[email-masked]> wrote:

> "- Under normal circumstances, when a record expires, all clients querying that record suffer (unnecessary) latency while the record is being re-queried upstream.  Fixing this was a convenient benefit."
> 

--
Brian Somers
[email-masked]

---

From: Daniel Migault <[email-masked]>
Date: Thu, 7 Nov 2013 06:53:28 +0100

Thanks for the complete answer. As you mention, this benefits not only the
end users but also authoritative and resolving servers (especially with
DNSSEC).

BR
Daniel

On Thu, Nov 7, 2013 at 2:02 AM, Brian Somers <[email-masked]> wrote:

> Using a sample of our US traffic over a 7 minute period, I see 112,044
> lookups of www.facebook.com out of a total of 4,081,834 queries (2.74%).
> Doing a lookup where our resolver is only missing star.c10r.facebook.com(which the
> www.facebook.com CNAME points at; the record with a 60 second TTL) takes
> 1.6ms.
> Given that our prefetch implementation actually charges the client that
> first queries the record in the last 3 seconds of its TTL, and given that
> we now cap our resolvers at 6 threads, this means that in the 7 minute
> period, we had 7 clients waiting for the upstream rather than 265 times 7
> cilents.
>
> This is a relatively big win, but is also a drop in the ocean -- not much
> more than a second of latency shared among these clients.
>
> The real win for us is that we don't ask facebook the same question 6
> times per minute (one per thread).  Instead, we ask once every 57 seconds.
>  This is bigger in the grand scheme of things because it makes the facebook
> auth servers happier :)
>
>> At OpenDNS, we implemented the same thing some months ago (without
>> knowing about this work) with the following differences:
>> We saw similar non-results in our graphs - at ~50 billion queries per
>> day, prefetch didn't change anything.... However, there were two other
>> issues addressed:

-- 
Daniel Migault
Orange Labs -- Security
+33 6 70 72 69 58

---

From: JINMEI Tatuya / 神明達哉 <[email-masked]>
Date: Fri, 15 Nov 2013 09:33:53 -0800

At Thu, 7 Nov 2013 06:53:28 +0100,

> end users but also authoritative and resolving servers (especially with

It's already noted in this thread, but: I'd note that's a benefit only
if the resolving server doesn't unify the same query from multiple
clients while it resolves it.  For those implementations (like ISC
BIND 9) that do this unification, prefetching would only increase
(although maybe marginally) external query/responses and only increase
the authoritative server's load.  So, this is not an inherent benefit
of prefetch itself, but one for a particular type of implementation.

I'm not saying this to insist prefetch is a bad idea, though.
Reducing worst-case latency for end clients, (again, perhaps
marginally) is an inherent benefit of prefetching for all types of
resolver implementations, for example.  I just wanted to clarify one
minor detail.

--
JINMEI, Tatuya

---

From: Brian Somers <[email-masked]>
Date: Mon, 18 Nov 2013 09:46:59 -0800

I would agree, perhaps wording it that the upstream lookup reduction is only realized
if there is a single cache shared among entities capable of doing upstream lookups
independently of each other.

--
Brian Somers
[email-masked]

---

From: Shane Kerr <[email-masked]>
Date: Fri, 22 Nov 2013 17:26:32 +0100

Brian,

[ sorry for coming back to this thread so late ]

On Wed, 6 Nov 2013 17:02:50 -0800
Brian Somers <[email-masked]> wrote:

> Using a sample of our US traffic over a 7 minute period, I see
> 112,044 lookups of www.facebook.com out of a total of 4,081,834
> queries (2.74%). That's 266 www.facebook.com queries per second.
> 
> Doing a lookup where our resolver is only missing
> star.c10r.facebook.com (which the www.facebook.com CNAME points at;
> the record with a 60 second TTL) takes 1.6ms. Doing a lookup where
> everything's cached, our resolver takes 0.7ms.
> 
> Given that our prefetch implementation actually charges the client
> that first queries the record in the last 3 seconds of its TTL, and
> given that we now cap our resolvers at 6 threads, this means that in
> the 7 minute period, we had 7 clients waiting for the upstream rather
> than 265 times 7 cilents.
> 
> This is a relatively big win, but is also a drop in the ocean -- not
> much more than a second of latency shared among these clients.
> 
> times per minute (one per thread).  Instead, we ask once every 57
> seconds.  This is bigger in the grand scheme of things because it
> makes the facebook auth servers happier :)

First, thank you for providing actual data! Much appreciated. :)

But... while the Facebook case is interesting, I am thinking you'll get
a lot more win from sites with long latencies. So, looking at #5 on the
top 1 million web sites list: baidu.com. From here I see latencies
between 300 and 500 msec. The TTL for the A record of baidu.com is 600
seconds.

It's not just China. Going to #16 on the list is wordpress.com, which
gives me times of 100 to 200 msec from all of its 6 (!!!) name servers.
At #29 ask.com has times between 90 and 200 msec. At #37 apple.com also
has times between 100 and 200 msec.

(I didn't check all of the names in between, since I expect that
yahoo.co.jp and yandex.ru and so on probably only care about "local"
traffic in the same way that Baidu seems to. I took special care to
single out Apple because I'm mean that way.)

The busy server + long latency is where we'll see the most win, IMHO.

Cheers,

--
Shane

p.s. What's the point of having a ton of name servers if they're all in
     California/Beijing/wherever? People, if you're going to have a lot
     of NS for your domain, please peer the network of at least one
     server in AMS-IX so I can get fast DNS resolution from here in
     Holland. Thanks! ;)