Subject: Submitted new I-D: Cache Digests for HTTP/2

From: Kazuho Oku <[email-masked]>
Date: Fri, 8 Jan 2016 16:17:16 +0900

Hello,

Yesterday, Mark and I have submitted a new draft named "Cache Digests
for HTTP/2."
https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/

The draft proposes a new HTTP/2 frame named CACHE_DIGEST that conveys
client's cache state so that a server can determine what should be
pushed to the client.

Quoting from the introduction of the I-D:
    HTTP/2 allows a server to "push" synthetic request/response pairs
into a client's cache optimistically. While there is strong interest
in using this facility to improve perceived Web browsing performance,
it is sometimes counterproductive because the client might already
have cached the "pushed" response.

My estimation is that in some cases a server may be able to push
hundreds of kilobytes of asset files critical to the rendering path
(e.g. CSS and script files) before the main content (i.e. HTML) is
returned from the application server, and having such fingerprint is
essential for determining what to push (for better
perceived-performance) and for determining what not to push (to not
waste the bandwidth).

A more detailed explanation of how it works can be found in the link
below, which describes the test I conducted using H2O HTTP/2 server's
cache-aware server-push feature (this I-D is essentially an effort to
standardize the feature).
http://blog.kazuhooku.com/2015/12/optimizing-performance-of-multi-tiered.html

You may be also interested in the following slides explaining how the
feature is implemented in H2O version 1.5.
http://www.slideshare.net/kazuho/cache-awareserverpush-in-h2o-version-15

Source code of the Golomb-Rice encoder used in the cache-aware
server-push of H2O can be found at:
https://github.com/kazuho/golombset/ (note: it encodes "N" and "P"
differently from the steps defined in the I-D since in the H2O's
implementation the server is capable of maintaining "N" out-of-band).

Please let us know how you think about the proposal.  Thank you in advance.

-- 
Kazuho Oku

---

From: Alex Rousskov <[email-masked]>
Date: Fri, 8 Jan 2016 11:33:37 -0700

> Please let us know how you think about the proposal.

If possible, I recommend removing Draft language that makes (or appears
to make) your feature specific to optimizing push traffic to user
agents. Cache digests are useful for many things. Optimizing push
traffic to user agents is just one use case. For example, Squid proxies
already use Cache Digests (based on Bloom Filters) to optimize
cache-to-cache communication in caching hierarchies [1,2].

  [1] http://www.squid-cache.org/CacheDigest/cache-digest-v5.txt
  [2] http://wiki.squid-cache.org/SquidFaq/CacheDigests

I suspect it is possible to define the new CACHE_DIGEST frame without
adding artificial restrictions on its use. Let the agents sending and
receiving that frame decide what use is appropriate between them while
following some general guidelines.

Since there are already two cache digests formats (based on Bloom
filters and based on Golumb-coded sets), we should expect a third one.
Have you considered allocating the first few response octets to specify
the digest format?

> A CACHE_DIGEST frame can be sent from a client to a server on any
>    stream in the "open" state, and conveys a digest of the contents of
>    the cache associated with that stream

Perhaps I am missing some important HTTP/2-derived limits here, but the
"cache associated with a stream" sounds too vague because HTTP caches
are often not associated with specific streams. Did you mean something
like "the cache portion containing shared-origin URIs?"

>    servers ought not
>    expect frequent updates; instead, if they wish to continue to utilise
>    the digest, they will need update it with responses sent to that
>    client on the connection.

Perhaps I am missing some important HTTP/2 caveats here, but how would
an origin server identify "that client" when the "connection" is coming
from a proxy and multiplexes responses to many user agents?

>        1.  Convert "URL" to an ASCII string by percent-encoding as
>            appropriate [RFC3986].

There are many ways to percent-encode the same URI. This step must
define a single way for doing so. Besides case insensitive parts and the
decision of what characters to [un]escape, please do not forget about
trailing slashes, URI fragments, and other optional parts. This is
critical for interoperation!

>    MUST choose a parameter, "P",
>    that indicates the probability of a false positive it is willing to
>    tolerate

For clarity, please detail what you mean by a "false positive" in this
context. It may also be useful to mention whether the digesting
algorithm may create false negatives.

> 7.  Write log base 2 of "N" and "P" to "digest" as octets.

The wording is ambiguous: Store log2(N) and then store log2(P)? Store
log2(N&P)? Store log2(N) and then store P? I suspect it is the latter
and recommend splitting step #7 into two steps, one step per number.

BTW, why note store the actual value of N?

> 7.  Write log base 2 of "N" and "P" to "digest" as octets.
...
> 8.  Write "R" to "digest" as binary, using log2(P) bits.

It is not clear how a number should be written/encoded. Different
programming languages and different systems store/represent numbers
differently, so I would expect the Draft to specify encoding precisely.
Sorry if I missed that detail.

The draft appears to be missing a section documenting how the digest
recipient can test whether the digest contains a given URI.

Please consider an additional Security Consideration: Origin servers are
expected to store digests so that the stored digests can be consulted
when pushing traffic. Most origin servers will store digests in RAM. A
malicious client may send a huge digest as a form of a DoS attack on a
naive server that does not validate digest sizes. Malicious client(s)
may send many small digests as a form of a (D)DoS attack on a naive
server that do not control the total size of stored digests.

Thank you,

Alex.

---

From: Martin Thomson <[email-masked]>
Date: Sat, 9 Jan 2016 06:57:19 +1100

> Please let us know how you think about the proposal.  Thank you in advance.

This is good stuff, I'd like to see it validated, but it could be the
thing that makes server push viable for a lot of servers.

Like Alex, I'm interested in other applications than the primary one
you describe.  I don't think that you need to remove text about server
push, but you should avoid making statements that restrict its use.  I
recommend that you define the basic mechanism and then describe its
application to your primary use case.

I think that the draft is lacking a description of how to consume the
value.  That's particularly relevant as you get to the tail of the
value.

I wonder if we might be able to pack N and P a little more tightly by
constraining their range just a little.  And not only because it saves
a byte: you also want to limit the damage someone can do with the
header field and small P would bound the size of the data.  Similarly,
it will simplify implementations considerably if they can store
integers in uint64_t, which is possible if log2(N) + log2(P) doesn't
exceed 64.  I don't see any case for probabilities of 1/2^255 or 1/1;
likewise sets of 1 resource aren't interesting, and sets of 2^255
resources is a shade on the massive size.  2^32 is probably fine for
both.

"key" modulo ( "N" * "P" ) should instead be constructed by truncating
the hash to log2(N) + log2(P) bits and converting to an integer.

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 9 Jan 2016 15:27:14 +0900

Hello,

> Have you considered allocating the first few response octets to specify

Thank you for the suggestion and the info.  I did not know that Squid
was using Bloom filters for such purpose.

If we are to generalize the proposal to support other purposes such as
exchanging cache states between proxies, I think we should also
consider of defining a way for sending a digest divided into multiple
HTTP/2 frames in case the size of the digest exceeds 16KB, in addition
to providing space to define which encoding is being used.

Or if there is no immediate demand to use an encoding other than
Golomb-coded sets for sending a small-sized digest, then we can add a
sentence stating that:

* sender of a CACHE_DIGEST frame must set its flags to zero
* receiver of the frame must ignore if its flags are not set to zero

, and if such demand arises, define new flags to extend the semantics.

For the purpose of optimizing HTTP/2 push, my assumption has been that
it is unlikely for a client implementation to want to send a digest
that does not fit into INITCWND (therefore the proposal does not
define a way to send multi-frame digest).  Also, Golomb-coded sets
will be the only practical choice, the size of the digest will become
significantly larger if Bloom filter was chosen (in case false
positive rate is set to 1/256, it will be about 8x as large).

> like "the cache portion containing shared-origin URIs?"

Yes.

> from a proxy and multiplexes responses to many user agents?

Proxies implementing HTTP/2 ignores extensions that it does not understand.

Therefore, it wouldn't be a problem if a client sends a CACHE_DIGEST
frame to a HTTP/2 proxy that does not understand it; it will simply be
ignored.

Proxies understanding the frame can simply transfer it to the upstream
server; or it can merge the status of its cache into the digest before
sending it upstream in order to save the bandwidth.

> critical for interoperation!

Thank you for pointing that out.

RFC 3986 section 6 defines how to normalize URIs.  I agree that we
should state explicitly which section should be applied before
calculating the hash.

IMO section 6.2.2 (Syntax-Based Normalization) and 6.2.3 (Scheme-Based
Normalization) are the ones that must be applied.

> and recommend splitting step #7 into two steps, one step per number.

It's log2(N) and then log2(P).

I agree to your recommendation to split the description into two steps.

> BTW, why note store the actual value of N?

In order to disallow the use N that is not power of 2.

As show in step 4, we need to calculate sha256(url) modulo (N*P) for
every URL.  The calculation is not only required on the client side
for generating the digest, but also on the server side on determining
if a given URL is already likely to be cached by the server.

If both N (in addition to P) is a power of two, then the modulo
operation can be a bit operation.  But if not, it will be very
computer intensive, might become an attack vector.

> recipient can test whether the digest contains a given URI.

Thank you for the advise.  I agree that the description on how to
encode the bits should be more precise (probably like that of HPACK),
and that how to use the digest should be explained.

> server that do not control the total size of stored digests.

Thank you for bringing it up.  I agree that such statement should exist.

-- 
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 9 Jan 2016 15:45:16 +0900

> thing that makes server push viable for a lot of servers.

Thank you for the positive response.

> application to your primary use case.

That approach sounds very reasonable.

Considering the fact that there are specific requirements to cache
digests for optimizing HTTP/2 push (i.e. the digest should be small /
the digest may be sent before the first HTTP/2 frame arrives from the
server), I think it would be appropriate to keep the description of
the primary use case.

> value.  That's particularly relevant as you get to the tail of the

Agreed.

> resources is a shade on the massive size.  2^32 is probably fine for

Thank you for the thoughtful suggestion.  Limiting the value of N and
P to be below 2^32 sounds like a very good idea.

> the hash to log2(N) + log2(P) bits and converting to an integer.

Agreed.  Defining the operation as truncation and conversion to an
integer will be more precise.

Thank you for the advices.

-- 
Kazuho Oku

---

From: Alex Rousskov <[email-masked]>
Date: Sat, 9 Jan 2016 00:27:30 -0700

> to providing space to define which encoding is being used.

This is an important caveat that I have missed! Squid Cache Digests are
often many megabytes in size... Perhaps the Draft should be renamed to
"Small Cache Digests for HTTP/2" to emphasize that the proposed
mechanism is not applicable to large caches?

> , and if such demand arises, define new flags to extend the semantics.

It feels wrong to use frame flags to specify digest _encoding_, but
perhaps that is appropriate in HTTP/2 context.

> Also, Golomb-coded sets

I would not limit the possibilities to Bloom filters and Golomb-coded
sets. For example, I can imagine a client talking to a server with a
small set of *known-a-priori* objects and using a small 1:1 bitmap to
reliably represent the current client cache digest.

You only need to "waste" an octet to open up support for other digest
formats without changing the overall semantics of the "small cache
digest" feature...

> server

Yes, but how would an origin server identify "that client" when the
"connection" is coming from a CACHE_DIGEST-aware proxy and multiplexes
responses to many user agents served by that proxy? AFAICT, the server
cannot know whether the responses sent "on the connection" are going to
be cached by the proxy (and, hence, should not be pushed again) or are
going to be forwarded to the user agent without proxy caching (and,
hence, should be pushed again in case other user agents need them).

IIRC, from terminology point of view, the proxy is the "client" in this
context so there is no problem in the current Draft wording if that is
what you meant. There may be a problem if, by "that client", you meant
"that user agent" instead.

Please note that I am _not_ saying that there is a protocol bug here. I
am just noting that it is not clear what should happen when proxies
multiplex streams from different user agents to the same origin server,
and whether there are some specific strategies that caching and
non-caching proxies should deploy to maximize the savings. There seems
to be at least three cases to consider: CACHE_DIGEST-unaware proxies,
aware caching proxies, and aware non-caching proxies.

Thank you,

Alex.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 Jan 2016 10:36:12 +1100

> server), I think it would be appropriate to keep the description of

I definitely agree.  We understand this use case, and it doesn't make
sense to solve problems we don't understand well.  Let's at least make
sure that it works for one use case :)

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 12 Jan 2016 10:50:22 +0900

> perhaps that is appropriate in HTTP/2 context.

Sorry for my wording, what I wanted to say is that we can add a flag
to identify that the payload is using a new format, that includes the
ID of the encoding together with other things that are required to
support such extension.

> formats without changing the overall semantics of the "small cache

The question is if only including an octet and keeping other semantics
the same is fine to support other purposes.  To me the answer is
uncertain at this point, I am afraid if such octet will actually be
used.  But this is my thoughts only, I am open to making the spec.
more generic if the general tone is that I should.

> aware caching proxies, and aware non-caching proxies.

Thank you for bringing up the case of a CACHE_DIGEST-aware proxy that
multiplexes requests from many clients.

As you pointed out, it is not sensible for a such proxy to simply
transfer the digest value sent from one client to the server.  What it
should do is:

* send the digest of proxy's cache to the server
* store the pushed resources within the proxy's cache
* when the server's response includes a `Link: rel=preload` header,
and if the resource specified for preload exists in the proxy's cache,
push that resource to the client

The performance may not be optimal when compared to a
CACHE_DIGEST-aware proxy that does not multiplex requests from
multiple clients, but it would be better than the case of a
CACHE_DIGEST-unaware proxy.

-- 
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 18 Jan 2016 09:18:49 +0900

FWIW, I have implemented a simulator of the I-D, which is now
available at https://github.com/kazuho/h2-cache-digest.

When running `make`, it generates a command named
`h2-cache-digest-00`, which can be used as a simulator for the draft
version 00.

It accepts three mode: `--encode`, `--decode`, `--push`; each mode can
be used for encoding / decoding the frame as well as a simulator on
the server-side checking where if a URL should be push (or not be
pushed in case the resource is expected to be cached by the client).

A synopsis of how to use the command can be found on
https://github.com/kazuho/h2-cache-digest#h2-cache-digest-00

I hope this will help people understand how the draft can be
implemented.  Thank you in advance.

-- 
Kazuho Oku