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