Phoenix: Add support for a cache aware H2 PUSH_PROMISE with CASPer

[idyll]

In order to complete H2 support in Phoenix we need to support a mechanism for the server to push or hint resources. There are two mechanisms for this now: Early Hints and Push Promises.

Initially I was hoping to add support for Early Hints but during the process it became apparent that it may be months before any of the major web browser support early hints. (This is based on a conversation on twitter with Ilya.)

That means at least initially we need to support Push Promise as well.

I've looked at how Rails has added support for Push Promise (I know they say that they are doing early hints, but that's not 100% accurate. They are using h2o to convert an early hint from puma into a push promise.) We can do the same thing for anyone that wants to proxy through h2o like rails does. H2O is using a technique called CASPer when they store a representation of a list of assets on the client in a cookie.

Their implementation is here:
https://github.com/h2o/h2o/blob/master/lib/http2/casper.c

As discussion of it is here:
https://h2o.examp1e.net/configure/http2_directives.html#http2-casper

TL;DR they are using golomb compressed sets (https://www.imperialviolet.org/2011/04/29/filters.html) aka a bloom filter.

So to support Early Hints and Push Promises we need:

1. a dependency for a Bloom filter. (maybe https://github.com/gmcabrita/bloomex)
2. functions to read and write the cookie.
3. functions to get a list of the assets that should be pushed for a page.
4. a function that takes a list of assets and the cookie and determines which assets to push.
5. a function that connects this all into a push promise.
6. a function that uses the list from 3 to do early hints.

I think we should support them both. This gives the end use maximum flexibility and there's very little extra effort on top of Push Promise needed to support Early Hints.

I am hoping to gather some feedback on this and then I will start working on a PR.

Plug already has support for Push Promise (but there's going to be a Cowboy fix before it fully works) and there's an open PR for Early Hints support.

[Gazler]

@idyll Thanks for opening this proposal.

The solution by h2o is neat. There's another proposal for caching with server push https://datatracker.ietf.org/doc/draft-ietf-httpbis-cache-digest/?include_text=1 which is somewhat related this.

From an API point of view, if we already have server_push(conn, "foo.css") then we'd maybe want something like:

# Cache is default
server_push(conn, "foo.css")

# Implementation is transparent
server_push(conn, "foo.css", cache: false)

# Instead of
server_push(conn, "foo.css", casper: false)

This will allow us to use a different cache strategy in the future.

If a user wants to use early hints then they would have to use a different function, such as early_hint(conn, "foo.css)

With the way server_push currently works, the trickiest part of the implementation would be:

functions to get a list of the assets that should be pushed for a page.

Currently the assets to be pushed are not known ahead of time, they are pushed at the point of the server_push function.

[idyll]

Looking at the proposal for caching you mention above it requires client side changes - the client (browsers) will need to send up a frame that provides cache information to the server.

So I suspect we will need CASPer for some time before we can move over to it. I agree though, we should abstract the details away from the client. Probably with a note that mentions the client will need to accept cookies to use the cache.

Long term, I would like to see the browser support Early Hints as it works correctly even when "private mode" is on for a browser -- as opposed to Push Promise which will either rely on a cookie that the use can clear/block or the caching proposal above which notes that in private mode clients shouldn't send the frame.

[josevalim]

Using a bloom filter is a great idea. The issue is that we need to serialize the bloom filter into the cookie. We can ping @gmcabrita for discussions although I think serializing the Elixir data structure will take too much space and be expensive in terms of encoding/decoding.

One approach I can think of is to have a hash table of up to 1024 entries of 10 bits where those entries are encoded in base32, giving us exactly 2 bytes per entry. This gives us the option to track 1024 entries in 2kbytes.

Alternatively we could use a hash table of up to 256 entries of 8 bits, where those entries are encoded in base16, giving us exactly 2 bytes per entry. This gives us the option to track 256 entries in 512bytes.

Both cases should comfortably fit in the cookie of all browsers and we can lookup the data in log2(n).

[josevalim]

@idyll so basically our best option is server push with cache because browsers won't handle early hints over http 2 anyway?

[idyll]

Chrome, Webkit and Firefox all have open issues. So it's coming. We just don't know when. It would probably speed them up if they have more test implementations.

As for the cache, the h2o implementation needs 13 bits for approximately 100 files with a 1/100 chance of a false positive. I just don't know what the performance hit is going to be.

[idyll]

And the risk of not pushing a file is very minor I should add. If we do hit a false positive it just means that the user gets the file after the page is parsed, not before.

[josevalim]

As for the cache, the h2o implementation needs 13 bits for approximately 100 files with a 1/100 chance of a false positive. I just don't know what the performance hit is going to be.

@idyll that's so compact I can't even argue against it. The only issue though is that we will probably need a data structure designed for serialization, i.e. that can have its bitarray easily converted to a binary, so I don't think the existing bloom filter will work out of the box.

[idyll]

I think you're right @josevalim.

So the question for you is where does that code live? It's probably something that should live with whatever we use for a bloom filter. But maybe that needs to live in the Phoenix or Elixir orgs? Thoughts?

[josevalim]

@idyll the "binary bloom filter" can be inside of Phoenix or outside as a separate package. The integration with the bloom filter will be part of Phoenix for now. Nothing goes to plug so far as everything is quite new and we don't know how general those things are yet.

[josevalim]

@idyll btw, casper uses 6.6bits per entry on average without decoding (which implies an extra cost of 33%). The 100 entries is the false positive frequency.

GCS seems to be really straight-forward to implement and we can implement in a streaming fashion (i.e. we decode the data up to the point we need it).

[Gazler]

A cuckoo filter may be worth investigating too, it is faster for lookup, but slower on insertion as the data set grows.

This page has some good comparisons https://bdupras.github.io/filter-tutorial/

[josevalim]

@Gazler i looked at cuckoo but it has a more complex structure, which means more work when decoding/encoding. GCS is interesting because the data structure is literally a bit array where each number is encoded using Golombo encoding. All we need to do serialize it and deserialize it is to apply Base64 and this can be done in a streaming fashion (if we want to).

[josevalim]

Here is an accessible description of GCS: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters

[josevalim]

Actually, even if we use a cookie, we can run into an issue where two requests would overwrite each other cookies, causing us to push the data again. H2O solves this because as a proxy they can centralize everything in the handler process, see discussion here: https://github.com/h2o/h2o/issues/421

We could do this by using custom Cowboy handler but then the price of implementing this feature is just too high.

And even if we did, we would have issues when running in two different tabs. So I think for now we should continue to test and streamline the low-level early hints and push experience in Plug and we will add this to Phoenix later on.

[josevalim]

Thanks a lot @idyll for pushing this forward. For now let's focus the Plug APIs work with Cowboy and we will have those available for those willing to try things out. However, for now, it is probably not the best idea to push those in Phoenix until everything is a bit more battle tested.

[idyll]

If none of this is practical then there is still one thing we can try to help a little.

The header is tossed into a different frame than the body of H2 pages. (The body can have multiple frames.)

If we get the lists of assets for the page we can add them as link headers to the page itself.

In my testing, Chrome seems to look at this header list and fetch the resources. (I think Safari too).

I am going to separate the head from the body in the response and see if there is any speed up.

I think that any approach is going to need the list of assets for a page.

[josevalim]

@idyll i thought about this approach but given the headers are sent alongside the body, the gains we would see here would be very minimal compared to having those same links at the top of your <head>. I don't think the complexity in introducing a stateful helper would be worth in this case, unfortunately. :(

[idyll]

@josevalim I've been thinking more about pushing assets.

I think that a single tracking value in a cookie is probably good enough. The value would be the version of the app. If it exists and matches, assume assets are pushed. If it does not push the assets again and update the cookie.

All assets are typically in the default layout. Just worry about those assets. Maybe do this in a plug?
What if it's wrong?

and you need assets: fine, you just get them a bit later, after the page is parsed. just like right now. this is where we are anyways.
and you already have them: still fine, the browser will reset the stream. we should try to minimize this case but the assets aren't resent, just a frame that is a request for the client to download them.

It's super minimal. It should work most of the time. If it doesn't work it's not a big deal because the likely failure case is the same as not pushing the assets to begin with.

I think it's a good place to start testing...

Thoughts?

[josevalim]

@idyll the issue with cookies is how we are going to handle concurrent access. We will end-up overwriting the cookie on concurrent requests causing the same asset to be pushed multiple times. Unless we have a cookie name per layout? So basically we would be able to push whatever goes in the first rendering of the page, which is likely enough.

What do you think @Gazler?

[Gazler]

I think if the worst case scenario is that it works the exact same way it does at the moment, then there isn't much of an issue. The most important assets are the ones that are included in every page, as long as concurrent requests overwrite the cookie in a way that preserves those values (which it should, since they would be on all pages) then I think we can try it out and see how it works.

Is this something that could perhaps be built outside of Phoenix initially so we can test it out?

[idyll]

There's nothing Phoenix specific about most of this. But I am not sure how we want to get the list of assets to push.

Instead of having to parse templates I'd almost rather get the list of fonts, css, and js and push that. I would ensure that the push promise comes back before the page. Really css and fonts are the biggest deal because you want them as soon as the page is ready so that it displays correctly. The best way to do this isn't obvious to me.

For testing it out I'd be inclined to just make a static list of files, but then we need to deal with the hash the asset pipeline applies to them when compiled.

The rest of this should be easy to keep separate from Phoenix.

[josevalim]

@idyll I think the implementation is small enough that coupling with Phoenix is fine and it will yield the best user experience. Basically:

1. add something like static_push(...) that checks if a cookie was set and, if not, it pushes
2. static_push also stores the pushed assets in the process dictionary
3. We have a register_before_send that checks if something was under said process dictionary and then send the cookies

[josevalim]

I will go ahead and close this as it is no longer high priority while the state in browsers improve. Someone willing to tackle this on the side is very welcome as the features are in plug already. :)

[idyll]

Now that the changes to plug are merged in, this is next on my list.