topk

package
v0.0.4 Latest Latest
Warning

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

Go to latest
Published: May 8, 2023 License: Apache-2.0 Imports: 12 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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
}

Jump to

Keyboard shortcuts

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