com.netflix.spectator.api.patterns

Class DistinctCountSketch

java.lang.Object

com.netflix.spectator.api.patterns.DistinctCountSketch

All Implemented Interfaces:

Meter

public final class DistinctCountSketch
extends Object
implements Meter

Estimates the number of distinct values seen during a step interval, for example the number of unique users, device ids, or source ips. It is backed by a HyperLogLog sketch that is decomposed into a fixed set of per-register max-gauges so that:

• recording a value is a constant time, allocation-free operation,
• sketches from many instances/nodes/regions merge correctly via the normal aggregation path (the per-register union is a max),
• the cardinality estimate is computed at query time on the backend, and
• results can still be sliced and diced by any other dimension on the Id.

The result is an estimate, not an exact count. With the fixed register count used here the relative standard error is approximately 13%. This is generally good enough for "how many distinct things this interval" style questions at a fixed and predictable publishing cost, independent of the true cardinality (whether it is 10 or 10 million).

Distinct count sketches are more expensive than a plain counter. Each instance publishes a fixed number of gauges (64). Be diligent about any additional dimensions added to a sketch and ensure they have a small bounded cardinality, the same way you would for a percentile timer.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DistinctCountSketch.Builder Helper for getting instances of a DistinctCountSketch.

Field Summary

Fields

Modifier and Type	Field and Description
static int	REGISTERS Number of HLL registers.

Method Summary

Modifier and Type	Method and Description
static IdBuilder<DistinctCountSketch.Builder>	builder(Registry registry) Return a builder for configuring and retrieving an instance of a distinct count sketch.
double	cardinality() Estimate the number of distinct values recorded into this sketch on the local node.
static double	cardinality(double[] registers) Estimate the number of distinct values from the per-register values of a merged sketch.
static DistinctCountSketch	get(Registry registry, Id id) Creates a sketch that can be used for estimating the number of distinct values.
boolean	hasExpired() Returns true once every register that has been created has expired (and so the cached sketch can be dropped from the registry state).
Id	id() Identifier for the sketch.
Iterable<Measurement>	measure() The sketch publishes its data as the per-register max-gauges, so it has no measurements of its own.
void	record(byte[] value) Record a distinct value from its raw bytes.
void	record(CharSequence value) Record a distinct string value, such as a string id or ip address.
void	record(long value) Record a distinct long value, such as a numeric id.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

REGISTERS

public static final int REGISTERS

Number of HLL registers. This is a fixed global constant: a distinct=R## tag must mean the same partition of the hash space everywhere or sketches from different sources cannot be merged from the tag alone. There is deliberately no precision knob. Exposed so that consumers reconstructing the sketch (such as the backend estimator) can size the register array consistently.

See Also:

Constant Field Values

Method Detail

get

public static DistinctCountSketch get(Registry registry,
                                      Id id)

Creates a sketch that can be used for estimating the number of distinct values. Distinct count sketches are more expensive than a plain counter. Be diligent about ensuring that any additional dimensions have a small bounded cardinality.

Parameters:

registry - Registry to use.

id - Identifier for the metric being registered.

Returns:

Sketch that keeps track of the registers used to estimate the distinct count.

builder

public static IdBuilder<DistinctCountSketch.Builder> builder(Registry registry)

Return a builder for configuring and retrieving an instance of a distinct count sketch. If the sketch has dynamic dimensions, then the builder can be used with the new dimensions. If the id is the same as an existing sketch, then it will update the same underlying registers in the registry.

id

public Id id()

Identifier for the sketch.

Specified by:

id in interface Meter

measure

public Iterable<Measurement> measure()

The sketch publishes its data as the per-register max-gauges, so it has no measurements of its own. This is only implemented so the registry can reclaim the cached sketch from its state once the backing registers have expired (see hasExpired()).

Specified by:

measure in interface Meter

hasExpired

public boolean hasExpired()

Returns true once every register that has been created has expired (and so the cached sketch can be dropped from the registry state). A register is created lazily on first use, so a sketch is considered expired until something is recorded into it.

This is only called by the registry's periodic state cleanup, not on the recording hot path, so the scan over the registers is inexpensive. It cannot delegate to a single representative register because registers expire independently: a register that receives no value for a while can expire while the sketch is still actively recording into others, so all created registers must be expired before the sketch is reclaimed.

Specified by:

hasExpired in interface Meter

record

public void record(long value)

Record a distinct long value, such as a numeric id.

record

public void record(CharSequence value)

Record a distinct string value, such as a string id or ip address.

record

public void record(byte[] value)

Record a distinct value from its raw bytes.

cardinality

public double cardinality()

Estimate the number of distinct values recorded into this sketch on the local node.

This only reflects what was recorded into this instance. The fleet-wide distinct count is computed on the backend, which merges the registers across all sources (by taking the per-register max) before applying the same estimator. The result is an approximation with a relative standard error of roughly 1.04/sqrt(REGISTERS).

cardinality

public static double cardinality(double[] registers)

Estimate the number of distinct values from the per-register values of a merged sketch. The input holds the register value (the max rho, or 0 for an unset register) for each of the m registers; it may be any length, with a relative standard error of roughly 1.04/sqrt(m).

This is the estimator applied at query time on the backend, after the registers have been merged across the requested space and time aggregation. It is exposed here so that the client and the backend share a single implementation. It uses the standard HyperLogLog estimator with linear counting for the small cardinality range.

Parameters:

registers - Per-register max rho values for the merged sketch.

Returns:

Estimated number of distinct values.