1 // 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
6 // http://www.apache.org/licenses/LICENSE-2.0
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.
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).
23 const SeparatorByte byte = 255
26 // cache the signature of an empty label set.
27 emptyLabelSignature = hashNew()
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.)
33 func LabelsToSignature(labels map[string]string) uint64 {
35 return emptyLabelSignature
38 labelNames := make([]string, 0, len(labels))
39 for labelName := range labels {
40 labelNames = append(labelNames, labelName)
42 sort.Strings(labelNames)
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)
54 // labelSetToFingerprint works exactly as LabelsToSignature but takes a LabelSet as
55 // parameter (rather than a label map) and returns a Fingerprint.
56 func labelSetToFingerprint(ls LabelSet) Fingerprint {
58 return Fingerprint(emptyLabelSignature)
61 labelNames := make(LabelNames, 0, len(ls))
62 for labelName := range ls {
63 labelNames = append(labelNames, labelName)
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)
74 return Fingerprint(sum)
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.
80 func labelSetToFastFingerprint(ls LabelSet) Fingerprint {
82 return Fingerprint(emptyLabelSignature)
86 for labelName, labelValue := range ls {
88 sum = hashAdd(sum, string(labelName))
89 sum = hashAddByte(sum, SeparatorByte)
90 sum = hashAdd(sum, string(labelValue))
93 return Fingerprint(result)
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.
100 func SignatureForLabels(m Metric, labels ...LabelName) uint64 {
101 if len(labels) == 0 {
102 return emptyLabelSignature
105 sort.Sort(LabelNames(labels))
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)
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.
120 func SignatureWithoutLabels(m Metric, labels map[LabelName]struct{}) uint64 {
122 return emptyLabelSignature
125 labelNames := make(LabelNames, 0, len(m))
126 for labelName := range m {
127 if _, exclude := labels[labelName]; !exclude {
128 labelNames = append(labelNames, labelName)
131 if len(labelNames) == 0 {
132 return emptyLabelSignature
134 sort.Sort(labelNames)
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)