Subject: Re: [httpwg/http-extensions] Enabling O(1) removal from digest (#268)

From: HTTP issue updates <[email-masked]>
Date: Thu, 17 Nov 2016 05:09:09 -0800

Thank you for opening the issue. I think we should adopt a method that can be implemented by web browsers easily, as long as the digest remains fairly compact. Regarding the size of the digest, I have no objection for choosing Cuckoo Filters.

However, I am not sure if the proposed method would work as expected.

> Browsers can calculate a per-host digest once, then keep updating it as resources are added to the cache as well as when resources are removed from the cache.

There are two digests (i.e. fresh and stale) for every host. You need to update the digests when the state of a cached response changes from fresh to stale, by evicting the entry from the fresh digest and inserting it to the stale digest.

Is that possible?

Also, if it is possible to maintain a per-origin Cuckoo Filter that is kept in sync with the cached resources, I think it would also be possible to maintain a per-host list of cached URLs as well.

Anyways, let me state that I'm very delighted to see people looking into how Cache Digests can be implemented within the web browser. I was considering of polishing up my ServiceWorker implementation, but maybe I should spend time in looking into the browsers as well.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/268#issuecomment-261242398

---

From: HTTP issue updates <[email-masked]>
Date: Thu, 17 Nov 2016 05:28:55 -0800

> There are two digests (i.e. fresh and stale) for every host. You need to update the digests when the state of a cached response changes from fresh to stale, by evicting the entry from the fresh dig…

Hmm, that would indeed increase complexity as I believe the cache is not aware of resources going into the "stale" state unless they're queried. (@cbentzel & @mcmanus - please correct me if I'm wrong).

Is there any reason we can't use a single digest with URL+ETag (so use the ETags also for fresh resources) to avoid that complexity? Are there any downsides to that?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/268#issuecomment-261246217

---

From: HTTP issue updates <[email-masked]>
Date: Thu, 17 Nov 2016 06:05:51 -0800

@yoavweiss 
> Is there any reason we can't use a single digest with URL+ETag (so use the ETags also for fresh resources) to avoid that complexity? Are there any downsides to that?

It is true that you could use URL+ETag as a key of fresh digests (though server implementations might become slightly complicated).

However, it is still desirable to be able to distinguish if whether a resource is freshly cached or stale-cached, since the server behavior needs to be different for the two. For freshly cached resources, there is no need to push anything. For stale-cached resources, the server needs to push 304.

If the client sends a single digest covering both freshly and stale-cached resources, then the server would need to either push nothing for both of them (which means that client would issue conditional requests for stale-cached responses that it need to use), or push 304 for both of them (which means that the server would send 304 for even the freshly cached resources).

Note also that we haven't agreed on whether if sending a digest of stale responses is worth the extra bandwidth, or how we should push 304.

Last time I looked into my Firefox's cache, the number of cached objects were as follows:

|domain|total objects|fresh objects|
| --- | --- | --- |
|*.facebook.com|2273|790|
|*.google.com|1003|373|

As you can see, fresh objects consists about 1/3 of the total objects cached for a domain. Sending a digest for all objects would roughly triple the size of the digest from when we just send the digest for freshly-cached objects.

Considering the fact that assets critical to the rendering path is likely marked as fresh, it would make sense to just send the digest for freshly cached objects.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/268#issuecomment-261254539

---

From: HTTP issue updates <[email-masked]>
Date: Fri, 18 Nov 2016 07:59:08 -0800

> In addition to my previous comments, I think you cannot expand an existing Cuckoo Filter.
> 
> In other words, every time the number of resources that need to be tracked doubles (or halves), you would need to reconstruct a new Cuckoo Filter (of the adjusted size) by iterating through the cache entries. I do not think that is something you would like to do.

My understanding from the Cuckoo filter and [Cuckoo hashing](http://www.it-c.dk/people/pagh/papers/cuckoo-jour.pdf) papers is that this expansion is taken into consideration in the amortized complexity analysis. Even if you look at the worst case, such expansion's cost is O(N), which is asymptotically similar to the cost GCS incur on every connection establishment.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/268#issuecomment-261567356

---

From: HTTP issue updates <[email-masked]>
Date: Sun, 20 Nov 2016 00:05:28 -0800

> However, in a Cuckoo Filter, there is no such reference. Therefore, to (re)build a Cuckoo Filter, you would need to use some pre-existing structure in the browser cache to iterate through the objects belonging to a specific origin. However, under premise that there is no per-origin index (note: we are considering the use of Cookie Filters since we do not want to introduce such index), we would need to iterate through the entire cache.

That would indeed be a serious handicap to the Cuckoo filter approach.
Fortunately, browsers can extend the basic Cuckoo filter implementation to also store the full crypto hashes or other references to the stored objects on top of storing fingerprints.

This extra info won't be sent up as part of the Cuckoo filter, but can be used locally to extend it in O(N) complexity.

Such references to the actual stored objects can also allow periodic (potentially out-of-band) O(N) calculation to create a stale resources filter that would make it easier to push 304s.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/268#issuecomment-261764848