Awesome
go-hll
![GoDoc](https://godoc.org/github.com/segmentio/go-hll?status.svg)
A Go implementation of HyperLogLog that is storage-compatible with the Aggregate Knowledge HLL Storage Spec.
Overview
HyperLogLog (HLL) is a fixed-size, set-like structure used for distinct value counting with tunable precision. For example, in 1280 bytes HLL can estimate the count of tens of billions of distinct values with only a few percent error.
In addition to the algorithm proposed in the original paper, this implementation is augmented to improve its accuracy and memory use without sacrificing much speed.
Motivation
While there are a handful of existing HLL implementations in Go, none of them implement the AK Storage Spec.
The unified storage format is useful for reading and writing HLLs in a multi-lingual environment. At Segment, most of
our runtime code is written in Go, but we frequently persist data to PostgreSQL for long-term storage. The Postgres HLL
plugin is fairly ubiquitous--it's available for the standalone server, AWS RDS, AWS Aurora, and CitusDB.
An excellent description for the motivation behind the storage strategy can be found in the Java HLL library's README.
Hashing
A good hashing algorithm is crucial to achieving the pseudorandomness that HLL requires in order to perform its calculations. The 64 bit variant of MurmurHash3 is recommended. If using a seed, it must be constant for all inputs to a given HLL. Further, if that HLL is to be unioned, then the same seed must be used for all inputs to the other HLL.
See the Java HLL README for a discussion on why MurmurHash3 is a good choice.
Adaptations to Go
The API is intended to be as similar as possible to Java HLL and Postgresql HLL. There are a couple of features, though, that make it more friendly to Go Programmers.
Zero Value
If default settings are specified using the hll.Defaults
function, the zero value can be used directly as an empty HLL.
Since its impossible to reason about an HLL without the settings, operations on a zero value in lieu of default settings will panic.
StrictUnion
The other HLL implementations allow for two HLLs to be union-ed even if their log2m or regwidth parameters differ.
However, doing so can produce wildly inaccurate results. This library provides an additional StrictUnion
operation
that will return an error if attempting a union on HLLs with incompatible settings.
Building
Dependencies are managed with Go Modules. Accordingly, this project requires Go version 1.12 or later.
Test
make test
Usage
package main
import (
"fmt"
"github.com/segmentio/go-hll"
)
func main() {
// install default settings.
hll.Defaults(hll.Settings{
Log2m: 10,
Regwidth: 4,
ExplicitThreshold: hll.AutoExplicitThreshold,
SparseEnabled: true,
})
// add elements.
h := hll.Hll{}
h.AddRaw(123456789)
fmt.Print(h.Cardinality()) // prints "1"
// union Hlls
h2 := hll.Hll{}
h2.AddRaw(123456789)
h2.AddRaw(987654321)
h2.Union(h)
fmt.Print(h2.Cardinality()) // prints "2"
// write to/read from bytes.
h3, _ := hll.FromBytes(h2.ToBytes())
fmt.Print(h3.Cardinality()) // prints "2"
}
There is a compatibility battery run as part of the unit tests. The battery was produced by the Test Generator in the java-hll package.
Additional Resources
- HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
- Understanding the HyperLogLog
License
Released under the MIT license.