3 ms·
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.
by adgjlsfhk1 2y ago
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.
- rshrin 2y agoQuerying 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.
- rshrin 2y agoJust 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.