promsketch

package module
v0.0.0-...-1d29c73 Latest Latest
Warning

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

 Go to latest Published: Jul 6, 2025 License: GPL-3.0 Imports: 26 Imported by: 4

README

PromSketch: Approximation-First Timeseries Qery At Scale

About

PromSketch is an approximation-first timeseries query framework serving as intermediate result caches for cloud telemetry systems. It eliminates two major query bottlnecks in window-based aggregation queries, i.e., 1) repeated data scans, and 2) repeated query computation concerning window overlaps in rule queries.

PromSketch combines approximate window-based query frameworks, e.g., Exponential Historgrams, and sketch-based precomputation as algorithmic building blocks. It can serve as a plugin to Prometheus and VictoriaMetrics, two representative cloud monitoring systems, and significantly reduces query latency operational dollar costs.

Check out our PromSketch demo here!

Quick Start

Install Dependencies

# installs Golang
wget https://go.dev/dl/go1.22.4.linux-amd64.tar.gz
sudo rm -rf /usr/local/go && sudo tar -C /usr/local -xzf go1.22.4.linux-amd64.tar.gz
export PATH=$PATH:/usr/local/go/bin

# installs nvm (Node Version Manager)
curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.40.0/install.sh | bash
# download and install Node.js (you may need to restart the terminal)
nvm install 20

Datasets

Run EHUniv test

cd promsketch
go test -v -timeout 0 -run ^TestExpoHistogramUnivMonOptimizedCAIDA$ github.com/froot/promsketch

Run EHKLL test

cd promsketch
go test -v -timeout 0 -run ^TestCostAnalysisQuantile$ github.com/froot/promsketch

Integration with Prometheus

git clone git@github.com:zzylol/prometheus-sketches.git

Compile:

cd prometheus-sketches
make build

Integration with VictoriaMetrics single-node version

git clone git@github.com:zzylol/VictoriaMetrics.git

Compile:

cd VictoriaMetrics
make victoria-metrics
make vmalert

Integration with VictoriaMetrics Cluster version

https://github.com/zzylol/VictoriaMetrics-cluster

Citation

Please consider citing this work if you find the repository helpful.

@article{zhu2025approximation,
  title={Approximation-First Timeseries Monitoring Query At Scale},
  author={Zhu, Zeying and Chamberlain, Jonathan and Wu, Kenny and Starobinski, David and Liu, Zaoxing},
  journal={arXiv preprint arXiv:2505.10560},
  year={2025}
}

Contact

Feel free to raise issues or contact us if you have any questions or suggestions. You can reach us at:

Documentation

Index

Constants

View Source 
const (
	LargeError = iota
	SmallError
)
View Source 
const BILLION int = 1000000000
View Source 
const CM_COL_NO int = 1000
View Source 
const CM_ROW_NO int = 5

sketch configurations

View Source 
const CS_COL_NO int = 4096
View Source 
const CS_COL_NO_Univ_ELEPHANT int = 2048
View Source 
const CS_COL_NO_Univ_MICE int = 512
View Source 
const CS_LVLS int = 16 // total layers
View Source 
const CS_ONE_COL_NO int = 100000
View Source 
const CS_ROW_NO int = 5
View Source 
const CS_ROW_NO_Univ_ELEPHANT int = 3
View Source 
const CS_ROW_NO_Univ_MICE int = 3
View Source 
const (
	// DefaultStripeSize is the default number of entries to allocate in the stripeSeries hash map.
	DefaultStripeSize = 1 << 14
)
View Source 
const EHUniv_MAX_MAP_SIZE int = (ELEPHANT_LAYER*(CS_ROW_NO_Univ_ELEPHANT*CS_COL_NO_Univ_ELEPHANT) + MICE_LAYER*(CS_ROW_NO_Univ_MICE*CS_COL_NO_Univ_MICE))
View Source 
const ELEPHANT_LAYER = 8

Configuration 1, used in performance evaluation

View Source 
const HASH_SEED int = 2147483647
View Source 
const INTERVAL int = 1000 // ms
View Source 
const MICE_LAYER = 8
View Source 
const MILLION int = 1000000
View Source 
const TOPK_SIZE int = 100
View Source 
const TOPK_SIZE2 int = 200
View Source 
const TOPK_SIZE_MICE int = 100
View Source 
const UnivPoolCAP uint32 = 1
View Source 
const WINDOW_SIZE int = 1000000

Variables

View Source 
var FunctionCalls = map[string]FunctionCall{
	"change_over_time":   funcChangeOverTime,
	"avg_over_time":      funcAvgOverTime,
	"count_over_time":    funcCountOverTime,
	"entropy_over_time":  funcEntropyOverTime,
	"max_over_time":      funcMaxOverTime,
	"min_over_time":      funcMinOverTime,
	"stddev_over_time":   funcStddevOverTime,
	"stdvar_over_time":   funcStdvarOverTime,
	"sum_over_time":      funcSumOverTime,
	"sum2_over_time":     funcSum2OverTime,
	"distinct_over_time": funcCardOverTime,
	"l1_over_time":       funcL1OverTime,
	"l2_over_time":       funcL2OverTime,
	"quantile_over_time": funcQuantileOverTime,
}

FunctionCalls is a list of all functions supported by PromQL, including their types.

View Source 
var SamplingFunctionCalls = map[string]SamplingFunctionCall{
	"avg_over_time":      funcSamplingAvgOverTime,
	"count_over_time":    funcSamplingCountOverTime,
	"entropy_over_time":  funcSamplingEntropyOverTime,
	"max_over_time":      funcSamplingMaxOverTime,
	"min_over_time":      funcSamplingMinOverTime,
	"stddev_over_time":   funcSamplingStddevOverTime,
	"stdvar_over_time":   funcSamplingStdvarOverTime,
	"sum_over_time":      funcSamplingSumOverTime,
	"sum2_over_time":     funcSamplingSum2OverTime,
	"distinct_over_time": funcSamplingCardOverTime,
	"l1_over_time":       funcSamplingL1OverTime,
	"l2_over_time":       funcSamplingL2OverTime,
	"quantile_over_time": funcSamplingQuantileOverTime,
}

FunctionCalls is a list of all functions supported by PromQL, including their types.

View Source 
var VMFunctionCalls = map[string]VMFunctionCall{
	"change_over_time":   funcVMChangeOverTime,
	"avg_over_time":      funcVMAvgOverTime,
	"count_over_time":    funcVMCountOverTime,
	"entropy_over_time":  funcVMEntropyOverTime,
	"max_over_time":      funcVMMaxOverTime,
	"min_over_time":      funcVMMinOverTime,
	"stddev_over_time":   funcVMStddevOverTime,
	"stdvar_over_time":   funcVMStdvarOverTime,
	"sum_over_time":      funcVMSumOverTime,
	"sum2_over_time":     funcVMSum2OverTime,
	"distinct_over_time": funcVMCardOverTime,
	"l1_over_time":       funcVML1OverTime,
	"l2_over_time":       funcVML2OverTime,
	"quantile_over_time": funcVMQuantileOverTime,
}

VMFunctionCalls is a list of all funcVMtions supported by PromQL, including their types.

Functions

func AbsFloat64 

func AbsFloat64(x float64) float64

func AbsInt 

func AbsInt(x int) int

func AbsInt64 

func AbsInt64(x int64) int64

func Max 

func Max(a []float64) (max float64)

func MaxFloat64 

func MaxFloat64(x float64, y float64) float64

func MaxInt64 

func MaxInt64(a, b int64) int64

func Median 

func Median(a []float64) (median float64)

func MedianOfFive 

func MedianOfFive(a, b, c, d, e int64) int64

TODO

func MedianOfThree 

func MedianOfThree(a, b, c int64) int64

func MergeMaps 

func MergeMaps(m1 *EHMap, m2 *EHMap)

func MetricNameHash 

func MetricNameHash(mn *storage.MetricName) uint64

Hash returns a hash value for the label set. Note: the result is not guaranteed to be consistent across different runs of Prometheus.

func Min 

func Min(a []float64) (min float64)

func MinInt 

func MinInt(x int, y int) int

func MinInt64 

func MinInt64(a, b int64) int64

func NewSketchSeries 

func NewSketchSeries(stripeSize int) *sketchSeries

func SignFloat64 

func SignFloat64(x float64) float64

func SignInt 

func SignInt(x int) int

Types

type CMConfig 

type CMConfig struct {
	Row_no int
	Col_no int
}

type CSConfig 

type CSConfig struct {
	Row_no int
	Col_no int
}

type CountBucket 

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

type CountMinSketch 

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

func NewCountMinSketch 

func NewCountMinSketch(row, col int, seed1 []uint32) (s CountMinSketch, err error)

func (CountMinSketch) CMProcessing 

func (s CountMinSketch) CMProcessing(key string, value float64)

func (CountMinSketch) Col 

func (s CountMinSketch) Col() int

Col returns the number of colums

func (CountMinSketch) EstimateStringCount 

func (s CountMinSketch) EstimateStringCount(key string) float64

func (CountMinSketch) EstimateStringSum 

func (s CountMinSketch) EstimateStringSum(key string) float64

func (CountMinSketch) EstimateStringSum2 

func (s CountMinSketch) EstimateStringSum2(key string) float64

func (CountMinSketch) FreeCountSketch 

func (s CountMinSketch) FreeCountSketch() error

func (CountMinSketch) Row 

func (s CountMinSketch) Row() int

Row returns the number of rows (hash functions)

type CountSketch 

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

CountSketch struct. row is the number of hashing functions. col is the size of every hash table count, a matrix, is used to store the count. int is used to store the count, the maximum count is (1<<32)-1 in 32-bit OS, and (1<<64)-1 in 64-bit OS.

func NewCountSketch 

func NewCountSketch(row int, col int, seed1, seed2 []uint32) (s *CountSketch, err error)

New create a new Count Sketch with row hasing funtions and col counters per row.

func NewCountSketchWithEstimates 

func NewCountSketchWithEstimates(epsilon, delta float64) (s *CountSketch, err error)

NewWithEstimates creates a new Count Sketch with given error rate and condifence. Accuracy guarantees will be made in terms of a pair of user specified parameters, ε and δ, meaning that the error in answering a query is within a factor of ε with probability δ.

func (*CountSketch) Col 

func (s *CountSketch) Col() int

Col returns the number of colums

func (*CountSketch) EstimateStringCount 

func (s *CountSketch) EstimateStringCount(key string) int64

func (*CountSketch) FreeCountSketch 

func (s *CountSketch) FreeCountSketch() error

func (*CountSketch) MergeWith 

func (s *CountSketch) MergeWith(other *CountSketch)

func (*CountSketch) Row 

func (s *CountSketch) Row() int

Row returns the number of rows (hash functions)

func (*CountSketch) UpdateAndEstimateString 

func (s *CountSketch) UpdateAndEstimateString(key string, count float64) float64

func (*CountSketch) UpdateString 

func (s *CountSketch) UpdateString(key string, count float64)

type CountSketchUniv 

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

CountSketchUniv struct. row is the number of hashing functions. col is the size of every hash table count, a matrix, is used to store the count. int is used to store the count, the maximum count is (1<<32)-1 in 32-bit OS, and (1<<64)-1 in 64-bit OS.

func NewCountSketchUniv 

func NewCountSketchUniv(row int, col int, seed1, seed2 []uint32) (s *CountSketchUniv, err error)

New create a new Count Sketch with row hasing funtions and col counters per row.

func NewCountSketchUnivWithEstimates 

func NewCountSketchUnivWithEstimates(epsilon, delta float64) (s *CountSketchUniv, err error)

NewWithEstimates creates a new Count Sketch with given error rate and condifence. Accuracy guarantees will be made in terms of a pair of user specified parameters, ε and δ, meaning that the error in answering a query is within a factor of ε with probability δ.

func (*CountSketchUniv) CleanCountSketchUniv 

func (s *CountSketchUniv) CleanCountSketchUniv() error

func (*CountSketchUniv) Col 

func (s *CountSketchUniv) Col() int

Col returns the number of colums

func (*CountSketchUniv) EstimateIntCount 

func (s *CountSketchUniv) EstimateIntCount(key uint32) float64

func (*CountSketchUniv) EstimateStringCount 

func (s *CountSketchUniv) EstimateStringCount(key string) int64

func (*CountSketchUniv) FreeCountSketchUniv 

func (s *CountSketchUniv) FreeCountSketchUniv() error

func (*CountSketchUniv) MergeWith 

func (s *CountSketchUniv) MergeWith(other CountSketchUniv)

func (*CountSketchUniv) Row 

func (s *CountSketchUniv) Row() int

Row returns the number of rows (hash functions)

func (*CountSketchUniv) UpdateAndEstimateString 

func (s *CountSketchUniv) UpdateAndEstimateString(key string, count int64, pos *([]int16), sign *([]int8)) int64

func (*CountSketchUniv) UpdateAndEstimateStringNoL2 

func (s *CountSketchUniv) UpdateAndEstimateStringNoL2(key string, count int64, pos *([]int16), sign *([]int8)) int64

func (*CountSketchUniv) UpdateIntCount 

func (s *CountSketchUniv) UpdateIntCount(key uint32, count int64)

func (*CountSketchUniv) UpdateString 

func (s *CountSketchUniv) UpdateString(key string, count int64, pos []int16, sign []int8)

func (*CountSketchUniv) UpdateStringNoL2 

func (s *CountSketchUniv) UpdateStringNoL2(key string, count int64, pos []int16, sign []int8)

type EHCountConfig 

type EHCountConfig struct {
	K                int64
	Time_window_size int64
}

type EHDDConfig 

type EHDDConfig struct {
	K                int64
	Time_window_size int64
	DDAccuracy       float64
}

type EHKLLConfig 

type EHKLLConfig struct {
	K                int64
	Kll_k            int
	Time_window_size int64
}

type EHMap 

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

func NewMap 

func NewMap() *EHMap

type EHUnivConfig 

type EHUnivConfig struct {
	K                int64
	Time_window_size int64
	Univ_config      UnivConfig
}

type EffSum2Config 

type EffSum2Config struct {
	Item_window_size int64
	Time_window_size int64
	Epsilon          float64
	R                float64
}

type EffSumConfig 

type EffSumConfig struct {
	Item_window_size int64
	Time_window_size int64
	Epsilon          float64
	R                float64
}

type EfficientSum 

type EfficientSum struct {
	T float64

	R float64

	B int64
	// contains filtered or unexported fields
}

func NewEfficientSum 

func NewEfficientSum(item_window_size int64, time_window_size int64, epsilon float64, R float64) *EfficientSum

func (*EfficientSum) Cover 

func (s *EfficientSum) Cover(mint, maxt int64) bool

func (*EfficientSum) GetMemory 

func (s *EfficientSum) GetMemory() float64

func (*EfficientSum) Insert 

func (s *EfficientSum) Insert(t int64, x float64)

func (*EfficientSum) InsertLargeError 

func (s *EfficientSum) InsertLargeError(t int64, x float64)

func (*EfficientSum) InsertSmallError 

func (s *EfficientSum) InsertSmallError(t int64, x float64)

func (*EfficientSum) Query 

func (s *EfficientSum) Query(t1, t2 int64, subinterval bool) float64

func (*EfficientSum) QueryLargeError 

func (s *EfficientSum) QueryLargeError(t1, t2 int64, subinterval bool) float64

func (*EfficientSum) QuerySmallError 

func (s *EfficientSum) QuerySmallError(t1, t2 int64, subinterval bool) float64

type ExpoHistogramCS 

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

func ExpoInitCountCS 

func ExpoInitCountCS(k int64, time_window_size int64) (eh *ExpoHistogramCS)

func (*ExpoHistogramCS) Cover 

func (eh *ExpoHistogramCS) Cover(mint, maxt int64) bool

func (*ExpoHistogramCS) GetMemory 

func (eh *ExpoHistogramCS) GetMemory() float64

func (*ExpoHistogramCS) QueryIntervalMergeCount 

func (eh *ExpoHistogramCS) QueryIntervalMergeCount(t1, t2 int64) *CountSketch

func (*ExpoHistogramCS) Update 

func (eh *ExpoHistogramCS) Update(time int64, key string, value float64)

type ExpoHistogramCount 

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

func ExpoInitCount 

func ExpoInitCount(k int64, time_window_size int64) (eh *ExpoHistogramCount)

func (*ExpoHistogramCount) Cover 

func (eh *ExpoHistogramCount) Cover(mint, maxt int64) bool

func (*ExpoHistogramCount) GetMemory 

func (eh *ExpoHistogramCount) GetMemory() float64

func (*ExpoHistogramCount) QueryIntervalMergeCount 

func (eh *ExpoHistogramCount) QueryIntervalMergeCount(t1, t2 int64) (CountBucket, error)

func (*ExpoHistogramCount) Update 

func (eh *ExpoHistogramCount) Update(time int64, value float64)

type ExpoHistogramDD 

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

func ExpoInitDD 

func ExpoInitDD(k int64, time_window_size int64, ddAccuracy float64) (ehdd *ExpoHistogramDD)

func (*ExpoHistogramDD) Cover 

func (ehdd *ExpoHistogramDD) Cover(mint, maxt int64) bool

func (*ExpoHistogramDD) GetMemory 

func (ehdd *ExpoHistogramDD) GetMemory() float64

func (*ExpoHistogramDD) QueryIntervalMergeDD 

func (ehdd *ExpoHistogramDD) QueryIntervalMergeDD(t1, t2 int64) *ddsketch.DDSketch

func (*ExpoHistogramDD) Update 

func (ehdd *ExpoHistogramDD) Update(time int64, value float64)

type ExpoHistogramKLL 

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

func ExpoInitKLL 

func ExpoInitKLL(k int64, kll_k int, time_window_size int64) (ehkll *ExpoHistogramKLL)

func (*ExpoHistogramKLL) Cover 

func (ehkll *ExpoHistogramKLL) Cover(mint, maxt int64) bool

func (*ExpoHistogramKLL) GetMaxTime 

func (ehkll *ExpoHistogramKLL) GetMaxTime() int64

func (*ExpoHistogramKLL) GetMemory 

func (ehkll *ExpoHistogramKLL) GetMemory() float64

func (*ExpoHistogramKLL) GetMinTime 

func (ehkll *ExpoHistogramKLL) GetMinTime() int64

func (*ExpoHistogramKLL) QueryIntervalMergeKLL 

func (ehkll *ExpoHistogramKLL) QueryIntervalMergeKLL(t1, t2 int64) *kll.Sketch

func (*ExpoHistogramKLL) Update 

func (ehkll *ExpoHistogramKLL) Update(time int64, value float64)

func (*ExpoHistogramKLL) UpdateWindow 

func (ehkll *ExpoHistogramKLL) UpdateWindow(window int64)

type ExpoHistogramUniv 

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

func ExpoInitUniv 

func ExpoInitUniv(k int64, time_window_size int64) (ehu *ExpoHistogramUniv)

func (*ExpoHistogramUniv) Cover 

func (eh *ExpoHistogramUniv) Cover(mint, maxt int64) bool

func (*ExpoHistogramUniv) GetMemory 

func (eh *ExpoHistogramUniv) GetMemory() float64

func (*ExpoHistogramUniv) GetUnivSketch 

func (ehu *ExpoHistogramUniv) GetUnivSketch() (*UnivSketch, error)

func (*ExpoHistogramUniv) PutUnivSketch 

func (ehu *ExpoHistogramUniv) PutUnivSketch(u *UnivSketch) error

func (*ExpoHistogramUniv) QueryIntervalMergeUniv 

func (ehu *ExpoHistogramUniv) QueryIntervalMergeUniv(t1, t2 int64, cur_t int64) (univ *UnivSketch, err error)

func (*ExpoHistogramUniv) StartBackgroundClean 

func (ehu *ExpoHistogramUniv) StartBackgroundClean(ctx context.Context)

func (*ExpoHistogramUniv) StopBackgroundClean 

func (ehu *ExpoHistogramUniv) StopBackgroundClean()

func (*ExpoHistogramUniv) Update 

func (ehu *ExpoHistogramUniv) Update(time_ int64, fvalue float64)

type ExpoHistogramUnivOptimized 

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

func ExpoInitUnivOptimized 

func ExpoInitUnivOptimized(k int64, time_window_size int64) (ehu *ExpoHistogramUnivOptimized)

func (*ExpoHistogramUnivOptimized) Cover 

func (eh *ExpoHistogramUnivOptimized) Cover(mint, maxt int64) bool

func (*ExpoHistogramUnivOptimized) GetMaxTime 

func (eh *ExpoHistogramUnivOptimized) GetMaxTime() int64

func (*ExpoHistogramUnivOptimized) GetMemoryKB 

func (eh *ExpoHistogramUnivOptimized) GetMemoryKB() float64

func (*ExpoHistogramUnivOptimized) GetMinTime 

func (eh *ExpoHistogramUnivOptimized) GetMinTime() int64

func (*ExpoHistogramUnivOptimized) GetTotalBucketSizes 

func (eh *ExpoHistogramUnivOptimized) GetTotalBucketSizes() int64

func (*ExpoHistogramUnivOptimized) GetUnivSketch 

func (ehu *ExpoHistogramUnivOptimized) GetUnivSketch() (*UnivSketch, error)

func (*ExpoHistogramUnivOptimized) PutUnivSketch 

func (ehu *ExpoHistogramUnivOptimized) PutUnivSketch(u *UnivSketch) error

func (*ExpoHistogramUnivOptimized) QueryIntervalMergeUniv 

func (ehu *ExpoHistogramUnivOptimized) QueryIntervalMergeUniv(t1, t2 int64, cur_t int64) (univ *UnivSketch, m *map[float64]int64, n float64, err error)

func (*ExpoHistogramUnivOptimized) StartBackgroundClean 

func (ehu *ExpoHistogramUnivOptimized) StartBackgroundClean(ctx context.Context)

func (*ExpoHistogramUnivOptimized) StopBackgroundClean 

func (ehu *ExpoHistogramUnivOptimized) StopBackgroundClean()

func (*ExpoHistogramUnivOptimized) Update 

func (ehu *ExpoHistogramUnivOptimized) Update(time_ int64, fvalue float64)

func (*ExpoHistogramUnivOptimized) UpdateWindow 

func (ehu *ExpoHistogramUnivOptimized) UpdateWindow(window int64)

type FPoint 

type FPoint struct {
	T int64
	F float64
}

FPoint represents a single float data point for a given timestamp.

func (FPoint) MarshalJSON 

func (p FPoint) MarshalJSON() ([]byte, error)

MarshalJSON implements json.Marshaler.

JSON marshaling is only needed for the HTTP API. Since FPoint is such a frequently marshaled type, it gets an optimized treatment directly in web/api/v1/api.go. Therefore, this method is unused within Prometheus. It is still provided here as convenience for debugging and for other users of this code. Also note that the different marshaling implementations might lead to slightly different results in terms of formatting and rounding of the timestamp.

func (FPoint) String 

func (p FPoint) String() string

type FunctionCall 

type FunctionCall func(ctx context.Context, series *memSeries, c float64, t1, t2, t int64) Vector

type HHCountSketch 

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

type HeavyHitter 

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

type Item 

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

type Matrix 

type Matrix []Series

Matrix is a slice of Series that implements sort.Interface and has a String method.

func (Matrix) ContainsSameLabelset 

func (m Matrix) ContainsSameLabelset() bool

ContainsSameLabelset checks if a matrix has samples with the same labelset. Such a behavior is semantically undefined. https://github.com/zzylol/prometheus-sketch-VLDB/prometheus-sketches/issues/4562

func (Matrix) Len 

func (m Matrix) Len() int

func (Matrix) Less 

func (m Matrix) Less(i, j int) bool

func (Matrix) String 

func (m Matrix) String() string

func (Matrix) Swap 

func (m Matrix) Swap(i, j int)

func (Matrix) TotalSamples 

func (m Matrix) TotalSamples() int

TotalSamples returns the total number of samples in the series within a matrix. Float samples have a weight of 1 in this number, while histogram samples have a higher weight according to their size compared with the size of a float sample. See HPoint.size for details.

type PromSketches 

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

func NewPromSketches 

func NewPromSketches() *PromSketches

func (*PromSketches) Eval 

func (ps *PromSketches) Eval(funcName string, lset labels.Labels, otherArgs float64, mint, maxt, cur_time int64) (Vector, annotations.Annotations)

func (*PromSketches) GetTotalMemory 

func (ps *PromSketches) GetTotalMemory() float64

func (*PromSketches) GetTotalMemoryEHUniv 

func (ps *PromSketches) GetTotalMemoryEHUniv() float64

func (*PromSketches) LookUp 

func (ps *PromSketches) LookUp(lset labels.Labels, funcName string, mint, maxt int64) bool

func (*PromSketches) LookUpAndUpdateWindow 

func (ps *PromSketches) LookUpAndUpdateWindow(lset labels.Labels, funcName string, mint, maxt int64) bool

func (*PromSketches) NewSketchCacheInstance 

func (ps *PromSketches) NewSketchCacheInstance(lset labels.Labels, funcName string, time_window_size int64, item_window_size int64, value_scale float64) error

func (*PromSketches) PrintCoverage 

func (ps *PromSketches) PrintCoverage(lset labels.Labels, funcName string) (int64, int64)

func (*PromSketches) PrintEHUniv 

func (ps *PromSketches) PrintEHUniv(lset labels.Labels)

func (*PromSketches) PrintSampling 

func (ps *PromSketches) PrintSampling(lset labels.Labels)

func (*PromSketches) SketchInsert 

func (ps *PromSketches) SketchInsert(lset labels.Labels, t int64, val float64) error

SketchInsert will be called in Prometheus scrape module, for SketchCache version t.(int64) is millisecond level timestamp, based on Prometheus timestamp

func (*PromSketches) SketchInsertDefinedRules 

func (ps *PromSketches) SketchInsertDefinedRules(lset labels.Labels, t int64, val float64) error

SketchInsertDefinedRules will be called in Prometheus scrape module, with pre-defined sketch rules (hard-coded) t.(int64) is millisecond level timestamp, based on Prometheus timestamp

func (*PromSketches) SketchInsertInsertionThroughputTest 

func (ps *PromSketches) SketchInsertInsertionThroughputTest(lset labels.Labels, t int64, val float64) error

SketchInsertInsertionThroughputTest will be called in Prometheus scrape module, only for worst-case insertion throughput test t.(int64) is millisecond level timestamp, based on Prometheus timestamp

func (*PromSketches) StopBackground 

func (ps *PromSketches) StopBackground()

type SHCountConfig 

type SHCountConfig struct {
	Beta             float64
	Time_window_size int64
}

type SHUnivConfig 

type SHUnivConfig struct {
	Beta             float64
	Time_window_size int64
	Univ_config      UnivConfig
}

type SSample 

type SSample struct {
	T int64
	F string
}

type SVector 

type SVector []SSample

type Sample 

type Sample struct {
	T int64
	F float64
}

Sample is a single sample belonging to a metric. It represents either a float sample or a histogram sample. If H is nil, it is a float sample. Otherwise, it is a histogram sample.

func (Sample) MarshalJSON 

func (s Sample) MarshalJSON() ([]byte, error)

MarshalJSON is mirrored in web/api/v1/api.go with jsoniter because FPoint and HPoint wouldn't be marshaled with jsoniter otherwise.

func (Sample) String 

func (s Sample) String() string

type SamplingCache 

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

func NewSamplingCache 

func NewSamplingCache() *SamplingCache

func (*SamplingCache) Eval 

func (sc *SamplingCache) Eval(funcName string, lset labels.Labels, otherArgs float64, mint, maxt int64) (Vector, error)

func (*SamplingCache) Insert 

func (sc *SamplingCache) Insert(lset labels.Labels, t int64, val float64) error

func (*SamplingCache) LookUp 

func (sc *SamplingCache) LookUp(funcName string, lset labels.Labels, mint, maxt int64) bool

func (*SamplingCache) NewSamplingCacheEntry 

func (sc *SamplingCache) NewSamplingCacheEntry(lset labels.Labels, sampling_rate float64, time_window_size int64, item_window_size int) error

func (*SamplingCache) Select 

func (sc *SamplingCache) Select(lset labels.Labels, t1 int64, t2 int64) ([]float64, error)

type SamplingCacheEntry 

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

func (*SamplingCacheEntry) Append 

func (s *SamplingCacheEntry) Append(t int64, val float64)

type SamplingCacheHashMap 

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

type SamplingCacheSeries 

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

func NewSamplingCacheSeries 

func NewSamplingCacheSeries(stripeSize int) *SamplingCacheSeries

type SamplingConfig 

type SamplingConfig struct {
	Sampling_rate    float64
	Time_window_size int64
	Max_size         int
}

type SamplingFunctionCall 

type SamplingFunctionCall func(ctx context.Context, values []float64, c float64) Vector

type Scalar 

type Scalar struct {
	T int64
	V float64
}

Scalar is a data point that's explicitly not associated with a metric.

func (Scalar) MarshalJSON 

func (s Scalar) MarshalJSON() ([]byte, error)

func (Scalar) String 

func (s Scalar) String() string

type Series 

type Series struct {
	Metric labels.Labels `json:"metric"`
	Floats []FPoint      `json:"values,omitempty"`
}

Series is a stream of data points belonging to a metric.

func (Series) String 

func (s Series) String() string

type SketchConfig 

type SketchConfig struct {
	// 	CM_config       CMConfig
	// CS_config      CSConfig
	// Univ_config    UnivConfig
	// SH_univ_config SHUnivConfig
	// 	SH_count_config SHCountConfig
	// EH_count_config EHCountConfig
	EH_univ_config EHUnivConfig
	EH_kll_config  EHKLLConfig
	// EH_dd_config    EHDDConfig
	// EffSum_config   EffSumConfig
	// EffSum2_config  EffSum2Config
	Sampling_config SamplingConfig
}

SketchConfig bundles sketch configurations for promsketch

type SketchInstances 

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

Each series maintain their own sketches

func (*SketchInstances) Eval 

func (si *SketchInstances) Eval(mn *storage.MetricName, funcName string, args []float64, mint, maxt, cur_time int64) float64

func (*SketchInstances) PrintMinMaxTimeRange 

func (s *SketchInstances) PrintMinMaxTimeRange(mn *storage.MetricName, funcName string) (mint, maxt int64)

type SketchType 

type SketchType int
const (
	SHUniv SketchType = iota + 1
	EHUniv
	EHCount
	EHKLL
	EHDD
	EffSum
	EffSum2
	USampling
)

type SmoothHistogramCM 

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

type SmoothHistogramCS 

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

func SmoothInitCS 

func SmoothInitCS(beta float64, time_window_size int64) (sh *SmoothHistogramCS)

---------------------------------------------------------- 

Smooth Histogram for count, sum, and avg, sum2

----------------------------------------------------------

func (*SmoothHistogramCS) Cover 

func (sh *SmoothHistogramCS) Cover(mint, maxt int64) bool

func (*SmoothHistogramCS) GetMemory 

func (sh *SmoothHistogramCS) GetMemory() float64

func (*SmoothHistogramCS) QueryIntervalMergeCS 

func (sh *SmoothHistogramCS) QueryIntervalMergeCS(t1, t2, t int64) (*CountSketch, error)

Merge the universal sketches to the interval of t1 to t2; cur_t - time_window_size <= t1 < = t2 <= cur_t

func (*SmoothHistogramCS) Update 

func (sh *SmoothHistogramCS) Update(time int64, key string, value float64)

type SmoothHistogramCount 

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

func SmoothInitCount 

func SmoothInitCount(beta float64, time_window_size int64) (sh *SmoothHistogramCount)

func (*SmoothHistogramCount) Cover 

func (sh *SmoothHistogramCount) Cover(mint, maxt int64) bool

func (*SmoothHistogramCount) GetMemory 

func (sh *SmoothHistogramCount) GetMemory() float64

func (*SmoothHistogramCount) QueryIntervalCount 

func (sh *SmoothHistogramCount) QueryIntervalCount(t1 int64, t int64) (*CountBucket, error)

func (*SmoothHistogramCount) QueryIntervalSum 

func (sh *SmoothHistogramCount) QueryIntervalSum(t1, t int64) float64

func (*SmoothHistogramCount) QueryIntervalSum2 

func (sh *SmoothHistogramCount) QueryIntervalSum2(t1, t int64) float64

func (*SmoothHistogramCount) QueryT1T2IntervalAvg 

func (sh *SmoothHistogramCount) QueryT1T2IntervalAvg(t1, t2, t int64) float64

func (*SmoothHistogramCount) QueryT1T2IntervalCount 

func (sh *SmoothHistogramCount) QueryT1T2IntervalCount(t1, t2, t int64) float64

func (*SmoothHistogramCount) QueryT1T2IntervalSum 

func (sh *SmoothHistogramCount) QueryT1T2IntervalSum(t1, t2, t int64) float64

func (*SmoothHistogramCount) QueryT1T2IntervalSum2 

func (sh *SmoothHistogramCount) QueryT1T2IntervalSum2(t1, t2, t int64) float64

func (*SmoothHistogramCount) Update 

func (sh *SmoothHistogramCount) Update(time int64, value float64)

type SmoothHistogramUnivMon 

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

func SmoothInitUnivMon 

func SmoothInitUnivMon(beta float64, time_window_size int64) (shu *SmoothHistogramUnivMon)

func (*SmoothHistogramUnivMon) Cover 

func (sh *SmoothHistogramUnivMon) Cover(mint, maxt int64) bool

func (*SmoothHistogramUnivMon) GetMemory 

func (shu *SmoothHistogramUnivMon) GetMemory() float64

func (*SmoothHistogramUnivMon) GetUnivSketch 

func (shu *SmoothHistogramUnivMon) GetUnivSketch() (*UnivSketch, error)

func (*SmoothHistogramUnivMon) PutUnivSketch 

func (shu *SmoothHistogramUnivMon) PutUnivSketch(u *UnivSketch) error

func (*SmoothHistogramUnivMon) QueryIntervalMergeUniv 

func (shu *SmoothHistogramUnivMon) QueryIntervalMergeUniv(t1, t2, t int64) (univ *UnivSketch, err error)

Merge the universal sketches to the interval of t1 to t2; cur_t - time_window_size <= t1 <= t2 <= cur_t

func (*SmoothHistogramUnivMon) StartBackgroundClean 

func (shu *SmoothHistogramUnivMon) StartBackgroundClean(ctx context.Context)

func (*SmoothHistogramUnivMon) StopBackgroundClean 

func (shu *SmoothHistogramUnivMon) StopBackgroundClean()

func (*SmoothHistogramUnivMon) Update 

func (shu *SmoothHistogramUnivMon) Update(time_ int64, value string)

type String 

type String struct {
	T int64
	V string
}

String represents a string value.

func (String) MarshalJSON 

func (s String) MarshalJSON() ([]byte, error)

func (String) String 

func (s String) String() string

type SumArr 

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

type TSId 

type TSId int

type TopKHeap 

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

func NewTopKFromHeap 

func NewTopKFromHeap(from *TopKHeap) (topkheap *TopKHeap)

func NewTopKHeap 

func NewTopKHeap(k int) (topkheap *TopKHeap)

func (*TopKHeap) Clean 

func (topkheap *TopKHeap) Clean()

func (*TopKHeap) Find 

func (topkheap *TopKHeap) Find(key string) (int, bool)

func (*TopKHeap) GetMemoryBytes 

func (topkheap *TopKHeap) GetMemoryBytes() float64

func (*TopKHeap) Insert 

func (topkheap *TopKHeap) Insert(key string, count int64)

func (*TopKHeap) Print 

func (topkheap *TopKHeap) Print()

func (*TopKHeap) Update 

func (topkheap *TopKHeap) Update(key string, count int64) bool

update modifies the priority and value of an Item in the queue.

func (*TopKHeap) UpdateCS 

func (topkheap *TopKHeap) UpdateCS(key string, count int64) bool

update modifies the priority and value of an Item in the queue.

type UniformSampling 

type UniformSampling struct {
	Arr              []Sample
	Max_size         int
	Time_window_size int64
	Sampling_rate    float64
	Cur_time         int64
	K                int
	// contains filtered or unexported fields
}

func NewUniformSampling 

func NewUniformSampling(Time_window_size int64, Sampling_rate float64, Max_size int) *UniformSampling

func (*UniformSampling) Cover 

func (s *UniformSampling) Cover(t1, t2 int64) bool

func (*UniformSampling) GetMaxTime 

func (s *UniformSampling) GetMaxTime() int64

func (*UniformSampling) GetMemory 

func (s *UniformSampling) GetMemory() float64

func (*UniformSampling) GetMinTime 

func (s *UniformSampling) GetMinTime() int64

func (*UniformSampling) GetSamples 

func (s *UniformSampling) GetSamples(t1, t2 int64) []float64

func (*UniformSampling) Insert 

func (s *UniformSampling) Insert(t int64, x float64)

func (*UniformSampling) QueryAvg 

func (s *UniformSampling) QueryAvg(t1, t2 int64) float64

func (*UniformSampling) QueryCount 

func (s *UniformSampling) QueryCount(t1, t2 int64) float64

func (*UniformSampling) QueryDistinct 

func (s *UniformSampling) QueryDistinct(t1, t2 int64) float64

func (*UniformSampling) QueryEntropy 

func (s *UniformSampling) QueryEntropy(t1, t2 int64) float64

func (*UniformSampling) QueryGSum 

func (s *UniformSampling) QueryGSum(t1, t2 int64) (float64, float64, float64, float64)

func (*UniformSampling) QueryL1 

func (s *UniformSampling) QueryL1(t1, t2 int64) float64

func (*UniformSampling) QueryL2 

func (s *UniformSampling) QueryL2(t1, t2 int64) float64

func (*UniformSampling) QueryMax 

func (s *UniformSampling) QueryMax(t1, t2 int64) float64

func (*UniformSampling) QueryMin 

func (s *UniformSampling) QueryMin(t1, t2 int64) float64

func (*UniformSampling) QueryQuantile 

func (s *UniformSampling) QueryQuantile(phis []float64, t1, t2 int64) []float64

func (*UniformSampling) QueryStddev 

func (s *UniformSampling) QueryStddev(t1, t2 int64) float64

func (*UniformSampling) QueryStdvar 

func (s *UniformSampling) QueryStdvar(t1, t2 int64) float64

func (*UniformSampling) QuerySum 

func (s *UniformSampling) QuerySum(t1, t2 int64) float64

func (*UniformSampling) QuerySum2 

func (s *UniformSampling) QuerySum2(t1, t2 int64) float64

func (*UniformSampling) UpdateWindow 

func (s *UniformSampling) UpdateWindow(window int64)

type UnivConfig 

type UnivConfig struct {
	TopK_size int
	Row_no    int
	Col_no    int
	Layer     int
}

type UnivSketch 

type UnivSketch struct {
	HH_layers []*TopKHeap
	// contains filtered or unexported fields
}

func NewUnivSketch 

func NewUnivSketch(k, row, col, layer int, seed1, seed2 []uint32, seed3 uint32, pool_idx int64) (us *UnivSketch, err error)

New create a new Universal Sketch with row hashing funtions and col counters per row of a Count Sketch.

func NewUnivSketchPyramid 

func NewUnivSketchPyramid(k, row, col, layer int, seed1, seed2 []uint32, seed3 uint32, pool_idx int64) (us *UnivSketch, err error)

func (*UnivSketch) Free 

func (us *UnivSketch) Free()

func (*UnivSketch) GetBucketSize 

func (us *UnivSketch) GetBucketSize() int64

func (*UnivSketch) GetMemoryKB 

func (us *UnivSketch) GetMemoryKB() float64

func (*UnivSketch) GetMemoryKBPyramid 

func (us *UnivSketch) GetMemoryKBPyramid() float64

func (*UnivSketch) MergeWith 

func (us *UnivSketch) MergeWith(other *UnivSketch)

func (*UnivSketch) PrintHHlayers 

func (us *UnivSketch) PrintHHlayers()

func (*UnivSketch) QueryTopK 

func (us *UnivSketch) QueryTopK(K int) *TopKHeap

type UnivSketchPool 

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

type VMFunctionCall 

type VMFunctionCall func(ctx context.Context, sketchIns *SketchInstances, c []float64, t1, t2, t int64) float64

type VMSketchSeries 

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

sketchSeries holds series by ID and also by hash of their MetricName. ID-based lookups via getByID() are preferred over getByHash() for performance reasons.

func NewVMSketchSeries 

func NewVMSketchSeries(stripeSize int) *VMSketchSeries

type VMSketchSeriesHashMap 

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

type VMSketches 

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

func NewVMSketches 

func NewVMSketches() *VMSketches

func (*VMSketches) AddRow 

func (vs *VMSketches) AddRow(mn *storage.MetricName, t int64, value float64) error

func (*VMSketches) GetSeriesCount 

func (vs *VMSketches) GetSeriesCount() uint64

func (*VMSketches) LookupAndUpdateWindowMetricNameFuncName 

func (vs *VMSketches) LookupAndUpdateWindowMetricNameFuncName(mn *storage.MetricName, funcName string, window int64) bool

func (*VMSketches) LookupMetricNameFuncNamesTimeRange 

func (vs *VMSketches) LookupMetricNameFuncNamesTimeRange(mn *storage.MetricName, funcNames []string, mint, maxt int64) (*SketchInstances, bool)

func (*VMSketches) NewVMSketchCacheInstance 

func (vs *VMSketches) NewVMSketchCacheInstance(mn *storage.MetricName, funcName string, time_window_size int64, item_window_size int64) error

func (*VMSketches) OutputTimeseriesCoverage 

func (vs *VMSketches) OutputTimeseriesCoverage(mn *storage.MetricName, funcNames []string)

func (*VMSketches) Stop 

func (vs *VMSketches) Stop()

type Vector 

type Vector []Sample

Vector is basically only an alias for []Sample, but the contract is that in a Vector, all Samples have the same timestamp.

func (Vector) String 

func (vec Vector) String() string

func (Vector) TotalSamples 

func (vec Vector) TotalSamples() int

TotalSamples returns the total number of samples in the series within a vector. Float samples have a weight of 1 in this number, while histogram samples have a higher weight according to their size compared with the size of a float sample. See HPoint.size for details.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.