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

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

Current spec is using Golomb-coded sets as the algorithm to create digests.

While they show great space-efficiency, Golomb-coded sets do not enable O(1) removal from the digest, which means from a browser implementation perspective, the browser would have to calculate the hash for each host upon connection creation.

That poses a couple of issues from an implementation perspective:

* Calculating the hash on each connection establishment may be expensive. That part seems inherent to the algorithm and not likely to be optimized away.
* Calculating the hash requires per-host indexing. That part is just a limitation of many current cache implementations.

A cache digest algorithm that enables O(1) removal (as well as addition) to the digest would enable us to move away from those limitations:

* 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. No need for per-host indexing.
  -  In order to do that, browsers would need to persist digests along with the cache
* Upon connection establishment, the browser can just send the ready-made digest to the server. Win!

During the HTTPWS, counting bloom filters were mentioned as an O(1) removal algorithm, but they are extremely inefficient when it comes to space. (~4 times bigger than bloom filters)

Turns out, [Cuckoo filters](https://www.cs.cmu.edu/~binfan/papers/login_cuckoofilter.pdf) enable O(1) removal while being more space efficient than bloom filters. While they are slightly bigger than Golomb-coded sets based digests, the cheaper runtime costs can make up for that deficiency.

/cc @kazuho @mnot @cbentzel @mcmanus

-- 
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