Re: draft-ietf-httpbis-cache-digest-00 comments

Kazuho Oku <> Thu, 14 July 2016 07:29 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 85AC812B071 for <>; Thu, 14 Jul 2016 00:29:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -8.308
X-Spam-Status: No, score=-8.308 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RP_MATCHES_RCVD=-1.287, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id SKqJzB1jptQL for <>; Thu, 14 Jul 2016 00:29:26 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A241C12B050 for <>; Thu, 14 Jul 2016 00:29:26 -0700 (PDT)
Received: from lists by with local (Exim 4.80) (envelope-from <>) id 1bNb1A-0005oj-Lj for; Thu, 14 Jul 2016 07:25:08 +0000
Resent-Date: Thu, 14 Jul 2016 07:25:08 +0000
Resent-Message-Id: <>
Received: from ([]) by with esmtps (TLS1.2:DHE_RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <>) id 1bNb14-0004Yh-PW for; Thu, 14 Jul 2016 07:25:02 +0000
Received: from ([]) by with esmtps (TLS1.2:RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <>) id 1bNb0u-0001Jo-Hw for; Thu, 14 Jul 2016 07:24:58 +0000
Received: by with SMTP id o80so100861327wme.1 for <>; Thu, 14 Jul 2016 00:24:32 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=W58+sqofkDA2ludI2UxTypJqPlMMmE/JOkmZLc1pxEY=; b=XwHpR+ItYzRTst41sC13jQsgaDpHxWgf/zdIJ8UIq7q2WMB/1lJYnm8zP6A4Plw4Tw 3rPFgbqG7VDHsbLb/xL2VjYG5NS5Kw5SB11LpBEPXqfFd8dO/Bpus3m7oCAZml2A12DV Ih18LdH7810APnB9jA+o7904v9tCuhht+Fzp7bEdfeA59n3cgG8/s8MuawUGxuX6y4I3 iWkQtj5X4XsTgCfq5ufN7MMkJD/9DnFl3gWcMo4APAguxjbGDr2UjrlgrRqtOFe1duNP 7KpGmqB0dU5DbUeh8CHxtUFlkx8CLMFO6oiTcb1Sj5EEKtkKVIgQ0iJNRaJccj6MAthn mT8A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=W58+sqofkDA2ludI2UxTypJqPlMMmE/JOkmZLc1pxEY=; b=D1nwHAiBQGtMVcLhMBHYCzOteJL/h3QooTFIgruHNyZ4dWtYHgIbM2u39QtrfafW9x 1Solhf9yym3AvLY8Te4u8h1FsFpwo6XxNvYVRj0XIK2DVA0ReZxD7nH0OumZ27hb8wAC mZHWOoHKWrhLzBmco85Ps4NIAo+qhK9oIeM/AffKsWW+HMx71JVjwE+GYIrgdmz9yBJK q7qtTczmyqF1cYna0r5zfcgNvyIJf4ZiUX7ARUpqbGZlmHZVFsIutT0FGCmKvPSd3LYW FwhNQ/1yKP+yWfr2KbJGyzTi4A+qNrmwz6eUt9E5oDx3HR9QiJmpBAuuFWC7GoyI8PCc 9eKA==
X-Gm-Message-State: ALyK8tJWxkSAGYx3gjrBP+/rT6gYeT6225kwtHu8ZsNyyOvuaDE4ZwFoQQKTOWuck5xMW4q5aNr7EjD185BL5A==
X-Received: by with SMTP id f127mr14604076wmf.90.1468481065667; Thu, 14 Jul 2016 00:24:25 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Thu, 14 Jul 2016 00:24:24 -0700 (PDT)
In-Reply-To: <>
References: <>
From: Kazuho Oku <>
Date: Thu, 14 Jul 2016 16:24:24 +0900
Message-ID: <>
To: Martin Thomson <>
Cc: HTTP Working Group <>, Mark Nottingham <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Received-SPF: pass client-ip=;;
X-W3C-Hub-Spam-Status: No, score=-5.5
X-W3C-Hub-Spam-Report: AWL=-0.817, BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: 1bNb0u-0001Jo-Hw 058094d91e3fd145a8007cd4cb70f5f6
Subject: Re: draft-ietf-httpbis-cache-digest-00 comments
Archived-At: <>
X-Mailing-List: <> archive/latest/31964
Precedence: list
List-Id: <>
List-Help: <>
List-Post: <>
List-Unsubscribe: <>


Thank you for your comments.

The comments below are mine, and Mark might have different opinions.

2016-07-13 11:18 GMT+09:00 Martin Thomson <>:
> As I've said before, this is really interesting work, I'm very much
> interested in seeing this progress.  However, I found a lot of issues
> with the current draft.
> The latest version seems to be a bit of a regression.  In particular,
> the addition of all the flags makes it a lot more complicated, and I'm
> already concerned about managing complexity here, especially since
> this is an optimization.
> The draft doesn't actually say where this frame should be sent - on a
> stream that carries a request, or on stream 0.

In section 2.1 the draft states: A CACHE_DIGEST frame can be sent from
a client to a server on any stream in the “open” state. My
understanding is that it would be enough to indicate that the frame
should be sent on a stream that carries a request as well as when it
should be sent.

> This is important
> because there are several mentions of origin.  For instance, the new
> RESET flag talks about clearing digests for the "applicable origin".
> That establishes a large point of confusion about the scope that a
> digest is assumed to apply to; by their nature, this isn't necessarily
> fatal, until you want to talk about RESET and COMPLETE.
> To up-level a bit on this general issue, I'd like to see a better
> formulated description of the information that clients and servers are
> expected to maintain.  There seem to be multiple objects that are
> stored, but I'm not sure what scope they are maintained in; is the
> scope an origin?


> Assuming a particular scope, are there two objects, or four?  That is,
> is there could be four stores:
> 1. assumed fresh by URL
> 2. assumed fresh by URL and etag
> 3. assumed stale by URL
> 4. assumed stale by URL and etag
> Or are 1+2 and 3+4 combined?  The definition of RESET implies that all
> four stores are cleared.  The definition of COMPLETE implies that only
> 1+2 or 3+4 are affected.

There are four objects, which are grouped into two.

Your reading is correct that RESET flag clears all of them, and that
the COMPLETE flag implies to either 1+2 or 3+4.

> The draft doesn't talk about URL normalization.  That is a risk to the
> feasibility of this; fail to do something sensible here and you could
> get a lot of spurious misses.  Given that it is just an optimization,
> we don't need 100% agreement for this to work, but saying something is
> probably wise.  We can probably get away with making some lame
> recommendations about how to encode a URL.  Here's a rough cut of
> something that didn't make the draft deadline this time around:

Thank you for the suggestion.

I have a mixed feeling about this; in section 2.2.1 the current draft
says "Effective Request URI of a cached response" should be used.

So the cache digest would work without URL normalization if both of
the following conditions are met:
* if the client caches a response NOT normalizing the request URI into some form
* if the server looks up the cache digest using a URI that a client would send

For example, if a HTML with a script tag specifying /%7Efoo/script.js
is served to the client, then the draft excepts the client to use that
value (including %7E) to be used as the key, and that the server
should test the digest using the exact same form.

The pros of this approach would be that it would be easier to
implement. The cons is that it would be fragile due to no

And I agree with you that in case we go without normalization we
should warn the users that the paths should be same in terms of

> I don't see any value in COMPLETE.  Even if we accept that there is
> only one connection from this client to this server, the benefit in
> knowing that the digest is complete is marginal at best.  Is there
> just one extra resource missing, or thousands.  As such, it changes
> the probability by some unknown quantity, which isn't actionable.

I do find value in COMPLETE.

For a server with the primary goal to minimize B/W consumption and the
second goal to minimize latency, it is wise to push responses that are
known NOT to be cached by a client.

That's what the COMPLETE flag can be used for. Without the flag, a
server can only tell if a response is already cached or _might_ by

> Can a frame with the RESET flag include a digest as well?

Yes. That is the intention of the draft.

> N and P could fit into a single octet.  Since you are into the flags
> on the frame anyway, reduce N and P to 4 bits apiece and use flags to
> fill the upper bits as needed.  But I don't think that they will be
> needed.  At the point that you have more than 2^16 entries in the
> digest, you are probably not going to want to use this.  Even with a
> tiny P=3 - which is too high a false positive probability to be useful
> - with N=2^16 you still need 32K to send the digest.  You could safely
> increase the floor for P before you might need or want higher bits
> (and make the minimum higher than 2^0, which is probably too high a
> false-positive probability in any case).

I would argue that P=1 would still be useful in some cases. For
example if 10 resources are missing on the client side, it would mean
that a server can detect 5 of them missing and push them in case P=1
is used.

And considering the fact that we would nevertheless have read-n-bits
operation while decoding the Golomb-encoded values, I do not see
strong reason to squash N and P into a single octet.

> Is the calculation of N really round(log2(urls.length)).  I thought
> that you would want to use ceil() instead.  Is the word "up" missing
> from step 1 in Section 2.1.1?

That draft has intentionally been written to use round.

The numbers that matter when using Golomb-coded sets are:

    P: divisor used to divide bits that are unary-encoded and binary-encode
    N*P: range of the encoded values

For efficiency, both P and N*P must be powers of 2.

To encode effectively, the real probability should be near to the
value of P. And that in turn means that N*P should be
round_to_power_of_two(urls.length * P) rather than
round_up_to_power_of_two(urls.length * P).

> The draft never actually mentions that it uses [Rice-]Golomb-coding
> until the appendix.  Including a reference to the Rice paper would
> help people implementing this understand where this comes from, as
> well as leading them to being able to find the relevant research.
> (nit: Spelling Golomb correctly would help here.)

I agree. Thank you for noticing that!

Kazuho Oku