cubefs

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

14
package model
15

16
import (
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).
23
const SeparatorByte byte = 255
24

25
var (
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.)
33
func 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.
56
func 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.
80
func 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.
100
func 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.
120
func 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