Add cache aware server push

[frank-dspeed]

To optimize the responsiveness of a website, I use normal Enterprise Tech like this maybe your interested into that. it is desirable to push assets (e.g. CSS and/or JavaScript files) that block the page rendering process when and only when such files do not already exist within the client's cache. However, the specifications do not define a way to determine whether if a resource is already cached.

This issue proposes of using a cookie containing a probabilistic data set as an approximation for determining the cache state of the client, and using it for restricting server-push - i.e. only push the asset files that are unlikely to be cached.

if you want i could raise more issues like this we got web servers that outperform nginx by more then 100% in all disciplines.

this is only for your personal education you don't need to adapt that feature because i will port all our existing tech to steal-server. But this would be good for a keynote speak at the next contributors meeting ;)

Basic Design

• use a single cookie that stores a Golomb coded set as to mark if the assets are cached
• key for the set will be calculated as key(filename)=sha1(filename + etag(filename))
• for each HTTP2 connection, the server maintains the value of the set
  • set is initialized as empty
  • when receiving the cookie, the value of that cookie gets set.
  • when starting to send a response, mark the set using a key calculated using the rule above, and send set-cookie header containing the value.
  • when application logic triggers a server-push, check if the to-be-pushed content is marked within the set, and if marked, ignore the trigger. If not, push the content to the client at the same time updating the value of the set using the rule above.
• server may also maintain a set that maps all the existing files, and use the set to clear the keys of the incoming set that do not exist (i.e. means that the corresponding file has either been removed or updated), before copying the value to the internally maintained value

By applying this design for restricting server push, the only drawback of using server push will become when the cookie on the client expires before the asset cached in the client's cache expires. In other words, the design will work effectively if such case is unlikely.

Notes

Since HTTP2 multiplexes the HTTP requests over a single stream, it has become possible for the web server to expect in which order the client receives the responses (i.e. we can safely say that: if the client has received the headers of response A, then it must have received the headers of response B that has been sent prior to A). The design takes advantage of the property.

A good read on Golomb coded set is this blogpost http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters. The only issue the doc has is how M of Golomb coded is calculated; theoretically it should use median instead mean value.

Additional note not verifyed

just encoding the raw deltas gives 26 bytes (208 bits),

• slightly greater than Golomb results,
• will most likely have better lookup performance.
• With that encoding you could halve lookup time by scanning backwards from an index (or the maximum, if you don't create an index).

Of course, you'd have to have a system for handling spans greater than 256, in this kind of system. If it's very uncommon, you could just encode skip bytes (such as 0 for skipping 255 forward, so 0+1 encodes a span of 256).