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
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}
145