gohll

package module
v1.0.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 12, 2026 License: Apache-2.0 Imports: 6 Imported by: 0

README

gohll

Go Reference Go Coverage

gohll counts distinct items approximately with HyperLogLog — built for the hot path: Add is lock-free, allocates nothing and takes a nanosecond, from any number of goroutines at once.

Why gohll?

A HyperLogLog sketch answers "how many distinct users / IPs / keys did we see" in 16 KiB, whatever the number of items, with a standard error of 0.81%. The Go libraries that implement it are not safe for concurrent use: every Insert on a shared sketch needs a mutex, and on a server that counts on every request the mutex costs more than the sketch.

gohll keeps the registers packed eight to a 64-bit word and updates them with a compare-and-swap: no lock, no allocation, no coordination between goroutines.

gohll axiomhq/hyperloglog
Concurrent Add lock-free mutex around Insert
Memory per sketch 16 KiB, fixed, zero value ready 16 KiB dense; smaller sparse mode for few items
Estimate LogLog-Beta (HyperLogLog++ accuracy) LogLog-Beta
Merge, binary encoding yes; the encoding is axiomhq's dense format yes
Precision 14 4–18
Dependencies none metro hash, intmap

Features

  • Lock-free Add — one CAS on the register's word; ~1 ns on one goroutine, scales with cores.
  • Zero allocations — Add, Count, Merge, Reset, AppendBinary.
  • HyperLogLog++ accuracy over the whole range — the LogLog-Beta estimator (Qin, Kim, Tung, Wang, 2016) in one formula: tiny counts are exact or off by one, the 40K–80K band where plain HyperLogLog is biased is not, and the error is unbiased with the theoretical 0.81% spread (tested over many seeds).
  • Merge — the union of two sketches, usable while one is being written to.
  • Binary encoding compatible with axiomhq/hyperloglog (dense, version 2): sketches can move between the two libraries and be merged if both were fed the same hashes (axiomhq's Insert hashes with MetroHash64, seed 1337). encoding.BinaryMarshaler, BinaryUnmarshaler, BinaryAppender.
  • You bring the hash — Add(hash uint64): xxhash, MetroHash, whatever already hashed the item. The sketch does not hash again; see Choosing a hash.
  • Zero dependencies — only the standard library.

Installation

go get github.com/darxnet/gohll

Requires Go 1.24.

Quick Start

// The zero value is ready to use; share it between goroutines as it is.
var users gohll.Sketch

// Add takes a 64-bit hash of the item: a stable one (here
// github.com/cespare/xxhash/v2), so that sketches from other processes merge.
users.Add(xxhash.Sum64String(userID))

// How many distinct items so far?
n := users.Count()

// Union with another sketch (same hash function and seed on both sides).
users.Merge(&usersFromOtherServer)

// Persist, or send to another instance: axiomhq's dense encoding.
data, _ := users.MarshalBinary()
var back gohll.Sketch
_ = back.UnmarshalBinary(data)

// Start the next day.
users.Reset()
Choosing a hash

The hash must spread well over all 64 bits: the top 14 pick the register. Sketches are only comparable if they were fed the same hash function with the same seed, so anything that crosses a process boundary — Merge with a sketch from another server, UnmarshalBinary of stored or received bytes — needs a stable hash such as xxhash, or MetroHash64 with seed 1337 to merge with sketches that axiomhq's Insert filled.

hash/maphash is fine within one process only: maphash.MakeSeed is random and a seed cannot be saved, so two processes hash the same item differently and their merged sketch counts roughly the sum of the two sets, not the union. hash/fnv alone is not enough either: FNV-1a barely changes the top bits between similar keys, and needs a finalizer (such as SplitMix64's) after it.

Accuracy

Mean error and spread over 24 random data sets per size (go test, the TestSketch_Unbiased gate):

Distinct items Mean error Spread (1σ)
1 – 100 exact or ±1 —
20 000 +0.08% 0.62%
40 000 −0.06% 0.67%
60 000 +0.11% 0.65%
80 000 −0.06% 0.63%
120 000 +0.05% 0.72%
300 000 −0.04% 0.79%

Theory for 2^14 registers: 1.04/√16384 = 0.81%. Fed the same hashes, a gohll sketch and an axiomhq sketch in its dense representation hold identical registers, and gohll.Count() and axiomhq.Estimate() apply the same LogLog-Beta formula to them. axiomhq.New14() starts sparse, though, and while it stays sparse (its first several thousand items) Estimate uses linear counting at precision 25 instead, so small counts differ, within the error above; NewNoSparse() is dense from the start.

Benchmarks

Environment: Apple M3 Pro · darwin/arm64 · Go 1.26 go test -bench=. -benchmem -count=5 -cpu=1,12 ./bench/, summarised with benchstat. Same 64-bit hashes on both sides; axiomhq gets InsertHash, with and without the mutex a shared sketch needs.

gohll axiomhq axiomhq + mutex
Add, 1 goroutine 1.08 ns 1.90 ns 3.00 ns
Add, 12 goroutines on one sketch 0.21 ns/op — 117 ns/op
Count / Estimate (1M items) 53 µs 171 µs
Allocs/op 0 0 0

Twelve goroutines adding to one sketch cost axiomhq 550x more per item than gohll: that is the mutex, not the sketch. bench/ is its own module, so the library itself stays dependency-free.

Design

  • 2^14 registers of one byte, packed eight to an atomic.Uint64: Add extracts the register, compares, builds the new word and swaps it in; a lost race just retries. Merge takes the byte-wise maximum of each word the same way.
  • Count reads every register once (16 KiB, L1-resident) and applies the LogLog-Beta formula; Reset and UnmarshalBinary store the words one by one, so they are not atomic with respect to concurrent Adds.
  • No sparse representation on purpose: it would need a lock, and 16 KiB is the point of the fixed-size design. For many small sketches, prefer a library with sparse mode.

See also

The sibling modules follow the same rule — nothing allocated on the hot path, the zero value ready to use:

  • goshard — sharded, lock-based concurrent map for high-churn data: stores allocate nothing
  • gosync — generic concurrent map with sync.Map semantics and no interface boxing, for read-mostly data
  • goreset — generates Reset() for pooled structs: back to the zero state, memory kept
  • gocopy — generates CopyFrom/Copy that reuse the destination's memory instead of allocating

License

Apache License 2.0. See LICENSE for details. The LogLog-Beta coefficients for precision 14 are the published fit from the paper, as also used by axiomhq/hyperloglog (MIT).

Documentation

Overview

Package gohll counts distinct items approximately with HyperLogLog.

A Sketch keeps m = 2^14 one-byte registers (16 KiB, eight to a 64-bit word for lock-free updates) whatever the number of items, and estimates their cardinality with a standard error of 1.04/sqrt(m) ≈ 0.8%. Items are added as 64-bit hashes: the top 14 bits pick a register, the register keeps the longest run of leading zeros seen in the rest, plus one.

The estimate is the LogLog-Beta one (Qin, Kim, Tung, Wang, 2016): a single formula with a per-precision polynomial correction that covers the whole range, from a handful of items to billions, with the accuracy of the HyperLogLog++ bias tables and without its switch between estimators.

Add is lock-free (a compare-and-swap max on the register's word) and allocates nothing; Count walks the registers; Merge takes the union of two sketches; Reset starts over.

Index

Constants

This section is empty.

Variables

View Source
var (
	// ErrEncoding is wrapped by UnmarshalBinary for data it cannot read.
	ErrEncoding = errors.New("gohll: invalid encoding")
	// ErrSparseEncoding is wrapped by UnmarshalBinary for an axiomhq sketch in
	// its sparse representation.
	ErrSparseEncoding = errors.New("gohll: sparse encoding is not supported")
)

Functions

This section is empty.

Types

type Sketch

type Sketch struct {
	// contains filtered or unexported fields
}

Sketch is a HyperLogLog counter. The zero value is ready to use.

func (*Sketch) Add

func (s *Sketch) Add(hash uint64)

Add records one item given by its 64-bit hash. The hash must spread well over all bits (xxhash, MetroHash...): the sketch does not hash again.

Sketches that are merged or restored with UnmarshalBinary must have been fed the same hash function with the same seed. hash/maphash seeds are random per process and cannot be saved, so maphash suits sketches that never leave the process; across processes use a stable hash.

func (*Sketch) AppendBinary

func (s *Sketch) AppendBinary(data []byte) ([]byte, error)

AppendBinary appends the encoding of the sketch to data. Registers are read one by one, so Adds running concurrently may or may not be included.

func (*Sketch) Count

func (s *Sketch) Count() uint64

Count estimates the number of distinct items added since the last Reset.

func (*Sketch) Empty

func (s *Sketch) Empty() bool

Empty reports whether nothing was added since the last Reset.

func (*Sketch) MarshalBinary

func (s *Sketch) MarshalBinary() ([]byte, error)

MarshalBinary encodes the sketch; see the package's encoding note.

func (*Sketch) Merge

func (s *Sketch) Merge(other *Sketch)

Merge adds every item of other to s: the union of the two sets, exact in the sense that it is the sketch the union would have produced. Both must have been fed the same hash function with the same seed (see Add). other is only read; s may be in use by concurrent Adds.

func (*Sketch) Reset

func (s *Sketch) Reset()

Reset forgets every item. It is not atomic with respect to concurrent Adds: an Add racing with Reset may land before or after it.

func (*Sketch) UnmarshalBinary

func (s *Sketch) UnmarshalBinary(data []byte) error

UnmarshalBinary replaces the sketch's registers with the encoded ones. It is not atomic with respect to concurrent Adds, like Reset.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL