It's a bit weird to not compare this to HyperLogLog & similar techniques that are designed to solve exactly this problem but much more cheaply (at least as far as I understand).
Added a note on why we chose EvCache for the "Best-Effort" use-case instead of probabilistic data structures like HLL/CMS. Appreciate the discussion.
Can you do a distributed HyperLogLog? Wouldn't you have to have a single instance of it somewhere?
hyperloglog distributes perfectly. Each node keeps track of the "best" hash, and then to query the global maximum, you just ask each node for their value.
Querying each instance can lead to availability and latency challenges. Moreover, HLL is not suited for tasks like increments/decrements, TTLs on counts, and clearing of counts. Count-Min Sketch could work if we're willing to forgo certain requirements like TTLs, but relying solely on in-memory data structures on every instance isn't ideal (think about instance crashes, restarts, new code deployments etc.) Instead, using data stores that support HLL or Count-Min Sketch, like Redis, would offer better reliability. That said, we prefer to build on top of data stores we already operate. Also, the "Best-Effort" counter is literally 5 lines of code for EvCache. The bulk of the post focuses on "Eventually Consistent Accurate" counters, along with a way to track which systems sent the increments, which probabilistic counting is not ideal for.
Just to add, we are also trying to support idempotency wherever possible to enable safe hedging and retries. This is mentioned a bunch in the article on Accurate counters. So take that into consideration.
I came here to write the same thing. Getting an estimate accurate for at least 5 digits on all netflix video watches worldwide can all be done with intelligent sampling (like hyperloglog) and likely one macbook air as the backend. And aside from the compute save the complexity and implementation time would be much lower too.
Fwiw, we didn't mention any probabilistic data structures because they don't satisfy some of the basic requirements we had for the Best-Effort counter. HyperLogLog is designed for cardinality estimation, not for incrementing or decrementing specific counts (which in our case could be any arbitrary +ve/-ve number per key). AFAIK, both Count-Min Sketch and HyperLogLog do not support clearing counts for specific keys. I believe Count-Min Sketch cannot support decrement as well. The core EvCache solution for the Best-Effort counter is like 5 lines of code. And EvCache can handle millions of operations/second relatively cheaply.
Including this in the blog would have been helpful although I don’t think the decrement explanation is unsolvable - just have a second field for decrements that is incremented when you want to decrement & then the final result is a sum of the two.
True. You could do decrements that way. We trimmed this article as the post is already quite long. But considering the multiple threads on this, we might add a few lines. There is also something to be said on operating data stores that support HLL or similar probabilistic data structures. Our goal is to build taller on what we already operate and deploy (like EvCache)