topk

Documentation

Overview

Package topk provides a Metric/Collector implementation of a top-K streaming summary algorithm for use with high cardinality data.

The github.com/dgryski/go-topk package is used to implement the calculations.

Package topk implements the Filtered Space-Saving TopK streaming algorithm

The original Space-Saving algorithm: https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf

The Filtered Space-Saving enhancement: http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf

This implementation follows the algorithm of the FSS paper, but not the suggested implementation. Specifically, we use a heap instead of a sorted list of monitored items, and since we are also using a map to provide O(1) access on update also don't need the c_i counters in the hash table.

Licensed under the MIT license.

Index

• type Element
• type Stream
  • func NewStream(n int) *Stream
  • func (s *Stream) Estimate(x string) Element
  • func (s *Stream) GobDecode(b []byte) error
  • func (s *Stream) GobEncode() ([]byte, error)
  • func (s *Stream) Insert(x string, count float64) Element
  • func (s *Stream) Keys() []Element
• type TopK
  • func NewTopK(opts TopKOpts, labelNames []string) TopK
• type TopKBucket
• type TopKOpts

Types

type Element

type Element struct {
	Key   string
	Count float64
	Error float64
}

Element is a TopK item

type Stream

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

Stream calculates the TopK elements for a stream.

This type has been modified from the original; it has been changed to use floating-point counters.

func NewStream

func NewStream(n int) *Stream

NewStream returns a Stream estimating the top n most frequent elements

func (*Stream) Estimate

func (s *Stream) Estimate(x string) Element

Estimate returns an estimate for the item x

func (*Stream) GobDecode

func (s *Stream) GobDecode(b []byte) error

func (*Stream) GobEncode

func (s *Stream) GobEncode() ([]byte, error)

func (*Stream) Insert

func (s *Stream) Insert(x string, count float64) Element

Insert adds an element to the stream to be tracked It returns an estimation for the just inserted element

func (*Stream) Keys

func (s *Stream) Keys() []Element

Keys returns the current estimates for the most frequent elements

type TopK

type TopK interface {
	prometheus.Collector

	CurryWith(prometheus.Labels) (TopK, error)
	MustCurryWith(prometheus.Labels) TopK
	GetMetricWith(prometheus.Labels) (TopKBucket, error)
	GetMetricWithLabelValues(lvs ...string) (TopKBucket, error)
	With(prometheus.Labels) TopKBucket
	WithLabelValues(lvs ...string) TopKBucket
}

TopK is a metric package for estimating the top keys of a high-cardinality set.

On every collection, the top "K" label pairs (where K is the value of opts.Buckets) are exported as Counters with variable labels, plus a parallel set of Gauges for the error bars.

Usage: call one of the With() methods to receive a TopKBucket, and call the Observe method to record an observation. If any NaN values are passed to Observe, they are treated as 0 so as to not pollute the storage.

func NewTopK

func NewTopK(opts TopKOpts, labelNames []string) TopK

NewTopK constructs a new TopK metric container.

type TopKBucket

type TopKBucket interface {
	Observe(float64)
	Inc()
}

type TopKOpts

type TopKOpts struct {
	// Namespace, Subsystem, and Name are components of the fully-qualified
	// name of the TopK (created by joining these components with "_").
	// Only Name is mandatory, the others merely help structuring the name.
	// Note that the fully-qualified name of the TopK must be a valid
	// Prometheus metric name.
	Namespace string
	Subsystem string
	Name      string

	// Help provides information about this Histogram.
	//
	// Metrics with the same fully-qualified name must have the same Help
	// string.
	Help string

	// ConstLabels are used to attach fixed labels to this metric. Metrics
	// with the same fully-qualified name must have the same label names in
	// their ConstLabels.
	//
	// ConstLabels are only used rarely. In particular, do not use them to
	// attach the same labels to all your metrics. Those use cases are
	// better covered by target labels set by the scraping Prometheus
	// server, or by one specific metric (e.g. a build_info or a
	// machine_role metric). See also
	// https://prometheus.io/docs/instrumenting/writing_exporters/#target-labels,-not-static-scraped-labels
	ConstLabels prometheus.Labels

	// Buckets provides the number of metric streams that this metric is
	// expected to keep an accurate count for (the "K" in top-K).
	Buckets uint64

	// To help preserve privacy, any values under the ReportingThreshold
	// are not collected.
	ReportingThreshold float64
}