signature.go

Documentation: github.com/prometheus/common/model

     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  // cache the signature of an empty label set.
    26  var emptyLabelSignature = hashNew()
    27  
    28  // LabelsToSignature returns a quasi-unique signature (i.e., fingerprint) for a
    29  // given label set. (Collisions are possible but unlikely if the number of label
    30  // sets the function is applied to is small.)
    31  func LabelsToSignature(labels map[string]string) uint64 {
    32  	if len(labels) == 0 {
    33  		return emptyLabelSignature
    34  	}
    35  
    36  	labelNames := make([]string, 0, len(labels))
    37  	for labelName := range labels {
    38  		labelNames = append(labelNames, labelName)
    39  	}
    40  	sort.Strings(labelNames)
    41  
    42  	sum := hashNew()
    43  	for _, labelName := range labelNames {
    44  		sum = hashAdd(sum, labelName)
    45  		sum = hashAddByte(sum, SeparatorByte)
    46  		sum = hashAdd(sum, labels[labelName])
    47  		sum = hashAddByte(sum, SeparatorByte)
    48  	}
    49  	return sum
    50  }
    51  
    52  // labelSetToFingerprint works exactly as LabelsToSignature but takes a LabelSet as
    53  // parameter (rather than a label map) and returns a Fingerprint.
    54  func labelSetToFingerprint(ls LabelSet) Fingerprint {
    55  	if len(ls) == 0 {
    56  		return Fingerprint(emptyLabelSignature)
    57  	}
    58  
    59  	labelNames := make(LabelNames, 0, len(ls))
    60  	for labelName := range ls {
    61  		labelNames = append(labelNames, labelName)
    62  	}
    63  	sort.Sort(labelNames)
    64  
    65  	sum := hashNew()
    66  	for _, labelName := range labelNames {
    67  		sum = hashAdd(sum, string(labelName))
    68  		sum = hashAddByte(sum, SeparatorByte)
    69  		sum = hashAdd(sum, string(ls[labelName]))
    70  		sum = hashAddByte(sum, SeparatorByte)
    71  	}
    72  	return Fingerprint(sum)
    73  }
    74  
    75  // labelSetToFastFingerprint works similar to labelSetToFingerprint but uses a
    76  // faster and less allocation-heavy hash function, which is more susceptible to
    77  // create hash collisions. Therefore, collision detection should be applied.
    78  func labelSetToFastFingerprint(ls LabelSet) Fingerprint {
    79  	if len(ls) == 0 {
    80  		return Fingerprint(emptyLabelSignature)
    81  	}
    82  
    83  	var result uint64
    84  	for labelName, labelValue := range ls {
    85  		sum := hashNew()
    86  		sum = hashAdd(sum, string(labelName))
    87  		sum = hashAddByte(sum, SeparatorByte)
    88  		sum = hashAdd(sum, string(labelValue))
    89  		result ^= sum
    90  	}
    91  	return Fingerprint(result)
    92  }
    93  
    94  // SignatureForLabels works like LabelsToSignature but takes a Metric as
    95  // parameter (rather than a label map) and only includes the labels with the
    96  // specified LabelNames into the signature calculation. The labels passed in
    97  // will be sorted by this function.
    98  func SignatureForLabels(m Metric, labels ...LabelName) uint64 {
    99  	if len(labels) == 0 {
   100  		return emptyLabelSignature
   101  	}
   102  
   103  	sort.Sort(LabelNames(labels))
   104  
   105  	sum := hashNew()
   106  	for _, label := range labels {
   107  		sum = hashAdd(sum, string(label))
   108  		sum = hashAddByte(sum, SeparatorByte)
   109  		sum = hashAdd(sum, string(m[label]))
   110  		sum = hashAddByte(sum, SeparatorByte)
   111  	}
   112  	return sum
   113  }
   114  
   115  // SignatureWithoutLabels works like LabelsToSignature but takes a Metric as
   116  // parameter (rather than a label map) and excludes the labels with any of the
   117  // specified LabelNames from the signature calculation.
   118  func SignatureWithoutLabels(m Metric, labels map[LabelName]struct{}) uint64 {
   119  	if len(m) == 0 {
   120  		return emptyLabelSignature
   121  	}
   122  
   123  	labelNames := make(LabelNames, 0, len(m))
   124  	for labelName := range m {
   125  		if _, exclude := labels[labelName]; !exclude {
   126  			labelNames = append(labelNames, labelName)
   127  		}
   128  	}
   129  	if len(labelNames) == 0 {
   130  		return emptyLabelSignature
   131  	}
   132  	sort.Sort(labelNames)
   133  
   134  	sum := hashNew()
   135  	for _, labelName := range labelNames {
   136  		sum = hashAdd(sum, string(labelName))
   137  		sum = hashAddByte(sum, SeparatorByte)
   138  		sum = hashAdd(sum, string(m[labelName]))
   139  		sum = hashAddByte(sum, SeparatorByte)
   140  	}
   141  	return sum
   142  }
   143
View as plain text