Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Big Data Cardinality: fast unique visitor counting for large instances using HyperLogLog #6212

Open
diosmosis opened this issue Sep 14, 2014 · 6 comments
Labels
c: Performance For when we could improve the performance / speed of Matomo. Task Indicates an issue is neither a feature nor a bug and it's purely a "technical" change.

Comments

@diosmosis
Copy link
Member

HyperLogLog is an algorithm that provides 97% accuracy on cardinality counts (ie, unique visitors), while using a very small memory footprint. We could add support for this algorithm within Piwik to not only provide fast cardinality for large numbers of visits, but also we can use it to provide a unique visitor count for any period. HyperLogLog results can themselves be aggregated, so they can be stored in archive tables as blobs.

More info:

@mattab mattab added this to the Long term milestone Sep 17, 2014
@mattab
Copy link
Member

mattab commented Sep 17, 2014

I also heard of Bloom filters doing good job: https://en.wikipedia.org/wiki/Bloom_filter

@mattab mattab added Task Indicates an issue is neither a feature nor a bug and it's purely a "technical" change. c: Performance For when we could improve the performance / speed of Matomo. labels Sep 17, 2014
@diosmosis
Copy link
Member Author

According to the second article, bloom filters will take up more space (though provide more accuracy) and the results cannot be merged so the process cannot be done in parallel across several machines.

@mattab
Copy link
Member

mattab commented Mar 24, 2015

btw there is now HyperLogLog data structure in Redis http://antirez.com/news/75

update 2021

simple explanation of how it works https://stackoverflow.com/a/12734343/3759928

also from https://segment.com/blog/scaling-up-reporting-on-high-cardinality-metrics/

MySQL has UDFs (user defined functions) that we could use for this, but we use MySQL on AWS, and from my research, there doesn’t seem to be a way to use UDFs on Aurora, or RDS.
PostgreSQL on the other hand, has an extension called postgresql-hll, which is available on PostgresSQL RDS.

@diosmosis
Copy link
Member Author

Apparently possible to implement hyperloglog in pure SQL: https://www.periscope.io/blog/hyperloglog-in-pure-sql.html

@mattab mattab modified the milestones: Long term, Mid term Dec 23, 2015
@mattab mattab modified the milestones: Long term, Mid term Dec 5, 2016
@diosmosis
Copy link
Member Author

diosmosis commented May 23, 2021

We recently ran some tests with hyperloglog in matomo to use instead of COUNT(DISTINCT idvisitor) and noticed in every case it was far more efficient.

Details about the test:

  • The test used hyperloglog in pure SQL run against COUNT(DISTINCT idvisitor) on periods that ranged from having 700 distinct visitors to 50,000,000 distinct visitors. Tests were run on day periods and month periods only.
  • Hyperloglog is a probablistic counter so it is not as accurate, BUT it allows you to control the error rate. We used a 5% error rate for the test, lower % error rates would require more memory/storage. (For 5% error rate, we need 512 rows in memory, or if we store intermediate data in the archive tables in the database, a datatable w/ 512 rows in a blob row).
  • We checked how accurate the results were along with how much faster they were.

Test results:

  • For smaller sets of distinct idvisitors (ranging from 700 to 500,000), hyperloglog was always faster, ranging from 50% faster to 90% faster.
  • For larger sets of distinct idvisitors (ranging from 14 million to 50 million), hyperloglog was faster, but only around ~20% faster. This may have something to do w/ the overall amount of rows that had to be traversed.
  • The error rate was usually < 1%, but ranged from 1% to 6.5%. Only one of our test had an error rate > 5%.

Conclusions:

  • DISTINCT queries are used in many archiving queries. Since HyperLogLog shows performance boosts for every period, including day periods, it's conceivable that using hyperloglog would have a dramatic effect on archiving performance.
  • HyperLogLog intermediate results can be saved. This means we could store them in the blob table for day periods, and just aggregate them together for higher periods. This means for higher periods, we don't actually have to query the log tables, which would make querying for distinct visitors immediate.
  • Having a 2% error rate means using 4096 rows in memory or in a datatable. For instances where hyperloglog would be useful, this is likely very doable. 1% means 16384 rows, which might also be doable depending on the user.
  • For some visit counts/action counts, we don't need to do hyperloglog and could enable it conditionally.
  • When hyperloglog is used, we would have to change 'Unique Visitors' or 'Unique X' to 'Estimated Unique X' w/ metric documentation that explains what it is. We might also want a setting whether to enable it for only higher periods or also for day periods.

All of this depends on whether large users would want exact numbers or a close enough estimate, but it might make Matomo usable for very high traffic websites.

@tsteur
Copy link
Member

tsteur commented May 23, 2021

Great findings @diosmosis 💯

From UI perspective when enabling this the biggest challenge will be making it clear to users when accurate numbers are used and when estimates. So if someone was to enable these estimates, then we'd need to change the metric/column name to "Estimated Unique Visitors" and update the description to mention the estimate and it's error rate etc to prevent users getting confused or reporting errors that aggregating the unique visitors from lower periods isn't the same etc.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
c: Performance For when we could improve the performance / speed of Matomo. Task Indicates an issue is neither a feature nor a bug and it's purely a "technical" change.
Projects
None yet
Development

No branches or pull requests

3 participants