This is awesome...
question though:
```pub fn HyperLogLog(comptime p: u8) type {
return struct {
dense: [1<<p]u6;
const Self = @This();
pub fn init() Self {
var s = Self{};
for (s.dense) |*x| x.* = 0;
return s;
}
}
}```
doesn't this allocate 1<<p upfront though. If yes then the HLL of size 16384 bytes upfront which kinda beats the purpose of having a sparse representation no?
Great question (and apologies for the length of the answer)! Through our previous experiences in building services around tsdbs & relying on tsdbs to host monitoring data, we kept hitting the same issues around ingest, retention, and querying capabilities.
Existing solutions, and those architected in a more traditional way than Axiom, would require highly-coordinated nodes running on expensive VMs that would be bound by cpu, memory, and storage depending on your use case:
- Want to store TBs of data for months/years and query any piece of that at any time? Prepare to have expensive SSDs or wait for 'archived' data to swap in from cheaper storage.
- Want to run a query that combines N datasets, calculates aggregations, over TBs of data, and then compare that against data with the time shifted back a week, month, or year? Great, fire up some heavy VMs with enough cpu, memory, and bandwidth to compute all that.
- What if you use case varying greatly in each dimension (how much ingest you'd use, how much storage you'd need, and how heavy your queries would be) across a day, week, or month? You'd have to find a way to adapt to changing requirements or just scale up for the worst case x2 and just pay the $$$.
With Axiom, we had three key goals:
- Hyper-efficient, co-ordination free, schema-less, and index-free ingest (~1.4TB/day on a $5/mo container)
- Cheapest storage for hot, cold, archived and warehoused data: all data is stored in object storage, highly compressed & ready to query. 10 seconds or 10 years old data is the same, already as cheap as possible.
- Serverless querying that can expand from 0 to as-much-as-AWS-will-allow depending on what your query needs + how many of your team are querying at once.
The above was achieved through a lot of trial-and-error, tweaking, testing, and head-scratching, but we're really proud of what we've built. We can run super-fast ad-hoc queries, we've eliminated the need to think about retention, we have live streaming, and we have an incredible query language inspired by Microsoft's Kusto (Splunk users will be familiar!).
We still have a lot I'd like to see done, but I think we really do have something unique :)
We are familiar with honeycomb and we also have a honeycomb->axiom multiplexer, so you can use their great tools, to forward to use and compare side by side.
Author of the Library here:
I can't fully agree that HyperLogLogs are good for intersections, that does not mean it can't be done, just there is always a high error rate. The easy way to do that is to maintain a separate MinHash sketch per HLL and use the Jaccard Index of several of those HLLs... an even more naive just use the Jaccard Index with the HLL registers but good luck getting good results out of that. This library is based on https://arxiv.org/pdf/1710.08436v4.pdf which has the benchmarks...
Also I will be taking a stab at http://www.vldb.org/pvldb/vol11/p1097-nazi.pdf very soon :)