blob: 8762b13c63d1ac239db221d6437170ff77c11877 [file] [log] [blame]
Matthias Andreas Benkard832a54e2019-01-29 09:27:38 +01001// Copyright 2014 The Prometheus Authors
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14package model
15
16import (
17 "sort"
18)
19
20// SeparatorByte is a byte that cannot occur in valid UTF-8 sequences and is
21// used to separate label names, label values, and other strings from each other
22// when calculating their combined hash value (aka signature aka fingerprint).
23const SeparatorByte byte = 255
24
25var (
26 // cache the signature of an empty label set.
27 emptyLabelSignature = hashNew()
28)
29
30// LabelsToSignature returns a quasi-unique signature (i.e., fingerprint) for a
31// given label set. (Collisions are possible but unlikely if the number of label
32// sets the function is applied to is small.)
33func LabelsToSignature(labels map[string]string) uint64 {
34 if len(labels) == 0 {
35 return emptyLabelSignature
36 }
37
38 labelNames := make([]string, 0, len(labels))
39 for labelName := range labels {
40 labelNames = append(labelNames, labelName)
41 }
42 sort.Strings(labelNames)
43
44 sum := hashNew()
45 for _, labelName := range labelNames {
46 sum = hashAdd(sum, labelName)
47 sum = hashAddByte(sum, SeparatorByte)
48 sum = hashAdd(sum, labels[labelName])
49 sum = hashAddByte(sum, SeparatorByte)
50 }
51 return sum
52}
53
54// labelSetToFingerprint works exactly as LabelsToSignature but takes a LabelSet as
55// parameter (rather than a label map) and returns a Fingerprint.
56func labelSetToFingerprint(ls LabelSet) Fingerprint {
57 if len(ls) == 0 {
58 return Fingerprint(emptyLabelSignature)
59 }
60
61 labelNames := make(LabelNames, 0, len(ls))
62 for labelName := range ls {
63 labelNames = append(labelNames, labelName)
64 }
65 sort.Sort(labelNames)
66
67 sum := hashNew()
68 for _, labelName := range labelNames {
69 sum = hashAdd(sum, string(labelName))
70 sum = hashAddByte(sum, SeparatorByte)
71 sum = hashAdd(sum, string(ls[labelName]))
72 sum = hashAddByte(sum, SeparatorByte)
73 }
74 return Fingerprint(sum)
75}
76
77// labelSetToFastFingerprint works similar to labelSetToFingerprint but uses a
78// faster and less allocation-heavy hash function, which is more susceptible to
79// create hash collisions. Therefore, collision detection should be applied.
80func labelSetToFastFingerprint(ls LabelSet) Fingerprint {
81 if len(ls) == 0 {
82 return Fingerprint(emptyLabelSignature)
83 }
84
85 var result uint64
86 for labelName, labelValue := range ls {
87 sum := hashNew()
88 sum = hashAdd(sum, string(labelName))
89 sum = hashAddByte(sum, SeparatorByte)
90 sum = hashAdd(sum, string(labelValue))
91 result ^= sum
92 }
93 return Fingerprint(result)
94}
95
96// SignatureForLabels works like LabelsToSignature but takes a Metric as
97// parameter (rather than a label map) and only includes the labels with the
98// specified LabelNames into the signature calculation. The labels passed in
99// will be sorted by this function.
100func SignatureForLabels(m Metric, labels ...LabelName) uint64 {
101 if len(labels) == 0 {
102 return emptyLabelSignature
103 }
104
105 sort.Sort(LabelNames(labels))
106
107 sum := hashNew()
108 for _, label := range labels {
109 sum = hashAdd(sum, string(label))
110 sum = hashAddByte(sum, SeparatorByte)
111 sum = hashAdd(sum, string(m[label]))
112 sum = hashAddByte(sum, SeparatorByte)
113 }
114 return sum
115}
116
117// SignatureWithoutLabels works like LabelsToSignature but takes a Metric as
118// parameter (rather than a label map) and excludes the labels with any of the
119// specified LabelNames from the signature calculation.
120func SignatureWithoutLabels(m Metric, labels map[LabelName]struct{}) uint64 {
121 if len(m) == 0 {
122 return emptyLabelSignature
123 }
124
125 labelNames := make(LabelNames, 0, len(m))
126 for labelName := range m {
127 if _, exclude := labels[labelName]; !exclude {
128 labelNames = append(labelNames, labelName)
129 }
130 }
131 if len(labelNames) == 0 {
132 return emptyLabelSignature
133 }
134 sort.Sort(labelNames)
135
136 sum := hashNew()
137 for _, labelName := range labelNames {
138 sum = hashAdd(sum, string(labelName))
139 sum = hashAddByte(sum, SeparatorByte)
140 sum = hashAdd(sum, string(m[labelName]))
141 sum = hashAddByte(sum, SeparatorByte)
142 }
143 return sum
144}